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

1.二元有序组：由两个元素x和y按一定顺序排成二元组，记作：x，y。§4.1二元关系的概念如：平面直角坐标系中点的坐标一、二元关系的概念二元有序组的性质(1)当xy时，x，yy，x(2)x，y=u，v，当且仅当x=u，y=v(1)、(2)说明有序组区别于集合n元有序组：由n个元素x1，x2，…，xn，按一定顺序排成的n元组，记作：(x1，x2，…，xn)。2.一种新的集合运算–––积运算：设A、B为两集合，用A中元素为第一元素，B中元素作为第二元素构成的二元有序组的全体叫做A和B的笛卡儿积。记作：AB符号化：AB={x,y|xAyB}例4.1设A={a,b}，B={0,1,2}，求AB，BA解：根据笛卡儿积的定义知AB={a,0,a,1,a,2,}BA={0,a,0,b,}一般地：如果|A|=m，|B|=n，则|AB|=|BA|=mnb,0,b,1,b,21,a,1,b,2,a,2,b积运算的性质(1)若A，B中有一个空集，则笛卡儿积是空集，即：B=A=(2)当AB，且A，B都不是空集时，有ABBA(3)当A，B，C都不是空集时，有(AB)CA(BC)因为(AB)C中的元素x,y,z，而A(BC)中的元素为x,y,z。(4)A(B∪C)=(AB)∪(AC)(对∪的分配律)(B∪C)A=(BA)∪(CA)A(B∩C)=(AB)∩(AC)(B∩C)A=(BA)∩(CA)我们证明：A(B∪C)=(AB)∪(AC)(?)(?)(?)证明思想要证明两个集合相等，通常有两种方法：一是证两个集合相互包含；二是利用已有的集合运算的性质(算律和已证明过的公式)，仿照代数恒等式的证明方法，一步步从左(右)边推出右(左)边，或从左、右边分别推出同一个集合式子。一般说来，最基本的集合相等关系要用第一种证法，比较复杂的集合相等关系用第二种方法更好，但第二种方法的使用取决于我们对算律和常用公式的熟练程度。证明：用第一种方法对于任意的x,yA(B∪C)xAy(B∪C)xA(yByC)(xAyB)(xAyC)x,yABx,yACx,y(AB)∪(AC)A(B∪C)=(AB)∪(AC)例4.2设A={1,2}，求P(A)A解：P(A)A={，{1}，{2}，{1,2}}={,1，,2，n阶笛卡儿积：={(x1,x2,…xn)|x1A1x2A2…xnAn}A1A2…An{1,2}{1},1，{1},2，{2},1，{2},2，{1,2},1，{1,2},2}二元关系：如果一个集合的元素都是二元有序组，则这个集合称为一个二元关系，记作：R。如果x,yR，记作xRy如果x,yR，记作xRy3、二元关系的数学定义从A到B的二元关系：设A，B为集合，AB的任何子集所定义的二元关系叫做从A到B的二元关系。若A=B，叫做A上的二元关系；若|A|＝n，则|AA|＝n2。2n2就是说，A上有个不同的二元关系，其中包括空关系、全域关系UA和恒等关系IA。2n2AA的所有子集有个。例4.3设A={a,b}，写出P(A)上的包含关系R：解：P(A)={,{a},{b}{a,b}}R={,,,{a},{,{b},{a,b},{a},{a},{a},{a,b},{b},{b},{b},{a,b},{a,b},{a,b}}A上关系的表示法1.关系矩阵：设A={x1,x2,…,xn)，R是A上的关系，rij=1若xiRxj0若xiRxj(i,j=1,2,…,n)则(rij)nxn=是R的关系矩阵令：nnnnnnrrrrrrrrr212222111211二、二元关系的表示方法2.关系图：以E={xi,xj|xiAxjAxiRxj}为有向边集组成的有向图G=V,E以V=A={x1,x2,…,xn}为顶点集，例4.4设A={1,2,3,4}，R={1,1,1,2,2,3,2,4,4,2}是A上的关系，试写出R的关系矩阵并画出关系图：解：关系矩阵：0011000001001100关系图：1342§4.2关系的运算关系R的定义域：domR={x|(y)x,yR}(即R中有序组的第一个元素构成的集合)关系R的值域：ranR={y|(x)x,yR}(即R中有序组的第二个元素构成的集合)一、关系的定义域与值域例4.5下列关系都是整数集Z上的关系，分别求出它们的定义域和值域：(1)R1={x,y|x,yZxy}(2)R2={x,y|x,yZx2+y2=1}(3)R3={x,y|x,yZy=2x}(4)R4={x,y|x,yZ|x|=|y|=3}解：domR1=ranR1=Z解：R2={0,1,0,1,domR2=(?)ranR2=(?)(1)R1={x,y|x,yZxy}(2)R2={x,y|x,yZx2+y2=1}1,0,1,0}解：domR3=Z，ranR3={偶数}解：domR4=ranR4=(?)(3)R3={x,y|x,yZy=2x}(4)R4={x,y|x,yZ|x|=|y|=3}二、关系的常用运算F是任意关系，F的逆F1={x,y|yFx}F、G是任意两个关系，F与G的合成记作：FG={x,y|(z)(xGzzFy)}关系F在集A上的限制，记作：F|A={x,y|xFyxA}集A在关系F下的象F[A]=ran(F|A)(1)逆：(2)合成：(3)限制：(4)象：例4.6设F，G是N上的关系，其定义为：F={x,y|x,yNy=x2}G={x,y|x,yNy=x+1}求G1，FG，GF，F|{1,2}，F[{1,2}]解：由定义知：G1={y,x|y,xNy=x+1}列出G1中的元素就是G1={1,0,2,1,3,2,…,x+1,x,…}为了求FG，可以先直观表示如下：对任何xNxx+1=G即y=(x+1)2因此FG={x,y|x,yNy=(x+1)2}同理可求GF={x,y|(?)}(自己做！)发现FGGFF|{1,2}={1,1,2,4}F[{1,2}]=ran(F|{1,2})={1,4}FZZ2=y关系运算的性质：设F、G、H、为任意关系，则有：(1)(F1)1=F(2)domF1=ranF，ranF1=domF(3)(FG)H=F(GH)(4)(FG)1=G1F1(5)F(G∪H)=FG∪FH(对∪的分配律)(6)F(G∩H)FG∩FH(对∩的半分配律)(7)(G∪H)F=GF∪HF(8)(G∩H)FGF∩HF(?)(?)任取x,yx,y(FG)1y,xFG(z)(y,zGz,xF)(z)(z,yG1x,zF1)x,yG1F1(4)(FG)1=G1F1的证明：任取x,yx,yF(G∪H)(z)(x,z(G∪H)z,yF)(z)((x,zG∪x,zH)z,yF)(注意对括号的顺序)(z)(x,zGz,yF∪(x,zHz,yF))x,yFG∪x,yFH∴F(G∪H)=FG∪FH(5)F(G∪H)=FG∪FH的证明：§4.3关系的性质R的关系矩阵：主对角线元素全是1R的关系图：每个顶点都有环自反性：xA有x,xR(R是A上的关系)关系矩阵：主对角线元素全是0关系图：每个顶点都没有环反自反性：xAx,xR对称性：若x,yR，则y,xR关系矩阵：对称阵关系图：如果两个顶点之间有边，一定是一对方向相反的边。反对称性：若x,yR且xy，则y,xR关系矩阵：如果rij=1，且ij，则rji=0关系图：如果两个顶点之间有边，一定是只有一条有向边。传递性：若x,yR且y,zR，则x,zR关系图：如果顶点xi到xj有边，xj到xk有边，则从xi到xk有边例4.7设A={1,2,…,10}，对于A上的关系R={x,y|(xy)/3I}I为整数集，问R有哪些性质？解：逐条性质加以验证R={x,y|(xy)/3I}任取A中元素x，由于(xx)/3=0，所以R是自反的；又设A中任意两个元素x,y，如果xRy，即xy可被3整除，则yx也一定可被3整除，即yRx，从而R是对称的；如果A中三个元素x，y，z满足xRy，yRz，则xy，yz被3整除，由于xz=(xy)+(yz)，所以xz被3整除，从而xRz即R具有传递性。§4.4关系的闭包运算闭包：设RAA，自反闭包记作r(R)对称闭包记作s(R)传递闭包记作t(R)由A求r(R)，s(R)，t(R)的过程叫闭包运算。那么，包含R而使之具有自反性质的最小关系，称之为R的自反闭包；包含R而使之具有对称性质(传递性质)的最小关系，称之为R的对称(传递)闭包。一、定义幂运算：设RAA，kN，约定(1)R0=IA={x,x|xA}(2)R1=R(3)Rk+1=RkR显然RmRn=Rm+n(Rm)n=Rmn二、计算方法为了有效地计算关系R的各种闭包，先引进关系的幂运算概念。闭包运算的方法：设R是A上的任一关系，则(1)r(R)=R∪IA(2)s(R)=R∪R(3)t(R)=R∪R2∪R3∪…∪Rn∪…矩阵形式：(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)=R∪IA={a,b,b,c,c,d,d,c,,a,a,b,b,c,c,d,d}R={a,b,b,c,c,d,d,c,a,a}=R∪{a,a,b,b,c,c,d,d}三、实例s(R)=R∪R={a,b,b,c,c,d,d,c,b,a,c,b,a,a}t(R)=R∪R2∪R3∪……=R∪{b,a,c,b,d,c,c,d,a,a}而R2=RRR3=R2RR4=R3R={a,c,b,dc,c,d,d,a,b,a,d,a,a}={a,d,b,c,c,d,d,c,a,b,a,c,a,a}={a,c,b,d,c,c,d,d,a,b,a,a}实际上，看到当k4时，已有R4R∪R2∪R3故t(R)=R∪R2∪R3={a,b,b,cc,d,d,c,a,d,a,c,b,d,c,c,d,d,a,a}四、闭包运算的性质设A是有限集且|A|=n，RAA，则：ikiRRtnk1)()1(，使有)()()2(RsrRrs)()()3(RtrRrt)()()4(RtsRst§4.6等价关系和偏序关系等价关系：集A上的关系R是自反的,对称的和传递的。等价类：R是集A上的等价关系，对于任一aA，[a]R={x|aRx,xA}被称为a的等价类。即A中所有和a有R关系的元素的集合。一、等价关系及用途等价类的性质：R是非空集合，对任意的x，yA，下面的结论成立：(1)[x]