离散数学课后习题答案(左孝凌版)

dintin@gmail.com 1 离散数学课后习题答案离散数学课后习题答案离散数学课后习题答案离散数学课后习题答案 ((((左孝凌版左孝凌版左孝凌版左孝凌版)))) 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 dintin@gmail.com 2 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 ∨ dintin@gmail.com 3 T T T T T F T F T T F F F T T F T F F F T F F F T F F F T F F F T F F F F F F F T T F F F F F F T 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 T F F T F F F F T T F T F T F T T T F T T T F F F T F F F T 所以，┓(P∧Q) ⇔┓P∨┓Q, ┓(P∨Q) ⇔┓P∧┓Q （5）解：如，对问好所填的地方，可得公式 F1～F6，可表达为 P Q R F1 F2 F3 F4 F5 F6 dintin@gmail.com 4 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) Q 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 F F T F T F T F T F T F T F T F T T F F T T F F T T F F T T F F T T F F F F F T T T T F F F F 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) ⇔┐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) dintin@gmail.com 5 ⇔ (┐(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 dintin@gmail.com 6 ⇔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) 仅当你走我将留下。 dintin@gmail.com 7 设 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 dintin@gmail.com 8 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 dintin@gmail.com 9 ⇔ (┐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 ⇔ ⇔ dintin@gmail.com 10 ∨ ∨ 故(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），故任何命题公式中的联结词，如仅用{ , ┐}表达，则必可用{↔, ┐}表达，其逆亦真。故{ , ┐}也必不是最小联结词组。 (8)证明{∨}，{∧}和{→}不是最小联结词组。 证明：若{∨}，{∧}和{→}是最小联结词，则 ┐P⇔（P∨P∨……） ┐P⇔（P∧P∧……） ┐P⇔P→(P→(P→……) 对所有命题变元指派 T，则等价式左边为 F，右边为 T，与等价表达式矛盾。 所以{∨}，{∧}和{→}不是最小联结词。 (9)证明{┐,→}和{┐, }是最小联结词组。 证明：因为{┐,∨}为最小联结词组，且 P∨Q⇔┐P→Q 所以{┐,→}是功能完备的联结词组，又{┐},{→}都不是功能完备的联结词组。 所以{┐,→}是最小联结词组。 又因为 P→Q⇔┐(P Q)，所以{┐, }是功能完备的联结词组，又{┐},{ }不是功能完备的联结词组， 所以{┐, }是最小联结词组。 →c ∨ →c →c →c →c dintin@gmail.com 11 习题 1-7 (1) 解： P∧(P→Q) ⇔P∧(┐P∨Q) ⇔ (P∧┐P)∨(P∧Q) P∧(P→Q) ⇔ (P∨(┐Q∧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) ⇔┐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) dintin@gmail.com 12 ⇔(┐P∨┐Q)∧(Q∨P) (4) 解： 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) (5) 证明： 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 dintin@gmail.com 13 (┐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 ⇔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→(C V D) B 和 C 不能都去。 ┐(B∧C) C 去则 D要留下。 C→┐D 按题意应有：A→(C V D)，┐(B∧C)，C→┐D必须同时成立。 因为 C V D ⇔ (C∧┐D) ∨(D∧┐C) 故(A→(C V D))∧┐(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) dintin@gmail.com 14 ∨(┐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是第二。 由题意得 (P V Q) ∧(R V S) ∧(EV S) ⇔ ((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 dintin@gmail.com 15 (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 dintin@gmail.com 16 (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 dintin@gmail.com 17 (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 证法二：（反证法） dintin@gmail.com 18 (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：小张。 dintin@gmail.com 19 则有 ¬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）解： dintin@gmail.com 20 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)|)))) 习题 2222----4444 (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) dintin@gmail.com 21 因为 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-52-52-52-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