离散数学-第七章的课件

1、1,主要内容 有序对与笛卡儿积 二元关系的定义与表示法 关系的运算 关系的性质 关系的闭包 等价关系与划分 偏序关系,第七章 二元关系,2,7.1 有序对与笛卡儿积,定义7.1 由两个元素 x 和 y(允许x = y)，按照一定的顺序组成的二元组称为有序对或序偶，记作. 其中，x是它的第一个元素，y是它的第二个元素。 有序对的性质: (1) 有序性 （当xy时） (2) 与相等的充分必要条件是 = x=uy=v. 注意：区别二元集x,y与有序对 例7.1 已知=，求x和y。 解 由有序对相等的充要条件有x+2=52x+y=4解得x=3,y=-2。,3,笛卡儿积,定义7.2 设A,B为集合，用A

2、中元素为第一元素，B中元素为 第二元素构成有序对.所有这样的有序对组成的集合叫做 A与B的笛卡儿积,记作AB. 笛卡儿积的符号化表示为: AB = | xAyB.,例 （1） A=1,2,3, B=a,b,c AB =, BA =, （2）A=, B= P(A)A =, = , P(A)B = ,若 |A| = m, |B| = n, 则 |AB| = mn,4,笛卡儿积的性质,(1) 若 A 或 B 中有一个为空集，则 AB 就是空集. A = B = (2) 不适合交换律 AB BA (当AB A B时) (3) 不适合结合律 (AB)C A(BC) (当A B C时) (4) 对于并或交

3、运算满足分配律 A(BC) = (AB)(AC) (BC)A = (BA)(CA) A(BC) = (AB)(AC) (BC)A = (BA)(CA) (5) A CB D AB CD,5,实例,例7.2 设A=1,2,求P(A)A。 解 P(A)A =,1,2,1,21,2 =, 例7.3 设A，B，C，D为任意集合，判断以下命题是否为真，并说明理由。 (1) AB=AC B=C (2) A(BC)=(AB)(AC) (3) A=BC=D AC=BD (4) 存在集合A，使得A AA 解： (1) 不一定为真。当A= ，B=1,C=2时，有AB=AC=，但BC。 (2) 不一定为真。当A=B

4、=1,C=2时有 A(BC)=1=1 (AB)(AC)= 1= (3) 为真。由等量代入的原理可证。 (4) 为真。当A= 时有A AA成立。,6,7.1 有序对与笛卡尔积,定义7.1 由两个元素 x 和 y(允许x = y)，按照一定的顺序组成 的二元组称为有序对或序偶，记作. 其中，x是它的第一个元素，y是它的第二个元素。 定义7.2 设A,B为集合，用A中元素为第一元素，B中元素为 第二元素构成有序对.所有这样的有序对组成的集合叫做 A与B的笛卡儿积,记作AB.,若 |A| = m, |B| = n, 则 |AB| = mn,7,7.2 二元关系,定义7.3 如果一个集合满足以下条件之一

5、： (1) 集合非空, 且它的元素都是有序对 (2) 集合是空集 则称该集合为一个二元关系, 简称为关系，记作R. 如果R, 可记作xRy；如果R, 则记作x y 实例：R=, S=,a,b. R是二元关系, 当a, b不是有序对时，S不是二元关系，只是一个集合。 根据上面的记法，可以写1R2, aRb, a c等.,8,A到B的关系与A上的关系,定义7.4 设A,B为集合, AB的任何子集所定义的二元关系叫做从A 到B的二元关系, 当A=B时则叫做A上的二元关系.,例 A=0,1, B=1,2,3, 那么 R1=, R2=AB, R3=, R4= R1, R2, R3, R4是从 A 到 B

6、 的二元关系, R3 和 R4 也是A上的二元关系. 计数: |A|=n, |AA|=n2, AA的子集有2n2个. 所以 A上有2n2 个不同的二元关系. 例如 |A| = 3, 则 A上有232 =512个不同的二元关系.,9,A上重要关系的实例,定义7.5 设 A 为任意集合, (1) 空集是任何集合的子集，是A上的关系，称为空关系 (2) 全域关系 EA = | xAyA = AA 恒等关系 IA = | xA 小于等于关系 LA = | xAyAxy, A为实数集R的子集 整除关系 DB = | xByBx整除y, B为非零整数集Z*的子集 包含关系 R = | xAyAxy, A是

7、由一些集合构成的集合族. 类似地还可以定义： 大于等于关系、小于关系、大于关系、真包含关系等。,10,实例,例如, A=1, 2, 则 EA = , IA = , 例如 A = 1, 2, 3, B=a, b, 则 LA = , DA = , 例如 A = P(B) = ,a,b,a,b, 则 A上的包含关系是 R = , ,11,实例,例7.4 设A=1,2,3,4，下面各式定义的R都是A上的关系，试用列元素法表示R。(1) R=|x是y的倍数(2) R=|(x-y)2A(3) R=|x/y是素数(4) R=|xy,解： (1)R=, (2) R=, (3) R=, (4) R=EA-IA=

8、 , ,12,关系的表示,关系的表示方法有三种:集合表达式、关系矩阵和关系图。例7.4中的关系就是用集合表达式来给出的。 1. 关系矩阵 若A=x1, x2, , xm，B=y1, y2, , yn，R是从A到B的关系，R的关系矩阵是布尔矩阵MR = rij mn, 其中 rij = 1 R 。 2. 关系图 若A= x1, x2, , xm，R是A上的关系，R的关系图是GR=, 其中A为顶点集，R为边集. 如果属于关系R，在关系图中就需要增加一条从 xi 到 xj 的有向边。 注意： 关系矩阵适合表示从A到B的关系或A上的关系（A,B为有穷集） 关系图适合表示有穷集A上的关系,13,实例,例

9、 A=1,2,3,4, R=, R的关系矩阵MR和关系图GR如下：,14,题目 A=a, b, c, d, R=, R的关系矩阵 MR 和关系图 GR 如下：,15,7.3 关系的运算,关系的基本运算（7种） 定义7.6 设R是二元关系。 （1）R中所有的有序对的第一元素构成的集合称为R的定义域，记作domR，形式化表示为 domR = x | y (R) （2）R中所有的有序对的第二元素构成的集合称为R的值域，记作ranR，形式化表示为 ranR = y | x (R) （3）R的定义域和值域的并集称为R的域，记作fldR，形式化表示为 fldR = domR ranR,例7.5 R=, 求

10、domR，ranR和fldR。 解： domR=1, 2, 4 ranR=2, 3, 4 fldR=1, 2, 3, 4,16,关系运算(逆与合成),定义7.7 关系的逆运算 设R为二元关系，R的逆关系，简称R的逆，记作R-1 ，其中 R1 = | R 定义7.8 关系的合成运算 设F,G为二元关系，G对F的右复合记作FG, 其中 FG = | t (F G) ,例7.6 F = , , G= 求： F1 、FG 、GF 解： F1 = , FG = GF = 类似地也可以定义关系的左复合FG ，即 FG = | t (G F) ,右复合F G 表示在右边的G是复合到F上的第二步作用,左复合F

11、 G 表示在左边的F是复合到G上的第二步作用,右复合与左复合这两种规定都合理，本书采用右复合的定义，其它书本可能采用左复合的定义，请注意两者的区别。,17,实例,练习： R = , , , S = , , , , 求： R1 、RS 、 SR 解： R1 = , , , RS = , , SR = , , , ,关系是集合，所以关于集合的运算均适用于关系运算， 优先级是：逆运算关系运算集合运算,18,关系运算(限制与像),定义7.9 设R为二元关系, A是集合 (1) R在A上的限制记作 RA, 其中 RA = | xRyxA (2) A在R下的像记作RA, 其中 RA=ran(RA) 说明：

12、 R在A上的限制 RA是 R 的子关系，即 RA R A在R下的像 RA 是 ranR 的子集，即 RA ranR,19,关系运算(限制与像),例7.7 设R=, 求R1， R， R2,3， R1， R， R3。 解： R1 = , R = R2,3 = , R1 = 2,3 R = R3 = R3 = 2,定义7.9 设R为二元关系, A是集合 (1) R在A上的限制记作 RA, 其中 RA = | xRyxA (2) A在R下的像记作RA, 其中 RA=ran(RA),20,关系运算的性质,定理7.1 设F是任意的关系, 则 (1) (F1)1=F (2) domF1= ranF, ran

13、F1= domF,定理7.2 设F, G, H是任意的关系, 则 (1) (FG)H = F(GH) (2) (FG)1 = G1F1,定理7.3 设R为A上的关系, 则 RIA= IAR=R,21,关系运算的性质,定理7.4 设F，G，H为任意关系，则 (1) F(GH) = FGFH (2) (GH)F = GFHF (3) F(GH) FGFH (4) (GH)F GFHF,定理7.4 的结论可以推广到有限多个关系 R(R1R2Rn) = RR1RR2RRn (R1R2Rn)R = R1RR2RRnR R(R1R2 Rn) RR1RR2 RRn (R1R2 Rn)R R1RR2R RnR

14、,22,关系运算的性质,定理7.5 设F 为关系, A, B为集合, 则 (1) F (AB) = F AF B (2) F AB = F AF B (3) F (AB) = F AF B (4) F AB F AF B,23,关系的幂运算,定义7.10 设 R 为 A 上的关系, n为自然数, 则 R 的 n 次幂定义为： (1) R0 = | xA = IA (2) Rn+1 = RnR 注意： 对于A上的任何关系 R1 和 R2 ，都有 R10 = R20 = IA 对于A上的任何关系 R 都有 R1 = R 给定A上的关系R和自然数n，怎样计算Rn呢？ 如果n是0或1，结果是很简单的。

15、下面考虑n2的情况： 如果R用集合表达式给出，可以通过n-1次右复合计算得到Rn 如果R用关系矩阵M给出，则Rn的关系矩阵是Mn，即n个矩阵M之积。与普通矩阵乘法不同的是，其中的相加是逻辑加，即 1+1=1，1+0=1，0+1=1，0+0=0,24,关系的幂运算,如果R用关系图G给出，可以直接由关系图G得到Rn的关系图G （G 的顶点集与G相同）。考察G的每个顶点xi，如果在G中从xi出发经过n步长的路径到达顶点xj，则在G中加一条从xi到xj的边。当把所有这样的边都找到以后，就得到Rn的关系图G。,25,例 7.8 设A = a,b,c,d, R = , 求R的各次幂, 分别用关系矩阵和关系

16、图表示.,解 R 与 R2的关系矩阵分别是：,幂的求法,26,R3和R4的矩阵分别是： 因此M4=M2, 即R4=R2. 由此可以得到 R2=R4=R6=， R3=R5=R7= 而R0，即IA的关系矩阵是 至此，R各次幂的关系矩阵都得到了。,幂的求法,27,关系图,用关系图的方法得到R0, R1, R2, R3,的关系图如下图所示：,R0,R1,R2=R4=,R3=R5=,例 7.8 设A = a,b,c,d, R = , 求R的各次幂, 分别用矩阵和关系图表示.,28,幂运算的性质,定理7.6 设 A 为 n 元集, R 是A上的关系, 则存在自然数 s 和 t, 使得 Rs = Rt.,该

17、定理说明有穷集上只有有穷多个不同的二元关系。 当t足够大时Rt必与某个Rs(st)相等。如例 7.8中的R4=R2。,29,定理7.7 设 R 是 A上的关系, m, nN, 则 (1) RmRn = Rm+n (2) (Rm)n = Rmn,幂运算的性质,定理7.8 设R 是A上的关系, 若存在自然数 s, t (st) 使得 Rs=Rt, 则 (1) 对任何 kN有 Rs+k = Rt+k (2) 对任何 k, iN有 Rs+kp+i = Rs+i, 其中 p = ts (3) 令S = R0,R1,Rt1, 则对于任意的 qN 有RqS,通过上面的定理可以看出，有穷集A上的关系R的幂序列

18、R0，R1，R2 ，是一个周期性变化的序列。利用它的周期性可以将R的高次幂化简为R的低次幂。,30,例7.9 设A=a,b,d,e,f，R=,。求出最小的自然数m和n，使得mn且Rm=Rn。解 由R的定义可以看出A中的元素可分成两组，即a,b和d,e,f。它们在R的右复合运算下有下述变化规律： abab defdef对于a或b,每个元素的变化周期是2。对于d，e，f，每个元素的变化周期是3。因此必有Rm=Rm+6，其中6是2和3的最小公倍数。取m=0,n=6即满足题目要求。,31,7.4 关系的性质,定义7.11 设 R 为A上的关系, (1) 若 x(xAR), 则称 R 在 A 上是自反的

19、. (2) 若 x(xAR), 则称 R 在 A 上是反自反的.,实例： 自反：全域关系EA, 恒等关系IA, 小于等于关系LA, 整除关系DA 反自反：实数集上的小于关系、幂集上的真包含关系. A=1,2,3, R1, R2, R3是A上的关系, 其中 R1, R2, R3,R2 自反 ，R3 反自反， R1既不是自反的也不是反自反的.,关系的性质主要有以下五种： 自反性，反自反性，对称性，反对称性和传递性。,32,对称性与反对称性,定义7.12 设 R 为 A上的关系, (1) 若xy( x,yARR), 则称 R 为 A上对 称的关系. (2) 若xy( x,yARRx=y), 则称 R

20、 为 A上的反对称关系.,实例： 对称关系：A上的全域关系EA, 恒等关系IA和空关系 反对称关系：恒等关系IA和空关系也是A上的反对称关系. 设A1,2,3, R1, R2, R3和R4都是A上的关系, 其中 R1,，R2, R3,，R4, R1：对称和反对称； R2：只有对称；R3：只有反对称； R4：不对称、不反对称,33,传递性,定义7.13 设R为A上的关系, 若 xyz(x,y,zARRR), 则称 R 是A上的传递关系.,实例： A上的全域关系 EA,恒等关系 IA和空关系 ，小于等 于和小于关系，整除关系，包含与真包含关系 设 A1,2,3, R1, R2, R3是A上的关系,

21、 其中 R1, R2, R3 R1和R3是A上的传递关系, R2不是A上的传递关系.,34,关系性质成立的充要条件,定理7.9 设R为A上的关系, 则 (1) R 在A上自反当且仅当 IA R (2) R 在A上反自反当且仅当 RIA = (3) R 在A上对称当且仅当 R=R1 (4) R 在A上反对称当且仅当 RR1 IA (5) R 在A上传递当且仅当 RR R,关系的性质不仅反映在它的集合表达式上，也明显地反映在它的关系矩阵和关系图上。以下将列出五种性质在关系矩阵和关系图中的特点。要求熟记、理解及掌握好表7.1的内容。,35,关系性质的三种等价条件,表示,性质,元素以主对角线为对称轴对

22、应相等的矩阵称为对称矩阵。,36,实例,例7.14 判断图7.3中关系的性质，并说明理由。,解： （1） 该关系是对称的，因为无单向边。它不是自反的也不是反自反的。因为有的顶点有环，有的顶点无环。它不是反对称的，因为图中有双向边。它也不是传递的，因为图中有边和，但没有从3到3的边，即通过3的环。,37,实例,例7.14 判断图7.3中关系的性质，并说明理由。,（2） 该关系是反自反的但不是自反的，因为每个顶点都没有环。它是反对称的但不是对称的，因为图中只有单向边。它也是传递的，因为不存在顶点x,y,z，使得x到y有边，y到z有边，但x到z没有边，其中x,y,z1,2,3。,38,实例,例7.1

23、4 判断图7.3中关系的性质，并说明理由。,（3） 该关系是自反的但不是反自反的，因为每个顶点都有环。它是反对称的但不是对称的，因为图中只有单向边。但它不是传递的，因为2到1有边，1到3有边，但2到3没有边。,39,关系的性质和运算之间的联系,其中的和分别表示“能保持”和“不一定能保持”的含义。,原有性质,运 算,40,7.5 关系的闭包,主要内容 闭包定义 闭包的构造方法 集合表示 矩阵表示 图表示 闭包的性质,41,闭包定义,定义7.14 设R是非空集合A上的关系, R的自反(对称或传递)闭 包是A上的关系R, 使得R满足以下条件： (1) R是自反的(对称的或传递的) (2) RR (3

24、) 对A上任何包含R的自反(对称或传递)关系R 有RR R的自反闭包记作r(R), 对称闭包记作s(R), 传递闭包记作t(R).,定理7.10 设R为A上的关系, 则有 (1) r(R)=RR0 (2) s(R)=RR1 (3) t(R)=RR2R3 说明：对有穷集A(|A|=n)上的关系, (3)中的并最多不超过Rn,推论 设R为有穷集A上的关系，则存在正整数r使得t(R)=RR2Rr,42,闭包的矩阵表示和图表示,设关系R, r(R), s(R), t(R)的关系矩阵分别为M, Mr , Ms 和 Mt 则 Mr=M+E， Ms=M+M ， Mt=M+M2+M3+ E 是和M同阶的单位矩

25、阵, M 是转置矩阵，相加时使用逻辑加.,设关系R, r(R), s(R), t(R)的关系图分别记为G, Gr, Gs, Gt, 则Gr , Gs , Gt 的顶点集与G 的顶点集相等. 除了G 的边以外, 按下述 方法添加新的边： (1) 考察G 的每个顶点, 若没环就加一个环，得到Gr (2) 考察G 的每条边, 若有一条 xi 到 xj 的单向边, ij, 则在G 中加一条 xj 到 xi 的反向边, 得到Gs (3) 考察G 的每个顶点 xi, 找出xi 出发的所有2步，3步，n步长的路径（n为G中的顶点数）。设路径的终点为 xj1 , xj2 , , xjk 。如果没有从 xi 到

26、 xjl（l=1，2， ，k） 的边, 就加上这条边。当检查完所有的顶点后就得到图Gt,43,实例,例7.15 设A=a,b,c,d, R=, R和r(R), s(R), t(R)的关系图如下图所示.,重点：一定要基于原图画各个闭包图,44,闭包的性质,定理7.11 设R是非空集合A上的关系, 则 (1) R是自反的当且仅当 r(R)=R. (2) R是对称的当且仅当 s(R)=R. (3) R是传递的当且仅当 t(R)=R.,定理7.12 设R1和R2是非空集合A上的关系, 且 R1R2, 则 (1) r(R1) r(R2) (2) s(R1) s(R2) (3) t(R1) t(R2),4

27、5,定理7.13 设R是非空集合A上的关系, (1) 若R是自反的, 则 s(R) 与 t(R) 也是自反的 (2) 若R是对称的, 则 r(R) 与 t(R) 也是对称的 (3) 若R是传递的, 则 r(R) 是传递的. 定理7.13讨论了关系性质和闭包运算之间的联系。如果关系R是自反或对称的，那么经过求闭包运算以后所得到的关系仍然是自反或对称的。但是对于传递闭包的关系则不然。它的自反闭包仍旧保持传递性，而对称闭包就可能失去传递性。 如果计算关系R的自反、对称、传递闭包，为了不失去传递性，传递闭包运算应该放在对称闭包运算的后面。若令tsr(R)表示R的自反、对称、传递闭包，则tsr(R) =

28、 t(s(r(R),闭包的性质,46,7.6 等价关系与划分,主要内容 等价关系的定义与实例 等价类及其性质 商集与集合的划分 等价关系与划分的一一对应,47,等价关系的定义与实例,定义7.15 设R为非空集合A上的关系. 如果R是自反的、对称的和 传递的, 则称R为A上的等价关系. 设 R 是一个等价关系, 若 R, 称 x等价于y, 记做xy.,实例 设 A=1,2,8, 如下定义A上的关系R： R=| x,yAx y(mod 3) 其中x y(mod 3)叫做 x与 y 模3相等, 即x除以3的余数与y除以 3的余数相等. 不难验证 R 为A上的等价关系, 因为 (1) xA, 有 x

29、x (mod 3) (2) x,yA, 若x y(mod 3), 则有y x(mod 3) (3) x,y,zA, 若x y(mod 3), y z(mod 3), 则有x z(mod 3),R具有自反性,R具有对称性,R具有传递性,48,模 3 等价关系的关系图,等价关系的实例,实例 设 A=1,2,8, 如下定义A上的关系R： R=| x,yAx y(mod 3),上述关系图被分成三个互不连通的部分。每部分中的数两两都有关系，不同部分中的数则没有关系。每一部分中的所有的顶点构成一个等价类。,49,等价类定义,定义7.16 设R为非空集合A上的等价关系, xA，令 xR = y | yAxR

30、y 称xR 为x关于R的等价类, 简称为x的等价类, 简记为x或 从以上定义知道，x的等价类是A中所有与x等价的元素构成的集合。 实例 A=1, 2, , 8上模3等价关系的等价类： 1 = 4 = 7 = 1, 4, 7 2 = 5 = 8 = 2, 5, 8 3 = 6 = 3, 6,50,等价类的性质,定理7.14 设R是非空集合A上的等价关系, 则 (1) xA, x是A的非空子集 (2) x,yA, 如果 xRy, 则 x = y (3) x,yA, 如果 x y, 则 x与y不交 (4) x | xA=A,51,商集与划分,定义7.17 设 R 为非空集合A上的等价关系, 以 R

31、的所有等价 类作为元素的集合称为A关于R的商集, 记做A/R, A/R = xR | xA 实例 设 A=1,2,8，A关于模3等价关系R的商集为 A/R = 1,4,7, 2,5,8, 3,6 A关于恒等关系和全域关系的商集为： A/IA = 1, 2, , 8， A/EA = 1,2,8,定义7.18 设A为非空集合, 若A的子集族( P(A)，是A的 子集构成的集合)满足: (1) (2) xy(x,yxyxy=) (3) = A 则称是A的一个划分, 称中的元素为A的划分块.,等价类的性质 定理7.14 设R是非空集合A上的等价关系, 则 (1) xA, x是A的非空子集 (2) x,

32、yA, 如果 xRy, 则 x = y (3) x,yA, 如果 x y, 则 x与y不交 (4) x | xA=A,52,划分实例,例7.17 设 A a, b, c, d , 给定 1, 2, 3, 4, 5, 6如下： 1= a, b, c , d 2= a, b, c , d 3= a , a, b, c, d 4= a, b, c 5=, a, b , c, d 6= a, a , b, c, d 则 1和 2是A的划分, 其它都不是A的划分.,(1) (2) xy(x,yxyxy=) (3) = A,53,等价关系与划分的一一对应,把商集A/R和划分的定义相比较，易见商集就是A的一

33、个划分，并且不同的商集将对应于不同的划分。反之，任给A的一个划分，如下定义A上的关系R：R=|x,yAx与y在的同一划分块中则不难证明R为A上的等价关系，且该等价关系所确定的商集就是。由此可见，A上的等价关系与A的划分是一一对应的。,54,例7.18 给出 A1,2,3上所有的等价关系,实例,1对应 EA, 5 对应 IA, 2, 3 和 4分别对应 R2, R3和 R4. R2=,IA R3=,IA R4=,IA,解 先做出A的划分, 从左到右分别记作 1, 2, 3, 4, 5.,55,7.7 偏序关系,主要内容 偏序关系 偏序关系的定义 偏序关系的实例 偏序集与哈斯图,56,定义与实例,

34、定义7.19 偏序关系：非空集合A上的自反、反对称和传递的关系， 记作. 设为偏序关系, 如果 , 则记作 x y, 读作 x“小于或等于”y. 注意:这里的“小于或等于”不是指数的大小，而是在偏序关系中的顺序性。x“小于或等于”y的含义是：依照这个序，x排在y的前边或者x就是y。 实例 集合A上的恒等关系 IA是 A上的偏序关系. 小于或等于关系, 整除关系和包含关系也是相应集合上的偏 序关系.一般来说，全域关系EA不是A上的偏序关系,57,相关概念,定义7.20 设 R 为非空集合A上的偏序关系, (1)x，yA，x y x yxy。 (2)x, yA, x与y可比 x yy x 任取元素 x 和