离散数学,二元关系与运算PPT课件

.,二元关系和运算,第四章,.,1.二元有序组：由两个元素x和y按一定顺序排成二元组，记作：。,4.1二元关系的概念,如：平面直角坐标系中点的坐标,一、二元关系的概念,.,二元有序组的性质,(1)当xy时，,(2)=，当且仅当x=u，y=v,(1)、(2)说明有序组区别于集合,n元有序组：由n个元素x1，x2，xn，按一定顺序排成的n元组，记作：(x1，x2，xn)。,.,2.一种新的集合运算积运算：,设A、B为两集合，用A中元素为第一元素，B中元素作为第二元素构成的二元有序组的全体叫做A和B的笛卡儿积。,记作：AB,符号化：AB=|xAyB,.,例4.1设A=a,b，B=0,1,2，求AB，BA,解：根据笛卡儿积的定义知,AB=,BA=,一般地：如果|A|=m，|B|=n，则|AB|=|BA|=mn,.,积运算的性质,(1)若A，B中有一个空集，则笛卡儿积是空集，即：B=A=,(2)当AB，且A，B都不是空集时，有ABBA,(3)当A，B，C都不是空集时，有(AB)CA(BC),因为(AB)C中的元素,z，而A(BC)中的元素为。,.,(4)A(BC)=(AB)(AC)(对的分配律),(BC)A=(BA)(CA),A(BC)=(AB)(AC),(BC)A=(BA)(CA),我们证明：,A(BC)=(AB)(AC),(?),(?),(?),.,证明思想,要证明两个集合相等，通常有两种方法：一是证两个集合相互包含；,二是利用已有的集合运算的性质(算律和已证明过的公式)，仿照代数恒等式的证明方法，一步步从左(右)边推出右(左)边，或从左、右边分别推出同一个集合式子。,一般说来，最基本的集合相等关系要用第一种证法，比较复杂的集合相等关系用第二种方法更好，但第二种方法的使用取决于我们对算律和常用公式的熟练程度。,.,证明：用第一种方法,对于任意的A(BC),xAy(BC),xA(yByC),(xAyB)(xAyC),ABAC,(AB)(AC),A(BC)=(AB)(AC),.,例4.2设A=1,2，求P(A)A,解：P(A)A,=，1，2，1,2,=，,n阶笛卡儿积：,=(x1,x2,xn)|x1A1x2A2xnAn,A1A2An,1,2,，,，,，,.,二元关系：如果一个集合的元素都是二元有序组，则这个集合称为一个二元关系，记作：R。,如果R，记作xRy,3、二元关系的数学定义,.,从A到B的二元关系：设A，B为集合，AB的任何子集所定义的二元关系叫做从A到B的二元关系。,若A=B，叫做A上的二元关系；,若|A|n，则|AA|n2。,就是说，A上有个不同的二元关系，其中包括空关系、全域关系UA和恒等关系IA。,AA的所有子集有个。,.,例4.3设A=a,b，写出P(A)上的包含关系R：,解：P(A)=,a,ba,b,R=,.,A上关系的表示法,1.关系矩阵：,设A=x1,x2,xn)，R是A上的关系，,则(rij)nxn=,是R的关系矩阵,令：,二、二元关系的表示方法,.,2.关系图：,以E=|xiAxjAxiRxj为有向边集组成的有向图G=,以V=A=x1,x2,xn为顶点集，,.,例4.4设A=1,2,3,4，R=,是A上的关系，试写出R的关系矩阵并画出关系图：,解：关系矩阵：,0011,0000,0100,关系图：,.,4.2关系的运算,关系R的定义域：domR=x|(y)R(即R中有序组的第一个元素构成的集合),关系R的值域：ranR=y|(x)R(即R中有序组的第二个元素构成的集合),一、关系的定义域与值域,.,例4.5下列关系都是整数集Z上的关系，分别求出它们的定义域和值域：,(1)R1=|x,yZxy,(2)R2=|x,yZx2+y2=1,(3)R3=|x,yZy=2x,(4)R4=|x,yZ|x|=|y|=3,.,解：domR1=ranR1=Z,解：R2=,domR2=(?),ranR2=(?),(1)R1=|x,yZxy,(2)R2=|x,yZx2+y2=1,.,解：domR3=Z，ranR3=偶数,解：domR4=ranR4=(?),(3)R3=|x,yZy=2x,(4)R4=|x,yZ|x|=|y|=3,.,二、关系的常用运算,F是任意关系，F的逆F1=|yFx,F、G是任意两个关系，F与G的合成记作：FG=|(z)(xGzzFy),关系F在集A上的限制，记作：F|A=|xFyxA,集A在关系F下的象FA=ran(F|A),(1)逆：,(2)合成：,(3)限制：,(4)象：,.,例4.6设F，G是N上的关系，其定义为：,F=|x,yNy=x2,G=|x,yNy=x+1,求G1，FG，GF，F|1,2，F1,2,解：由定义知：,G1=|y,xNy=x+1,列出G1中的元素就是,G1=,.,为了求FG，可以先直观表示如下：,对任何xN,即y=(x+1)2,因此FG=|x,yNy=(x+1)2,同理可求GF=|(?)(自己做！),发现FGGF,F|1,2=,F1,2=ran(F|1,2)=1,4,.,关系运算的性质：设F、G、H、为任意关系，则有：,(1)(F1)1=F,(2)domF1=ranF，ranF1=domF,(3)(FG)H=F(GH),(4)(FG)1=G1F1,(5)F(GH)=FGFH(对的分配律),(6)F(GH)FGFH(对的半分配律),(7)(GH)F=GFHF,(8)(GH)FGFHF,(?),(?),.,任取,(FG)1,FG,(z)(GF),(z)(G1F1),G1F1,(4)(FG)1=G1F1的证明：,.,任取,F(GH),(z)(GH)F),(z)(GH)F)(注意对括号的顺序),(z)(GF(HF),FGFH,F(GH)=FGFH,(5)F(GH)=FGFH的证明：,.,4.3关系的性质,R的关系矩阵：主对角线元素全是1,R的关系图：每个顶点都有环,自反性：xA有R(R是A上的关系),关系矩阵：主对角线元素全是0,关系图：每个顶点都没有环,反自反性：xAR,.,对称性：若R，则R,关系矩阵：对称阵,关系图：如果两个顶点之间有边，一定是一对方向相反的边。,.,反对称性：若R且xy，则R,关系矩阵：如果rij=1，且ij，则rji=0,关系图：如果两个顶点之间有边，一定是只有一条有向边。,.,传递性：若R且R，则R,关系图：如果顶点xi到xj有边，xj到xk有边，则从xi到xk有边,.,例4.7设A=1,2,10，对于A上的关系R=|(xy)/3I,I为整数集，问R有哪些性质？,.,解：逐条性质加以验证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，则xy，yz被3整除，由于xz=(xy)+(yz)，所以xz被3整除，从而xRz即R具有传递性。,.,4.4关系的闭包运算,闭包：设RAA，,自反闭包记作r(R),对称闭包记作s(R),传递闭包记作t(R),由A求r(R)，s(R)，t(R)的过程叫闭包运算。,那么，包含R而使之具有自反性质的最小关系，称之为R的自反闭包；,包含R而使之具有对称性质(传递性质)的最小关系，称之为R的对称(传递)闭包。,一、定义,.,幂运算：设RAA，kN，约定,(1)R0=IA=|xA,(2)R1=R,(3)Rk+1=RkR,显然RmRn=Rm+n(Rm)n=Rmn,二、计算方法,为了有效地计算关系R的各种闭包，先引进关系的幂运算概念。,.,闭包运算的方法：设R是A上的任一关系，则,(1)r(R)=RIA,(2)s(R)=RR,(3)t(R)=RR2R3Rn,.,矩阵形式：(M为R的关系矩阵),(1)Mr=M+E,(2)Ms=M+M(M是M的转置),(3)Mt=M+M2+M3,其中“+”均表示“逻辑加”,.,例4.8设A=a,b,c,d，A上的关系,求r(R)，s(R)和t(R),解：r(R)=RIA,=,R=,=R,三、实例,.,s(R)=RR,=,t(R)=RR2R3,=R,.,而R2=RR,R3=R2R,R4=R3R,=,=,=,实际上，看到当k4时，已有R4RR2R3,故t(R)=RR2R3,=,.,四、闭包运算的性质,设A是有限集且|A|=n，RAA，则：,.,4.6等价关系和偏序关系,等价关系：集A上的关系R是自反的,对称的和传递的。,等价类：R是集A上的等价关系，对于任一aA，,aR=x|aRx,xA,被称为a的等价类。,即A中所有和a有R关系的元素的集合。,一、等价关系及用途,.,等价类的性质：R是非空集合，对任意的x，yA，下面的结论成立：,(1)x且xA(等价类为A的子集),(2)若xRy，则x=y,(3)若xRy，则xy=,.,集A在等价关系R下的商集：设R为非空集A上的等价关系，以R的不交的等价类为元素的集合叫做A在R下的商集，记作A/R.,即：,A/R=xR|xA,.,集A的划分：设A是非空集合，,(1),(2)中任意两个元素不交,(3)中所有元素的并集为A,则为A的划分。,如果存在一个A的子集族，P(A)满足以下条件：,.,由等价类的性质和商集的定义可知，商集A/R是A的划分，称之为由R诱导的划分。,反过来，给定A的任一划分，则A被分割成若干个划分块。,若定义A上的二元关系R：x，yA且x,y属的同一块，则xRy，那么R是A上的等价关系，称之为由诱导的等价关系。,集A上的等价关系与划分是一一对应的。,.,例4.9设A=1,2,3，求出A上所有的等价关系：,解：先求A的各种划分：只有1个划分块的划分1，具有两个划分块的划分2，3，和4，具有3个划分块5。,1=A,2=1,2,3，,4=3,1,2，,3=2,1,3，,5=1,2,3,.,设对应于划分i的等价关系Ri，i=1,2,5，则有,R5=，,R1=，,R2=，,R3=，,R4=，,，,，,，,，,，,，,，,，,.,偏序关系：集A上的关系R是自反的，反对称的和传递的，记作“”，且称x，从而R,对任意的R，R,由于xyyz，所以xz，从而R。,.,例4.11设C=a,b,a,b,，C上关系T是集合的“包含于”，试写出T，并验证它是偏序关系。,解：同例4.10类似，自己做！,.,偏序集的哈斯图,(1)用小圆圈表示偏序集的元素(称为结点)；,(2)按每个元素在偏序中的次序从底向上列结点位置；,(3)对于偏序集中任意两个元素x和y，如果xy且不存在另一个元素a，使xaay，则在x与y两结点之间划上一杠，即“|”(x在下，y在上),.,全序关系：设是偏序集，,(x)(y)(xAyA(xyyx),成立，则称A,)为全序集，这时的偏序关系叫全序关系。,全序集A,)中全部元素可以排序，它的哈斯图为一条直线。,如果,.,偏序集中的一些特殊元素,设是偏序集，BA,(1)如果yB，使得(x)(xByx)为真，则y是B的最小元(“小于”B中所有元),(2)如果yB，使得(x)(xBxy)为真，则y是B的最大元(“大于”B中所有元),.,(4)若yB，使得(x)(xBxy)，则称y是B的极大元(B中没有比y大的其他元),(5)若yA，使得(x)(xBxy)为真，则称y是B的上界,(3)若yB，使得(x)(xBxy)，则称y是B的极小元(B中找不到x小于y),.,(6)若yA，使得(x)(xByx)为真，则称y是B的下界,(7)令C=y|y为B的上界，则称C的最小元为B的上确界或最小上界,(8)令D=y|y为B的下界，则D的最大元为B的下确界或最大下界,.,例4.12画出和的哈斯图，并指出其中的特殊元。,解：(1)的哈斯图如下：,由图可知1为最小元，没有最大元；,7,8,9,10,11,12均为极大元，极小元为1；,1为1,2,12的下界，也是下确界；,1,2,12中没有上确界或上界。,.,(2)的哈斯图如下：,P(a,b,c)=,a,b,c,a,b,a,c,b,c,a,b,c,由图可知：为P(a,b,c)的最小元，a,b,c为它的最大元；,同时，a,b,c也分别为它们的极小元和极大元、下确界和上确界。,.,a,b,c,d,e