离散数学及其应用02-集合论课件

1、第2篇集合论集合论集合论是现代各科数学的基础，它是德国数学家康托（Geog Cantor, 18451918）于1874年创立的 1900年前后出现了各种悖论，使集合的发展一度陷入僵滞的局面。19041908年，策墨罗（Zermelo）列出了第一个集合论的公理系统，它的公理，使数学哲学中产生的一些矛盾基本上得到了统一，在此基础上以后就逐渐形成了公理化集合论和抽象集合论，使该学科成为在数学中发展最为迅速的一个分支。 集合论在计算机科学中也具有十分广泛的应用，计算机科学领域中的大多数基本概念和理论几乎均采用集合论的有关术语来描述和论证，成为计算机科学工作者必不可少的基础知识。集合论可作为数学学科的

2、通用语言，一切必要的数据结构都可以利用集合这个原始数据结构而构造出来，计算机科学家或许也可以利用这种方法。 第 3 章 集合与关系 3.1 集合的概念和表示法 3.2 集合的运算 3.3 集合的计数3.4序偶与笛卡尔积3.5 关系及其表示第 3 章 集合与关系3.1 集合的概念和表示法 一般地说，把具有共同性质的或满足一定条件的事物汇集成一个整体，就形成一个集合。例如：教室内的桌椅、图书馆的藏书、自然数的全体、直线上的所有点等，均分别构成一个集合，而同学、高等学校、每个自然数、直线上的点等分别是所对应集合的元素。通常用大写英文字母表示集合的名称，用小写英文字母表示组成集合的“事物”，即元素。若

3、元素a属于集合A，记作aA，也称集合A包含a，或a在A之中，或a是A的成员；若元素a属于集合的元素，记作aA，也称集合A不包含a，或a不在A之中，或a不是A的成员。若一个集合包含的元素个数是有限的，则称该集合为有限集，否则称为无限集。 第 3 章 集合与关系3.1 集合的概念和表示法集合的方法通常有两种：列举法和描述法。 列举法是指将集合中所有元素都列举出来，或者列出足够多的元素以反映集合中成员的特征，并把它们写在大括号里。例如：Aa,b,c,d，B课桌，灯泡，自然数，老虎，C1,2,3,，D=a,a2,a3, 。从方法的定义中可以看出，列举法必须把元素的全体尽列出来，不能遗漏任何一个，并且集

4、合中的元素没有顺序之分且不重复。而描述法是指利用一项规则，概括集合中元素的属性，以便决定某一事物是否属于该集合。如果我们用谓词P(x)表示一个集合中的元素x所具有的属性，则任一集合可表示为x| P(x)，其中竖线“|”前写的是元素的一般表示，右边写出元素应满足（具有）的属性。含义为该集合中的元素x具有属性P。设集合Ax| P(x)，如果P(a)为真，则a A，否则aA。例如： 第 3 章 集合与关系3.1 集合的概念和表示法本书中用如下专用字母表示常见的集合：N自然数的集合（包含0）；Nm 小于m的自然数集合，即0,1,n-1；I(或Z)整数的集合；I+(或Z+)正整数的集合；I_（或Z_）负

5、整数的集合；R实数的集合；R+正实数的集合；R_负实数的集合；Q有理数的集合；C复数的集合。 第 3 章 集合与关系3.1 集合的概念和表示法集合间的关系 定义3.1.1设A，B为任意两个集合，则有：（1）对于每个a A皆有a B，那么称A为B的子集或B包含A，也称B为A的母集，记作AB或BA。即：ABx(xA xB) 可等价地表示成： ABx(xBxA)。（2）若AB且AB，则称A为B的真子集或B真包含A，记作AB或BA。即：ABx(xA xB)x(xBxA)（3）若AB且BA，则称A和B相等，记作A=B；否则，称A和B不相等，并记作AB。即：A=B (AB) ( BA)第 3 章 集合与关

6、系3.1 集合的概念和表示法例题3.1.1设N为自然数集合，Q为一切有理数组成的集合。R为全体实数集合，C为全体复数集合，则 NQRC ，1N，1,1.2,9.9Q，2,R。也有NQRC ，1N，1,1.2,9.9Q，a,ba,b,c,d。注意符号“”和“”在概念上的区别，“”表示元素与集合间的“属于”关系，“”表示集合间的“包含”关系。集合间的包含关系“”具有下述性质：定理3.1.1 设A，B是任意的集合，则（1）AA，称为自反性； （2）若AB且BC，则AC，称传递性； 证明：（1）由集合间包含关系的定义直接得证。（2）对任意xA，由AB可知，一定有xA，又由BC可知，一定有xC，因此AC

7、。第 3 章 集合与关系3.1 集合的概念和表示法定义3.1.2 不包含任何元素的集合是空集(Empty Set)，记作。即= x| P(x)P(x)，P(x)是任意谓词。 定理3.1.2 对于任意一个集合A，有A。且空集是惟一的。 定义3.1.3 在一定范围内，如果所有集合均为某一集合的子集，则称该集合为全集，记作E（或U）。对于任一xA，因AE，故xE，即x(xE)恒真,故 E x| P(x)P(x),P(x)是任意谓词。定义3.1.4给定集合A，由集合A的所有子集为元素组成的集合，称为集合A的幂集。记为P(A)（或记为2A）。即 P(A)X|X A。定义3.1.5 设A为任一集合，用|A

8、|表示A含有不同元素的个数，也称为集合A的基数。 定理3.1.3 如果有限集A的基数An，则其幂集P(A)有个元素，即|P(A)|= 2n 。 第 3 章 集合与关系3.1 集合的概念和表示法定理3.1.4 设A，B任意两个集合，则有（1）P(A)；（2）AP(A)；（3）若AB，则P(A) P(B)。证明 (1)和(2)由定理3.1和定义3.1.4直接推出。（3）若xP(A)，则xA，又AB，所以xB，因此，xP(B)，从而知P(A) P(B)。 第 3 章 集合与关系3.2 集合的运算 定义3.2.1 集合的几种主要的基本运算。设A，B是集合， 并集(Union)：AB称为集合A与B的并集

9、，由A和B的所有元素所组成，定义为AB=xxA xB；称为集合的并运算。交集(Intersection)：AB称为集合A与B的交集，由所有同属于A和B的元素所组成，定义为AB=xxA xB；称为集合的交运算。 差集(Difference)：B-A称为B与A的差集，或称为A关于B的相对补集，由所有属于A而不属于B的元素所组成，定义为B-A=xxB xA。 补集(Complement)：称为A关于全集U的相对补集，或称为A的绝对补集，简称为A的补集，由由U中不属于A的所有元素所组成，定义为=x|xU xA 。 对称差(Symmetric Difference)：称为集合A与B的对称差或布尔和, 由

10、除A和B中共同元素外其它的A和B中元素所组成，定义为=(A-B)(B-A)=(AB)-(AB)。 第 3 章 集合与关系3.2 集合的运算集合运算的文氏图表示 B A AB ABAABA集合AU图3-1 五种基本集合运算的文氏图第 3 章 集合与关系3.2 集合的运算 交换律 AB=BA，AB=BA； 结合律 (AB)C=A(BC)，(AB)C=A(BC)； 分配律 A(BC)=(AB)(AC)，A(BC)=(AB)(AC)； 幂等律 AA=A，AA=A； 同一律 A=A，AU=A； 零 律 AU=U，A = ； 互补律 A=U，A=； 双重否定律 =A； 吸收律 A(AB)=A，A(AB)=

11、A； 德摩根律 ， 。第 3 章 集合与关系3.3有限集合中元素的计 集合的运算，可用于有限集中元素的计数问题。我们记A为有限集合A所含元素的个数，通常有两种方法文氏图法和容斥原理法来进行集合运算的计数。3.3.1文氏图法(1)A1A2|A1|+|A2|(2)A1A2min(|A1|,|A2|)(3)A1A2|A1|-|A2|(4)A1A2=|A1|+|A2|-2A1A2 第 3 章 集合与关系3.3有限集合中元素的计容斥原理法容斥原理也称包含与排斥原理或逐步淘汰原则，它也是“多退少补”计数思想的应用。定理3.3.1 设A，B为有限集合，其元素个数分别为|A|，|B|则AB=|A|+|B|-A

12、B 定理3.3.2 S中不具有性质P1，P2，Pm的元素个数为 = +(-1)m(|A1A2Am|)。第 3 章 集合与关系3.4 序偶与笛卡尔积 序偶定义3.4.1 由两个元素x，y(允许x=y)按给定次序排成的二元组合称为一个有序对或序偶（Ordered pair），记作，其中称x是有序对的第一元素，y是有序对的第二元素。例如，上、下；左、右；34；张华高于李明；中国地处亚洲；平面上点的坐标等。这些实例可分别用序偶表示：；等。从这里可看出序偶是用来刻画两个对象之间的关系。 序偶可以看作是具有两个元素的集合。但它与一般集合不同的是序偶具有确定的次序。在集合中a，bb，a，但对序偶。 定义3.

13、4.2 两个序偶相等，当且仅当 xu， yv。第 3 章 集合与关系3.4 序偶与笛卡尔积例3.4.1 设=，求x，y。 解 由定义3.4.2可列出如下方程组： 求解得x=5，y=0。第 3 章 集合与关系3.4 序偶与笛卡尔积序偶的概念可以推广到有序三元组的情况。三元组是一个序偶，其第一元素本身也是一个序偶，可形式化表示为，z。由序偶相等的定义，可以知道，z，w，当且仅当，zw，即xu，yv，zw。今后约定三元组可记作。应该注意的是：当xy时，。同理四元组被定义为一个序偶，其第一元素为三元组，故四元组有形式为，w且 ，w，s 当且仅当(xp)(yq)(zr)(ws)依此类推，n元组可写为，x

14、n且 ，xn，yn当且仅当 (x1=y1)(x2=y2)(xn-1yn-1)(xnyn)一般地，n元组可简写为，第i个元素xi称作n元组的第i个坐标。 第 3 章 集合与关系3.4 序偶与笛卡尔积定义3.4.3 设A，B是任意集合，以A中元素作第一元素，B中元素作第二元素生成的所有有序对的集合称为A，B的笛卡尔积（Descartes Product），记作AB。即AB=xA yB。由定义，两集合的笛卡尔积仍是集合，所以可应用集合的运算，如并、交、差、补。 第 3 章 集合与关系3.4 序偶与笛卡尔积例3.4.2 设集合A=x, y, z，B=0, 1, C=u, v，求AB, BA, AA,

15、ABC, (AB)C, A(BC), (AB)(BA)。解 AB=, , , , , BA=, , , , , AA=, , , , , , , , ABC=, , , , , , , , , , , (AB)C=, u, , v, , u, , v, , u, , v, , u, , v, , u, , v, , u, , v=, , , , , , , , , , , A(BC)=x, , x, , x, , x, , y, , y, , y, , y, , z, , z, , z, , z, , , , , , , , , , , , 第 3 章 集合与关系3.4 序偶与笛卡尔积由笛卡尔

16、积的定义可得：1对于任意集合A，约定A=，A=。2笛卡尔积运算是不可交换的，当A，B，AB时ABBA。3笛卡尔积运算是不可结合的，因为(AB)C=, zxA, y B, z C是三元组的集合。A(BC)=x, x A, y B, z C是二元组的集合。定理3.4.1设A，B，C是三个集合，则有(1)A(BC)=(AB)(AC) (2)A(BC)=(AB)(AC)(3)(BC)A=(BA)(CA) (4)(BC)A=(BA)(CA)第 3 章 集合与关系3.4 序偶与笛卡尔积定理3.4.2对于任意集合A，B，C，若C，则(1)AB的充分必要条件是ACBC，(2)AB的充分必要条件是CACB。证明

17、 (1)充分性：设对任意的x A，因为C，任取y C，则 AC，又因为AC BC，因此 B C，从而x B，故AB；必要性：对任意的 AC，则x A且y C，因为AB，所以x B，因此，故ACBC。(2) 的证明留给读者。在证明过程中C的条件在证明必要性时可减弱，因而ABACBC。 第 3 章 集合与关系3.4 序偶与笛卡尔积定理3.4.3 设A、B、C、D为四个非空集合，则 AB CD的充要条件为AC，BD。 定义3.4.4 定义A1A2An=(A1A2An-1)An，称为集合A1, A2, , An的叉积。特别地，当A1=A2=An=A时，简记A1A2An为An。定理3.4.3 若A、B都

18、是有限集，|A|=m，|B|=n,则AB 也是有限集，且|AB|=mn。证明：根据笛卡尔积的定义，A的一个元素要产生n个序对，A的m 个元素就共要产生mn个序对。 第 3 章 集合与关系3.5 关系及其表示关系的定义定义3.5.1 设A，B为集合，AB的任何子集R称为从集合A到集合B的二元关系，简称为关系（Relation）。并称A为关系R的前域，B为关系R的后域。对于二元关系R，若R，常记作xRy；若R，则记作xy。特别当A=B时称R为集合A上的二元关系。例3.5.1 A=0, 1，B=x, y, z，则R1=，R2=AB，R3=等都是从A到B的二元关系，R4=和R3同时也是A上的二元关系。

19、A为整数集合，R=|x能整除y, x, yA为A上的整除关系。R为实数集合，=|xy, x, yR为R上的大于关系。例3.5.2设A=2,3,4, B=2,3,4,5,6,A到B的关系R定义为：对于aA，bB，R当且仅当a | b（a | b即a整除b），则R=, 第 3 章 集合与关系3.5 关系及其表示例3.5.3 设A=1,2,3,4,定义A上的关系R为R=| a , bA , (ab)/2=k, kI 则 R=,通常称R为A上的模2同余关系，也可等价地表示为R=| a , bA , a b (mod 2) 对于集合A，今后常用到的三个特殊关系： 空关系（Empty Relation）：

20、由于AA，所以是A上的关系，称其为A上的空关系； 全（域）关系（Total Relation）：由AAAA，所以AA是 A上的关系，称其为A上的全域关系，记作EA，即EA=aA，bA； 恒等关系（Identity Relation）： A=aA，称其为A上的恒等关系。 第 3 章 集合与关系3.5 关系及其表示例3.5.4 设A=x, y, z，则(1)EA=, , , , , , , , 是A上的全关系，EA=AA=9。(2)A=, , 是A上的恒等关系，A=A=3。 第 3 章 集合与关系3.5 关系及其表示定义3.5.2 关系R中所有有序对的第一元素的集合称为关系R的定义域（Domain

21、），记作domR，第二元素的集合称为关系R的值域（Range），记作ranR。称fldR=domRranR为R的域（field）。即domR=x|xAy(yBR)，ranR=y|yBx(xAR)显然R是从A到B的关系，有domRA，ranRB，fldRAB。关系的定义域与值域可用图3-5表示。 第 3 章 集合与关系3.5 关系及其表示第 3 章 集合与关系3.5 关系及其表示关系的表示1集合表示法关系是一种集合，因而集合的表示方法，诸如列举法、描述法都能用于关系的表示，上面几例给出了这两方法的应用。关系又是一种特殊的集合，因而它又有区别于通常集合的表示方法，对有限集合间的二元关系R除了可以用

22、序偶集合的形式表达以外，还可用矩阵和图形表示，以便引入线性代数和图论的知识来讨论。第 3 章 集合与关系3.5 关系及其表示关系的表示2矩阵表示法 设有限集合X=x1, x2, , xn，Y=y1, y2, , ym，其中m1，n1，R为集合X到集合Y的关系，则R的关系矩阵为MR=rijnm，其中如果R是有限集合X上的二元关系或X和Y含有相同数量的有限个元素，则MR是方阵。第 3 章 集合与关系3.5 关系及其表示例3.5.6 若A=a1,a2,a3,a4,a5,B=b1,b2,b3，R=,，写出关系矩阵MR。解: 第 3 章 集合与关系3.5 关系及其表示例3.5.7设A = 1 , 2 ,

23、 3 , 4 ,写出集合A上大于关系“”的关系矩阵。解： = , , , , , ，故第 3 章 集合与关系3.5 关系及其表示3关系图表示法有限集合的二元关系也可用图形来表示。设集合X=x1, x2, , xn到集合Y=y1, y2, , ym的一个二元关系为R，以两列结点（小实心黑点）表示集合X、Y中的元素，关系R中的每一有序对，用一带箭头的有向边画出，对任意 R，画一条箭头从结点x指向结点y的有向边(注意x是始点，y是终点，次序不能颠倒)。就得到一个全部由有向边构成的有向图，称为关系R的关系图，记作GR。特别地，当集合X=Y时，只用一列结点表示即可；当R，有向边由结点x指向自身。 第 3

24、 章 集合与关系3.5 关系及其表示例3.5.8 画出例3.5.6的关系图。解 本题的关系图如图3-6所示：第 3 章 集合与关系3.5 关系及其表示例3.5.9设X=1, 2, 3, 4，Y=2, 4, 6，R=|x能整除y，xA，yB，则R=, , , , ，对应的关系图如图3-7所示。 图3-7 R的关系图1232464第 3 章 集合与关系3.6 复合关系和逆关系 1. 复合关系的定义定义3.6.1设A、B、C都是集合，R是A到B的关系，S是B到C的关系，则R与S的复合关系是一个A到C的关系，记作RS，定义为：RS=xAzC(y)(yBRS)从R和S求RS，称为关系的复合运算。复合运算

25、是关系的二元运算，它能够由两个关系生成一个新的关系，以此类推。例如，R是从X到Y的关系，S是从Y到Z的关系，P是从Z到W的关系，则(RS)P是从X到W的关系。第 3 章 集合与关系3.6 复合关系和逆关系 例3.6.1设A=1, 2, 3, 4, 5，B=3, 4, 5, C=1, 2, 3，A到B的关系R=|x+y=6，B到C的关系S=y-z=2，求RS，SR。解 方法一：因 R， S，所以 RS；因 R， S，所以 RS；因 R， S，所以 RS；从而RS=, , 。 由复合关系的定义，S与R不能作复合运算，即SR无意义。方法二：由x+y=6，y-z=2，消去y得x+z=4，从而可写出关系

26、RS=, , 。第 3 章 集合与关系3.6 复合关系和逆关系 例3.6.2 设R1和R2是集合X0，1，2，3上的关系，R1|ji+1 或 ji/2 , R2|ij+2 ， 求 R1R2，R2R1，R1R2R1，R1R1，R1R1R1。 解： R1，, R2， R1R2， R2R1， (R1R2)R1， R1R1， (R1R1)R10，3，第 3 章 集合与关系3.6 复合关系和逆关系 定理3.6.1 设有限集合A=a1, , am，B=b1, , bn，C=c1, ,cP，R是A到B的关系，其关系矩阵MR是mn阶矩阵，S是B到C的关系，其关系矩阵MS是np阶矩阵，则复合关系RS是A到C的关

27、系，其关系矩阵MRS是mp阶矩阵，且MRS=MRMS=wij。其中 wij= ，按布尔运算进行的矩阵乘法。是求逻辑和：00=0，01=10=11=1；是求逻辑积：00=01=10=0，11=1。第 3 章 集合与关系3.6 复合关系和逆关系 例3.6.3 已知集合A=1, 2, 3, 4, 5，B=3, 4, 5，C=1, 2, 3，A到B的关系R=, , , ，B到C的关系S=, , ，利用关系矩阵求RS。解 ， 所以 RS=, , , 。 第 3 章 集合与关系3.6 复合关系和逆关系 2. 关系的复合运算的性质定理3.6.2 设R是由集合X到Y的关系，则IXR=RIX=R。定理3.6.3

28、 设R是A到B的关系，S、T都是B到C的关系，U是C到D的关系，则R(ST)=RSRT；R(ST)RSRT；(ST)U=SUTU； (ST)U SUTU。定理3.6.4 设A,B,C是集合，R是A到B的关系，S是B到C的关系，T是C到D的关系，则(RS) T=R(ST)。第 3 章 集合与关系3.6 复合关系和逆关系 定义3.6.2 设R是集合A上的二元关系，则关系R的n次幂Rn，定义为：(1)R0=IA=|x A是A上的恒等关系；(2) Rn=Rn-1R(n N且n1)。易知，RmRn=Rm+n，(Rm)n=Rmn例3.6.5 设A=a, b, c, d，A上关系R为R=, , , ，则：R

29、0 =A =, , , ；R1=R；R2=RR=, , , ；R3=R2R=, , , =IA；R4=R3R=IAR=R；R5=R4R=RR=R2，一般地，R3k+i= Ri,k,iN,且0i3。第 3 章 集合与关系3.6 复合关系和逆关系 逆关系定义3.6.3 设R是从X到Y的二元关系，若将R中每一序偶的元素顺序互换，得到的集合称为R的逆关系(Inverse Relation)，记为R-1。即R-1=|R例如，在实数集上，关系“”。说明：(1)R-1就是将R中的所有有序对的两个元素交换次序后得到，故|R|=|R-1|；(2) R-1的关系矩阵是R的关系矩阵的转置，即MR-1=MRT；(3)

30、 R-1的关系图就是将R的关系图中的弧改变方向后得到的关系图。(4) 从逆关系的定义，我们容易看出(R-1)-1=R。第 3 章 集合与关系3.6 复合关系和逆关系 逆关系性质定理3.6.5设R和S均是A到B的关系，则(1)(R-1)-1=R；(2)(RS)-1=R-1S-1；(3)(RS)-1= R-1S-1；(4) 。定理3.6.6设R是A到B的关系，S是B到C的关系，则(RS)-1=S-1R-1。第 3 章 集合与关系3.7二元关系的性质关系的性质定义3.6.1设R是集合X上的关系，(1) 对任意的xX，均有 R，则称R为A上的自反关系(Reflexive Relation)，或称R具有

31、自反性(Reflexivity)。即 R在X上是自反的 。(2) 对任意的xX，均有R，则称R为X上的反自反关系(Anti-reflexive Relation)，或称R具有反自反性(Anti-reflexivity)。即 R在X上是反自反的 。第 3 章 集合与关系3.7二元关系的性质关系的性质(3) 对任意的x，yX，若 R，则必有 R，称R为X上的对称关系(Symmetric Relation)，或称R具有对称性(Symmetry)。即 R在X上是对称的 。(4) 对任意的x，y X，若 R且 R，则必有xy，称R是X上的反对称关系(Antisymmetric Relation)，或称R

32、具有反对称性(Antisymmetry)。即 R在X上是反对称的 反对称的定义也可以表示为第 3 章 集合与关系3.7二元关系的性质关系的性质(5) 设R是集合X上的关系，对任意的x,y,zX，若 R且 R，则必有 R，则称R为X上的传递关系(Transitive Relation)，或称R具有传递性(Transitivity)。即 R在X上是传递的 第 3 章 集合与关系3.7二元关系的性质例3.7.1 设集合A=x, y, z，判定下列A上的关系是否有自反性和反自反性：R1=, , , , ，R2=, , ，R3=, ,。解： R1是自反关系； 2是反自反关系；R3既不是自反关系，又不是反

33、自反关系。例3.7.2 设集合A=1, 2, 3，判定下列关系是否有对称性和反对称性：R1=, , , ， R2=, , ，R3=, ， R4=, , , ，解 R1是对称的；R2是反对称的；R3既是对称关系，又是反对称关系； R4既不是对称关系，又不是反对称关系第 3 章 集合与关系3.7二元关系的性质例3.7.3 设A=a, b, c，判定下列关系是否有传递性：R1, , ， R2, ,， R3, 。解 R1是传递的，R2不是传递的，但R3是传递的。因为，若将传递性的定义符号化为：xyz(x Ay Az A R R R)永真。在R3中没有使得符号化定义的前件为真的情况，即前件永假，亦即符号

34、化定义永真，因此，R3具有传递性。第 3 章 集合与关系3.7二元关系的性质注意 (1) 不存在既自反又反自反的关系；(2) 判定A上的关系R是否具有某种性质时，一定要注意结合集合来判断。(3) 反对称不是对对称关系的否定，而是要求更多的限制。反对称性定义可等价表述为：对任意的x，y A，若xy且 R，则必有 R。即不相同的两个元素x，y，可组成的两个有序对，在反对称关系中，至多能出现一个。反对称性定义的否命题说法并不成立，如“xy， R，则 R”并不成立。(4) 若R不是对称关系，则R未必一定是反对称关系。即一个关系可能既不是对称关系，也不是反对称关系。另一方面，一个关系可既有对称性，又有反

35、对称性。第 3 章 集合与关系3.7二元关系的性质关系图、关系矩阵与关系的性质关系特性关系矩阵特征关系图特征自反性对角线元素全为1每个结点均有自回路反自反性对角线元素全为0每个结点均无自回路对称性矩阵对称两个不同的结点间若有边，则成对出现反对称性若1i，jn且ij，则aijaji=0两个不同的结点之间，至多有一条边，但允许是没有边传递性若有正整数kn使aikakj=1，则aij=1(从关系矩阵较难看出)若结点xi到xj有路，则xi到xj必有直达边第 3 章 集合与关系3.8关系的闭包运算定义3.8.1 R是非空集合A上的关系，若有A上的关系R满足如下三条：RR；R是自反的(对称的、传递的)；

36、对A上任一个关系R ，若RR且R具有自反性（对称性、传递性），则有R R，则称关系R为R的自反(对称、传递)闭包（Closure），记作r(R)，(s(R)、t(R)。注意 由知R是R的扩张；由(2)知R扩张的目的是使其具有自反性(对称性，传递性)；由(3)知，扩张后得到的新关系R，是R的具有自反性(对称性，传递性)的所有扩张中最小的一个，即要在保证其具有自反性(对称性，传递性)的前提下，尽量少添加元素。第 3 章 集合与关系3.8关系的闭包运算例3.8.1 设集合A=a, b, c, d，A上的关系R=, , 则自反闭包r(R)=, , , , 对称闭包s(R)=, , , , 传递闭包t(

37、R)=, , , 第 3 章 集合与关系3.8关系的闭包运算定理3.8.1设R是非空集A上的关系，则R是自反的充要条件是R=r(R)；R是对称的充要条件是R=s(R)；R是传递的充要条件是R=t(R)。证明 必要性：由对称闭包的定义显然Rs(R)，要证明R=s(R)只须证明s(R) R。又因为R R且R是对称的，则由对称闭包的定义的第条有s(R) R，综合上述得R=s(R)。充分性：因为s(R)是对称的，所以R=s(R)是对称的。可以类似证明、。第 3 章 集合与关系3.8关系的闭包运算第 3 章 集合与关系3.8关系的闭包运算第 3 章 集合与关系3.8关系的闭包运算Warshall提出了一

38、个求R+的有效计算方法：设R是n个元素集合上的二元关系，MR是R的关系矩阵，第一步：置新矩阵M，MMR；第二步：置i，i1；第三步：对j(1jn)，若M的第j行i列处为1，则对k=1,2,n作如下计算：将M的第j行第k列元素与第i行第k列元素进行逻辑加，然后将结果送到第j行k列处，即 Mj,k Mj,kMi,k；第四步：ii+1；第五步：若in，转到第三步，否则停止。Warshall算法为计算机解决集合分类问题奠定了基础。第 3 章 集合与关系3.8关系的闭包运算定理3.8.4设R为集合A上的二元关系，则(1)R是自反的，则s(R)和t(R)是自反的；(2)R是对称的，则r(R)和t(R)是对

39、称的；(3)若R是传递的，则r(R)是传递的。定理3.8.5设R是集合A上的二元关系，则(1)rs(R)=sr(R)；(2)rt(R)=tr(R)；(3)st(R) ts(R)。证明 设IA表示集合A上的恒等关系，显然 。(1)rs(R)=r(RR-1)=RR-1IA=RIAR-1IA=(RIA)(RIA)-1=s(RIA)=sr(R)。(2)(3)略习惯上记t(R)=R+，rt(R)=R*。第 3 章 集合与关系 3.9 集合的划分与等价关系定义3.9.1任意给定一个非空集合S，若有集合族=S1,S2,Sn，使得有Si且SiS(i=1,2,n)；(2) S1S2Sn=S。则称集合族是集合S的

40、一个覆盖(Covering)。例 设集合S=a,b,c ，若1=a,a,b,b,c； 2=a,c,b,c ；3=a,b,c ； 4=a,a,b,b ；则1, 2, 3 都是S的覆盖，但 4不是。第 3 章 集合与关系 3.9 集合的划分与等价关系定义3.9.2定义3.9.2 对于非空集合S，若有集合族=S1,S2,Sn使得是集合S的一个覆盖；SiSj=(ij;1i,jn)；则称是集合S的一个划分。中的元素Si称为其划分块或分类。例 设Aa, b, c, d, 给定 1, 2, 3, 4, 5, 6如下： 1=a, b, c,d， 2=a, b,c,d3=a,a, b, c, d， 4=a, b

41、,c 5=,a, b,c, d， 6=a,a,b, c, d 则 1和 2是A的划分, 其他都不是A的划分. 第 3 章 集合与关系 3.9 集合的划分与等价关系在非空集合S的所有划分中，以S中的每一个元素作为一个集合组成的集合族，是S的一个划分，称之为集合S的最大划分；以集合S作为某个集合中的所有元素得到的集合，是S的一个划分，称之为集合S的最小划分。定义3.9.3 设1=A1,A2,Am ， 2=B1,B2,Bn 是非空集合S的两个划分，若对任意Bi 2 ，存在一个Aj 1 ，使得 Bi Aj ，则称 2是1 的细分。若 2是1的细分，并且21 ，则称 2是1的真细分。第 3 章 集合与关

42、系 3.9 集合的划分与等价关系定义3.9.4 设1=A1,A2,Am ， 2=B1,B2,Bn 是非空集合S的两个划分，则称集合族=Ai Bj| Ai Bj , 1 i m j,1 j n 为 1和2 的交叉划分。例如，设X表示所有生物的集合。A=A1,A2，其中A1表示所有植物的集合，A2表示所有动物的集合，则A是集合X的一种分划；B=B1,B2，其中B1表示史前生物，B2表示史后生物，则B也是集合X的一种划分。A , B的交叉划分S=A1 B1 , A1 B2 , A2B1 , A2B2，其中A1B1表示史前植物，A1B2表示史后植物，A2B1表示史前动物，A2B2表示史后动物。第 3

43、章 集合与关系 3.9 集合的划分与等价关系定理3.9.1设A=A1,A2,Am与B=B1,B2,Bn是集合X的两个不同的划分，则A，B的交叉划分是集合X的一种划分。例3.9.3 设集合S=1,2,3,4 ，1=1，2，3，4 ，2=1，2，3，4 ，求 1和2 的交叉划分。解 1和2的交叉划分为 =1，2，3，4。 定理3.9.2任何两种划分的交叉划分都是原各分划的一种细分。第 3 章 集合与关系 3.9 集合的划分与等价关系1. 等价关系 定义3.9.5 设集合A上的二元关系R，同时具有自反性、对称性和传递性，则称R是A上的等价关系。若x, yR，称x等价于y，记作xy。例 3.9.4 （

44、1） 平面上三角形集合中，三角形的相似关系是等价关系。（）数的相等关系是任何数集上的等价关系。（3）一群人的集合中姓氏相同的关系也是等价关系。（4）设A是任意非空集合，则A上的恒等关系IA和全域关系EA均是A上的等价关系。第 3 章 集合与关系 3.9 集合的划分与等价关系例3.9.5 设Z为整数集，k是Z中任意固定的正整数，定义Z上的二元关系R为：任一a，bZ，R的充要条件是a，b被k除余数相同，即k整除a-b，亦即a-b=kq，其中qZ。即R=(aZ)(cZ) (qZ)(a-b=kq)，则R是Z上的等价关系。证明 (1) R是Z上自反关系。aZ，因为a-a=k0，0Z，所以R。 (2) R

45、是Z上对称关系。如果 R，则a-b=kq (qZ)，故b - a =k(-q) (-qZ),于是R。(3) R是Z上对称关系。如果 R且 R，则a-b=kq1，b-c=kq2，(其中q1， q2 Z)，故a-c=(a-b)+(b-c)=k(q1+q2)，(q1+q2Z)，因此， R。所以，R是Z上的等价关系，称为Z上的模k同余关系。当x, y R，常记作 。第 3 章 集合与关系 3.9 集合的划分与等价关系例3.9.6 设集合A=a,b,c,d,e，R=,验证R是A上的等价关系。证明 R的关系矩阵：关系图如图所示关系矩阵中，对角线上的所有元素都是1，关系图上每个结点都有自环，说明R是自反的。

46、关系矩阵是对称的，关系图上任意两结点间或没有弧线连接，或有成对弧出现，故R是对称的。从R的序偶表示式中，可以看出R是传递的。故R是A上的等价关系。第 3 章 集合与关系 3.9 集合的划分与等价关系2等价类 定义3.9.6 设R是非空集合A上的等价关系，对任意xA，令xR=y|yAxRy，称xR为x关于R的等价类，简称为x的等价类，在不引起混乱时，可以将xR简记为x。由等价类的定义可知xR是非空的，因为xRx，xxR。因此，任给集合A及其上的等价关系R，必可写出A上各个元素的等价类。第 3 章 集合与关系 3.9 集合的划分与等价关系例3.9.7 若R是I上的模3同余关系，则元素0、1、2关于

47、R的等价类分别为0=, -6, -3, 0, 3, 6, ；1=, -5, -2, 1, 4, 7, ；2=, -4, -1, 2, 5, 8, 。还可以看出，两个有等价关系的元素，所产生的等价类相同，如0=3=-3=, -6, -3, 0, 3, 6, ；1=4=-2=, -5, -2, 1, 4, 7, ；2=5=-1=, -4, -1, 4, 5, 8, 。第 3 章 集合与关系 3.9 集合的划分与等价关系等价类性质定理3.9.3设R是非空集合A上的等价关系，对任意的x，yA，下面的结论成立。(1)x ，且xA；(2)若xRy，则x=y；(3)若x y，则xy=；(4) 第 3 章 集

48、合与关系 3.9 集合的划分与等价关系第 3 章 集合与关系 3.9 集合的划分与等价关系定义3.9.7 设R为非空集合A上的等价关系，以R的不同的等价类为元素的集合叫做A关于R的商集，记作A/R，即A/R=xR|xA 例3.9.8 (1)设A=0, 1, 2, , 7，R=|x, y A, 且xy(mod 4)，则A在R下的商集是A/R0, 4, 1, 5, 2, 6, 3, 7。整数集I上的模k同余关系R的商集为kz+i|0ik-1，z I，即kz，kz+1，kz+k-1，可以简写为0, 1, 2 , , k-1。(2)非空集合A上的全域关系E是等价关系，对任意x A有xA，商集A/EA。

49、(3)非空集合A上的恒等关系IA是等价关系，商集A/IA =x|xA 。第 3 章 集合与关系 3.9 集合的划分与等价关系定理3.9.4 非空集合A上的等价关系R，其所有等价类的集合，即商集A/R是A的一个划分。证明 (1)由R产生的等价类都是A的非空子集；(2)不同的等价类之间相交为空；(3)所有等价类的并集就是A。因此所有等价类的集合，即商集A/R，就是A的一个划分，称为由R所诱导的划分。例3.9.9 设A=1, 2, 3, 4, 5，R=, , , ，, , , , , , ，则A/R=1, 3, 4, 2，5，即R所诱导的划分为1, 3, 4, 2, 5。第 3 章 集合与关系 3.

50、9 集合的划分与等价关系定理3.9.5 在非空集合A上给定一个划分，可确定A的元素之间的一个等价关系。证明 设A有一个划分=A1, A2, , An，现定义关系R，RAi(AiaAibAi)，即R当且仅当a，b在同一划分块中。可证明该关系R为一个等价关系。(1)aA，a与a在同一划分块中，因此必有R，即R具有自反性。(2)若R，则存在Ai ，使得aAibAi ，所以bAiaAi ，故R，即R具有对称性。(3)若R，且R，由R的定义，则存在i，j，使得a,bAi且b,cAj，由划分的定义，要么Ai=Aj，要么AiAj=，而这里bAiAj，所以Ai=Aj，即a,cAi，因此a,bR, 即R具有传递

51、性。综上所述，R为等价关系从定理的证明，可看出由集合A上的一个划分=A1, A2, , An，可以确定一个与其对应的A上的等价关系R就是 。第 3 章 集合与关系 3.9 集合的划分与等价关系例3.9.10 设集合A=1, 2, 3, 4, 5，有一个划分=1, 5, 2, 3, 4，试由划分 确定A上的一个等价关系R。解 依据定理可设R=1, 51, 5223, 43, 4 =, , , , , , , , 第 3 章 集合与关系 3.9 集合的划分与等价关系例3.9.11 设A是由4个元素组成的集合，试问在A上可以定义多少个不同的等价关系？解 如果直接考虑A上可以定义多少个等价关系，则计算

52、过程比较繁琐，也容易出错。根据定理3.9.5可知集合A上的等价关系与分划存在一一对应的关系，因此此题可转化为考虑A上有多少个不同的分划。将集合A分划为一块：有1种分法；将集合A分划为两块：有 =7 种分法将集合A分划为三块：有 =6种分法将集合A分划为四块：有1种分法因此，集合A上不同等价关系的个数为1+7+6+1=15。第 3 章 集合与关系 3.9 集合的划分与等价关系第 3 章 集合与关系 3.9 集合的划分与等价关系相容关系定义3.9.8 非空集合A上的二元关系R若是自反的，对称的，则称R是相容关系。相容关系R只要求满足自反性与对称性，因此，等价关系必定是相容关系但反之不真。 第 3

53、章 集合与关系 3.9 集合的划分与等价关系例3.9.11设X=boy , girl , computer , artificial , intelligence，R=x , yX且x , y至少有一个相同的字母则R是X上的相容关系。证明：简记X中的元素依次为1，2，3，4，5，则R= , , , , , , , , , , , , , , , , , , R的关系矩阵如下第 3 章 集合与关系 3.9 集合的划分与等价关系定义3.9.9 设R是集合A上的相容关系，CA，如果对于C中任意两个元素a1，a2有a1Ra2，称C是由相容关系R的相容类(Compatible Class)。定义3.9.

54、10 设R是集合A上的相容关系，不能是任何其他相容类的真子集的相容类，称做最大相容类。记作CR。第 3 章 集合与关系 3.10 偏序关系偏序关系的定义定义3.10.1 设A是一个集合，如果A上的一个关系R，满足自反性、反对称性和传递性，则称R是A上的一个偏序关系，并把它记为“”。序偶称作偏序集。若 ，则记作ab，读作“a小于等于b”。有序对称为偏序集。我们指出：这里的“小于或等于”不是指普通数的大小关系的，而是指偏序关系中的顺序性。x“小于或等于”y表示：x排在y的前边，即xy；或x=y。第 3 章 集合与关系 3.10 偏序关系例3.10.1 在实数集R上，小于等于关系“”是偏序关系。因为

55、：（1）对于任何实数aR，有aa成立，故“”是自反的；（2）对任何实数a,bR，如果ab且ba，则必有a=b，故“”是反对称的；（3）对任何实数a,b,cR，如果ab，bc，那么必有ac，故“”是传递的。第 3 章 集合与关系 3.10 偏序关系例3.10.2 设S为任意非空集合，P(S)上的包含关系=|A,BP(S),AB是偏序关系。因为：（1）对于任意A P(S)，有AA，所以“”是自反的； （2）对任意A,BP(S)，若AB且BA，则A=B，所以“”是反对称的； （3）对任意A,B,CP(S)，若AB且BC，则AC，所以“”是可传递的。 第 3 章 集合与关系 3.10 偏序关系例3.1

56、0.3 正整数集I+上的整除关系|=|m,n I+,a整除b是偏序关系。因为： （1）对于任何正整数m I+，有m|m成立，故“|”是自反的；（2）对任何正整数m,n I+，如果m|n且n|m，则必有m=n，故“|”是反对称的；（3）对任何正整数m,n,k I+，如果m|n且n|k，那么必有m|k，故“|”是传递的。第 3 章 集合与关系 3.10 偏序关系例3.10.4 （1）实数集R上的小于关系“”不是偏序关系。因为没有自反性。（2）任意非空集合S的幂集P(S)上的真包含关系“”不是偏序关系。因为没有自反性。例3.10.5设A=1,2,3,4,6,12，则是偏序集。证明：,关系矩阵为显然，

57、偏序关系“”具有自反、反对称和传递性，因此是偏序集第 3 章 集合与关系 3.10 偏序关系偏序关系的哈斯图定义3.10.2在偏序集中，若x，y A，xy，xy，并且没有其它元素z满足xz，zy，则称元素y盖住元素x。并且记COVA=|x, y A，y盖住x。称COVA为偏序集中的盖住关系。显然COVA。显然，对于给定的偏序集，元素之间的“盖住”关系是唯一的，可以利用这一特性画出偏序集的关系图，即哈斯图。画法步骤如下：(1)用小圆圈表示元素；(2)若y盖住x，则把表示y的小圆圈画在表示x的小圆圈之上，并在两个小圆圈之间连一条边，由于所有边的箭头向上，因此略去箭头。根据盖住关系，画出的哈斯图把表

58、示偏序关系的传递性的连线都省略了，具体说，若 COVA， COVA，即xy，yz，显然必有xz。第 3 章 集合与关系 3.10 偏序关系例3.10.6 设A=1,2,3,4,6,12，并设“|”为整除关系，求COVA并画出哈斯图。 解 “|”=,COVA=,。它的哈斯图如3-15所示1361242图3-15“|”哈斯图第 3 章 集合与关系 3.10 偏序关系例3.10.7画出下列偏序集的哈斯图。(1)设是偏序集，其中A=2, 3, 4, 6, 8，=, , , , , , , , , 。解 根据偏序关系，画出的关系图，根据COVA，画出哈斯图，如图3-16所示。63284的关系图63284

59、的哈斯图图3-16 关系图与哈斯图第 3 章 集合与关系 3.10 偏序关系(2) 设A， 是偏序集，A=a, b,c。解 P(A)= , a, b, c, a, b, a, c, b, c, a, b, cCOVA=, a, , b, , c, a, a, b, a, a, c, b, a, b, b, b, c, c, a, c, c, b, c, a, b, a, b, c, a, c, a, b, c, b, c, a, b, c，作出哈斯图如图3-17所示。a,b,ca,bb,cca,cab图3.-17哈斯图第 3 章 集合与关系 3.10 偏序关系例3.10.8设A=2 , 3 ,

60、 6 , 12 , 24 , 36，是A上的整除关系，求偏序集A, 的哈斯图。解：|=2,2,2,6,2,12,2,24,2,36,3,3,3,6, 3,12,3,24,3,36,6,6,6,12,6,24,6,36, 12,12,12,24,12,36,24,24,36,36偏序集A, 的盖住关系为COVA=2,6,3,6,6,12,12,24,12,36243612623图3-18 哈斯图第 3 章 集合与关系 3.10 偏序关系例3.10.9 设Z是整数集，“”为数的大小相等关系，则的哈斯图如图3-19所示。 10122图3-19 哈斯图第 3 章 集合与关系 3.10 偏序关系偏序集中