离散数学第4章习题答案.doc

第4章 关系第4章习题答案1.解 P(A)A，a， b，a，ba，b，。2. 解 (1)不正确。例如，令A，B1，C2，则ABAC，但BC不成立。(2)正确。因为(AB)C(AB)C(AB)C(ACB)(ACC)(AC)(BC)(AC)(BC)(AC)(BC)(AC)(BC)所以，(AB)C(ACBC)。(3)正确。例如，令A，则AAA。3.解 X到Y的不同的二元关系对应XY的不同的子集，而XY的不同的子集共有个，所以X到Y的二元关系总共有个。4. 证明 (2)因为A(BC) xAy(BC) xA(yByC) (xAyB)(xAyC)ABAC(AB)(AC)所以A(BC)(AB)(AC)。(3) )因为(AB)Cx(AB)yC (xAxB)yC(xAyC)xByC)ACBC(AC)(BC)所以(AB)C(AC)(BC)。(4)因为(AB)Cx(AB)yC (xAxB)yC(xAyC)(xByC)(AC)(BC)(AC)(BC)所以，(AB)C(AC)(BC)。5.解 DR0，1，2RR0，1，2R1，R10，2RRRR6. 证明 (2)因为 xDRS$y(x(RS)y)$y(xRyxSy)$y(xRy)$y(xSy)xDRxDSx(DRDS)所以DRS DRDS。(3)因为xDRDSxDRxDS xDR( xDS)$y(xRy)($y(xSy)$y(xRy) y( xSy)$y(xRyxSy)$y(x(RS)y) xDRS所以DRDSDRS。(4)因为yRRS$x(x(RS)y)$x(xR yxSy)$x(xR y)$x(xSy) yRRyRS yRRRS所以RRSRRRS。(5)因为yRRS$x(x(RS)y)$x(xR yxSy)$x(xR y)$x(xSy)yRRyRS yRRRS所以RRSRRRS。7. 证明 (1) 因为RAxAxRy xRy( xAxRy)RARRRARR所以RAR(ARR)。(2)若AB，则RAxAxRy xBxRyRB，所以RARA。(4)因为R(AB)x(AB)xRy(xAxB)xRy(xAxRy)(xBxRy)RARBRARB所以R(AB)RARB。(5)因为R(AB) x(AB)xRy(xAxB)xRy(xAxRy)(xBxRy)(xAxRy)(xBxRy)RA(RB)RARB所以R(AB)RARB。8. 证明 (1)因为RAB$x(xABxR y)$x(xAxB)xR y)$x(xAxR y)(xBxR y)$x(xAxR y)$x(xBxR y)RARBRARB所以RABRARB。(2)因为RAB$x(xABxR y)$x(xAxB)xR y)$x(xAxR y)(xBxR y)$x(xAxR y)$x(xBxR y)RARBRARB所以RABRARB。(3)因为RARBRARBRA(RB)$x(xAxR y)($x(xBxR y)$x(xAxR y)x(xBxR y)$x(xAxR y)(xBxR y)$x(xAxR y)(xBxR y)$x(xAxR yxB) $x(xABxR y)RAB所以RARBRAB。(4)若AB，则RA$x(xAxR y)$x(xBxR y)RB所以RARB。(5)必要性：因为RA y|$x(xAxR y)，DR x|$ y(xR y)，所以DR。从而DRA。充分性：若RA，由RA y|$x(xAxR y)可得DR，A，因而DRA。矛盾。故RA。(7)因为RABRAB$x(xAxR y)B(AR y)B(AR y)(BR y)(AR y)(ByR-1)(AR y)$(BR-1)(AR y)R1B(AR1BR y)$ x(xAR1BxR y)RAR1B所以RABRAR1B。9.解 R1*R2，R2*R1R12，R11*R21，*，10. 证明 (1)因为(R1)1R1R，所以(R1)1R。(3)因为(RS)1RSRSR1S1R1S1所以(RS)1R1S1。(5)因为(AB)1ABBA，所以(AB)1BA。11. 证明 (2)若RSTW，则对任意的x、y，R*T$(xRT y)($)(xSW y)S*W 所以，R*TS*W。(3) 对任意的x、y，R*(ST)$(xR(ST) y)$(xR(SyT y)$(xRS y)(xRT y)$(xRS y)$(xRT y)(R*S)(R*T)(R*S)(R*T)所以，R*(ST)(R*S)(R*T)。(5) 对任意的x、y，R*SR*TR*SR*TR*SR*T$(xRS y)($(xRT y)$(xRS y)(xRT y)(xRS y)(xRT y)(xRS y)(xRT y)(xRS y)T yxR(S yT y)xR(ST)y( xR(ST)y)$( xR(ST)y)R*(ST)所以，R*SR*TR*(ST)。(6)对任意的x、y，(R*S)1R*S$( yRS x)$(x S1R1y)S1*R1所以，(R*S)1S1*R1。(7)对任意的x、y，(R*S)*T$(x(R*S)T y)$($(xRS)T y)$(xR(ST y)$(xR(ST y)$(xR$(ST y)$(xR(S*T) y)R*(S*T)所以，(R*S)*TR*(S*T)。12. 解 (1)成立。对任意的，因为R和S是自反的，则R，S，于是R*S，故R*S也是自反的。(2)不成立。例如，令1，2，R，S，则R和S是反自反的，但R*S不是反自反的。(3)不成立。例如，令1，2，3，R，S，则R和S是对称的，但R*S，不是对称的。(4)不成立。例如，令1，2，3，R，S，则R和S是传递的，但R*S，不是传递的。(5)成立。对任意的，因为R和S是自反的，则R，S，于是RS，所以RS是自反的。(6)不成立。例如，令1，2，R，S，则R和S是传递的，但RS，不是传递的。13解 (1)R的关系图如图所示：(2) R的关系矩阵为：(3)对于R的关系矩阵，由于对角线上不全为1，R不是自反的；由于对角线上存在非0元，R不是反自反的；由于矩阵不对称，R不是对称的；经过计算可得，所以R是传递的。14.解 空关系不是自反的，但是反自反的、对称的、反对称的和传递的。全关系ZZ是自反的、对称的、传递的，但不是反自反的和反对称的。是自反的、对称的、反对称的、传递的，但不是反自反的。是反自反的、反对称的、传递的，但不是自反的和对称的。是自反的、反对称的、传递的，但不是反自反的和对称的。D(整除)是自反的、反对称的、传递的，但不是反自反的和对称的。15. 证明 (1)若R是自反的，则对任意的，有R，所以IA|R。反之，若IAR，则对任意的，有IAR，从而R，所以R是自反的。(2)若R是反自反的，则对任意的，有R，而IA|，所以RIA。反之，若RIA，由IA|得，对任意的，有R，所以R是反自反的。(3)若R是对称的，则对任意的、，因为RRR1，所以RR1。反之，若RR1，则对任意的、，若R，则R1，从而R。所以，R是对称的。(4)若RR1IA不成立，则存在、，使得RR1且，于是R，且R1，从而R，与R是反对称的矛盾，所以RR1IA。反之，若RR1IA，则对任意的、，若R且，则R，所以R是反对称的。16. 证明 (1)对任意的，由R和S是自反的得，R，S，于是RS，RS，R-1，R*S，所以RS、RS、R-1、R*S都是自反的。(2)对任意的，由R和S是反自反的得，R，S，于是RS，RS，R-1，RS，所以RS、RS、R-1、RS都是反自反的。(3)对任意的、，若RS，则RS。而R和S是对称的，则RS，从而RS，所以RS是对称的。对任意的、，若RS，则RS。而R和S是对称的，则RS，从而RS，所以RS是对称的。对任意的、，若R-1，则R。而R是对称的，则R ，从而R-1，所以R-1是对称的。对任意的、，若RS，则RS。而R和S是对称的，则RS，从而RS，所以RS是对称的。(4)对任意的、，若RS，则RS。由R和S是反对称的得R S，从而RS，所以RS是反对称的。对任意的、，若R-1，则R。由R是反对称的得R，从而 R-1，所以R-1是反对称的。对任意的、，若RS，则RS。由R和S是反对称的得R，从而RS，所以RS是反对称的。 (5)对任意的、，若RSRS，则RSRS。由R和S是传递的得RS，从而RS，所以RS是传递的。对任意的、，若R-1R-1，则RR。由R是传递的得R，从而 R-1 ，所以R-1是传递的。17.证明 若R*S对称，则R*S(R*S)-1S-1*R-1S*R。反之，若R*SS*R，则(R*S)-1(S*R)-1R-1*S-1R*S，从而R*S对称。18.证明 当1时，结论显然成立。设时，RkR。当1时，Rk+1Rk*RR*R。下面由R是自反和传递的推导出R*RR即可。由传递性得R*RR。另一方面，对任意的R，由R自反得R，再由关系的复合得R*R，从而RR*R。因此，RR*R。由数学归纳法知，对任意的正整数n，RnR。19.解 设表示A上所有自反关系构成的集合，表示A上所有反自反关系构成的集合，则|，(相当于AA中去掉个的所有子集个数)且显然有，所以|，从而|。20.解 r(R)RIA，s(R)RR-1，R2，R3，R4，R2t(R)，21. 证明 (2)若R是对称的，则RR-1，所以s(R)RR-1R。反之，若s(R)R，则由闭包的定义知R是对称的。(3)若R是传递的，由t(R)是包含R的最小传递关系得t(R)R。又因为R t(R)，所以t(R)R。反之，若t(R)R，则由闭包的定义知R是传递的。22.证明 (1)r(R1)R1 R2r(R2)，即r(R1) r(R2)。(2)因为s(R2)对称，且R2s(R2)，而R1 R2，所以R1s(R2)。又s(R1)是包含R1的最小对称关系，故s(R1)s(R2)。23.证明 (1)r(R1)r(R2)(R1)(R2)R1R2r(R1R2)。(2)s(R1)s(R2)(R1)(R2)(R1R2)()(R1R2)(R1R2)-1s(R1R2)。(3)因为R1R1R2，由定理4.16得t(R1)t(R1R2)。同理可证t(R2)t(R1R2)。所以t(R1)t(R2)t(R1R2)。24. 证明 (1)若R是自反的，则R。由闭包的定义得R s(R)，R t(R)，所以s(R)和t(R)是自反的。(3)因为R是传递的当且仅当t(R)R。要证r(R)是传递的，只需证明tr(R)r(R)。因为tr(R)t(R)，由归纳法可证：。所以tr(R)t(R)Rr(R)。故r(R)是传递的。25. 证明 (1)rs(R)r(RR-1)RR-1(R)(R-1)(R)(R)-1s(rR)sr(R)。(2) tr(R)t(R)t(R)r t(R)。26证明 设R是非空集合A上的二元关系，则由定理4.19知，tsr(R)是包含R的且具有自反性、对称性和传递性的关系。若是包含R的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r(R)。由定理4.15和由定理4.16得sr(R)s()，进而有tsr(R)t()。综上可知，tsr(R)是包含R的且具有自反性、对称性和传递性的最小关系。27.证明 对任意的AB，由R1是A上的等价关系可得R1，由R2是B上的等价关系可得R2。再由R的定义，有，R，所以R是自反的。对任意的、AB，若R，则R1且R2。由R1对称得R1，由R2对称得R2。再由R的定义，有，R，即R，所以R是对称的。对任意的、AB，若R且R，则R1且R2，R1且R2。由R1、R1及R1的传递性得R1，由R2、R2及R2的传递性得R1。再由R的定义，有，R，即R，所以R是传递的。综上可得，R是AB上的等价关系。28. 解 (1)P(R)，(2)X/P(R)1，2，4，7，3，6，5。29.解 RS、RS是A上的相容关系，R*S不是A上的相容关系。对任意的A，因为R和S是A上的两个相容关系，则R和S是自反的，于是R且S，从而RS。故RS是自反的。对任意的、A，因为RSRSRSRS，所以RS是对称的。因此，RS是A上的相容关系。对任意的A，因为R和S是A上的两个相容关系，则R和S是自反的，于是R且S，从而RS。故RS是自反的。对任意的、A，因为RSRSRSRS，所以RS是对称的。因此，RS是A上的相容关系。令A1，2，3，R，S，则R*S，R和S是相容关系，但R*S不是相容关系。30.证明 设R为A上的相容关系，故R是自反的和对称的。易证是自反的和对称的，又是传递的，所以是A上的等价关系。31. 解 (1) R的关系矩阵为：(2)由关系矩阵可知，对角线上所有元素全为1，故R是自反的；1，故R是反对称的；可计算对应的关系矩阵为：由以上矩阵可知R是传递的。32.解 的哈斯图如图所示：子集a，b的极大元为：，；极小元为：，；最大元不存在；最小元不存在；上界有 a，b， a，b，；下界为；上确界 a，b；下确界为。33. 解(1)所对应的哈斯图如图所示。它的最大元不存在，极大元为5、24，最小元为1，极小元为1。(2)所对应的哈斯图如图所示。它的最大元不存在，极大元为8、9、10、11，最小元不存在，极小元为2、3、11。34. 解 R的关系矩阵为：由关系矩阵可知，对角线上所有元素全为1，故R是自反的；1，故R是反对称的；可计算对应的关系矩阵为：由以上矩阵可知R是传递的。所以，R是偏序关系，即是偏序集。所对应的哈斯图如图所示：35.解 所有不同的偏序集的哈斯图共5个，如图所示：36. 解 令，则易证为包含序偶和的线序关系。12