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

证法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) b)

(P∧Q)∧┐P (P∧┐P)∧Q ┐(T∨Q) (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

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

↓(Q↓R). 故(P↓Q)↓(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

{ , ┐}表达，则必可用{ ,┐}表达，其逆亦真。故{ , ┐}也必不是最小联结词组。 (8){∧}和{→}

{∧}和{→} ┐P （P∨P∨ ） ┐P （P∧P∧ ） ┐P P→(P→(P→ )

对所有命题变元指派T，则等价式左边为F，右边为T，与等价表达式矛盾。 所以{∨}，{∧}和{→}不是最小联结词。

c (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)∨(┐ …… 此处隐藏：3511字，全部文档内容请下载后查看。喜欢就下载吧 ……