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

第二章 二元关系

第一章 集合

习题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，则??? ? 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 。 {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 。

b)

① {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} ? A ；

② 若?, ? ? A 且 ? ? 0，则 ??? ? A 。

c) ① 若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 ? {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}，则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 。 d) ① {0, 10} ? A ；

② 若? ? A，则1?? ? A ；

若?, ? ? A 且 ? ? 0，则 ??? ? A 。 e) Ev定义如下：

① {0} ? Ev 或0 ? Ev ； ② 若? ? Ev，则?+2 ? Ev 。

- 1 -

第二章 二元关系

Od定义如下：

① {1} ? Od 或1 ? Od ； ② 若? ? Od，则?+2 ? Od 。 ① {0} ? A 或 0 ? A ； ② 若? ? A，则(f)

??1)2 ? A 。

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

5. 题号 是否正确 a) ? b) ? （空集不含任何元素） c) ? d) ? e) ? 6. 7. 8. a) b) c) d) e) f) g) 9. a) b) c) d)

f) g) h) 题号 a) b) c) d)

? ? ?

是否正确

? （ 反例：A = {a}；B = ?；C = {{a}} ） ? （ 反例：A = ?；B = {?}；C = {?} ） ? （ 反例：A = ?；B = {a}；C = {?} ） ? （ 反例：A = ?；B = {?}；C = {{?}} ）

能。例如：B = A ? {A} 。

?；{1}；{2}；{3}；{1, 2}；{1, 3}；{2, 3}；{1, 2, 3}； ?；{1}；{{2, 3}}；{1, {2, 3}}； ?；{{1, {2, 3}}}； ?；{?}；

?；{?}；{{?}}；{?, {?}}； ?；{{1, 2}}；

?；{{?, 2}}；{{2}}；{{?, 2}, {2}}；

{?，{a}，{{b}}，{a, {b}}}； {?，{1}，{?}，{1, ?}}；

{?，{x}，{y}，{z}，{x, y}，{x, z}，{y, z}，{x, y, z}}；

{?，{?}，{a}，{{a}}，{?, a}，{?, {a}}，{a, {a}}，{?, a, {a}}}。

习题1.2

- 2 -

第二章 二元关系

1. a) b) c) d) e) f) g) h) 2. a) b) c) d) e)

A ? ~B = {4}；

(A ? B) ? ~C = {1, 3, 5}； ~ (A ? B) = {2, 3, 4, 5}； ~A ? ~B = {2, 3, 4, 5}； (A – B) – C = ?； A – (B – C) = {4}； (A ? B) ? C = {5}；

(A ? B) ? (B ? C) = {1, 2}。

B ? C 或 B – E ； A ? D ；

(A – B) ? C ； C – B 或C – A ；

(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) f) 4. a)

A – (B ? C) = A ? ~ (B ? C) = A ? (~ B ? ~C) = (A ? A) ? (~ B ? ~C) = (A ? ~B) ? (A ? ~C) = (A – B) ? (A – C)

A – (A – B) = A ? ~ (A – B) = A ? ~ (A ? ~B) = A ? (~ A ? B) = (A ? ~A) ? (A ? B) = ? ? (A ? B) = A ? B

?) 若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) d) e)

?

?

? （反例：A = {a, b}，B = {a}，C = {b}） ? （反例：A = {a}，B = {a, b}，C = {a, c}） ?

- 3 -

第二章 二元关系

6. a) b) c) d) e)

f) g) ? ? （反例：A = {a, b}，B = {a}，C = {b}） （反例：A = {a}，B = {a, b}，C = {a, c}）

B ? C ? ~ A； A ? B ? C；

A ? ~ (B ? C)，即B ? C ? ~ A； A ? B ? 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) ? (~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) ?{?, {?}} = {?}，?{?, {?}} = ?；

- 4 -

第二章 二元关系

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?

??Ri?1?i。

ii) 若x ?

?Ri?1i，则对于任意i?I+均有x ? Ri。所以对于任意i?I+均有x < 1+1/i。所以，x

? 1，故x?

?Ri?1?i。

??10. 因为An+1 ? An，所以

?An?0n?A0，?An??。

n?011.

?Ax?Rx?1x?{y|y?R且y?0}，?Ax?{y|y?R且0?y?1}。

x?Rx?112. a)

x?A iff ?m?0有x??Ai iff ?m?0总?n?m使得x?An；

i?m??b)

x?A iff ?m?0有x??Ai iff ?m?0使得?n?m有x?An。

i?m- 5 -

第二章 二元关系

习题1.3

1.

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

111k ?????1?22?3k?(k?1)k?1因为

1111?????? 1?22?3k?(k?1)(k?1)?(k?2)k1??

(k?1)(k?1)?(k?2)

k?(k?2)?1(k?1)2(k?1) ??(k?1)?(k?2)(k?1)?(k?2)(k?2) 即当n = k+1时命题也为真。 由i) ii)可知，对于任意n?1均有

111n。 ?????1?22?3n?(n?1)n?1b) 证明：用第一归纳法

i) 当n = 1 时，左边 = 2 = 右边； ii) 对任意的k ? 1，假设当n = k时命题为真，即 c)

2+22+23+?+2k = 2k+1-2 因为

2+22+23+?+2k+ 2k+1= 2k+1-2+2k+1 =2k+2-2 即当n = k+1时命题也为真。 由i) ii)可知，对于任意n?1均有

2+22+23+?+2n = 2n+1-2。

证明：用第一归纳法

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。

- 6 -

第二章 二元关系

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时命题为真，即 f)

1?2?3 + 2?3?4 + ? + k(k+1)(k+2) = k(k+1)(k+2)(k+3) / 4 因为

1?2?3 + 2?3?4 + ? + 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 + ? + n(n+1)(n+2) = n(n+1)(n+2)(n+3) / 4。

证明：证明分三部分

①三个相邻整数中最小者 ? 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整除。

- 7 -

第二章 二元关系

g)

3. 证明：用第二归纳法

i) 当n = 1 时，(证明：用第一归纳法

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

1?5?11?50)?F1?()，所以n = 1时命题为真； 221?51)，所以n = 2时命题为真； 2当n = 2 时，1?F2?F1?F0?1?(

ii) 对任意的k ? 2，假设当2 ? n ? k时命题均为真，

则由 对于任意n?I+，Fn+1 = Fn + Fn-1 可知

Fk+1 = Fk + Fk-1 ? (

1?5k?11?5k?2)?() 22

? (1?5k?21?51?5k?23?5)(?1) ? ()() 2222

? (1?5k) 21?5k?21?5k?3)?() 22

Fk+1 = Fk + Fk-1 ? (

? (1?5k?31?51?5k?33?5)(?1) ? ()() 2222

? (1?5k?1) 2 即当n = k+1时命题也为真。 由i) ii)可知，对于任意n?1均有

1?5n?21?5n?1()?Fn?() 。

22- 8 -

第二章 二元关系

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+。

- 9 -

第二章 二元关系

习题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=?，则左边={}，而右边=?） 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 = c且b = 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) e) 2.

R = {<0, 0>, <0, 2>, <2, 0>, <2, 2>} R = {<1, 1>, <4, 2>}

R1 ? R2 = {<1, 2>, <2, 4>, <3, 3>, <1, 3>, <4, 2>} R1 ? R2 = {<2, 4>}

- 10 -

第二章 二元关系

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使得 ? (R1 ? R2) 当且仅当 有y ? B使得 ? R1 或 ? R2 当且仅当 有y ? B使得 ? R1 或有y ? B使得 ? 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使得 ? (R1 ? R2) ； 有x ? A使得 ? R1 且 ? R2 ；

有x ? A使得 ? R1 且 有x ? A使得 ? 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不一定反对称。

- 11 -

第二章 二元关系

若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 ) ) = 2nm ；

nm因为R ? Am，所以A上共有2个m元关系。

10.

证明： 用反证法。

假设R不是反对称的，即 存在a, b ? A，使得 ? A, ? A 且a ? b。 因为R是传递的，所以由 ? A且 ? A可知 ? A。 这与R反自反性质矛盾。

所以假设不成立。即R是反对称的。 11.

证明：因为R = { | x, y ? A 且 ? R} = {{{x}, {x, y}} | x, y ? A 且 ? R } 所以，? R = {{x}, {x, y} | x, y ? A 且 ? R }。 所以，?(?R) = {x | x ? A且有y ? A使得 ? R }?{y | y ? A且有x ? A使得?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) 自反的、对称的、传递的；

- 12 -

第二章 二元关系

(4) 自反的、传递的； (5) 无； (6) 对称的；

(7) 自反的、反对称的、传递的； (8) 对称的； (9) 对称的； (10) 反对称的； (11) 自反的、反对称的； (12) 反对称的、传递的。 4.

b) A上共有2c) A上共有2d) A上共有2n2?n个不相同的自反关系； 个不相同的反自反关系； 个不相同的对称关系；

n2?n2n2?nn2?n2e) A上共有2?3f)

nn个不相同的反对称关系；

A上共有2个不相同的既是对称的又是反对称的关系；

习题2.3

1. 最多能有n(A) 个元素为1。 2. 证明：

i) R ? R-1为A上包含R的最小对称关系 ① R ? R ? R-1。所以，R?R-1包含R。

② 因为对于任意 ? R ? R-1，有 ? R或 ? R-1。 若 ? R，则 ? R-1；若 ? R-1，则 ? R。 因此， ? R ? R-1。所以，R?R-1为A上的对称关系。 ③ 设R?为任意的A上包含R的对称关系，则

对于任意 ? R ? R-1，有 ? R或 ? R-1。 若 ? R，由于R?包含R，所以 ? R?； 若 ? R-1，则 ? R，由于R?包含R，所以 ? R?，而R?对称，所以 ? R?。 因此，总有 ? R?。所以，R ? R-1 ? R?。

由①②③可知，R ? R-1为A上包含R的最小对称关系。

ii) R ? R-1为A上包含在R中的最大对称关系

- 13 -

第二章 二元关系

① R ? R-1 ? R。所以，R ? R-1包含在R中。

② 因为对于任意 ? R ? R-1，有 ? R且 ? R-1。 ? R，所以 ? R-1； ? R-1，所以 ? R。 因此， ? R ? R-1。所以，R ? R-1为A上的对称关系。 ③ 设R?为任意的A上包含在R中的对称关系，则

对于任意 ? R?，由于R?包含在R中，所以 ? R；

又由于R?对称，所以 ? R?，而R?包含在R中，所以 ? R，因此， ? R-1； 因此，总有 ? R ? R-1。所以，R ? R?R-1。

由①②③可知，R ? R-1为A上包含在R中的最大对称关系。

习题2.4

1.

R2 ? R1 = {}； R1 ? R2 = {, }； R12 = {, , }； R22 = {, }；

2. m = 1, n = 16。

4. A = {1, 2, 3}

令R1 = {<1, 2>, <1, 3>}；R2 = {<2, 2>}；R3 = {<3, 2>}；则 R1 ? ( R2 ? R3 ) = ?；( R1 ? R2 ) ? ( R1 ? R3 ) = {<1, 3>}； 所以，R1 ? ( R2 ? R3 ) ? ( R1 ? R2 ) ? ( R1 ? R3 ) 。

令R2 = {<2, 2>}；R3 = {<2, 3>}；R4 = {<2, 1>, <3, 1>}；则 ( R2 ? R3 ) ? R4 = ?；( R2 ? R4 ) ? ( R3 ? R4 ) = {<2, 1>}； 所以，( R2 ? R3 ) ? R4 ? ( R2 ? R4 ) ? ( R3 ? R4 ) ； 5.

a) 正确。 b) 不正确。令A = {1, 2}，则R1 = {<1, 2>}, R2 = {<2, 1>}都是反自反的，但R1 ? R2 ={<1, 1>}

不是反自反的。

c) 不正确。令A = {1, 2, 3}，则R1 = {<1, 2>, <2, 1>}, R2 = {<2, 3>, <3, 2>}都是对称的，但

R1 ? R2 = {<1, 3>}不是对称的。

d) 不正确。令A = {1, 2, 3}，则R1 = {<1, 2>, <3, 1>}, R2 = {<2, 3>, <1, 1>}都是反对称的，

但R1 ? R2 = {<1, 3>, <3, 1>}不是反对称的。

e) 不正确。令A = {1, 2, 3}，则R1 = {<1, 2>, <3, 1>, <3, 2>}, R2 = {<2, 3>, <1, 1>}都是传递

的，但R1 ? 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。

- 14 -

第二章 二元关系

f)

则当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 。 若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)

正确； 正确； 不正确；（不自反） 不正确；（不自反） 不正确；（不一定对称） 正确。

- 15 -

第二章 二元关系

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

3. A上共有2

n2?n2个不相同的相容关系。

习题2.7

1.

a) 不正确；（不自反） b) 不正确；（不自反） c) 不正确；（不自反） d) 不正确；（不传递，< -1, 0 > ? R, < 0, 1 > ? R, 但<-1, 1> ? R） e) 不正确；（不对称） f) 不正确；（不对称） g) 不正确；（不传递） h) 正确； i) 不正确。（不自反，i = 10k时， ? R）

2. 不对。

应加上条件：对于任意x?A，总存在y?A使得 ? R。 3.

证明：

① 已知条件：若 ? R， ? R，则 ? R。

先证对称性：若 ? R，则由于R自反，所以 ? R，由上式有 ? R。 所以R对称。

再证传递性：若 ? R， ? R，则因为R对称，所以 ? R。由已知条件，因为 ? R且 ? R，所以 ? R。 所以R传递。 因此，R时等价关系。

② 已知条件：R是等价关系。 若 ? R， ? R，则因为R对称，所以 ? R。又由于R传递，所以， ?R。 因此，若 ? R， ? R，则 ? R。

习题2.8

1. a) b) c) d)

半序；

半序、全序、良序； 无；（不是反对称的） 无；（不是传递的）

- 16 -

第二章 二元关系

e) f) g) h) 4. a) b) 6. a) b) c)

半序； 无；（不是传递的） 无；（不是传递的） 拟序。

设R是集合A上的二元关系，证明：

R是A上的半序，当且仅当R ? R-1 = IIA且R = R*。 自反、反对称 ___________ _______传递 R是A上的拟序，当且仅当R ? R-1 = ? 且R = R+。 反自反 ___________ _______传递

断言中为真的有：x4Rx1, x1Rx1。 P的最小元：无；P的最大元：x1 ；

P的极小元：x4和x5；P的极大元：x1 。

{x2, x3, x4}的上界：x1；下界：x4；上确界：x1；下确界：x4。 {x3, x4, x5}的上界：x1, x3；下界：无；上确界：x3；下确界：无。 {x1, x2, x3}的上界：x1；下界：x4；上确界：x1；下确界：x4。

7. a) b) c) d) 8. 9.

< I, ? >中的非空子集I无最小元。 < I+, |>（“|”为整除关系）中的非空子集{x | x >4}无最大元。 中的非空子集(0, 1)由下确界0，但无最小元。 书上例4中的非空子集{4}有上界8和12，但无上确界。 归纳法。 归纳法。

第三章 函数

习题3.1

1. g) h) i) 2. a)

不是部分函数；原因：存在<0, 1>, <0, 2> ? f，但1 ? 2 。 部分函数；

不是部分函数。原因：存在<4, 2>, <4, -2> ? f，但2 ? -2 。

部分函数；定义域为：{1, 2, 3, 4}，值域为：{<2, 3>, <3, 4>, <1, 4>}。

- 17 -

第二章 二元关系

b) 部分函数；定义域为：{1, 2, 3}，值域为：{<2, 3>, <3, 4>, <3, 2>}。 c) 不是部分函数；

d) 部分函数。定义域为：{1, 2, 3}，值域为：{<2, 3>}。 3. 证明：

证明分两部分：① 部分函数之单值性；② dom f = ?(A) ? ?(A) 。

5.

e) 证明：

对于任意y ? f [A] – f [B]，则y ? f [A] 且 y ? f [B] 。 因为y ? f [A] ，所以存在x ? A 使得 f (x) = y 。 又因为y ? f [B]，所以x ? B。（用反证法，假设x ? B，则f (x) ? f [B]，而y = f (x)，所以y ? f [B]。矛盾）

所以，x ? A - B 。因此，y = f (x) ? f [A-B]。 于是，f [A-B] ? f [A] – f [B]。

“=”不能代替“?”的反例，

令X = { x1, x2 }，Y = { y }，f = { , }。 A = { x1, x2 }，B = { x1 }。

则f [A-B] = {y}，而f [A] – f [B] = ?。 6.

e) f = { <<-1, -1>, 0>, <<-1, 0>, -1>, <<-1, 1>, -2>, <<0, -1>, 1>, <<0, 0>, 0>, <<0, 1>, -1>,

<<1, -1>, 2>, <<1, 0>, 1>, <<1, 1>, 0> }； f) ran f = {-2, -1, 0, 1, 2}；

g) f ?{0, 1}2 = { <<0, 0>, 0>, <<0, 1>, -1>, <<1, 0>, 1>, <<1, 1>, 0> }； h) 参见下题。 7.

a) ① m ? n，Pnm?n !个；② m > n，0个。

(n?m) !b) ① m < n，0个；② n = 0且m ? 0，0个；③ n = 0且m = 0，1个；

1n?1k④ m ? n ? 1，第二类Stirling数?(?1)kCn(n?k)m。

n !k?0 8.

a) 证明：f (99) = f ( f (110) ) = f (100) = f ( f (111) ) = f (101) = 91。 b) 证明：

① f (100) = f (99) = 91；

② ? i ? {1, 2, …, 9}，f (89 + i) = f (90 + i)，所以f (89) = f (90) = … = f (99) = 91。 f (89 + i) = f ( f (89 + i + 11) ) = f (90 + i)。

- 18 -

第二章 二元关系

③ 假设当k+1 ? x ? 100时，f (x)均等于91。(0 ? k ? 89)

则当x = k ( k ? 0 ) 时，则有 f (k) = f ( f (k+11) )。

而0 ? k ? 89，所以 k+1 ? k+11 ? 100，由归纳假设有f (k+11) = 91，即f (k) = f (91) = 91。

所以，f (x) = 91对于0 ? k ? 89也成立。

习题3.2

4. 归纳法。 5. 证明：

① 因为f : A?A为满射，所以? a ? A . ? xa ? A使得f ( xa ) = a。

又因为f ? f = f，所以f (a) = f ( f ( xa ) ) = f ? f ( xa ) = f ( xa ) = a ，即 f (a) = a。 所以 II A ? f 。 ② 对于任意 ? f ，因为II A ? f ，所以 ? f 。 而f为部分函数，即“单值”，于是，x = y 。 所以 = ? II A 。 所以f ? II A 。 ② 另证

下面要证明II A ? f不可能。用反证法，假设II A ? f，则 存在a? ? a使得f (a?) = a。 因为f为满射，所以必存在x a? ? A使得f (x a?) = a?。

因为f ? f = f，所以a? = f (x a?) = f ? f (x a?) = f ( f (x a?) ) = f (a? ) = a ，即 a? = a。 这与a? ? a矛盾。

所以假设不成立，即II A ? f不可能。 由①②可知II A = f 。 6.

证明：首先，dom (g ? f ) = f -1 [dom g]。 因为ran f ? dom g ，所以dom f = f –1 [ ran f ] ? f –1 [ dom g ]。

又因为dom g ? Y，而f -1 [Y] = domg f，所以f –1 [ dom g ] ? f –1 [ Y ] = dom f。 所以，dom (g ? f ) = dom f 。 8.

a) 因为f ? f = f ，所以对于任意i ? A，均有f (f (i) ) = f (i) 。即若f (i) = j ( j ? i )，则f (j) =

i。设m为集合{ i | i ? A且f (i) = i }的元素个数，即m为f中对应到自身的二元序偶个

数。则对m求累加和得到满足f ? f = f的函数个数为

?Cm?1nmnmn?m个。

b) f ? f = II A，所以f为双射，并且对于任意i ? A，均有f (f (i) ) = i（即若?f且i?j，

则?f ）。（特征：未对应到自身的二元序偶个数必为偶数个。）设k为集合{ i | i ? A

- 19 -

第二章 二元关系

且f (i) = i }的元素个数/2，即2k为f中对应到自身的二元序偶个数。则对k求累加和得到满足f ? f = II A的函数个数： 当n为偶数时，有

?Ck?0n/22kn?(n?2k?1)?(n?2k?3)???1个；

(n?1)/2当n为奇数时，有

?Ck?02k?1n?(n?2k?2)?(n?2k?4)???1个。

c) f ? f ? f = II A ，所以f为双射，因此满足f ? f ? f = II A的函数个数：

(n?1)/3当n = 3k+1 ( k ? N ) 时，有个；

?Ck?03k?1n?((n?3k?2)?(n?3k?3)?1)???(2?1?1)(n?2)/3当n = 3k+2 ( k ? N ) 时，有个；

当n = 3k ( k ? N ) 时，有

?Ck?03kn3k?2n?((n?3k?3)?(n?3k?4)?1)???(2?1?1)?Ck?0n/3?((n?3k?1)?(n?3k?2)?1)???(2?1?1)个。

9.

a) 证明：因为g ? f 为满射，所以g为满射。而g又是内射，所以g为双射。

假设f不是满射，则存在y ? Y使得 y ? ran f。 而g是双射，所以g (y) ? Z，又g ? f 为满射，所以ran (g ? f ) = Z。即g (y) ? ran (g ? f )。 所以存在x ? X使得 g (y) = g ? f (x) = g ( f (x) )。

因为g为内射，所以y = f (x)。因此，y ? ran f。这与y ? ran f矛盾。 所以假设不成立，即f 是满射。

b) 证明：因为g ? f 为内射，所以f为内射。而f又是满射，所以f为双射。

假设g不是内射，则存在y1, y2 ? Y使得 y1 ? y2并且 g (y1) = g (y2) 。

因为f为双射，所以存在x1, x2 ? X使得 x1 ? x2并且 f (x1) = y1，f (x2) = y2 。 而g ? f 为内射，则 g ? f (x1) ? g ? f (x2) ，即 g (y1) ? g (y2)。 这与g (y1) = g (y2)矛盾。

所以假设不成立，即g 是内射。

- 20 -

第二章 二元关系

习题3.3

3.

a) k (x) = ? x / 3 ? ； b) k (x) = ? (x+1) / 3 ? ； c)

4. f左可逆，但g不一定左可逆。

证明：因为g ? f左可逆，则g ? f为内射，所以f为内射。 g不一定左可逆，反例如下： A = {a}， B = {b1, b2}， C = {c}。 f = {}，g = {, }，g ? f = {}。 所以，g ? f是内射，即是左可逆的；但g不是内射，即不是左可逆的。 5.

证明：f是可逆的，则易证f又唯一的左（右）逆。 另一边证明以“f有唯一左逆，则f可逆。”为例。 ?a ? A，g = f-1 ? (( Y – ran f ) ? {a})就是f的一个左逆。

而f仅有唯一左逆且n(A)?2 ，这说明Y – ran f = ?，即ran f = Y。 所以，f为满射。又因为f左可逆，所以f为内射。 即f为双射。所以f可逆。

习题3.4

2. a) b) c) d)

A ? B ? C = ? ； A = B； B = ?； A = B。

习题3.5

1.

b)

1?0 x ? ?2?1?1f(x)??()n?1 x ? ()n (n?2)

2?2其它 ?x ??- 21 -

第二章 二元关系

1?0 x ? ?2?1?1 x ? (n?2) 或 f(x)??n?n?1其它 ?x ??

c) f (x) = 1/2 – x/4 或 f (x) = 1/2 cos(?x/3)。 2.

证明：若存在1 ? k? ? n使得x1 + … + xk? 被n整除，则取i = 1, k = k? 即可。

否则，x1 , x1 + x2 , … , x1 + … + xn共n个数，而它们被n除的余数除0外仅有n-1个。 根据抽屉原则，其中必有两个它们被n除的余数相等。假设它们为：（j1 < j2） x1 + … + xj1和x1 + … + xj2 则取i = j1+1, k = j2 即可。 4.

?1??3??5??2n?1??共有n组数据。任取n+1个小于等于2n正整数中必有证明：?? ?? ?? ... ??2??4??6??2n?????????两个数处于同一组，这两个数互素。

6.

证明：一个整数被100除的余数共有100个，可以将它们分成51组

?0??1??2??50??? ?? ?? ... ??。任取52个整数中必有两个数除100后余数同处于一组。这?0??99??98??50?????????是有两种情况：一是它们除100后余数相同，此时两个数相减即可；一是它们除100后余数不同，此时两个数相加即可。 8.

a) # ?* = ?0。

其中双射为：f ( ai) = i 。 b) # Q = ?0。

正有理数a = m / n，m>0, n>0并且m和n互质，则： Q+ ~ N?N ~ N。所以 # Q+ = ?0。

# Q = 2 ? #Q+ + 1 = 1 + ?0 + ?0 = ?0。 c) ?0。

10. f({n0,n1,...,nk})?2

n0?2n1???2nk。

- 22 -

第二章 二元关系

第四章 命题逻辑

习题4.1

1. 题号 a) 2.

b) c) d) e) f) g)

是否为命题 ? ? ? ? ? ? ?

命题的真值 （没有确定的真假） F T T F

（祈使句） （疑问句）

c) ?P?R?Q d) Q?R e) ?P

f) Q R??P （需考虑优先级）

3. （答案不止一种，只要真值表相同即可） a) ?P : P?P P?Q : (P?Q)?(P?Q)即?(P?Q) P?Q : (P?P)?(Q?Q)

P?Q : P?(Q?Q) P Q : (P?Q)?((P?P)?(Q?Q))或(P?(Q?Q))?(Q?(P?P)) b) ?P : P?P P?Q : (P?Q)?(P?Q)即?(P?Q) P?Q : (P?P)?(Q?Q) ?和 参考c)或d)定义 c) P?Q : ?(?P??Q) P?Q : ?P?Q

P Q : ?(P?Q)??(?P??Q) d) P?Q : ?(?P??Q) P?Q : ?(P??Q)

P Q : ?(P??Q) ?? (Q??P) e) P?Q : ?P?Q 其它参考c)

f) 证明：要证明用?、?、?、 不能表示?，只需证明仅用?、?、?、 不能表达出含?的某些公式即可。

因为P?P?P；P?P?P；P?P?T；P P ?T。

增加T之后，T?P?P?T?P；P?T ? T?P?T；T?P?P；P?T?T； T P ? P T ?P。 这也就是说，由?、?、?、 只能得出P或T，不能得出?P。

习题4.2

1. a) T b) T 2. 以e)为例

c) T

d) F

e) F

f) T

- 23 -

第二章 二元关系

P F F T T 3. c) d) 4. 5.

Q F T F T P ? ? Q ? ? P ? ? Q F F T F T T F T T F F F F T T T F T F T T T T F T F T T T F T F F T T F T F F T 解释以P、Q、R的顺序排列，则为真的解释如下所示： (F F T)、(F T T)、(T F T)、(T T T) (F F F)、(F T F) a) 是永真的 b) 是永真的 c) 是永真的 d) 是可满足的 e) 是可满足的 f) 是可满足的 g) 是永真的 h) 是永真的 i) 是永假的 j) 是永假的

a) (((P?Q)?((P?Q)?R))?(P?Q))?(P?Q) （有的括号可省略） b) (Q?(P??P))?((P??P)?Q) （有的括号可省略） 6. c)是a)的代换实例（ Q/P，(P?P)/Q ） d)是a)的代换实例（ (P?(Q?P))/Q ） e)是b)的代换实例（ R/P，S/Q，Q/R，P/S ） b)是e)的代换实例（ S/P，R/Q，P/R，Q/S ）

习题4.3

1. 以a)为例：

a) P?(Q?P) ?P?(P?Q)的真值表如下：

P F F T T Q F T F T P ? (Q ? P) ? P ? (P ? Q) F T F T F T T F T F T F F T T F F T T F T F T T T T F T T T F T T T F F T T T T T T F T T T T T 上述真值表说明P?(Q?P) ?P?(P?Q)为永真式。 所以，P?(Q?P) ? ?P?(P?Q)。 2. a)

? ? ? ? ? ? ? ?

?(?P??Q)?? (?P?Q) (??P???Q) ?? (?P?Q) (P???Q) ?? (?P?Q) (P?Q) ?? (?P?Q) (P?Q) ? (??P??Q) (P?Q) ? (P??Q) P? (Q ? ?Q) P?T P

- 24 -

第二章 二元关系

所以，?(?P??Q)?? (?P?Q) ? P 。

根据对偶原理得出的新的等价式为：

?(?P??Q) ?? (?P?Q) ? P 。

b) (P??Q) ? (P?Q) ? (?P??Q)

? (P? (?Q ? Q )) ? (?P??Q) ? (P? F) ? (?P??Q) ? P ? (?P??Q) ? (P ? ?P ) ? ( P ? ?Q ) ? F ? ( P ? ?Q ) ? ( P ? ?Q ) ? (??P? ?Q) ? ? (?P ? Q ) 所以，(P??Q) ? (P?Q) ? (?P??Q) ? ? (?P?Q) 。 根据对偶原理得出的新的等价式为：

(P??Q) ? (P?Q) ? (?P??Q) ? ? (?P?Q) 4. a)

P?Q

? Q （I2） ? P?Q （I6）

c)

P?Q

? P?P? P?Q （I9） ? P? P?Q （I1）

e) (P??P?Q)?(P??P?R)

? (T?Q)?(P??P?R) （E23） ? (T?Q)?(T?R) （E23） ? (?F?Q)?(T?R) （E16） ? (?F?Q)?(?F?R) （E16） ? (T?Q)?( ?F?R) ? (T?Q)?( T ? R) ? (Q?T)?( R ? T) （E3） ? Q? R （E14）

上述均为等价变换，所以蕴含式也成立。 5. 以b)为例： b) P? (?Q?R?P) ? P? (?(?Q?R) ? P) ? P? ((??Q??R) ? P) ? P? ((Q??R) ? P) ? P? (P ? (Q??R))

? (P? P) ? (Q??R) ? P? Q ? ?R

? ?(?P? ?Q ? R)

?(?P? ?Q ? R)为P? (?Q?R?P)只包含?和?的化简式。- 25 -

。

第二章 二元关系

- 26 -

第二章 二元关系

习题4.4

1.

e) ?P??Q?(P ?Q)

? ?P??Q?((P??Q) ? (?P???Q)) （化去 ） ? ?(?P??Q) ? ((P??Q) ? (?P???Q)) （化去?） ? (??P???Q) ? ((P??Q) ? (?P???Q)) （?内移） ? (P?Q) ? ((P??Q) ? (?P?Q)) （最多保留一个?） ? (P?Q) ? (P??Q) ? (?P?Q)

(P?Q) ? (P??Q) ? (?P?Q)为?P??Q?(P ?Q)的主合取范式。

(P?Q) ? (P??Q) ? (?P?Q) ? (P? (Q ? ?Q)) ? (?P?Q) ? (P? T) ? (?P?Q) ? P ? (?P?Q)

? (P ? ?P) ? (P ?Q) ? T? (P ?Q) ? P ? Q

P? Q为?P??Q? (P ?Q)的主合取范式。

(P?Q?R) ? (?P??Q??R)

(?P? (Q?R)) ? (??P? (?Q??R)) （化去?） (?P? (Q?R)) ? (P? (?Q??R)) （最多保留一个?） (?P? Q) ? (?P?R) ? (P? ?Q ) ? (P??R) （?关于?的分配率）

g)

? ? ?

? (?P? Q ? R) ? (?P? Q ? ?R) ? (?P? Q ? R) ? (?P??Q?R) ? (P??Q??R) ?

(P??Q?R) ? (P? Q ??R) ? (P? ?Q ??R) （变为极大项）

? (?P? Q ? R) ? (?P? Q ? ?R) ? (?P??Q?R) ? (P??Q??R) ? (P??Q?R) ? (P? Q

??R) （合并相同项）

(?P? Q ? R) ? (?P? Q ? ?R) ? (?P??Q?R) ? (P??Q??R) ? (P??Q?R) ? (P? Q ??R)为(P?Q?R) ? (?P??Q??R)的主合取范式。

(P?Q?R) ? (?P??Q??R)

? (?P? (Q?R)) ? (??P? (?Q??R)) （化去?） ? (?P? (Q?R)) ? (P? (?Q??R)) （最多保留一个?） ? (?P? P) ? (?P??Q??R) ? (Q?R?P) ? (Q?R??Q??R) （?关于?的分配率） ? F ? (?P??Q??R) ? (Q?R?P) ? F （化简） ? (?P??Q??R) ? (Q?R?P) （化简） (?P??Q??R) ? (Q?R?P)为(P?Q?R) ? (?P??Q??R)的主析取范式。

2. a)

? ? ?

(P?Q) ? (P?R) (?P? Q) ? (?P? R)

(?P? Q? R) ? (?P? Q? ?R) ? (?P? Q? R) ? (?P? ?Q? R) (?P? Q? R) ? (?P? Q? ?R) ? (?P? ?Q? R)

- 27 -

第二章 二元关系

P? Q? R ? ?P? (Q ? R)

? (?P? Q) ? (?P? R)

? (?P? Q? R) ? (?P? Q? ?R) ? (?P? ?Q? R)

所以，(P?Q) ? (P?R) ? P? Q? R 。 c)

? ? ?

P?Q?(?P??Q)

(P?Q??P)? (P?Q??Q) F?F F

?P??Q? (P?Q)

? (?P??Q?P)? (?P??Q?Q) ? F?F ? F

所以，P?Q?(?P??Q) ? ?P??Q? (P?Q) 。

3. 合式公式P既是主合取范式，又是主析取范式。

4. 求wff A的主析取范式的算法：

i) 利用E16和E22删去?和 在A中的所有出现，得到A1；

ii) 利用德?摩尔根律将A1中的?内移到原子之前，并用E1使每个原子之前至多仅有

一个?；

iii) 在用分配律将ii) 的结果化为若干个合取式的析取，其中每个合取式的因子皆为原

子或原子的否定；

iv) 对于iii) 的结果中的每个合取式B，若命题变元P在B中不出现，利用 (B?P) ? (B??P) ( ? B?(P??P) ? B?T ? B)

取代B，直到每个合取式都变为极小项，最后删除相同项。

第五章 谓词逻辑

习题5.1

1.

a) 每个自然数都有唯一的后继； 解：“每个”是全称的概念；“自然数”需引进一个特性谓词；“有”表示存在；“唯一”表示所有具有该性质的元素均相等（即若x具有该性质，y也具有该性质，则x等于y）；“后继”

- 28 -

第二章 二元关系

用谓词表示。于是，可令： N(x)：x是自然数； Q(x, y)：y是x的后继； E(x, y)：x等于y； 则上述命题可以符号化为：

(? x) ( N ( x ) ? (? y) (Q ( x, y ) ? (? z) (Q ( x, z ) ? E ( y, z ) )

b) 没有以0为后继的自然数； 解：“没有”表示不存在；“自然数”用特性谓词表示；“后继”用谓词表示。于是，可令： N(x)：x是自然数； Q(x, y)：y是x的后继； 则上述命题可以符号化为：

? (? x)( N ( x ) ? Q ( x, 0 ) )

注意：① 对于引进的特性谓词，在全称量词约束下要用逻辑联结词“?”，在存在量词约束

下要用逻辑联结词“?”。 ② “唯一”概念的符号化。 2.

g) 存在唯一的偶素数； 解：“存在”是存在量词的概念；“唯一”可参照上题；“偶数”、“素数”用谓词表示。于是，可令： E(x)：x是偶数； S(x)：x是素数； R(x, y)：x等于y； 则上述命题可以符号化为：

(? x) ( E ( x ) ? S ( x ) ? (? y) ( E ( y ) ? S ( y ) ? R ( x, y ) )

h) 没有既是奇数又是偶数的数； 解：“没有”表示不存在；“奇数”、“偶数”、“数”用谓词表示。于是，可令： O(x)：x是奇数； E(x)：x是偶数； Q(x)：x是数； 则上述命题可以符号化为：

? (? x) ( Q ( x ) ? O ( x ) ? E ( x ) )

3.

a) 所有可证明的算术命题都是真的； b) 存在真的但不可证明的算术命题；

c) 对于任意的三个算术命题x, y, z ，若z = x ? y且z是可证明的，则x是可证明的或y是可证明的；

d) 对于任意的三个算术命题x, y, z ，若x是真的并且z = x ? y，则z是真的； 4.

- 29 -

第二章 二元关系

a) 对任意整数x, y和z，x < z是x < y且y < z的必要条件； 解：“任意”是全称的概念；“整数”需引进一个特性谓词；“<”用谓词表示；“必要条件”用逻辑联结词来表示。于是，可令： I(x)：x是整数； L(x, y)：x < y； 则上述命题可以符号化为：

(? x) (? y) (? z) ( I ( x ) ? I ( y ) ? I ( z ) ? ( L ( x, y ) ? L ( y, z ) ? L ( x, z ) ) )

b) 对任意整数x，若x = 2，则3? x = 6；反之亦然； 解：“任意”是全称的概念；“整数”需引进一个特性谓词；“=”用谓词表示；“? ”用函词表示。于是，可令：（2、3、6可以用常元表示） I(x)：x是整数； E(x, y)：x = y； f(x, y)：x? y； 则上述命题可以符号化为：

(? x) ( I ( x ) ? ( E ( x, 2 ) ? E ( f(3, x), 6 ) ) ? ( E ( f(3, x), 6 ) ? E ( x, 2 ) ) ) 或 (? x) ( I ( x ) ? ( E ( x, 2 ) E ( f(3, x), 6 ) ) )

习题5.2

1.

b) 除了最后一个x是自由出现外，其它的6次x的出现都是约束出现。 第一个(? x) 的辖域为下面的划线部分：

(? x) ( P ( x ) ? ( ? x ) Q ( x ) ) ? ( (? x) P ( x ) ? Q ( x ) ) 第一个( ? x ) 的辖域为下面的划线部分：

(? x) ( P ( x ) ? ( ? x ) Q ( x ) ) ? ( (? x) P ( x ) ? Q ( x ) ) 第二个(? x) 的辖域为下面的划线部分：

(? x) ( P ( x ) ? ( ? x ) Q ( x ) ) ? ( (? x) P ( x ) ? Q ( x ) )

2. a) T ； b) F ；c) F ；d) T ；e) T ；f) T 。 以a)为例：

解：因为 P ( a , a ) 为T，所以 ( ? y ) P ( a , y ) 为T；

因为 P ( b , b ) 为T，所以 ( ? y ) P ( b , y ) 为T；

因为( ? y ) P ( a , y ) 和 ( ? y ) P ( b , y ) 均为T，所以 ( ? x ) ( ? y ) P ( x , y ) 也为T。

3. a) F ； b) T ；c) F。

4. a) T ； b) F ；c) T。

习题5.3

- 30 -

第二章 二元关系

1.

a) (? x ) ( P ( x ) ? Q ( x ) ) ? ( (? x ) P ( x ) ? (? x ) Q ( x ) ) 为永真式。 证明：给定 (? x ) ( P ( x ) ? Q ( x ) ) ? ( (? x ) P ( x ) ? (? x ) Q ( x ) ) 在论域D上的任意解释I，如果 (? x ) P ( x ) ? ( ? x ) Q ( x ) 在I 下为假，则

(? x ) P ( x ) 在I 下为真， 并且 (? x ) Q ( x ) 在I 下为假。

因为 (? x ) Q ( x ) 在I 下为假，所以存在c ? D使Q ( c ) 在I 下为假。 因为 (? x ) P ( x ) 在I 下为真，所以 P ( c ) 在I 下为真。 因此，P ( c ) ? Q ( c ) 在I 下为假。

所以，(? x ) ( P ( x ) ? Q ( x ) ) 在I 下为假。

于是，(? x ) ( P ( x ) ? Q ( x ) ) ? ( (? x ) P ( x ) ? (? x ) Q ( x ) ) 为永真式。

b) ( (? x ) P ( x ) ? (? x )Q ( x ) ) ? (? x ) ( P ( x ) ? Q ( x ) ) 不是永真式。 解：取上述合式公式的解释I 如下：

i) 论域D = {a, b}；

ii) P ( a ) P ( b ) Q ( a ) Q ( b )

_______ ________ _______ _______ F T F F

则(? x ) ( P ( x ) ? Q ( x ) ) 在I 下为假，( (? x ) P ( x ) ? (? x )Q ( x ) ) 在I 下为真。

所以，( (? x ) P ( x ) ? (? x )Q ( x ) ) ? (? x ) ( P ( x ) ? Q ( x ) ) 在I 下为假。

c) ( ( ? x ) P ( x ) ? (? x ) Q ( x ) ) ? (? x ) ( P ( x ) ? Q ( x ) ) 为永真式。 证明：给定 ( ( ? x ) P ( x ) ? (? x ) Q ( x ) ) ? (? x ) ( P ( x ) ? Q ( x ) ) 在论域D上的任意解释I，如果 (? x ) ( P ( x ) ? Q ( x ) ) 在I 下为假，则 存在c ? D使 P ( c ) ? Q ( c ) 在I 下为假。即 P ( c ) 在I 下为真 并且Q ( c ) 在I 下为假。 因为P ( c ) 在I 下为真，所以 ( ? x ) P ( x ) 在I 下为真。 因为Q ( c ) 在I 下为假，所以 (? x ) Q ( x ) 在I 下为假。 所以，( ? x ) P ( x ) ? (? x ) Q ( x ) 在I 下为假。

于是，( ( ? x ) P ( x ) ? (? x ) Q ( x ) ) ? (? x ) ( P ( x ) ? Q ( x ) ) 为永真式。

d) (? x ) ( P ( x ) ? Q ( x ) ) ? ( ( ? x ) P ( x ) ? (? x ) Q ( x ) ) 不是永真式。 解：取上述合式公式的解释I 如下：

i) 论域D = {a, b}；

ii) P ( a ) P ( b ) Q ( a ) Q ( b )

_______ ________ _______ _______ F T F T

则(? x ) ( P ( x ) ? Q ( x ) ) 在I 下为真，( ( ? x ) P ( x ) ? (? x ) Q ( x ) ) 在I 下为假。

所以，(? x ) ( P ( x ) ? Q ( x ) ) ? ( ( ? x ) P ( x ) ? (? x ) Q ( x ) ) 在I 下为假。 2.

??????

d)

(? x ) (? y ) ( P ( x ) ? Q ( y ) )

- 31 -

第二章 二元关系

? (? x ) ( P ( x ) ? (? y ) Q ( y ) ) （因为y在P ( x )中没有自由出现） ? (? x ) P ( x ) ? (? y ) Q ( y ) （因为x在 (? y ) Q ( y ) 中没有自由出现）

所以，(? x ) (? y ) ( P ( x ) ? Q ( y ) ) ? (? x ) P ( x ) ? (? y ) Q ( y )。 e)

(? x ) (? y ) ( P ( x ) ? Q ( y ) ) ? (? x ) ( P ( x ) ? (? y ) Q ( y ) ) ? (? x ) P ( x ) ? (? y ) Q ( y ) ? (? x ) P ( x )

（因为y在P ( x )中没有自由出现）

（因为x在 (? y ) Q ( y ) 中没有自由出现）

f)

所以，(? x ) (? y ) ( P ( x ) ? Q ( y ) ) ? (? x ) P ( x ) 。

(? x ) (? y ) ( P ( x ) ? Q ( y ) )

? (? x ) ( P ( x ) ? (? y ) Q ( y ) ) （因为y在P ( x )中没有自由出现）

? (? x ) P ( x ) ? (? y ) Q ( y ) （因为x在 (? y ) Q ( y ) 中没有自由出现）

所以，(? x ) (? y ) ( P ( x ) ? Q ( y ) ) ? (? x ) P ( x ) ? (? y ) Q ( y ) 。 ? ? ? ? ?

(? x ) (? y ) ( P ( x ) ? Q ( y ) ) (? x ) (? y ) ( ? P ( x ) ? Q ( y ) )

(? x ) (? P ( x ) ? (? y ) Q ( y ) ) （因为y在? P ( x )中没有自由出现）

(? x ) (? P ( x ) ) ? (? y ) Q ( y ) （因为x在 (? y ) Q ( y ) 中没有自由出现） ? (? x ) P ( x ) ? (? y ) Q ( y ) (? x ) P ( x ) ? (? y ) Q ( y )

g)

h)

所以，(? x ) (? y ) ( P ( x ) ? Q ( y ) ) ? (? x ) P ( x ) ? (? y ) Q ( y ) 。

(? x ) (? y ) ( P ( x ) ? Q ( y ) ) (? x ) (? y ) ( ? P ( x ) ? Q ( y ) )

(? x ) (? P ( x ) ? (? y ) Q ( y ) ) （因为y在? P ( x )中没有自由出现）

(? x ) (? P ( x ) ) ? (? y ) Q ( y ) （因为x在 (? y ) Q ( y ) 中没有自由出现） ? (? x ) P ( x ) ? (? y ) Q ( y ) (? x ) P ( x ) ? (? y ) Q ( y )

? ? ? ? ?

所以，(? x ) (? y ) ( P ( x ) ? Q ( y ) ) ? (? x ) P ( x ) ? (? y ) Q ( y ) 。 3. 解： ? ( ? x ) (? P ( x ) ? ? Q ( x ) )

? ? ( ( ? x ) (? P ( x ) ) ? ( ? x ) ( ? Q ( x ) ) ) ____ 上述这一步不正确。 根据书中105页I 16：

( ? x ) (? P ( x ) ? ? Q ( x ) ) ? ( ? x ) (? P ( x ) ) ? ( ? x ) ( ? Q ( x ) )

可知：

- 32 -

第二章 二元关系

? ( ? x ) (? P ( x ) ? ? Q ( x ) ) ? ? ( ( ? x ) (? P ( x ) ) ? ( ? x ) ( ? Q ( x ) ) )

因此，最后应该证明出： ( ? x ) ( P ( x ) ? Q ( x ) ) ? ( ? x ) P ( x ) ? ( ? x ) Q ( x ) ) 这就是书中的I 15。

习题5.4

1.

a) (? y ) (? z ) ( P ( z, y ) ? (? x ) ( P ( z, x ) ? P ( x, z ) ) )

? (? y ) (? z ) ( ( P ( z, y ) ? ? (? x ) ( P ( z, x ) ? P ( x, z ) ) )

? (? P ( z, y ) ? ? ? (? x ) ( P ( z, x ) ? P ( x, z ) ) ) ) （化去 ）

? (? y ) (? z ) ( ( P ( z, y ) ? (? x ) (? P ( z, x ) ? ? P ( x, z ) ) ) ? (? P ( z, y ) ? (? x ) ( P ( z, x ) ? P ( x, z ) ) ) ) （? 内移）

? (? y ) (? z ) ( (? x ) ( P ( z, y ) ? (? P ( z, x ) ? ? P ( x, z ) ) )

? (? x ) (? P ( z, y ) ? ( P ( z, x ) ? P ( x, z ) ) ) ) （?、?前移）

? (? y ) (? z ) ( (? x ) ( P ( z, y ) ? (? P ( z, x ) ? ? P ( x, z ) ) )

? (? u ) (? P ( z, y ) ? ( P ( z, u ) ? P ( u, z ) ) ) ) （换名）

? (? y ) (? z ) (? x ) (? u ) ( ( P ( z, y ) ? (? P ( z, x ) ? ? P ( x, z ) ) )

? (? P ( z, y ) ? ( P ( z, u ) ? P ( u, z ) ) ) ) （?、?前移）

上述公式即为原公式的前束范式。

令f为二元函词，则原公式的无?前束范式为：

(? z ) (? x ) ( ( P ( z, a ) ? (? P ( z, x ) ? ? P ( x, z ) ) ) ?

(? P ( z, a ) ? ( P ( z, f ( z, x ) ) ? P ( f ( z, x ), z ) ) ) ) b)

? (? x ) (? y ) (? z ) ( ( P ( x, y ) ? P ( y, z ) ? P ( z, z ) ) ?

( P ( x, y ) ? Q ( x, y ) ? Q ( x, z ) ? Q ( z, z ) ) )

? ? (? x ) (? y ) (? z ) ( (? P ( x, y ) ? ( P ( y, z ) ? P ( z, z ) ) ) ?

(? ( P ( x, y ) ? Q ( x, y ) ) ? (Q ( x, z ) ? Q ( z, z ) ) ) ) （化去?）

? (? x ) (? y ) (? z ) ( ( P ( x, y ) ? (? P ( y, z ) ? ? P ( z, z ) ) ) ?

( ( P ( x, y ) ? Q ( x, y ) ) ? (? Q ( x, z ) ? ? Q ( z, z ) ) ) ) （? 内移）

上述公式即为原公式的前束范式。

令g为二元函词，则原公式的无?前束范式为：

(? x ) (? y ) ( ( P ( x, y ) ? (? P ( y, g ( x, y ) ) ? ? P ( g ( x, y ), g ( x, y ) ) ) ) ?

( ( P ( x, y ) ? Q ( x, y ) ) ? (? Q ( x, g ( x, y ) ) ? ? Q ( g ( x, y ), g ( x, y ) ) ) ) )

2. 令原公式为X，则

? X

? (? x ) (? y ) (? P ( x, y ) ? P ( y, x ) ) ? (? x ) (? y ) (? z ) (? P ( x, y ) ? ? P ( y, z ) ?

P ( x, z ) ) ? (? x ) (? y ) P ( x, y ) ? (? x ) (? P ( x, x ) ) （? 内移） ? (? x ) (? y ) (? z ) ( (? P ( x, y ) ? P ( y, x ) ) ? (? P ( x, y ) ? ? P ( y, z ) ? P ( x, z ) ) )

? (? x ) (? y ) P ( x, y ) ? (? x ) (? P ( x, x ) ) （?前移） ? (? x ) (? y ) (? z ) ( (? P ( x, y ) ? P ( y, x ) ) ? (? P ( x, y ) ? ? P ( y, z ) ? P ( x, z ) ) ) ? (? x ) (? u ) P ( x, u ) ? (? v ) (? P ( v, v ) ) （换名）

- 33 -

第二章 二元关系

? (? v ) ( (? x ) (? y ) (? z ) ( (? P ( x, y ) ? P ( y, x ) ) ? (? P ( x, y ) ? ? P ( y, z ) ? P

( x, z ) ) ) ? (? x ) (? u ) P ( x, u ) ? ? P ( v, v ) ) （?前移） ? (? v ) (? x ) ( (? y ) (? z ) ( (? P ( x, y ) ? P ( y, x ) ) ? (? P ( x, y ) ? ? P ( y, z ) ? P

( x, z ) ) ) ? (? u ) P ( x, u ) ? ? P ( v, v ) ) （?前移）

? (? v ) (? x ) (? u ) ( (? y ) (? z ) ( (? P ( x, y ) ? P ( y, x ) ) ? (? P ( x, y ) ? ? P ( y, z ) ?

P ( x, z ) ) ) ? P ( x, u ) ? ? P ( v, v ) ) （?前移） ? (? v ) (? x ) (? u ) (? y ) (? z ) ( (? P ( x, y ) ? P ( y, x ) ) ? (? P ( x, y ) ? ? P ( y, z ) ? P ( x, z ) ) ? P ( x, u ) ? ? P ( v, v ) ) （?前移） 上述公式即为原公式的前束范式。

令f为一元函词，则原公式的无?前束范式为：

(? x ) (? y ) (? z ) ( (? P ( x, y ) ? P ( y, x ) ) ? (? P ( x, y ) ? ? P ( y, z ) ? P ( x, z ) ) ?

P ( x, f ( x ) ) ? ? P ( a, a ) )

所以，H = { a, f (a), f ( f (a) ), ? } 若将? X的无?前束范式看成(? x ) (? y ) (? z ) B( x, y, z )，则B( a, f(a), a )为永假式。根据艾尔布朗定理可知上述原公式的无?前束范式为永假式，即? X为永假式。所以，X为永真式。

B( a, f(a), a ) 为

(? P ( a, f ( a ) ) ? P ( f ( a ), a ) ) ? (? P ( a, f ( a ) ) ? ? P ( f ( a ), a ) ? P ( a, a ) ) ? P ( a, f ( a ) ) ? ? P ( a, a )

? P ( f ( a ), a ) ? ( ? P ( f ( a ), a ) ? P ( a, a ) ) ? P ( a, f ( a ) ) ? ? P ( a, a ) ? P ( a, a ) ? P ( a, f ( a ) ) ? ? P ( a, a ) ? F

第六章 自然推理系统

习题6.1

1. 不用导出规则证明 b) ?— (A? (B?C)) (B?(A?C)) 证明：

1. A? (B?C), B, A ?— A 2. A? (B?C), B, A ?— A? (B?C) 3. A? (B?C), B, A ?— B?C 4. A? (B?C), B, A ?— B 5. A? (B?C), B, A ?— C 6. A? (B?C), B ?— A?C 7. A? (B?C) ?— B? (A?C)

- 34 -

(?) (?)

(?-) (1, 2) (?)

(?-) (3, 4) (?+) (5) (?+) (6)

第二章 二元关系

8. B? (A?C) ?— A? (B?C) 9. ?— (A? (B?C)) (B?(A?C))

c) (A? B) ? C ?—? A ? (B?C) 证明：先证 (A? B) ? C?— A ? (B?C)

1. A ?— A 2. A ?— A ? (B?C) 3. B ?— B 4. B ?— B?C 同理可证 ( +) (7, 8)

(?) (?+) (1) (?) (?+) (3) 5. B ?— A ? (B?C) 6. A? B ?— A ? (B?C) 7. C ?— C 8. C ?— B?C 9. C ?— A ? (B?C) 10. (A? B) ? C ?— A ? (B?C)

A ? (B?C) ?— (A? B) ? C 证明类似

所以，(A? B) ? C ?—? A ? (B?C) d) ?— (A?B) (?B??A) 证明：

1. A?B, ?B, A ?— A 2. A?B, ?B, A ?— A?B 3. A?B, ?B, A ?— B 4. A?B, ?B, A ?— ?B 5. A?B, ?B ?— ?A 6. A?B ?— ?B??A

7. ?B ??A, A, ?B ?— ?B 8. ?B ??A, A, ?B ?— ?B ??A 9. ?B ??A, A, ?B ?— ?A 10. ?B ??A, A, ?B ?— A 11. ?B ??A, A ?— ??B 12. ?B ??A, A ?— B 13. ?B ??A ?— A?B 14. ?— (A?B) (?B??A)

e) A ? ?A ?—? F

证明：先证A ? ?A

?— F

1. A ? ?A ?— A ? ?A 2. A ? ?A ?— A 3. A ? ?A ?— ?A 4. A ? ?A

?— F

(?+) (4) (?-) (2, 5) (?) (?+) (7) (?+) (8) (?-) (6, 9)

(?) (?)

(?-) (1, 2) (?)

(?+) (3, 4) (?+) (5) (?) (?)

(?-) (7, 8) (?)

(?+) (9, 10) (??-) (11) (?+) (12)

( +) (6, 13)

(?) (?-) (1) (?-) (1)

(?-) (2, 3)

- 35 -

第二章 二元关系

再证F ?— A ? ?A 1. F ?— F 2. F ?— ?F 3. F ?— A ? ?A

所以，A ? ?A ?—? F 。

f) A? (B?C) ?—? A?B?C 证明：先证A? (B?C) ?— A?B?C

1. A? (B?C), A?B ?— A?B 2. A? (B?C), A?B ?— A 3. A? (B?C), A?B ?— B 4. A? (B?C), A?B ?— A? (B?C) 5. A? (B?C), A?B ?— B?C 6. A? (B?C), A?B ?— C 7. A? (B?C) ?— A?B?C

再证A?B?C ?— A? (B?C) 1. A?B?C, A, B ?— A 2. A?B?C, A, B ?— B 3. A?B?C, A, B ?— A?B 4. A?B?C, A, B ?— A?B?C 5. A?B?C, A, B ?— C 6. A?B?C, A ?— B?C 7. A?B?C ?— A? (B?C)

所以，A? (B?C) ?—? A?B?C 。 2.

i) (?x) A(x) ?— (?x) A(x) 证明：

1. (?x) A(x) ?— (?x) A(x) 2. (?x) A(x) ?— A(x) 3. (?x) A(x) ?— (?x) A(x)

j) (?x) (?y) A(x, y) ?— (?y) (?x) A(x, y) 证明：

1. (?y) A(x, y) ?— (?y) A(x, y) 2. (?y) A(x, y) ?— A(x, y) 3. (?y) A(x, y) ?— (?x) A(x, y) 4. (?y) A(x, y) ?— (?y) (?x) A(x, y) 5. (?x) (?y) A(x, y) ?— (?y) (?x) A(x, y)

- 36 -

(?)

(F规则) (?-) (1, 2)

(?) (?-) (1) (?-) (1) (?)

(?-) (2, 4) (?-) (3, 5) (?+) (6)

(?) (?)

(?+) (1, 2) (?)

(?-) (3, 4) (?+) (5) (?+) (6)

(?) (?-) (1) (?+) (2)

(?) (?-) (1) (?+) (2) (?+) (3) (左?+) (4)

第二章 二元关系

k) (?x) A(x) ? (?x) B(x) ?— (?x) (A(x) ? B(x)) 证明：

1. (?x) A(x) ?— (?x) A(x) (?) 2. (?x) A(x) ?— A(x) (?-) (1) 3. (?x) A(x) ?— A(x) ? B(x) (?+) (2) 4. (?x) A(x) ?— (?x) (A(x) ? B(x)) (?+) (3) 5. (?x) B(x) ?— (?x) (A(x) ? B(x)) 同理可证 6. (?x) A(x) ? (?x) B(x) ?— (?x) (A(x) ? B(x)) (?-) (4, 5)

l) (?x) (A? B(x)) ?—? A?(?x) B(x)，其中x不是A中的自由变元。 证明：先证 (?x) (A? B(x)) ?— A?(?x) B(x)

1. (?x) (A? B(x)), A ?— A (?) 2. (?x) (A? B(x)), A ?— (?x) (A? B(x)) (?) 3. (?x) (A? B(x)), A ?— A? B(x) (?-) (2) 4. (?x) (A? B(x)), A ?— B(x) (?-) (1, 3) 5. (?x) (A? B(x)), A ?— (?x)B(x) (?+) (4) 6. (?x) (A? B(x)) ?— A? (?x)B(x) (?+) (5)

再证A?(?x)B(x) ?— (?x) (A? B(x)) 1. A?(?x)B(x), A ?— A (?) 2. A?(?x)B(x), A ?— A?(?x)B(x) (?) 3. A?(?x)B(x), A ?— (?x)B(x) (?-) (1, 2) 4. A?(?x)B(x), A ?— B(x) (?-) (3) 5. A?(?x)B(x) ?— A?B(x) (?+) (4) 6. A?(?x)B(x) ?— (?x) (A? B(x)) (?+) (5)

所以，(?x) (A? B(x)) ?—? A?(?x) B(x) 。

m) (?x) (A(x)?B(x)) ?—? (?x)A(x)? (?x)B(x) 证明：先证 (?x) (A(x)?B(x)) ?— (?x)A(x)? (?x)B(x)

1. A(x) ?— A(x) (?) 2. A(x) ?— (?x) A(x) (?+) (1) 3. A(x) ?— (?x) A(x) ? (?x)B(x) (?+) (2) 4. B(x) ?— (?x) A(x) ? (?x)B(x) 同理可证 5. A(x)?B(x) ?— (?x) A(x) ? (?x)B(x) (?-) (4) 6. (?x) (A(x)?B(x)) ?— (?x) A(x) ? (?x)B(x) (左?+) (5)

再证 (?x)A(x)? (?x)B(x) ?— (?x) (A(x)?B(x)) 1. A(x) ?— A(x) (?) 2. A(x) ?— A(x)?B(x) (?+) (1) 3. A(x) ?— (?x) (A(x)?B(x)) (?+) (2) 4. (?x) A(x) ?— (?x) (A(x)?B(x)) (左?+) (3) 5. (?x) B(x) ?— (?x) (A(x)?B(x)) 同理可证 6. (?x) A(x) ? (?x)B(x) ?— (?x) (A(x)?B(x)) (?-) (4, 5)

- 37 -

第二章 二元关系

所以，(?x) (A(x)?B(x)) ?—? (?x)A(x)? (?x)B(x) 。

n) (?x) (A(x)?B(x)) ?—? (?x)A(x) ? (?x)B(x) 证明：先证 (?x) (A(x)?B(x)) ?— (?x)A(x) ? (?x)B(x)

1. (?x) (A(x)?B(x)) ?— (?x) (A(x)?B(x)) (?) 2. (?x) (A(x)?B(x)) ?— A(x)?B(x) (?-) (1) 3. (?x) (A(x)?B(x)) ?— A(x) (?-) (2) 4. (?x) (A(x)?B(x)) ?— (?x) A(x) (?+) (3) 5. (?x) (A(x)?B(x)) ?— B(x) (?-) (2) 6. (?x) (A(x)?B(x)) ?— (?x) B(x) (?+) (5) 7. (?x) (A(x)?B(x)) ?— (?x)A(x) ? (?x) B(x) (?+) (4, 6)

再证 (?x)A(x) ? (?x)B(x) ?— (?x) (A(x)?B(x)) 1. (?x)A(x) ? (?x)B(x) ?— (?x)A(x) ? (?x)B(x) (?) 2. (?x)A(x) ? (?x)B(x) ?— (?x)A(x) (?-) (1) 3. (?x)A(x) ? (?x)B(x) ?— A(x) (?-) (2) 4. (?x)A(x) ? (?x)B(x) ?— (?x)B(x) (?-) (1) 5. (?x)A(x) ? (?x)B(x) ?— B(x) (?-) (4) 6. (?x)A(x) ? (?x)B(x) ?— A(x)?B(x) (?+) (3, 5) 7. (?x)A(x) ? (?x)B(x) ?— (?x) (A(x)?B(x)) (?+) (6)

所以，(?x) (A(x)?B(x)) ?—? (?x)A(x) ? (?x)B(x) 。

o) (?x) A(x) ? (?x) B(x) ?— (?x) (A(x) ? B(x)) 证明：

1. (?x) A(x) ? (?x) B(x), A(x) ?— A(x) (?) 2. (?x) A(x) ? (?x) B(x), A(x) ?— (?x) A(x) (?+) (1) 3. (?x) A(x) ? (?x) B(x), A(x) ?— (?x) A(x) ? (?x) B(x) (?) 4. (?x) A(x) ? (?x) B(x), A(x) ?— (?x) B(x) (?-) (2, 3) 5. (?x) A(x) ? (?x) B(x), A(x) ?— B(x) (?-) (4) 6. (?x) A(x) ? (?x) B(x) ?— A(x) ?B(x) (?+) (5) 7. (?x) A(x) ? (?x) B(x) ?— (?x) (A(x) ?B(x)) (?+) (6)

p) (?x) (A(x) ? B(x)) ?— (?x) A(x) ? (?x) B(x) 证明：

1. (?x) (A(x) ? B(x)), (?x) A(x) ?— (?x) A(x) (?) 2. (?x) (A(x) ? B(x)), (?x) A(x) ?— A(x) (?-) (1) 3. (?x) (A(x) ? B(x)), (?x) A(x) ?— (?x) (A(x) ? B(x)) (?) 4. (?x) (A(x) ? B(x)), (?x) A(x) ?— A(x) ? B(x) (?-) (3) 5. (?x) (A(x) ? B(x)), (?x) A(x) ?— B(x) (?-) (2, 4) 6. (?x) (A(x) ? B(x)), (?x) A(x) ?— (?x) B(x) (?+) (5) 7. (?x) (A(x) ? B(x)) ?— (?x) A(x) ? (?x) B(x) (?+) (6)

- 38 -

第二章 二元关系

3.

解：令R(x, y)为x和y之间具有关系R，则

“对称”可符号化为：(?x) (?y) (R(x, y) ? R(y, x))；

“传递”可符号化为：(?x) (?y) (?z) (R(x, y) ? R(y, z)? R(x, z))； “定义域是全域”可符号化为：(?x) (?y) R(x, y)； “自反”可符号化为：(?x) R(x, x)。 因此，定理可描述为：

(?x) (?y) (R(x, y) ? R(y, x)), (?x) (?y) (?z) (R(x, y) ? R(y, z)? R(x, z)), (?x) (?y) R(x, y) ?— (?x) R(x, x)

令 X = (?x) (?y) (R(x, y) ? R(y, x))； Y = (?x) (?y) (?z) (R(x, y) ? R(y, z)? R(x, z))； Z = (?x) (?y) R(x, y)。 则

1. X, Y, Z ?— (?x) (?y) R(x, y) 2. X, Y, Z ?— (?y) R(x, y) 3. X, Y, Z, R(x, a) ?— R(x, a) 4. X, Y, Z, R(x, a) ?— (?x) (?y) (R(x, y) ? R(y, x)) 5. X, Y, Z, R(x, a) ?— (?y) (R(x, y) ? R(y, x)) 6. X, Y, Z, R(x, a) ?— (R(x, a) ? R(a, x)) 7. X, Y, Z, R(x, a) ?— R(a, x)) 8. X, Y, Z, R(x, a) ?— (?x) (?y) (?z) (R(x, y) ? R(y, z)? R(x, z)) 9. X, Y, Z, R(x, a) ?— (?y) (?z) (R(x, y) ? R(y, z)? R(x, z)) 10. X, Y, Z, R(x, a) ?— (?z) (R(x, a) ? R(a, z)? R(x, z)) 11. X, Y, Z, R(x, a) ?— (R(x, a) ? R(a, x)? R(x, x)) 12. X, Y, Z, R(x, a) ?— (R(x, a) ? R(a, x) 13. X, Y, Z, R(x, a) ?— R(x, x)) 14. X, Y, Z ?— R(x, x)) 15. X, Y, Z ?— (?x)R(x, x)

习题6.2

1. d) ?— ? (A?B) ?A??B 证明：

1. ? (A?B), A, B ?— A

(?) 2. ? (A?B), A, B ?— B (?)

3. ? (A?B), A, B ?— A?B (?+) (1, 2) 4. ? (A?B), A, B ?— ? (A?B) (?) 5. ? (A?B), A ?— ? B (?+) (4) 6. ? (A?B), A ?— ?A?? B (?+) (5) 7. ? (A?B), ?A ?— ? A (?) 8. ? (A?B), ?A ?— ?A?? B (?+) (7) 9. ? (A?B) ?— ?A?? B

(?-) (6, 8)

- 39 -

(?) (?-) (1) (?) (?) (?-) (4) (?-) (5) (?-) (6) (?) (?-) (8) (?-) (9) (?-) (10) (?+) (3, 7) (?-) (11,12) (?-) (2, 13) (?+) (14)

第二章 二元关系

10. ?A, A?B ?— ? A 11. ?A, A?B ?— A?B 12. ?A, A?B ?— A 13. ?A, A?B ?— F 14. ?B, A?B ?— ? B 15. ?B, A?B ?— A?B 16. ?B, A?B ?— B 17. ?B, A?B ?— F

(?) (?)

(?-) (11) (?-) (10, 12) (?) (?)

(?-) (15) (?-) (14, 16) 18. ?A?? B, A?B ?— F 19. ?A?? B, A?B ?— ? F 20. ?A?? B ?— ? (A?B) 21. ?— ? (A?B) ?A??B

f) ?— (A?B) ?A?B 证明：

1. A?B, A, ?B ?— A 2. A?B, A, ?B ?— A?B 3. A?B, A, ?B ?— B 4. A?B, A, ?B ?— ?B 5. A?B, A ?— ??B 6. A?B, A ?— B 7. A?B, A ?— ?A?B 8. A?B, ?A ?— ?A 9. A?B, ?A ?— ?A?B 10. A?B ?— ?A?B

11. ?A, A ?— A 12. ?A, A ?— ?A 13. ?A, A ?— B 14. ?A ?— A?B 15. B, A ?— B 16. B ?— A?B 17. ?A?B ?— A?B 18. ?— (A?B) ?A?B

g) ? (A?B)?— A 证明：

1. ? (A?B), ?A, A ?— A 2. ? (A?B), ?A, A ?— ?A 3. ? (A?B), ?A, A ?— B 4. ? (A?B), ?A ?— A?B 5. ? (A?B), ?A ?— ? (A?B) 6. ? (A?B) ?— ??A

(?-) (13, 17) (F规则) (?+) (18, 19) ( +) (9, 20)

(?) (?) (?-) (1, 2) (?) (?+) (4) (??-) (5) (?+) (6) (?) (?+) (8)

(?-) (7, 9)

(?) (?) (?-) (11, 12) (?+) (13) (?) (?+) (15) (?-) (14, 16) ( +) (10, 17) (?) (?) (?-) (1, 2) (?+) (3) (?) (?+) (4, 5)

- 40 -

第二章 二元关系

7. ? (A?B) ?— A (??-) (6)

3. a) ?— (?x) (C?A(x)) (C?(?x)A(x)) 证明：

1. C?A(x), C ?— C (?) 2. C?A(x), C ?— C?A(x) (?) 3. C?A(x), C ?— A(x) (?-) (1, 2) 4. C?A(x), C ?— (?x)A(x) (?+) (3) 5. (?x) (C?A(x)), C ?— (?x)A(x) (左?+) (4) 6. (?x) (C?A(x)) ?— C? (?x)A(x) (?+) (5)

7. ? (?x) (C?A(x)) ?— (?x) (? (C?A(x))) (可证?(?x)A(x)) ?— (?x) (?A(x)) ) 8. ?— ?(?x) (C?A(x)) ? (?x) (? (C?A(x))) (?+) (7) 9. C?(?x)A(x), ? (?x) (C?A(x)) ?— ? (?x) (C?A(x)) (?) 10. C?(?x)A(x), ? (?x) (C?A(x)) ?— ?(?x) (C?A(x)) ? (?x) (? (C?A(x)))

11.

12. 13. 14. 15. 16. 17. 18. 17. 18. 19. 20. 21. 22. 23.

(?+) (8)

C?(?x)A(x), ? (?x) (C?A(x)) ?— (?x) (? (C?A(x))) (?-) (9, 10) C?(?x)A(x), ? (?x) (C?A(x)) ?— ? (C?A(x)) (?-) (11) ? (C?A(x))?— C, ?A(x)) (可证?(A?B) ?— A, ?B) ?— ? (C?A(x)) ? C (?+) (13) C?(?x)A(x), ? (?x) (C?A(x)) ?— ? (C?A(x)) ? C (?+) (14) C?(?x)A(x), ? (?x) (C?A(x)) ?— C (?-) (12, 15) C?(?x)A(x), ? (?x) (C?A(x)) ?— C?(?x)A(x) (?) C?(?x)A(x), ? (?x) (C?A(x)) ?— (?x)A(x) (?-) (16, 17)

?— ? (C?A(x)) ? ?A(x) (?+) (13) C?(?x)A(x), ? (?x) (C?A(x)) ?— ?(C?A(x))??A(x) (?+) (17) C?(?x)A(x), ? (?x) (C?A(x)) ?— ?A(x) (?-) (12, 18) C?(?x)A(x), ? (?x) (C?A(x)) ?— (?x)(?A(x)) (?+) (19) (?x)(?A(x)) ?— ? (?x) A(x) (易证) ?— (?x)(?A(x)) ? ? (?x) A(x) (?+) (21) C?(?x)A(x), ? (?x) (C?A(x)) ?— (?x)(?A(x)) ? ? (?x) A(x)

(?+) (22)

24. C?(?x)A(x), ? (?x) (C?A(x)) ?— ? (?x) A(x) (?-) (20, 23) 25. C?(?x)A(x) ?— ? ? (?x) (C?A(x)) (?+) (18, 24) 26. C?(?x)A(x) ?— (?x) (C?A(x)) (??-) (25) 27. ?— (?x) (C?A(x)) (C?(?x)A(x))

e) ?(?x)A(x) ?—? (?x) (?A(x)) 证明：?— )

1. ?(?x)A(x), ?(?x) (?A(x)), ?A(x)

- 41 -

( +) (6, 26)

?— ?A(x) (?)

第二章 二元关系

—? )

2.

3. 4. 5. 6. 7. 8. 9. 1. 2. 3. 4. 5. 6. 7. 8. ?(?x)A(x), ?(?x) (?A(x)), ?A(x) ?(?x)A(x), ?(?x) (?A(x)) , ?A(x) ?(?x)A(x), ?(?x) (?A(x)) ?(?x)A(x), ?(?x) (?A(x)) ?(?x)A(x), ?(?x) (?A(x)) ?(?x)A(x), ?(?x) (?A(x)) ?(?x)A(x) ?(?x)A(x) (?x) (?A(x)), (?x)A(x) (?x) (?A(x)), (?x)A(x), ?A(a) (?x) (?A(x)), (?x)A(x), ?A(a) (?x) (?A(x)), (?x)A(x), ?A(a) (?x) (?A(x)), (?x)A(x), ?A(a) (?x) (?A(x)), (?x)A(x) (?x) (?A(x)), (?x)A(x) (?x) (?A(x)) ?—

?— ?— ?— ?— ?— ?— ?— ?— ?— ?— ?— ?— ?— ?— ?— (?x)?A(x)

?(?x) (?A(x)) ??A(x) A(x) (?x)A(x) ?(?x)A(x) ??(?x) (?A(x)) (?x) (?A(x)) (?x) (?A(x)) ?A(a) (?x)A(x) A(a) F F ?F ?(?x)A(x) (?+) (1) (?) (?+) (3) (??-) (4) (?+) (5) (?)

(?+) (6, 7) (??-) (8) (?) (?) (?) (?-) (3) (?-) (2, 4) (?-) (1, 5) (F规则) (?+) (6, 7)

所以，?(?x)A(x) ?—? (?x) (?A(x)) 。

f) (?x) (A(x)?B(x)) ?— (?x) A(x) ? (?x) B(x) 证明：

1. A(x)?B(x) ?— A(x)?B(x) (?) 2. A(x)?B(x) ?— A(x) 3. A(x)?B(x) ?— (?x) A(x) 4. A(x)?B(x) ?— B(x) 5. A(x)?B(x) ?— (?x) B(x) 6. A(x)?B(x) ?— (?x) A(x) ? (?x) B(x) 7. (?x) (A(x)?B(x)) ?— (?x) A(x) ? (?x) B(x)

(?-) (1) (?+) (2) (?-) (1) (?+) (4) (?+) (3, 5) (左?+) (6)

第七章 图 论

习题7.1

1.

j) 非简单图；（有自圈） k) 非简单图；（有自圈） l) 简单图。 3.

证明：因为n个顶点的有向简单图中，每两个不同顶点之间最多有两条边，因此其边数最多

- 42 -

第二章 二元关系

为：。

4. 利用定理7.1.3 证明：因为任何图均有偶数个奇结点，而3度正则图的所有结点度数均为3，即均为偶结点。所以，3度正则图必有偶数个奇结点。

5. 利用定理7.1.3

6.

证明：假设六个人分别为：a, b, c, d, e, f。则分两种情况讨论。

① 若a认识的人大于等于3个，即b, c, d, e, f中至少有3个与a认识。不妨设c, d, e与a认识，则c, d, e必定互相不认识。（否则，c, d, e中互相认识的两人与a就构成三个人互相都认识。产生矛盾。）

② 若a认识的人小于3个，即b, c, d, e, f中至少有3个与a不认识。不妨设b, c, d与a均不认识。则因为没有3个人彼此都认识，所以b, c, d中必有两个人互相不认识。假设c, d互相不认识，则a, c, d三个人彼此都不认识。

8. a ) 图中有一个与两个度数为3的结点邻接的结点，其度数也为3。

而b ) 图中没有任何一个度数为3的结点与两个度数为3的结点邻接。 所以，a ) 与b ) 不同构。

9. b ) 图的中心结点其入度为0，而a ) 图中没有入度为0 的结点。所以两图不同构。

10. n阶简单无向图的结点度数不可能超过n-1，即取值范围为：{0, 1, 2, … , n-1}。

证明n（n>1）阶图中必有两个结点度数相等，抽屉原则应该可以使用，但n个结点，n种度数可能，抽屉原则似乎用不上。但我们发现，若图中有孤立点，则所有结点的度数只可能从0到n-2中取值，即只有n-1种可能性。于是分两种情况： ① 若G中无孤立点（度数为0的结点），则G中n个结点的度数只能从1到n-1中取值。n个结点，n-1种可能的度数取值，由抽屉原则，G中必有两个结点的度数相等。

② 若G中有孤立点，则G中n个结点的度数只能从0到n-2中取值。n个结点，n-1种可能的度数取值，由抽屉原则，G中必有两个结点的度数相等。

11. 根据定理7.1.1可知无向图中所有结点的度数和是边数的两倍。所以，

，即。

- 43 -

第二章 二元关系

习题7.2

2. 显然G[V?]重任意两点之间必定互有有向边，并且无自圈、无平行边。 4.

(1) 自反的；

(2) 反对称的、传递的； (3) 自反的、对称的、传递的； (4) 自反的、传递的； (5) 无； (6) 对称的；

(7) 自反的、反对称的、传递的； (8) 对称的； (9) 对称的； (10) 反对称的； (11) 自反的、反对称的； (12) 反对称的、传递的。 4.

g) A上共有h) A上共有i) j)

A上共有A上共有个不相同的自反关系； 个不相同的反自反关系； 个不相同的对称关系；

个不相同的反对称关系；

个不相同的既是对称的又是反对称的关系；

k) A上共有

习题2.3

1. 最多能有n(A) 个元素为1。 2. 证明：

i) R ? R-1为A上包含R的最小对称关系 ① R ? R ? R-1。所以，R?R-1包含R。

② 因为对于任意 ? R ? R-1，有 ? R或 ? R-1。

- 44 -

第二章 二元关系

若 ? R，则 ? R-1；若 ? R-1，则 ? R。 因此， ? R ? R-1。所以，R?R-1为A上的对称关系。 ③ 设R?为任意的A上包含R的对称关系，则

对于任意 ? R ? R-1，有 ? R或 ? R-1。 若 ? R，由于R?包含R，所以 ? R?； 若 ? R-1，则 ? R，由于R?包含R，所以 ? R?，而R?对称，所以 ? R?。 因此，总有 ? R?。所以，R ? R-1 ? R?。

由①②③可知，R ? R-1为A上包含R的最小对称关系。

ii) R ? R-1为A上包含在R中的最大对称关系 ① R ? R-1 ? R。所以，R ? R-1包含在R中。

② 因为对于任意 ? R ? R-1，有 ? R且 ? R-1。 ? R，所以 ? R-1； ? R-1，所以 ? R。 因此， ? R ? R-1。所以，R ? R-1为A上的对称关系。 ③ 设R?为任意的A上包含在R中的对称关系，则

对于任意 ? R?，由于R?包含在R中，所以 ? R；

又由于R?对称，所以 ? R?，而R?包含在R中，所以 ? R，因此， ? R-1； 因此，总有 ? R ? R-1。所以，R ? R?R-1。

由①②③可知，R ? R-1为A上包含在R中的最大对称关系。

习题2.4

1.

R2 ? R1 = {}； R1 ? R2 = {, }； R12 = {, , }； R22 = {, }；

2. m = 1, n = 16。

4. A = {1, 2, 3}

令R1 = {<1, 2>, <1, 3>}；R2 = {<2, 2>}；R3 = {<3, 2>}；则 R1 ? ( R2 ? R3 ) = ?；( R1 ? R2 ) ? ( R1 ? R3 ) = {<1, 3>}； 所以，R1 ? ( R2 ? R3 ) ? ( R1 ? R2 ) ? ( R1 ? R3 ) 。

令R2 = {<2, 2>}；R3 = {<2, 3>}；R4 = {<2, 1>, <3, 1>}；则 ( R2 ? R3 ) ? R4 = ?；( R2 ? R4 ) ? ( R3 ? R4 ) = {<2, 1>}； 所以，( R2 ? R3 ) ? R4 ? ( R2 ? R4 ) ? ( R3 ? R4 ) ； 5.

a) 正确。 b) 不正确。令A = {1, 2}，则R1 = {<1, 2>}, R2 = {<2, 1>}都是反自反的，但R1 ? R2 ={<1, 1>}

不是反自反的。

c) 不正确。令A = {1, 2, 3}，则R1 = {<1, 2>, <2, 1>}, R2 = {<2, 3>, <3, 2>}都是对称的，但

R1 ? R2 = {<1, 3>}不是对称的。

- 45 -

第二章 二元关系

d) 不正确。令A = {1, 2, 3}，则R1 = {<1, 2>, <3, 1>}, R2 = {<2, 3>, <1, 1>}都是反对称的，

但R1 ? R2 = {<1, 3>, <3, 1>}不是反对称的。

e) 不正确。令A = {1, 2, 3}，则R1 = {<1, 2>, <3, 1>, <3, 2>}, R2 = {<2, 3>, <1, 1>}都是传递

的，但R1 ? R2 = {<1, 3>, <3, 1>, <3, 3>}不是传递的。

10. 证明：

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 。 m) 若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)。

- 46 -

第二章 二元关系

习题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) 不正确；（不自反） b) 不正确；（不自反） c) 不正确；（不自反） d) 不正确；（不传递，< -1, 0 > ? R, < 0, 1 > ? R, 但<-1, 1> ? R） e) 不正确；（不对称） f) 不正确；（不对称） g) 不正确；（不传递） h) 正确； i) 不正确。（不自反，i = 10k时， ? R）

2. 不对。

应加上条件：对于任意x?A，总存在y?A使得 ? R。 3.

证明：

① 已知条件：若 ? R， ? R，则 ? R。

先证对称性：若 ? R，则由于R自反，所以 ? R，由上式有 ? R。 所以R对称。

再证传递性：若 ? R， ? R，则因为R对称，所以 ? R。由已知条件，因为 ? R且 ? R，所以 ? R。 所以R传递。 因此，R时等价关系。

② 已知条件：R是等价关系。 若 ? R， ? R，则因为R对称，所以 ? R。又由于R传递，所以， ?R。

- 47 -

第二章 二元关系

因此，若 ? R， ? R，则 ? R。

习题2.8

1. a) b) c) d) e) f) g) h) 4. a) b) 6. a) b) c)

半序；

半序、全序、良序； 无；（不是反对称的） 无；（不是传递的） 半序； 无；（不是传递的） 无；（不是传递的） 拟序。

设R是集合A上的二元关系，证明：

R是A上的半序，当且仅当R ? R-1 = IIA且R = R*。 自反、反对称 ___________ _______传递 R是A上的拟序，当且仅当R ? R-1 = ? 且R = R+。 反自反 ___________ _______传递

断言中为真的有：x4Rx1, x1Rx1。 P的最小元：无；P的最大元：x1 ；

P的极小元：x4和x5；P的极大元：x1 。

{x2, x3, x4}的上界：x1；下界：x4；上确界：x1；下确界：x4。 {x3, x4, x5}的上界：x1, x3；下界：无；上确界：x3；下确界：无。 {x1, x2, x3}的上界：x1；下界：x4；上确界：x1；下确界：x4。

7. a) b) c) d) 8. 9.

< I, ? >中的非空子集I无最小元。 < I+, |>（“|”为整除关系）中的非空子集{x | x >4}无最大元。 中的非空子集(0, 1)由下确界0，但无最小元。 书上例4中的非空子集{4}有上界8和12，但无上确界。 归纳法。 归纳法。

- 48 -

本文来源：https://www.bwwdw.com/article/ytbp.html