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

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,

4、c,d，B课桌，灯泡，自然数，老虎，C1,2,3,，D=a,a2,a3,。从方法的定义中可以看出，列举法必须把元素的全体尽列出来，不能遗漏任何一个，并且集合中的元素没有顺序之分且不重复。而描述法是指利用一项规则，概括集合中元素的属性，以便决定某一事物是否属于该集合。如果我们用谓词P(x)表示一个集合中的元素x所具有的属性，则任一集合可表示为x|P(x)，其中竖线“|”前写的是元素的一般表示，右边写出元素应满足（具有）的属性。含义为该集合中的元素x具有属性P。设集合Ax|P(x)，如果P(a)为真，则a A，否则aA。例如：第第 3 章章 集合与关系集合与关系3.1 集合的概念和表示法集合的概念

5、和表示法 本书中用如下专用字母表示常见的集合：N自然数的集合（包含0）；Nm 小于m的自然数集合，即0,1,n-1；I(或Z)整数的集合；I+(或Z+)正整数的集合；I_（或Z_）负整数的集合；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且

6、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 章章 集合与关系集合与关系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。注意符号“”和“”在概念上的区别，“”表示元素与集合间的“属于”关系，“”表示集合间的“包含”关系。集合间的

7、包含关系“”具有下述性质：定理定理3.1.1 设A，B是任意的集合，则（1）AA，称为自反性；（2）若AB且BC，则AC，称传递性；证明：证明：（1）由集合间包含关系的定义直接得证。（2）对任意xA，由AB可知，一定有xA，又由BC可知，一定有xC，因此AC。第第 3 章章 集合与关系集合与关系3.1 集合的概念和表示法集合的概念和表示法 定义定义3.1.2 不包含任何元素的集合是空集(Empty Set)，记作。即=x|P(x)P(x)，P(x)是任意谓词。定理定理3.1.2 对于任意一个集合A，有A。且空集是惟一的。定义定义3.1.3 在一定范围内，如果所有集合均为某一集合的子集，则称该集

8、合为全集全集，记作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|表示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

9、(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的并集并集，由A和B的所有元素所组成，定义为AB=x xA xB；称为集合的并运算并运算。交集(Intersection)：AB称为集合A与B的交集交集，由所有同属于A和B的元素所组成，定义为AB=x xA xB；称为集合的交交运算运算。差集

10、(Difference)：B-A称为B与A的差集差集，或称为A关于B的相对补相对补集集，由所有属于A而不属于B的元素所组成，定义为B-A=x xB xA。补集(Complement)：称为A关于全集U的相对补集，或称为A的绝绝对补集对补集，简称为A的补集补集，由由U中不属于A的所有元素所组成，定义为=x|xU xA。对称差(Symmetric Difference)：称为集合A与B的对称差对称差或布尔和布尔和,由除A和B中共同元素外其它的A和B中元素所组成，定义为=(A-B)(B-A)=(AB)-(AB)。第第 3 章章 集合与关系集合与关系3.2 集合的运算集合的运算 集合运算的文氏图表示集

11、合运算的文氏图表示 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)=A；德德摩根律摩根律 ，。BABABABA第第 3 章章 集合与关系集合与关系3

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

13、|，|B|则AB=|A|+|B|-AB 定理定理3.3.2 S中不具有性质P1，P2，Pm的元素个数为 =+(-1)m(|A1A2Am|)。|21mAAAmiijijji 11 i j m1 i j k m|S|A|AA|AAA|第第 3 章章 集合与关系集合与关系3.4 序偶与笛卡尔积序偶与笛卡尔积 序偶序偶 定义定义3.4.1 由两个元素x，y(允许x=y)按给定次序排成的二元组合称为一个有序对有序对或序偶序偶（Ordered pair），记作，其中称x是有序对的第一元素第一元素，y是有序对的第二元素第二元素。例如，上、下；左、右；34；张华高于李明；中国地处亚洲；平面上点的坐标等。这些实

14、例可分别用序偶表示：；等。从这里可看出序偶是用来刻画两个对象之间的关系。序偶可以看作是具有两个元素的集合。但它与一般集合不同的是序偶具有确定的次序。在集合中a，bb，a，但对序偶。定义定义3.4.2 两个序偶相等，当且仅当 xu，yv。第第 3 章章 集合与关系集合与关系3.4 序偶与笛卡尔积序偶与笛卡尔积 例例3.4.1 设=，求x，y。解解 由定义3.4.2可列出如下方程组：2xy10 x3y5求解得x=5，y=0。第第 3 章章 集合与关系集合与关系3.4 序偶与笛卡尔积序偶与笛卡尔积 序偶的概念可以推广到有序三元组的情况。三元组是一个序偶，其第一元素本身也是一个序偶，可形式化表示为，z

15、。由序偶相等的定义，可以知道，z，w，当且仅当，zw，即xu，yv，zw。今后约定三元组可记作。应该注意的是：当xy时，。同理四元组被定义为一个序偶，其第一元素为三元组，故四元组有形式为，w且 ，w，s 当且仅当(xp)(yq)(zr)(ws)依此类推，n元组可写为，xn且 ，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中元素作第二元素生成的所有有序对的集合称为

16、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,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 序偶与笛卡尔积序偶与

17、笛卡尔积 由笛卡尔积的定义可得：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，(

18、2)AB的充分必要条件是CACB。证明证明(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

19、=An=A时，简记A1A2An为An。定理定理3.4.3 若A、B都是有限集，|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为集合集合

20、A上的二元关系上的二元关系。例例3.5.1 A=0,1，B=x,y,z，则R1=，R2=AB，R3=等都是从A到B的二元关系，R4=和R3同时也是A上的二元关系。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=,R 第第 3 章章 集合与关系集合与关系3.5 关系及其表示关系及其表示例例3.5.3 设A=1,2,3,4,定义A上的关系R为R=|a,bA,(ab)/2=k,kI 则 R=,通常称R为A

21、上的模2同余关系，也可等价地表示为R=|a,bA,a b(mod 2)对于集合A，今后常用到的三个特殊关系：空关系空关系（Empty Relation）：由于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=,是

22、A上的恒等关系，A=A=3。第第 3 章章 集合与关系集合与关系3.5 关系及其表示关系及其表示 定义定义3.5.2 关系R中所有有序对的第一元素的集合称为关系R的定义域定义域（Domain），记作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.5.1 设 R 和 S 是

23、从集合 X 到集合 Y 的两个关系，则 RS，RS，S，R-S 仍是从 X 到 Y 的关系。证证明明 因为 RXY，SXY，所以 RSXY，RSXY；因为S=XY-SXY，所以 R-S=RSXY。故 RS，RS，S，R-S 是从 X 到 Y 的关系。推推论论 设 R 和 S 是从集合 X 到集合 Y 的两个关系，(1)x(RS)yxRyxSy；(2)x(RS)yxRyxSy(3)x(S)yxS y；(4)x(R-S)yxRyxS y。第第 3 章章 集合与关系集合与关系3.5 关系及其表示关系及其表示 关系的表示关系的表示1集合表示法集合表示法关系是一种集合，因而集合的表示方法，诸如列举法、描

24、述法都能用于关系的表示，上面几例给出了这两方法的应用。关系又是一种特殊的集合，因而它又有区别于通常集合的表示方法，对有限集合间的二元关系R除了可以用序偶集合的形式表达以外，还可用矩阵和图形表示，以便引入线性代数和图论的知识来讨论。第第 3 章章 集合与关系集合与关系3.5 关系及其表示关系及其表示 关系的表示关系的表示2矩阵表示法矩阵表示法 设有限集合X=x1,x2,xn，Y=y1,y2,ym，其中m1，n1，R为集合X到集合Y的关系，则R的关系矩阵为MR=rijnm，其中ijijij1,x,yRri 1,2,n,j 1,2,m0,x,yR若（）若如果R是有限集合X上的二元关系或X和Y含有相同

25、数量的有限个元素，则MR是方阵。第第 3 章章 集合与关系集合与关系3.5 关系及其表示关系及其表示例例3.5.6 若A=a1,a2,a3,a4,a5,B=b1,b2,b3，R=,，写出关系矩阵MR。解解:R101011M100010010第第 3 章章 集合与关系集合与关系3.5 关系及其表示关系及其表示例例3.5.7设A=1,2,3,4,写出集合A上大于关系“”的关系矩阵。解解：=,，故00001000M11001110第第 3 章章 集合与关系集合与关系3.5 关系及其表示关系及其表示 3关系图表示法关系图表示法 有限集合的二元关系也可用图形来表示。设集合X=x1,x2,xn到集合Y=y

26、1,y2,ym的一个二元关系为R，以两列结点（小实心黑点）表示集合X、Y中的元素，关系R中的每一有序对，用一带箭头的有向边画出，对任意 R，画一条箭头从结点x指向结点y的有向边(注意x是始点，y是终点，次序不能颠倒)。就得到一个全部由有向边构成的有向图，称为关系R的关系图关系图，记作GR。特别地，当集合X=Y时，只用一列结点表示即可；当R，有向边由结点x指向自身。第第 3 章章 集合与关系集合与关系3.5 关系及其表示关系及其表示 例例3.5.8 画出例3.5.6的关系图。解解 本题的关系图如图3-6所示：第第 3 章章 集合与关系集合与关系3.5 关系及其表示关系及其表示 例例3.5.9设X

27、=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，称为关系的复合运算。复合运算是关系的二元运算，它能够由两个关系生成一个新的关系，以此类推。例如，R是从X到Y的关系，S是从Y到Z的关系，P是从Z到W的关系，则(RS

28、)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，从而可写出关系RS=,。第第 3 章章 集合与关系集合与关系3.6 复合关系和逆关系复合关系和逆关系 例例3.6.2 设R1和R2是集合X0，1，2

29、，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的关系，其关系矩阵MRS是mp阶矩阵，且MRS=MRMS=wij。其中 wij=，按布尔运算进行的矩阵乘法。是求逻

30、辑和：00=0，01=10=11=1；是求逻辑积：00=01=10=0，11=1。)(1kjiknkuu第第 3 章章 集合与关系集合与关系3.6 复合关系和逆关系复合关系和逆关系 例例3.6.3 3.6.3 已知集合已知集合A=1,2,3,4,5A=1,2,3,4,5，B=3,4,5B=3,4,5，C=1,2,3C=1,2,3，A A到到B B的关系的关系R=,R=,，B B到到C C的关系的关系S=,S=,，利用关系矩阵求，利用关系矩阵求RSRS。S100M010001R001010M100001000R SRS001001100010010MMM010100100001001001000

31、000解解 ，所以 RS=,。第第 3 章章 集合与关系集合与关系3.6 复合关系和逆关系复合关系和逆关系 2.关系的复合运算的性质关系的复合运算的性质 定理定理3.6.2 设R是由集合X到Y的关系，则IXR=RIX=R。定理定理3.6.3 设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

32、.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=,，则：R0=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中每一序偶的元素顺序互换，得到的集合

33、称为R的逆关系(Inverse Relation)，记为R-1。即R-1=|R 例如，在实数集上，关系“”。说明说明：(1)R-1就是将R中的所有有序对的两个元素交换次序后得到，故|R|=|R-1|；(2)R-1的关系矩阵是R的关系矩阵的转置，即MR-1=MRT；(3)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)(R

34、S)-1=R-1S-1；(4)。定理定理3.6.6设R是A到B的关系，S是B到C的关系，则(RS)-1=S-1R-1。11(R)R第第 3 章章 集合与关系集合与关系3.7二元关系的性质二元关系的性质 关系的性质关系的性质 定义定义3.6.1设R是集合X上的关系，(1)对任意的xX，均有 R，则称R为A上的自反关系自反关系(Reflexive Relation)，或称R具有自反性自反性(Reflexivity)。即 R在X上是自反的。(2)对任意的xX，均有R，则称R为X上的反自反关系反自反关系(Anti-reflexive Relation)，或称R具有反自反性反自反性(Anti-refle

35、xivity)。即 R在X上是反自反的。x(xX)x,xR)x(xX)(x,xR)第第 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具有反对称性反对称性(Antisymmetry)。即 R在X上是反对称的 x y(xX)(yX)(x,yR)(y,x

36、R)x y(x X)(y X)(x,yR)(y,xR)(xy)反对称的定义也可以表示为x y(xX)(yX)(x,yR)(xy)(y,xR)第第 3 章章 集合与关系集合与关系3.7二元关系的性质二元关系的性质 关系的性质(5)设R是集合X上的关系，对任意的x,y,zX，若 R且 R，则必有 R，则称R为X上的传递关系传递关系(Transitive Relation)，或称R具有传递性传递性(Transitivity)。即 R在X上是传递的 x y z(x X)(y X)(z X)(x,yR)(y,zR)(x,zR)第第 3 章章 集合与关系集合与关系3.7二元关系的性质二元关系的性质例例3.

37、7.1 设集合A=x,y,z，判定下列A上的关系是否有自反性和反自反性：R1=,，R2=,，R3=,。解：解：R1是自反关系；2是反自反关系；R3既不是自反关系，又不是反自反关系。例例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是传

38、递的。因为，若将传递性的定义符号化为：xyz(x Ay Az A R R R)永真。在R3中没有使得符号化定义的前件为真的情况，即前件永假，亦即符号化定义永真，因此，R3具有传递性。第第 3 章章 集合与关系集合与关系3.7二元关系的性质二元关系的性质注意注意 (1)不存在既自反又反自反的关系；(2)判定A上的关系R是否具有某种性质时，一定要注意结合集合来判断。(3)反对称不是对对称关系的否定，而是要求更多的限制。反对称性定义可等价表述为：对任意的x，y A，若xy且 R，则必有 R。即不相同的两个元素x，y，可组成的两个有序对，在反对称关系中，至多能出现一个。反对称性定义的否命题说法并不成立

39、，如“xy，R，则 R”并不成立。(4)若R不是对称关系，则R未必一定是反对称关系。即一个关系可能既不是对称关系，也不是反对称关系。另一方面，一个关系可既有对称性，又有反对称性。第第 3 章章 集合与关系集合与关系3.7二元关系的性质二元关系的性质 关系图、关系矩阵与关系的性质关系图、关系矩阵与关系的性质关系特性关系矩阵特征关系图特征自反性对角线元素全为1每个结点均有自回路反自反性对角线元素全为0每个结点均无自回路对称性矩阵对称两个不同的结点间若有边，则成对出现反对称性若1i，jn且ij，则aijaji=0两个不同的结点之间，至多有一条边，但允许是没有边传递性若有正整数kn使aikakj=1，

40、则aij=1(从关系矩阵较难看出)若结点xi到xj有路，则xi到xj必有直达边第第 3 章章 集合与关系集合与关系3.8关系的闭包运算关系的闭包运算 定义定义3.8.1 R是非空集合A上的关系，若有A上的关系R满足如下三条：RR；R是自反的(对称的、传递的)；对A上任一个关系R，若RR且R具有自反性（对称性、传递性），则有R R，则称关系R为R的自反自反(对称对称、传传递递)闭包闭包（Closure），记作r(R)，(s(R)、t(R)。注意注意 由知R是R的扩张；由(2)知R扩张的目的是使其具有自反性(对称性，传递性)；由(3)知，扩张后得到的新关系R，是R的具有自反性(对称性，传递性)的所

41、有扩张中最小的一个，即要在保证其具有自反性(对称性，传递性)的前提下，尽量少添加元素。第第 3 章章 集合与关系集合与关系3.8关系的闭包运算关系的闭包运算例例3.8.1 设集合A=a,b,c,d，A上的关系R=,则自反闭包r(R)=,对称闭包s(R)=,传递闭包t(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是对

42、称的，则由对称闭包的定义的第条有s(R)R，综合上述得R=s(R)。充分性：因为s(R)是对称的，所以R=s(R)是对称的。可以类似证明、。第第 3 章章 集合与关系集合与关系3.8关系的闭包运算关系的闭包运算第第 3 章章 集合与关系集合与关系3.8关系的闭包运算关系的闭包运算第第 3 章章 集合与关系集合与关系3.8关系的闭包运算关系的闭包运算 Warshall提出了一个求R+的有效计算方法：设R是n个元素集合上的二元关系，MR是R的关系矩阵，第一步：置新矩阵M，MMR；第二步：置i，i1；第三步：对j(1jn)，若M的第j行i列处为1，则对k=1,2,n作如下计算：将M的第j行第k列元素

43、与第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)是对称的；(3)若R是传递的，则r(R)是传递的。定理定理3.8.5设R是集合A上的二元关系，则(1)rs(R)=sr(R)；(2)rt(R)=tr(R)；(3)st(R)ts(R)。证明证明

44、设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的一个覆盖覆盖(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

45、；则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,c 5=,a,b,c,d，6=a,a,b,c,d 则 1和 2是A的划分,其他都不是A的划分.第第 3 章章 集合与关系集合与关系 3.

46、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 章章 集合与关系集合与关系 3.9 集合的划分与等价关系集合的划分与等价关系 定义定义3.9.4 设设 1=

47、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,A

48、1 B2,A2B1,A2B2，其中其中A1B1表示史前植物，表示史前植物，A1B2表示史后植物，表示史后植物，A2B1表示史前表示史前动物，动物，A2B2表示史后动物。表示史后动物。第第 3 章章 集合与关系集合与关系 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

49、的交叉划分为的交叉划分为 =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（1）平面上三角形集合中，三角形的相似关系是等价关系。（）数的相等关系是任何数集上的等价关系。（3）一群人的集合中姓氏相同的关系也是等价关系。（4）设A是任意非空集合，则A上的

50、恒等关系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是Z上对称关系。如果 R，则a-b=kq(qZ)，故b-a=k(-q)(-qZ),于是R。(3)R是Z上对称关系。如果 R且 R，则a-b=kq