离散数学课后练习题答案(第三版)-乔维声-汤维版、命题逻辑1. 用形式语言写出下列命题：(1) 如果这个数是大于1 的整数，则它的大于1 最小因数一定是素数。
(2) 如果王琳是学生党员又能严格要求自己，则她一定会得到大家的尊敬。
(3) 小王不富有但很快乐。
(4) 说逻辑学枯燥无味或毫无价值都是不对的。
(5) 我现在乘公共汽车或者坐飞机。
(6) 如果有雾，他就不能搭船而是乘车过江。
解： (1)设P ：这个数是大于1 的整数。
Q ：这个数的大于1 最小因数是素数。
则原命题可表示为：P →Q 。
或：设P 1：这个数大于1。
P 2：这个数是整数。
Q ：这个数的大于1 最小因数是素数。
则原命题可表示为：P 1∧ P 2→Q 。
(2)设P ：王琳是学生。
Q ：王琳是党员。
R ：王琳能严格要求自己。
S ：王琳会得到大家的尊敬。
则原命题可表示为：P ∧Q ∧R → S 。
(3)设P ：小王富有。
Q ：小王很快乐。
则原命题可表示为：⌝P ∧Q 。
(4)设P ：逻辑学枯燥无味。
Q ：逻辑学毫无价值。
则原命题可表示为：⌝( P ∨Q)。
(5)设P ：我现在乘公共汽车。
Q ：我现在坐飞机。
则原命题可表示为：P ⎺∨Q 。
(6)设P ：天有雾。
Q ：他搭船过江。
R ：他乘车过江。
则原命题可表示为：P →⌝ Q ∧R 。
2.设P ：天下雪。
Q ：我将进城。
R ：我有时间。
将下列命题形式化： (1) 天不下雪，我也没有进城。
(2) 如果我有时间，我将进城。
(3) 如果天不下雪而我又有时间的话，我将进城。
解：原命题可分别表示为：(1) ⌝P ∧⌝ Q 。
(2) R →Q 。
(3) ⌝P ∧ R →Q 。
3. 将P 、Q 、R 所表示的命题与上题相同，试把下列公式翻译成自然语言： (1) R ∧Q (2) ⌝(R ∨Q) (3) Q ↔(R ∧⌝P) (4) (Q →R)∧(R →Q)解： (1) 原公式可翻译为：我有时间而且我将进城。
(2) ⌝(R ∨Q) ⇔⌝R ∧⌝Q 。
原公式可翻译为：我没有时间也没有进城。
(3) 我将进城当且仅当我有时间而且天不下雪。
(4)(Q →R)∧(R →Q) ) ⇔(Q ∧R) ∨ (⌝Q ∧⌝ R) ⇔ Q ↔R 。
原公式可翻译为：如果我进城，我就有时间；如果我有时间，我就进城。
或：我进城而且我有时间，或者我没有进城而且我也没有时间。
或：我进城当且仅当我有时间。
4. 构造下列命题公式的真值表： (1) Q ∧(P →Q)→P (2) (P ∧⌝Q)∨(R ∧Q)→R (3) ((P ∨Q)→(Q ∨R))→(P ∧⌝R) (4) ((⌝P →(P ∧⌝Q))→R)∨(Q ∧⌝R) 解： (1)Q ∧(P →Q)→P 是含二个变元的三层复合命题，其真值表如下表所示： P Q P →Q Q ∧(P →Q) Q ∧(P →Q)→P 0 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 1 1 1 15. (P ∧⌝Q)∨(R ∧Q)→R 是含三个变元的四层复合命题，其真值表如下表所示：P Q R ⌝QR ∧Q P ∧⌝Q (P ∧⌝Q)∨(R ∧Q) (P ∧⌝Q)∨(R∧Q)→R 0 0 0 1 0 0 0 1 0 0 1 10 0 0 10 0 1 0 1 0 1 1 1 1 1 0 0 0 1 11 1 1 1(6)(P →Q)∧(Q →P)→(⌝P ∧Q) 是含二个变元的三层复合命题，其真值表如下表所示：P Q ⌝P P →Q Q →P⌝P ∧Q (P →Q)∧(Q →P) (P →Q)∧(Q →P)→(⌝P ∧Q) 0 0 1 1 1 0 1 0 0 1 1 1 0 1 0 1 1 0 0 0 1 0 0 1 1 1 01 1 0 1 06. 所以(P →Q)∧(Q →P)→(⌝P ∧Q)既不是重言式又不是矛盾式（或，是可满足式）。
7.Q ∧(P →Q)→(P →⌝Q) 是含二个变元的三层复合命题，其真值表如下表所示：P Q ⌝Q P →Q Q ∧(P →Q) P →⌝Q Q ∧(P →Q)→(P→⌝Q) 0 0 1 1 0 1 1 0 1 0 1 1 1 1 1 0 1 0 0 1 1 1 10 1 1 0(8)(P ↔Q)→(P ∧Q →P) 是含二个变元的三层复合命题，其真值表如下表所示：P Q P ∧Q P ↔Q P ∧Q →P (P ↔Q)→(P ∧Q →P) 0 0 0 1 1 1 0 1 0 0 1 1 1 0 0 0 1 1 1 1 1 1 1 1(10)记((P →Q)∨(R →S))→(P ∨R →Q ∨S) 为A ，它是含四个变元的三层复合命题，其真值表如下表所示：P Q R S P ∨R Q ∨S P →Q R →S (P →Q)∨(R →S ) P ∨R →Q ∨S A 0 0 0 0 0 0 1 1 1 1 10 0 0 1 0 1 1 1 1 1 1 0 0 1 0 1 0 1 0 1 0 0 0 0 1 1 1 1 1 1 1 1 1 0 1 0 0 0 1 1 1 1 1 1 0 1 0 1 0 1 1 1 1 1 1 0 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 0 0 1 1 0 0 1 0 0 1 1 1 0 1 1 1 1 1 0 1 0 1 0 0 0 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1 1 0 0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 11 1 1 1 1 11(11)所以((P→Q)∨(R→S))→(P∨R→Q∨S) 既不是重言式又不是矛盾式（或，是可满足式）。
(12)用推导法证明下列命题公式是等价的：(13)P→(Q→P)⇔⌝P→(P→Q)(14)⌝(P↔Q)⇔(P∧⌝Q)∨(⌝P∧Q)(15)⌝(P∧Q)→(⌝P∨(⌝P∨Q))⇔(⌝P∨Q)(16)(P→Q)∧(R→Q)⇔ P∨R→Q(17)P→(Q→R)⇔(P→⌝Q)∨(P→R)(18)(Q∧R→S)∧ (R→ P∨S) ⇔ R∧(P→Q)→S(19)证明：(20)P→(Q→P)⇔(P∧Q)→P(21)⇔⌝(P∧Q)∨P(22)⇔(⌝P∨⌝Q)∨ P(23)⇔(⌝P∨ P)∨⌝Q(24)⇔1∨⌝Q(25)⇔1(26)⌝P→(P→Q) ⇔(⌝P∧P)→ Q(27)⇔0→ Q(28)⇔1(29)所以P→(Q→P)⇔⌝P→(P→Q)。
(30)⌝(P↔Q)⇔⌝((P→Q) ∧(Q→P))(31)⇔⌝(P→Q) ∨⌝ (Q→P)(32)⇔⌝(⌝P∨Q) ∨⌝(⌝Q∨P)(33)⇔(P∧⌝Q)∨(Q ∧⌝P)(34)⇔(P∧⌝Q)∨(⌝P∧Q)(35)⌝(P∧Q)→(⌝P∨(⌝P∨Q))⇔ (P∧Q) ∨ (⌝P∨(⌝P∨Q))(36)⇔(P∧Q) ∨ ((⌝P∨⌝P)∨Q)(37)⇔(P∧Q) ∨ (⌝P∨Q)(38)⇔( (P∧Q) ∨ Q) ∨⌝P(39)⇔ Q ∨⌝P(40)⇔⌝P∨Q(41)(P→Q)∧(R→Q)⇔(⌝P∨Q)∧(⌝R∨Q)(42)⇔( (⌝P∨Q)∧⌝R)∨( (⌝P∨Q)∧Q)(43)⇔( ⌝P∧⌝R) ∨(Q∧⌝R)∨Q(44)⇔⌝ ( P∨R) ∨Q(45)⇔P∨R→Q(46)P→(Q→R)⇔ (P∧Q)→R(47)⇔⌝ (P∧Q) ∨R(48)(P→⌝Q)∨(P→R) ⇔ (⌝P∨⌝Q)∨( ⌝P∨R)(49)⇔( (⌝P∨⌝Q)∨⌝P)∨R(50)⇔(⌝P∨⌝Q) ∨R(51)⇔⌝ (P∧Q) ∨R(52)所以P→(Q→R)⇔ (P→⌝Q)∨(P→R)。
(53)(Q∧R→S)∧ (R→ P∨S) ⇔ (⌝ (Q∧R) ∨S)∧ (⌝R∨ P∨S)(54)⇔ (⌝Q∨⌝R∨S)∧ (⌝R∨ P∨S)(55)⇔ (⌝Q∨(⌝R∨S) )∧ (P ∨ (⌝R ∨S) )(56)⇔(⌝Q∨(⌝R∨S) )∧ P∨ (⌝Q∨(⌝R∨S) ) ∧ (⌝R ∨S)(57)⇔(⌝Q∨(⌝R∨S) )∧ P∨ (⌝R ∨S)(58)⇔(⌝Q∧ P )∨((⌝R∨S) ∧ P)∨ (⌝R ∨S)(59)⇔(⌝Q∧ P )∨ (⌝R ∨S)(60)R∧(P→Q)→S⇔ R∧(⌝P∨Q)→S(61)⇔⌝(R∧(⌝P∨Q) ) ∨S(62)⇔ (⌝R∨⌝ (⌝P∨Q) ) ∨S(63)⇔ (⌝R∨ (P∧⌝Q) ) ∨S(64)⇔ (P∧⌝Q) ∨(⌝R∨S)(65)所以(Q∧R→S)∧ (R→ P∨S) ⇔ R∧(P→Q)→S。
(66)用分析法证明下列蕴含重言式：(67)P∧Q⇒P→Q(68)P→Q⇒P→ P∧Q(69)P⇒⌝P→Q(70)P→(Q→R)⇒(P→Q)→ (P→R)(71)(P→Q)∧(Q→R)⇒P→R(72)证明：(73)若P∧Q为真，则P与Q都为真，所以P→Q为真，故P∧Q⇒P→Q。
(74)假设P→ P∧Q 为假，则P为真，且P∧Q为假，于是Q为假，所以P→Q为假，故P→Q⇒P→ P∧Q。
(75)假设⌝P→Q为假，则⌝P为真，即P为假，故P⇒⌝P→Q。
(76)假设(P→Q)→ (P→R) 为假，则P→Q为真，P→R为假；由P→R为假知P为真，R为假；再由P→Q为真知Q为真；所以Q→R为假，则P→(Q→R)为假，故P→(Q→R)⇒(P→Q)→(P→R)。
(77)假设P→R为假，则P为真，R为假，(78)若Q为真，则Q→R为假，所以(P→Q)∧(Q→R) 为假；(79)若Q为假，则P→Q为假，所以(P→Q)∧(Q→R) 为假；(80)故(P→Q)∧(Q→R)⇒P→R。
(81)写出下列命题公式的对偶：(82)⌝(⌝P∨⌝Q)∨⌝(⌝P∨Q) ↔P(83)(P∨⌝Q) ∧(P∨Q) ∧(⌝P∨⌝Q)(84)P→( (Q→R) ∧⌝(P∧⌝Q) )(85)解：(86)因为⌝(⌝P∨⌝Q)∨⌝(⌝P∨Q) ↔P⇔⌝ ((⌝P∨⌝Q) ∧ (⌝P∨Q) )↔P(87)⇔⌝ ( ⌝P∧⌝P ∨⌝P∧Q∨⌝Q∧⌝P∨⌝Q ∧Q )↔P(88)⇔⌝ (⌝P∨⌝P ∧ Q ∨⌝P ∧⌝Q) ↔P(89)⇔⌝ (⌝P) ↔P(90)⇔ P ↔P(91)⇔1(92)所以⌝(⌝P∨⌝Q)∨⌝(⌝P∨Q) ↔P的对偶为0。
(93)(P∨⌝Q) ∧(P∨Q) ∧(⌝P∨⌝Q) 的对偶为(P∧⌝Q) ∨ (P∧Q) ∨ (⌝P∧⌝Q)。
(94)因为P→( (Q→R) ∧⌝(P∧⌝Q) ) ⇔⌝ P ∨ ( (Q→R) ∧⌝(P∧⌝Q) )(95)⇔⌝ P ∨ ( (⌝Q ∨R) ∧⌝(P∧⌝Q) )(96)所以P→( (Q→R) ∧⌝(P∧⌝Q) )的对偶为⌝ P∧ ( (⌝Q∧ R) ∨⌝(P∨⌝Q) )。