《离散数学二元关系与运算.ppt》由会员分享，可在线阅读，更多相关《离散数学二元关系与运算.ppt（60页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、离散数学二元关系与运算现在学习的是第1页，共60页1.二元有序组二元有序组二元有序组二元有序组：由两个元素由两个元素x和和y按一定顺序排成按一定顺序排成二元组，记作：二元组，记作：。4.1 4.1 二元关系的概念二元关系的概念如：平面直角坐标系中点的坐标一、二元关系的概念现在学习的是第2页，共60页(1)当x y时，(2)=，当且仅当x=u，y=v(1)、(2)说明有序组区别于集合n元有序组：由由n个元素个元素x1，x2，xn，按一定，按一定顺序排成的顺序排成的n元组，记作：元组，记作：(x1，x2，xn)。现在学习的是第3页，共60页2.一种新的集合运算一种新的集合运算 积运算积运算：设A、
2、B为两集合，用A中元素为第一元素，B中元素作为第二元素构成的二元有序组的全体叫做A和B的笛卡儿积。记作：A B符号化：A B=|xA y B现在学习的是第4页，共60页例例4.1 设A=a,b，B=0,1,2，求A B，B A解：解：根据笛卡儿积的定义知A B=,B A=,一般地：如果|A|=m，|B|=n，则|A B|=|B A|=m n,现在学习的是第5页，共60页(1)若A，B中有一个空集，则笛卡儿积是空集，即：B=A =(2)当AB，且A，B都不是空集时，有ABBA(3)当A，B，C都不是空集时，有(A B)C A(B C)因为(A B)C中的元素,z，而A(B C)中的元素为 x,。
3、现在学习的是第6页，共60页(4)A(BC)=(A B)(A C)(对的分配律)(BC)A=(B A)(C A)A(BC)=(A B)(A C)(BC)A=(B A)(C A)我们证明：A(BC)=(A B)(A C)(?)(?)(?)现在学习的是第7页，共60页 要证明两个集合相等，通常有两种方法：一是证两个集合相互包含；二是利用已有的集合运算的性质(算律和已证明过的公式)，仿照代数恒等式的证明方法，一步步从左(右)边推出右(左)边，或从左、右边分别推出同一个集合式子。一般说来，最基本的集合相等关系要用第一种证法，比较复杂的集合相等关系用第二种方法更好，但第二种方法的使用取决于我们对算律和常
4、用公式的熟练程度。现在学习的是第8页，共60页证明：证明：用第一种方法对于任意的 A (BC)xA y(BC)xA(yB yC)(xA yB)(xA yC)A B A C(A B)(A C)A(BC)=(A B)(A C)现在学习的是第9页，共60页例例4.2 设A=1,2，求P(A)A解：解：P(A)A=，1，2，1,2=，n阶笛卡儿积：=(x1,x2,xn)|x1A1 x2A2 xnAnA1 A2 An1,2，现在学习的是第10页，共60页二二元元关关系系：如如果果一一个个集集合合的的元元素素都都是是二二元元有有序序组组，则则这这个个集集合合称称为为一一个个二二元元关关系系，记记作：作：R
5、。如果 R ，记作 x R y如果 R ，记作 x R y3、二元关系的数学定义、二元关系的数学定义现在学习的是第11页，共60页从从A到到B的二元关系：的二元关系：设设A，B为集合，为集合，A B的任何子的任何子集所定义的二元关系叫做从集所定义的二元关系叫做从A到到B的的二元关系。二元关系。若A=B，叫做 A上的二元关系；若|A|n，则|A A|n2。就是说，A上有 个不同的二元关系，其中包括空关系、全域关系UA和恒等关系IA。A A的所有子集有 个。现在学习的是第12页，共60页例例4.3 设A=a,b，写出P(A)上的包含关系R：解：解：P(A)=,a,ba,bR=,现在学习的是第13页
6、，共60页1.关系矩阵：设A=x1,x2,xn)，R是A上的关系，rij=1 若xi R xj0 若xi R xj(i,j=1,2,n)则 (rij)nxn=是R的关系矩阵令：二、二元关系的表示方法现在学习的是第14页，共60页2.关系图：以E=|xiA xjA xiRxj为有向边集组成的有向图G=以V=A=x1,x2,xn 为顶点集，现在学习的是第15页，共60页例例4.4 设A=1,2,3,4，R=,是A上的关系，试写出R的关系矩阵并画出关系图：解：解：关系矩阵：0 0 1 10 0 0 00 1 0 01 1 0 0关系图：134 2现在学习的是第16页，共60页4.2 4.2 关系的运
7、算关系的运算关系关系R的定义域：的定义域：domR=x|(y)R(即即R中有序组的第一个元中有序组的第一个元素构成的集合素构成的集合)关关系系R的的值值域域：ranR=y|(x)R(即即R中中有有序序组组的的第第二二个个元元素素构构成的集合成的集合)一、关系的定义域与值域现在学习的是第17页，共60页例例4.5 下列关系都是整数集Z上的关系，分别求出它们的定义域和值域：(1)R1=|x,y Z xy(2)R2=|x,y Z x2+y2=1(3)R3=|x,y Z y=2x(4)R4=|x,y Z|x|=|y|=3 现在学习的是第18页，共60页解：解：domR1=ranR1=Z解：解：R2=,
8、domR2=(?)ranR2=(?)(1)R1=|x,y Z xy(2)R2=|x,y Z x2+y2=1,现在学习的是第19页，共60页解：解：domR3=Z，ranR3=偶数 解：解：domR4=ranR4=(?)(3)R3=|x,y Z y=2x(4)R4=|x,y Z|x|=|y|=3 现在学习的是第20页，共60页二、关系的常用运算F是任意关系，F的逆F1=|yFx F、G是任意两个关系，F与G的合成记作：F G=|(z)(xGz zFy)关系F在集A上的限制，记作：F|A=|xFy xA集A在关系F下的象FA=ran(F|A)(1)逆：(2)合成：(3)限制：(4)象：现在学习的是
9、第21页，共60页例例4.6 设F，G是N上的关系，其定义为：F=|x,yN y=x2G=|x,yN y=x+1求 G1，F G，G F，F|1,2，F1,2解：解：由定义知：G1=|y,xN y=x+1列出G1 中的元素就是G1=,现在学习的是第22页，共60页为了求F G，可以先直观表示如下：对任何xNx x+1=G即 y=(x+1)2因此 F G=|x,yN y=(x+1)2 同理可求 G F=|(?)(自己做！)发现 F G G FF|1,2=,F 1,2=ran(F|1,2)=1,4F Z Z2=y现在学习的是第23页，共60页关系运算的性质：关系运算的性质：设F、G、H、为任意关系
10、，则有：(1)(F1)1=F(2)domF1=ranF，ranF1=domF(3)(F G)H=F (G H)(4)(F G)1=G1 F1(5)F (GH)=F GF H (对的分配律)(6)F (GH)F GF H (对的半分配律)(7)(GH)F=G FH F(8)(GH)F G FH F(?)(?)现在学习的是第24页，共60页任取 (F G)1 F G(z)(G F)(z)(G1 F1)G1 F1(4)(F G)1=G1 F1的证明：现在学习的是第25页，共60页任取F (GH)(z)(GH)F)(z)(GH)F)(注意对括号的顺序)(z)(G F(H F)F GF H F (GH)
11、=F GF H(5)F (GH)=F GF H的证明：现在学习的是第26页，共60页4.3 4.3 关系的性质关系的性质R的关系矩阵：主对角线元素全是1R的关系图：每个顶点都有环自反性：x A 有R (R是A上的关系)关系矩阵：主对角线元素全是0关系图：每个顶点都没有环反自反性：x A R现在学习的是第27页，共60页对称性：若 R，则 R 关系矩阵：对称阵关 系 图：如果两个顶点之间有边，一定是一对方向相反的边。现在学习的是第28页，共60页反对称性：反对称性：若 R且xy，则 R 关系矩阵：如果rij=1，且 i j，则rji=0 关系图：如果两个顶点之间有边，一定是只有一条有向边。现在学
12、习的是第29页，共60页传递性：传递性：若 R且 R，则 R 关系图：如果顶点xi到xj有边，xj到xk有边，则从xi到xk有边现在学习的是第30页，共60页例例4.7 设A=1,2,10，对于A上的关系R=|(xy)/3II为整数集，问R有哪些性质？现在学习的是第31页，共60页解：解：逐条性质加以验证R=|(xy)/3I 任取A中元素x，由于(xx)/3=0，所以R是自自反的反的；又设A中任意两个元素x,y，如果 xRy，即xy可被3整除，则yx也一定可被3整除，即yRx，从而R是对称的对称的；如果A中三 个元素x，y，z满足xRy，yRz，则x y，yz被3整除，由于xz=(xy)+(y
13、z)，所以xz被3整除，从而xRz即R具有传递性传递性。现在学习的是第32页，共60页4.4 4.4 关系的闭包运算关系的闭包运算闭包：设RAA，自反闭包 记作 r(R)对称闭包 记作 s(R)传递闭包 记作 t(R)由A求r(R)，s(R)，t(R)的过程叫闭包运算。那么，包含R而使之具有自反性质的最小关系，称之为R的自反闭包自反闭包；包含R而使之具有对称性质(传递性质)的最小关系，称之为R的对称(传递传递)闭包闭包。一、定义现在学习的是第33页，共60页幂运算：设RAA，kN，约定(1)R0=IA=|xA(2)R1=R(3)Rk+1=Rk R显然 Rm Rn=Rm+n (Rm)n=Rmn二
14、、计算方法为了有效地计算关系R的各种闭包，先引进关系的幂运算概念。现在学习的是第34页，共60页闭包运算的方法：闭包运算的方法：设R是A上的任一关系，则(1)r(R)=RIA(2)s(R)=RR(3)t(R)=RR2R3 Rn现在学习的是第35页，共60页矩阵形式矩阵形式：(M为R的关系矩阵)(1)Mr=M+E(2)Ms=M+M (M 是M的转置)(3)Mt=M+M2+M3其中“+”均表示“逻辑加”现在学习的是第36页，共60页例例4.8 设A=a,b,c,d，A上的关系求 r(R)，s(R)和 t(R)解：解：r(R)=RIA=,R=,=R,三、实例现在学习的是第37页，共60页s(R)=R
15、R=,t(R)=RR2R3=R,现在学习的是第38页，共60页而R2=R RR3=R2 RR4=R3 R=,=,=,实际上，看到当k 4时，已有R4 RR2R3故 t(R)=RR2R3=,现在学习的是第39页，共60页四、闭包运算的性质设A是有限集且|A|=n，R A A，则：现在学习的是第40页，共60页4.6 4.6 等价关系和偏序关系等价关系和偏序关系等价关系：集A上的关系R是自反的,对称的和传递的。等价类：R是集A上的等价关系，对于任一aA，aR=x|aRx,xA被称为a的等价类。即A中所有和a有R关系的元素的集合。一、等价关系及用途现在学习的是第41页，共60页等价类的性质：等价类的
16、性质：R是非空集合，对任意的x，yA，下面的结论成立：(1)x且x A (等价类为A的子集)(2)若xRy，则x=y(3)若xRy，则xy=现在学习的是第42页，共60页集A在等价关系R下的商集：设R为非空集A上的等价关系，以R的不交的等价类为元素的集合叫做A在R下的商集，记作A/R.即：A/R=xR|x A现在学习的是第43页，共60页集A的划分：设A是非空集合，(1)(2)中任意两个元素不交(3)中所有元素的并集为A则 为A的划分。如果存在一个A的子集族，P(A)满足以下条件：现在学习的是第44页，共60页 由等价类的性质和商集的定义可知，商集A/R是A的划分，称之为由R诱导的划分。反过来
17、，给定A的任一划分，则A被分割成若干个划分块。若定义A上的二元关系R：x，yA且x,y属 的同一块，则xRy，那么R是A上的等价关系，称之为由 诱导的等价关系。集A上的等价关系与划分是一一对应的。现在学习的是第45页，共60页例例4.9 设A=1,2,3，求出A上所有的等价关系：解：解：先求A的各种划分：只有1个划分块的划分1，具有两个划分块的划分2，3，和4，具有3个划分块5。1=A2=1,2,3，4=3,1,2，3=2,1,3，5=1,2,3现在学习的是第46页，共60页设对应于划分i 的等价关系 Ri，i=1,2,5，则有R5=，R1=，R2=，R3=，R4=，现在学习的是第47页，共6
18、0页偏序关系：偏序关系：集集A上的关系上的关系R是自反的，反对称的是自反的，反对称的和传递的，记作和传递的，记作“”，且称，且称A,)为偏序集。为偏序集。二、偏序关系及用途现在学习的是第48页，共60页例例4.10 设A=2,4,6,8，A上关系R是通常意义下的小于或等于关系，试写出R并验证它是偏序关系。解：解：R=,(1)自反性：(2)反对称性：(3)传递性：,均属于R对任意的R，必有xy，当xy时，yx，从而R对任意的R，R,由于 xy yz，所以xz，从而R。现在学习的是第49页，共60页例例4.11 设C=a,b,a,b,，C上关系T是集合的“包含于”，试写出T，并验证它是偏序关系。解
19、：解：同例4.10类似，自己做！现在学习的是第50页，共60页(1)用小圆圈表示偏序集的元素(称为结点)；(2)按每个元素在偏序中的次序从底向上列结点位置；(3)对于偏序集中任意两个元素x和y，如果xy且不存在另一个元素a，使xa ay，则在x与y两结点之间划上一杠，即“|”(x在下，y在上)现在学习的是第51页，共60页全序关系：设是偏序集，(x)(y)(xA yA(xy yx)成立，则称A,)为全序集，这时的偏序关系叫全序关系。全序集A,)中全部元素可以排序，它的哈斯图为一条直线。如果现在学习的是第52页，共60页设是偏序集，B A(1)如果yB，使得(x)(xByx)为真，则y是B的最小
20、元(“小于”B中所有元)(2)如果yB，使得(x)(xB xy)为真，则y是B的最大元(“大于”B中所有元)现在学习的是第53页，共60页(4)若yB，使得 (x)(xB xy)，则称y是B的极大元(B中没有比y大的其他元)(5)若yA，使得(x)(xB xy)为真，则称y是B的上界(3)若yB，使得 (x)(xB xy)，则称y是B的极小元(B中找不到x小于y)现在学习的是第54页，共60页(6)若yA，使得(x)(xB yx)为真，则称y是B的下界(7)令C=y|y为B的上界，则称C的最小元为B的上确界或最小上界(8)令D=y|y为B的下界，则D的最大元为B的下确界或最大下界现在学习的是第
21、55页，共60页12 84610例例4.12 画出和的哈斯图，并指出其中的特殊元。解：解：(1)的哈斯图如下：92513711由图可知1为最小元，没有最大元；7,8,9,10,11,12均为极大元，极小元为1；1为1,2,12的下界，也是下确界；1,2,12中没有上确界或上界。现在学习的是第56页，共60页(2)的哈斯图如下：P(a,b,c)=,a,b,c,a,b,a,c,b,c,a,b,ca,b,ca,ca,bb,ccab由图可知：为P(a,b,c)的最小元，a,b,c为它的最大元；同时，a,b,c也分别为它们的极小元和极大元、下确界和上确界。现在学习的是第57页，共60页abcde例例4.
22、13 已知偏序集的哈斯图如下：hgf 试写出对应的A和A上的偏序关系R，并指出A中的特殊元。现在学习的是第58页，共60页,解：解：A=a,b,c,d,e,f,g,h 直接由哈斯图可知：A中没有最小元和最大元；e,g和h均为A的极大元，a,b,f 和h均为A的极小元；没有上确界和下确界。R=,abcdehgf,现在学习的是第59页，共60页了了解解二二元元关关系系的的定定义义和和表表示示方方法法；熟熟练练掌掌握握关关系系的的性性质质和和运运算算；特特别别是是复复合合和和三三种种闭闭包包运运算算;理理解解等等价价关关系系和和偏偏序序关关系系，明明确确它它们们在在描描述述研研究究对对象象的的结结构构和和特特点点时时重重要要作作用用(即即分分类类和和覆覆盖盖)。它它们们在在计计算算机机科科学学中中有有重重要要应用。应用。现在学习的是第60页，共60页