离散数学课件(第3章)

1、离散数学教案,计算机科学与技术学院 课程学时：64 主 讲：宋 成,河南理工大学电子教案,第二篇：集合论,集合论是研究集合的一般性质的数学分支，它研究集合不依赖于组成它的事物的特性的性质。 在现代数学中，每个对象（如数，函数等）本质上都是集合，都可以用某种集合来定义。数学的各个分支本质上都是在研究这种或那种对象集合的性质。集合论已经称为全部现代数学的理论基础。,第二篇：集合论,集合论的特点是研究对象的广泛性。它总结出由各种对象组成的集合的共同性质，并用统一的方法来处理。因此，集合论被广泛应用于各个科学和技术领域中。 由于集合论的语言适合描述和研究离散对象及其关系，所以也是计算机科学与工程的理论

2、基础，在程序设计、关系数据库、排队论、开关理论、形式语言和自动机理论等学科领域中都有重要的应用。 本篇主要介绍：集合、二元关系和函数,第三章：集合与关系,3.1集合的概念与表示 3.2集合的运算 3.3序偶与笛卡尔积 3.4关系及其表示 3.5关系的性质 3.6复合关系和逆关系 3.7关系的闭包运算 3.8集合的划分和覆盖 3.9等价关系与等价类 3.10相容关系 3.11序关系,第三章：集合与关系,教学目的及要求： 深刻理解和掌握有关集合和关系的基本概念和基本运算。 教学类容： 集合的概念和表示方法、集合的运算、序偶与笛卡尔积、关系及其表示、关系的性质、复合关系和逆关系、关系的闭包运算、集合

3、的划分和覆盖、等价关系与等价类、相容关系、序关系。 教学重点： 关系及关系的运算、等价关系、序关系 教学难点：关系的闭包运算、等价关系、等价类。,第三章：集合与关系,3.1 集合的概念与表示 1、集合的基本概念 【定义】具有某种特定性质的事物（客体）的总体。 这里的“事物”可以是人，物品，也可以是数学元素。 定义的讨论： 符号表示： 通常用大写的英文字母表示，如A、B、C等。组成集合的对象叫做集合的元素或成员，常用小写的英文字母表示。,第三章：集合与关系,集合的性质 确定性：所谓确定的，是指任何一个对象是不是集合的元素是明确的、确定的，不能模棱两可。每一个对象都能确定是不是某一集合的元素，没有

4、确定性就不能成为集合，例如“个子高的同学”“很小的数”都不能构成集合。这个性质主要用于判断一个集合是否能形成集合。 互异性：集合的元素又是能区分的，能区分的是指集合中的元素是互不相同的。如果一个集合中有几个元素相同，算做一个。例如集合1,2,3,3和1,2,3是同一集合。 无序性：集合的元素又是无序的，即1,2,3和3,1,2是同一集合,第三章：集合与关系,集合与元素的关系： 设S是集合，a是S的一个元素，记为aS，读做“a属于S”，也可读做“a在S中”。如果a不是S的元素，记为aS，读做“a不属于S ”，也可读做“a不在S中”。例如：26个英文字母组成一个集合，任一英文字母是该集合的元素。河

5、南理工大学全体学生组成一个集合，该校的每一个学生是这个集合的元素。 集合的基数（势）： 集合中元素的个数，假设集合为S，则集合S的基数为|S|，根据集合的基数（元素）是否为有限个，又分为有限集合和无限集合,第三章：集合与关系,2、集合的表示方法 集合有三种表示法。 列举法：在花括号“”中列举出该集合的元素，元素之间用逗号隔开。 例如：I5=1,2,3,4,5 I+=1,2,3, I =0,1,-1,2,-2, S=T,F 第二种表示法是描述法：用谓词界定集合的元素。 例如： Q=x | x是有理数 R=x | x是实数 C=x | x是复数 A=x | x I0 xx5 文氏图法：用一条封闭的

6、曲线的内部来表示一个集合的方法，人们常用文氏图描述集合运算和它们之间的关系。如图3.1 （形象，直观）。,第三章：集合与关系,3、集合间的关系 【定义】设A，B是任意的集合，当A的每一元素都是B的元素时，则称A是B的子集，也称A包含在B内或B包含A。记为AB或BA。 当A不是B的子集时，记为AB。 AB用谓词公式表示为：AB(x)(xAxB) AB用谓词公式表示为： AB(x)(xAxB) 例如：设A=1，B=1,2，C=1,2,3 则 AA AB，BC，AC CB 可以证明，集合的包含有下列性质： 自反性。即对任意集合A，AA。 传递性。即对任意集合A、B、C，当AB和BC时，AC。,第三章

7、：集合与关系,【定义】设A，B是集合，如果AB且BA，则称A与B相等。记为A=B。如果A与B不相等，记为AB。 集合相等也可用谓词公式表示为： A=BABBA (x)(xAxB)(x)(xBxA) (x)(xAxB) 例如：设 A=1,2，B=1, 2，C=2,1 则 A=C，AB 由集合相等的定义可以看出，集合相等有下列性质： 自反性: 即对任意集合A，A=A。 对称性: 即对任意集合A、B，当A=B时，B=A。 传递性: 即对任意集合A、B、C，当A=B和B=C时，A=C。,第三章：集合与关系,【定义】 设A，B是集合，如果AB且AB，则称A是B的真子集。记为AB。如果A不是B的真子集，记

8、为AB。 真子集用谓词公式表示为： ABABAB (x)(xAxB)(x)(xBxA) 例如：设 A=a，B=a,b，C=a,b,c 则 AB，BC，AC AA 又如，自然数集是整数集合的真子集，也是有理数集合和实数集合的真子集，即NI，NQ，NR。,【 定义】 不包含任何元素的集合叫空集。记为。 空集可以表示为： =x | P(x)P(x) 其中，P(x)为任意谓词 空集是不包含任何元素的集合，所以，|=0。 【 定理1】 空集是任意集合的子集。 证明：设A是任意集合。对任意对象x，由空集的定义知，x为假，由条件联结词的定义知，xxA为真。根据全称推广规则有 (x)( xxA) 为真，故A,

9、第三章：集合与关系,根据定理1，空集是任意集合的子集，即A；对任意集合A，AA。一般地说，任意集合A至少有两个子集，一个是空集，另一个是它本身A。 推论 空集是惟一的。 证明：设有两个空集1和2，由定理1有12和21，根据集合相等的定义知，1=2。 【定义】 在一个具体问题中，如果所涉及的集合都是某个集合的子集，则称这个集合为全集。记为E。 全集是相对的，不同的问题有不同的全集。即使是同一问题也可以取不同的全集。,第三章：集合与关系,第三章：集合与关系,4、幂集合 【定义】 设A是集合，A的所有子集构成的集合称为A的幂集合，记为P (A)，即 P (A) =S | SA 【例】设A=a,b,c

10、，是空集，试求 P (A)，P (P ()。 解：P (A)= ,a,b,c,a,b,a,c,b,c,a,b,c P ()= P (P () = , ,第三章：集合与关系,第三章：集合与关系,3.2 集合的运算 【定义】 设A，B是任意的集合，由A中的元素或B中的元素组成的集合，称为A和B的并集，记为AB。 AB=x |xAxB 并集的定义如图3.2所示。 从并集的定义可以得到： AAB，BAB,第三章：集合与关系,【 定义】 设A，B是集合，由A与B的公共元素组成的集合，称为A和B的交集，记为AB。 AB=x |xAxB 交集的定义如图3.3所示。 从交集的定义可以得到： ABA，ABB 如

11、果A与B无公共元素，即AB=，则称A和B是互不相交的。 例如，令A=a,b,c，B=d,e，则AB=，A和B是互不相交的。,第三章：集合与关系,【定义】 设A，B是集合，属于A的而不属于B的元素组成的集合，称为B对于A的补集，也叫B对于A的相对补集。记为A-B。 A-B=x |xAxB 相对补集定义如图3.4所示。 【例】令A=,，B=， 则A-B=,-=, 又如，令C=a，D= a,b，则 C-D =a-a,b= C-C= ,第三章：集合与关系,【定义】 设A是集合，A对于全集E的相对补集，称为A的绝对补集，记为A。 A=E-A=x |xExA=x | xA A的定义如图3.5所示。 例如，

12、令全集E=1,2,3,4，A= 1,2,3 则 A=1,2,3,4-1,2,3=4,【例】设A,B是任意的集合，求证: A-B= A(B) 证明： xA-BxAxBxAxB xAB 即 A-B AB。 xABxAxBxAxBxA-B 故 ABA-B 所以，A-B= A(B)。 A-B=A(B)是一个重要的公式，在集合的运算中经常用到，它的意义在于将相对补运算转换绝对补和交运算。,第三章：集合与关系,【定义】设A，B是集合，由 A中元素或B中元素，但不是A与B的公共元素组成的集合，称为A和B的对称差，记为A B。 A B=x |xA xB=(AB)-(AB) A B的定义如图3.6所示。 例如，

13、令A=1,2,3,4， B= 1,2,5,6，则 A B=AB-AB =1,2,3,4,5,6-1,2 =3,4,5,6,第三章：集合与关系,【例】设A,B是任意的集合，求证: A B=(A-B)(B-A)=(AB)(BA)。 证明：先证A B=(A-B)(B-A)。 xA BxAxB (xAxB)(xAxB) xA-BxB-A x(A-B)(B-A) 所以，A B=(A-B)(B-A)。 再证(A-B)(B-A)=(AB)(BA)。 由前面一个例子很容易得到此结论。这里从略。,第三章：集合与关系,利用上例中的公式可以证明对称差A B下列的性质。 设A,B是任意的集合。 A A= 证明：A A

14、=(A-A)(A-A) = = A = A 证明：A =(A-)(-A)=A =A A E= A 证明：A E=(A-E)(E-A)= A= A,为了使集合的表达式更加简洁，我们对集合运算的优先顺序规定如下： 绝对补的运算级别比其它的4个运算高，先进行绝对补运算，再进行其它的4个运算；其它的4个运算的运算顺序由括号决定。,第三章：集合与关系,用文氏图不仅可以表示集合的运算和它们之间的关系，而且还可以很方便地解决有限集合的计数问题。 用文氏图解决有限集合的计数问题的方法是： 每一条性质定义一个集合，画一个圆表示这个集合。如果没有特别说明，任何两个圆画成相交的。将已知集合的元素数填入表示该集合的区

15、域内。通常从n个集合的交集填起，根据计算的结果逐步将数字填入其它各空白区域内。 如果交集的值是未知的，可以设为x。根据题目的条件，列出方程或方程组，求出所需的结果。,第三章：集合与关系,【例】某班有50名学生，第一次考试中26人成绩为优，第二次考试中21人成绩为优，已知两次考试中都不为优的共17人。问两次考试中都为优的有多少人？ 解：设A，B分别表示第一次和 第二次考试中成绩为优的学生集合。 画出文氏图，如图3.7所示。首先填 AB中的人数，这正是要求的，设 为x。A-B中的人数是26-x，B-A中 的人数是21-x，分别填入对应的区 域。并列出如下 方程： (26-x)x(21-x)17=5

16、0 解得：x=14,第三章：集合与关系,3.3 序偶与笛卡尔积 【定义】两个个体x，y的有序序列，称为二重组，也称为有序对或序偶。记为x,y。x，y分别叫做二重组的第一分量和第二分量。 所谓有序序列是指调换第一分量和第二分量位置后，就和原来的含义不同了。 【定义】设x,y与a,b是两个二重组，如果x=a且y=b，则称二重组x,y与a,b相等，记为x,y=a,b。 二重组x,y与a,b相等，用逻辑的方法表示为 (x,y=a,b)(x=a)(y=b)。 由定义可以看出，当xy时，x,yy,x。 例如，平面上的点P1=2,1和点P2=1,2是两个不同的点，它们都是二重组。,第三章：集合与关系,【定义

17、】 二重组x1,x2,xn-1,xn叫做n重组。记为x1,x2,xn，xi叫做该n重组的第i个分量i=1,n。 由定义可看出：三重组x1,x2,x3定义为x1,x2,x3，其中第一分量是二重组；四重组x1,x2,x3,x4定义为x1,x2,x3,x4，其中第一分量是三重组；。 根据三重组的定义，第一分量是二重组，第二分量是一个个体的序偶x1,x2,x3是3重组。而第一分量是一个个体，第二分量是二重组的序偶x1,x2,x3不是三重组。这个结论对任意的n(n=3,4,5,)重组也是对的。例如，x1,x2,x3,x4是四重组，而x1,x2,x3,x4不是四重组；x1,x2,x3,x4,x5是五重组，

18、而x1,x2,x3,x4,x5不是五重组。,第三章：集合与关系,【定义】 设x1,x2,xn与y1,y2,y n是两个n重组，如果xi=yi，i=1,n，则称这两个n重组相等，记为 x1,x2,xn=y1,y2,y n。 n重组x1,x2,xn与y1,y2,y n相等，用逻辑的方法表示为 (x1,x2,xn=y1,y2,y n) (x1= y1)(x2= y2)(xn= yn)。 【定义】 设A，B是集合，集合a,b| aAbB叫做A，B的笛卡尔积，也叫A，B的叉乘积，直积。记为： AB。 如果A，B都是有限集，|A|= n，|B|= m，根据排列组合原理，|AB|=nm=|A|B|。,第三章

19、：集合与关系,【例】设 A=a,b，B=1,2,3， 试求AB和BA 验证|AB|=|A|B|和|BA|=|B|A| 解：求AB和BA AB=a,1,a,2,a,3,b,1,b,2,b,3 BA=1,a,1,b,2,a, 2,b,3,a, 3,b 验证|AB|=|A|B|和|BA|=|B|A| |AB|=6=23=|A|B| |BA|=6=32=|B|A|,如果把看成运算，笛卡尔积有以下的性质： 设A为任意的集合，则A = A= 一般地说，不满足交换律：即ABBA。 在上例中，ABBA 一般地说，不满足结合律：即(AB)CA(BC),第三章：集合与关系,【定理】 设A，B，C是集合，则 A(B

20、C) =(AB)(AC) A(BC) =(AB)(AC) (AB)C =(AC)(BC) (AB)C =(AC)(BC) 证明：仅证明, 可类似地证明、。 a,bA(BC) aAbBC aA( bBbC) (aAbB)(aAbC) a,bABa,bAC a,b(AB)(AC) 故 A(BC)=(AB)(AC),第三章：集合与关系,【定理】 设A，B，C是集合，C，则 AB的充分必要条件是ACBC AB的充分必要条件是CACB 证明: 仅证明,可类似地证明。 设AB，下证 AC BC a,bACaAbC aBbC a,bBC 所以 ACBC 设ACBC，下证 AB 因为C，所以存在bC aAaA

21、bCa,bAC a,bBCaBbCaB 所以 AB,第三章：集合与关系,【定理】 设A，B，C，D是非空集合，则 ABCD的充分必要条件是AC且BD。 证明： 设ABCD， 下证 AC且BD aAbBa,bAB a,bCD aCbD 所以 AC且BD 设AC且BD，下证ABCD a,bABaAbB aCbD a,bCD 所以 ABCD,第三章：集合与关系,【定义】 叉乘积A1A2An定义为 (A1A2An-1)An， 即A1A2An =a1, a2, an| a1A1a2A2anAn 由定义可以看出： 当n=3时，A1A2A3定义为(A1A2)A3 A1A2A3=a1, a2, a3| a1A

22、1a 2A2a3A3 当n=4时，A1A2A3A4定义为(A1A2A3)A4 A1A2A3A4 =a1, a2, a3, a4| a1A1a2A2a3A3a4A4 约定 An=,第三章：集合与关系,【例】设A=1,2，B=a,b，A=x,y，求： ABC，A(BC)。 解： ABC=(AB)C =1,a,1,b,2,a,2,bx,y =1,a, x,1,b, x,2,a,x, 2,b,x, 1,a, y,1,b, y,2,a,y, 2,b,y =1,a,x,1,b,x,2,a,x, 2,b,x, 1,a,y,1,b, y,2,a,y, 2,b,y A(BC)=1,2a,x,a, y,b,x,b

23、, y =1,a,x,1,a, y,1,b,x,1,b, y 2,a,x,2,a, y,2,b,x,2,b, y 显然ABCA(BC)。,第三章：集合与关系,3.4关系及其表示 1、二元关系的概念 【定义】设A和B是任意集合，如果RAB，则称R是A到B的二元关系。如果R是A到A的二元关系，则称R是A上的二元关系。 设A=1,2,3，B=a,b，R=1,a,2,a,3,b。R是A到B的二元关系。S=3,1,2,2,2,1,1,1。S是A上的二元关系。 【定义】设A和B是任意集合，RAB，若x,yR，则称x与y有R关系。记为xRy。若x,yR，则称x与y没有R关系。记为x y。,第三章：集合与关系

24、,如果R是A到B的二元关系，根据【定义】，x,yR与 xRy，x,yR与x y的意义相同。 【定义】设A和B是任意集合，空集叫做A到B的空关系，仍然记为。A，B的笛卡尔积AB叫做A到B的全域关系，记为E。集合a,a|aA叫做A上的恒等关系。记为IA。 【例1】设A=a,b，B=1,2，求A上的恒等关系IA和 A到B的全域关系AB。 解：A上的恒等关系IA=a,a,b,b，A到B的全域关系E =AB=a,1,a,2,b,1,b,2 【定理】设A是具有n个元素的有限集，则A上的二元关系有2n2种。 证明：设A为具有n个元素的有限集，即|A|=n，由排列组合原理知|AA|=n2。根据幂集合定理定理有

25、|P (AA) |=2|AA|=2 ，即AA的子集有2 个。所以具有n个元素的有限集A上有2 种二元关系。,第三章：集合与关系,2、关系的表示 （1）用列举法表示二元关系 上例中的A到B的全域关系 E=AB=a,1,a,2,b,1,b,2 A上的恒等关系: IA=a,a,b,b 都是用列举法表示的。 （2）用描述法表示二元关系 设R是实数集，LR= x,y | xRyRxy， LR是实数集R上的二元关系。,（3）用矩阵表示二元关系 如果A，B是有限集， A=a1,a2,am， B=b1,b2,bn， R是A到B的二元关系，R的关系矩阵定义为： MR= mn,第三章：集合与关系,i=1,m j=

26、1,n 称为二元关系R的关系矩阵。,【例2】设A=a1,a2,a3,a4，B=b1,b2,b3，R是A到B的二元关系，定义为： R=a1,b1,a1,b3,a2,b2,a2,b3,a3,b1,a4,b1,a4,b2 写出R的关系矩阵。 解：R的关系矩阵为：,MR=,第三章：集合与关系,第三章：集合与关系,（4）用图表示二元关系 如果A和B是有限集，R是A到B二元关系，还可以用图表示二元关系R。表示二元关系R的图叫做R的关系图。A到B二元关系的关系图和A上的二元关系的关系图的定义是不一样的。分别描述如下： A到B二元关系R的关系图 设A=a1,a2,am，B=b1,b2,bn，R是A到B二元关系

27、，R的关系图的绘制方法如下： 画出m个小圆圈表示A的元素，再画出n个小圆圈表示B的元素。这些小圆圈叫做关系图的结点(下同)。 如果ai,bj R，则从ai到bj画一根有方向(带箭头)的线。这些有方向(带箭头)的线叫做关系图的边(下同)。,第三章：集合与关系,【例2】中的二元关系R的关系图如图3.8。 A上的二元关系R的关系图 设A=a1,a2,am，R是A上的二元关系，其关系图如下绘制： 画出m个小圆圈表示A的元素。 如果ai,ajR，则从ai到aj画一根有方向(带箭头)的线。 【例3】中的二元关系R的关系图如图3.9。,第三章：集合与关系,3、关系的运算 【定义】设A，B是集合，RAB。 d

28、om R=x|x,yR 叫做R的定义域。 ran R=y| x,yR 叫做R的值域。 FLD R= dom Rran R叫做R的域。 A叫做R的前域；B叫做R的陪域。 二元关系的交、并、补、对称差运算 【定理】设R，S是X到Y的二元关系，则RS，RS，R-S，R，R S也是X到Y的二元关系。 证明：因为R，S是X到Y的二元关系，所以， RXY且SXY。显然， RSXY，即RS是X到Y的二元关系。 RSXY，即RS是X到Y的二元关系。 R-SXY，即R-S是X到Y的二元关系。,第三章：集合与关系,在二元关系运算中，认为全域关系是全集。所以 R= XY-R XY，即R是X到Y的二元关系。 由以上结

29、论可以得到： (RS)XY和(SR)XY，从而 (RS)(SR)XY，所以 R S=(RS)(SR)XY，即R S是X到Y的二元关系。 【例4】设X=1,2,3,4，X上的二元关系H和S定义如下： H=x,y | 是整数 S=x,y | 是正整数 试求HS，HS，H，S-H,第三章：集合与关系,解：将H和S用列举法表示： H=1,1,1,3,2,2,2,4,3,3,3,1,4,4,4,2 S=4,1 HS=1,1,1,3,2,2,2,4,3,3,3,1,4,4, 4,2,4,1 HS= H=X2- H=1,2,1,4,2,1,2,3,3,2,3,4, 4,3,4,1 SH=4,1,第三章：集合

30、与关系,3.5关系的性质 【定义】设RXX，(x)(xXx,xR)，则称R在X上是自反的。 设R是X上的自反关系，由【定义】知，R的关系矩阵MR的主对角线全为1；在关系图中每一个结点上都有自回路。 设X=1,2,3，X上的二元关系 R=1,1,2,2,3,3,1,2 R是自反的,它的关系图如图3.10所示， 关系矩阵如下： MR=,第三章：集合与关系,【定理】设R是X上的二元关系，R是自反的当且仅当IXR。 证明：设R在X上是自反的，下证IXR。 x,yIXx=yx,yR，即IXR。 设IXR，下证R在X上是自反的。 xXx,xIXx,xR，即R在X上是自反的。 【定义】设RXX，(x)(xX

31、x,xR)，则称R在X上是反自反的。 设R是X上的反自反关系，由【定义】可知，R的关系矩阵MR的主对角线全为0；在R的关系图中每一个结点上都没有自回路。 设X=1,2,3，X上的二元关系R=1,2,2,3,3,1，R是反自反的,它的关系图如图3.11所示，关系矩阵如下：,第三章：集合与关系,MR =,【例】设R是实数集合， =x,y| xRyRxy 是实数集合上的大于关系。证明实数集合上的大于关系是反自反的。 证明：xR，xx，x,x，所以是反自反的。,第三章：集合与关系,【定理】 设R是X上的二元关系, R是反自反的当且仅当RIX=。 证明：设R在X上是反自反的，下证RIX=。 假设RIX

32、必存在 x,yRIXx,yRx,yIXx,yR x=y，即x,xR，这与R是X上的反自反关系相矛盾。所以RIX=。 设RIX=，下证R在X上是反自反的。 任取xX x,xIX，由于RIX=，必然x,xR，即R在X上是反自反的。,第三章：集合与关系,【例】设A=1,2,3，定义A上的二元关系如下： R=1,1,2,2,3,3,1,3 S=1,3 T=1,1 试说明R，S，T是否是A上的自反关系或反自反关系。 解：因为1,1、2,2和3,3都是R的元素，所以R是A上的自反关系，不是反自反关系。因为1,1、2,2和3,3都不是S的元素，所以S是反自反关系，不是A上的自反关系。因为2,2T，所以T不是

33、A上的自反关系。因为1,1T，所以T不是A上的反自反关系,第三章：集合与关系,【定义】 设RXX， (x)(y)(xXyXx,yR y,xR)，则称R在X上是对称的。 R是X上的对称关系，由定义知，R的关系矩阵MR是对称阵。在R的关系图中，如果两个不同的结点间有边，一定有方向相反的两条边。 设X=1,2,3，X上的二元关系R=1,2,2,1,3,3，R是对称的。它的关系图如图3.12所示，关系矩阵如下： MR=,第三章：集合与关系,【例】设A=1,3,5,7，定义A上的二元关系如下： R=a,b|(ab)/2是整数 试证明R在A上是自反的和对称的。 证明：aA，(a-a)/2=0，0是整数，所

34、以 a,aR。即R是自反的。 aA，bA，a,bR，(a-b)/2是整数，因为整数的相反数也是整数，所以(b-a)/2=-(a-b)/2是整数，b,aR。即R是对称的。,第三章：集合与关系,【定义】设RXX， (x)(y)(xXyXx,yRy,xR(x=y) 则称R在X上是反对称的。 x,yRy,xR(x=y) (x=y)(x,yRy,xR) (x=y)(x,yRy,xR) (x=y)x,yR)y,xR (xy)x,yR)y,xR (xy)x,yRy,xR x,yR(xy)y,xR 由此，反对称的定义又可以等价的描述为： (x)(y)(xXyXx,yR(xy)y,xR),第三章：集合与关系,设

35、R是X上的反对称关系，由【定义】知，在R的关系矩阵MR中以主对角线为轴的对称位置上不能同时为1(主对角线除外)。在R的关系图中每两个不同的结点间不能有方向相反的两条边。 设X=1,2,3，X上的二元关系R=1,2,2,3,3,3，R是反对称的。它的关系图如图3.13所示，关系矩阵如下： MR=,第三章：集合与关系,【例】 设A=1,2,3，定义A上的二元关系如下： R=1,1,2,2 S=1,1,1,2,2,1 T=1,2,1,3 U=1,3,1,2,2,1 试说明R，S，T，U是否是A上的对称关系和反对称关系。 解：R是A上的对称关系，也是A上的反对称关系。 S是A上的对称关系。因为1,2和

36、2,1都是S元素，而12，所以S不是A上的反对称关系。 因为1,2T，而2,1T，所以T不是A上的对称关系。T是A上的反对称关系。 U不是A上的对称关系，也不是A上的反对称关系。,第三章：集合与关系,【 定义】设RXX， (x)(y)(z)(xXyXzXx,yRy,z R x,zR) 则称R在X上是传递的。,【例】设R是实数集合， S=x,y|xRyRx=y是实数集合上的等于关系。证明实数集合上的等于关系是传递的。 证明：xR，yR，zR，x,yS且y,zS，由S的定义有x=y和y=z，由实数相等的概念得x=z。再根据S的定义，x,zS。故实数集合上的等于关系S是传递的。,第三章：集合与关系,

37、3.6复合关系和逆关系 1、复合关系 【定义】设X，Y，Z是集合，RXY，SYZ，集合 x,zxXzZ(y)(yYx,yRy,zS) 叫做R和S的复合关系。记为RS，RSXZ，即RS是X到Z的二元关系。,【例3.6.1】X=1,2,3,4,5，X上的二元关系R和S定义如下： R=1,2,3,4,2,2 S=4,2,2,5,3,1,1,3 试求RS，SR，R(SR)，(RS)R，RR，SS，RRR,第三章：集合与关系,解：RS=1,5,3,2,2,5 SR=4,2,3,2,1,4 (RS)R=3,2 R(SR)=3,2 RR=1,2,2,2 SS=4,5,3,3,1,1 RRR =1,2,2,2

38、 从该例可以看出，RSSR，这说明，二元关系的复合运算不满足交换律。,第三章：集合与关系,【定理】设X，Y，Z，W是集合，RXY，SYZ，T ZW，则 (RS)T= R(ST) 证明：x,w(RS)T(z)(x,zRSz,wT) (z)(y)(x,yRy,zS)z,wT) (z)(y)(x,yRy,zS)z,wT) (y)(z)(x,yR(y,zSz,wT) (y)(x,yR(z)(y,zSz,wT) (y)(x,yRy,wST)x,wR(ST) 所以 (RS)T=R(ST),第三章：集合与关系,【定理】 设R是A上的二元关系，RIA=IAR=R 证明：先证RIA=R x,yRIA(z)(x,

39、zRz,yIA) (z)(x,zRz=y)x,yR 所以 RIAR x,yRx,yRy,yIAx,yRIA 所以 RRIA 故 RIA=R 类似的，可以证明IAR= R,第三章：集合与关系,【定理】设R，S，T是A上的二元关系, 则 R(ST)=RSRT (RS)T=RTST R(ST)RSRT (RS)TRTST 证明：仅证明，类似地可证明、和。 x,yR(ST)(z)(x,zRz,yST) (z)(x,zR(z,ySz,yT) (z)(x,zRz,yS)(x,zRz,yT) (z)(x,zRz,yS)(z)(x,zRz,yT) x,yRSx,yRT x,yRSRT 故 R(ST)RSRT,

40、第三章：集合与关系,一般地说，RSRTR(ST)，举反例如下： 设A=1,2,3,4,5 R=4,1,4,2AA S=1,5,3,5AA T=2,5,3,5AA RSRT =4,54,5 =4,5 R(ST) =4,1,4,23,5= RSRTR(ST) 【定理】说明，关系的复合运算“”对并运算“”满足左分配律。说明，关系的复合运算“”对并运算“”满足右分配律。所以，复合运算“”对并运算“”满足分配律。由和知，复合运算“”对交运算“”不满足分配律。,【定义】设R是A上的二元关系，n为自然数，R的n次幂记为Rn，定义为： R0=IA Rn+1= RnR 由该定义可以看出，A上的任何二元关系的0次

41、幂都相等，等于A上的恒等关系IA。由该定义还可以看出： R1= R0 R=IAR=R R2= R1R= RR R3= R2R=(RR)R 因为复合运算满足结合律，所以R3又可以写成： R3= RRR 同样的道理Rn也可以写成： Rn=,第三章：集合与关系,例如,在【例3.6.1】中 R2=RR=1,2,2,2 S2 =SS=4,5,3,3,1,1 R3=RRR=1,2,2,2 【定理】设A是具有n个元素的有限集，R是A上的二元关系，则必存在自然数s和t，使得Rs=Rt，0st2 。 证明：R是A上的二元关系，对任何自然数k，由复合关系的定义知，Rk仍然是A上的二元关系，即RkAA。另一方面，

42、A上的二元关系仅有2 种。列出R的各次幂R0，R1，R2 ， ，共有2 1个，必存在自然数s和t，使得Rs=Rt，0st2 。,第三章：集合与关系,【例】A= 1,2,3,4，A上的二元关系R定义如下： R=1,2,2,1,2,3,3,4 求二元关系R的各次幂，验证定理4.2.5。 解：|A|=4 R0=IA=1,1,2,2,3,3,4,4 R1=R=1,2,2,1,2,3,3,4 R2=R1 R= RR=1,1,1,3,2,2,2,4 R3= R2R =1,2,2,1,2,3,1,4 R4=R3 R=1,1,1,3,2,2,2,4=R2， 024216=2 R5=R4R=R2R=R3 R6=

43、R5R=R3R=R4= R2 R2n=R2 R2n+1=R3, n =1,2,3,第三章：集合与关系,【定理】设R是A上的二元关系，m，n为自然数，则 RmRn =Rm+n (Rm)n=Rmn 证明：对任意给定的mN，关于n进行归纳证明： 当n=0时，Rm R0=Rm IA=Rm=Rm+0 设n=k时，RmRk=Rm+k。下证n=k+1时，结果也对。 RmRk+1=Rm(RkR)=(RmRk)R=Rm+kR= Rm+k+1 对任意给定的mN，关于n进行归纳证明： 当n=0时，(Rm)0=IA=R0=Rm0 设n=k时，(Rm)k=Rmk。下证n=k+1时，结果也对。 (Rm)k+1=(Rm)k

44、 Rm=RmkRm=Rmk+m=Rm(k+1) 设X，Y，Z是集合，RXY，SYZ，RS是R和S的复合关系，RSXZ，它们的关系矩阵分别是MR、MS和MRS。以下研究这三个矩阵之间的关系。,第三章：集合与关系,设X=x1,x2, ,xm，Y=y1,y2, ,yn， Z=z1,z2, ,zP RXY， SYZ， RS XZ MR= mn i=1, ,m，j=1, ,n MS= np i=1,n，j =1, p MRS= mp i=1,m，j =1, p,第三章：集合与关系,与 ， 有如下的关系： = i=1,m，j=1,p 将上述关系用矩阵符号记为： MR S=MR MS， 其中，i=1,m，j

45、 =1,p 矩阵运算“”叫做关系矩阵MR和MS的布尔乘法。 把关系矩阵的布尔乘法公式 = i=1,m，j =1,p 与线性代数中的矩阵乘法公式相比，发现，只要把矩阵乘法公式中的数乘改为合取，把数加改为析取，就得到了关系矩阵的布尔乘法公式。,第三章：集合与关系,【例】A=1,2,3,4,5，A上的二元关系R和S定义如下： R=1,2,2,2,3,4 S=1,3,2,5,3,1,4,2 试求MR S和MR MS，它们是否相等 ? 解：按照R 和S的定义，求出 RS=1,5,3,2,2,5 写出R 、S和R S关系矩阵如下： MR= MS= MR S=,第三章：集合与关系,MR MS= = 所以MR

46、 S=MR MS 2、逆关系 【定义】 设X，Y是集合，RXY，集合 y,xx,yR 叫做R的逆关系。记为RC，RCYX，RC是Y到X的二元关系。 容易证明，RC的关系矩阵 是R的关系矩阵MR的转置矩阵，即 =MRT 可以验证，将R关系图中的弧线的箭头反置，就可以得到RC关系图。,第三章：集合与关系,【例】设X=1,2,3,4，Y=a,b,c，X到Y二元关系 R=1,a,2,b,4,c， 试求RC，写出MR和 ，验证 =MRT 画出R和RC的关系图，验证将R关系图中的弧线的箭头反置可得到RC关系图。 解：RC=a,1,b,2,c,4 R和RC的关系矩阵是： MR= = 显然， =MRT,第三章

47、：集合与关系,R和RC的关系图分别是图3.14和图3.15，它们中的弧线的方向是相反的。,第三章：集合与关系,【定理】设X，Y是集合，R，S是X到Y的二元关系，则 (RS)C = RCSC (RS)C =RCSC (AB)C=BA (R) C = (R C) (R-S)C =RC-SC 证明： x,y(RS)Cy,xRSy,xRy,xS x,yRCx,ySCx,yRCSC 所以 (RS)C =RCSC 类似可证明和。 x,y(R)Cy,xRy,xRy,xR x,yRCx,yRC x,y (RC) 所以 (R) C =(R C),第三章：集合与关系,利用、和证明： (R-S)C=(RS)C=RC

48、(S)C=RC(SC)=RC-SC 【定理】设X，Y，Z是集合，RXY，SYZ，则 (RS)C=SCRC 证明： z,x(RS)Cx,z(RS) (y)(x,yRy,zS) (y)(y,xRCz,ySC) (y)(z,ySCy,xRC) z,xSCRC 所以 (RS)C=SCRC,第三章：集合与关系,第三章：集合与关系,【定理】设R是X上的二元关系, R是对称的当且仅当R=RC。 证明：设R是对称的，下证R =RC。 x,yRy,xRx,yRC , 所以 R =RC。 设R =RC，下证R是对称的。 x,yRy,xRCy,xR, 所以R是对称的。,【定理】设R是X上的二元关系，则R是反对称的当

49、且仅当RRCIX。 证明：设R是反对称的，下证RRCIX。 x,yRRCx,yRx,yRC x,yRy,xR 因为R是反对称的，所以y=x，x,y=x,x=y,yIX，故RRCIX,第三章：集合与关系,设RRCIX，下证R是反对称的。 x,yRy,xRx,yRx,yRC x,yRRC 因为RRCIX，所以x,yIX，故x=y，R是反对称的。,【定理】设R是X上的二元关系，R是传递的当且仅当RR R。 证明：设R是传递的，下证RRR。 x,yRR，zX, 使得x,zR且z,yR，又因为R是传递的，所以x,yR，这就证明了RR R。 设RR R，下证R是传递的。 x,yR且y,zR，由复合关系的定

50、义得x,z RR ，因为RRR，所以x,zR，所以R是传递的。,第三章：集合与关系,【例】设R，S是X上的二元关系，证明 若R，S是自反的，则RS和RS也是自反的。 若R，S是对称的，则RS和RS也是对称的。 若R，S是传递的，则RS也是传递的。 证明：设R，S是自反的，则有，IXR，IXS，所以IXRS，IXRS，则有，RS和RS也是自反的。,设R，S是对称的，则有，R=RC，S=SC，则有，RS=RCSC=(RS)C，RS=RCS C=(RS) C， 则有，RS和RS也是对称的。 设R，S是传递的，则有，RRR，SSS，则有， (RS)(RS)(RR)(RS)(SR)(SS) (RR)(S

51、S)RS 即(RS)(RS)RS，则有，RS是传递的。,3.7关系的闭包运算 【定义】设R XX，X上的二元关系R 满足： R是自反的(对称的，传递的)。 RR 。 对X上的任意二元关系R，如果RR且R是自反的 (对称的，传递的)，就有R R 。 则称R 是R的自反(对称，传递)闭包。记为r(R)(s(R), t(R) 【定义】的和的意思是自反(对称，传递)闭包R 是包含R的自反(对称，传递)关系；【定义】的的意思是在所有包含R的自反(对称，传递)关系中自反(对称，传递)闭包R是最小的。所以，【定义】又可以描述为：包含R的最小自反(对称，传递)关系是R的自反(对称，传递)闭包。 传递闭包t(R

52、)有时也记为R+，读作“R加”。传递闭包在语法分析中有很多重要的应用。,第三章：集合与关系,当二元关系R是自反(对称，传递)的时，求R的自反(对称，传递)闭包方法由下面的定理给出了。 【定理】设RXX，则 R是自反的当且仅当r(R)=R。 R是对称的当且仅当s(R)=R。 R是传递的当且仅当t(R)=R。 证明：仅证明，其余留做练习。 设R是自反的，下证r(R)=R 令R =R R =R，R是自反的，所以R是自反的。 因为R=R，所以RR 。 R 是X上的任意自反关系且RR，因为R=R，所以RR。 故R是R的自反闭包。即r(R)=R。,第三章：集合与关系,设r(R)=R，下证R是自反的。 由自

53、反闭包的定义知，R是自反的。 以下的几个定理给出了求二元关系R的自反闭包、对称闭包和传递闭包的一般方法。 【 定理】 设RXX，则 r(R)=RIX 证明：令R=RIX IXRIX，而RIX =R，所以IXR，R是自反的。 RRIX，而RIX =R ，所以R R R是X上的任意自反关系且RR，由于R是自反的，所以IX R，从而有R=RIXR。 根据自反闭包的定义，R=RIX是R的自反闭包，即r(R)=RIX。,第三章：集合与关系,【定理】设RXX，则s(R)=RRC 证明：令R=RRC (R)C= (RRC) C= RC(RC)C= RCR=RRC=R，所以R是对称的。 RRRC，而RRC =

54、R，所以RR。 R是X上的任意对称关系且RR ， x,yRCy,xRy,xR x,yR(R是对称的)， 所以RCR ，从而有R=RRCR 。R是R的对称闭包，即s(R)= RRC。 【定理】设RXX，则 t(R)=RR2R3 证明：先证RR2R3t(R) 用数学归纳法证明：iI+ Rit(R),第三章：集合与关系, 当i =1时，由传递闭包的定义，R1= Rt(R)。 设i =n时，Rnt(R)。下证 Rn+1t(R)。 x,yRn+1(c)(x,cRnc,yR) (c)(x,ct(R)c,yt(R) (和归纳假设) x,yt(R) (t(R)是传递的) 即 Rn+1 t (R) 故RR2R3

55、 t (R) 再证t(R)RR2R3 显然 RRR2R3 以下证明RR2R3是传递的。 x,yRR2R3且y,zRR2R3 tI+使x,yRtsI+ 使y,zRs x,zRtRs=Rt+sRR2R3 x,zRR2R3 根据传递关系的定义，RR2R3是传递的。,第三章：集合与关系,综上所述，RR2R3是包含R的传递关系。而R的传递闭包是包含R的最小传递关系。所以t(R)RR2R3 t(R)=RR2R3 【例】设A=1,2,3，定义A上的二元关系R为： R=1,2,2,3,3,1 试求：r(R)，s(R)，t(R) 解：r(R)= RIA=1,2,2,3,3,1,1,1,2,2,3,3 s(R)=RRC=1,2,2,3,3,1,2,1,3,2,1,3 以下求t(R)： R2= RR=1,3,2,1,3,2 R3= R2R =1,1,2,2,3,3=IA R4= R3R = IAR=R 继续这个运算，则有,第三章