离散数学课件第四章二元关系习题.ppt

1、第四章 二元关系习题练习、(79页第题)R1,R2是集合中的关系，试证明：(1)r(R1R2)=r(R1)r(R2)(2)s(R1R2)=s(R1)s(R2)(3)t(R1R2)t(R1)t(R2)（书上是等号）证明(1)左边=r(R1R2)=R1R2 Ix 右边=r(R1)r(R2)=R1 Ix R2 Ix =R1R2 Ix(1)式得证。2 证(2)左边=s(R1R2)=(R1R2)(R1 R2)=R1R2 R1 R2=(R1 R1)(R2 R2)=s(R1)s(R2)(2)得证。3 证(3)t(R1R2)t(R1)t(R2)t(R1R2)=(R1R2)(R1R2)2 (R1R2)n 而(R

2、1R2)2=(R1R2)o(R1R2)=(R1R2)oR1)(R1R2)oR2)=R12R2oR1R1oR2R22R12 R22 (R1R2)n R1n R2n 于是有(R1R2)(R1R2)2 (R1R2)n R1 R12 R1n R2 R22 4 R22 R2n 即t(R1R2)t(R1)t(R2)(3)得证、(85页第题)设1,2,n是集合的划分，试证明：1，2,n 是集合 的划分 证明：因为1 2 5 n 于是有1BB 2 B B n B B 并且1B2B n B=(1 2 n)B=AB.对任何对任何(iB)(jB)=(ij)B=B=(ij)6 3.(85页第题）把n个元素的集合划分为

3、两个类，共有多少种不同的分法？解：个元素的有种分法：即1a1,a2,即2(2-1)-1 3个元素的有种分法：即1a1,a2,a3 2a2,a1,a3 3a3,a1,a2即2(-1)-17 4个元素的有种：即1a1,a2,a3,a4 2a2,a1,a3,a4 3a3,a1,a2,a4 4a4,a1,a2,a3 5a1,a2,a3,a4 6a1,a3,a2,a4 7a1,a4,a2,a3 即2(4-1)-1 一般具有n个元素的集合分成两堆的分法有2(n-1)-1种8 4.(85页第题)在等价关系图中，应如何识别等价类？解：关系图中如果有孤立的结点，则它是一个等价类；都不与其它结点相关联的相互联结的

4、两个结点构成一个等价类；都不与其它结点相关联的相互联结的三个结点构成一个等价类；都不与其它结点相关联对角线相关联的四个结点构成一个等价类9 都不与其它结点相关联的正五角星构成一个等价类；都不与其它结点相关联的正六角星构成一个等价类；10 上述图例中，省略了各结点上的自环，用一条无向边代替一对方向相反的有向边 5.(85页第题)设是集合中的关系，对于所有的xi,xj和xk属于，如果xixj和xjxk就有xkxi 则称是循环关系，试证明当且仅当是一个等价关系，才是自反的和循环的 证明：充分性设是等价关系，来证明是循环的(自反性是明显的)11 对任何xi,xj和xk属于和xixj，xjxk有 xix

5、k及xkxi(由的可传递性和对称性得)即是循环的 必要性：设是自反的和循环的来证是个等价关系实际上只要证是对称的和可传递的即可 对任何xi,xj和xk属于和xixj，xjxk有 xkxi及xixi于是有xixk即是对称的和可传递的 综上问题得证12 6.(86页第题)设1和R2是集合中的等价关系，试证明：当且仅当1中的每一个等价类都包含于2中的某一个等价类中，才有R1 R2 证明：设1和R2造成的划分分别是 1=c11,c12,c1n 2=c21,c22,c2m 对任意的c1i1(i=1,.,n),在2中都存在 某一个c2j(j=1,2,.,m)并且c1ic2j13 对于任何x,yc1i则x,

6、yc2j 于是有1则R2 即1R2充分性得证 再证必要性：设1R2，于是对任意1(等价于x,y应属于1造成的划分1 的某一个类c1i中,i=1,2,.n)则R2，(等价于x,y一定属于2造成的划分2 的某一个类c2j中,j=1,2,.m)必要性得证14.(86页第题)设1和R2是集合中的等价关系，并分别有秩r1和r2，试证明：1R2也是集合X中的等价关系，它的秩至多是r1r2。而 1R2不一定是集合X中的等价关系 证明：首先证明1R2是等价关系 1)(x)(xX R1R2)=(x)(xX(R1R2)=(x)(xXR1)(xX R2)15=(x)(xXR1)(x)(xXR2)=T T=T利用全称

7、量词对与的可分配性 自反性得证 再来证1R2是对称的 用反证法，假设1R2是不对称的，即(x)(y)(x,yX1R2 1R2)=(x)(y)(x,yX1 2(12)16=(x)(y)(x,yX1 2 1)(x,yX1 R22)=(x)(y)(x,yX1 2 1)(x)(y)(x,yX1 R22)(利用存在量词对的可分配性)=F F=F即假设不成立，对称性得证17 使用反证法同样可以证明1R2 是可传递的即它是等价关系 再来证1R2 至多有r1r2个类 因为对任意的x,yX和R1 R2x,y C1i x,y C2j 其中i=1,2,r1,j=1,2,r2至多为r1r2 证毕18.(89页第题)给

8、定集合=A1,A2,An的覆盖，如何确定此覆盖的相容关系。解：其对应的相容关系为：R=A1x A1 A2x A2 Anx An 9.(90页第题)设集合=1,2,3,求出中的等价关系R1 R2,使得R1OR2也是个等价关系 解：令R1是任何等价关系,R2是个恒等关系即可19 例如令R1=,R2=Ix R1oR2为所求 10.(95页第题)如果是集合中的偏序关系,且X,试证明R(AXA)是A中的偏序关系 证明：即证R(AXA)是自反的，反对称的和可传递的。20)证自反性，即证对(x)(xA R(AXA)为真，而(x)(xA R(AXA)(x)(xA R(AXA)(x)(xA(R(AXA)(x)(

9、xAR)(xA(AXA)(x)(xAR)(x)(xA(AXA)（全称量词对的可分配性）(x)(xAR)(x)(xA(AXA)TT=T自反性得证21)证反对称性即证对(x)(y)(x,yAR(AXA)R(AXA)x=y)为真 上式=(x)(y)(x,yAR(AXA)R(AXA)x=y)=(x)(y)(x,yA)R(AXA)R(AXA)x=y)=(x)(y)(x,yA)R Rx=y)(x,yA)(AXA)(AXA)x=y)而上式可由(x)(y)(x,yA)R Rx=y)(x)(y)(x,yA)(AXA)(AXA)x=y)逻辑地推出 22 显然此式为真(已知条件)，于是(x)(y)(x,yAR(AXA)R(AXA)x=y)为真)再证R(AXA)是可传递的，即证(x)(y)(z)(x,y,zAR(AXA)R(AXA)R(AXA)为真,而上式=(x)(y)(z)(x,y,zA)R(AXA)R(AXA)(R(AXA)23 对上式使用对的分配律，再利用全称量词对的可分配性及已知条件，问题可得证24