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

第4章 关系
第4章习题答案
1.解 P(A)×A＝{Æ，{a}，{ b}，{a，b}}×{a，b}＝{<Æ，a >，<Æ，b >，<{a}，a >，<{a}，b >，<{ b}，a >，<{ b}，b >，<{a，b}，a >，<{a，b}，b >}。
2. 解 (1)不正确。例如，令A＝Æ，B＝{1}，C＝{2}，则A×B＝A×C＝Æ，但B＝C不成立。
(2)正确。因为
<，>∈(A－B)×CÛ∈(A－B)∧∈C
Û(∈A∧ÏB)∧∈C
Û(∈A∧∈C∧ÏB)∨(∈A∧∈C∧ÏC)
Û(∈A∧∈C)∧(ÏB∨ÏC)
Û(∈A∧∈C)∧Ø(∈B∧∈C)
Û<，>∈(A×C)∧<，>Ï(B×C)
Û<，>∈(A×C)－(B×C)
所以，(A－B)×C＝(A×C－B×C)。
(3)正确。例如，令A＝Æ，则AÍA×A。
3.解 X到Y的不同的二元关系对应X×Y的不同的子集，而X×Y的不同的子集共有个，所以X到Y的二元关系总共有个。
4. 证明 (2)因为<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)。
(3) )因为<x，y>∈(A∪B)×CÛx∈(A∪B)∧y∈C
Û (x∈A∨x∈B)∧y∈C
Û(x∈A∧y∈C)∨x∈B∧y∈C)
Û<x，y>∈A×C∨<x，y>∈B×C
Û<x，y>∈(A×C)∪(B×C)
所以(A∪B)×C＝(A×C)∪(B×C)。
(4)因为<x，y>∈(A∩B)×CÛx∈(A∩B)∧y∈C
Û (x∈A∧x∈B)∧y∈C
Û(x∈A∧y∈C)∧(x∈B∧y∈C)
Û<x，y>∈(A×C)∧<x，y>∈(B×C)
Û<x，y>∈(A×C)∩(B×C)
所以，(A∩B)×C＝(A×C)∩(B×C)。
5.解 DR＝{0，1，2}
RR＝{0，1，2}
R{1}＝{<1，0>，<1，2>}
R[{1}]＝{0，2}
RÆ＝Æ
R{Æ}＝Æ
R[Æ]＝Æ
R[{Æ}]＝Æ
6. 证明 (2)因为 x∈DR∩SÞ$y(x(R∩S)y)
Þ$y(xRy∧xSy)
Þ$y(xRy)∧$y(xSy)
Þx∈DR∧x∈DS
Þx∈(DR∩DS)
所以DR∩S ÍDR∩DS。
(3)因为x∈DR－DSÞx∈DR∧xÏDS
Þ x∈DR∧Ø( x∈DS)
Þ$y(xRy)∧Ø($y(xSy))
Þ$y(xRy)∧" y(Ø xSy)
Þ$y(xRy∧ØxSy)
Þ$y(x(R－S)y)
Þ x∈DR－S
所以DR－DSÍDR－S。
(4)因为y∈RR∪SÛ$x(x(R∪S)y)
Û$x(xR y∨xSy)
Û$x(xR y)∨$x(xSy)
Û y∈RR∨y∈RS
Û y∈RR∪RS
所以RR∪S＝RR∪RS。
(5)因为y∈RR∩SÞ$x(x(R∩S)y)
Þ$x(xR y∧xSy)
Þ$x(xR y)∧$x(xSy)
Þy∈RR∧y∈RS
Þ y∈RR∩RS
所以RR∩SÍRR∩RS。
7. 证明 (1) 因为<x，y>∈RAÛx∈A∧xRy
Û xRy∧( x∈A∧xRy)
Û<x，y>∈R∧<x，y>∈A×RR
Û<x，y>∈R∩A×RR
所以RA＝R∩(A×RR)。
(2)若AÍB，则<x，y>∈RAÛx∈A∧xRyÞ x∈B∧xRyÛ<x，y>∈RB，所以RAÍRA。
(4)因为<x，y>∈R(A∪B)Ûx∈(A∪B)∧xRy
Û(x∈A∨x∈B)∧xRy
Û(x∈A∧xRy)∨(x∈B∧xRy)
Û<x，y>∈RA∨<x，y>∈RB
Û<x，y>∈RA∪RB
所以R(A∪B)＝RA∪RB。
(5)因为<x，y>∈R(A－B)Û x∈(A－B)∧xRy
Û(x∈A∧xÏB)∧xRy
Û(x∈A∧xRy)∧(xÏB∨ØxRy)
Û(x∈A∧xRy)∧Ø(x∈B∧xRy)
Û<x，y>∈RA∧Ø(<x，y>∈RB)
Û<x，y>∈RA－RB
所以R(A－B)＝RA－RB。
8. 证明 (1)因为∈R[A∪B]Û$x(x∈A∪B∧xR y)
Û$x((x∈A∨x∈B)∧xR y)
Û$x((x∈A∧xR y)∨(x∈B∧xR y))
Û$x(x∈A∧xR y)∨$x(x∈B∧xR y)
Û∈R[A]∨∈R[B]
Û∈R[A]∪R[B]
所以R[A∪B]＝R[A]∪R[B]。
(2)因为∈R[A∩B]Û$x(x∈A∩B∧xR y)
Û$x((x∈A∧x∈B)∧xR y)
Û$x((x∈A∧xR y)∧(x∈B∧xR y))
Þ$x(x∈A∧xR y)∧$x(x∈B∧xR y)
Û∈R[A]∧∈R[B]
Û∈R[A]∩R[B]
所以R[A∩B]ÍR[A]∩R[B]。
(3)因为∈R[A]－R[B]Þ∈R[A]∧ÏR[B]
Þ∈R[A]∧Ø(∈R[B])
Þ$x(x∈A∧xR y)∧Ø($x(x∈B∧xR y))
Þ$x(x∈A∧xR y)∧"x(Ø(x∈B∧xR y))
Þ$x((x∈A∧xR y)∧Ø(x∈B∧xR y))
Þ$x((x∈A∧xR y)∧(Øx∈B∨ØxR y))
Þ$x(x∈A∧xR y∧Øx∈B)
Þ $x(x∈A－B∧xR y)
Þ∈R[A－B]
所以R[A]－R[B]ÍR[A－B]。
(4)若AÍB，则∈R[A]Û$x(x∈A∧xR y)
Þ$x(x∈B∧xR y)
Û∈R[B]
所以R[A]ÍR[B]。
(5)必要性：因为R[A]＝{ y|$x(x∈A∧xR y)}＝Æ，DR＝{ x|$ y(xR y)}，所以DR＝Æ。从而DR∩A＝Æ。
充分性：若R[A]≠Æ，由R[A]＝{ y|$x(x∈A∧xR y)}可得DR≠Æ，A≠Æ，因而DR∩A≠Æ。矛盾。故R[A]＝Æ。
(7)因为∈R[A]∩BÛ∈R[A]∧∈B
Û$x(x∈A∧xR y)∧∈B
Þ(∈A∧R y)∧∈B
Û(∈A∧R y)∧(∈B∧R y)
Û(∈A∧R y)∧(∈B∧yR-1)
Þ(∈A∧R y)∧$(∈B∧R-1)
Û(∈A∧R y)∧∈R－1[B]
Û(∈A∩R－1[B]∧R y)
Þ$ x(x∈A∩R－1[B]∧xR y)
Û∈R[A∩R－1[B]]
所以R[A]∩BÍR[A∩R－1[B]]。
9.解 R1*R2＝{<a，d>，<a，c>，<a，d>}
R2*R1＝{<c，d>}
R12＝{<a，a>，<a，b>，<a，d>}
R1－1*R2－1＝{<a，a>，<b，a>，<d，b>}*{<d，a>，<c，b>，<d，b>，<b，c>}＝{<d，c>}
10. 证明 (1)因为<x，y>∈(R－1)－1Û<y，x>∈R－1Û<x，y>∈R，所以(R－1)－1＝R。
(3)因为<x，y>∈(R∩S)－1Û<y，x>∈R∩S
Û<y，x>∈R∧<y，x>∈S
Û<x，y>∈R－1∧<x，y>∈S－1
Û<x，y>∈R－1∩S－1
所以(R∩S)－1＝R－1∩S－1。
(5)因为<x，y>∈(A×B)－1Û<y，x>∈A×BÛ<x，y>∈B×A，所以(A×B)－1＝B×A。
11. 证明 (2)若RÍS∧TÍW，则对任意的x、y，
<x，y>∈R*TÛ$(xR∧T y)
Þ($)(xS∧W y)
Û<x，y>∈S*W
所以，R*TÍS*W。
(3) 对任意的x、y，
<x，y>∈R*(S∪T)Û$(xR∧(S∪T) y)
Û$(xR∧(Sy∨T y))
Û$((xR∧S y)∨(xR∧T y))
Û$(xR∧S y)∨$(xR∧T y)
Û<x，y>∈(R*S)∨<x，y>∈(R*T)
Û<x，y>∈(R*S)∪(R*T)
所以，R*(S∪T)＝(R*S)∪(R*T)。
(5) 对任意的x、y，
<x，y>∈R*S－R*TÛ<x，y>∈R*S∧<x，y>ÏR*T
Û<x，y>∈R*S∧Ø<x，y>∈R*T
Û$(xR∧S y)∧Ø($(xR∧T y))
Û$(xR∧S y)∧"(Ø(xR∧T y))
Þ(xR∧S y)∧Ø(xR∧T y))
Û(xR∧S y)∧(ØxR∨ØT y))
Û(xR∧S y)∧ØT y
ÛxR∧(S y∧ØT y)
ÛxR∧(S－T)y
Û( xR∧(S－T)y)
Û$( xR∧(S－T)y)
Û<x，y>∈R*(S－T)
所以，R*S－R*TÍR*(S－T)。
(6)对任意的x、y，
<x，y>∈(R*S)－1Û<y，x>∈R*S
Û$( yR∧S x)
Û$(x S－1∧R－1y)
Û<x，y>∈S－1*R－1
所以，(R*S)－1＝S－1*R－1。
(7)对任意的x、y，
<x，y>∈(R*S)*TÛ$(x(R*S)∧T y)
Û$($(xR∧S)∧T y)
Û$$(xR∧(S∧T y))
Û$$(xR∧(S∧T y))
Û$(xR∧$(S∧T y))
Û$(xR∧(S*T) y)
Û<x，y>∈R*(S*T)
所以，(R*S)*T＝R*(S*T)。
12. 解 (1)成立。对任意的∈，因为R和S是自反的，则<，>∈R，<，>∈S，于是<，>∈R*S，故R*S也是自反的。
(2)不成立。例如，令＝{1，2}，R＝{<1，2>}，S＝{<2，1>}，则R和S是反自反的，但R*S＝{<1，1>}不是反自反的。
(3)不成立。例如，令＝{1，2，3}，R＝{<1，2>，<2，1>，<3，3>}，S＝{<2，3>，<3，2>}，则R和S是对称的，但R*S＝{<1，3>，<3，2>}不是对称的。
(4)不成立。例如，令＝{1，2，3}，R＝{<1，2>，<2，3>，<1，3>}，S＝{<2，3>，<3，1>，<2，1>}，则R和S是传递的，但R*S＝{<1，3>，<1，1>，<2，1>}不是传递的。
(5)成立。对任意的∈，因为R和S是自反的，则<，>∈R，<，>∈S，于是<，>∈R∩S，所以R∩S是自反的。
(6)不成立。例如，令＝{1，2}，R＝{<1，2>}，S＝{<2，1>}，则R和S是传递的，但R∪S＝{<1，2>，<2，1>}不是传递的。
13解 (1)R的关系图如图所示：
(2) R的关系矩阵为：

(3)对于R的关系矩阵，由于对角线上不全为1，R不是自反的；由于对角线上存在非0元，R不是反自反的；由于矩阵不对称，R不是对称的；
经过计算可得
，所以R是传递的。
14.解 空关系Æ不是自反的，但是反自反的、对称的、反对称的和传递的。
全关系Z×Z是自反的、对称的、传递的，但不是反自反的和反对称的。
＝是自反的、对称的、反对称的、传递的，但不是反自反的。
＜是反自反的、反对称的、传递的，但不是自反的和对称的。
≤是自反的、反对称的、传递的，但不是反自反的和对称的。
D(整除)是自反的、反对称的、传递的，但不是反自反的和对称的。
15. 证明 (1)若R是自反的，则对任意的∈，有<，>∈R，所以IA＝{<，>|∈}ÍR。
反之，若IAÍR，则对任意的∈，有<，>∈IAÍR，从而R，所以R是自反的。
(2)若R是反自反的，则对任意的∈，有<，>ÏR，而IA＝{<，>|∈}，所以R∩IA＝Æ。
反之，若R∩IA＝Æ，由IA＝{<，>|∈}得，对任意的∈，有<，>ÏR，所以R是反自反的。
(3)若R是对称的，则对任意的、∈，因为<，>∈RÛ<，>∈RÛ<，>∈R－1，所以R＝R－1。
反之，若R＝R－1，则对任意的、∈，若<，>∈R，则<，>∈R－1，从而<，>∈R。所以，R是对称的。
(4)若R∩R－1ÍIA不成立，则存在、∈，使得<，>∈R∩R－1且≠，于是<，>∈R，且<，>∈R－1，从而<，>∈R，与R是反对称的矛盾，所以R∩R－1ÍIA。
反之，若R∩R－1ÍIA，则对任意的、∈，若<，>∈R且≠，则<，>ÏR，所以R是反对称的。
16. 证明 (1)对任意的∈，由R和S是自反的得，<，>∈R，<，>∈S，于是<，>∈R∪S，<，>∈R∩S，<，>∈R-1，<，>∈R*S，所以R∪S、R∩S、R-1、R*S都是自反的。
(2)对任意的∈，由R和S是反自反的得，<，>ÏR，<，>ÏS，于是<，>ÏR∪S，<，>ÏR∩S，<，>ÏR-1，<，>ÏR－S，所以R∪S、R∩S、R-1、R－S都是反自反的。
(3)对任意的、∈，若<，>∈R∪S，则<，>∈R∨<，>∈S。而R和S是对称的，则<，>∈R∨<，>∈S，从而<，>∈R∪S，所以R∪S是对称的。
对任意的、∈，若<，>∈R∩S，则<，>∈R∧<，>∈S。而R和S是对称的，则<，>∈R∧<，>∈S，从而<，>∈R∩S，所以R∩S是对称的。
对任意的、∈，若<，>∈R-1，则<，>∈R。而R是对称的，则<，>∈R ，从而<，>∈R-1，所以R-1是对称的。
对任意的、∈，若<，>∈R－S，则<，>∈R∧Ø<，>∈S。而R和S是对称的，则<，>∈R∧Ø<，>∈S，从而<，>∈R－S，所以R－S是对称的。
(4)对任意的、∈，若<，>∈R∩S∧≠，则<，>∈R∧<，>∈S∧≠。由R和S是反对称的得<，>ÏR∧<，>Ï S，从而<，>ÏR∩S，所以R∩S是反对称的。
对任意的、∈，若<，>∈R-1∧≠，则<，>∈R∧≠。由R是反对称的得<，>ÏR，从而<，>Ï R-1，所以R-1是反对称的。
对任意的、∈，若<，>∈R－S∧≠，则<，>∈R∧Ø<，>∈S∧≠。由R和S是反对称的得<，>ÏR，从而<，>ÏR－S，所以R－S是反对称的。
(5)对任意的、、∈，若R∩S∧R∩S，则R∧S∧R∧S。由R和S是传递的得R∧S，从而R∩S，所以R∩S是传递的。
对任意的、、∈，若R-1∧R-1，则R∧R。由R是传递的得R，从而 R-1 ，所以R-1是传递的。
17.证明 若R*S对称，则R*S＝(R*S)-1＝S-1*R-1＝S*R。
反之，若R*S＝S*R，则(R*S)-1＝(S*R)-1＝R-1*S-1＝R*S，从而R*S对称。
18.证明 当＝1时，结论显然成立。设＝时，Rk＝R。当＝＋1时，Rk+1＝Rk*R＝R*R。下面由R是自反和传递的推导出R*R＝R即可。
由传递性得R*RÍR。另一方面，对任意的<，>∈R，由R自反得<，>∈R，再由关系的复合得<，>∈R*R，从而RÍR*R。因此，R＝R*R。
由数学归纳法知，对任意的正整数n，Rn＝R。
19.解 设表示A上所有自反关系构成的集合，表示A上所有反自反关系构成的集合，则||＝||＝，(相当于A×A中去掉个<，>的所有子集个数)且显然有∩＝Æ，所以|∪|＝||＋||，从而|∩|＝－|∪|＝。
20.解 r(R)＝R∪IA＝{<a，b>，<b，a>，<b，c>，<c，d>，<a，a>，<b，b>，<c，c>，<d，d>}
s(R)＝R∪R-1＝{<a，b>，<b，a>，<b，c>，<c，d>，<c，b>，<d，c>}
R2＝{<a，a>，<a，c>，<b，b>，<b，d>}
R3＝{<a，b>，<a，d>，<b，a>，<b，c>}
R4＝{<a，a>，<a，c>，<b，b>，<b，d>}＝R2
t(R)＝＝{<a，b>，<b，a>，<b，c>，<c，d>，<a，a>，<a，c>，<b，b>，<b，d>，<a，d>}
21. 证明 (2)若R是对称的，则R＝R-1，所以s(R)＝R∪R-1＝R。
反之，若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∪Í R2∪＝r(R2)，即r(R1)Í r(R2)。
(2)因为s(R2)对称，且R2Ís(R2)，而R1Í R2，所以R1Ís(R2)。又s(R1)是包含R1的最小对称关系，故s(R1)Ís(R2)。
23.证明 (1)r(R1)∪r(R2)＝(R1∪)∪(R2∪)＝R1∪R2∪＝r(R1∪R2)。
(2)s(R1)∪s(R2)＝(R1∪)∪(R2∪)＝(R1∪R2)∪(∪)＝(R1∪R2)∪(R1∪R2)-1＝s(R1∪R2)。
(3)因为R1ÍR1∪R2，由定理4.16得t(R1)Ít(R1∪R2)。同理可证t(R2)Ít(R1∪R2)。所以t(R1)∪t(R2)Ít(R1∪R2)。
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)＝∪R＝r(R)。故r(R)是传递的。
25. 证明 (1)rs(R)＝r(R∪R-1)＝R∪R-1∪＝(R∪)∪(R-1∪)＝(R∪)∪(R∪)-1＝s(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.证明 对任意的<x，y>∈A×B，由R1是A上的等价关系可得<x，x>∈R1，由R2是B上的等价关系可得<y，y>∈R2。再由R的定义，有<<x，y>，<x，y>>∈R，所以R是自反的。
对任意的<x，y>、<u，v>∈A×B，若<x，y>R<u，v>，则<x，u>∈R1且<y，v>∈R2。由R1对称得<u，x>∈R1，由R2对称得<v，y>∈R2。再由R的定义，有<<u，v>，<x，y>>∈R，即<u，v>R<x，y>，所以R是对称的。
对任意的<x，y>、<u，v>、<s，t>∈A×B，若<x，y>R<u，v>且<u，v>R<s，t>，则<x，u>∈R1且<y，v>∈R2，<u，s>∈R1且<v，t>∈R2。由<x，u>∈R1、<u，s>∈R1及R1的传递性得<x，s>∈R1，由<y，v>∈R2、<v，t>∈R2及R2的传递性得<y，t>∈R1。再由R的定义，有<<x，y>，<s，t>>∈R，即<x，y>R<s，t>，所以R是传递的。
综上可得，R是A×B上的等价关系。
28. 解 (1)P(R)＝{<1，1>，<2，2>，<3，3>，<4，4>，<5，5>，<6，6>，<7，7>，<1，2>，<2，1>，<2，4>，<4，2>，<6，3>，<3，6>，<7，1>，<1，7>，<1，4>，<4，1>，<2，7>，<7，2>，<7，4>，<4，7>}
(2)X/P(R)＝{{1，2，4，7}，{3，6}，{5}}。
29.解 R∩S、R∪S是A上的相容关系，R*S不是A上的相容关系。
对任意的∈A，因为R和S是A上的两个相容关系，则R和S是自反的，于是<，>∈R且<，>∈S，从而<，>∈R∩S。故R∩S是自反的。
对任意的、∈A，因为<，>∈R∩SÞ<，>∈R∧<，>∈SÞ<，>∈R∧<，>∈SÞ<，>∈R∩S，所以R∩S是对称的。
因此，R∩S是A上的相容关系。
对任意的∈A，因为R和S是A上的两个相容关系，则R和S是自反的，于是<，>∈R且<，>∈S，从而<，>∈R∪S。故R∪S是自反的。
对任意的、∈A，因为<，>∈R∪SÞ<，>∈R∨<，>∈SÞ<，>∈R∨<，>∈SÞ<，>∈R∪S，所以R∪S是对称的。
因此，R∪S是A上的相容关系。
令A＝{1，2，3}，R＝{<1，1>，<2，2>，<3，3>，<1，2>，<2，1>}，S＝{<1，1>，<2，2>，<3，3>，<1，3>，<3，1>}，则R*S＝{<1，1>，<1，3>，<2，2>，<3，3>，<3，1>，<1，2>，<2，1>，<2，3>}，R和S是相容关系，但R*S不是相容关系。
30.证明 设R为A上的相容关系，故R是自反的和对称的。
＝
易证是自反的和对称的，又是传递的，所以是A上的等价关系。
31. 解 (1) R的关系矩阵为：

(2)由关系矩阵可知，对角线上所有元素全为1，故R是自反的；＋≤1，故R是反对称的；可计算对应的关系矩阵为：

由以上矩阵可知R是传递的。
32.解 <P(A)，Í>的哈斯图如图所示：

子集{{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是偏序关系，即<A，R>是偏序集。所对应的哈斯图如图所示：
35.解 所有不同的偏序集的哈斯图共5个，如图所示：

36. 解 令＝{<0，0>，<1，1>，<2，2>，<3，3>，<0，2>，<0，1>，<0，3>，<2，1>，<2，3>，<1，3>}，则易证为包含序偶<0，3>和<2，1>的线序关系。
12