离散数学第七章课件

1、第七章 二元关系 7.1 有序对与笛卡尔积 7.2 二元关系 7.3 关系的运算 7.4 关系的性质 7.5 关系的闭包 7.6 等价关系与划分 7.7 偏序关系,7.1 有序对与笛卡尔积,1.序偶： 定义由二个具有给定次序的客体所组成的序列称 为序偶。记作x，y 例：XY二维平面上点的坐标x，y就是序偶。 说明：在序偶中二个元素要有确定的排列次序。即： 若ab时，则a，bb，a 若x，y=a，b（x=ay=b）,7.1 有序对与笛卡尔积,2.笛卡尔乘积 定义设A，B为二个任意集合，若序偶的第一个成 员（左元素）是A的一个元素，序偶的第 二个成员（右元素）是B的一个元素，则所 有这样的序偶的集

2、合称为A和B的笛卡尔乘积 记作：AB=x，y|（xA）（yB） 例：设A=1，2 B=a，b 则AB=, ABBA 即“”是不满足交换律。,7.1 有序对与笛卡尔积,例：设A=a，b，B=1，2，C=z 则 (AB)C=,z =, A ( BC ) =a,b1,z,2,z =, （AB）CA（BC）“”不满足结合律,7.1 有序对与笛卡尔积,性质若A，B，C是三个集合，则有： (1)A（BC）=（AB）（AC） (2)A（BC）=（AB）（AC） (3)（AB）C=（AC）（BC） (4)（AB）C=（AC）（BC）,7.1 有序对与笛卡尔积,证明：（2） 设是A(BC)中的任一元素,则 A（

3、BC） x,y |xAyBC |xAyByC |(xAyB)(xAyC) (AB)(AC) 即 A(BC)=(AB)(AC),7.1 有序对与笛卡尔积,例：设A=1，B=1，2，C=2，3 则A（BC） =11，2，3 =1，1，1，2，1，3 （AB）（AC）=11，212，3 =1，1，1，2，1，3 A（BC）=12=1，2 （AB）（AC） =1,1,1，21,2,1,3 =1，2,7.2 二元关系,序偶a，b实际上反映了二个元素之间的关系， 关系反映了事物的结构。 1.关系：指事物之间（客体之间）的相互联系。 日常生活中：父子关系，母子关系，兄弟关系等均 为二个客体之间的关系。 而祖

4、孙关系是三个客体之间的关系（父子关系和父子关 系的合成）。 n元笛卡尔积A1A2An是n元关系。,7.2 二元关系,定义若 若R AB,则R是一个二元关系。 即：序偶作为元素的 任何集合都是一个二元关系。 关系表示方法 （1）枚举法（直观法、列举法） 设R表示二元关系，用 xRy表示特定的序偶， 若 ，则也可写成： x R y。,7.2 二元关系,例：二元关系定义如图： 可写成： 由定义可见：关系是一个集合， 定义集合的方法都可以来定义关系。 （2）谓词公式表示法 前面讲述，一个集合可用谓词公式来表达，所以关系 也可用谓词公式来表达。,7.2 二元关系,例：实数集合R上的“”关系可表达为： 大

5、于关系：“”= 父子关系：“F”= （3）关系矩阵表示法 规定： (a)二元关系中的序偶中左元素表示行，右元素表示列； (b)若xiRyi，则在对应位置记上“1”，否则为“0”。,7.2 二元关系,例1：设 并定义为 列出关系矩阵：,3.关系图表示法 关系图由结点和边组成,例如， 例7中的 ， ,A,B,则 的关系图如下,例如,的关系图如下：,二、特殊关系,7.3 关系的运算,显然有,定义1：设R是由A到B的一个关系，R的定义域或前域记作domR，R的值域记作ranR，分别定义为：,1定义域和值域,例3:设A=1,2,3,4,5,6,B=a,b,c,d, R=,求domR,ranR.,解:do

6、mR=2,3,4,6,ranR=a,b,d,7.3 关系的运算,R=,R-1=,讨论定义： （1）只要将R中每一个序偶中的元素全部调换位置，就可得到R的逆关系 （2）关系矩阵为原始关系矩阵的转置 （3）在R的关系图中，只要把所有箭头改换方向就可得到（自回路箭头改变与否无关）,2逆关系,7.3 关系的运算,定义3:设R1是由A到B的关系， R2是由B到C的关系，则R1和R2的复合关系是一个由A到C 的关系，用R1R2 表示，定义为：当且仅当存在元素b，使得b C时，有 aR1 R2c这种由R1和R2 求复合关系R1R2的运算称为关系的复合运算。 由定义可知:,3复合关系,7.3 关系的运算,于是

7、复合关系,例2 设 是由 到 的关 系。 是由 B 到 的关系。 分别定义为：,2. A=1，2，3，4，5，R，S是A上的二元关系 R=， S=，,合成关系不满足交换律，满足结合律。,7.3 关系的运算,关系是以序偶为元素的集合，故可对关系进行集合的运算以产生新的关系。作为关系，绝对补运算是对全关系而言的。,4. 逆运算的性质,7.3 关系的运算,5. 复合运算的性质,定理2：设F,G,H是任意的关系，则 (1)(FG)H= F (G H) (2) (FG)-1= G-1F-1,定理3：设R为A上的关系，则 RIA)= IA R=R,7.3 关系的运算,定义给定集合X，R是X中的二元关系，设

8、n为自然数，则R的n次幂Rn定义为：,（1）,（2）,例：设R,S是,中的二元关系，且,则：,7.3 关系的运算,幂运算的求解：,若R是列举法表示，可进行多次右复合；,例：设A=a，b，c，d，R=，则R0， R2 ，R3，R4。,R0=，,R2=，,R3=，,R4=，,7.3 关系的运算,若R用关系矩阵M表示，则Rn的关系矩阵是Mn；,若R是用关系图G表示的，则可由G得Rn的关系图G。 G与G的顶点集合相同，考察G中每个顶点x，若在G中 从x出发经过n步长的路径到达顶点y，则在G中加一条 从x到y的边。当把所有顶点都考察完后，就得到G。,7.3 关系的运算,定理10.幂运算满足指数定律：Rn

9、 Rm=Rn+m （Rn）m=Rmn,幂运算的性质：,定理11.设A为n元集，R是A上的关系，则存在s、tN，使得Rs=Rt。,7.3 关系的运算,7.4 关系的性质,自反性：,定义 设是集合中的二元关系，对于每一个（所有的）,有,，则称是自反关系，X中R是自反的,例：设,是自反的关系。,R的关系矩阵,定义设R是X中的二元关系，对于每一个 ， 有x x，则称R是反自反的关系，表示成：R是X中的反 自反的关系 x x 。,例：设X=1,2,3,7.4 关系的性质,2反自反性：,7.4 关系的性质,3对称性,定义设R是X中的二元关系，对于每一个,来讲，如果每当有xRy，则必有yRx，则称R是X中的

10、 对称关系，并表示成：R是X中的对称关系,S4既不是自反的，又不是反自反的,7.4 关系的性质,例：设X=1,2,3,R= 则R是对称的关系,定义设R是X集合中的二元关系，对于每一个x,yX,来讲，如果每当xRy和yRx就必有x=y，则称R是反对称 的关系。,4反对称性,7.4 关系的性质,即当且仅当,X中的R才是反对称的。,讨论定义：（1）前件,为“T”，,则x=y也为“T”,则为反对称的；,（2）前件,为“F”，,则有三种情况：,后件（x=y）不论是真还是假，命题公式为“T”。,下面举例说明：,7.4 关系的性质,例：设X=a,b,c,均是反对称的,7.4 关系的性质,例：X=a,b,c,

11、下列关系不是对称的，也不是反对称的,7.4 关系的性质,X上的恒等关系,是自反、对称、反对称的。,7.4 关系的性质,X上的全域关系：,是自反的，对称的,X上的空关系是：,反自反、对称、反对称的。,7.4 关系的性质,5传递性：,定义设R是X中的二元关系，对于每一个,来说，如果每当,，就必有,则称R是可传递的，并表示成：X中R可传递,讨论定义：（1）前件,为“T”，,则xRz也为“T”，R是可传递的；,（2）前件为“F”，有三种情况,后件不论是真还是假，命题为“T”，则R是可传递的,7.4 关系的性质,例：设X=a,b,c，则下列关系均是可传递的,7.4 关系的性质,下列关系是不可传递的：,7

12、.4 关系的性质,6确定二元关系性质举例,（1）设X=1,2,3，,反自反，反对称，可传递的；,反对称的；,7.4 关系的性质,根据定义可证明下面几个定理是成立的。,7.4 关系的性质,7.4 关系的性质,定理3. 设R AA,则下面的命题是等价的： （1）R是对称的； （2）R-1=R； （3）MR是对称的； （4）GR中如果两个顶点之间有边，则一定是一对方向向反的边（无单边）,7.4 关系的性质,7.4 关系的性质,有没有既是对称的，又是反对称的的例子？,S=a，b，c，S上的关系R=，,有没有既不是对称的，也不是反对称的？,S上的关系Q=，,7.4 关系的性质,7.4 关系的性质,传递性

13、对并运算保持吗 ？,例1.设 是由 A上的关系， A=1,2,3, (1)求A上的关系 使得 且 是自反的。 (2)这样的关系共有多少个?,7.5 关系的闭包,关系的闭包运算是关系上的一元运算，他把给出的关系R扩充成一新关系Rc，使Rc具有一定的性质，且进行的扩充又是最小的。,7.5 关系的闭包,7.5 关系的闭包,讨论定义： （1）已知一个集合中的二元关系R，则r(R),s(R),t(R)是唯一的，它是包含R的最小的自反（对称，传递）关系； （2）若R是自反（对称，传递）的，则r(R),s(R),t(R)就是R本身。 （3）若R不是自反（对称，传递）的，则我们可以补上最少序偶，使之变为自反、

14、对称、传递关系，从而得到r(R),s(R),t(R)；,7.5 关系的闭包,例：设X=a,b,R=， r(R)=,s(R)=, t(R)=R,例：求t(R)需要特别小心，要进行多次添项。 设X=a,b,c,R=，求r(R),s(R),t(R),解：r(R)=,s(R)=,t(R)=,7.5 关系的闭包,定理给定集合X，R是X中的二元关系，于是可有： （1）当且仅当r(R)=R，则R是自反的； （2）当且仅当s(R)=R，则R是对称的； （3）当且仅当t(R)=R，则R是可传递的。,定理R是X中的二元关系,是X中的恒等关系，,则有,证明：按定义证：（1）设,，则R是自反的，,7.5 关系的闭包,

15、(3)设R是A上任一包含R的自反关系，则,定理给定集合X，R是X中的二元关系，则有,定理设X是一集合，R是X中的二元关系，则：,7.5 关系的闭包,例：X=a,b,c,R=，|X|=3, 则,定理设|X|=n，R是X中的二元关系，则,设R、r(R)、s(R)、t(R)的关系矩阵分别为M、Mr、Ms、Mt，则 Mr=M+E Ms=M+M Mt=M+M2+M3+,设R、r(R)、s(R)、t(R)的关系图分别为G、Gr、Gs、Gt，则 考察G中的每个顶点，若没有环就加上一个，得到Gr； 考察G中每条边，若有xi到xj的单向边（ij），则加xj到xi 的反向边，得Gs； 考察G中每个顶点xi，找出从

16、xi出发的所有2步、3步n步 长的路径（n为G中的顶点数）。设路径的终点为xj1、xj2、 、xjk，若没有从xi到xjl（l=1，2，k)的边，就加上这条 边。考察完所有的顶点后，得到Gt。,a b c d,解（1）,因为 所以,于是,于是,根据 的关系矩阵,于是,于是,3.利用关系图求 的闭包 例4 对例3中的关系 ，利用关系图求其闭包。,的关系图,r() 的关系图,t()的关系图,S()的关系图,7.5 关系的闭包,7.5 关系的闭包,7.6 等价关系与划分,定义1设X是一个集合，R是X中的二元关系，若R是自反的，对称的和可传递的，则称R是等价关系。,例：下列关系均为等价关系 （1）实数

17、（或I、N集上）集合上的“=”关系（相等）,（2）人类 中的同姓关系,（3）命题集合上的等价关系,例：设X=1,2,3,4,5,6,7，,为整数,7.6 等价关系与划分,试验证R是等价关系，画出R的关系图，列出R的关系矩阵,解：（1）R= ,（2）R的关系矩阵,7.6 等价关系与划分,定义设mI+ ,x,y I，若对于某个整数n 有(x-y)=n m,(x-y)/m=n(整数)，则称x模m等于y，记作：,7.6 等价关系与划分,定义2设R是X集合中的等价关系，对于任何的,来讲，可把集合,规定成：,并称是由,生成的R等价类。,讨论定义：,（1）等价类,是一个集合，由定义中可见,（2）,中的元素是

18、在等价关系R中，所有与x,具有关系的元素所组成的集合，且,7.6 等价关系与划分,例：设X=a,b,c,d,R是X中的等价关系， R=,则,定理设X是一个集合，R是X中的等价关系，则,（1）若,，则,（2）对于所有的,，或者,或者,（3）,例：设X=N，关系R=,可被3整除,是一等价关系，,则R可以找出三个等价类：,=0，3，6，9，此集合中的元素除以3的余数为“0”；,=1，4，7，10，此集合中的元素除以3的余数为“1”；,=2，5，8，11，此集合中的元素除以3的余数为“2”。,例：X为全班同学的集合，则班中同姓关系是一个等价关系，,（1）任何一个人均某一个等价类，王某某王 R 张某 张

19、R,7.6 等价关系与划分,7.6 等价关系与划分,（2）任何二个姓的等价类，只有二种可能,一种：王 R= 李R,二种：王 R李R=,（3）全班同学的集合=同姓关系等价类的并集=王,李,（4）所有等价类的集合，一定导致全班同学集合 的一个划分：A=王R，李R.,7.6 等价关系与划分,定义3设X是一非空集合，R是X中的等价关系，R等价类的集合xR| x X是X的一个划分，且此集合称为X按R的商集，记作X/R,例：设X=x1,x2.xn,（1）X集合中的全域关系，,，它是一个等价关系，,X按 R1的商集,它形成了X的一个最小划分,7.6 等价关系与划分,（2）X中的恒等关系,它形成了X的一个最大

20、划分,例：X为全班同学的集合，|X|=n, (nN),（1）同学关系R1是一个等价关系，,（2）按指纹的相同关系R2是一个等价关系，,它形成了全班同学的最大划分,7.6 等价关系与划分,（3）同姓关系R3是一等价关系,张 R3，李R3，,它形成了全班同学的既不是最大，又不是最小划分,7.6 等价关系与划分,定理X是一非空集合， A为X的一个划分，且 A=A1,A2,.An，则由A导出的X中的一个等价关系,例：Xa,b,c,d，A=a,b,c,d 则 R(a,b a,b)(c,d c,d) =, 由此我们看到：集合X上的等价关系与X的划分之间有对应关系。,7.7 偏序关系,定义设R是P中的二元关

21、系，如果R是自反的，反对称和可传递的，则称R是P中的偏序关系（或称偏序），并用符号“”表示，而序偶P，则称为偏序集合。,讨论定义：,（1）“”不单纯意味着在实数中的关系，而是代表更为普遍的关系（具有自反，反对称和可传递性的关系）；,（2）若x,y P,，“xy”读作：,“x小于或等于y”“y包含x”“x在y的前面”等；,（3）R是集合P中的偏序关系，则,也是P中的偏序关系，即R用“”表示，,则用“”表示；,（4）若P，是一个偏序集合，则P，也一定是偏序集合，且偏序集合是一个序偶，左元素为集合P，右元素为偏序关系。,例： （1）在领导机构的集合中“领导和被领导的关系”是 偏序关系；,（2）在I（整数）集合中，“”、“”均是偏序关系；,7.7 偏序关系,7.7 偏序关系,例：,中的“”（整除）=,而“”（整倍数）=,均是偏序关系。,7.7 偏序关系,定义设P，是一个偏序集合，若对于每一个,，或者xy，或者yx，即,，则“”,称为全序关系，而P，称为