离散数学集合论部分

1、 对于从事计算机科学工作的人们来说，集对于从事计算机科学工作的人们来说，集合论是必不可少的基础知识。例如程序设计语合论是必不可少的基础知识。例如程序设计语言、数据结构、形式语言等都离不开子集、幂言、数据结构、形式语言等都离不开子集、幂集、集合的分类等概念。集合成员表和范式在集、集合的分类等概念。集合成员表和范式在逻辑设计、定理证明中也都有重要应用。逻辑设计、定理证明中也都有重要应用。 本部分从集合的直观概念出发，介绍了集本部分从集合的直观概念出发，介绍了集合论中的一些合论中的一些基本概念基本概念和和基本理论基本理论。 集合论是研究集合的一般性质的数学集合论是研究集合的一般性质的数学分支分支，它

2、研究集合不依赖于组成它的事物，它研究集合不依赖于组成它的事物的特性的性质。集合论总结出由各种对象的特性的性质。集合论总结出由各种对象构成的集合的共同性质，并用统一的方法构成的集合的共同性质，并用统一的方法来处理。来处理。 集合论的特点是研究对象的广泛性，集合论的特点是研究对象的广泛性，集合是各种不同对象的抽象，这些对象可集合是各种不同对象的抽象，这些对象可以是数或图形，也可以使任意其它事务。以是数或图形，也可以使任意其它事务。 1. 1. 二十六个英文字母可以看成是一个集合；二十六个英文字母可以看成是一个集合；2. 2. 所有的自然数看成是一个集合；所有的自然数看成是一个集合；3. 3. 重庆

3、邮电大学计算机学院重庆邮电大学计算机学院20102010级的本科学生可以看级的本科学生可以看成是一个集合；成是一个集合；4. 4. 这间教室中的所有座位可以看成是一个集合。这间教室中的所有座位可以看成是一个集合。 组成一个集合的那些对象或单元称为这组成一个集合的那些对象或单元称为这个集合的元素。个集合的元素。通常，用小通常，用小写的英文字母写的英文字母a, b, c,表示表示集合中的元素。元素可以是单个集合中的元素。元素可以是单个的数字也可以是字母，还可以是集合。的数字也可以是字母，还可以是集合。 如：如：A=a,c,b ; B=a,b,c设设A是一个集合，是一个集合，a是集合是集合A中的元素

4、，中的元素，元素与元素与集合的关系：集合的关系： 属于属于； 不属于不属于 若若a是集合是集合A中的元素记为中的元素记为a A，读作，读作a属于属于A；若若a不是集合不是集合A中的元素，则记为中的元素，则记为a A，读作，读作a不不属于属于A。 例如：例如：A是正偶数集合，则是正偶数集合，则2 A，4 A，6 A；而；而 1 A，3 A，19 A。特别注意：特别注意： 集合并不决定于它的元素展示方法。集合的元素集合并不决定于它的元素展示方法。集合的元素被重复或重新排列，集合并不改变，即被重复或重新排列，集合并不改变，即a, a ,b, c, d, c= a, b, c, d。集合的元素可以是具

5、体事物，可以是抽象概念，集合的元素可以是具体事物，可以是抽象概念，也可以是集体，如一本书，一支笔；集合也可以是集体，如一本书，一支笔；集合1,2,3可可以是集合以是集合B=一本书，一支笔，一本书，一支笔，1,2,3 的元素。的元素。特别地，以集合为元素的集合称为集合族或集合特别地，以集合为元素的集合称为集合族或集合类如类如A=1,2,3, 8,9,6。 集合中元素之间可以有某种关联，也可以彼此毫集合中元素之间可以有某种关联，也可以彼此毫无关系。无关系。 有限集有限集A 中所含元素的个数称为集合的中所含元素的个数称为集合的元数。记作：元数。记作：| A | 如：如： A =1,3,2,4,5,9

6、 则则 | A |= 6； 设设A是所有英文字母组成的集合，则是所有英文字母组成的集合，则 A=26。 特别，特别， | |=0列举法列举法(列元素法列元素法) ：将集合中的元素一一列举，将集合中的元素一一列举，或列出足够多的元素以反映集合中元素的特征，或列出足够多的元素以反映集合中元素的特征，例如：例如：V=a, b, c, d, e 或或 B=1,2,3, 4, 5,6,。 描述法描述法(谓词表示法谓词表示法) :将集合元素的条件或性将集合元素的条件或性质用文字或符号在花括号内竖线后面表示出来。质用文字或符号在花括号内竖线后面表示出来。A=x|关于关于x的一个命题的一个命题P; 如：如：B

7、=x|0 x10; B= x|x=a2,a是自然数是自然数。EAae文氏图文氏图 用一个大的矩形表示全集，在矩形内画一些圆或用一个大的矩形表示全集，在矩形内画一些圆或其它的几何图形，来表示集合，有时也用一些点来表其它的几何图形，来表示集合，有时也用一些点来表示集合中的特定元素。示集合中的特定元素。 例如：例如：集合集合A=a,b,c,d,e ，用，用文氏图文氏图表示如下表示如下:dcb几类特殊集合几类特殊集合:N=0,1,2,3,，即自然数集合。，即自然数集合。Z=,-2,-1,0,1,2,3,，即整数集合。，即整数集合。Z+=1,2,3,，即正整数集合。，即正整数集合。Q=有理数集合。有理数

8、集合。R=实数集合。实数集合。C=复数集合。复数集合。确定性；确定性；互异性；互异性；无序性；无序性；多样性；多样性； 任何一个对象，或者是这个集合的元素，或任何一个对象，或者是这个集合的元素，或者不是，二者必居其一；者不是，二者必居其一； 例如：例如：A=x| x是自然数，且是自然数，且x100； B=x| x+1=3； C=x| x是大学生是大学生。 集合中任何两个元素都是不同的，即集集合中任何两个元素都是不同的，即集合中不允许出现重复的元素。合中不允许出现重复的元素。 例如：例如： 集合集合A=a,b,c,c,b,dA=a,b,c,c,b,d，实际，实际 上，应该是上，应该是A=a,b,

9、c,dA=a,b,c,d 。 再如再如 1,2,3,2,4= 1,2,3,41,2,3,2,4= 1,2,3,4。 集合与其中的元素的顺序无关；集合与其中的元素的顺序无关； 例如：例如： 集合集合a,b,c,d,e、d,c,e,a,b、 e,c,d,b,a，都是表示同一个集合。都是表示同一个集合。 集合集合4,2,1,3 = 1,2,3,4。 集合中的元素可以是任意的对象，集合中的元素可以是任意的对象， 相互独立，相互独立，不要求一定要具备明显不要求一定要具备明显 的共同特征。的共同特征。 例如：例如： A=a,a,a,b,a, 1； A=1,a,*,-3,a,b,x| x是汽车是汽车,地球地

10、球 注意注意: 对于任何集合对于任何集合A, 都有都有A A。 设设A，B是两个集合，若是两个集合，若B的元素都是的元素都是A的元的元素，则称素，则称B是是A的的子集子集，也称，也称A包含包含B，或，或B被被A包包含，记以含，记以B A ，或，或A B 。 若若B A ，且，且A B，则称，则称B是是A的的真子集真子集，也，也称称A真包含真包含B ，或，或B真包含于真包含于A ，记以，记以A B，或，或B A 。例例3.1 设设A=a, b,c, a, a, b 试判断下列表达试判断下列表达式正确与否。式正确与否。（1）a A （2）a A （3）a A （4） A （5） A （6）b A（

11、7）b A （8）b A （9）a,b A (10) a,b A (11) c A (12) c A (13) c A (14) a,b,c A 。 解解：( (4)4)，(7)(7)，(11)(11)，(13), (14) (13), (14) 错误。错误。例例3.2 对于任意集合对于任意集合A, B和和C, 下述论断是否正确下述论断是否正确（1）若）若A B, B C 则则A C（2）若）若A B, B C 则则A C（3）若）若A B, B C 则则A C 解解：（：（1） （2） （3） 对对(3)举反例举反例 A= , B= 1, C= 1。例例3.3 设设A=1,2,3, 4,5,

12、 6,7,8 下列选项正确的是（下列选项正确的是（ 3 ）；）； （1） 1 A （2）1,2,3 A （3）4,5 A （4） A 例例3.4 下列各选项错误的是（下列各选项错误的是（2）；）； （1） （2） （3） （4） 例例3.5 在在0 _ 之间填上正确的符号：（之间填上正确的符号：（4） （1） = （2） （3） （4） 当两个集合当两个集合A A和和B B的元素完全一样，即的元素完全一样，即A A，B B实实际上是同一个集合时，则称集合际上是同一个集合时，则称集合A A，B B相等，记为相等，记为A=BA=B。 符号化表示为：符号化表示为： A=B A B B A 例：例：设

13、设A=x|x是偶数，且是偶数，且0 x10， B=2,4,6,8， 则则 A=B。注：注：说明两个集合说明两个集合A、B相等，需说明两相等，需说明两 个问题：个问题：1、A是集合是集合B的子集（的子集（A B） （任意元素（任意元素aA，有，有aB）2、B是集合是集合A的子集（的子集（A B） （任意元素（任意元素aB，有，有aA）集合的包含关系也可表成集合的包含关系也可表成A B( x)(x Ax B)这表明，要证明这表明，要证明A B，只需对任意元素，只需对任意元素x，有下式有下式 x Ax B成立即可。成立即可。 不含任何元素的集合叫做空集，记作不含任何元素的集合叫做空集，记作 。空集的

14、符号化表示为：空集的符号化表示为：=x | P(x)P(x) 。 其中其中P(x)为任何谓词公式。为任何谓词公式。 如：如：A=x|xR x2+1=0。 该方程无实数解。该方程无实数解。 注意：注意： 由定义可知，对任何集合由定义可知，对任何集合A，有，有A。这是因为任。这是因为任意元素意元素x，公式，公式xx A总是为真。总是为真。注意：注意： 与与是不同的。是不同的。 是以是以为元素的集合，为元素的集合， 而而没有任何元素，能用没有任何元素，能用构成集合的无限序列：构成集合的无限序列：，该序列除第一项外，每项均以前一项为元素的集合。该序列除第一项外，每项均以前一项为元素的集合。定理：定理：

15、空集是一切集合的子集。空集是一切集合的子集。 证明：证明：对于任何集合对于任何集合A，由子集定义有，由子集定义有 , A x(x xA) 右边的蕴涵式中前件为右边的蕴涵式中前件为x为假，所以整个为假，所以整个蕴涵式对一切蕴涵式对一切 x 为真，所以为真，所以 A为真为真推论推论：空集是唯一的。：空集是唯一的。 证明证明: 如不唯一如不唯一, 设存在空集设存在空集1和和2, 由由空集是空集是一切集合的子集一切集合的子集得得1 2 和和2 1 。根据集合相等。根据集合相等的定义得，的定义得， 1 = 2 如果一个集合包含了所要讨论的每一个如果一个集合包含了所要讨论的每一个集合，则称该集合为全集，记

16、为集合，则称该集合为全集，记为E 或或 U。它可形式地表为它可形式地表为 E =x | P(x)P(x)。其中。其中P(x)为任何谓词公式。为任何谓词公式。注意符号注意符号 和和 意义的区别：意义的区别： 表示元素与集合之间的关系，而表示元素与集合之间的关系，而 则表则表示集合与集合之间的关系。但由于集合的抽象示集合与集合之间的关系。但由于集合的抽象性，集合中的元素可以是集合，故可以发生如：性，集合中的元素可以是集合，故可以发生如：A B且且A B的情形的情形 例例 设设A=1,2,3, 1,2,3， 则则 1,2,3 A 且且 1,2,3 A 。 注意：注意：对任意集合对任意集合A, 有有A

17、 A。空集是任意集合的子集，且空集是唯一的。空集是任意集合的子集，且空集是唯一的。对于任意两个集合对于任意两个集合A、B，A=B的充的充 要条件是要条件是A B且且B A。（。（这个结论非常简单，但它非常重要，很多证这个结论非常简单，但它非常重要，很多证明都是用这个方法或思路来证明。）明都是用这个方法或思路来证明。）设设A 是集合，是集合，A的所有子集为元素做成的集的所有子集为元素做成的集合称为合称为A的的幂集幂集,记以记以P(A) 符号化表示为：符号化表示为： P(A)=x| x A。例：例： A=a,b,c ，则，则P(A)= ,a,b,c,a,b,a,c,b,c,a,b,c。例例3.6

18、设设 A=a, a 下列选项错误的是下列选项错误的是 A. a P(A) B. a P (A) C. a P(A) D. a P (A)例例3.7 幂集幂集P(P(P()为（为（C ） A. , B. , , C. , , , D. , , P(A)=P(A)=, a, a, a, a 例例3.8 判断下面的关系是否正确判断下面的关系是否正确,并简要说明理由。并简要说明理由。 a,b a,b,c, a,b,c a,b a,b,c, a,b,c a,b a,b, a,b a,b a,b,a,b 解答解答： 对选项对选项, 因为因为a,b 中每个元素中每个元素(只有只有a和和b)均在集合均在集合a

19、,b,c, a,b,c 对选项对选项, 因为因为a,b 中每个元素中每个元素(只有只有a和和b)均在集合均在集合a,b, a,b 对选项对选项 , 集合集合a,b,c, a,b,c中含有中含有4个元个元素，分别为素，分别为a, b, c, a,b,c没有没有a,b，所以不正确。，所以不正确。 对选项对选项, 集合集合a,b,a,b中含有中含有3个元素，个元素，分别为分别为a, b, a,b没有没有a,b，所以不正确。，所以不正确。1.若若A为有穷集，为有穷集，|A|=n，则，则|2A | = Cn0 + Cn1 + + Cnn =2n 。2.x P(A)当且仅当当且仅当x A。3.设设A、B是

20、两个集合，是两个集合，A B当且仅当当且仅当P(A) P(B)。并并 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 。 A B A A B A A B A B A-B A B A A B B C A B (A B)-C集合运算对应的文氏图表示集合运算对应的文氏图表示 并和交运算可以推广到有穷个集合上，即并和交运算可以推广到有穷个集合上，即 A1 A2 An= x | x A1 x A2 x An A

21、1 A2 An= x | x A1 x A2 x An某些重要结果：某些重要结果： A B A A B A B= A B= A B=A集合的广义交和广义并集合的广义交和广义并 设设S为集合，为集合，S的元素的元素构成的集合称的元素的元素构成的集合称为为S的的广义并广义并，记为，记为 S，其中，其中 S=xz(z S x z； 设设S非空集合，非空集合，S的元素的公共元素构成的的元素的公共元素构成的集合称为集合称为S的广义交，记为的广义交，记为 S，其中，其中 S=xz(z Sx z。说明：说明： （1 1）规定）规定 = = ， 无意义。无意义。 （2 2）若）若 ，则由定义不难证明，则由定义

22、不难证明 S=S= S=S=（3 3）并运算和广义并运算的运算符相同，但前者是二元运算，）并运算和广义并运算的运算符相同，但前者是二元运算，后者是一元运算，因此在运算过程中不会对后者是一元运算，因此在运算过程中不会对 产生误解。产生误解。123,nSS SSS123nSSSS123nSSSS 例：例：设集合设集合A=a,b,c,a,c,d,a,c,e，求，求 A， A，A，A，A，A。解：解： A=a,b,c,d,e； A=a,c； A=a b c d e； A=a c； A=a c； A=a b c d e 。优先级优先级 一般地, 一元运算符(补集,幂集,广义并,广义交)优先于优先于 二元

23、运算符(差集,并集,交集,对称差,笛卡儿积)； 二元运算符优先于优先于集合关系符(, , ) 。此外,许多集合表达式里还使用到联结词,和逻辑关系符以及括号,我们规定:(1) 集合运算优先于逻辑运算；(2) 括号内优先于括号外；(3) 同一括号内,同一优先级按从左至右运算。集合运算律集合运算律幂等律幂等律：AAA； AAA同一律同一律：AA； AE=A零零 律：律：AE=E ； A结合律：结合律：(AB)CA(BC)； (AB)CA(BC)交换律交换律：ABBA； ABBA分配律分配律：A（BC）（）（AB）(AC)； A(BC)=(AB)(AC)排中律：排中律：矛盾律：矛盾律：吸收律吸收律：A

24、（AB）A A(AB)A摩根律：摩根律：双重否定律双重否定律：AAEAAABABABAB()()()ABCABAC()()()ABCABACAA AB A , AB B ； A AB , B AB ； A-B A ，A-B=AB； AB=BA BAB=A A-B= ； A B=B A； (A B) C=A ( B C) A =A； A A = ； A B=A CB=C。集合集合等式的证明，可采用命题逻辑的等值式证明，等式的证明，可采用命题逻辑的等值式证明，其基本思想是其基本思想是互为子集互为子集： 欲证欲证:A=B 即证即证:即证即证:对任意的对任意的 x , ，当上述过程可逆时，可以合并为当

25、上述过程可逆时，可以合并为对任意的对任意的x, ABBAxAxBxBxAxAxB 集合相等的证明方法集合相等的证明方法例：例： 证明下列集合恒等式。证明下列集合恒等式。（1 1）AA（BCBC）（）（ABAB）(AC)(AC)（2 2）（3 3）证明：证明：(1) (1) 对任意的对任意的x xA (BC)A(BC)A()(A)(A)()()xxxxxBxCxxBxxCxABxACxABACABAB()()()ABCABAC(2) 对任意的对任意的xBA()xABxAxxxBxAB(3) 对任意的对任意的x()()()()()()()()()()()xABCxAxBCxAxBCxAxBxCxA

26、xBxCxAxBxAxCxABxACxABAC 例例3.3.2 证明：（证明：（1） （2）A B=（AB）-（AB）ABABAB()()()EABEAEBAB证明证明：(1)(2) AB=（A-B）（B-A）()()()()()()()()()()ABBAABAABBBAABABABAB例例 证明证明(AB)- C =(A-C)(B-C).证明证明: 对于对于 x x (AB)- C x (AB) x C ( x A xB ) x C ( x A x C) (xB x C) x ( A- C ) x ( B- C) x ( A-C) (B- C) (AB)- C =(A-C)(B-C)例例

27、证明证明证明：证明：(1)必要性必要性：对任意的：对任意的X,因此，因此， 。(2)充分性充分性：对任意的：对任意的x，因此因此 ，结论得证。，结论得证。( )( )ABP AP B( )( )xP AxAxBxP B( )( )P AP B ( ) ( ) xAxAxP AxP BxBxBAB例例 求在求在1和和1000之间不能被之间不能被5或或6，也不能被，也不能被8整整除的数的个数解：设除的数的个数解：设1到到1000之间的整数构成全之间的整数构成全集集E，A，B，C分别表示其中可被分别表示其中可被5，6或或8整除整除的数的集合。的数的集合。 解：解：在在ABC中的数一定可被中的数一定可

28、被5,6和和8的最小的最小公倍数公倍数 5,6,8 =120整除，即整除，即 ABC= 1000/ 5,6,8 =8 同样可得同样可得 AB= 1000/ 5,6 =33； AC= 1000/ 5,8 =25； BC= 1000/ 6,8 =41；然后计算然后计算 A= 1000/5 =200 ； B= 1000/6 =166 ； C= 1000/8 =125从而得到从而得到 ABC=200+100+33+67=400 所以，所以，不能被不能被5或或6,也不能被也不能被8整除的数有整除的数有600个。个。150100671733258对上述子集计数：对上述子集计数： |S|=1000； |A|

29、= 1000/5 =200； |B|= 1000/6 =133； |C|= 1000/8 =125； |A B|= 1000/30 =33； |B C| = 1000/40 =25 |B C|= 1000/24 =41； |A B C| = 1000/120 =8。 代入公式：代入公式： N = 1000 (200+133+125)+(33+25+41) 8=600。这个方法叫这个方法叫容斥原理。容斥原理。称为包含排斥原理，简称称为包含排斥原理，简称容斥原理容斥原理。容斥原理容斥原理定理：定理： 有穷集有穷集S中不具有中不具有p1,p2,pm元素数是元素数是1211121( 1)mmiiiji

30、ij mmijkmij k mAAASAAAAAAAAA mmkjikjijijimiimiiAAAAAAAAAA21111) 1(推论推论 设设A1,A2,An是是n个集合，则个集合，则 例例 某班有某班有2525个学生，其中个学生，其中1414人会打篮球，人会打篮球，1212人人会打排球，会打排球，6 6人会打篮球和排球，人会打篮球和排球，5 5人会打篮球人会打篮球和网球，还有和网球，还有2 2人会打这三种球。而人会打这三种球。而6 6个会打网个会打网球的人都会打另外一种球球的人都会打另外一种球( (指篮球或排球指篮球或排球) )，求，求不会打这三种球的人数。不会打这三种球的人数。解：解：

31、设会打排球、网球、篮球的学生集合设会打排球、网球、篮球的学生集合分别为分别为A，B 和和 C，则有，则有 A=12， B=6， C=14， S=25 AC=6，BC=5， ABC=2现在求现在求 AB，因为会打网球的人都会打另一种球，即篮，因为会打网球的人都会打另一种球，即篮球和排球，而其中会打篮球的有球和排球，而其中会打篮球的有5人，那么另一个人肯定人，那么另一个人肯定会打排球但不会打篮球，再加上会打三种球的会打排球但不会打篮球，再加上会打三种球的2人，共有人，共有3人会打排球和网球，即人会打排球和网球，即AB=3，根据容斥定理有，根据容斥定理有 ABC = 25-（12+6+14）+（3+

32、6+5）-2 = 5324排球排球1212篮球篮球1414网球网球6 6155不会打三种球人不会打三种球人数为：数为：25-(12+5+3)=5课堂练习：证明下列等式课堂练习：证明下列等式()ABAAB()ABABA()()ABCABC()AABB()()()()ABCDADBC( )( )ABP AP B( )( )()P AP BP AB( )( )()P AP BP AB第四章第四章 二元关系和函数二元关系和函数 说起关系这个词，对我们并不陌生，世界上存在说起关系这个词，对我们并不陌生，世界上存在着各种各样的关系，人与人之间的着各种各样的关系，人与人之间的“同志同志”关系；关系；“同学同

33、学”关系；关系；“朋友朋友”关系；关系；“师生师生”关系；关系；“上上下级下级”关系；关系；“父子父子”关系；两个数之间有关系；两个数之间有“大于大于”关系；关系；“等于等于”关系和关系和“小于小于”关系；两个变量之间关系；两个变量之间有一定的有一定的“函数函数”关系；计算机内两电路间有导线关系；计算机内两电路间有导线“连接连接”关系；程序间有关系；程序间有“调用调用”关系等等。所以对关系等等。所以对关系进行深刻的研究，对数学与计算机科学都有很大关系进行深刻的研究，对数学与计算机科学都有很大的用处。的用处。集合的笛卡尔积与二元关系集合的笛卡尔积与二元关系 由两个元素由两个元素x,y（允许（允许

34、x=y）按一定顺序排列成）按一定顺序排列成的二元组叫做一个的二元组叫做一个有序对或序偶有序对或序偶，记作，记作,其中其中x是是它的它的第一元素第一元素，y是它的是它的第二元素第二元素。有序对有序对具有以下性质：具有以下性质：(1) 当当xy时，时， (2) = x=w y=v例例：已知：已知 = ，求，求 x 和和 y。解：由有序对相等的充要条件得解：由有序对相等的充要条件得 x+3 = y+7 y-2 = 3y-x 解得解得 x = 6, y = 2。一个一个有序有序n元组元组 (n3)是一个有序对，其中第一个元素是一个有序对，其中第一个元素是一个有序是一个有序n-1元组，一个有序元组，一个

35、有序n元组记作元组记作,即即 = , xn 例：例：空间直角坐标系中点的坐标空间直角坐标系中点的坐标 ,等都是有序等都是有序3元组。元组。 n维空间中点的坐标或维空间中点的坐标或n维向量都是有序维向量都是有序n元组。元组。形式上也可以把形式上也可以把看成有序看成有序1元组。元组。 设设A，B为集合，用为集合，用A中元素为第一元素，中元素为第一元素，B中中元素为第二元素构成有序对。所有这样的有序对元素为第二元素构成有序对。所有这样的有序对组成的集合叫做组成的集合叫做A和和B的的笛卡儿积笛卡儿积，记作，记作AB。 笛卡儿积的符号化表示为：笛卡儿积的符号化表示为： AB=|x A yB例例：若：若A

36、=1,2, B=a,b,c,则则AB=, , , , , BA=, , , , , 易知：若易知：若|A|=m,(即集合即集合A的元素的个数的元素的个数),|B|=n,则则| AB|= |BA|= m n 有序对就是有顺序的数组有序对就是有顺序的数组，如，如，x,y 的的位置是确定的，不能随意放置。位置是确定的，不能随意放置。 注意注意：有序对：有序对 ，以，以a,b为元素的集合为元素的集合a,b=b,a；有序对；有序对(a,a)有意义，而集合有意义，而集合a,a不成立。不成立。 笛卡儿积是一种集合合成的方法笛卡儿积是一种集合合成的方法，把集合，把集合A，B合合成集合成集合AB，规定，规定AB

37、 x A, y B。由于有序对由于有序对中中x,y的位置是确定的，因此的位置是确定的，因此AB的的记法也是确定的，不能写成记法也是确定的，不能写成BA。笛卡儿积也可以多个集合合成笛卡儿积也可以多个集合合成 A1A2An。笛卡儿积的运算性质。笛卡儿积的运算性质。笛卡儿积的性质：笛卡儿积的性质：1、对任意集合、对任意集合A，根据定义有，根据定义有 A = A= 2、一般来说，笛卡儿积不满足交换律，即、一般来说，笛卡儿积不满足交换律，即 ABBA （当（当A B B 、A 时）时）3、笛卡儿积不满足结合律，即、笛卡儿积不满足结合律，即 (AB) CA(B C) （当（当ABC时）时）4、笛卡儿积运算

38、对并和交运算满足分配律，即、笛卡儿积运算对并和交运算满足分配律，即 A(BC)= (AB)(A C) (BC) A = (BA)(C A) A(BC)= (AB) (A C) (BC) A = (BA) (C A)例：例： 证明证明 (BC) A = (BA)(C A)对于对于 (BC) A x(B C) y A xB x C y A xB x C y A y A (xB y A) (x C y A) B A C A (BA) (C A) (BC) A = (BA) (C A)例例：设：设A， C， B， D为任意集合，为任意集合， 判断以下命题是否为真，并说明理由。判断以下命题是否为真，并说

39、明理由。(1) AB= AC =B= C。(2) A-(BC)=( A-B)(A-C)。(3) 存在集合存在集合A,使得使得A A A。解：解：(1) (1) 不一定为真。反例不一定为真。反例A=, BA=, B、C C为任意不相为任意不相 等的非空集合。等的非空集合。 (2) (2) 不一定为真。反例不一定为真。反例A=1, B=2, C=3.A=1, B=2, C=3. (3) (3) 为真。当为真。当 A= A= 时成立。时成立。 设设A1,A2,An,是集合是集合(n2),它们的它们的n阶笛卡儿积阶笛卡儿积记作记作A1A2An ，其中，其中 A1A2An= | x1 A1x2 A2xn

40、 An 。 当当A1=A2=An=A时时, 将起将起n阶笛卡儿积记作阶笛卡儿积记作An例例，A= a ,b , 则：则： A3=AAA=a,ba,ba,b =, , , 。例例：设集合：设集合 A=a,b,B=1,2,3,C=d, 求求ABC，BA。解：解： 先计算先计算AB,ABC ,d, BA, 。例：例： 设集合设集合A1,2,求求AP(A)。解：解： P(A)=,1,2,1,2AP(A)1,2,1,2,1,2=, , , 如果一个集合符合以下条件之一：如果一个集合符合以下条件之一：(1) 集合非空，且它的元素都是有序对集合非空，且它的元素都是有序对(2) 集合是空集集合是空集 则称该集

41、合为一个则称该集合为一个二元关系二元关系，记作，记作R，简称为关系。，简称为关系。 对于二元关系对于二元关系R，若，若 R,可记作可记作xRy;如果如果 R, 则记作则记作xRy。例例：R1=, aR1b, 1R12。二元关系二元关系是两种客体之间的联系，例如某学生是两种客体之间的联系，例如某学生学习语文、数学、外语，表示为：学习语文、数学、外语，表示为： A A 语文语文, , 数学数学, , 外语外语 功课的成绩分四个等级，记作功课的成绩分四个等级，记作B BAA，B B，C C，DD于是该生成绩的全部可能为于是该生成绩的全部可能为A AB BA AB B ,D, ,D, ,D而该生的实际

42、成绩而该生的实际成绩 P P,DP P是是A AB B的一个子集，它表示了功课与其成绩的一种关系。的一个子集，它表示了功课与其成绩的一种关系。 由此可见：由此可见：两个集合之间的二元关系，实际上就是两个两个集合之间的二元关系，实际上就是两个元素之间的某种相关性。元素之间的某种相关性。 设设A，B为集合，为集合，AB的任何子集所定义的的任何子集所定义的二元关系叫做从二元关系叫做从A到到B的的二元关系二元关系； 特别当特别当A=B时则叫做时则叫做A上的上的二元关系二元关系。 例：例：若若A=a,b，B=1,2,3，则，则 A B= , 令令 R1= , R2=, , R3=。因为因为R1 A B，

43、 R2 A B， R3 A B，所以，所以R1, R2和和 R3均是由均是由A到到B的二元关系。的二元关系。又例：若又例：若A=a,b，B=1,2,3，则，则 BA= , 令令 R4= , R5=, , 因为因为R4 BA， R5 BA，所以所以R4和和 R5均是由均是由B到到A的关系。的关系。又又 BB=, , , 。令令 R6= ，, R7=, 因为因为R6 BB， R7 BB， 所以所以R6和和 R7均是集合均是集合B上上的关系。的关系。若集合若集合|A|=n,则集合则集合A上的二元关系有多少个？上的二元关系有多少个？答：答： |A|=n，则，则|A A|=n2, A A的任一个子集的任

44、一个子集就是就是A上的二元关系，即上的二元关系，即P(A)= 2n 个。个。 例例 A= 1,2 则则A A有有 2n 个不同的二元关系；个不同的二元关系； AA=1,21,2= ,。 AA的任一个子集就是的任一个子集就是A A的幂集，即的幂集，即P(A)P(A)= , , , , , , , , , , , , , , , , , , , , , , , ,三类特殊的关系三类特殊的关系空关系：空关系：对于任何集合对于任何集合A，空集，空集 是是A A的的子集，称作子集，称作A上的上的空关系；空关系；全关系：全关系：定义定义EA=|xA yA= AA为为全全域关系；域关系；恒等关系：恒等关系：

45、 定义定义IA=|xA 为为A上上恒等关系。恒等关系。 例：例：若若A=1,2,3，则，则 EA= , , IA =, 。例：例：设设A=1,2,3,4，请表示下列关系。，请表示下列关系。(1) R= |x是是y的倍数的倍数(2) R= |(x-y)2 A(3) R= |x除除y是素数是素数(4) R= |xy解：解：(1) R = , , , , ,； (2) R = , , ,； (3) R = ,； (4) R= , , 关系表示法关系表示法有穷集合上的二元关系的三种表示方法：有穷集合上的二元关系的三种表示方法：n 集合表示法集合表示法 （前已使用）（前已使用）n 关系矩阵法关系矩阵法n

46、 关系图关系图 关系矩阵是表示关系的另一种有效的方法，其关系矩阵是表示关系的另一种有效的方法，其优点是可以利用矩阵作为研究关系的手段，而且这优点是可以利用矩阵作为研究关系的手段，而且这样做便于计算机进行处理。样做便于计算机进行处理。 设设R：AB，A和和B都是有限集，且都是有限集，且 |A|=n, |B|=m, A , B中的元素已按一定的次序排列若中的元素已按一定的次序排列若A=x1,x2,xn ,B= y1,y2,ym 且且R A B,若若则称矩阵则称矩阵为为R的的关系矩阵关系矩阵关系矩阵法关系矩阵法1,0,ijijijx yRrx yR 0 1 1 1MR= 0 0 1 1 0 0 0

47、1 0 0 0 0例例 A=1,2,3,4, R为为A上的小于关系，上的小于关系，则则R=, , , R的关系矩阵为：的关系矩阵为：1 2 3 41 2 3 41 2 3 41 2 3 4例例: 设集合设集合A2,3,4, B=8,9,12,14。 R是由是由A到到B的二元关系，定义：的二元关系，定义：R= | a整除整除b写出写出R的表达式和关系矩阵。的表达式和关系矩阵。 解解：R=, R的关系矩阵：的关系矩阵： 101 101101010RM关系图关系图 关系图是表示关系的一种直观形象的方法，设关系图是表示关系的一种直观形象的方法，设R：AB，A和和B都是有限集，都是有限集， A=x1,x

48、2,xn , B= y1,y2,ym 关系关系R的有序对的有序对 可用图中从结点可用图中从结点xi 到到yj 的有向的有向边表示，这样即可将关系用图表示之。边表示，这样即可将关系用图表示之。例例 设设 R: AB，A=x1,x2, x3, x4 , B= y1,y2,y3 R=, , ， R的关系如下图所示的关系如下图所示x1x2x3x4y1y2y3设设R是在是在A上的二元关系，上的二元关系， A=x1,x2,xn 关系关系R的有序的有序偶偶 可用图中从结点可用图中从结点xi 到到xj 的有向边表示，这样的有向边表示，这样即可将关系用图表示之。即可将关系用图表示之。 例例 ：设设 R: AA，

49、A= a,b, c, d R=, , , R的关系如下图所示：的关系如下图所示：abcd 例：例： 设集合设集合A=a,b,c,d,R是是A上的关系上的关系R=,试以试以关系矩阵和关系图来表示关系关系矩阵和关系图来表示关系R。解：解： （1）关系矩阵为：）关系矩阵为： 1110001000010001Mbcda（2）关系图为：）关系图为： 关系的运算关系的运算（1）R中所有的有序对的第一元素构成的集合称为中所有的有序对的第一元素构成的集合称为R的的定义域定义域，记作，记作domR。 domR=x| y( R（2）R中所有的有序对的第二元素构成的集合称为中所有的有序对的第二元素构成的集合称为R的

50、的值域值域，记作，记作ranR。 ranR=y| x R（3）R的定义域和值域的并集称为的定义域和值域的并集称为R的的域域，记作，记作fldR。 fldR=domR ranR例：例： 设设R=,则则 domR=1，2，3 ranR=1，2，3，4 fldR=1，2，3，4限制关系限制关系设设R为二元关系，为二元关系，A是集合是集合（1）R在在A上的限制，记作上的限制，记作R A,其中其中 R A=|xRy x A（2）A在在R下的象，记作下的象，记作RA，其中，其中 RA=ran(R A)例例：设集合：设集合A=1,2,3,4,R是是A上的关系上的关系R=,集合集合B=1,2,4,试求试求R

51、B及及RB。解：解：R B=,； RB=1，3，4。逆运算逆运算设设R为二元关系，称为二元关系，称 为为R的逆关系，其中的逆关系，其中 =| R 定理定理4.1 设设F是任意关系，则是任意关系，则（1） （2）1R1R11()FF证明：证明：（1）对任意的）对任意的11domFranF,ranFdomF111()FFF（2）对任意的）对任意的y11(,)(,)ydomFxy xFxx yFyranF 对任意的对任意的x11(,)(,)xranFyy xFyx yFxdomF 复合运算复合运算 设设F,G为二元关系为二元关系G对对F的右复合记作的右复合记作F?G,其中其中F?G=| t( F G

52、。说明：说明：（1）本书采用右复合的规则，而有的教材采用左复合）本书采用右复合的规则，而有的教材采用左复合规则，两者都可行，只是需要注意它们的区别，从变换的规则，两者都可行，只是需要注意它们的区别，从变换的角度来说，角度来说，G对对F的右复合是先的右复合是先F变换后变换后G变换，而变换，而G对对F的左复合是先的左复合是先G变换后变换后F变换。变换。（2）一般来说，并没有）一般来说，并没有F?G等于等于G?F，请读者仔细注意，请读者仔细注意其区别。其区别。例：例：设设F=,G=,则求则求F?F，G?G，F?G和和G?F。 解：解：F?F= ，G?G= F?G= G?F=。例：例：设有集合设有集合

53、 A=4,5,8,15, B=3,4,5,9,11C=1,6,8,13, F 是由是由 A 到到 B 的关系的关系, G 是由是由 B 到到 C 的的关系关系,分别定义为分别定义为 F=| |b-a|=1 G=| |b-c|=2或或|b-c|=4求合成关系求合成关系G F和和F G 解：解： 先求先求G F, 由题意知由题意知 F=, ,； G=, ,； G F= ,。 定理：定理： 设设F、G、H是任意关系是任意关系, 则则 (1) (F-1)-1=F (2) dom(F-1)=ranF , ranF-1=domF (3) (F G) H= F (G H) (4) (F G)-1= G-1

54、F-1证明证明: (1) 任取任取,由逆的定义有由逆的定义有 (F-1)-1 F-1 F (F-1) -1 = F (2) 任取任取x, xran F-1 y( F-1 ) y( F) x dom F ran F-1 = dom F 同理可证同理可证 dom (F-1) = ran F 证明证明: (3) 任取任取, (F G) H t( F G H ) t s( F G H ) s( F t ( G H ) s( F G 。H ) F (G H ) (4) 任取任取, (F G)-1 F G t( F G) t( G-1 F-1 ) G-1 F-1 定理：定理： 设设F、G、H是任意关系是任

55、意关系,则则 (1) F (GH)= F G F H (2) (GH) F= G F H F (3) F (GH) F G F H (4) (GH) F G F H F证明证明: (1) 任取任取, F (GH) t( FG H ) t (F(GH ) t (FG)( FH) t (FG) t(FH) F G F H F G F H证明证明: (3) 任取任取 , F (GH) t( F G H ) t ( F G H ) t (FG)( FH)= t(FG) t( F H) F G F H F G F H本定理对有限个关系的并和交都成立。本定理对有限个关系的并和交都成立。R (R1R2 Rn

56、)= R R1R R2R Rn(R1R2 Rn) R= R1 RR2 RRn RR (R1 R2 Rn) R R1R R2 R Rn(R1R2 Rn) R R1 RR2 RRn R幂运算：幂运算：设设R是是A上的关系上的关系, n为自然数，则为自然数，则R的的n次幂规定如下：次幂规定如下： (1) R0= | xA (2) Rn= Rn-1 R n1 由定义可以知道由定义可以知道R0就是就是A上的恒等关系上的恒等关系IA，不难证，不难证明下面的等式明下面的等式R R0 =R=R0 R 。由这个等式立即可以得到由这个等式立即可以得到 R1 =R0 R =R例：例： 设设A= a,b,c,d ,R

57、= , 求求R0 ，R1，R2， R3 ，R4和和R5解：解： R0 = , R1 = R0 R = , , = , 。 R2 = R R = , , = , R3 = R2 R = , , =, R4 = R3 R = , , =, R5 = R4 R = , , =,定理：定理：设设R是是A上的关系上的关系, m, n 为自然数，为自然数，则下面的等式成立则下面的等式成立 (1) Rm Rn= Rm+n (2) (Rm)n= Rmn证明：证明：(1) 任给任给m，对，对n作归纳法。作归纳法。 n=0时，时，Rm R0=Rm = Rm+0。 假设假设Rm Rn=Rm+n，那么，那么RmRn+

58、1=Rm(RnR1)= (RmRn )R1= Rm+nR1= Rm+n+1= Rm+(n+1) 。(2) 任给任给m，对，对n作归纳法。作归纳法。 n=0时，时，(Rm)0= R0 = Rm 0。 假设假设(Rm)n=Rmn。那么。那么(Rm)n+1= (Rm)n Rm = Rmn Rm = Rmn+m= Rm(n+1) 例例: 已知集合已知集合A=a,b,c,d,A上的关系上的关系R=,，求，求 。解：解：法一法一：由复合定义知：由复合定义知2RR R32RRR=,=,23,RR 法二法二：关系：关系R R矩阵为矩阵为0100101000010000M2M010010100001000001

59、0010100001000031010010100000000M101001010000000001001010000100000101101000000000= =法三：法三：R的关系图为的关系图为bcda2R的关系图为的关系图为 bcda3R的关系图为的关系图为bcda定理定理 A为n元集,R为A上的关系,则存在自然数s和t， 使得Rs=Rt证明：证明：因为A为n元集，所以集合A上的关系为有限N= 个，而关系序列存在无限多个关系，故存在自然数s和t，使得Rs=Rt.。22n0121,NNRR RRR 设设 R 是是 A 上的关系，上的关系，R 的性质主要有以下的性质主要有以下 5 种种:(

60、1) 自反性：自反性：若若 x(x A R),则称则称 R 在在 A 上是上是自反自反的。的。 也就是说，对也就是说，对R A A，若，若A中每个中每个x，都有，都有xRx，则，则称称R是自反的，即是自反的，即A上关系上关系R是自反的是自反的x(x AxRx)。 该定义表明了，在自反的关系该定义表明了，在自反的关系R中，除其它有序对中，除其它有序对外，必须包括有全部由每个外，必须包括有全部由每个x A所组成的元素相同的有所组成的元素相同的有序对。序对。 例如：设例如：设A=1, 2, 3, R 是是 A 上的关系，上的关系， R=, , 则则 R 是自反的是自反的关系的性质关系的性质(2) 反