左孝凌离散数学课后题答案

1-1，1-2 （1） 解：

a) 是命题，真值为T。 b) 不是命题。

c) 是命题，真值要根据具体情况确定。 d) 不是命题。

e) 是命题，真值为T。 f) 是命题，真值为T。 g) 是命题，真值为F。 h) 不是命题。 i) 不是命题。 （2） 解：

原子命题：我爱北京天安门。

复合命题：如果不是练健美操，我就出外旅游拉。 （3） 解：

a) (┓P ∧R)→Q b) Q→R c) ┓P d) P→┓Q （4） 解：

a)设Q:我将去参加舞会。R:我有时间。P:天下雨。

Q? (R∧┓P):我将去参加舞会当且仅当我有时间和天不下雨。 b)设R:我在看电视。Q:我在吃苹果。 R∧Q:我在看电视边吃苹果。

c) 设Q:一个数是奇数。R:一个数不能被2除。

（Q→R）∧(R→Q):一个数是奇数，则它不能被2整除并且一个数不能被2整除，则它是奇数。 (5) 解：

a) 设P：王强身体很好。Q：王强成绩很好。P∧Q b) 设P：小李看书。Q：小李听音乐。P∧Q c) 设P：气候很好。Q：气候很热。P∨Q

d) 设P： a和b是偶数。Q：a+b是偶数。P→Q

e) 设P：四边形ABCD是平行四边形。Q ：四边形ABCD的对边平行。P?Q

f) 设P：语法错误。Q：程序错误。R：停机。（P∨ Q）→ R (6) 解：

a) P:天气炎热。Q:正在下雨。 P∧Q b) P:天气炎热。R:湿度较低。 P∧R c) R:天正在下雨。S:湿度很高。 R∨S d) A:刘英上山。B:李进上山。 A∧B

e) M:老王是革新者。N:小李是革新者。 M∨N f) L:你看电影。M:我看电影。 ┓L→┓M

g) P:我不看电视。Q:我不外出。 R:我在睡觉。 P∧Q∧R

h) P:控制台打字机作输入设备。Q:控制台打字机作输出设备。P∧Q 1-3

（1）解：

a) 不是合式公式，没有规定运算符次序（若规定运算符次序后亦可

作为合式公式） b) 是合式公式

c) 不是合式公式（括弧不配对）

d) 不是合式公式（R和S之间缺少联结词） e) 是合式公式。 （2）解：

a） A是合式公式，(A∨B)是合式公式，(A→(A∨B)) 是合式公式。

这个过程可以简记为： A；(A∨B)；(A→(A∨B)) 同理可记

b） A；┓A ；(┓A∧B) ；((┓A∧B)∧A)

c） A；┓A ；B；(┓A→B) ；(B→A) ；((┓A→B)→(B→A)) d） A；B；(A→B) ；(B→A) ；((A→B)∨(B→A)) （3）解：

a） ((((A→C)→((B∧C)→A))→((B∧C)→A))→(A→C)) b） ((B→A)∨(A→B))。 （4）解：

a) 是由c) 式进行代换得到，在c) 中用Q代换P, (P→P)代换Q.

d) 是由a) 式进行代换得到，在a) 中用 P→(Q→P)代换Q.

e) 是由b) 式进行代换得到，用R代换P, S代换Q, Q代换R, P代换S. （5）解：

a) P: 你没有给我写信。 R: 信在途中丢失了。 P Q b) P: 张三不去。Q: 李四不去。R: 他就去。 (P∧Q)→R

c) P: 我们能划船。 Q: 我们能跑步。 ┓(P∧Q)∨

d) P: 你来了。Q: 他唱歌。R: 你伴奏。 P→(Q?R) （6）解：

P:它占据空间。 Q:它有质量。 R:它不断变化。 S:它是物质。 这个人起初主张：(P∧Q∧R) ? S 后来主张：(P∧Q?S)∧(S→R)

这个人开头主张与后来主张的不同点在于：后来认为有P∧Q必同时有R，开头时没有这样的主张。 （7）解：

a) P: 上午下雨。 Q:我去看电影。 R:我在家里读书。 S:我在家里看报。(┓P→Q)∧(P→(R∨S))

b) P: 我今天进城。Q:天下雨。┓Q→P c) P: 你走了。 Q:我留下。Q→P 1-4

（4）解：a) P Q R Q∧R P∧(Q∧R) P∧Q (P∧Q)∧R T T T T T T T T T F F F T F T F T F F F F T F F F F F F F T T T F F F F T F F F F F F F T F F F F F F F F F F F 所以，P∧(Q∧R) ? (P∧Q)∧R b)

P Q R Q∨R P∨(Q∨R) P∨Q (P∨Q)∨R T T T Ｔ Ｔ Ｔ Ｔ T T F Ｔ Ｔ Ｔ Ｔ T F T Ｔ Ｔ Ｔ Ｔ T F F Ｆ Ｔ Ｔ Ｔ F T T Ｔ Ｔ Ｔ Ｔ F T F Ｔ Ｔ Ｔ Ｔ F F T Ｔ Ｔ Ｆ Ｔ F F F Ｆ Ｆ Ｆ Ｆ 所以，P∨(Q∨R) ? (P∨Q)∨R ｃ） Ｐ Ｑ Ｒ Ｑ∨Ｒ Ｐ∧（Ｑ∨Ｒ） Ｐ∧Ｑ Ｐ∧Ｒ （Ｐ∧Ｑ）∨（Ｐ∧Ｒ） Ｔ Ｔ Ｔ Ｔ Ｔ Ｆ Ｔ Ｆ Ｔ Ｔ Ｔ Ｔ Ｔ Ｔ Ｔ Ｔ Ｔ Ｆ Ｔ Ｔ Ｆ Ｔ Ｔ Ｆ Ｔ Ｔ Ｆ Ｆ Ｆ Ｆ Ｆ Ｆ Ｆ Ｔ Ｔ Ｆ Ｆ Ｆ Ｆ Ｔ Ｔ Ｆ Ｆ Ｆ Ｆ Ｆ Ｔ Ｔ Ｆ Ｆ Ｆ Ｆ Ｆ Ｆ Ｆ Ｆ Ｆ Ｆ Ｆ Ｆ Ｔ Ｆ Ｆ Ｆ 所以，P∧(Q∨R) ? (P∧Q)∨(P∧R) ｄ）

P Q ┓P ┓Q ┓P∨┓Q ┓(P∧Q) ┓P∧┓Q ┓(P∨Q) T T F F F F F F T F F T T T F F F T T F T T F F F F T T T T T T 所以，┓(P∧Q) ?┓P∨┓Q, ┓(P∨Q) ?┓P∧┓Q （5）解：如表，对问好所填的地方，可得公式F1～F6，可表达为 P Q R F1 F2 F3 F4 F5 F6 T T T T F T T F F T T F F F T F F F T F T T F F T T F T F F F T F T T F F T T T F F T T F F T F T F F F T F F F T T F T T T F F F F F T F T T T F1:(Q→P)→R F2:(P∧┓Q∧┓R)∨(┓P∧┓Q∧┓R) F3:(P←→Q)∧(Q∨R)

F4:(┓P∨┓Q∨R)∧(P∨┓Q∨R)

F5:(┓P∨┓Q∨R)∧(┓P∨┓Q∨┓R) F6:┓(P∨Q∨R)

(6) P Q 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 F F F T F T F T F T F T F T F T F T F T F F T T F F T T F F T T F F T T T F F F F F T T T T F F F F T T T T T T F F F F F F F F T T T T T T T T 解：由上表可得有关公式为 1.F 2.┓(P∨Q) 3.┓(Q→P) 4.┓P

5.┓(P→Q) 6.┓Q 7.┓(P?Q) 8.┓(P∧Q) 9.P∧Q 10.P?Q 11.Q 12.P→Q 13.P 14.Q→P 15.P∨Q 16.T

(7) 证明：

a) A→(B→A)? ┐A∨(┐B∨A)

? A∨(┐A∨┐B) ? A∨(A→┐B) 1 ?┐A→(A→┐B)

b) ┐(A?B) ?┐((A∧B)∨(┐A∧┐B))

?┐((A∧B)∨┐(A∨B)) ?(A∨B)∧┐(A∧B)

或 ┐(A?B) ?┐((A→B)∧(B→A))

?┐((┐A∨B)∧(┐B∨A))

?┐((┐A∧┐B)∨(┐A∧A)∨(B∧┐B)∨(B∧A)) ?┐((┐A∧┐B)∨(B∧A)) ?┐(┐(A∨B))∨(A∧B) ?(A∨B)∧┐(A∧B)

c) ┐(A→B) ? ┐(┐A∨B) ?A∧┐B d) ┐(A?B)?┐((A→B)∧(B→A))

?┐((┐A∨B)∧(┐B∨A)) ?(A∧┐B)∨(┐A∧B)

e) (((A∧B∧C)→D)∧(C→(A∨B∨D)))

?(┐(A∧B∧C)∨D)∧(┐C∨(A∨B∨D)) ?(┐(A∧B∧C)∨D)∧(┐(┐A∧┐B∧C)∨D) ? (┐(A∧B∧C)∧┐(┐A∧┐B∧C))∨D ?((A∧B∧C)∨(┐A∧┐B∧C))→D ? (((A∧B)∨(┐A∧┐B))∧C)→D ? ((C∧(A?B))→D)

f) A→(B∨C) ? ┐A∨(B∨C)

? (┐A∨B)∨C ?┐(A∧┐B)∨C ? (A∧┐B)→C

g) (A→D)∧(B→D)?(┐A∨D)∧(┐B∨D)

?(┐A∧┐B)∨D ? ┐(A∨B)∨D ? (A∨B)→D

h) ((A∧B)→C)∧(B→(D∨C))

?(┐(A∧B)∨C)∧(┐B∨(D∨C)) ? (┐(A∧B)∧(┐B∨D))∨C ?(┐(A∧B) ∧┐(┐D∧B))∨C ?┐((A∧B)∨(┐D∧B))∨C ? ((A∨┐D)∧B)→C ? (B∧(D→A))→C （8）解：

a) ((A→B) ? (┐B→┐A))∧C

? ((┐A∨B) ? (B∨┐A))∧C ? ((┐A∨B) ? (┐A∨B))∧C ?T∧C ?C

b) A∨(┐A∨(B∧┐B)) ? (A∨┐A)∨(B∧┐B) ?T∨F ?T c) (A∧B∧C)∨(┐A∧B∧C)

? (A∨┐A) ∧(B∧C) ?T∧(B∧C) ?B∧C

（9）解：1）设C为T，A为T，B为F，则满足A∨C?B∨C，但A?B不成立。

2）设C为F，A为T，B为F，则满足A∧C?B∧C，但A?B不成立。

3）由题意知┐A和┐B的真值相同，所以A和B的真值也相同。 习题 1-5 （1） 证明：

a) (P∧(P→Q))→Q

? (P∧(┐P∨Q))→Q ?(P∧┐P)∨(P∧Q)→Q ?(P∧Q)→Q ?┐(P∧Q)∨Q ?┐P∨┐Q∨Q ?┐P∨T ?T b) ┐P→(P→Q)

?P∨(┐P∨Q) ? (P∨┐P)∨Q ?T∨Q ?T

c) ((P→Q)∧(Q→R))→(P→R)

因为(P→Q)∧(Q→R)?(P→R) 所以 (P→Q)∧(Q→R)为重言式。

d) ((a∧b)∨(b∧c) ∨(c∧a))?(a∨b)∧(b∨c)∧(c∨a)

因为((a∧b)∨(b∧c)∨(c∧a)) ?((a∨c)∧b)∨(c∧a)

?((a∨c)∨(c∧a))∧(b∨(c∧a)) ?(a∨c)∧(b∨c)∧(b∨a)

所以((a∧b)∨(b∧c) ∨(c∧a))?(a∨b)∧(b∨c)∧(c∨a)为重言式。

（2） 证明：

a)(P→Q)?P→(P∧Q) 解法1： 设P→Q为T

（1）若P为T，则Q为T，所以P∧Q为T，故P→(P∧Q)为T （2）若P为F，则Q为F，所以P∧Q为F，P→(P∧Q)为T 命题得证 解法2：

设P→(P∧Q)为F ，则P为T，(P∧Q)为F ，故必有P为T，Q为F ，所以P→Q为F。 解法3：

(P→Q) →(P→(P∧Q))

?┐(┐P∨Q)∨(┐P∨(P∧Q))

?┐(┐P∨Q)∨((┐P∨P)∧(┐P∨Q)) ?T

所以(P→Q)?P→(P∧Q) b)(P→Q)→Q?P∨Q

设P∨Q为F，则P为F，且Q为F，

故P→Q为T，(P→Q)→Q为F， 所以(P→Q)→Q?P∨Q。

c)(Q→(P∧┐P))→(R→(R→(P∧┐P)))?R→Q

设R→Q为F，则R为T，且Q为F，又P∧┐P为F 所以Q→(P∧┐P)为T，R→(P∧┐P)为F

所以R→(R→(P∧┐P))为F，所以(Q→(P∧┐P))→(R→(R→(P∧┐P)))为F

即(Q→(P∧┐P))→(R→(R→(P∧┐P)))?R→Q成立。 （3） 解：

a) P→Q表示命题“如果8是偶数，那么糖果是甜的”。

b) a)的逆换式Q→P表示命题“如果糖果是甜的，那么8是偶数”。 c) a)的反换式┐P→┐Q表示命题“如果8不是偶数，那么糖果不是甜的”。

d) a)的逆反式┐Q→┐P表示命题“如果糖果不是甜的，那么8不是偶数”。

（4） 解：

a) 如果天下雨，我不去。

设P：天下雨。Q：我不去。P→Q

逆换式Q→P表示命题:如果我不去，则天下雨。 逆反式┐Q→┐P表示命题:如果我去，则天不下雨 b) 仅当你走我将留下。

设S：你走了。R：我将留下。R→S

逆换式S→R表示命题：如果你走了则我将留下。

逆反式┐S→┐R表示命题：如果你不走，则我不留下。 c) 如果我不能获得更多帮助，我不能完成个任务。

设E：我不能获得更多帮助。H：我不能完成这个任务。E→H

逆换式H→E表示命题：我不能完成这个任务，则我不能获得更多帮助。

逆反式┐H→┐E表示命题：我完成这个任务，则我能获得更多帮助 （5） 试证明P?Q，Q逻辑蕴含P。 证明：解法1：

本题要求证明(P?Q) ∧Q?P,

设(P?Q) ∧Q为T，则(P?Q)为T，Q为T，故由?的定义，必有P为T。

所以(P?Q) ∧Q?P 解法2：

由体题可知，即证((P?Q)∧Q)→P是永真式。

((P?Q)∧Q)→P ? (((P∧Q) ∨(┐P∧┐Q)) ∧Q)→P ? (┐((P∧Q) ∨(┐P∧┐Q)) ∨┐Q) ∨P ? (((┐P∨┐Q) ∧(P∨Q)) ∨┐Q) ∨P ? ((┐Q∨┐P∨┐Q) ∧(┐Q∨P∨Q)) ∨P ? ((┐Q∨┐P) ∧T) ∨P ?┐Q∨┐P∨P ?┐Q∨T ?T （6） 解：

P：我学习 Q：我数学不及格 R：我热衷于玩扑克。如果我学习，那么我数学不会不及格： P→┐Q 如果我不热衷于玩扑克，那么我将学习: ┐R→P 但我数学不及格: Q 因此我热衷于玩扑克。 R 即本题符号化为：(P→┐Q)∧(┐R→P)∧Q?R 证：

证法1：((P→┐Q)∧(┐R→P)∧Q)→R ? ┐((┐P∨┐Q)∧(R∨P)∧Q) ∨R ? (P∧Q)∨(┐R∧┐P)∨┐Q∨R

? ((┐Q∨P)∧(┐Q∨Q))∨((R∨┐R)∧(R∨┐P)) ? ┐Q∨P∨R∨┐P ? T

所以，论证有效。

证法2：设(P→┐Q)∧(┐R→P)∧Q为T， 则因Q为T，(P→┐Q) 为T，可得P为F， 由(┐R→P)为T，得到R为T。 故本题论证有效。 （7） 解：

P：6是偶数 Q：7被2除尽 R：5是素数 如果6是偶数，则7被2除不尽 P→┐Q 或5不是素数，或7被2除尽 ┐R∨Q 5是素数 R 所以6是奇数 ┐P 即本题符号化为：（P→┐Q）∧（┐R∨Q）∧R ?┐P 证：

证法1：((P→┐Q)∧(┐R∨Q)∧R)→┐P ? ┐((┐P∨┐Q) ∧(┐R∨Q) ∧R) ∨┐P ? ((P∧Q) ∨(R∧┐Q) ∨┐R) ∨┐P

? ((┐P∨P) ∧(┐P∨Q)) ∨((┐R∨R) ∧(┐R∨┐Q)) ? (┐P∨Q) ∨(┐R∨┐Q) ?T

所以，论证有效，但实际上他不符合实际意义。 证法2：(P→┐Q)∧(┐R∨Q)∧R为T， 则有R为T，且┐R∨Q 为T，故Q为T， 再由P→┐Q为T，得到┐P为T。 8） 证明：

a) P?(┐P→Q)

设P为T，则┐P为F，故┐P→Q为T b) ┐A∧B∧C?C

假定┐A∧B∧C为T，则C为T。 c) C?A∨B∨┐B

因为A∨B∨┐B为永真，所以C?A∨B∨┐B成立。 d) ┐(A∧B) ?┐A∨┐B

设┐(A∧B)为T，则A∧B为F。

若A为T，B为F，则┐A为F，┐B为T，故┐A∨┐B为T。若A为F，B为T，则┐A为T，┐B为F，故┐A∨┐B为T。若A为F，B为F，则┐A为T，┐B为T，故┐A∨┐B为T。命题得证。

e) ┐A→(B∨C)，D∨E，(D∨E)→┐A?B∨C 设┐A→(B∨C)，D∨E，(D∨E)→┐A为T， 则D∨E为T，(D∨E)→┐A为T，所以┐A为T 又┐A→(B∨C)为T，所以B∨C为T。命题得证。 f) (A∧B)→C，┐D，┐C∨D?┐A∨┐B

设(A∧B)→C，┐D，┐C∨D为T，则┐D为T，┐C∨D为T，所以C为F

又(A∧B)→C为T，所以A∧B为F，所以┐A∨┐B为T。命题得证。 （9）解：

a) 如果他有勇气，他将得胜。

P：他有勇气 Q：他将得胜

原命题：P→Q 逆反式：┐Q→┐P 表示：如果他失败了，说明他没勇气。

b) 仅当他不累他将得胜。

P：他不累 Q：他得胜

原命题：Q→P 逆反式：┐P→┐Q 表示：如果他累，他将失败。

习题 1-6 (1)解：

a) (P∧Q)∧┐P?(P∧┐P)∧Q?┐(T∨Q) b) (P→(Q∨┐R)) ∧┐P∧Q

? (┐P∨(Q∨┐R))∧┐P∧Q

?(┐P∧┓P∧Q)∨(Q∧┓P∧Q)∨(┓R∧┓P∧Q) ?(┓P∧Q)∨(┓P∧Q)∨(┓P∧┓R∧Q) ?┓P∧Q

?┐(P∨┐Q)

c) ┐P∧┐Q∧(┐R→P)

?┐P∧┐Q∧(R∨P)

?(┐P∧┐Q∧R)∨(┐P∧┐Q∧P) ?(┐P∧┐Q∧R)∨F ?┐P∧┐Q∧R ?┐(P∨Q∨┐R)

(2) 解：

a)┐P? P↓P

b)P∨Q?┐(P↓Q) ? (P↓Q)↓(P↓Q)

（ c)P∧Q?┐P↓┐Q? (P↓P)↓(Q↓Q) (3)解：

P→(┐P→Q) ?┐P∨(P∨Q) ?T

?┐P∨P

? (┐P↑┐P)↑(P↑P) ?P↑(P↑P)

P→(┐P→Q) ?┐P∨(P∨Q) ?T

?┐P∨P ?┐(┐P↓P) ?┐((P↓P)↓P)

?((P↓P)↓P)↓((P↓P)↓P) (4)解：

P↑Q

?┐(┐P↓┐Q)

?┐((P↓P)↓(Q↓Q))

? ((P↓P)↓(Q↓Q))↓((P↓P)↓(Q↓Q)) (5)证明：

┐(B↑C)

?┐(┐B∨┐C) ? ┐B↓┐C ┐(B↓C)

?┐(┐B∧┐C) ?┐B↑┐C

(6)解：联结词“↑”和“↓”不满足结合律。举例如下：

a)给出一组指派：P为T，Q为F，R为F，则(P↑Q)↑R为T，P↑(Q↑R)为F ?

故 (P↑Q)↑R P↑(Q↑R).

b)给出一组指派：P为T，Q为F，R为F，则(P↓Q) ↓R为T，P↓(Q

?

↓R)为F

故(P↓Q)↓R P↓(Q↓R). (7)证明：

设变元P，Q，用连结词?,┐作用于P，Q得到：P，Q，┐P，┐Q，P?Q，P?P，Q?Q，Q?P。

但P?Q?Q?P，P?P?Q?Q，故实际有：

P，Q，┐P，┐Q，P?Q，P?P（T） （A） 用┐作用于（A）类，得到扩大的公式类（包括原公式类）： P，Q，┐P，┐Q，┐（P?Q）， T，F， P?Q （B） 用?作用于（A）类，得到：

P?Q，P?┐P?F，P?┐Q?┐（P?Q），P?（P?Q）?Q，P?（P?P）?P，

Q?┐P?┐（P?Q），Q?┐Q?F，Q?（P?Q）?P，Q?T?Q, ┐P?┐Q?P?Q，┐P?（P?Q）?┐Q，┐P?T?┐P, ┐Q?（P?Q）?┐P，┐Q?T?┐Q, （P?Q）?（P?Q）?P?Q. 因此，（A）类使用运算后，仍在（B）类中。 对（B）类使用┐运算得：

┐P，┐Q，P，Q， P?Q， F，T， ┐（P?Q）， 仍在（B）类中。

对（B）类使用?运算得：

P?Q，P?┐P?F，P?┐Q?┐（P?Q），P?┐（P?Q）?┐Q，P?T?P，P?F?┐P，P?（P?Q）?Q， Q?┐P?┐（P?Q），Q?┐Q?F，Q?┐（P?Q）?┐P，Q?T?Q, Q?F?┐Q， Q?（P?Q）?P，

┐P?┐Q?P?Q，┐P?┐（P?Q）?Q，┐P?T?┐P, ┐P?F?P,┐P?（P?Q）?┐Q，

┐Q?┐（P?Q）?P，┐Q?T?┐Q, ┐Q?T?┐Q,┐Q?（P?Q）?┐P， ┐（P?Q）?T?┐（P?Q），┐（P?Q）?F?P?Q，┐（P?Q）?（P?Q）?F

T?F?F，T?（P?Q）? P?Q

F?（P?Q）? ┐（P?Q） （P?Q）?（P?Q）?P?Q.

故由（B）类使用?运算后，结果仍在（B）中。

由上证明：用?,┐两个连结词，反复作用在两个变元的公式中，结果只能产生（B）类中的公式，总共仅八个不同的公式，故{?,┐}不是功能完备的，更不能是最小联结词组。 ∨ 已证{?,┐}不是最小联结词组，又因为P Q? ┐（P?Q），故任何命题公式中的联结词，如仅用{ , ┐}表达，则必可用{?,┐}表达，∨ ∨ ? (P∨┐Q)∧(P∨Q)∧(┐P∨Q) (2) 解：

a) (┐P∧Q)→R

?┐(┐P∧Q)∨R ? P∨┐Q∨R

?(P∧Q)∨(P∧┐Q) ∨(┐Q∧R)∨(┐Q∧┐R)∨(R∧P)∨(R∧┐P)

b) P→((Q∧R)→S)

其逆亦真。故{ , ┐}也必不是最小联结词组。 (8)证明{∨}，{∧}和{→}不是最小联结词组。 证明：若{∨}，{∧}和{→}是最小联结词，则 ┐P?（P∨P∨??） ┐P?（P∧P∧??） ┐P?P→(P→(P→??)

对所有命题变元指派T，则等价式左边为F，右边为T，与等价表达式矛盾。

所以{∨}，{∧}和{→}不是最小联结词。

(9)证明{┐,→}和→c{

┐, }是最小联结词组。 证明：因为{┐,∨}为最小联结词组，且P∨Q?┐P→Q

所以{┐,→}是功能完备的联结词组，又{┐},{→}都不是功能完备的联结词组。

所以{┐,→}是最小联结词组。又因为P→Q?→c

┐ (P Q)，所以→c {┐, }是功能完备的联结词组，又→c

{┐},{ }不是功能完备的联结词组，

所以{┐→c, }

是最小联结词组。

习题 1-7 (1) 解：

P∧(P→Q)

?P∧(┐P∨Q)

? (P∧┐P)∨(P∧Q) P∧(P→Q)

? (P∨(┐Q∧Q))∧(┐P∨Q) ?┐P∨(┐(Q∧R)∨S) ?┐P∨┐Q∨┐R∨S

?(┐P∧Q)∨(┐P∧┐Q) ∨(┐Q∧R)∨(┐Q∧┐R)∨(┐R∧S)∨(┐R∧┐S)∨(S∧P)∨(S∧┐P) c) ┐(P∨┐Q)∧(S→T)

?(┐P∧Q)∧(┐S∨T)

?(┐P∧Q∧┐S)∨(┐P∧Q∧T) d) (P→Q)→R

?┐(┐P∨Q)∨R ?(P∧┐Q)∨R

?(P∨R)∧(┐Q∨R) e) ┐(P∧Q)∧(P∨Q)

?(┐P∨┐Q)∧(P∨Q)

?(┐P∧P)∨(┐P∧Q)∨(┐Q∧P)∨(┐Q∧Q) ? (┐P∧Q)∨(┐Q∧P) (3) 解：

a) P∨(┐P∧Q∧R)

?(P∨┐P)∧(P∨Q)∧(P∨R) ?(P∨Q)∧(P∨R) b) ┐(P→Q)∨(P∨Q) ?┐(┐P∨Q)∨(P∨Q) ?(P∧┐Q)∨(P∨Q)

?(P∨P∨Q)∧(┐Q∨P∨Q) c) ┐(P→Q) ?┐(┐P∨Q)

? P∧┐Q ?(P∨Q)∧(P∨┐Q)∧(┐Q∨┐P) d) (P→Q)→R ?┐(┐P∨Q)∨R ? (P∧┐Q)∨R ? (P∨R)∧(┐Q∨R) e) (┐P∧Q)∨(P∧┐Q) ?(┐P∨P)∧(┐P∨┐Q)∧(Q∨P)∧(Q∨┐Q) ?(┐P∨┐Q)∧(Q∨P) 解： a) (┐P∨┐Q)→(P?┐Q) ?┐(┐P∨┐Q) ∨(P?┐Q) ? (P∧Q) ∨(P∧┐Q)∨(┐P∧Q) ??1，2，3 ?P∨Q=?0 b) Q∧(P∨┐Q) ? (P∧Q)∨(Q∧┐Q) ? P∧Q =?3 ??0，1，2 ?(P∨Q)∧(P∨┐Q) ∧(┐P∨Q) c) P∨(┐P→(Q∨(┐Q→R)) ?P∨(P∨(Q∨(Q∨R)) ?P∨Q∨R=?0 ??1，2，3,4,5,6,7 =(┐P∧┐Q∧R) ∨(┐P∧Q∧┐R) ∨(┐P∧Q∧R) ∨(P∧┐Q∧┐R) ∨(P∧┐Q∧R) ∨(P∧Q∧┐R) ∨(P∧Q∧R) d) (P→(Q∧R) )∧(┐P→(┐Q∧┐R)) ? (┐P∨(Q∧R)) ∧(P∨(┐Q∧┐R)) ? (P∧┐P) ∨(P∧(Q∧R)) ∨ ((┐Q∧┐R) ∧┐P) ∨((┐Q∧┐R) ∧(Q∧R)) ? (P∧Q∧R) ∨(┐P∧┐Q∧┐R) =?0,7 ??1，2，3,4,5,6?? (P∨Q∨┐R) ∧(P∨┐Q∨R) ∧(P∨┐Q∨┐R) ∧(┐P∨Q∨R) ∧(┐P∨Q∨┐R) ∧(┐P∨┐Q∨R) e) P→(P∧(Q→P) ?┐P∨(P∧(┐Q∨P) ?(┐P∨P)∧(┐P∨┐Q∨P) ?T∨(T∧┐Q) ?T ??0,1,2,3= (┐P∧┐Q) ∨(┐P∧Q) ∨(P∧┐Q) ∨(P∧Q) f) (Q→P) ∧(┐P∧Q) ? (┐Q∨P) ∧┐P∧Q ? (┐Q∨P) ∧┐(P∨┐Q) ?F

??0,1，2，3= (P∨Q) ∧(P∨┐Q) ∧(┐P∨Q) ∧(┐P∨┐Q)证明： a) (A→B) ∧(A→C) ? (┐A∨B) ∧(┐A∨C) A→(B∧C) ?┐A∨(B∧C) ? (┐A∨B) ∧(┐A∨C) b) (A→B) →(A∧B) ?┐(┐A∨B) ∨(A∧B) ? (A∧┐B) ∨(A∧B) ?A∧(B∨┐B) ?A∧T ?A (┐A→B) ∧(B→A) ? (A∨B) ∧(┐B∨A) ?A∨(B∧┐B) ?A∨F ?A c) A∧B∧(┐A∨┐B) ? ((A∧┐A)∨(A∧┐B))∧B ?A∧B∧┐B

(4)

(5) ?F

┐A∧┐B∧(A∨B)

? ((┐A∧A)∨(┐A∧B))∧┐B ?┐A∧┐B∧B ?F d)

A∨(A→(A∧B) ?A∨┐A∨(A∧B) ?T

┐A∨┐B∨(A∧B) ?┐(A∧B) ∨(A∧B) ?T

(6)解：A?R↑(Q∧┐(R↓P)),则A*? R↓(Q∨┐(R↑P))

A?R↑(Q∧┐(R↓P)) ?┐(R∧(Q∧(R∨P))) ?┐R∨┐Q∨┐(R∨P) ?┐(R∧Q) ∨┐(R∨P) A*?R↓(Q∨┐(R↑P)) ?┐(R∨(Q∨(R∧P)) ?┐R∧┐Q∧┐(R∧P) ?┐(R∨Q) ∧┐(R∧P)

(7) 解：设A：A去出差。B：B去出差。C：C去出差。D：D去出差。若A去则C和D中要去一个。 A→(CVD) B和C不能都去。 ┐(B∧C) C去则D要留下。 C→┐D

按题意应有：A→(CVD)，┐(B∧C)，C→┐D必须同时成立。 因为CVD ? (C∧┐D) ∨(D∧┐C) 故(A→(CVD))∧┐(B∧C) ∧(C→┐D)

? (┐A∨(C∧┐D) ∨(D∧┐C)) ∧┐(B∧C) ∧(┐C∨┐D)

? (┐A∨(C∧┐D) ∨(D∧┐C)) ∧(┐B∨┐C) ∧(┐C∨┐D) ? (┐A∨(C∧┐D) ∨(D∧┐C)) ∧((┐B∧┐C) ∨(┐B∧┐D) ∨(┐C∧┐D) ∨┐C)

? (┐A∧┐B∧┐C) ∨(┐A∧┐B∧┐D) ∨(┐A∧┐C∧┐D) ∨(┐A∧┐C)

∨(┐B∧┐C∧D) ∨(┐C∧D∧┐B∧┐D) ∨(┐C∧D∧┐C∧┐D) ∨(┐C∧D∧┐C) ∨(┐D∧C∧┐B∧┐C) ∨(┐D∧C∧┐B∧┐D) ∨(┐D∧C∧┐C∧┐D) ∨(┐D∧C∧┐C)

在上述的析取范式中，有些（画线的）不符合题意，舍弃，得 (┐A∧┐C) ∨(┐B∧┐C∧D) ∨（┐C∧D）∨(┐D∧C∧┐B) 故分派的方法为：B∧D ,或 D∧A,或 C∧A。

(8) 解：设P：A是第一。Q：B是第二。R：C是第二。S：D是第四。E：A是第二。

由题意得 (PVQ) ∧(RVS) ∧(EVS)

? ((P∧┐Q) ∨(┐P∧Q)) ∧((R∧┐S) ∨(┐R∧S)) ∧((E∧┐S) ∨(┐E∧S))

? ((P∧┐Q∧R∧┐S) ∨(P∧┐Q∧┐R∧S) ∨(┐P∧Q∧R∧┐S) ∨(┐P∧Q∧┐R∧S))∧((E∧┐S)∨(┐E∧S))

因为 (P∧┐Q∧┐R∧S)与(┐P∧Q∧R∧┐S)不合题意，所以原式可化为

((P∧┐Q∧R∧┐S) ∨(┐P∧Q∧┐R∧S))∧((E∧┐S) ∨(┐E∧S))

? (P∧┐Q∧R∧┐S∧E∧┐S) ∨(P∧┐Q∧R∧┐S∧┐E∧S) ∨(┐P∧Q∧┐R∧S∧E∧┐S)∨(┐P∧Q∧┐R∧S∧┐E∧S) ? (P∧┐Q∧R∧┐S∧E) ∨(┐P∧Q∧┐R∧S∧┐E) 因R与E矛盾，故┐P∧Q∧┐R∧S∧┐E为真，

即A不是第一，B是第二，C不是第二，D为第四，A不是第二。 于是得： A是第三 B是第二 C是第一 D是第四。

习题1-8 (1)证明：

a)┐(P∧┐Q)，┐Q∨R，┐R?┐P

(1) ┐R P (2) ┐Q∨R P

(3) ┐Q (1)(2)T,I (4) ┐(P∧┐Q) P (5) ┐P∨Q (4)T,E (6) ┐P (3)(5)T,I

b)J→(M∨N)，(H∨G)→J，H∨G?M∨N (1) (H∨G) →J P (2) (H∨G) P

(3) J (1)(2)T,I (4) J→(M∨N) P (5) M∨N (3)(4)T,I c)B∧C，(B?C)→(H∨G)?G∨H (1) B∧C P (2) B (1)T,I (3) C (1)T,I (4) B∨┐C (2)T,I (5) C∨┐B (3)T,I (6) C→B (4)T,E (7) B→C (5)T,E (8) B?C (6)(7)T,E (9) (B?C) →(H∨G) P (10) H∨G (8)(9)T,I

d)P→Q，(┐Q∨R)∧┐R，┐(┐P∧S)?┐S (1) (┐Q∨R) ∧┐R (2) ┐Q∨R (1)T,I (3) ┐R (1)T,I (4) ┐Q (2)(3)T,I (5) P→Q P

(6) ┐P (4)(5)T,I (7) ┐(┐P∧┐S) P (8) P∨┐S (7)T,E (9) ┐S (6)(8)T,I (2) 证明：

a)┐A∨B，C→┐B?A→┐C

(1) ┐(A→┐C) P (2) A (1)T,I (3) C (1)T,I (4) ┐A∨B P

(5) B (2)(4)T,I (6) C→┐B P

(7) ┐B (3)(6)T,I (8) B∧┐B 矛盾。(5),(7)

b)A→(B→C)，(C∧D)→E，┐F→(D∧┐E)?A→(B→F) (1) ┐(A→(B→F)) P (2) A (1)T,I (3) ┐(B→F) (1)T,I (4) B (3)T,I (5) ┐F (3)T, (6) A→(B→C) P

(7) B→C (2)(6)T,I (8) C (4)(7)T,I (9) ┐F→(D∧┐E) P

(10) D∧┐E (5)(9)T,I (11) D (10)T,I (12) C∧D (8)(11)T,I (13) (C∧D) →E P

(14) E (12)(13)T,I (15) ┐E (10)T,I

(16) E∧┐E 矛盾。(14),(15) c)A∨B→C∧D，D∨E→F?A→F

(1) ┐(A→F) P (2) A (1)T,I (3) ┐F (1)T,I (4) A∨B (2)T,I (5) (A∨B) →C∧D P

(6) C∧D (4)(5)T,I (7) C (6)T,I (8) D (6)T,I (9) D∨E (8)T,I (10) D∨E→F P

(11) F (9)(10)T,I (12) F∧┐F 矛盾。(3),(11)

d)A→(B∧C)，┐B∨D，(E→┐F)→┐D，B→(A∧┐E)?B→E (1) ┐(B→E) P (2) B (1)T,I (3) ┐E (1)T,I (4) ┐B∨D P

(5) D (2)(4)T,I (6) (E→┐F) →┐D P

(7) ┐(E→┐F) (5)(6)T,I (8) E (7)T,I (9) E∧┐E 矛盾

e)(A→B)∧(C→D)，(B→E)∧(D→F)，┐(E∧F)，A→C?┐A (1) (A→B) ∧(C→D) P (2) A→B (1)T,I (3) (B→E) ∧(D→F) P (4) B→E (3)T,I (5) A→E (2)(4)T,I (6) ┐(E∧F) P (7) ┐E∨┐F (6)T,E (8) E→┐F (7)T,E (9) A→┐F (5)(8)T,I (10) C→D (1)T,I (11) D→F (3)T,I

(12) C→F (10)(10)T,I (13) A→C P

(14) A→F (13)(12)T,I (15) ┐F→┐A (14)T,E (16) A→┐A (9)(15)T,I (17) ┐A∨┐A (16)T,E (18) ┐A (17) T,E (3) 证明：

a)┐A∨B，C→┐B?A→┐C

(1) A P (2) ┐A∨B P

(3) B (1)(2)T,I (4) C→┐B P

(5) ┐C (3)(4)T,I (6) A→┐C CP

b)A→(B→C)，(C∧D)→E，┐F→(D∧┐E)?A→(B→F)

(1) A P (2) A→(B→C) P

(3) B→C (1)(2)T,I (4) B P

(5) C (3)(4)T,I (6) (C∧D) →E P (7) C→(D→E) (6)T,E (8) D→E (5)(7)T,I (9) ┐D∨E (8)T,E (10) ┐(D∧┐E) (9)T,E (11) ┐F→(D∧┐E) P

(12) F (10)(11)T,I (13) B→F CP (14) A→(B→F) CP c)A∨B→C∧D，D∨E→F?A→F

(1) A P

(2) A∨B (1)T,I (3) A∨B→C∨D P

(4) C∧D (2)(3)T,I (5) D (4)T,I (6) D∨E (5)T,I

(7) D∨E→F P

(8) F (6)(7)T,I (9) A→F CP

d)A→(B∧C)，┐B∨D，(E→┐F)→┐D，B→(A∧┐E)?B→E

(1) B P(附加前提) (2) ┐B∨D P

(3) D (1)(2)T,I (4) (E→┐F)→┐D P

(5) ┐(E→┐F) (3)(4)T,I (6) E (5)T,I (7) B→E CP (4)证明：

a) R→┐Q，R∨S，S→┐Q，P→Q?┐P (1) R→┐Q P (2) R∨S P (3) S→┐Q P

(4) ┐Q (1)(2)(3)T,I (5) P→Q P

(6) ┐P (4)(5)T,I b) S→┐Q，S∨R，┐R，┐P?Q?P 证法一：

(1) S∨R P (2) ┐R P

(3) S (1)(2)T,I (4) S→┐Q P (5) ┐Q (3)(4)T,I (6) ┐P?Q P (7)(┐P→Q)∧(Q→┐P) (6)T,E (8) ┐P→Q (7)T,I (9) P (5)(8)T,I 证法二：（反证法）

(1) ┐P P（附加前提） (2) ┐P?Q P

(3)（┐P→Q）∧（ Q→┐P） (2)T，E (4) ┐P→Q (3)T,I (5) Q (1)(4)T,I (6) S→┐Q P

(7) ┐S (5)(6)T,I (8) S∨R P

(9) R (7)(8)T,I (10) ┐R P

(11) ┐R∧R 矛盾（9）（10）T，I c)┐(P→Q)→┐(R∨S)，((Q→P)∨┐R)，R?P?Q (1) R P (2) (Q→P) ∨┐R P

(3) Q→P (1)(2)T,I (4)┐(P→Q) →┐(R∨S) P (5) (R∨S) →(P→Q) (4)T,E (6) R∨S (1)T,I (7) P→Q (5)(6) (8) (P→Q) ∧(Q→P) (3)(7)T,I (9) P?Q (8)T,E (5) 解：

a) 设P：我跑步。Q：我很疲劳。 前提为：P→Q，┐Q

(1) P→Q P (2) ┐Q P (3) ┐P (1)(2)T,I 结论为：┐P，我没有跑步。

b) 设S：他犯了错误。 R：他神色慌张。 前提为：S→R，R

因为（S→R）∧R?（┐S∨R）∧R?R。故本题没有确定的结论。 实际上，若S →R为真，R为真,则S可为真，S也可为假，故无有效结论。

c) 设P：我的程序通过。 Q：我很快乐。

R：阳光很好。 S：天很暖和。（把晚上十一点理解为阳光不

好）

前提为：P→Q，Q→R，┐R∧S

(1) P→Q P (2) Q→R P

(3) P→R (1)(2)T,I (4) ┐R∨S P

(5) ┐R (4)T,I (6) ┐P (3)(5)T,I

结论为： ┐P，我的程序没有通过

习题2-1,2-2 （1） 解：

a) 设W（x）：x是工人。c：小张。 则有 ?W（c） b) 设S（x）：x是田径运动员。B（x）：x是球类运动员。h：他则有 S（h）?B（h） c) 设C（x）：x是聪明的。B（x）：x是美丽的。l：小莉。 则有 C（l）? B（l） d）设O（x）：x是奇数。 则有 O（m）?? O（2m）。 e)设R（x）：x是实数。Q（x）：x是有理数。 则有 （?x）（Q（x）?R（x）） f) 设R（x）：x是实数。Q（x）：x是有理数。 则有 （?x）（R（x）?Q（x）） g) 设R（x）：x是实数。Q（x）：x是有理数。 则有 ?（?x）（R（x）?Q（x）） h)设P（x，y）：直线x平行于直线y G（x，y）：直线x相交于直线y。 则有 P（A，B）??G（A，B） （2） 解：

a) 设J(x)：x是教练员。L(x)：x是运动员。 则有 （?x）（J（x）?L（x））

b) 设S(x)：x是大学生。L(x)：x是运动员。 则有 （?x）（L（x）?S（x））

c) 设J(x)：x是教练员。O(x)：x是年老的。V（x）：x是健壮的。 则有 （?x）（J（x）?O（x）?V（x）） d) 设O(x)：x是年老的。V（x）：x是健壮的。j：金教练 则有 ? O（j）??V（j）

e) 设L(x)：x是运动员。J(x)：x是教练员。 则 ?（?x）（L（x）?J（x））

本题亦可理解为：某些运动员不是教练。 故 （?x）（L（x）??J（x）） f) 设S（x）：x是大学生。L（x）：x是运动员。C（x）：x是国家选手。 则有 （?x）（S（x）?L（x）?C（x）） g) 设C（x）：x是国家选手。V（x）：x是健壮的。 则有 （?x）（C（x）?V（x））或?（?x）（C（x）??V（x）） h) 设C（x）：x是国家选手。O（x）：x是老的。L（x）：x 是运动员。 则有 （?x）（O（x）?C（x）?L（x）） i) 设W（x）：x是女同志。H（x）：x是家庭妇女。C（x）：x是国家选手。

则有 ?（?x）（W（x）?C（x）?H（x）） j）W（x）：x是女同志。J（x）：x是教练。C（x）：x是国家选手。 则有（?x）（W（x）?J（x）?C（x）） k）L（x）：x 是运动员。J（y）：y是教练。A(x,y)：x钦佩y。 则有 （?x）（L（x）? （?y）（J（y）?A（x，y））） l）设S（x）：x是大学生。L（x）：x 是运动员。A(x,y)：x钦佩y。 则（?x）（S（x）?（?y）（L（y）?? A(x,y)））

习题2-3 （1）解：

a）5是质数。

b）2是偶数且2是质数。

c）对所有的x，若x能被2除尽，则x是偶数。 d）存在x，x是偶数，且x能除尽6。（即某些偶数能除尽6） e）对所有的x，若x不是偶数，则x不能被2除尽。

f）对所有的x，若x是偶数，则对所有的y，若x能除尽y，则y也是偶数。

g）对所有的x，若x是质数，则存在y，y是偶数且x能除尽y（即所有质数能除尽某些偶数）。

h）对所有的x，若x是奇数，则对所有y，y是质数，则x不能除尽y（即任何奇数不能除尽任何质数）。 （2）解：（?x）(?y)((P(x)∧P(y)∧┐E(x,y)→(?!z)(L(z)∧R(x,y,z))) 或 （?x）(?y)((P(x)∧P(y)∧┐E(x,y)→(?z)(L(z)∧R(x,y,z) ∧┐(?u)(┐E(z,u) ∧L(u)∧R(x,y,u)))) （3）解：

a) 设N(x):x是有限个数的乘积。 z(y):y为0。

P(x):x的乘积为零。 F(y):y是乘积中的一个因子。

则有 (?x)((N(x)∧P(x)→(?y)(F(y)∧z(y)))

b) 设R(x):x是实数。Q(x,y):y大于x。 故 (?x)(R(x)→(?y)(Q(x,y)∧R(y)))

c) R(x):x是实数。G(x,y):x大于y。 则 (?x)(?y)(?z)(R(x)∧R(y)∧R(z)∧G(x+y,x·z)

（4）解：设G(x,y):x大于y。则有 (?x)(?y)(?z)(G(y,x) ∧G(0,z)→G(x·z,y·z))

（5）解：设N(x):x是一个数。 S(x,y):y是x的后继数。E(x,y)：x=y.则

a) (?x)(N(x)→(?!y)(N(y)∧S(x,y)))

或(?x)(N(x)→(?y)(N(y)∧S(x,y) ∧┐(?z)(┐E(y,z) ∧N(z)∧S(x,z))))

b) ┐(?x)(N(x)∧S(x,1))

c) (?x)(N(x)∧┐S(x,2)→(?!y)(N(y) ∧S(y,x)))

或(?x)(N(x)∧┐S(x,2)→(?y)(N(y) ∧S(y,x) ∧┐(?z)(┐E(y,z) ∧N(z)∧S(z,x))))

（6）解：设S(x):x是大学生。 E(x):x是戴眼睛的。

F(x):x是用功的。 R(x,y):x在看y。

G(y):y是大的。 K(y):y是厚的。 J(y):y是巨著。 a:这

本。 b:那位。

则有 E(b)∧F(b)∧S(b)∧R(b,a)∧G(a)∧K(a)∧J(a)

（7）解：设P(x,y):x在y连续。 Q(x,y):x>y。则

P(f,a)?((?ε)(?δ)(?x)(Q(ε,0)→(Q(δ,0)∧Q(δ,|x-a|)→Q(ε,|f(x)-f(a)|))))

习题2-4

(1) 解：a) x是约束变元，y是自由变元。 b) x是约束变元，P(x)∧Q(x)中的x受全称量词?的约束，S(x)中的x受存在量词?的约束。

c) x，y都是约束变元,P(x)中的x受?的约束，R(x)中的x受?的约束。 d) x，y是约束变元，z是自由变元。 (2) 解：a) P(a)∧P(b)∧P(c) b) R(a)∧R(b)∧R(c)∧S(a)∧S(b)∧S(c) c) (P(a)→Q(a))∧(P(b)→Q(b))∧(P(c)→Q(c) d) (┐P(a)∧┐P(b)∧┐P(c))∨(P(z)∧P(b)∧P(c)) e) (R(a)∧R(b)∧R(c))∧(S(a)∨S(b)∨S(c)) (3) 解： a) (?x)(P(x)∨Q(x))?(P(1)∨Q(1))∧(P(2)∨Q(2))， 但P(1)为T，Q(1)为F，P(2)为F，Q(2)为T,所以 (?x)(P(x)∨Q(x))?(T∨F)∧(F∨T)??T。 b) (?x)(P→Q(x))∨R(a)? ((P→Q(?2))∧(P→Q(3))∧(P→Q(6)))∨R(a) 因为P 为T，Q(?2)为T，Q(3)为T，Q(6)为F，R(5)为F，所以 (?x)(P→Q(x))∨R(a)? ((T→T)∧(T→T)∧(T→F))∨F? F (4) 解：a) (?u)(?v)(P(u，z)→Q(v))?S(x，y) b) (?u)(P(u)→ (R(u)∨Q(u))∧(?v)R(v))→(?z)S(x,z) (5) 解：a) ((?y)A(u，y)→(?x)B(x，v))∧(?x)(?z)C(x，t，z) b) ((?y)P(u，y)∧(?z)Q(u，z))∨(?x)R(x，t)

习题2-5 （1）解： a) P(a,f(a))∧P(b,f(b))?P(1,f(1))∧P(2,f(2))?P(1,2)∧P(2,1)??T∧F?F

b) (?x)(?y)P(y,x)? (?x) (P(1,x)∨P(2,x))? (P(1,1)∨P(2,1))∧(P(1,2)∨P(2,2))

? (T∨F)∧(T∨F)?? T

c) (?x)( ?y)(P(x,y)→P(f(x),f(y)))??? (?x) ((P(x,1)→P(f(x),f(1)))∧(P(x,2) →P(f(x)f(2))))

? (P(1,1)→P(f(1),f(1)))∧(P(1,2)→P(f(1),f(2))) ∧(P(2,1)→P(f(2),f(1)))∧(P(2,2) →P(f(2),f(2)))

? 前提：对论域中所有x，如果x不是研究生则x是大学生。

对论域中所有x， x不是大学生。

结论：对论域中所有x都是研究生。

(P(1,1)→P(2,2))∧(P(1,2)→P(2,1))∧(P(2,1)→P(1,2))∧(P(2,2)→P(1,1)) ? (T→F∧(T→F)∧(F→T)∧(F→T)?F∧F∧T∧T?F （2）解：a) (?x)(P(x)→Q(f(x),a))??

?(P(1)→Q(f(1),1))∧(P(2)→Q(f(2),1)) ? (F→Q(2,1))∧(T→Q(1,1))??? (F→F)∧(T→T)??T b) (?x)(P(f(x))∧Q(x,f(a))??? (P(f(1))∧Q(1,f(1)))∨(P(f(2))∧Q(2,f(1)) ? (T∧T)(F∧F)??T

c) (?x)(P(x)∧Q(x,a)) ? (P(1)∧Q(1,a))∨(P(2)∧Q(2,a)) ? (P(1)∧Q(1,1))∨(P(2)∧Q(2,1))??? (F∧T)∨(T∧F)??F d) (?x)( ?y)(P(x)∧Q(x,y))??? (?x) (P(x)∧(?y)Q(x,y))??? (?x) (P(x)∧(Q(x,1)∨Q(x,2))) ? (P(1)∧(Q(1,1)∨Q(1,2)))∧(P(2)∧(Q(2,1)∨Q(2,2))) ? (F∧(T∨T))∧(T∧(F∨F))??F

(3) 举例说明下列各蕴含式。

a) ?((?x)(P(x)∧Q(a))? (?x)P(x)??Q(a) b) (?x) (? P(x) ?Q(x)), (?x) ?Q(x)?P(a)

c) (?x) (P(x) ?Q(x)), (?x) (Q(x) ?R(x))? (?x) (P(x) ?R(x)) d) (?x) (P(x) ?Q(x)), (?x) ?P(x)? (?x)Q (x) e) (?x) (P(x) ?Q(x)), (?x) ?P(x)? (?x)Q (x) 解：a）因为?((?x)(P(x)∧Q(a)) ??(?x)P(x)∨?Q(a) 故原式为?(?x)P(x)∨?Q(a) ? (?x)P(x)??Q(a) 设P（x）：x是大学生。Q（x）：x是运动员

前提 或者不存在x，x是大学生，或者a是运动员 结论 如果存在x是大学生，则必有a是运动员。 b)设P（x）：x是研究生。Q（x）：x是大学生。a：论域中的某人。 故，对论域中某个a，必有结论a是研究生，即P（a）成立。 c）设P（x）：x是研究生。Q（x）：x曾读过大学。R（x）：x曾读过中学。

前提 对所有x，如果x是研究生，则x曾读过大学。

对所有x，如果x曾读过大学，则x曾读过中学。

结论：对所有x，如果x是研究生，则x曾读过中学。 d）设P（x）：x是研究生。Q（x）：x是运动员。

前提 对所有x，或者x是研究生，或者x是运动员。

对所有x，x不是研究生

结论 必存在x，x是运动员。 e）设P（x）：x是研究生。Q（x）：x是运动员。

前提 对所有x，或者x是研究生，或者x是运动员。

对所有x，x不是研究生

结论 对所有x，x是运动员。 （4）证明：(?x)(A(x)→B(x))? (?x) (┐A(x)∨B(x)) ? (?x)┐A(x)∨ (?x) B(x)

? ┐(?x)A(x)∨(?x) B(x) ? (?x)A(x)→(?x) B(x)

（5） 设论域D={a，b，c}，求证(?x)A(x)∨(?x)B(x)?( ?x)(A(x)∨B(x)) 证明：因为论域D={a，b，c}，所以

(?x)A(x)∨(?x)B(x) ?(A(a) ∧A(b) ∧A(c)) ∨(B(a) ∧B(b) ∧B(c)) ?(A(a) ∨B(a)) ∧(A(a) ∨B(b)) ∧(A(a) ∨B(c)) ∧(A(b) ∨B(a)) ∧

(A(b) ∨B(b)) ∧(A(b)∨B(c)) ∧(A(c) ∨B(a)) ∧(A(c) ∨B(b)) ∧(A(c) ∨B(c))

?(A(a) ∨B(a)) ∧(A(b) ∨B(b))∧(A(c) ∨B(c)) ?( ?x)(A(x)∨B(x))

所以(?x)A(x)∨(?x)B(x)?( ?x)(A(x)∨B(x)) （6）解：推证不正确，因为

┐(?x)(A(x)∧┐B(x))?┐((?x)A(x)∧(?x)┐B(x)) （7）求证(?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) ?┐(?x)P(x) ∨( ?y)Q(y) ? ( ?x)P(x)→(?y)Q(y)

习题2-6

（1）解：a) (?x)(P(x)→(?y)Q(x,y))

?(?x)( ┐P(x) ∨(?y)Q(x,y)) ?(?x) (?y) (┐P(x) ∨Q(x,y))

b) (?x)(┐((?y)P(x,y))→((?z)Q(z)→R(x))) ?(?x)((?y)P(x,y)∨((?z)Q(z)→R(x)))

?(?x)((?y)P(x,y) ∨(┐(?z)Q(z) ∨R(x))) ?(?x)((?y)P(x,y) ∨((?z)┐Q(z) ∨R(x))) ?(?x) (?y) (?z) ( P(x,y) ∨┐Q(z) ∨R(x))

c)(?x)( ?y)(((?zP(x,y,z)∧(?u)Q(x,u))→(?v)Q(y,v))

?(?x)( ?y)( ┐((?z)P(x,y,z)∧(?u)Q(x,u))∨(?v)Q(y,v)) ?(?x)( ?y)( (?z)┐P(x,y,z) ∨(?u)┐Q(x,u)∨(?v)Q(y,v)) ?(?x)( ?y)( (?z)┐P(x,y,z) ∨(?u)┐Q(x,u)∨(?v)Q(y,v)) ?(?x)( ?y) (?z) (?u) (?v) (┐P(x,y,z) ∨┐Q(x,u)∨Q(y,v)) （2）解：a) ((?x)P(x)∨(?x)Q(x))→(?x)(P(x)∨Q(x))

?┐((?x)P(x)∨(?x)Q(x)) ∨(?x)(P(x)∨Q(x)) ?┐(?x) (P(x)∨Q(x)) ∨(?x)(P(x)∨Q(x)) ?T b) (?x)(P(x)→(?y)((?z)Q(x,y)→┐(?z)R(y,x))) ?(?x)( ┐P(x) ∨(?y)( Q(x,y)→┐R(y,x))) ?(?x) (?y) ( ┐P(x) ∨┐Q(x,y) ∨┐R(y,x)) 前束合取范式

?(?x) (?y)( (P(x) ∧Q(x,y) ∧R(y,x)) ∨(P(x) ∧Q(x,y) ∧┐R(y,x)) ∨ (P(x) ∧┐Q(x,y) ∧R(y,x)) ∨(┐P(x) ∧Q(x,y) ∧R(y,x)) ∨(┐P(x) ∧┐Q(x,y) ∧R(y,x)) ∨( (P(x) ∧┐Q(x,y) ∧┐R(y,x)) ∨(┐P(x) ∧Q(x,y) ∧┐R(y,x))) 前束析取范式

c) (?x)P(x)→(?x)((?z)Q(x,z)∨(?z)R(x,y,z)) ?┐(?x)P(x) ∨(?x)((?z)Q(x,z)∨(?z)R(x,y,z)) ?(?x)┐P(x) ∨(?x)((?z)Q(x,z)∨(?u)R(x,y,u)) ?(?x)(┐P(x) ∨(?z)Q(x,z)∨(?u)R(x,y,u)) ?(?x) (?z) (?u)(┐P(x) ∨Q(x,z)∨R(x,y,u)) 前束合取范式

?(?x) (?z) (?u)(( P(x) ∧Q(x,z) ∧R(x,y,u)) ∨(P(x) ∧Q(x,z) ∧┐R(x,y,u)) ∨(P(x) ∧┐Q(x,z) ∧R(x,y,u)) ∨(P(x) ∧┐Q(x,z) ∧┐R(x,y,u)) ∨(┐P(x) ∧Q(x,z) ∧┐R(x,y,u)) ∨(┐P(x) ∧┐Q(x,z) ∧R(x,y,u)) ∨(┐P(x) ∧┐Q(x,z) ∧┐R(x,y,u))) 前束析取范式

d)(?x)(P(x)→Q(x,y))→((?y)P(y)∧(?z)Q(y,z))

?┐(?x)( ┐P(x) ∨Q(x,y)) ∨((?y)P(y)∧(?z)Q(y,z)) ?(?x)( P(x) ∧┐Q(x,y)) ∨((?u)P(u)∧(?z)Q(y,z)) ?(?x) (?u) (?z) (( P(x) ∧┐Q(x,y)) ∨(P(u)∧Q(y,z))) 前束析取范式

?(?x) (?u) (?z) (( P(x)∨P(u)) ∧ (P(x)∨Q(y,z)) ∧(┐Q(x,y)∨P(u)) ∧ (┐Q(x,y)∨Q(y,z))) 前束合取范式

习题2-7 (1) 证明：

(2) a) ①(?x)(┐A(x)→B(x)) P

②┐A(u)→B(u) US① ③( ?x)┐B(x) P ④┐B(u) US③ ⑤A(u)∨B(u) T②E ⑥A(u) T④⑤I ⑦ ( ?x)A(x) EG⑥

b) ①┐( ?x)(A(x)→B(x)) P（附加前提） ②( ?x)┐(A(x)→B(x)) T①E ③┐(A(c)→B(c)) ES② ④A(c) T③I ⑤┐B(c) T③I ⑥( ?x)A(x) EG④ ⑦ (?x)A(x)→(?x)B(x) P

⑧(?x)B(x) T⑥⑦I ⑨B(c) US⑧ ⑩B(c)∧ ┐B(c) T⑤⑨矛盾 c）①(?x)(A(x)→B(x)) P ②A(u)→B(u) US① ③( ?x)(C(x)→┐B(x)) P ④C(u)→┐B(u) US③ ⑤┐B(u) →┐A(u) T②E ⑥C(u)→┐A(u) T④⑤I ⑦(?x)(C(x)→┐A(x)) UG⑥

d) (?x)(A(x)∨B(x)),( ?x)(B(x)→┐C(x)),( ?x)C(x)? (?x)A(x) ①( ?x)(B(x)→┐C(x)) P

②B(u)→┐C(u) US① ③( ?x)C(x) P

④C(u) US③ ⑤┐B(u) T②④I ⑥ (?x)(A(x)∨B(x)) P ⑦A(u)∨B(u) US

⑧A(u) T⑤⑦I ⑨(?x)A(x) UG⑧ (2) 证明：

a)①( ?x)P(x) P（附加前提）②P(u) US① ③(?x)(P(x)→Q(x)) P ④P(u)→Q(u) US③ ⑤Q(u) T②④I ⑥(?x)Q(x) UG⑤ ⑦( ?x)P(x)→(?x)Q(x) CP b)因为(?x)P(x)∨(?x)Q(x)?┐(?x)P(x) →(?x)Q(x)

故本题就是推证(?x)(P(x)∨Q(x))?? ┐(?x)P(x) →(?x)Q(x) ①┐(?x)P(x) P（附加前提） ②( ?x)┐P(x) T①E ③┐P(c) ES② ④(?x)(P(x)∨Q(x)) P ⑤P(c)∨Q(c) ES④ ⑥Q(c) T③⑤I ⑦( ?x) Q(x) EG⑥ ⑧┐(?x)P(x) →(?x)Q(x) CP (3)

解：a)设R（x）：x是实数。Q（x）：x是有理数。I（x）：x是整数。 本题符号化为：

(?x)(Q(x) →R(x)) ∧(?x)(Q(x) ∧I(x))?? (?x)(R(x) ∧I(x)) ①(?x)(Q(x) ∧I(x)) P ②Q(c) ∧I(c) ES① ③(?x)(Q(x) →R(x)) P

④Q(c) →R(c) US③ ⑤Q(c) T②I ⑥ R(c) T④⑤I ⑦I(c) T②I ⑧R(c)∧I(c) T⑥⑦I ⑨(?x)(R(x) ∧I(x)) EG⑧ b)设P（x）：x喜欢步行。Q（x）：x喜欢乘汽车。R（x）：x喜欢骑自行车

本题符号化为：

(?x)(P(x) →┐Q(x)), (?x)(Q(x) ∨R(x)) , (?x) ┐R(x)?? (?x) ┐P(x) ①(?x) ┐R(x) P ②┐R (c) ES① ③(?x)(Q(x) ∨R(x)) P ④Q(c) ∨R(c) US③

⑤Q(c) T②④I ⑥ (?x)(P(x) →┐Q(x)) P ⑦P(c) →┐Q(c) US⑥ ⑧┐P (c) T⑤⑦I ⑨(?x) ┐P(x) EG⑧

c) 每个大学生不是文科学生就是理工科学生，有的大学生是优等生，小张不是理工科学生，但他是优等生，因而如果小张是大学生，他就是文科学生。 设G（x）：x是大学生。L（x）：x是文科学生。P（x）：x是理工科学生。S（x）：x是优秀生。c：小张。 本题符号化为：

(?x)(G(x) →L(x)∨P(x)), (?x)(G(x) ∧ S(x)), ┐P (c) , S(c) ? G(c) →L(c)

①G(c) P（附加前提） ②(?x)(G(x) →L(x)∨P(x)) P ③G(c) →L(c)∨P(c) US② ④L(c)∨P(c) T①③I ⑤┐P (c) P

⑥ L(c) T④⑤I ⑦G(c) →L(c) CP 注意：本题推证过程中未用到前提(?x)(G(x) ∧ S(x))以及S(c)。主要是S（x）：x是优秀生，这个条件与其他前提的联系对证明结论没有影响，因S（x）与其他前提不矛盾，故本题的推证仍是有效的。

3-5.1 列出所有从X={a,b,c}到Y={s}的关系。 解：Z1={} Z2={} Z3={} Z4={,} Z5={,} Z6={,} Z7={,,} 3-5.2 在一个有n个元素的集合上，可以有多少种不同的关系。 解 因为在X中的任何二元关系都是X×X的子集，而X×X=X2中共有n2个元素，取0个到n2个元素，共可组成2n2个子集，即|?(X?X)|?2n2。 3-5.3 设A＝{6：00，6：30,7：30，?, 9：30,10：30}表示在晚上每隔半小时的九个时刻的集合，设B={3,12,15,17}表示本地四个电视频道的集合,设R1和R2是从A到B的两个二元关系，对于二无关系R1，R2，R1∪R2，R1∩R2，R1?R2和R1-R2可分别得出怎样的解释。 解：A×B表示在晚上九个时刻和四个电视频道所组成的电视节目表。 R1和R2分别是A×B的两个子集，例如R1表示音乐节目播出的时间表，R2是戏曲节日的播出时间表，则R1∪R2表示音乐或戏曲节目的播出时间表，R1∩R2表示音乐和戏曲一起播出的时间表，R1?R2表示音乐节目表以及戏曲节目表，但不是音乐和戏曲一起的节日表，R1-R2表示不是戏曲时间的音乐节目时间麦。 3-5.4 设L表示关系“小于或等于”，D表示‘整除”关系,L和D刀均定义于{1,2,3,6}，分别写出L和D的所有元素并求出L∩D. 解：L={<1,2>,<1,3>,<1,6>,<2,3>,<2,6>, <3,6>,<1,1>,<2,2>,<3,3>,<6,6>} D={<1,2>,<1,3>,<1,6>,<2,6>,<3,6>,<1,1>,<2,2>,<3,3>,<6,6>} L∩D= {<1,2>,<1,3>,<1,6>,<2,6>,<3,6>,<1,1>,<2,2>,<3,3>,<6,6>} 3-5.5对下列每一式，给出A上的二元关系，试给出关系图： a){|0?x∧y?3}，这里A={1,2,3,4}； b){|2?x,y?7且x除尽y,这里A＝{n|n?N∧n?10} c) {|0?x-y<3}，这里A={0,1,2,3,4}； d){|x,y是互质的}，这里A={2,3,4,5,6} 解： a) R={<0,0>,<0,1>,<0,2>,<0,3>, <1,0>,<1,1>,<1,2>,<1,3>, <2,0>,<2,1>,<2,2>,<2,3>, <3,0>,<3,1>,<3,2>,<3,3>,} 其关系图 b) R={<2,0>,<2,2>,<2,4>,<2,6>, <3,0>,<3,3>,<3,6>, <4,0>,<4,4>, <5,0>,<5,5>, <6,0>,<6,6>, <7,0>,<7,7>} 3-6.1 分析集合A={1，2，3}上的下述五个关系： （1）R={＜1，1＞，＜1，2＞，＜1，3＞，＜3，3＞}； （2）S={＜1，1＞，＜1，2＞，＜2，1＞，＜2，2＞，＜3，3＞}； （3）T={＜1，1＞，＜1，2＞，＜2，2＞，＜2，3＞}； （4）?=空关系； （5）A×A=全域关系。 判断A中的上述关系是否为a）自反的，b）对称的，c）可传递的，d）反对称的。 解（1）R是可传递和反对称的。 （2）S是自反，对称和可传递的。 （3）T是反对称的。 （4）空关系是对称，可传递和反对称的。 （5）全域关系是自反，对称和可传递的。 3-6.2给定A={1，2，3,4}，考虑a上的关系R,若R={＜1，3＞，＜1，4＞，＜2，3＞，＜2，4＞，＜3，4＞} a) 在A?A的坐标图上标出R，并绘出它的关系图； b) R是ⅰ)自反的ⅱ）对称的ⅲ)可传递的，iv) 反对称的吗？ 解 a） 1 2 4 3 R是可传递的的和反对称的；但不是自反的和对称的。 3-6.3 举出A={1，2，3}上关系R的例子，使其具有下述性质： a）既是对称的，又是反对称的； b）R既不是对称的，又不是反对称的； c）R是可传递的。 解 a）R={＜1，1＞，＜2，2＞，＜3，3＞} b）R={＜1，2＞，＜2，1＞，＜2，3＞} c) R={＜1，2＞，＜2，1＞，＜1，1＞，＜2，2＞，＜3，3＞} 3-6.4 如果关系R和S是自反的，对称的和可传递的，证明R∩S也是自反，对称和可传递的。 证明 设R和S是X上的自反的，对称的和可传递的关系。 1）对任意x?X，有＜x，x＞?R和＜x，x＞?S，所以＜x，x＞?R∩S，即R∩S在X上是自反的。 2）对任意的＜x，y＞?R∩S，有＜x，y＞?R∧＜x，y＞?S，因为R和S是对称的，故必有＜y，x＞?R∧＜y，x＞?S。即＜y，x＞?R∩S，所以R∩S在X上是对称的。 3）对任意的＜x，y＞?R∩S∧＜y，z＞?R∩S，则有 ＜x，y＞?R∧＜x，y＞?S∧＜y，z＞?R∧＜y，z＞?S 因为R和S是传递的，故得＜x，z＞?R∧＜x，z＞?S，即＜x，z＞?R∩S，所以R∩S在X上是传递的。 3-6.5给定S={1，2，3，4}和S上关系：R={＜1，2＞，＜4，3＞，＜2，2＞，＜2，1＞，＜3，1＞} 说明R是不可传递的，找出关系R1?R，使得R1是可传递的，还能找出另一个3-7.1设R1和R2是A上的任意关系，说明以下命题的真假并予以证明。 a）若R1和R2是自反的，则R1○R2也是自反的； b）若R1和R2是反自反的，则R1○R2也是反自反的； c）若R1和R2是对称的，则R1○R2也是对称的； d）若R1和R2是传递的，则R1○R2也是传递的。 证明 a）对任意a∈A，设R1和R2是自反的，则＜a，a＞∈R1，＜a，a＞∈R2 所以，＜a，a＞∈R1○R2，即R1○R2也是自反的。 b）假。例如：设A={a，b}，有R1={＜a，b＞}与R2={＜b，a＞} R1和R2是反自反的。但R1○R2={＜a，a＞}，所以R1○R2在A上不是反自反的。 c)假。例如：设A={a，b，c}，有 R1={＜a，b＞，＜b，a＞，＜c，c＞}，R2={＜b，c＞，＜c，b＞} R1和R2是对称的，但R 1○R2={＜a，c＞，＜c，b＞} 所以，R1○R2不是对称的。 d）假。例如：设A={a，b，c}，有 R1={＜a，b＞，＜b，c＞，＜a，c＞}，R2={＜b，c＞，＜c，a＞，＜b，a＞} 则R1，R2都是传递的。但R 1○R2={＜a，c＞，＜a，a＞，＜b，a＞} 所以，R1○R2不是传递的。 3-7.2 证明 若S为集合X上的二元关系： a）S是传递的，当且仅当（S○S）?S； b）S是自反的，当且仅当IX?S； c）证明定理3-7.3（b）（即S是反对称的，当且仅当S∩Sc?IX）。 证明 a）设S为传递的，若＜x，z＞∈S○S，则存在某个y∈X，使得＜x，y＞∈S，且＜y，z＞∈S。 若S是传递的，＜x，z＞∈S，所以（S○S）?S。 反之，设（S○S）?S ，假定＜x，y＞∈S且＜y，z＞∈S，则＜x，z＞∈S○S。因为（S○S）?S，故＜x，z＞∈S，得到S是传递的。 b）设S是自反的，令＜x，y＞∈IX，则x=y。但＜x，x＞∈S，因此＜x，y＞=＜x，x＞∈S，得IX?S。 反之，令IX?S，设任意x∈X，＜x，x＞∈IX，故＜x，x＞∈S，因此S是自反的。 c）设S是反对称的。假定＜x，y＞∈S∩Sc，则 ＜x，y＞∈S∧＜x，y＞∈Sc?＜x，y＞∈S∧＜y，x＞∈S 因为S是反对称的，故x＝y， 所以＜x，y＞＝＜x，x＞∈IX，即S∩Sc?IX。 反之，若S∩Sc?IX，设＜x，y＞∈S且＜y，x＞∈S，则 ＜x，y＞∈S∧＜x，y＞∈Sc ?＜x，y＞∈S∩Sc ?＜x，y＞∈IX 故x＝y，即S是反对称的。 3-7.3 设S为X上的关系，证明若S是自反和传递的，则S○S=S，其逆为真吗 ？ 证明 若S是X上传递关系，由习题3-7.2a）可知（S○S）?S， 令＜x，y＞∈S，根据自反性，必有＜x，x＞∈S，因此有＜x，y＞∈S○S，即S?S○S。得到 S=S○S. 这个定理的逆不真。例如X={1，2，3}，S={＜1，2＞，＜2，2＞，＜1，1＞}，

3-8.1 根据图3-8.1中的有向图，写出邻接矩阵和关系R，并求出R的自反闭包和对称闭包。 解 a M1 1 0 R= 0 0 1 b c 0 1 0 图3-8.1 R={＜a，a＞，＜a，b＞，＜b，c＞，＜c，b＞＝ r（R）= R∪IX ={＜a，a＞，＜b，b＞，＜c，c＞，＜a，b＞，＜b，c＞，＜c，b＞＝ s（R）= R∪RC={＜a，a＞，＜a，b＞，＜b，a＞，＜b，c＞，＜c，b＞} 3-8.2 设集合A={a，b，c，d}A上的关系 R={＜a，b＞，＜b，a＞，＜b，c＞，＜c，d＞} a） 用矩阵运算和作图方法求出R的自反、对称、传递闭包； b） 用Warshall算法，求出R的传递闭包。 解 a） 0 1 0 0 MR= 1 0 1 0 0 0 0 1 0 0 0 0 R的关系图如图所示。 a b d c M0 1 0 0 1 0 0 0 1 1 0 0 R+MIA= 1 0 1 0 0 1 0 0 1 1 1 0 0 0 0 1 + 0 0 1 0 = 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 1 r（R）= R∪IA ={＜a，a＞，＜a，b＞，＜b，a＞，＜b，b＞，＜b，c＞，＜c，c＞，＜c，d＞，＜d，d＞}（图（a）） a b d c 图（a） 0 1 0 0 0 1 0 0 0 1 0 0 MR+MRc= 1 0 1 0 1 0 0 0 0 1 0 0 0 0 1 + 0 1 0 0 = 1 0 1 0 1 0 0 0 0 0 0 1 0 0 0 1 0 3-9.1 4个元素的集合共有多少不同的划分。 解 整数4可划分为：4，1+3，1+1+2，2+2，1+1+1+1。 1+C12+14+C4 C224+1=15（种） 3-9.2 设{A1，A2，?，Ak}是集合A的一个划分，我们定义A上的一个二元关系R，使＜a,b＞∈R当且仅当a和b在这个划分的同一块中。证明R是自反的，对称的，和传递的。 证明 设对任意a∈A，则必存在Ai，使a∈Ai，因a与a必可看作在同一块中，故有＜a,a＞∈R。即R是自反的。 设a,b∈A，若有＜a,b＞∈R，则a与b必在同一块，故b与a亦在同一块，＜b, a＞∈R，即R是对称的。 对任意a,b,c∈A， ＜a,b＞∈R∧＜b,c＞∈R ?（?i）（a∈Ai∧b∈Ai）∧（?j）（b∈Aj∧c∈Aj） ?（?i）（?j）（a∈Ai∧c∈Aj∧b∈Ai∩Aj） ?（?i）（?j）（a∈Ai∧c∈Aj∧Ai∩Aj≠?） ?（?i）（?j）（a∈Ai∧c∈Aj∧i=j）（∵i≠j?Ai∩Aj= ?） ?a,c在同一块 ?＜a,c＞∈R ∴R传递 3-10.1 设R和R′是集合A上的等价关系，用例子说明：R∪R′不一定是等价关系。 证明 设 A={1，2，3}，S=R∪R′ R={＜1，1＞，＜2，2＞，＜3，3＞，＜3，1＞，＜1，3＞} R′={＜1，1＞，＜2，2＞，＜3，3＞，＜3，2＞，＜2，3＞} 则R∪R′={＜1，1＞，＜2，2＞，＜3，3＞，＜3，1＞，＜1，3＞，＜3，2＞，＜2，3＞} 因为如＜2，3＞∈S∧＜3，1＞∈S，但＜2，1＞?S，故R∪R′不是传递的，即R∪R′不是A上的等价关系。 3-10.2 试问由4个元素组成的有限集上所有等价关系的个数为多少？ 解 因为集合X上的等价关系与X的划分是一一对应的，所以4个元素的有限集上等价关系证明 设A上定义的二元关系R为：

xu

＜＜x,y＞, ＜u,v＞＞∈R? =

yvxx

① 对任意＜x,y＞∈A，因为 = ，所以

yy的数目，与4个元素集合进行划分的数目是相同的，由习题3-9.1可知共有15个不同的等价关系。 3-10.3 给定集合S={1，2，3，4，5}，找出S上的等价关系R，此关系R能产生划分{{1，2}，{3}，{4，5}}，并画出关系图。 解 我们可用如下方法产生一个等价关系： R1={1，2}×{1，2}={＜1，1＞，＜1，2＞，＜2，1＞，＜2，2＞} R2={3}×{3}={＜3，3＞} R3={4，5}×{4，5}={＜4，4＞，＜4，5＞，＜5，4＞，＜5，5＞} R= R1∪R2∪R3={＜1，1＞，＜1，2＞，＜2，1＞，＜2，2＞，＜3，3＞，＜4，4＞，＜4，5＞，＜5，4＞，＜5，5＞} 关系图如图。 3-10.4 设R是一个二元关系，S={＜a，b＞∣对于某一c，有＜a，c＞∈R∧＜c，b＞∈R}，证明若R是一个等价关系，则S也是一个等价关系。 证明 设R是A上的等价关系： （1） 对任一x∈A，因为R在A上自反，所以＜x，x＞∈R。由S定义，＜x，x＞∈S，所以S是自反的。 （2） 对任意x,y∈A，若＜x，y＞∈S，则存在某个c，使得＜x，c＞∈R∧＜c，y＞∈R，因为R是对称，故有：＜y，c＞∈R∧＜c，x＞∈R，由S的定义，可知＜y，x＞∈S，所以S是对称的。 （3） 对任意x,y,z∈A，若＜x，y＞∈S，及＜y，z＞∈S，则必存在某个c1，使＜x，c1＞∈R，＜c1，y＞∈R。由R的传递性，可知＜x，y＞∈R，同理存在c2，使＜y，c2＞∈R∧＜c2，z＞∈R，由R传递，可知＜y，z＞∈R。再由S定义，得＜x，z＞∈S。故S是传递的。 3-10.5 设正整数的序偶集合A，在A上定义二元关系R如下：＜＜x,y＞, ＜u,v＞＞∈R，当且仅当xv=yu，证明R是一个等价关系。

＜＜x,y＞, ＜x,y＞＞∈R 即R是自反的。

② 设＜x,y＞∈A，＜u,v＞∈A，若

＜＜x,y＞, ＜u,v＞＞∈R?xuux

y =v ?v =y ?＜＜u,v＞,＜

x,y＞＞∈R

即R是对称的。

③ 设任意＜x,y＞∈A，＜u,v＞∈A，＜w,s＞∈A，对

＜＜x,y＞, ＜u,v＞＞∈R∧＜＜u,v＞, ＜w,s＞＞∈R

?（xuuwxwy =v ）∧（v =s ）?y =s

?＜＜x,y＞, ＜w,s＞＞∈R

故R是传递的，于是R是A上的等价关系。

3-10.6 设R是集合A 上的对称和传递关系，证明如果对于A中的每一个元素a,在A中同时也存在b，使在R之中，则R是一个等价关系。证明 对任意a∈A，必存在一个b∈A，使得＜a,b＞∈R. 因为R是传递的和对称的，故有：

＜a,b＞∈R∧＜b, c＞∈R?＜a, c＞∈R?＜c,a＞∈R 由＜a,c＞∈R∧＜c, a＞∈R?＜a,a＞∈R

所以R在A上是自反的，即R是A上的等价关系。

3-10.7 设R1和R2是非空集合A上的等价关系，试确定下述各式，哪些是A上的等价关系，对不是的式子，提供反例证明。

a）（A×A）-R1； b）R1-R2； c）R21；

d) r（R1-R2）（即R1-R2的自反闭包）。 解 a）（A×A）-R1不是A上等价关系。例如：

A={a,b}，R1={＜a,a＞，＜b,b＞}

A×A={＜a,a＞，＜a,b＞，＜b,a＞，＜b,b＞} （A×A）-R1={＜a,b＞，＜b,a＞} 所以（A×A）-R1不是A上等价关系。 b）设 A={a,b,c}

R1={＜a,b＞，＜b,a＞，＜b,c＞，＜c,b＞，＜a,c＞，＜c,a＞，

＜a,a＞，＜b,b＞，＜c,c＞}

R2={＜a,a＞，＜b,b＞，＜c,c＞，＜b,c＞，＜c,b＞} R1-R2={＜a,b＞，＜b,a＞，＜a,c＞，＜c,a＞}

所以R1和R2是A上等价关系，但R1-R2不是A上等价关系。 c）若R1是A上等价关系，则

＜a,a＞∈R1?＜a,a＞∈R1○R1

所以R21是A上自反的。

若＜a,b＞∈R21则存在c，使得＜a, c＞∈R1∧＜c,b＞∈R1。因R1

对称，故有

＜b, c＞∈R21∧＜c,a＞∈R1?＜b, a＞∈R1

即R2

1是对称的。

若＜a,b＞∈R21∧＜b, c＞∈R21,则有 ＜a,b＞∈R1○R1∧＜b, c＞∈R1○R1 ?（?e1）（＜a, e1＞∈R1∧＜e1, b＞∈R1) ∧（?e2）（＜b, e2＞∈

R1∧＜e2, c＞∈R1）

?＜a,b＞∈R1∧＜b, c＞∈R1（∵R1传递）

?＜a,c＞∈R2

1

即R2

1是传递的。

故R21是A上的等价关系。

d）如b）所设，R1和R2是A上的等价关系，但 r（R1-R2）=（R1-R2）∪IA

={＜a,b＞, ＜b,a＞, ＜a,c＞，＜c,a＞，＜a,a＞，＜b,b＞, ＜c,c＞} 不是A上的等价关系。

3-10.8 设C*是实数部分非零的全体复数组成的集合，C*上的关系R定义为：(a+bi)R(c+di)?ac>0,证明R是等价关系，并给出关系R的等价类的几何说明。

证明：(1)对任意非零实数a，有a2>0?(a+bi)R(a+bi) 故R在C*上是自反的。

(2) 对任意(a+bi)R(c+di)?ac>0, 因ca=ac>0?(c+di)R(a+bi), 所以R在C*上是对称的。

(3)设(a+bi)R(c+di) ，(c+di)R(u+vi)，则有ac>0?cu>0 若c>0，则a>0?u>0? au>0 若c<0，则a<0?u<0? au>0

所以(a+bi)R(u+vi)，即R在C*上是传递的。

关系R的等价类，就是复数平面上第一、四象限上的点，或第二、三象限上的点，因为在这两种情况下，任意两个点(a,b)，(c,d)，其横坐标乘积ac>0。

3-10.9 设Π和Π?是非空集合A上的划分，并设R和R?分别为由Π和Π?诱导的等价关系，那么Π?细分Π的充要条件是R? ? R。

证明：若Π?细分Π。由假设aR?b，则在Π?中有某个块S?，使得a,b∈S?，因Π?细分Π，故在Π中，必有某个块S，使S?? S，即a,b∈S，于是有aRb,即R? ? R。

反之，若R? ? R，令S?为H?的一个分块，且a∈S?，则S?=[a]R?={x|xR?a} 但对每一个x，若xR?a，因R? ? R，故xRa，因此{x|xR?a} ?{x|xRa}即[a]R? ?[a]R

设S=[a]R,则S?? S

这就证明了Π?细分Π。

3-10.10 设Rj是表示I上的模j等价关系，Rk是表示I上的模k等价关系，证明I/Rk细分I/Rj当且仅当k是j的整数倍。

证明：由题设Rj={|x≡y(modj)}

Rk={|x≡y(modk)}

故∈Rj?x-y=c?j (对某个c∈I) ∈Rk?x-y=d?k (对某个d∈I) a)假设I/Rk细分I/Rj，则Rk ? Rj 因此∈Rk?∈Rj 故k-0=1?k=c?j (对某个c∈I) 于是k是j的整数倍。

b)若对于某个r∈I，有k=rj则： ∈Rk?x-y=ck (对某个c∈I) ? x-y=crj (对某个c,r∈I) ?∈Rj

因此，Rk ? Rj，于是I/Rk细分I/Rj

5-1代数系统的引入 5.1.1设集合A={1，2，3，?，10}，问下面定义的二元运算*关于集合A是否封闭？ a） x*y=max(x,y); b） x*y=min(x,y); c） x*y=GCD(x,y);（最大公约数） d） x*y=LCM(x,y);（最小公倍数） e） x*y=质数p的个数，其中x?p?y。 解：a）封闭。b）封闭。c）封闭。d）不封闭。e）不封闭。 5.1.2在下表所列出的集合和运算中，请根据运算是否在相应集合上封闭，在相应位置上填写“是”或“否”，其中I表示整数集，N表示自然数集合。 是否封闭 运算 集合 + - ∣x-y∣ max min ∣x∣ I N {x∣0?x?10} {x∣-10?x?10} {2x∣x?I} 解： 是否封闭 运算 集合 + - ∣x-y∣ max min ∣x∣ I 是 是 是 是 是 是 N 是 否 是 是 是 是 {x∣0?x?10} 否 否 是 是 是 是 {x∣-10?x?10} 否 否 否 是 是 是 {2x∣x?I} 是 是 是 是 是 是 5-2运算及其性质 5.2.1对于实数集合R，下表所列的二元运算是否具有左边一列中那些性质，请在相应位置上填写“是”或“否”。 + - × max min ∣x-y∣ 结合律 交换律 有单位元 有零元 解： + - × max min ∣x-y∣ 结合律 是 否 是 是 是 否 交换律 是 否 是 是 是 是 有单位元 是 否 是 否 否 否 有零元 否 否 是 否 否 否

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