第1章习题答案

习题

1.判断下列语句是否是命题，为什么？若是命题，判断是简单命题还是复合命题？ (1)离散数学是计算机专业的一门必修课。 (2)李梅能歌善舞。 (3)这朵花真美丽！ (4)３＋２＞６。

(5)只要我有时间，我就来看你。 (6)x＝５。

(7)尽管他有病，但他仍坚持工作。 (8)太阳系外有宇宙人。 (9)小王和小张是同桌。 (10)不存在最大的素数。

解 在上述10个句子中，(3)是感叹句，因此它不是命题。(6)虽然是陈述句，但它没有确定的值，因此它也不是命题。其余语句都是可判断真假的陈述句，所以都是命题。其中：(1)、(4) 、(8) 、(9) 、是简单命题，、(2) 、(5) 、(7)、(10) 是复合命题。

2.判断下列各式是否是命题公式，为什么？ (1)(P(P∨Q))。 (2)(PQ)(QP)))。 (3)((PQ)(QP))。 (4)(QR∧S)。 (5)(P∨QR)S。

(6)((R(QR)(PQ))。 解 (1)是命题公式。

(2)不是命题公式，因为括号不配对。 (3)是命题公式。 (4)是命题公式。

(5)不是命题公式，因为QR没有意义。

(6)不是命题公式，因为R(QR)(PQ) 没有意义。 3.将下列命题符号化： (1)我们不能既划船又跑步。 (2)我去新华书店，仅当我有时间。 (3)如果天下雨，我就不去新华书店。

1

第1章 命题逻辑

(4)除非天不下雨，我将去新华书店。 (5)张明或王平都可以做这件事。

(6)“2或4是素数，这是不对的”是不对的。 (7)只有休息好，才能工作好。 (8)只要努力学习，成绩就会好的。 (9)大雁北回，春天来了。 (10)小张是山东人或河北人。

解 (1)符号化为(P∧Q)，其中，P：我们划船，Q：我们跑步。 (2)符号化为QR，其中，R：我有时间，Q：我去新华书店。 (3)符号化为PQ，其中，P：天下雨，Q：我去新华书店。 (4)符号化为PQ，其中，P：天下雨，Q：我去新华书店。

(5)符号化为P∧Q，其中，P：张明可以做这件事，Q：王平可以做这件事。

(6)符号化为((P∨Q))，“2或4是素数，这是不对的”是不对的，其中，P：2是素数，Q：4是素数，。

(7)符号化为QP，其中，P：休息好，Q：工作好。 (8)符号化为PQ，其中，P：努力学习，Q：成绩就会好的。 (9)符号化为PQ，其中，P：大雁北回，Q：春天来了。

(10)符号化为PQ，其中，P：小张是山东人，Q：小张是河北人。

4.构造下列命题公式的真值表，并据此说明哪些是其成真赋值，哪些是其成假赋值？ (1)(P∨Q)。 (2)P∧(Q∨R)。

(3)(P∨Q)(P∧Q)。 (4)P(QP)。 解 (1)

P Q 0 0 0 1 1 0 1 1 P∨Q 1 0 1 1 (P∨Q) 0 1 0 0 由真值表可知，公式(P∨Q)的成真赋值为：01，成假赋值为00、10、11。 (2)

P Q R Q∨R P∧(Q∨R) 2

第1章 命题逻辑

0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 0 0 0 0 0 1 1 1 由真值表可知，公式P∧(Q∨R)的成真赋值为：101、110、111，成假赋值为000、001、010、011、100。

(3)

P Q 0 0 0 1 1 0 1 1 ( P∨Q) 1 0 0 0 P∧Q 1 0 0 0 (P∨Q)(P∧Q) 1 1 1 1 由真值表可知，公式(P∨Q)(P∧Q)的成真赋值为：00、01、10、11，没有成假赋值。 (4)

P Q 0 0 0 1 1 0 1 1 QP 1 0 1 1 P(QP) 1 0 1 1 由真值表可知，公式P(QP)的成真赋值为：00、10、11，成假赋值为：01。 5.分别用真值表法和公式法判断下列命题公式的类型： (1)(P∨Q)(P∧Q)。 (2)(P∧Q)(P∨Q)。

(3)(P∨Q)∧(Q∨R)∧(R∨P∨Q)。 (4)(P∧QR)(P∧R∧Q)。 (5)(QP)∧(P∧Q)。 (6)(PQ)(PQ)。 (7)(P∧Q)∧(P∨Q)。 解 (1)真值表法：

P Q 0 0 0 1 1 0 1 1 P∨Q 0 1 1 1 P∧Q 0 0 0 1 (P∨Q)(P∧Q) 1 0 0 1 由真值表可知，公式(P∨Q)(P∧Q)为可满足式。

公式法：因为(P∨Q)(P∧Q)(P∨Q)∨(P∧Q)(P∧Q)∨(P∧Q)，所以，公式(P∨Q)(P∧Q)为可满足式。

3

第1章 命题逻辑

(2)真值表法：

P Q 0 0 0 1 1 0 1 1 P∧Q 0 0 0 1 P∨Q 0 1 1 1 (P∧Q)(P∨Q) 1 1 1 1 由真值表可知，公式(P∧Q)(P∨Q)为重言式。

公式法：因为(P∧Q)(P∨Q)(P∧Q)∨(P∨Q)P∨Q∨P∨QT，所以，公式(P∧Q)(P∨Q)为重言式。

(3)真值表法：

P Q R 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 P∨Q 1 1 1 1 0 0 1 1 Q∨R 1 0 1 1 1 0 1 1 R∨P∨Q 1 1 1 1 1 1 0 1 (P∨Q)∧(Q∨R)∧(R∨P∨Q) 0 0 0 0 0 0 0 0 由真值表可知，公式(P∨Q)∧(Q∨R)∧(R∨P∨Q)为矛盾式。

公式法：因为(P∨Q)∧(Q∨R)∧(R∨P∨Q)(P∨Q)∧Q∧R∧(R∧P∧Q)F，所以，公式(P∨Q)∧(Q∨R)∧(R∨P∨Q)为矛盾式。

(4)真值表法：

P Q R 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 P∧QR 1 1 1 1 1 1 0 1 P∧R∧Q 0 0 0 0 0 0 1 0 (P∧QR)(P∧R∧Q) 0 0 0 0 0 0 1 0 由真值表可知，公式(P∧QR)(P∧R∧Q)为可满足式。

公式法：因为(P∧QR)(P∧R∧Q)(( P∧Q)∨R)∨(P∧R∧Q)

( P∧Q∧R)∨(P∧R∧Q)( P∧Q∧R)

所以，公式(P∧QR)(P∧R∧Q)为可满足式。 (5)真值表法：

P Q 0 0 0 1 1 0 1 1 QP 1 0 1 1 P∧Q 0 1 0 0 (QP)∧(P∧Q) 0 0 0 0 由真值表可知，公式(QP)∧(P∧Q)为可矛盾式。

公式法：因为(QP)∧(P∧Q)(Q∨P)∧(P∧Q)(Q∧P)∧(P∧Q)F，所以，公式为

4

第1章 命题逻辑

可矛盾式。

(6)真值表法：

P Q 0 0 0 1 1 0 1 1 PQ (PQ) 0 0 1 1 1 1 0 0 (PQ)(PQ) 1 1 1 1 由真值表可知，公式(PQ)(PQ)为永真式。

公式法：因为(PQ)(PQ)((PQ)∧(QP))((P∧Q)∨(P∧Q))

((P∨Q)∧(P∨Q))((P∨Q)∧(P∨Q))T

所以，公式(PQ)(PQ)为永真式。 (7)真值表法：

P Q 0 0 0 1 1 0 1 1 P∧Q 0 0 0 1 P∨Q 0 1 1 1 (P∧Q)∧(P∨Q) 0 0 0 0 由真值表可知，公式(P∧Q)∧(P∨Q)为矛盾式。

公式法：因为(P∧Q)∧(P∨Q)(P∧Q)∧(P∧Q)F，所以，公式(P∧Q)∧(P∨Q)为矛盾式。

6.分别用真值表法和公式法证明下列各等价式： (1)(P∨Q)∧PP∧Q。 (2)(P∨Q)∨(P∧Q)P。 (3)(P∧Q)∨PP∨Q。 (4)P(Q∧R)(PQ)∧(PR)。 (5)(PQ)∧(RQ)(P∨R)Q)。

(6)(P∧Q∧AC)∧(AP∨Q∨C)(A∧(PQ))C。 (7)(PQ)PQ。 (8)(PQ)PQ。 证明 (1)真值表法：

P Q 0 0 0 1 1 0 1 1 P∨Q 0 1 1 1 (P∨Q)∧P 0 1 0 0 P∧Q 0 1 0 0 由真值表可知，(P∨Q)∧PP∧Q。

公式法：(P∨Q)∧P(P∧P)∨(Q∧P)P∧Q。 (2)真值表法：

P Q P∧Q (P∨Q)∨(P∧Q) P 5

第1章 命题逻辑

0 0 0 1 1 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 由真值表可知，(P∨Q)∨(P∧Q)P。

公式法：(P∨Q)∨(P∧Q)(P∧Q)∨(P∧Q)P∧(Q∨Q)P。 (3)真值表法：

P Q 0 0 0 1 1 0 1 1 P∧Q 0 0 0 1 (P∧Q)∨P 1 1 0 1 P∨Q 1 1 0 1 由真值表可知，(P∧Q)∨PP∨Q。

公式法：(P∧Q)∨P(P∨P)∧(Q∨P)P∨Q。 (4)真值表法：

P Q R 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 PQ 1 1 1 1 0 0 1 1 PR 1 1 1 1 0 1 0 1 (PQ)∧(PR) 1 1 1 1 0 0 0 1 P( Q∧R) 1 1 1 1 0 0 0 1 由真值表可知，P(Q∧R)(PQ)∧(PR)。

公式法：P(Q∧R)P∨(Q∧R)(P∨Q)∧(P∨R)(PQ)∧(PR)。 (5)真值表法：

P Q R 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 PQ 1 1 1 1 0 0 1 1 RQ 1 0 1 1 1 0 1 1 (PQ)∧(RQ) 1 0 1 1 0 0 1 1 ( P∨R)Q 1 0 1 1 0 0 1 1 由真值表可知，(PQ)∧(RQ)(P∨R)Q)。

公式法：(PQ)∧(RQ)(P∨Q)∧(R∨Q)(P∧R)∨Q

(P∨R)∨Q(P∨R)Q)。

(6)真值表法：

P Q A C PQ (P∧Q∧A C)∧(A P∨Q∨C) (A∧(PQ))C 6

第1章 命题逻辑

0 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 1 0 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 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 1 1 1 1 1 0 1 由真值表可知，(P∧Q∧AC)∧(AP∨Q∨C)(A∧(PQ))C。

公式法：(P∧Q∧AC)∧(AP∨Q∨C)(P∨Q∨A∨C)∧(A∨P∨Q∨C)

(P∨Q∨A∨C)∧(A∨P∨Q∨C) ((P∨Q∨A)∧(A∨P∨Q))∨C ((P∧Q∧A)∨(A∧P∧Q))∨C ( A∧((P∧Q)∨(P∧Q)))∨C ( A∧(PQ))∨C (A∧(PQ))C。

(7)真值表法：

P Q 0 0 0 1 1 0 1 1 PQ 1 1 1 0 ( PQ) 0 0 0 1 PQ 0 0 0 1 由真值表可知，(PQ)PQ。

公式法：(PQ)((P∧Q))(P∨Q))PQ。 (8)真值表法：

P Q 0 0 0 1 1 0 1 1 PQ 1 0 0 0 (PQ) 0 1 1 1 PQ 0 1 1 1 由真值表可知，(PQ)PQ。

公式法：(PQ)((P∨Q))(P∧Q)PQ。 7.设A、B、C为任意的三个命题公式，试问下面的结论是否正确？ (1)若A∨CB∨C，则AB。 (2)若A∧CB∧C，则AB。 (3)若AB，则AB。

7

第1章 命题逻辑

(4)若ACBC，则AB。 (5)若ACBC，则AB。

解 (1)不正确。例如，设有一赋值：A＝T，B＝F，C＝T，则A∨CB∨C，但AB不成立。 (2)不正确。例如，设有一赋值：A＝T，B＝F，C＝F，则A∧CB∧C，但AB不成立。 (3)正确。因为AB(AB)∧(BA)(A∨B)∧(B∨A)(B A)∧(AB) AB，所以，若AB，则AB。

(4)不正确。例如，设有一赋值：A＝T，B＝F，C＝T，则ACBC，但AB不成立。 (5)正确。因为，若ACBC，则AC与BC等值。当AC与BC都为真时，A和C等值且B和C等值，从而A和B等值，此时AB；当AC与BC都为假时，A和C不等值且B和C也不等值，从而A和B等值，此时AB。

总之有，若ACBC，则AB。 8.试给出下列命题公式的对偶式： (1)(P∧Q)∨R。 (2)T∨(P∧Q)。 (3)(P∨Q)∧F。

(4)(P∧Q)∧(P∨Q)。 解 (1)对偶式为(P∨Q)∧R。 (2)对偶式为F∧(P∨Q)。 (3)对偶式为(P∧Q)∨T。

(4)对偶式为(P∨Q)∨(P∧Q)。

9.分别用真值表法、分析法和公式法证明下列蕴涵式： (1)(PQ)P。 (2)(PQ)QP∨Q。 (3)PQP(P∧Q)。 (4)(PQ)∧(QR)(PR)。 证明 (1)真值表法：

P Q 0 0 0 1 1 0 1 1 PQ 1 1 0 1  (PQ) 0 0 1 0 P 0 0 1 1 由真值表可知，(PQ)P。

分析法：若(PQ)为真，则PQ为假，从而P为真，而Q为假。故(PQ)P。 公式法：因为(PQ)P(P∨Q)∨PT，所以(PQ)P。 (2)真值表法：

P Q

PQ (PQ)Q 8

P∨Q 第1章 命题逻辑

0 0 0 1 1 0 1 1 1 1 0 1 0 1 1 1 0 1 1 1 由真值表可知，(PQ)QP∨Q。

分析法：若P∨Q为假，都P和Q为假，于是PQ为真，从而(PQ)Q为假。故(PQ)QP∨Q。

公式法：因为((PQ)Q)(P∨Q) ((P∨Q)∨Q)∨(P∨Q)

((P∨Q)∧Q)∨(P∨Q) (P∧Q)∨(Q∧Q)∨(P∨Q) (P∨Q)∨(P∨Q) T

所以，(PQ)QP∨Q。 (3)真值表法：

P Q 0 0 0 1 1 0 1 1 P∧Q 0 0 0 1 PQ 1 1 0 1 P(P∧Q) 1 1 0 1 由真值表可知，PQP(P∧Q)。

分析法：若P(P∧Q)为假，则P为真且P∧Q为假，于是P为真且Q为假，从而PQ为假。故PQP(P∧Q)。

公式法：因为(PQ)(P(P∧Q))(P∨Q)∨(P∨(P∧Q)

(P∧Q)∨(P∨(P∧Q) (P∧Q)∨(P∨Q) (P∧Q)∨(P∧Q) T

所以，PQP(P∧Q)。 (4)真值表法：

P Q R 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 PQ 1 1 1 1 0 0 1 1 QR 1 1 0 1 1 1 0 1 (PQ)∧(QR) 1 1 0 1 0 0 0 1 PR 1 1 1 1 0 1 0 1 由真值表可知，(PQ)∧(QR)(PR)。

分析法：若PR为假，则P为真而R为假。当Q为真时，QR为假；当Q为假时，PQ为假。

9

第1章 命题逻辑

从而不管Q取什么值，都有(PQ)∧(QR)为假。故(PQ)∧(QR)(PR)。

公式法：因为((PQ)∧(QR))(PR)((P∨Q)∧(Q∨R))∨(P∨R)

(P∧Q)∨(Q∧R)∨P∨R

(P∧Q)∨((Q∨P∨R)∧(R∨P∨R)) (P∧Q)∨(Q∨P∨R)

(P∨Q∨P∨R)∧(Q∨Q∨P∨R) T

所以，(PQ)∧(QR)(PR)。

10.将下列命题公式化成与之等价的仅含联结词或的公式： (1)P∧(QR)。 (2)(P(Q∧R))∨P。 解 因为

P(P∧P)PP

P∧Q(PQ)(PQ)(PQ)

P∨Q(P∧Q)PQ(PP)(QQ) P(P∨P)PP

P∨Q(PQ)(PQ)(PQ) P∧QPQ(PP)(QQ) 所以

(1)P∧(QR)P∧(Q∨R)

 P∧((Q)(Q))(RR)  P∧((QQ)( QQ))(RR)

(P(((QQ)( QQ))(RR)))(P(((QQ)( QQ))(RR)))

P∧(QR) P∧(Q∨R)

 P∧((Q)PR)((Q)PR)  P∧((QQ)PR)(( QQ)PR)

(PP)((((QQ)PR)(( QQ)PR))(((QQ)PR)(( QQ)PR)))

(2)(P(Q∧R))∨P(P∨(Q∧R))∨P

(( PP)∨((QR)(QR)))∨P (( PP)∨((QR)(QR)))∨P

((( PP)(PP))((((QR)(QR)))(((QR)(QR)))))∨P ((((( PP)(PP))((((QR)(QR)))(((QR)(QR))))))(((( P

P)(PP))((((QR)(QR)))(((QR)(QR)))))))(PP)

(P(Q∧R))∨P(P∨(Q∧R))∨P

10

第1章 命题逻辑

(( PP)∨((QQ)(RR)))∨P

((( PP)((QQ)(RR))))(( PP)((QQ)(RR)))))∨P

((((( PP)((QQ)(RR))))(( PP)((QQ)(RR))))))P)(((((

PP)((QQ)(RR))))(( PP)((QQ)(RR))))))P)

11.证明{∧，∨}，{∨}和{}都不是全功能联结词组。

证明 命题P经联结词∧和∨反复运算只能得出P，不能得出P，所以{∧，∨}不是全功能联结词组。

命题P经联结词∨反复运算只能得出P，不能得出P，所以{∨}不是全功能联结词组。 命题P经联结词反复运算只能得出P和P，不能得出P∧Q，所以{}不是全功能联结词组。 12.证明{，∧}是最小全功能联结词组。 证明 因为 P∨Q(P∧Q) PQP∨Q(P∧Q)

PQ(PQ)∧(QP)(P∧Q)∧(Q∧P) 所以，{，∧}是最小全功能联结词组。 13.完成定理1.8的证明。

证明 设A为简单析取式，其包含的所有命题变元为p1、p2、…、pn。

若A为永真式，但不同时含有某个命题变元及其否定，则不妨设A＝p1∨p2∨„∨pi∨pi＋1∨„∨pn，于是当p1、p2、„、pi的真值都是假，而pi＋1、„、pn的真值都是真时，A的真值为假，与A为永真式矛盾。

反之，若A同时含有某个命题变元及其否定，显然有A为永真式。 14.完成定理1.10的证明。

证明 公式A为矛盾式当且仅当A的析取范式的每个简单合取式都是矛盾式。由定理1.7可得，简单合取式是矛盾式当且仅当它同时有一个命题变元及其否定。因此，公式A为矛盾式当且仅当A的析取范式的每个简单合取式至少同时含有一个命题变元及其否定。

15.完成定理1.11的证明。

证明 公式A为永真式当且仅当A的合取范式的每个简单析取式都是永真式。由定理1.8可得，简单析取式是永真式当且仅当它同时有一个命题变元及其否定。因此，公式A为永真式当且仅当A的合取范式的每个简单析取式至少同时含有一个命题变元及其否定。

16.完成定理1.14的证明。

证明 设A是A的合取范式，即AA。若A的某个简单析取式Ai中不含命题变元P及其否定P，将Ai展成形式AiAi∨TAi∨(P∧P)(Ai∨P)∧(Ai∨P)，继续这个过程，直到所有的简单析取式成为大项。然后，消去重复的项及永真式之后，得到A的主合取范式。

下面证明其惟一性。

11

第1章 命题逻辑

若A有两个与之等价的主合取范式B和C，则BC。由B和C是A的不同的主合取范式，不妨设大项Mi只出现在B中而不在C中，于是i的二进制为B的成假赋值，C的成真赋值，与BC矛盾。因而A的主合取范式是惟一的。

17.完成定理1.15的证明。

证明 设命题公式A的真值为F的赋值所对应的大项为M1、M2、„、Mk，令B＝M1∧M2∧„∧Mk。下证AB。

若A为假，则其赋值所对应的小项一定是M1、M2、„、Mk中的某一项，不妨设为Mi，因为Mi为假，而M1、M2、„、Mi－1、Mi＋1、„、Mk都为真，故B也为假。

若A为真，则其赋值所对应的大项一定不是M1、M2、„、Mk中的某一项，此时M1、M2、„、Mk都为真，故B也为假。

因此，AB。

18.完成定理1.18的证明。

证明 设A是含n个命题变元的命题公式，则：

(1)由定理1.13可知，A的真值为T的赋值所对应的小项的析取即为此公式A的主析取范式，所以，A为永真式当且仅当A的主析取范式含有全部2n个小项。

(2)由定理1.13可知，A的真值为F的赋值所对应的大项的合取即为此公式的主合取范式，所以，A为矛盾式当且仅当A的主合取范式含有全部2n个大项。

(3)由(1)、(2)即得。

19.分别用真值表法和公式法求下面命题公式的主析取范式与主合取范式，判断各公式的类型，并写出其相应的成真赋值和成假赋值。

(1)P(QR)。 (2)(P∨Q)R。

(3)(P(Q∨R))∧(P∨(QR))。 (4)((PQ)∧Q)∨R。 (5)(P∨Q)(PQ)。 (6)(PQ)(P∧(Q∨R))。

(7)((PQ)∧(RP))∨((RQ)P)。 (8)((P(P∨Q))(Q∧R))(P∨R)。 解 (1)公式法：因为P(QR)P∨Q∨R

M6

m0∨m1∨m2∨m3∨m4∨m6∨m7

所以，公式P(QR)为可满足式，其相应的成真赋值为000、001、010、011、100、101、111：成假赋值为：110。

12

第1章 命题逻辑

真值表法：

P Q R 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 QR 1 1 0 1 1 1 0 1 P(QR) 1 1 1 1 1 1 0 1 由真值表可知，公式P(QR)为可满足式，其相应的成真赋值为000、001、010、011、100、101、111：成假赋值为：110。

(2)公式法：因为(P∨Q)R(P∨Q)∨R(P∧Q)∨R

(P∨(Q∧Q)∨R)∧((P∧P)∨Q∨R)

(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R) M2∧M4∧M6 m0∨m1∨m3∨m5vm7

所以，公式(P∨Q)R为可满足式，其相应的成真赋值为000、001、011、101、111：成假赋值为：010、100、110。

真值表法：

P Q R 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 P∨Q 0 0 1 1 1 1 1 1 (P∨Q)R 1 1 0 1 0 1 0 1 由真值表可知，公式(P∨Q)R为可满足式，其相应的成真赋值为000、001、011、101、111：成假赋值为：010、100、110。

(3)公式法：因为(P(Q∨R))∧(P∨(QR))

(P∨Q∨R)∧(P∨(Q∧R)∨(Q∧R))

(P∨Q∨R)∧(((P∨Q)∧(P∨R))∨(Q∧R))

(P∨Q∨R)∧(P∨Q∨Q)∧(P∨Q∨R)∧(P∨R∨Q)∧(P∨R∨R) (P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R) M4∧M5∧M6 m0∨m1∨m2∨m3∨m7

所以，公式(P(Q∨R))∧(P∨(QR))为可满足式，其相应的成真赋值为000、001、010、011、111：成假赋值为：100、101、110。

13

第1章 命题逻辑

真值表法：

P Q R 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 QR 1 0 0 1 1 0 0 1 P(Q∨R) 1 1 1 1 0 1 1 1 P∨(QR) 1 1 1 1 1 0 0 1 (P(Q∨R))∧(P∨(QR)) 1 1 1 1 0 0 0 1 由真值表可知，公式(P(Q∨R))∧(P∨(QR))为可满足式，其相应的成真赋值为000、001、010、011、111：成假赋值为：100、101、110。

(4)公式法：因为((PQ)∧Q)∨R((P∨Q)∧Q)∨R

(P∧Q∧Q)∨R R

(Q∨Q)∧R (Q∧R)∨(Q∧R)

((P∨P)∧Q∧R)∨((P∨P)∧Q∧R)

(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R) m1∨m3∨m5∨m7 M0∧M2∧M4∧M6

所以，公式((PQ)∧Q)∨R为可满足式，其相应的成真赋值为001、011、101、111：成假赋值为：000、010、100、110。

真值表法：

P Q R 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 PQ 1 1 1 1 0 0 1 1 (PQ)∧Q 0 0 0 0 0 0 0 0 ((PQ)∧Q)∨R 0 1 0 1 0 1 0 1 由真值表可知，公式((PQ)∧Q)∨R为可满足式，其相应的成真赋值为001、011、101、111：成假赋值为：000、010、100、110。

(5)公式法：因为(P∨Q)(PQ)(P∨Q)∨(P∧Q)∨(P∧Q)

(P∧Q)∨(P∧Q)∨(P∧Q) m1∨m2∨m3 M0

所以，公式(P∨Q)(PQ)为可满足式，其相应的成真赋值为01、10、11：成假赋值为：00。

14

第1章 命题逻辑

真值表法：

P Q 0 0 0 1 1 0 1 1 P∨Q 1 1 1 0 PQ 0 1 1 0 (P∨Q)(PQ) 0 1 1 1 由真值表可知，公式(P∨Q)(PQ)为可满足式，其相应的成真赋值为01、10、11：成假赋值为：00。

(6)公式法：因为(PQ)(P∧(Q∨R))(( P∨Q))∨(P∧Q∧R))

(P∨Q)∨(P∧Q∧R))

(P∨Q∨P)∧(P∨Q∨Q)∧(P∨Q∨R) (P∨Q)∧(P∨Q∨R)

(P∨Q∨(R∧R))∧(P∨Q∨R) (P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R) M0∧M1

m2∨m3∨m4∨m5∨m6∨m7

所以，公式(PQ)(P∧(Q∨R))为可满足式，其相应的成真赋值为010、011、100、101、110、111：成假赋值为：000、001。

真值表法：

P Q R 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 Q∨R 1 0 1 1 1 0 1 1 P∧(Q∨R) 0 0 0 0 1 0 1 1 PQ 1 1 0 0 0 0 0 0 (PQ)(P∧(Q∨R)) 0 0 1 1 1 1 1 1 由真值表可知，公式(PQ)(P∧(Q∨R))为可满足式，其相应的成真赋值为010、011、100、101、110、111：成假赋值为：000、001。

(7)公式法：因为((PQ)∧(RP))∨((RQ)P) ((P∨Q)∧(R∨P))∨((R∨Q)∨P) (P∨Q)∨(R∨P)∨((R∨Q)∧P) (P∧Q)∨(R∧P)∨(R∧P)∨(Q∧P) (P∧Q)∨(P∧R)∨(P∧R)

(P∧Q∧(R∨R))∨(P∧(Q∨Q)∧R)∨(P∧(Q∨Q)∧R)

(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R) (P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)

15

第1章 命题逻辑

m1∨m3∨m4∨m5∨m6 M0∧M2∧M7

所以，公式((PQ)∧(RP))∨((RQ)P)为可满足式，其相应的成真赋值为001、011、100、101、110：成假赋值为：000、010、111。

真值表法：

P Q R ((PQ)∧(RP)) ((RQ)P) 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 1 1 1 0 1 0 0 1 1 1 0 1 1 1 1 1 0 0 1 1 1 1 0 0 ((PQ)∧(RP))∨((RQ)P) 0 1 0 1 1 1 1 0 由真值表可知，公式((PQ)∧(RP))∨((RQ)P)为可满足式，其相应的成真赋值为001、011、100、101、110：成假赋值为：000、010、111。

(8)公式法：因为((P(P∨Q))(Q∧R))(P∨R)

((P∨P∨Q)(Q∧R))(P∨R) (Q∧R)(P∨R)

(Q∧R∧(P∨R))∨((Q∧R)∧(P∨R)) (Q∧R∧P)∨(Q∧R∧R)∨((Q∨R)∧P∧R) (P∧Q∧R)∨(Q∧R)∨(Q∧P∧R)∨(R∧P∧R)

(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R) (P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R) m3∨m4∨m6∨m7 M0∧M1∧M2∧M5

所以，公式((P(P∨Q))(Q∧R))(P∨R)为可满足式，其相应的成真赋值为011、100、110、111：成假赋值为：000、001、010、101。

真值表法：

P Q R 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 P(P∨Q) 1 1 1 1 1 1 1 1 (P(P∨Q))(Q∧R) 0 0 0 1 0 0 0 1 P∨R 1 1 1 1 0 1 0 1 ((P(P∨Q))(Q∧R))(P∨R) 0 0 0 1 1 0 1 1 由真值表可知，公式((P(P∨Q))(Q∧R))(P∨R)为可满足式，其相应的成真赋值为011、100、110、111：成假赋值为：000、001、010、101。

16

第1章 命题逻辑

20.使用将命题公式化为主范式的方法，证明下列各等价式： (1)(PQ)(P∧Q)(QP)∧(P∨Q)。 (2)P∧Q∧(P∨Q)P∧Q∧(P∨Q)。 (3)(PQ)(P∨Q)∧(P∧Q)。

(4)(P∧Q)∨(P∧R)∨(Q∧R)(P∧Q)∨(P∧R)。 解 (1)因为(PQ)(P∧Q)(P∨Q)∨(P∧Q)

(P∧Q)∨(P∧Q)

(QP)∧(P∨Q)(Q∨P)∧(P∨Q)

(P∧Q)∨(Q∧Q)∨(P∧P) ∨(P∧Q) (P∧Q)∨P

(P∧Q)∨(P∧(Q∨Q)) (P∧Q)∨(P∧Q)∨(P∧Q) (P∧Q)∨(P∧Q)

所以，(PQ)(P∧Q)(QP)∧(P∨Q)。

(2)因为P∧Q∧(P∨Q)(P∨(Q∧Q))∧((P∧P)∨Q)∧(P∨Q)

(P∨Q)∧(P∨Q)∧(P∨Q)∧(P∨Q)∧(P∨Q) (P∨Q)∧(P∨Q)∧(P∨Q)∧(P∨Q)

P∧Q∧(P∨Q)(P∨(Q∧Q))∧((P∧P)∨Q)∧(P∨Q)

(P∨Q)∧(P∨Q)∧(P∨Q)∧(P∨Q)∧(P∨Q) (P∨Q)∧(P∨Q)∧(P∨Q)∧(P∨Q) (P∨Q)∧(P∨Q)∧(P∨Q)∧(P∨Q)

所以，P∧Q∧(P∨Q)P∧Q∧(P∨Q)。 (3)因为(PQ)((P∧Q)∨(P∧Q))

(P∧Q)∧(P∧Q)) (P∨Q)∧(P∨Q)) (P∨Q)∧(P∨Q)

(P∨Q)∧(P∧Q)(P∨Q)∧(P∨Q) 所以，(PQ)(P∨Q)∧(P∧Q)。 (4)(P∧Q)∨(P∧R)∨(Q∧R)

(P∧Q∧(R∨R))∨(P∧(Q∨Q)∧R)∨((P∨P)∧Q∧R)

(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R) (P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R) (P∧Q)∨(P∧R)

(P∧Q∧(R∨R))∨(P∧(Q∨Q)∧R)

17

第1章 命题逻辑

(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R) (P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R) 所以，(P∧Q)∨(P∧R)∨(Q∧R)(P∧Q)∨(P∧R)。

21.设计一盏电灯的开关电路，要求受3个开关A、B、C的控制：当且仅当A和C同时关闭或B和C同时关闭时灯亮。设F表示灯亮。

(1)写出F在全功能联结词组{}中的命题公式。 (2)写出F的主析取范式与主合取范式。

解 (1)设A：开关A关闭；B：开关B关闭；C：开关C关闭；F＝(A∧C)∨(B∧C)。 在全功能联结词组{}中：

A(A∧A)AA

A∧C( A∧C)( AC)(AC)(AC)

A∨B(A∧B)(( AA)∧(BB))( AA)(BB)

所以

F((AC)(AC))∨((BC)(BC))

(((AC)(AC))((AC)(AC)))(((BC)(BC))((BC)(BC)))

(2)F(A∧C)∨(B∧C)

(A∧(B∨B)∧C)∨((A∨A)∧B∧C)

(A∧B∧C)∨(A∧B∧C)∨(A∧B∧C)∨(A∧B∧C) m3∨m5∨m7 主析取范式 M0∧M1∧M2∧M4∧M6 主合取范式

22.证明下列推理：

1)P∨Q，Q∨R，RSPS。 2)P，P(Q(R∧S))QS。 3)(P∨Q)R(P∧Q)R。

4)A(BC)，B(CD)A(BD)。 5)AB，A∨C，CB，RBR。 6)B，CA，BA，C∨DD。

7)(A∨B)(P∨Q)，P，(BA)∨PA。 8)P(QR)，SQP(SR)。 9)(P∧Q)，Q∨R，RP。

证明 1)(1)P 附加前提

(2)P∨Q P

(3)Q T(1)(2)，I (4)Q∨R P

18

第1章 命题逻辑

(5)R T(3)(4)，I (6)RS P

(7)S T(5)(6)，I (8)PS CP

2)(1)P P (2)P(Q(R∧S)) P

(3)Q(R∧S) T(1)(2)，I (4)Q (5)R∧S T(3)(4)(6)S T(5)(7)QS CP 3)(1)P∧Q (2)P∨Q T(1)(3)(P∨Q)R P

(4)R T(2)(3)(5)(P∧Q)R CP 4)(1)A (2)A(BC) P

(3)BC T(1)(2)(4)B (5)C T(3)(4)(6)B(CD) P

(7)CD T(4)(6)(8)D T(5)(7)(9)A(BD) CP 5)(1)A∨C P (2)AB P (3)CB P

(4)B T(1)(2)(3)(5)RB P

(6)R T(4)(5)6)(1)B P (2)BA P

(3)A T(1)(2)附加前提 ，I ，I 附加前提 ，I ，I 附加前提 ，I 附加前提 ，I ，I ，I ，I ，I ，I

19

第1章 命题逻辑

(4)CA P

(5)C T(3)(4)，I (6)C∨D P

(7)D T(5)(6)，I 7)(1)(A∨B)(P∨Q) P (2)(P∨Q)(A∨B) T(1)，E (3)P P

(4)A∨B T(2)(3)，I (5)(BA)∨P P

(6)BA T(3)(5)，I (7)A∨B T(6)，E (8)(A∨B)∧(A∨B) T(4)(7)，I (9)A∧(B∨B) T(8)，E (10)A T(9)，E 8)(1)P(QR) P (2)P 附加前提 (3)QR T(1)(2)，I (4)SQ P

(5)SR T(3)(4)，I (6)P(SR) CP 9)(1)Q∨R P (2)R P

(3)Q T(1)(2)，I (4)(P∧Q) P (5)P∨Q T(4)，E (6)P T(3)(5)，I 23.证明R∨M、R∨S、M和S是不相容的。

证明 (R∨M)∧(R∨S)∧M∧S(R∨M)∧((R∧M∧S)∨(S∧M∧S))

(R∨M)∧(R∧M∧S)

((R∧R∧M∧S)∨(M∧R∧M∧S)) F

所以，R∨M、R∨S、M和S是不相容的。

24.某项工作需要派A、B、C和D 4个人中的2个人去完成，按下面3个条件，有几种派法？如何派？ (1)若A去，则C和D中要去1个人；

20

第1章 命题逻辑

(2)B和C不能都去； (3)若C去，则D留下。

解 设A：A去工作；B：B去工作；C：C去工作；D：D去工作。则根据题意应有：ACD，(B∧C)，CD必须同时成立。因此

(ACD)∧(B∧C)∧(CD)

(A∨(C∧ D)∨(C∧D))∧(B∨C)∧(C∨D)

(A∨(C∧ D)∨(C∧D))∧((B∧C)∨(B∧D)∨C∨(C∧D)) (A∧B∧C)∨(A∧B∧D)∨(A∧C)∨(A∧C∧D)

∨(C∧ D∧B∧C)∨(C∧ D∧B∧D)∨(C∧ D∧C)∨(C∧ D∧C∧D) ∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨(C∧D∧C∧D) F∨F∨(A∧C)∨F∨F∨(C∧ D∧B)∨F∨F∨(C∧D∧B)∨F∨(C∧D)∨F (A∧C)∨(B∧C∧ D)∨(C∧D∧B)∨(C∧D) (A∧C)∨(B∧C∧ D)∨(C∧D) T

故有三种派法：B∧D，A∧C，A∧D。

25.在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断： 甲说：王教授不是苏州人，是上海人。 乙说：王教授不是上海人，是苏州人。 丙说：王教授既不是上海人，也不是杭州人。

王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。试判断王教授是哪里人？

解 设设P：王教授是苏州人；Q：王教授是上海人；R：王教授是杭州人。则根据题意应有： 甲：P∧Q 乙：Q∧P 丙：Q∧R

王教授只可能是其中一个城市的人或者3个城市都不是。所以，丙至少说对了一半。因此，可得甲或乙必有一人全错了。又因为，若甲全错了，则有Q∧P，因此，乙全对。同理，乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为：

((P∧Q)∧((Q∧R)∨(Q∧R)))∨((Q∧P)∧(Q∧R))

(P∧Q∧Q∧R)∨(P∧Q∧Q∧R)∨(Q∧P∧Q∧R) (P∧Q∧R)∨(P∧Q∧R) P∧Q∧R T

因此，王教授是上海人。

21

第1章 命题逻辑

26.判断下述推理是否正确：

1) 如果2是偶数，则3是奇数。或者2是偶数或者2整除3，结果2整除3，所以3不是奇数。 2) 如果A努力工作，那么B或C感到愉快；如果B愉快，那么A不努力工作；如果D愉快那么C不愉快。所以，如果A努力工作，则D不愉快。

解 1)设A：2是偶数；B：3是奇数，C：2整除3；则推理化形式为： AB，A∨C，CB

该推理形式不正确。例如，设有一赋值：A＝F，B＝T，C＝T，则AB、A∨C、C都为真，但B为假。

2)设A：A努力工作；B、C、D分别表示B、C、D愉快；则推理化形式为： AB∨C，BA，DCAD 该推理形式正确。下面给出证明：

(1)A 附加前提 (2)AB∨C P

(3)B∨C T(1)(2)，I (4)BA P (5)AB T(4)，E (6)B T(1)(5)，I (7)C T(3)(6)，I (8)DC P

(9)D T(7)(8)，I (10)AD CP

22