离散数学课后习题答案左孝凌版) 下载本文

内容发布更新时间 : 2024/11/1 7:28:23星期一 下面是文章的全部内容请认真阅读。

(9)证明{┐,→}和{┐, }是最小联结词组。

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

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

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

词组,

c 所以{┐, }是最小联结词组。 →

习题 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)

dintin@gmail.com

11

?┐(┐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)

(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)

dintin@gmail.com

12

? (┐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

(┐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))

dintin@gmail.com

13

?┐(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

dintin@gmail.com

14

(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∨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 (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) ┐(AC) 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∧┐?A→(B→F) (1) ┐(A→(B→F)) P

(2) A (1)T,I (3) ┐(B→F) (1)T,I

dintin@gmail.com

15