国防科大版离散数学习题答案.doc

第二章 二元关系
第一章 集合
习题1.1

1.
a) {0, 1, 2, 3, 4}
b) {11, 13, 17, 19}
c) {12, 24, 36, 48, 64}

2.
a) {x | x Î N 且x £ 100}
b) Ev = {x | x Î N 且2整除x } Od = {x | x Î N 且2不能整除x }
c) {y | 存在x Î I 使得 y = 10 · x } 或 {x | x/10 Î I }

3. 极小化步骤省略
a) ① {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} Í A ；
② 若a, b Î A，则a·b Î A 。
或
① {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} Í A ；
② 若a Î A 且 a Î {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}，则a·a Î A 。
或
① {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} Í A ；
② 若a Î A 且 a Î {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}，则a·a Î A 。
b)
① {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} Í A ；
② 若a, b Î A 且 a ¹ 0，则 a·b Î A 。
c) ① 若a Î {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}，则 a. Î A ；
② 若a Î A 且 a Î {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}，则a·a Î A ；
若a Î A 且 a Î {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}，则a·a Î A 。
或
① {0., 1., 2., 3., 4., 5., 6., 7., 8., 9.} Í A ；
② 若a Î A 且 a Î {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}，则a·a Î A ；
若a Î A 且 a Î {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}，则a·a Î A 。
d) ① {0, 10} Í A ；
② 若a Î A，则1·a Î A ；
若a, b Î A 且 a ¹ 0，则 a·b Î A 。
e) Ev定义如下：
① {0} Í Ev 或0 Î Ev ；
② 若a Î Ev，则a+2 Î Ev 。
Od定义如下：
① {1} Í Od 或1 Î Od ；
② 若a Î Od，则a+2 Î Od 。
f) ① {0} Í A 或 0 Î A ；
② 若a Î A，则 Î A 。

4. A = G；C = F；B = E。

5. 题号 是否正确
a) ü
b) ´ （空集不含任何元素）
c) ü
d) ü
e) ü
f) ´
g) ü
h) ´

6. 题号 是否正确
a) ´ （ 反例：A = {a}；B = Æ；C = {{a}} ）
b) ´ （ 反例：A = Æ；B = {Æ}；C = {Æ} ）
c) ´ （ 反例：A = Æ；B = {a}；C = {Æ} ）
d) ´ （ 反例：A = Æ；B = {Æ}；C = {{Æ}} ）

7. 能。例如：B = A È {A} 。

8.
a) Æ；{1}；{2}；{3}；{1, 2}；{1, 3}；{2, 3}；{1, 2, 3}；
b) Æ；{1}；{{2, 3}}；{1, {2, 3}}；
c) Æ；{{1, {2, 3}}}；
d) Æ；{Æ}；
e) Æ；{Æ}；{{Æ}}；{Æ, {Æ}}；
f) Æ；{{1, 2}}；
g) Æ；{{Æ, 2}}；{{2}}；{{Æ, 2}, {2}}；

9.
a) {Æ，{a}，{{b}}，{a, {b}}}；
b) {Æ，{1}，{Æ}，{1, Æ}}；
c) {Æ，{x}，{y}，{z}，{x, y}，{x, z}，{y, z}，{x, y, z}}；
d) {Æ，{Æ}，{a}，{{a}}，{Æ, a}，{Æ, {a}}，{a, {a}}，{Æ, a, {a}}}。
习题1.2

1.
a) A Ç ~B = {4}；
b) (A Ç B) È ~C = {1, 3, 5}；
c) ~ (A Ç B) = {2, 3, 4, 5}；
d) ~A È ~B = {2, 3, 4, 5}；
e) (A – B) – C = Æ；
f) A – (B – C) = {4}；
g) (A Å B) Å C = {5}；
h) (A Å B) Å (B Å C) = {1, 2}。

2.
a) B Ç C 或 B – E ；
b) A Ç D ；
c) (A – B) Ç C ；
d) C – B 或C – A ；
e) (A Ç C) È (E – B) 或 (A – E) È (E – B)；

3.
a) 证明：对于任意x Î A È C，
因为x Î A È C，所以x Î A或x Î C。
若x Î A，则由于A Í B，因此x Î B；
若x Î C，则由于C Í D，因此x Î D。
所以，x Î B或x Î D，即x Î B È D。
所以，A È C Í B È D。
类似可证A Ç C Í B Ç D。
d) A – (B È C) = A Ç ~ (B È C) = A Ç (~ B Ç ~C) = (A Ç A) Ç (~ B Ç ~C)
= (A Ç ~B) Ç (A Ç ~C) = (A – B) Ç (A – C)
f) A – (A – B) = A Ç ~ (A – B) = A Ç ~ (A Ç ~B) = A Ç (~ A È B)
= (A Ç ~A) Ç (A Ç B) = Æ Ç (A Ç B) = A Ç B

4.
a) Þ) 若A = B，则A È B = A且 A Ç B = A。
因此，A Å B = (A È B) – (A Ç B) = A – A = Æ。
Ü) 若A Å B = Æ，则A È B = A Ç B。
又因为A Ç B Í A Í A È B且A Ç B Í B Í A È B，所以
A Ç B = A = B = A È B。
所以A = B。

5. 证明略。
a) ü
b) ü
c) ´ （反例：A = {a, b}，B = {a}，C = {b}）
d) ´ （反例：A = {a}，B = {a, b}，C = {a, c}）
e) ü
f) ´ （反例：A = {a, b}，B = {a}，C = {b}）
g) ´ （反例：A = {a}，B = {a, b}，C = {a, c}）

6.
a) B Ç C Í ~ A；
b) A Í B Ç C；
c) A Í ~ (B È C)，即B È C Í ~ A；
d) A Í B È C；
e) (A – B) Å (A – C) = (A Ç ~B) Å (A Ç ~C) =
((A Ç ~B) È (A Ç ~C)) – ((A Ç ~B) Ç (A Ç ~C)) =
((A Ç ~B) È (A Ç ~C)) Ç ~ ((A Ç ~B) Ç (A Ç ~C)) =
((A Ç ~B) È (A Ç ~C)) Ç (~ (A Ç ~B) È ~ (A Ç ~C)) =
((A Ç ~B) È (A Ç ~C)) Ç ( (~ A È B) È (~A È C)) =
(A Ç (~B È ~C)) Ç ( ~ A È (B È C)) =
(A Ç (~B È ~C)) Ç (B È C) =
A Ç ( (B È C) Ç ~ (B Ç C) ) =
A Ç (B Å C)
因此，若(A – B) Å (A – C) = A，则A Ç (B Å C) = A。
所以，A Í (B Å C)。
f) 由上题，(A – B) Å (A – C) = A Ç (B Å C)
因此，若(A – B) Å (A – C) = Æ，则A Ç (B Å C) = Æ。
g) A = B；
h) A = B = Æ；
i) A = B；
j) B = Æ；
k) B Í A 或 A Í B。

7.
a) 对于任意x ÎÃ(A) ÈÃ(B)，则x ÎÃ(A) 或x ÎÃ(B)。
若x ÎÃ(A)，则x Í A。因为A Í A È B，所以，x Í A È B。
因此，x ÎÃ(A È B)。
若x ÎÃ(B)，则x Í B。因为B Í A È B，所以，x Í A È B。
因此，x ÎÃ(A È B)。
所以，总有x ÎÃ(A È B)。
因此，Ã(A) ÈÃ(B) Í Ã(A È B)。
b) 对于任意x ÎÃ(A) ÇÃ(B)，则x ÎÃ(A) 且x ÎÃ(B)。
x ÎÃ(A)，因此x Í A。x ÎÃ(B)，因此x Í B。
所以，x Í A Ç B。
因此，x ÎÃ(A Ç B)。
所以，Ã(A) ÇÃ(B) Í Ã(A Ç B)。

8.
a) È{{Æ}} = {Æ}，Ç{{Æ}} = {Æ}；
b) È{Æ, {Æ}} = {Æ}，Ç{Æ, {Æ}} = Æ；
c) È{{a}, {b}, {a, b}} = {a, b}，Ç{{a}, {b}, {a, b}} = Æ。

9. 证明：
i) 若x Î R0，则x Î R且x £ 1。所以对于任意iÎI+均有x < 1+1/i。即对于任意iÎI+均有x Î Ri。所以，xÎ。
ii) 若x Î ，则对于任意iÎI+均有x Î Ri。所以对于任意iÎI+均有x < 1+1/i。所以，x £ 1，故xÎ。
10. 因为An+1 £ An，所以，。
11. ，。
12.

a) ；
b) 。

习题1.3

1.
a) 证明：用第一归纳法
i) 当n = 1 时，左边 = 1/2 = 右边；
ii) 对任意的k ³ 1，假设当n = k时命题为真，即

因为

即当n = k+1时命题也为真。
由i) ii)可知，对于任意n³1均有
。
b) 证明：用第一归纳法
i) 当n = 1 时，左边 = 2 = 右边；
ii) 对任意的k ³ 1，假设当n = k时命题为真，即
2+22+23+L+2k = 2k+1-2
因为
2+22+23+L+2k+ 2k+1= 2k+1-2+2k+1 =2k+2-2
即当n = k+1时命题也为真。
由i) ii)可知，对于任意n³1均有
2+22+23+L+2n = 2n+1-2。
c) 证明：用第一归纳法
i) 当n = 0 时，左边 = 1 ³ 0 = 右边；
当n = 1 时，左边 = 2 ³ 2 = 右边；
ii) 对任意的k ³ 1，假设当n = k时命题为真，即
2k ³ 2k
因为
2k+1= 2·2k ³ 2·2k ³ 2k+2 =2(k+1) （因为k ³ 1）
即当n = k+1时命题也为真。
由i) ii)可知，对于任意n³1均有
2n = 2n。
d) 证明：用第一归纳法
i) 当n = 1 时，左边 = 3 ，右边 = 3，3|3，所以n=1时命题为真；
ii) 对任意的k ³ 1，假设当n = k时命题为真，即
3 | k3 +2k
因为
(k+1)3 + 2(k+1) = k3 + 3k2 + 3k +1 + 2k +2 = (k3 + 2k) + 3(k2 + k +1)
由于3 | k3 +2k且3 | 3(k2 + k +1)，因此，3 | (k+1)3 +2(k+1)
即当n = k+1时命题也为真。
由i) ii)可知，对于任意n³1均有
3 | n3 +2n。
e) 证明：用第一归纳法
i) 当n = 1 时，左边 = 6 = 右边 = 3，所以n=1时命题为真；
ii) 对任意的k ³ 1，假设当n = k时命题为真，即
1·2·3 + 2·3·4 + L + k(k+1)(k+2) = k(k+1)(k+2)(k+3) / 4
因为
1·2·3 + 2·3·4 + L + k(k+1)(k+2) + (k+1)(k+2)(k+3) =
k(k+1)(k+2)(k+3) / 4+ (k+1)(k+2)(k+3) =
(k+1)(k+2)(k+3)(k+4) / 4
即当n = k+1时命题也为真。
由i) ii)可知，对于任意n³1均有
1·2·3 + 2·3·4 + L + n(n+1)(n+2) = n(n+1)(n+2)(n+3) / 4。
f) 证明：证明分三部分
①三个相邻整数中最小者 ³ 0；
②三个相邻整数中最小者 = -1；
③三个相邻整数中最小者 £ -2。
对①用第一归纳法，即证9 | n3 + (n+1) 3 + (n+2) 3
i) 当n = 0 时，9 | 9，所以n = 0时命题为真；
ii) 对任意的k ³ 0，假设当n = k时命题为真，即
9 | k3 + (k+1) 3 + (k+2) 3
因为
(k+1)3 + (k+2) 3 + (k+3) 3 =
k3 + 3k2 + 3k +1 + (k+1) 3 + 3(k+1)2 + 3(k+1) +1 + (k+2) 3 + 3(k+2)2 + 3(k+2) +1 =
k3 + (k+1) 3 + (k+2) 3 + 3k2 + 3k +1 + 3(k+1)2 + 3(k+1) +1 + 3(k+2)2 + 3(k+2) +1 =
k3 + (k+1) 3 + (k+2) 3 + 9k2 + 27k +27 =
k3 + (k+1) 3 + (k+2) 3 + 9(k2 + 3k +3)
由于 9 | k3 + (k+1) 3 + (k+2) 3且9 | 9(k2 + 3k +3)
所以，9 | (k+1)3 + (k+2) 3 + (k+3) 3，即当n = k+1时命题也为真。
由i) ii)可知，对于任意n ³ 0均有
9 | n3 + (n+1) 3 + (n+2) 3
对③由于9 | n3 + (n+1) 3 + (n+2) 3，所以，9 | (-n)3 + (-(n+1)) 3 + (-(n+2)) 3。
对②因为9 | 0，所以此时命题也为真。

根据以上证明可知，任意三个相邻整数的立方和能被9整除。
g) 证明：用第一归纳法
i) 当n = 0 时，112 + 121 = 133，133 | 133，所以n = 0时命题为真；
ii) 对任意的k ³ 0，假设当n = k时命题为真，即
133 | 11 k+2+122 k+1
因为
11 k+3+122 (k+1)+1 = 11·11 k+2+122·122 k + 1 = 11· (11 k+2+122 k + 1) + 133·122 k + 1
由于 133 | 11 k+2+122 k+1 且 133 | 133·122 k + 1
因此，133 | 11· (11 k+2+122 k + 1) + 133·122 k + 1。
即当n = k+1时命题也为真。
由i) ii)可知，对于任意n³1均有
133 | 11 n+2+122 n+1

3. 证明：用第二归纳法
i) 当n = 1 时，，所以n = 1时命题为真；
当n = 2 时，，所以n = 2时命题为真；
ii) 对任意的k ³ 2，假设当2 £ n £ k时命题均为真，
则由 对于任意nÎI+，Fn+1 = Fn + Fn-1 可知
Fk+1 = Fk + Fk-1 £
£ £
£
Fk+1 = Fk + Fk-1 ³
³ ³
³
即当n = k+1时命题也为真。
由i) ii)可知，对于任意n³1均有
。

4. 分析：（证明略）
设n = (m+1) q + r，m ³ r > 0。
首先，甲扳倒r根，然后每当乙扳倒x（1£ x £ m）根，因为1£ (m+1) – x £ m，所以此时甲可扳倒(m+1) – x根，故甲总能获胜。
证明：对q（即n除以m+1的商）用第一归纳法。
i) 当q = 0时，因为n = r且m ³ r ³ 1，所以甲可一次将r根全部扳倒，则甲获胜。
ii) 对任意的k ³ 0，假设当q = k时命题为真，
则当q = k+1时，即存在r使得n = (m+1) (q+1) + r，m ³ r > 0 ，由于
此时甲可扳倒r根，然后乙只能扳倒x（1£ x £ m）根，此时剩下n¢ = (m+1)q+(m+1)-q根， 因为1£ (m+1) – x £ m，则根据归纳假设可知甲总能获胜。
即当q = k+1时命题也为真。
由i) ii)可知，对于任意q ³ 0均有甲总能获胜。

5. 证明：用第一归纳法
对于每个i ³ i0，用Q(i)表示下列命题：
对于任意j ³ j0，P (i, j)皆真。
下面验证：Q(i)满足第一归纳法的条件。
i) Q(i0)为真， 因为（对j用第一归纳法）：
a) P(i0, j0)为真；
b) 若P(i0, j)为真，则P (i0, j+1)为真；
由归纳法可知，Q(i0)为真。
ii) 若Q(i)为真（i ³ i0），即对于任意i ³ i0，j ³ j0，P (i, j)为真。
则对于任意j ³ j0，P(i+1, j)为真，即Q (i+1)为真。
由i)和ii)可知，对于任意i ³ i0，Q (i)皆真。
所以，对于任意i ³ i0，j ³ j0，P (i, j)为真。

6. 证明：假设有n Î N使n Î n ，即 {n} Í n ，故n+ = {n}Èn Í n ，同时n Í n+ ，所以n = n+。矛盾！（与皮亚诺公理矛盾）

10. 证明：假设有m Î N使n < m，则由“<”定义可知n Î m，所以由习题7有n Ì m。因为n Î m 且n Ì m，所以 nÈ{n} Í m，即n+ Í m。
而m < n+，则由“<”定义可知m Î n+，由习题7有m Ì n+。
n+ Í m与m Ì n+矛盾，所以假设不成立，即不可能有m Î N使n < m < n+。

习题1.4

1.
a) A ´ {1} ´ B = {<0, 1, 1>, <0, 1, 2>, <1, 1, 1>, <1, 1, 2> }
b) A2 ´ B = {<0, 0, 1>, <0, 0, 2>, <0, 1, 1>, <0, 1, 2>, <1, 0, 1>, <1, 0, 2>, <1, 1, 1>, <1, 1, 2> }
c) (B ´ A)2 = { <1, 0, 1, 0>, <1, 0, 1, 1>, <1, 0, 2, 0>, <1, 0, 2, 1>,
<1, 1, 1, 0>, <1, 1, 1, 1>, <1, 1, 2, 0>, <1, 1, 2, 1>,
<2, 0, 1, 0>, <2, 0, 1, 1>, <2, 0, 2, 0>, <2, 0, 2, 1>,
<2, 1, 1, 0>, <2, 1, 1, 1>, <2, 1, 2, 0>, <2, 1, 2, 1> }

2. 题号 是否正确
a) ´ （反例：A=D={a}，B=C=Æ，则左边={<a,a>}，而右边=Æ）
b) ü
c) ´ （反例：A=C=D=N，B=Æ，则左边=Æ，而右边=N´N）
d) ´ （反例：A=C={1, 2}，B={1}，D={2}，则左边={<2, 1>}，
而右边={<1, 1>, <2, 1>, <2, 2>}）

7. 证明：题目等价于证明：若<a, b> = <c, d>，则a = c且b = d。
设<a, b> = <c, d>，则{{a, A}, {b, B}} = {{c, A}, {d, B}}
① {a, A} = {c, A}且{b, B} = {d, B}
所以，a = c且b = d。
② {a, A} = {d, B}且{b, B} = {c, A}
则因为A¹B，所以a = B, d = A, b = A且c = B。
所以，a = c且b = d。
故总有：a = c且b = d。

第二章 二元关系
习题2.1

1.
d) R = {<0, 0>, <0, 2>, <2, 0>, <2, 2>}
e) R = {<1, 1>, <4, 2>}

2.
R1 È R2 = {<1, 2>, <2, 4>, <3, 3>, <1, 3>, <4, 2>}
R1 Ç R2 = {<2, 4>}
dom R1 = {1, 2, 3}
dom R2 = {1, 2, 4}
ran R1 = {2, 3, 4}
ran R2 = {2, 3, 4}
dom (R1 È R2) = {1, 2, 3, 4}
ran (R1 Ç R2) = {4}

3.
证明：（根据定义域和值域的定义进行证明）
因为
x Î dom (R1 È R2) 当且仅当 有y Î B使得<x, y> Î (R1 È R2)
当且仅当 有y Î B使得<x, y> Î R1 或 <x, y> Î R2
当且仅当 有y Î B使得<x, y> Î R1 或有y Î B使得<x, y> Î R2
当且仅当 x Î dom (R1) 或 x Î dom (R2)
当且仅当 x Î dom (R1) È dom (R2)
所以，dom (R1 È R2) = dom (R1) È dom (R2) 。
因为
若x Î ran (R1 Ç R2)，则 有x Î A使得<x, y> Î (R1 Ç R2) ；
有x Î A使得<x, y> Î R1 且 <x, y> Î R2 ；
有x Î A使得<x, y> Î R1 且 有x Î A使得<x, y> Î R2 ；
x Î ran (R1) 且 x Î ran (R2) ；
x Î ran (R1) Ç ran (R2) 。
所以，ran (R1 Ç R2) Í ran (R1) Ç ran (R2) 。

4.
L = {<1, 2>, <1, 3>, <1, 6>, <2, 3>, <2, 6>, <3, 6> }；
D = {<1, 1>, <1, 2>, <1, 3>, <1, 6>, <2, 2>, <2, 6>, <3, 3>, <3, 6>, <6, 6> }；
L Ç D = { <1, 2>, <1, 3>, <1, 6>, <2, 6>, <3, 6> }。

5.
a) Æ上的空关系Æ；
b) 集合 {1, 2 } 上的二元关系 { <1, 1> }；
c) 集合 {1, 2 } 上的二元关系 { <1, 1> } ；
d) 集合 {1, 2, 3 } 上的二元关系 { <1, 2>, <2, 1>, <1, 3> } ；

6.
若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 È S , R – S , R Å S对称。
若R, S反对称， 则R Ç S , R – S反对称，R È S , R Å S不一定反对称。
若R, S传递， 则R Ç S传递，, R – S , R È S , R Å S不一定传递。

8.
a) S是对称的、传递的；
b) S是自反的、对称的；
c) S是反对称的、传递的；
d) S是反自反的、反对称的、传递的；

8.
n ( Am ) = nm ；
n (Ã( Am ) ) = ；
因为R Í Am，所以A上共有个m元关系。

10.
证明： 用反证法。
假设R不是反对称的，即
存在a, b Î A，使得<a, b> Î A, <b, a> Î A 且a ¹ b。
因为R是传递的，所以由<a, b> Î A且<b, a> Î A可知<a, a> Î A。
这与R反自反性质矛盾。
所以假设不成立。即R是反对称的。

11.
证明：因为R = {<x, y> | x, y Î A 且<x, y> Î R} = {{{x}, {x, y}} | x, y Î A 且<x, y> Î R }
所以，È R = {{x}, {x, y} | x, y Î A 且<x, y> Î R }。
所以，È(ÈR) = {x | x Î A且有y Î A使得<x, y> Î R }È{y | y Î A且有x Î A使得<x, y>ÎR }。
= dom R È ran R 。
即：fld R = dom R È ran R 。

12.
证明：因为dom R Í fld R = È ( È R )，ran R Í fld R = È ( È R )，
所以，R Í dom R ´ ran R Í È ( È R ) ´ È ( È R ) 。

习题2.2

1.
R是自反的、对称的、传递的。

2.
(1) 自反的；
(2) 反对称的、传递的；
(3) 自反的、对称的、传递的；
(4) 自反的、传递的；
(5) 无；
(6) 对称的；
(7) 自反的、反对称的、传递的；
(8) 对称的；
(9) 对称的；
(10) 反对称的；
(11) 自反的、反对称的；
(12) 反对称的、传递的。

4.
b) A上共有个不相同的自反关系；
c) A上共有个不相同的反自反关系；
d) A上共有个不相同的对称关系；
e) A上共有个不相同的反对称关系；
f) A上共有个不相同的既是对称的又是反对称的关系；

习题2.3

1. 最多能有n(A) 个元素为1。

2.
证明：
i) R È R-1为A上包含R的最小对称关系
① R Í R È R-1。所以，RÈR-1包含R。
② 因为对于任意<a, b> Î R È R-1，有<a, b> Î R或<a, b> Î R-1。
若<a, b> Î R，则<b, a> Î R-1；若<a, b> Î R-1，则<b, a> Î R。
因此，<b, a> Î R È R-1。所以，RÈR-1为A上的对称关系。
③ 设R¢为任意的A上包含R的对称关系，则
对于任意<a, b> Î R È R-1，有<a, b> Î R或<a, b> Î R-1。
若<a, b> Î R，由于R¢包含R，所以<a, b> Î R¢；
若<a, b> Î R-1，则<b, a> Î R，由于R¢包含R，所以<b, a> Î R¢，而R¢对称，所以<a, b> Î R¢。
因此，总有<a, b> Î R¢。所以，R È R-1 Í R¢。
由①②③可知，R È R-1为A上包含R的最小对称关系。

ii) R Ç R-1为A上包含在R中的最大对称关系
① R Ç R-1 Í R。所以，R Ç R-1包含在R中。
② 因为对于任意<a, b> Î R Ç R-1，有<a, b> Î R且<a, b> Î R-1。
<a, b> Î R，所以<b, a> Î R-1；<a, b> Î R-1，所以<b, a> Î R。
因此，<b, a> Î R Ç R-1。所以，R Ç R-1为A上的对称关系。
③ 设R¢为任意的A上包含在R中的对称关系，则
对于任意<a, b> Î R¢，由于R¢包含在R中，所以<a, b> Î R；
又由于R¢对称，所以<b, a> Î R¢，而R¢包含在R中，所以<b, a> Î R，因此，<a, b> Î R-1；
因此，总有<a, b> Î R Ç R-1。所以，R Í RÈR-1。
由①②③可知，R Ç R-1为A上包含在R中的最大对称关系。

习题2.4

1.
R2 O R1 = {<c, d>}； R1 O R2 = {<a, d>, <a, c>}；
R12 = {<a, a>, <a, b>, <a, d>}； R22 = {<b, b>, <c, c>}；

2. m = 1, n = 16。

4. A = {1, 2, 3}
令R1 = {<1, 2>, <1, 3>}；R2 = {<2, 2>}；R3 = {<3, 2>}；则
R1 O ( R2 Ç R3 ) = Æ；( R1 O R2 ) Ç ( R1 O R3 ) = {<1, 3>}；
所以，R1 O ( R2 Ç R3 ) Ì ( R1 O R2 ) Ç ( R1 O R3 ) 。

令R2 = {<2, 2>}；R3 = {<2, 3>}；R4 = {<2, 1>, <3, 1>}；则
( R2 Ç R3 ) O R4 = Æ；( R2 O R4 ) Ç ( R3 O R4 ) = {<2, 1>}；
所以，( R2 Ç R3 ) O R4 Ì ( R2 O R4 ) Ç ( R3 O R4 ) ；

5.
a) 正确。
b) 不正确。令A = {1, 2}，则R1 = {<1, 2>}, R2 = {<2, 1>}都是反自反的，但R1 O R2 ={<1, 1>}不是反自反的。
c) 不正确。令A = {1, 2, 3}，则R1 = {<1, 2>, <2, 1>}, R2 = {<2, 3>, <3, 2>}都是对称的，但R1 O R2 = {<1, 3>}不是对称的。
d) 不正确。令A = {1, 2, 3}，则R1 = {<1, 2>, <3, 1>}, R2 = {<2, 3>, <1, 1>}都是反对称的，但R1 O R2 = {<1, 3>, <3, 1>}不是反对称的。
e) 不正确。令A = {1, 2, 3}，则R1 = {<1, 2>, <3, 1>, <3, 2>}, R2 = {<2, 3>, <1, 1>}都是传递的，但R1 O R2 = {<1, 3>, <3, 1>, <3, 3>}不是传递的。

9. 证明：
a) 对于任意k Î N，因为Rs = Rt ，所以Rs+k = Rs ·Rk = Rt ·Rk = Rt+k 。
b) 用关于k的归纳法证明。
i) 当k=0时，Rs+i = Rs+i。所以命题成立。
ii) 假设当k=m时命题成立，即Rs + mp + i = Rs + i。
则当k=m+1时，因为Rs + (m+1) p + i=Rs + p + mp+ i=Rt + mp + i=Rt ·Rmp+i =Rs ·Rmp+i =Rs + mp + i。
由归纳假设，Rs + (m+1) p + i = Rs + mp + i = Rs + i。
由i) ii)可知对于任意k, i Î N，均有Rs + kp + i = Rs + i 。
f) 若k £ t-1，则Rk Î {R0, R1, …, Rt-1}；
若k ³ t，则k = s + (t-s)q + r，即k = s + pq + r；（其中，qÎ N, 0 £ r < t-s = p）
此时，由b)可知Rk = Rs + pq + r = Rs + r Î {R0, R1, …, Rt-1}。
所以，若k Î N，则Rk Î {R0, R1, …, Rt-1}。

习题2.5

2.
使t (R1 È R2) É t ( R1 ) È t ( R2 ) 的R1 和R2 的具体实例如下：
A = {1, 2}，R1 = {<1, 2>}，R1 = {<2, 1>}；
则t ( R1 ) = R1 ，t ( R2 ) = R2 ，t (R1 È R2) = {<1, 2>, <2, 1>, <1, 1>, <2, 2>}，
故真包含。

4.
b) 使s (R1 Ç R2) Ì s ( R1 ) Ç s ( R2 ) 的R1 和R2 的具体实例如下：
A = {1, 2}，R1 = {<1, 2>}，R1 = {<2, 1>}；
则s ( R1 ) = s ( R2 ) = {<1, 2>, <2, 1>}，s (R1 Ç R2) = s(Æ) = Æ。
故真包含：s (R1 Ç R2) Ì s ( R1 ) Ç s ( R2 )。

b) 使t (R1 Ç R2) Ì t ( R1 ) Ç t ( R2 ) 的R1 和R2 的具体实例如下：
A = {1, 2, 3}，R1 = {<1, 2>, <2, 1>}，R1 = {<1, 3>, <3, 1>}；
则t ( R1 ) = {<1, 2>, <2, 1>, <1, 1>, <2, 2>}，t ( R2 ) = {<1, 3>, <3, 1>, <1, 1>, <3, 3>}，
t (R1 Ç R2) = s(Æ) = Æ。
故真包含：t (R1 Ç R2) Ì t ( R1 ) Ç t ( R2 )。

6. 令A = {1, 2}，R = {<1, 2>}，则
ts(R) = t ({<1, 2>, <2, 1>}) = {<1, 2>, <2, 1>, <1, 1>, <2, 2>}
st(R) = s ({<1, 2>}) = {<1, 2>, <2, 1>}
所以，st(R) ¹ ts(R)。

习题2.6

1.
a) 正确；
b) 正确；
c) 不正确；（不自反）
d) 不正确；（不自反）
e) 不正确；（不一定对称）
f) 正确。

2. R的所有极大相容类为：{x1, x2, x3}，{x1, x3, x6}，{x3, x4, x5}，{x3, x5, x6}。

3. A上共有个不相同的相容关系。

习题2.7

1.
a) 不正确；（