离散数学N元集合关系个数计算

Author ：ssjs

Mail ：632141456@https://www.wendangku.net/doc/be7731217.html,

看了离散数学中的关系整理了一点关于n 元集合中各种关系的计算，现写下这个方便大家学习交流理解。对文章所致一切后果不负任何责任，请谨慎使用。

如有错误之处请指正。

定义：

1，对称：对于a,b R a b ∈∈∈),b (),a (,A 有如果只要

2，反对称：如果R a b R b a b b ∈∈=∈),(),(a ,A ,a 和时仅当

3，自反：如果对每个元素R ),(A a ∈∈a a 有

4，反自反：如果对于每个R ),(A a ?∈a a 有

5，传递：如果对R ),(,R ),(R ),(,A ,,∈∈∈∈c a c b b a c b a 则且

6，非对称：如果R ),(R ),(?∈a b b a 推出【注】其中是含（a,a)这样的有序对的。

【重要】集合A 的关系是从A 到A 的关系 （也就是说集合A 的关系是A A ?的子集）。

如下结论：

N 元集合上的自反关系数为：)1(2

-n n N 元集合上的对称关系数为：2/)1(2+n n

N 元集合上的反对称关系数为：2/)1(n 3

2-n n N 元集合上的非对称关系数为：2

/)1(3-n n N 元集合上的反自反关系数为：)1(n 2-n

N 元集合上的自反和对称关系数为：2/)1(n 2-n

N 元集合上的不自反也不反自反关系数为：)1(n n 222

2-?-n

下面是上面结论的计算

1，自反 2A A ,A n n =?=因为也就是说集合A 有n 平方个有序对，由自反定义可知，对R ),(A a ∈∈?a a 有所以n 个有序对()).....3,2,1i X ,X (n i i =其中一定在所求关系中，否则的话此关系就不是自反的了，那么还有n n -2个有序对，所以由集合子集对应二进制串可得自反关系数为)1(n 222--=n n n

下图有助于理解。

（1,1) (2,2).......(n,n) | (1,2) (1,3).........(n-1,n)

N 个有序对 n n -2

个有序对

2，对称 2A A ,A n n =?=因为也就是说集合A 有n 平方个有序对，由对称定义可知，对于R a b b ∈∈∈),b (),a (,A ,a 有只要。另外知道在n 平方个有序对中有n 个有序对()).....3,2,1i X ,X (n i i =其中，相应的就有n n -2

个有序对（X,Y)且X Y ≠，定义可知后面的n n -2个有序对只能成对出现，所以有2/)(n 2n -对。前面的那n 对可以出现任意多对。图片如下。 （1,1) (2,2).......(n,n) (1,2) (1,3).........(n-1,n)

n 个有序对 (2,1) (3,1).........(n,n-1)

(n n -2)/2个有序对对

共有n+ (n n -2)/2 个元素

即 (n n +2)/2个

所以得到对称关系数为：2/)1(2+n n

3，反自反

2A A ,A n n =?=因为也就是说集合A 有n 平方个有序对，由对称定义可知，如果对于每个R ),(A a ?∈a a 有，构成该关系的元素个数为n n -2个，所以得出结论)1(n 2-n ，这个简单，不多说。

4，自反和对称

即是求自反的又对称的，由1知要是自反的就只能在n n -2个有序对中生成子集，又由对称定义可知，将n n -2个有序对分成形如(a,b)与(b,a)的(n n -2)/2个有序对对。所以有自反和对称关系数为：2/)1(n 2-n 。如下图

（1,1) (2,2).......(n,n) (1,2) (1,3).........(n-1,n)

n 个有序对 (2,1) (3,1).........(n,n-1)

要自反这n 个必在所求关系中

(n n -2)/2个有序对对

N 个有序对只有1种可能· 有2/)1(n 2-n 种可能 = 2/)1(n 21-?n

5，不自反也不反自反

不自反也不反自反 = 不自反 不反自反

= ）不反自反不自反（ -2n 2

= 反自反）（自反 -2n 2

= )22(2)1()1(n 2--+-n n n n

= )1(n 2222-?-n n

6，非对称

由定义：如果R ),(R ),(?∈a b b a 推出，很清楚形如(a,a)的有序对不在所求关系中。所以所求关系只能中剩下的n n -2个有序对中来生成。如下图。 （1,1) (2,2).......(n,n) (1,2) (1,3)...................................(n-1,n)

n 个有序对 (2,1) (3,1)....................................(n,n-1)

这n 个一定不在所求关系中 (n n -2 )/2个有序对对

由定义上图的同色对中只能取一个或是一个也不取，就有三种状态1）选上面的 2）选下面的 3）两个都不选

选取同色对？

0 1

不选 选上还是选下？

0 1

选上 选下

由题知，不选，选上，选下是三种互斥结果。同集合二进制求集合个数原理，可得集合子集个为：2/)1(3-n n

7，反对称

由定义：如果R a b R b a b b ∈∈=∈),(),(a ,A ,a 和时仅当 如下图。

（1,1) (2,2)......................(n,n) (1,2) (1,3)...................................(n-1,n)

n 个有序对 (2,1) (3,1)...................................(n,n-1)

这n 个有序对可以出现任意多次 (n n -2 )/2个有序对对

n 2 ? 2/)1(3-n n (由6可知）

所以得结果 ：n 2?2/)1(3-n n 即2/)1(n 32-n n

【注】其它组合或是要求可由定义同理推出。不要怕麻烦，其实不那么难，也还有许多方法可以导出结果，如矩阵之类的。强烈推荐看下Discrete Mathematics and Its Applications Seventh Edition 更新版的更好哈，讲得真的很不错。

参考资料：Discrete Mathematics and Its Applications SeventhEdition

离散数学(集合论)课后总结

第三章集合论基础 1、设A={a,{a},{a,b},{{a,b},c}}判断下面命题的真值。 ⑴{a}∈A T ⑵?({a}? A) F ⑶c∈A F ⑷{a}?{{a,b},c} F ⑸{{a}}?A T ⑹{a,b}∈{{a,b},c} T ⑺{{a,b}}?A T ⑻{a,b}?{{a,b},c} F ⑼{c}?{{a,b},c} T ⑽({c}?A)→(a∈Φ) T 2、证明空集是唯一的。（性质1：对于任何集合A，都有Φ?A。） 证明：假设有两个空集Φ1 、Φ2 ，则 因为Φ1是空集，则由性质1得Φ1 ?Φ2 。 因为Φ2是空集，则由性质1得Φ2 ?Φ1 。 所以Φ1=Φ2 。 3、设A={Φ},B=P(P(A)).问：(这道题要求知道幂集合的概念) a)是否Φ∈B?是否Φ?B? b)是否{Φ}∈B? 是否{Φ}?B? c)是否{{Φ}}∈B? 是否{{Φ}}?B? 解：设A={Φ}，B=P(P(A)) P(A)= {Φ,{Φ}} 在求P(P(A))时，一些同学对集合{Φ,{Φ}}难理解，实际上你就将{Φ,{Φ}}中的元素分别看成Φ=a ,{Φ}=b, 于是{Φ,{Φ}}={a,b} B=P(P(A))=P({a,b}) ={B0, B1 , B2 , B3 }={B00, B01,B10 ,B11}={Φ, {b}, {a}, {a,b}} 然后再将a,b代回即可B=P(P(A))=P({Φ,{Φ}})={Φ,{Φ} ,{{Φ}}, {Φ,{Φ}}} 以后熟悉后就可以直接写出。 a) Φ∈B Φ?B b) {Φ}∈B {Φ} ? B c) {{Φ}}∈B {{Φ}}?B a)、b)、c)中命题均为真。 4、证明A?B ? A∩B=A成立。 证明：A∩B=A ??x(x∈A∩B ?x∈A) ??x((x∈A∩B → x∈A)∧(x∈A→ x∈A∩B)) ??x((x?A∩B∨x∈A)∧(x?A∨x∈A∩B)) ??x((?(x∈A∧x∈B)∨x∈A)∧(x?A∨(x∈A∧x∈B)) ??x(((x?A∨x?B)∨x∈A)∧(x?A∨(x∈A∧x∈B))) ??x(T∧(T∧( x?A∨x∈B))) ??x( x?A∨x∈B)??x(x∈A→x∈B)? A?B 5、(A-B)-C=(A-C)-(B-C) 证明：任取x∈(A-C)-(B-C) ?x∈(A-C)∧x?(B-C) ?(x∈A∧x?C)∧?(x∈B∧x?C) ?(x∈A∧x?C)∧(x?B∨x∈C) ?(x∈A∧x?C∧x?B)∨(x∈A∧x?C∧x∈C) ?x∈A∧x?C∧x?B?x∈A∧x?B∧x?C ?(x∈A∧x?B)∧x?C ?x∈A-B∧x?C?x∈(A-B)-C 所以(A-B)-C=(A-C)-(B-C)

离散数学测试(集合论)

《离散数学》单元测试（集合论） 3.1集合的基本概念 1.设Ａ、Ｂ、Ｃ是集合，确定下列命题是否正确，说明理由。 （1）Ф?Ф （2）Ф∈Ф （3）Ф?{Ф} （4）Ф∈{Ф} （5）如果A∈B与B?C,则A?C （6）如果A∈B与B?C,则A∈C （7）如果A?B与B∈C,则A∈C （8）如果A?B与B∈C,则A?C 2.有n个元素的集合Ａ的幂集ρ(A)的元素个数为多少？求下列集合的幂集合。 （1）Ф （2）{Ф} （3）{Ф,{Ф}} （4）{a,b} （5）{a,b,{a,b}} （6）{1，{1}，2，{2}} 3.2 集合的运算 1.设A，B是两个集合，A={1，2，3}，B={2，3，4}，则B－A= ，ρ（B）－ ρ（A）= 。 2.全集E={a，b，c，d，e}，A={a，d}，B={a，b，e}，C={b，d}，求 ，ρ（A）∩ρ（B） A B C= () = 。 3.下列命题正确的是（）。 A．φ∩{φ}=φB．φ∪{φ}=φC．{a}∈{a，b，c} D．φ∈{a，b，c} 4.确定下列各式的值： Ф∩{Ф}＝ {Ф,{Ф}}－Ф＝ {Ф,{Ф}}－{Ф}＝ 6.证明下列各等式： A∩(B－A)＝Ф A∪(A∩B)＝A 3.3 有穷集合的计数问题 掌握文氏图和容斥原理求解有穷集合的计数问题的方法，并会简单应用。以教材的示例为基础。

第4章 二元关系 4.1二元关系的定义、表示方法与特性 1. A 和B 是任意两个集合，若序偶的第一个元素是A 的一个元素，第二个元素是B 的一个 元素，则所有这样的序偶集合称为集合A 和B 的 ， 记作A ?B ，即A ?B= 。A ?B 的子集R 称为A 到B 的一个 。若|A|=m ， B|=n ，则A 到B 共有 个不同的二元关系。 2. 设集合A ＝{a,b},B ＝{x,y},求笛卡尔乘积A ×B,B ×A,,A ×ρ(B)。 3. 证明： (1) (A ∩B)×C=(A ×C)∩(B ×C) (2) (A ∪B)×C=(A ×C)∪(B ×C) 4. 设A={a,b},B={x,y},则从A 到B 的二元关系共有多少个？请分别列出。 5. 设集合A={a,b,c,d},B={1,2,3},R 是A 到B 的二元关系，R={,,,,,},写出R 的关系矩阵和关系图。 6. 设集合 A={1，2，3}，A 上的关系R={<1，1>， <1，2>， <2，2>， <3，3>， <3，2>}，则R 不具备（ ）。 A 自反性 B. 反自反性 C. 对称性 D. 反对称性 E. 传递性 7. 设集合A={a,b,c},R 是A 上的二元关系，R={〈a,a 〉,〈a,b 〉,〈a,c 〉,〈c,a 〉}，那么R 具备（ ）。 A 自反性 B. 反自反性 C. 对称性 D. 反对称性 E. 传递性 4.2 关系的运算（合成、逆运算、闭包运算） 1． 集合A={a 1,a 2,a 3},B={b 1,b 2,b 3,b 4},C={c 1,c 2,c 3,c 4}; R 是A 到B 的二元关系，R={,,,,}; S 是B 到C 的二元关系，S={,,,,}。 求复合关系R оS 。 2． 设集合{1,2,,10}A = ，A 上的二元关系R={|x,y ∈A,x+3y=12}，试求R n 。 3． 设R ，S 是二元关系，证明：111)(---=R S S R 。 4． 集合},,,{d c b a R =，R 是集合A 上的关系，{,,,,,}R a b b a b c =<><><>，求 )(),(),(R t R s R r ，并分别画出它们的关系图。 4.3 等价关系及划分 1. R 是集合A 上的二元关系，如果关系R 同时具有 性、 性 和 性，则称R 是等价关系。 2. R 是集合A={a ，b ，c ，d ，e ，f }是上的二元关系， R={〈a ，d 〉，〈d ，a 〉，〈a ，e 〉，〈e ，a 〉， ，，，}∪I A

应用离散数学-集合与关系

集合与关系《应用离散数学》 第3章 21世纪高等教育计算机规划教材

目录 3.1 集合及其运算 3.2 二元关系及其运算3.3 二元关系的性质与闭包3.4 等价关系与划分 3.5 偏序关系与拓扑排序3.6 函 数 3.7 集合的等势与基数3.8 多元关系及其应用

集合是现代数学中最重要的基本概念之一，数学概念的建立由于使用了集合而变得完善并且统一起来。集合论已成为现代各个数学分支的基础，同时还渗透到各个科学技术领域，成为不可缺少的数学工具和表达语言。对于计算机科学工作者来说，集合论也是必备的基础知识，它在开关理论、形式语言、编译原理等领域中有着广泛的应用。 本章首先介绍集合及其运算，然后介绍二元关系及其关系矩阵和关系图，二元关系的运算、二元关系的性质、二元关系的闭包，等价关系与划分、函数，最后介绍多元关系及其在数据库中的应用等。

3.1 集合及其运算 3.1.1 基本概念 集合是数学中最基本的概念之一，如同几何中的点、线、面等概念一样，是不能用其他概念精确定义的原始概念。集合是什么呢？直观地说，把一些东西汇集到一起组成一个整体就叫做集合，而这些东西就是这个集合的元素或叫成员。 例3.1 （1）一个班级里的全体学生构成一个集合。 （2）平面上的所有点构成一个集合。 （3）方程 的实数解构成一个集合。 （4）自然数的全体（包含0）构成一个集合，用N表示。 （5）整数的全体构成一个集合，用Z表示。 （6）有理数的全体构成一个集合，用Q表示。 （7）实数的全体构成一个集合，用R表示。

（8）复数的全体构成一个集合，用C表示。 （9）正整数集合Z+，正有理数集合Q+，正实数集合R+。（10）非零整数集合Z*，非零有理数集合Q*，非零实数集合R*。（11）所有n 阶(n≥2)实矩阵构成一个集合，用M n(R)表示，即

7离散数学(集合的运算)实验报告

大连民族学院 计算机科学与工程学院实验报告 实验题目：集合的运算 课程名称：离散数学 实验类型：□演示性□验证性□操作性□设计性□综合性专业：网络工程班级：网络111班 学生姓名：张山学号：2011083123 实验日期：2013年12月22日实验地点：I区实验机房 实验学时：8小时实验成绩： 指导教师签字：年月日老师评语：

实验题目：集合的运算 实验原理： 1、实验内容与要求： 实验内容：本实验求两个集合间的运算，给定两个集合A、B，求集合A与集合B之间的交集、并集、差集、对称差集和笛卡尔乘积。 实验要求：对于给定的集合A、B。用C++/C语言设计一个程序（本实验采用C++），该程序能够完成两个集合间的各种运算，可根据需要选择输出某种运算结果，也可一次输出所有运算结果。 2、实验算法： 实验算法分为如下几步： （1）、设计整体框架 该程序采取操作、打印分离（求解和输出分开）的思想。即先设计函数求解各部分运算并将相应结果传入数组（所求集合）中，然后根据需要打印运算结果。 （2）、建立一个集合类（Gather） 类体包括的数组a、b、c、d、e、f、g分别存储集合A、B以及所求各种运算的集合。接口（实现操作的函数）包括构造函数，菜单显示函数，求解操作函数，打印各种运算结果等函数。 （3）、设计类体中的接口 构造函数：对对象进行初始化，建立集合A与集合B。 菜单显示函数：设计提示选项，给使用者操作提示。 操作函数：该函数是程序的主题部分，完成对集合的所有运算的求解过程，并将结果弹入（存入）对应数组（集合）中，用于打印。 具体操作如下：

1*求交集：根据集合中交集的定义，将数组a、b中元素挨个比较，把共同元素选出来，并存入数组c（交集集合）中，即求得集合A、B的交集。 2*求并集：根据集合中并集的定义，先将数组a中元素依次存入数组g（并集集合）中，存储集合A中某元素前，先将其与已存入g中的元素依次比较，若相同则存入下一个元素，否则直接存入g中，直到所有A中元素存储完毕。接着把b中元素依次存入数组g（并集集合）中，存储前将b中每个元素依次与已存入数组g中的集合A的元素比较，若数组g中没有与该元素相同的元素，则将该元素存入g（并集集合）中，否则进行下一次比较，直到所有b中元素比较并存储完毕，即求得A与B 的并集。 3*求差集：根据集合中差集的定义知，差集分为两部分，A对B的差集（数组d）和B对A的差集（e）。设计求解A对B的差集，将集合A中元素依次与B中元素比较，若B中无元素与该元素相同，则将其存入数组d中（同时删除d中相同的元素，操作方法与求并集时删除相同元素类似），否则进行下一轮比较，直到A中所有元素比较完毕，即求得A对B的差集（数组d）。求解B对A的差集方法与求解A对B 的差集类似，这里不再重复。 4*求对称差：根据集合中对称差集的定义，将3*中所求两部分差集求并集并存入数组f中即可。操作过程与求并集相似，这里不再重复。 5*求笛卡尔乘积：根据集合中笛卡尔乘积集的定义，分为A*B和B*A。先设计A*B是我算法，将a中元素循环依次与b中元素配对即可。求B*A与求A*B类似，这里不再重复。 实验步骤： 一、分析实验 阅读实验指导书和离散数学课本，充分理解整个实验的实验内容及要求，以便对实验进行科学的设计。然后对整个实验进行“解剖”，即把整个实验系统地分成若干

离散数学集合论部分测试题

离散数学集合论部分测试题

离散数学集合论部分综合练习 本课程综合练习共分3次，分别是集合论部分、图论部分、数理逻辑部分的综合练习，这3次综合练习基本上是按照考试的题型安排练习题目，目的是通过综合练习，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次是集合论部分的综合练习。 一、单项选择题 1．若集合A={a，b}，B={ a，b，{ a，b }}，则（）． A．A?B，且A∈B B．A∈B，但A?B C．A?B，但A?B D．A?B，且A?B 2．若集合A＝{2，a，{ a }，4}，则下列表述正确的是( )． A．{a，{ a }}∈A B．{ a }?A C．{2}∈A D．?∈A 3．若集合A＝{ a，{a}，{1，2}}，则下列表述正确的是( )． A．{a，{a}}∈A B．{2}?A C．{a}?A D．?∈A 4．若集合A={a，b，{1，2 }}，B={1，2}，则（）． A．B? A，且B∈A B．B∈ A，但B?A C．B ? A，但B?A D．B? A，且B?A 5．设集合A = {1, a }，则P(A) = ( )． A．{{1}, {a}} B．{?,{1}, {a}} C．{?,{1}, {a}, {1, a }} D．{{1}, {a}, {1, a }} 6．若集合A的元素个数为10，则其幂集的元素个数为（）． A．1024 B．10 C．100 D．1 7．集合A={1, 2, 3, 4, 5, 6, 7, 8}上的关系R={|x+y=10且x, y∈A}，则R 的性质为（）． A．自反的B．对称的 C．传递且对称的D．反自反且传递的 8．设集合A = {1，2，3，4，5，6 }上的二元关系R ={?a , b∈A , 且a +b = 8}，则R具有的性质为（）． A．自反的B．对称的 C．对称和传递的D．反自反和传递的 9．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有（）个． A．0 B．2 C．1 D．3 10．设集合A={1 , 2 , 3 , 4}上的二元关系 R = {<1 , 1>，<2 , 2>，<2 , 3>，<4 , 4>}，

离散数学之集合论

第二篇集合与关系 集合论是现代各科数学的基础，它是德国数学家康托（Geog Cantor, 1845～1918）于1874年创立的，1876～1883年康托一系列有关集合论的文章，对任意元的集合进行了深入的探讨，提出了关于基数、序数和良序集等理论，奠定了集合论深厚的基础，19世纪90年代后逐渐为数学家们采用，成为分析数学、代数和几何的有力工具。 随着集合论的发展，以及它与数学哲学密切联系所作的讨论，在1900年前后出现了各种悖论，使集合的发展一度陷入僵滞的局面。1904～1908年，策墨罗（Zermelo）列出了第一个集合论的公理系统，它的公理，使数学哲学中产生的一些矛盾基本上得到了统一，在此基础上以后就逐渐形成了公理化集合论和抽象集合论，使该学科成为在数学中发展最为迅速的一个分支。 现在，集合论已经成为内容充实、实用广泛的一门学科，在近代数学中占据重要地位，它的观点已渗透到古典分析、泛函、概率、函数论、信息论、排队论等现代数学各个分支，正在影响着整个数学科学。集合论在计算机科学中也具有十分广泛的应用，计算机科学领域中的大多数基本概念和理论几乎均采用集合论的有关术语来描述和论证，成为计算机科学工作者必不可少的基础知识。集合论可作为数学学科的通用语言，一切必要的数据结构都可以利用集合这个原始数据结构而构造出来，计算机科学家或许也可以利用这种方法。 本篇介绍集合论的基础知识，主要内容包括集合及其运算、性质、序偶、关系、映射、函数、基数等。 第2-1章集合及其运算 §2-1-1 集合的概念及其表示 一、集合的概念 “集合”是集合论中的一个原始的概念，因此它不能被精确地定义出来。一般地说，把具有某种共同性质的许多事物，汇集成一个整体，就形成一个集合。构成这个集合的每一个事物称为这个集合的一个成员（或一个元素），构成集合的这些成员可以是具体东西，也可以是抽象东西。例如：教室内的桌椅；图书馆的藏书；全国的高等学校；自然数的全体；程序设计语言C的基本字符的全体等均分别构成一个集合。通常用大写的英文字母表示集合的名称；用小写的英文字母表示元素。若元素a属于集合A记作

离散数学集合论练习题

集合论练习题 一、选择题 1．设B = { {2}, 3, 4, 2}，那么下列命题中错误的是（ ）． A ．{2}∈ B B ．{2, {2}, 3, 4}B C ．{2}B D ．{2, {2}}B 2．若集合A ={a ，b ，{ 1，2 }}，B ={ 1，2}，则（ ）． A ． B A ，且BA B ．B A ，但BA C ．B A ，但BA D ．B A ，且BA 3．设集合A = {1, a }，则P (A ) = ( )． A ．{{1}, {a }} B ．{?,{1}, {a }} C ．{?,{1}, {a }, {1, a }} D ．{{1}, {a }, {1, a }} 4.已知AB ={1,2,3}, AC ={2,3,4},若2 B,则（ ） A ． 1?C B ．2? C C ．3?C D ．4?C 5. 下列选项中错误的是( ) A ． ??? B ． ?∈? C ． {}??? D ．{}?∈? 6. 下列命题中不正确的是（ ） A ． x {x }-{{x }} B ．{}{}{{}}x x x ?- C ．{}A x x =?,则xA 且x A ? D ． A B A B -=??= 7. A , B 是集合，P (A ),P (B )为其幂集，且A B ?=?，则()()P A P B ?=( ) A ． ? B ． {}? C ． {{}}? D ．{,{}}?? 8. 空集?的幂集()P ?的基数是( ) A ． 0 B ．1 C ．3 D ．4 9．设集合A = {1，2，3，4，5，6 }上的二元关系R ={a , b ∈A , 且a +b = 8}，则R 具有的性质为（ ）． A ．自反的 B ．对称的 C ．对称和传递的 D ．反自反和传递的

离散数学集合论部分测试题

离散数学集合论部分综合练习 本课程综合练习共分3次，分别是集合论部分、图论部分、数理逻辑部分的综合练习，这3次综合练习基本上是按照考试的题型安排练习题目，目的是通过综合练习，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次是集合论部分的综合练习。 一、单项选择题 1．若集合A={a，b}，B={ a，b，{ a，b }}，则（）． A．A?B，且A∈B B．A∈B，但A?B C．A?B，但A?B D．A?B，且A?B 2．若集合A＝{2，a，{ a }，4}，则下列表述正确的是( )． A．{a，{ a }}∈A B．{ a }?A C．{2}∈A D．?∈A 3．若集合A＝{ a，{a}，{1，2}}，则下列表述正确的是( )． A．{a，{a}}∈A B．{2}?A C．{a}?A D．?∈A 4．若集合A={a，b，{1，2 }}，B={1，2}，则（）． A．B? A，且B∈A B．B∈ A，但B?A C．B ? A，但B?A D．B? A，且B?A 5．设集合A = {1, a }，则P(A) = ( )． A．{{1}, {a}} B．{?,{1}, {a}} C．{?,{1}, {a}, {1, a }} D．{{1}, {a}, {1, a }} 6．若集合A的元素个数为10，则其幂集的元素个数为（）． A．1024 B．10 C．100 D．1 7．集合A={1, 2, 3, 4, 5, 6, 7, 8}上的关系R={|x+y=10且x, y∈A}，则R的性质为（）． A．自反的 B．对称的 C．传递且对称的 D．反自反且传递的 8．设集合A= {1，2，3，4，5，6 }上的二元关系R ={?a, b∈A, 且a +b = 8}，则R具有的性质为（）． A．自反的 B．对称的 C．对称和传递的 D．反自反和传递的 9．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有（）个． A．0 B．2 C．1 D．3 10．设集合A={1 , 2 , 3 , 4}上的二元关系 R = {<1 , 1>，<2 , 2>，<2 , 3>，<4 , 4>}，

离散数学集合论期末复习题

集合论期末复习题 1. 求(())P P φ 答：(()){,{}}P P φφφ= 2. 设||A n =，求|()|P A 答：|()|2n P A = 3. {,{}}________φφφ-=，{,{}}{}________φφφ-= 答：{,{}}φφ，{{}}φ 4. 证明：()()()A B C A B A C ?⊕=?⊕? 证明： () [()()] (~)(~) (~)(~) (~)(~)(~)(~)[()(~~)][()(~~)] [()~()][()~()] [()()][()()] ()() A B C A B C C B A B C C B A B C A C B A B A A B C A C B A C A A B A C A C B A A B A C A C A B A B A C A C A B A B A C ?⊕=?-?-=????=?????=???????????=???????=???????=?-???-?=?⊕? 5. 200人中，有67人学数学，47人学物理，95人学生物，26人学数学和生物，28人学数学和物理，27人学生物和物理，50人三门都不学，问：三门都学的人数和单学一门的人数？ 解：设三门都学的人数和单学数学、物理、生物的人数分别为x ，y1,y2,y3，则如下图： (26)(28)167(27)(28)247(26)(27)395 (26)(27)(28)12350200 x x x y x x x y x x x y x x x x y y y +-+-+=??+-+-+=??+-+-+=??-+-+-+++++=? 求解得到：1132228135342214123269364 y x x y x y y x y y y y x y -==????-=-=?????-==????++-==?? 6. 集合S={0,1,2,3,4,5,6}，R 为S 上的关系。R={|x

离散数学及其应用集合论部分课后习题答案

作业答案：集合论部分 P90:习题六 5、确定下列命题是否为真。 （2）?∈? （4）{}?∈? （6）{,}{,,,{,}}a b a b c a b ∈ 解答：（2）假（4）真（6）真 8、求下列集合的幂集。 （5）{{1,2},{2,1,1},{2,1,1,2}} （6）{{,2},{2}}? 解答： （5）集合的元素彼此互不相同，所以{2,1,1,2}{1,2}=，所以该题的结论应该为 {,{{1,2}},{{2,1,1}},{{1,2},{2,1,1}}}? （6）{,{{,2}},{{2}},{{,2},{2}}}??? 9、设{1,2,3,4,5,6}E =，{1,4}A =，{1,2,5}B =,{2,4}C =,求下列集合。 （1）A B （2）()A B 解答： （1）{1,4}{3,4,6}{4}A B == （2）(){1}{2,3,4,5,6}A B == 31、设A,B,C 为任意集合，证明 () ()()()A B B A A B A B --=- 证明： ()() {|}{|()()}{|()()()()} {|()()}{|()()}{|()()} {|()()}{|()(A B B A x x A B x B A x x A x B x B x A x x A x B x B x B x A x A x B x A x x A x B x B x A x x A B x A x B x x A B x A x B x x A B x B x x A B x A --=∈-∨∈-=∈∧?∨∈∧?=∈∨∈∧?∨∈∧∈∨?∧?∨?=∈∨∈∧?∨?=∈∧?∨?=∈∧∈∨∈=∈∧∈=∈∧∈)} B A B A B =-

离散数学疑难解析——集合论部分

离散数学疑难解析——集合论部分 第一章 集合 [集合的知识点] 1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、幂集 2、集合的交、并、差、补等运算及其运算律（交换律、结合律、分配律、吸收律、 De Morgan 律等），文氏（Venn ）图 3、序偶与迪卡尔积 [集合的疑难解析] 1．集合的概念 因为集合的概念大家在中学阶段已经学过，这里只多介绍了一个幂集的概念，所重点要对幂集加以掌握，一是掌握幂集的构成，一个集合A 的幂集是由A 的所有子集组成的集合。二是掌握幂集元数为2n ，其中n 是集合A 的元素个数。 2．集合恒等式的证明 通过对集合恒等式证明的练习，既可以加深对集合性质的理解与掌握；又可以为第三章命题逻辑中公式的基本等价式的应用打下良好的基础。实际上，本章做题是一种基本功训练，尤其要求学生重视吸收律和重要等价式在B A B A ~?=-证明中的特殊作用。 第二章 关系与映射 [二元关系的知识点] 1、关系、关系矩阵与关系图 2、复合关系与逆关系 3、关系的性质（自反性、对称性、反对称性、传递性） 4、关系的闭包（自反闭包、对称闭包、传递闭包） 5、等价关系与等价类 6、偏序关系与哈斯图（Hasse ）、极大/小元、最大/小元、上/下界、最小上界、最大下界 7、函数及其性质（单射、满射、双射） 8、复合函数与反函数 [二元关系疑难解析] 1．关系的概念 关系的概念是第二章全章的基础，又是第一章集合概念的应用。因此，大家应该真正理解并熟练掌握二元关系的概念及关系矩阵、关系图表示。 2．关系的性质及其判定 关系的性质既是对关系概念的加深理解与掌握，又是关系的闭包、等价关系、半序关系的基础。对于四种性质的判定，可以依据教材中P49上总结的规律。这其中对传递性的判定，难度稍大一点，这里要提及两点：一是不破坏传递性定义，可认为具有传递性。如空关系具有传递性，同时空关系具有对称性与反对称性，但是不具有自反性。另一点是介绍一种判定传递性的“跟踪法”，即若()()()R a a R a a R a a i i ∈∈∈-,, ,,,,13221 ，则()R a a i ∈,1。如若()()R a b R b a ∈∈,,,，则有()R a a ∈,，且()R b b ∈,。 3．关系的闭包

离散数学N元集合关系个数计算

Author ：ssjs Mail ： 看了离散数学中的关系整理了一点关于n 元集合中各种关系的计算，现写下这个方便大家学习交流理解。对文章所致一切后果不负任何责任，请谨慎使用。 如有错误之处请指正。 定义： 1，对称：对于a,b R a b ∈∈∈),b (),a (,A 有如果只要 2，反对称：如果R a b R b a b b ∈∈=∈),(),(a ,A ,a 和时仅当 3，自反：如果对每个元素R ),(A a ∈∈a a 有 4，反自反：如果对于每个R ),(A a ?∈a a 有 5，传递：如果对R ),(,R ),(R ),(,A ,,∈∈∈∈c a c b b a c b a 则且 6，非对称：如果R ),(R ),(?∈a b b a 推出【注】其中是含（a,a)这样的有序对的。 【重要】集合A 的关系是从A 到A 的关系 （也就是说集合A 的关系是A A ?的子集）。 如下结论： N 元集合上的自反关系数为：)1(2 -n n N 元集合上的对称关系数为：2/)1(2+n n N 元集合上的反对称关系数为：2/)1(n 3 2-n n N 元集合上的非对称关系数为：2/)1(3-n n N 元集合上的反自反关系数为：)1(n 2-n N 元集合上的自反和对称关系数为：2/)1(n 2-n N 元集合上的不自反也不反自反关系数为：)1(n n 222 2-?-n 下面是上面结论的计算 1，自反 2A A ,A n n =?=因为也就是说集合A 有n 平方个有序对，由自反定义可知，对R ),(A a ∈∈?a a 有所以n 个有序对()).....3,2,1i X ,X (n i i =其中一定在所求关系中，否则的话此关系就不是自反的了，那么还有n n -2个有序对，所以由集合子集对应二进制串可得自反关系数为)1(n 222--=n n n 下图有助于理解。 （1,1) (2,2).......(n,n) | (1,2) (1,3).........(n-1,n) N n n -2 个有序对

离散数学第三章集合的基本概念和运算知识点总结

集合论部分 第三章、集合的基本概念和运算 3.1 集合的基本概念集合的定义与表示 集合与元素 集合没有精确的数学定义 理解：一些离散个体组成的全体组成集合的个体称为它的元素或成员集合的表示 列元素法A={ a, b, c, d } 谓词表示法B={ x | P(x) } B 由使得P(x) 为真的x构成常用数集 N, Z, Q, R, C 分别表示自然数、整数、有理数、 实数和复数集合，注意0 是自然数. 元素与集合的关系：隶属关系 属于∈，不属于? 实例 A={ x | x∈R∧x2-1=0 }, A={-1,1} 1∈A, 2?A 注意：对于任何集合A 和元素x (可以是集合)， x∈A和x?A 两者成立其一，且仅成立其一.

集合之间的关系 包含（子集）A?B??x (x∈A→x∈B) 不包含A?B??x (x∈A∧x?B) 相等A = B?A?B∧B?A 不相等A≠B 真包含A?B?A?B∧A≠B 不真包含A?B 思考：≠和?的定义 注意∈和?是不同层次的问题 空集?不含任何元素的集合 实例{x | x2+1=0∧x∈R} 就是空集 定理空集是任何集合的子集 ??A??x (x∈?→x∈A) ?T 推论空集是惟一的. 证假设存在?1和?2，则?1??2 且?1??2，因此?1=?2全集E 相对性

在给定问题中，全集包含任何集合，即?A (A?E ) 幂集定义P(A) = { x | x?A } 实例 P(?) = {?}， P({?}) = {?,{?}} P({1,{2,3}})={?,{1},{{2,3}},{1,{2,3}}} 计数 如果|A| = n，则|P(A)| = 2n 3.2 集合的基本运算 集合基本运算的定义??-~⊕ 并A?B = { x | x∈A∨x∈B } 交A?B = { x | x∈A∧x∈B } 相对补A-B = { x | x∈A∧x?B } 对称差A⊕B = (A-B)?(B-A) = (A?B)-(A?B) 绝对补~A = E-A 文氏图（John Venn）

离散数学集合论练习题

集合论练习题 一、选择题 1.设B = { {2}, 3, 4, 2},那么下列命题中错误的就是( ). A.{2}∈B B.{2, {2}, 3, 4}?B C.{2}?B D.{2, {2}}?B 2.若集合A ={a ,b ,{ 1,2 }},B ={ 1,2},则( ). A.B ? A ,且B ∈A B.B ∈ A ,但B ?A C.B ? A ,但B ?A D.B ? A ,且B ?A 3.设集合A = {1, a },则P (A ) = ( ). A.{{1}, {a }} B.{?,{1}, {a }} C.{?,{1}, {a }, {1, a }} D.{{1}, {a }, {1, a }} 4、已知A ⊕B ={1,2,3}, A ⊕C ={2,3,4},若2∈ B,则( ) A. 1∈C B.2∈C C.3∈C D.4∈C 5、 下列选项中错误的就是( ) A. ??? B. ?∈? C. {}??? D.{}?∈? 6、 下列命题中不正确的就是( ) A. x ∈{x }-{{x }} B.{}{}{{}}x x x ?- C.{}A x x =?,则x ∈A 且x A ? D. A B A B -=??= 7、 A , B 就是集合,P (A ),P (B )为其幂集,且A B ?=?,则()()P A P B ?=( ) A. ? B. {}? C. {{}}? D.{,{}}?? 8、 空集?的幂集()P ?的基数就是( ) A. 0 B.1 C.3 D.4 9.设集合A = {1,2,3,4,5,6 }上的二元关系R ={?a , b ∈A , 且a +b = 8},则R 具有的性质为( ). A.自反的 B.对称的 C.对称与传递的 D.反自反与传递的 10、 设集合A ={1 , 2 , 3 , 4}上的二元关系

离散数学集合论部分常考××题

离散数学常考题型梳理 第2章关系与函数 一、题型分析 本章主要介绍关系的概念及运算、关系的性质与闭包运算、等价关系、相容关系和偏序关系三个重要关系、函数以及函数相关知识等内容。常涉及到的题型主要包括： 2-1关系的概念理解以及关系的并、交、补、差以及复合和逆关系等运算2-2关系自反和反自反、对称和反对称等性质的概念理解与判定；自反、对称和传递闭包运算。 2-3等价关系 2-4偏序关系和哈斯图 2-5 函数的概念和性质 因此，在本章学习过程中希望大家要清楚地知道： 1．有序对和笛卡尔积 （1）有序对：所谓有序对就是指一个有顺序的数组，如< x , y >，x , y的位置是确定的，且< a , b >< b , a >。 （2）笛卡尔积：把集合A，B合成集合A×B，规定： {,|} ?=<>∈∈ 且 A B x y x A y B 由于有序对< x , y >中x，y 的位置是确定的，因此A×B 的记法也是确定的，不能写成B×A 。 笛卡儿积的运算一般不满足交换律。 2．二元关系的概念和表示、几种特殊的关系和关系的运算 （1）二元关系的概念：二元关系是一个有序对集合，设集合A，B ，从集合A 到B的二元关系 R∈ x ∈ < y =且 > } , x {B | y A 记作xRy。 二元关系的定义域：A Ram? R ) (。 ) R Dom? (；二元关系的值域：B 二元关系R 是一个有序对组成的集合．因此，一个二元关系是一个集合，可以用集合形式表示；反过来说，一个集合未必是一个二元关系，仅当集合是由有序对元素组成的，才能当做二元关系。 常用关系的表示法包括了集合表示法、列举法、描述法、关系矩阵法和关系图法。关系矩阵和关系图是有限集合上的二元关系的表示方法。

离散数学 集合与关系 函数 习题 测验

一、已知A、B、C是三个集合，证明(A∪B)－C＝(A－C)∪(B－C) 证明：因为 x∈(A∪B)－C?x∈(A∪B)－C ?x∈(A∪B)∧x?C ?(x∈A∨x∈B)∧x?C ?(x∈A∧x?C)∨(x∈B∧x?C) ?x∈(A－C)∨x∈(B－C) ?x∈(A－C)∪(B－C) 所以，(A∪B)－C＝(A－C)∪(B－C)。 二、设R={<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>}，求r(R)、s(R)和t(R)，并作出它们及R的关系图。 解：r(R)={<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>} s(R)={<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，2>，<4，2>，<4，3>} R2=R5={<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>} R3={<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>} R4={<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>} t(R)={<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，1>，<5，4>， <5，5>} 三、证明等价关系 设R是集合A上的一个具有传递和自反性质的关系，T是A上的关系，使得∈T?∈R且∈R，证明T是一个等价关系。 证明因R自反，任意a∈A，有∈R，由T的定义，有∈T，故T自反。 若∈T，即∈R且∈R，也就是∈R且∈R，从而∈T，故T对称。 若∈T，∈T，即∈R且∈R，∈R且∈R，因R 传递，由∈R和∈R可得∈R，由∈R和∈R可得∈R，由∈R和∈R可得∈T，故T传递。 所以，T是A上的等价关系。 四、函数 设A、B、C、D是集合，f是A到B的双射，g是C到D的双射，令h：A×C→B×D且?∈A×C，h()＝。证明h是双射。 证明：1）先证h是满射。 ?∈B×D，则b∈B，d∈D，因为f是A到B的双射，g是C到D的双射，所以存在a∈A，c∈C，使得f(a)=b，f(c)=d，亦即存在∈A×C，使得h()＝

离散数学(集合地运算)实验报告材料

民族学院 计算机科学与工程学院实验报告 实验题目：集合的运算 课程名称：离散数学 实验类型：□演示性□验证性□操作性□设计性□综合性专业：网络工程班级：网络111班 学生：山学号：2011083123 实验日期：2013年12月22日实验地点：I区实验机房 实验学时：8小时实验成绩： 指导教师签字：年月日老师评语：

实验题目：集合的运算 实验原理： 1、实验容与要求： 实验容：本实验求两个集合间的运算，给定两个集合A、B，求集合A与集合B 之间的交集、并集、差集、对称差集和笛卡尔乘积。 实验要求：对于给定的集合A、B。用C++/C语言设计一个程序（本实验采用C++），该程序能够完成两个集合间的各种运算，可根据需要选择输出某种运算结果，也可一次输出所有运算结果。 2、实验算法： 实验算法分为如下几步： （1）、设计整体框架 该程序采取操作、打印分离（求解和输出分开）的思想。即先设计函数求解各部分运算并将相应结果传入数组（所求集合）中，然后根据需要打印运算结果。 （2）、建立一个集合类（Gather） 类体包括的数组a、b、c、d、e、f、g分别存储集合A、B以及所求各种运算的集合。接口（实现操作的函数）包括构造函数，菜单显示函数，求解操作函数，打印各种运算结果等函数。 （3）、设计类体中的接口 构造函数：对对象进行初始化，建立集合A与集合B。 菜单显示函数：设计提示选项，给使用者操作提示。 操作函数：该函数是程序的主题部分，完成对集合的所有运算的求解过程，并将结果弹入（存入）对应数组（集合）中，用于打印。 具体操作如下：

1*求交集：根据集合集的定义，将数组a、b中元素挨个比较，把共同元素选出来，并存入数组c（交集集合）中，即求得集合A、B的交集。 2*求并集：根据集合中并集的定义，先将数组a中元素依次存入数组g（并集集合）中，存储集合A中某元素前，先将其与已存入g中的元素依次比较，若相同则存入下一个元素，否则直接存入g中，直到所有A中元素存储完毕。接着把b中元素依次存入数组g（并集集合）中，存储前将b中每个元素依次与已存入数组g中的集合A的元素比较，若数组g中没有与该元素相同的元素，则将该元素存入g（并集集合）中，否则进行下一次比较，直到所有b中元素比较并存储完毕，即求得A与B 的并集。 3*求差集：根据集合中差集的定义知，差集分为两部分，A对B的差集（数组d）和B对A的差集（e）。设计求解A对B的差集，将集合A中元素依次与B中元素比较，若B中无元素与该元素相同，则将其存入数组d中（同时删除d中相同的元素，操作方法与求并集时删除相同元素类似），否则进行下一轮比较，直到A中所有元素比较完毕，即求得A对B的差集（数组d）。求解B对A的差集方法与求解A对B 的差集类似，这里不再重复。 4*求对称差：根据集合中对称差集的定义，将3*中所求两部分差集求并集并存入数组f中即可。操作过程与求并集相似，这里不再重复。 5*求笛卡尔乘积：根据集合中笛卡尔乘积集的定义，分为A*B和B* A。先设计A* B是我算法，将a中元素循环依次与b中元素配对即可。求B* A与求A* B类似，这里不再重复。 实验步骤： 一、分析实验 阅读实验指导书和离散数学课本，充分理解整个实验的实验容及要求，以便对实验进行科学的设计。然后对整个实验进行“解剖”，即把整个实验系统地分成若干部

离散数学集合运算C++或C语言实验报告

离散数学实验报告 专业班级：12级计算机本部一班姓名：鲍佳珍 学号：201212201401016 实验成绩： 1．【实验题目】 命题逻辑实验四 2．【实验目的】 掌握用计算机求集合的交、并、差和补运算的方法。 3．【实验内容】 编程实现集合的交、并、差和补运算。 4、【实验要求】 C或C＋＋语言编程实现 5.【算法描述】 （1）用数组A，B，C，E表示集合。假定A={1,3，4，5，6，7，9，10}, B={2，,3，4，7，8，10}, E={1,2，3，4，5，6，7，8，9，10}, 输入数组A，B，E（全集），输入数据时要求检查数据是否重复（集合中的数据要求不重复），要求集合A，B是集合E的子集。 以下每一个运算都要求先将集合C置成空集。 （2）二个集合的交运算：A?B={x|x∈A且x∈B} 把数组A中元素逐一与数组B中的元素进行比较，将相同的元素放在数组C 中，数组C便是集合A和集合B的交。 C语言算法： for(i=0;i

for(j=0;j int main(){