集合论与关系

1、第三章 集合与关系,杨圣洪,3.1、集合的基本概念 不产生歧义的对象的汇集一块便构成集合. 集合常用枚举法: 湖大教学楼=复临,中楼,东楼,北楼,前进楼 描述法:偶数集=除以2余为0的所有整数 子集AB:A中的每个元素都是B的元素 幂集P(A)=A的所有子集的集合=2A. 如A=1,2,3 A000=,A001=3,A010=2,A011=2,3, A100=1,A101=1,3,A110=1,2,A111=1,2,3 其有23个 ,即2|A|个,3.2、集合的运算与性质 1、AB=由同时属于A与B的元素组成 2、AB=由属于A或属于B的元素组成 3、A-B=由属于A但不属于B的元素组成 4、

2、A=全集U中不属于A的元素组成=U-A,AB,AB,A-B,A,AB,3.2、集合的运算与性质 定义3.1.1 如果集合A中任何元素都是B的元素，则称A是B的子集，记为AB，也称B包含A，记为BA。 定义3.2.3 设A、B是两个集合，若AB、BA则A=B，即两个集合相等。 以下性质可根据相等定义得到，与命题逻辑性质一样 幂等律AA=A， AA=A 结合律ABC= A(BC)= (AB)C ABC= A (B C)= (AB)C 交换律AB=BA AB=BA 分配律A(BC)=(AB)(AC) A(BC)=(AB)(AC) 同一/零律 A=A A = 排中/矛盾律AA=E A A= 吸收律(大

3、吃小) A(BA)=A, A(BA)=A 德摩律 (AB)= AB (AB)= A B 双重否定 A=A,3.3、有穷集的计数 1、|A|=集合A的元素数 2、例题：24人中(书上缺少此条件)，会英=13、日=5、德=10、法=9，同时会英日有2人，会德、法、英中任意二种有4人，会日语的不懂法德语，只会1种和3种人？,令同时会三种语言为x人， 只会英为y1,只会法为y2, 只会德语y3 y1+2+4-x+x+4-x=13 y2+4-x+4-x+x=9 y3+2(4-x)+x=10 y1+y2+y3+3+2+3(4-x)+x=24,x=1， y1=4， y2=2， y3=3,3.3、包含排斥原理

4、 |A1A2|=|A1|+|A2|-|A1A2| 因为公共部分算了两次！ 例：A1=蓝球队=10，A2=足球队=13，双重身份球员3人，请问这二个球队总共多少人？ 解：|A1A2|=|A1|+|A2|-|A1A2|=10+13-3=20人 |A1A2 |=|Ai|-|AiAj| +|AiAjAk|-|AiAjAkAL| . +(-1)n-1| A1A2 An| 加奇数个集合相交-偶数集合相交,A1,A2,3.3、集合计数 |A1A2|=|A1|+|A2|-|A1A2| |A1A2 |=|Ai|-|AiAj| +|AiAjAk|-|AiAjAkAL| . +(-1)n-1| A1A2 An| 加

5、奇数个集合相交-偶数集合相交 例题：设校足球队的球衣有38件，蓝球有15件，排球有20件，三队总数为58人，3个同时参加3队，请问同时参加二队有多少？ 解|A1A2A3|=|Ai|-|AiAj|+|AiAjAk| 58=(38+15+20)-|AiAj|+3 |AiAj|=18,A1,A2,例题在1,300整数中能被3或5或7整除的整数的个数。 解：A3示能被3整除的数,A5能被5整除,A7能被7整除. 能被3整除的个数：|A3|=300/3=100 能被5整除的个数：|A5|=300/5=60 能被7整除的个数：|A7|=300/7=42 能被3与5同时整除的个数：|A3A5|=300/15

6、=20 能被3与7同时整除的个数：|A3A7|=300/21=100/7=14 能被5与7同时整除的个数：|A5A7|=300/35=60/7=8 能被3、5、7同时整除的个数：|A3A5A7|=2 能被3或被5或被7整除的个数：|A3A5A7| =|A3|+|A5|+|A7|-|A3A5|-|A3A7|-|A5A7|+|A3A5A7| =100+60+42-20-14-8+2 =162,3.4、序偶 定义3.4.1 将具有次序的两对象写在一块，称为序偶即有秩序的二个对象，记为或。 如:, 定义3.4.2 令与是二个序偶，如果x=u、y=v，那么=即2个序偶相等。 序偶，a代表操作码，b代表地

7、址码，显然来自两个不同的集合。 定义3.4.3 如果是序偶，且,z也是一个序偶，则称为三元组。 如，。 定义3.4.4 如果是n-1 元组，而,xn是序偶，则称为为n元组。,3.5 直积或笛卡尔积 定义3.5.1 令A、B是两个集合，称集合|xA, yB为A与B的直积或笛卡尔积，记为AB。 如A=1,2,3,B=a,b,c AB=1,2,3a,b,c=, , BA=a,b,c1,2,3=, 由于，所以ABBA 直积不满足交换律, 序偶的前后2个元素来自于不同的集合，也可以来自同一个集合。,3.5 直积或笛卡尔积 又如 A=中,巴,美,古 AA=中,巴,美,古中,巴,美,古=, 直积的结果实际是

8、一个集合,具有以下性质 1、A(BC)= ABAC 2、A(BC)= ABAC 3、(BC) A = BA CA 4、(BC) A = BACA 5、ABACBCCACB 6、AB,CD ACBD,3.6、关系 将笛卡尔积中前后两个元素之间存在某种关系的序偶检出来,便得到一个关系。 AB=1,2,3a,b,c=, , R1=前后两个元素的序号一样 =, AA=1,2,31,2,3=, , R2=第一个元素, 有时无法用文字描述两者的关系，只好将相关的序偶选出来。 R3=,3.6、关系 将笛卡尔积中前后两个元素之间存在某种关系的序偶检出来,便得到一个关系。 定义3.6.2 如果序偶或元组属于某个

9、关系R，则称序偶或元组具有关系R。 若序偶R，还可写成xRy， 将关系名称写在二个元素之间， 其他数学也是这样表示，如2R，可可写成2R4 如R2，可写成2R24 也有人认为，这种写法不直观，可能产生歧义，本课程尽量回避这种写法。,3.6 关系的描述 AB=1,2,3a,b,c=, , R1=前后两个元素的序号一样 =, 除给出关系中所包含的序偶外，还可用关系矩阵、关系图表示。,3.6 关系的描述 A=1,2,3,4,5,6,7,8, R3=, , , , , , , , , , 关系矩阵,3.6 关系的描述 关系图：令RAB，则将A、B的元素均画成一个点，如果序偶R，则从点x画一条有向边到点

10、y。 A=1,2,3,4,5,6,7,8， R=, , , , , , , , 序偶前后元素均是A，还可简化！,3.6 关系的描述 关系图：令RAB，则将A、B的元素均画成一个点，如果序偶R，则从点x画一条有向边到点y。 A=1,2,3,4,5， R=, , , , , ， 则其关系图如下,3.7、关系复合 A=1,2,3,FAxA,GAxA A上的关系 设F,G为二元关系,G对F的右复合记为FG,定义 FG=|t( F,G) 如F=, G=, FG=, M(FG)=M(F) M(G) 可用关系矩阵相乘 /关系图表示,A=1,2,3, FAxA,GAxA A上的关系 F=, G=,3.7、关系

11、复合 MF的第i行与MG的第j列相乘时， 乘法是合取，加法是析取， 如MF1行与MG3列相乘(11)(10)(00)，结果为1。 定义3.7.2 称|F 为F的逆， 记为F-1 令A=1,2,3，F=,。 则F-1=, 性质： (1)结合律 (PR)S=P(RS) (2)复合的逆(PR)-1= R-1P-1,3.8、关系的性质与分类 自反关系:若关系R前后二个元素来自同一个集合A,若xA,都有R,则R是自反的. 反自反关系:若关系R前后二个元素来自同一个集合 A,若xA,都有R,则R是反自反的. 如:A=1,2,3 R1=, 因为R1不是自反的 因为R1, R1,故不是反自反的. R2=, 自

12、反的! R3= 反自反的!,3.8、关系的性质与分类 自反关系:若xA,有R,则自反的.主对全1 反自反关系:若xA,有R,则R反自反主对全0 如:A=1,2,3 R1=, 自反的! R2= 反自反! R3=,不是自反 ,不是反自反.,自反,自反,反自反,反自反,3.8、关系的性质与分类 自反关系:若xA,有R,则自反的.主对全1 反自反关系:若xA,有R,则R反自反主对全0 定义3.8.3 若关系R=AA，则称为全域关系，记为EA. 在全域关系中，由于直积的每个序偶都在关系R中，所以其关系矩阵全是1， 主对角线肯定也为1，故是自反关系。 定义3.8.4 若所有形如的序偶都在关系R中，R也只有

13、这种形式的序偶，则称R为恒等关系，记为IA。 若R是自反关系，则恒等关系IAR 如A=1,2,3,则IA=,3.8、关系的分类 自反关系:若xA,都有R 反自反关系:若xA有R 对称关系:若R有R 反对称关系:若R,Rx=y 也可：若R且xyR则反对称 如:A=1,2,3 R1=, 对称 R2=, 反对称 R3=, 因R1不对称,因与成对出现,而不是反对称,3.8、关系的分类 1-2班 对称关系:若R有R 非对角成对 反对称关系: 若R且xyR 如:A=1,2,3 R1=, 对称 R2=, 反对称 R3=,3.8、关系的分类 对称关系:若R有R 非对角成对 反对称关系:若R,Rx=y 2个定义

14、等价 若R且xyR (Rxy)R (Rxy) R条件式的等值式 R xy R德摩律 R x=yR的含义 (RR)x=y结合律 (RR)x=y德摩律 (RR) x=y条件式的等值式,3.8、关系的性质与分类 传递关系:若R,RR 表示两个序偶的复合仍在R中, 即RRR,M2M A=a,b,c R=, RR=, , = , R 学会看图,R,R,RR,3.8、关系的性质与分类 传递关系:若R,RR 表示复合仍在R中, 即RRR,M2M 如A=1,2,3 R1=, R1R1=, , =, R故可传递 复合边已在图中，或传递可达的二点有边直连.,3.8、关系的性质与分类 传递关系:若R,RR 表示复合

15、仍在R中, 即RRR,M2M 如A=1,2,3 R2=, 传递的产生的R故不是 复合边已在图中，或传递可达的二点有边直连.,1,2,3,3.8、关系的性质与分类 传递关系:若R,RR 表示两个序偶的复合仍在R中, 即RRR,M2M 如A=1,2,3 R1=, 可传递的，OK R1R1=R1R1故为可传递！,3.8、关系的性质与分类 自反关系:xA RIAR 反自反关系:xA RIAR= 对称关系:R R R=R-1 反对称关系:R,Rx=y R且xy R RR-1IA 传递关系:R,RRR2R 自反:主对角线均为1 反自反:主对角线均为0 对称:M=MT。 反对称：MMT后只有主对角非0 传递

16、:R2R即M2M,3.9、关系的闭包：加点序偶使之成某种类型 1、R自反闭包r(R)：加序偶使之成自反的。 R=,不是自反 r(R)=, r(R)=RIA,3.9、关系的闭包：加点序偶使之成某种类型 2、R对称闭包s(R)：加序偶使之成对称的。 R=, 反对称 s(R)=, 对称 s(R)=RRT.,3.9、关系的闭包 A=a,b,c,d，R=, ，求其传递闭包 解：先求R2，若R2R则R是传递关系，即不添序偶就得传递关系，传递闭包就是R。 若R2R，表示复合产生的序偶不在R中，为了可传递，故将复合出来的序偶投入到R中即得到R2R。新序偶与旧序偶又复合出二代新序偶。 若二代新序偶已在R2R中，

17、则R2R已是可传递关系，则它就是传递闭包，即t(R)= R2R。 否则将二代新序偶放入R中，得到R3R2R。 重复以上过程，直到得到一个传递关系。,例A=a,b,c,d, R=, R2=, R3=, , =, t(R)=, , , , , , , , , , , , , 结点u出发经过2条边到达v,若u与v有边相连则可传递 当集合A有n结点时,从u出发，若结点不重复，最多可经过其他n-1结点，最多可依次跨越n-1条不同的边， 故以上重复过程，最多经过n-1轮，最多求到Rn-1。,例A=a,b,c,d, R=, R2=, R3=, , =, t(R)=, , , , , , , , , , ,

18、, , 由关系的复合可知，R,RR=R2,R3,Rn-1,可由关系矩阵的积来实现。 RR2R3 Rn-1,将剔除重复出现的序偶,因此可由矩阵幂次方的析取MR(MR)2(MR)n-1实现,即t(R)= MR(MR)2(MR)n-1。,t(R)=RR2 R3. Rn-1.任何两点最多n-1步达 =M M2 M3 . Mn-1. 例A=a,b,c,d, R=, t(R)=, , , , , , , , , , , , , , , , ,t(R)=RR2 R3. Rn-1.任何两点最多n-1步达 =M M2 M3 . Mn-1. 效率比较低！ Warshall算法 for (j=1;jn;j+) /第

19、1列到最后列 for(i=1;in;i+ /第j列从第1行到最后行 if (M(i,j)=1) 第i行=第i行第j行;,3.9、关系的闭包：加点序偶使之成某种类型 1、R自反闭包r(R)的定义： (1)r(R)自反; (2)Rr(R); (3)RR,R自反r(R)R 最小性 恰好增加到变成自反为止。 2、R对称闭包s(R)的定义： (1)s(R)对称; (2)Rs(R); (3)RR,R对称s(R)R 最小性 3、R传递闭包t(R)的定义： (1)t(R)传递; (2)Rt(R); (3)RR,R传递t(R)R 最小性,利用求闭包方法也可判断关系性质,3.10、等价关系、等价类、分类(划分)

20、自反、对称、可传递的关系称为等价关系。 例 A=1,2,3,4,5,6,7,8 R=, = |x-y=3k 判断:是否为等价关系 (1) xA,因x-x=0=3*0 ，故R，故自反 (2) Rx-y=3k y-x=3(-k) R (3)R,Rx-y=3k,y-z=3m x-z=3(k+m)R,3.10、等价关系、等价类、分类(划分) 例 A=1,2,3,4,5,6,7,8 R=, , 彼此有等价关系的元素的集合,称为等价类. 如：上述关系R的序偶分成3类 = , , , , , , , , , , , , 等价类有： 1,4,7 ，2,5,8，3,6 简记为1=4=7 这显然对集合A的元素进行

21、了划分！,3.10、等价关系、等价类、分类(划分) 设RAA，R是等价关系，A0,A1,Ak是基于R得到的等价类，则称集合A0,A1,Ak为A关于R的商集，记为A/R。 例 A=1,2,3,4,5,6,7,8 R=, = , , , , , , , , , , , , A/R=A0,A1,A2=1,4,7, 2,5,8, 3,6,划分:若A=A0A1 Ak, 且不相交,则称A的划分 例 A=1,2,3,4,5,6,7,8 R=, 因为等价类1,4,7,2,5,8,3,6彼此不相交，并集为A，称为A的划分,因此等价关系可划分集合。 定理 设RAA，R是等价关系，A0,A1,Ak-1是利用R得到的

22、k个不同的等价类，则A0,A1,Ak为集合A的划分,3.10、等价关系、等价类、分类（划分）,划分:若A=A0A1 Ak, 且不相交,则称A的划分 定理 设RAA，R是等价关系，A0,A1,Ak-1是利用R得到的k个不同的等价类，则A0,A1,Ak为集合A的划分 (1)当ij 时假设AiAj。则xAiAj可知xAi，xAj， 对Ai中任意元y，由等价类定义知, R， 对Aj中任意元素z，也有, R。 因R是等价关系及, R可知R,同理R， 所以,R，即二者的任意组合构成的序偶都在R中，根据等价类的定义y与z在同一个等价类中，即Ai=Aj，与前提矛盾，故假设错。只能AiAj=。 (2) xA，若

23、x与其他所有元素都没有关系，则单个x构成一个等价类。若x与有其他元素有等价关系R，则与他们处于一等价类. 总之x至少属于一个等价类Ai，所以xA0A1Ak-1，所以AA0A1Ak-1。又由等价类的定义可知AjA， 故A0A1Ak-1A，故A=A0A1Ak-1。,3.10、等价关系、等价类、分类（划分）,划分:若A=A0A1 Ak, 且不相交,则称A的划分 例 A=1,2,3,4,5,6,7,8 R=, 因为等价类1,4,7,2,5,8,3,6彼此不相交，并集为A，称为A的划分,因此等价关系可划分集合。 (1)观察关系中的序偶可得到划分 (2)观察关系图也可得到划分,3.10、等价关系、等价类、

24、分类（划分）,3.10、等价关系、等价类、分类(划分) 自反、对称、可传递的关系称为等价关系。 例 A=1,2,3,4,5,6,7,8 R= , , , , , , , , , , , , =1,4,7x1,4,72,5,8x2,5,8 3,6x3,6 由等价关系 找出 划分 1,4,7, 2,5,8,3,6. 反过来，由划分 构造 等价关系吗？,3.10、等价关系、等价类、分类(划分) R=A1A1A2A2 A3A3 R= 1,4,7x1,4,72,5,8x2,5,8 3,6x3,6 可验证R是等价关系! 再如A的划分:A1=1,2,3,A2=4,5,6,A3=7,8，则R=A1A1A2A2

25、 A3A3 =, , , , , , , R是对称、自反、可传递的等价关系。,3.10、等价关系、等价类、分类(划分) 定理3.10.2 设A0,A1,Ak-1是A的划分，R=A0A0A1A1Ak-1Ak-1，则R等价关系。 (1)xA，由划分的定义可知，x肯定属于某个子集Ai，所以AiAi，故R,自反。 (2)若R，则至少属于某个子集Ai的直积(如果不属于任何Ai 的直积则不属于R)，即AiAi，由于Ai的直积是对称的，故AiAiR,故R对称。 (3)若AiAi则AiAi。假设AjAj，其中ij。由AiAi有xAi,yAi，由AjAj有yAj,zAj，故yAi又yAj这不可能，故假设错，只能

26、AiAi。 因Ai直积可传递，故AiAiR，故R可传递。,3.11、偏序关系 1、自反、反对称、可传递的关系。 例题设A=实数集，R是实数中小于等于关系，即R=|x,y是实数，且xy，则R是偏序关系。 (1)xA(实数)有xx，故R，即为自反关系。 (2)若R,R，则xy且yx,故x=y,故反对称 (3)若R,R，则xy且yz，故xz,R可传递 例题：A=1,2,3,4,5,6 R= :x|y (1) x|x，故R即自反 (2)x|y,y|x即y=kx,x=my，故x=m(kx),故mk=1,故k=m=1 故x=y，故反对称 (3)x|y,y|z即y=kx,z=my，故z=m(kx)=mkx即

27、x|z故可传递 偏序关系可理解为广义的“小于等于”关系，记为。,3.11、偏序关系 1、自反、反对称、可传递的关系。可理解为广义的“小于等于”关系，记为。 2、当时，写成xy，主要为了直观。 3、当但xy时，记成x或，即xy或yx。 例题：A=1,2,3,4,5,6 R= :x|y R=, , , , R，可记为12,也可1R，可记为22,不可2R即24 可比与不可比 4与2可比，因为R即24 2与5不可比，因为R,R,3.11、偏序关系 1)自反、反对称、可传递的关系。广义的“小于等于”关系，记为。 2)当时，写成xy，主要为了直观。 3)当但xy时，记成x或。 5)全序(线序): x,yA

28、 ，x与y都可比。 如A=1,2,3,4,5,6 R=:xy 狭义 关系图中所有点在一条线上！ B=1,2,A=,1,2 R=:xy,xA,yA,即x与y是B的子集。全序 B=1,2,A=,1,2,1,2 R=:xy,xA,yA,即x与y是B的子集。 偏序,3.11、偏序关系 1)自反、反对称、可传递的关系。 2)当时，写成xy，主要为了直观。 3)当但xy时，记成x或。 5)全序(线序): x,yA ，x与y都可比。 6)偏序集：。 A=1,2,3,4,5,6 R=:xy B=1,2,A=,1,2,1,2 R1=:xy,xA,yA, B=1,2,A=,1,2 R2=:xy,xA,yA ,3.11、偏序关系 7)哈斯图 因箭头都朝上方，故箭头不画。 因每个结点都有自旋箭头，故不画自旋。 因可传递即复合边均在其中，故将传递可达的二点间的直达边去掉。 这样得到的图为哈斯图。,3.11、偏序关系 因箭头都朝上方，故箭头不画。 因每个结点都有自旋箭头，故不画自旋。 因可传递即复合边均在其中，故将传递可达的二点间的直达边去掉。 这样得到的图为哈斯图。,3.11、偏序关系 2)当时，写成xy，主要为了直观。 4)x,yA x与y可比是指或。 6)偏序集：。 8)盖住