离散数学及其应用(徐凤生版)数学习题答案

习题习题一一 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(PQ)。 (2)(PQ)(QP)。 (3)(PQ)(QP)。 (4)(QRS)。 (5)(PQR)S。 (6)(R(QR)(PQ)。 解 (1)是命题公式。 (2)不是命题公式，因为括号不配对。 (3)是命题公式。 (4)是命题公式。 (5)不是命题公式，因为 QR 没有意义。 (6)不是命题公式，因为 R(QR)(PQ) 没有意义。 3.将下列命题符号化： (1)我们不能既划船又跑步。 (2)我去新华书店，仅当我有时间。 (3)如果天下雨，我就不去新华书店。 (4)除非天不下雨，我将去新华书店。 (5)张明或王平都可以做这件事。 (6)“2 或 4 是素数，这是不对的”是不对的。 (7)只有休息好，才能工作好。 (8)只要努力学习，成绩就会好的。 (9)大雁北回，春天来了。 (10)小张是山东人或河北人。 解 (1)符号化为(PQ)，其中，P：我们划船，Q：我们跑步。 (2)符号化为 QR，其中，R：我有时间，Q：我去新华书店。 (3)符号化为 PQ，其中，P：天下雨，Q：我去新华书店。 (4)符号化为PQ，其中，P：天下雨，Q：我去新华书店。 (5)符号化为 PQ，其中，P：张明可以做这件事，Q：王平可以做这件事。 (6)符号化为(PQ)，“2 或 4 是素数，这是不对的”是不对的，其中，P：2 是素数，Q：4 是 素数，。 (7)符号化为 QP，其中，P：休息好，Q：工作好。 (8)符号化为 PQ，其中，P：努力学习，Q：成绩就会好的。 (9)符号化为 PQ，其中，P：大雁北回，Q：春天来了。 (10)符号化为 PQ，其中，P：小张是山东人，Q：小张是河北人。 4.构造下列命题公式的真值表，并据此说明哪些是其成真赋值，哪些是其成假赋值？ (1)(PQ)。 (2)P(QR)。 (3)(PQ)(PQ)。 (4)P(QP)。 解 (1) P Q PQ (PQ) 0 0 0 1 1 0 1 1 1 0 1 1 0 1 0 0 由真值表可知，公式(PQ)的成真赋值为：01，成假赋值为 00、10、11。 (2) P Q R QR P(QR) 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(QR)的成真赋值为：101、110、111，成假赋值为 000、001、010、011、 100。 (3) P Q ( PQ) PQ (PQ)(PQ) 0 0 0 1 1 0 1 1 1 0 0 0 1 0 0 0 1 1 1 1 由真值表可知，公式(PQ)(PQ)的成真赋值为：00、01、10、11，没有成假赋值。 (4) P Q QP P(QP) 0 0 0 1 1 0 1 1 1 0 1 1 1 0 1 1 由真值表可知，公式P(QP)的成真赋值为：00、10、11，成假赋值为：01。 5.分别用真值表法和公式法判断下列命题公式的类型： (1)(PQ)(PQ)。 (2)(PQ)(PQ)。 (3)(PQ)(QR)(RPQ)。 (4)(PQR)(PRQ)。 (5)(QP)(PQ)。 (6)(PQ)(PQ)。 (7)(PQ)(PQ)。 解 (1)真值表法： P Q PQ PQ (PQ)(PQ) 0 0 0 1 1 0 1 1 0 1 1 1 0 0 0 1 1 0 0 1 由真值表可知，公式(PQ)(PQ)为可满足式。 公式法： 因为(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)， 所以， 公式(PQ)(P Q)为可满足式。 (2)真值表法： P Q PQ PQ (PQ)(PQ) 0 0 0 1 1 0 1 1 0 0 0 1 0 1 1 1 1 1 1 1 由真值表可知，公式(PQ)(PQ)为重言式。 公式法： 因为(PQ)(PQ)(PQ)(PQ)PQPQT， 所以， 公式(PQ)(P Q)为重言式。 (3)真值表法： P Q R PQ QR RPQ (PQ)(QR)(RPQ) 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 1 1 1 0 0 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 0 0 0 由真值表可知，公式(PQ)(QR)(RPQ)为矛盾式。 公式法：因为(PQ)(QR)(RPQ)(PQ)QR(RPQ)F，所 以，公式(PQ)(QR)(RPQ)为矛盾式。 (4)真值表法： P Q R PQR PRQ (PQR)(PRQ) 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 由真值表可知，公式(PQR)(PRQ)为可满足式。 公式法：因为(PQR)(PRQ)( PQ)R)(PRQ) ( PQR)(PRQ)( PQR) 所以，公式(PQR)(PRQ)为可满足式。 (5)真值表法： P Q QP PQ (QP)(PQ) 0 0 0 1 1 0 1 1 1 0 1 1 0 1 0 0 0 0 0 0 由真值表可知，公式(QP)(PQ)为可矛盾式。 公式法：因为(QP)(PQ)(QP)(PQ)(QP)(PQ)F，所以，公式为 可矛盾式。 (6)真值表法： P Q PQ (PQ) (PQ)(PQ) 0 0 0 1 1 0 1 1 0 1 1 0 0 1 1 0 1 1 1 1 由真值表可知，公式(PQ)(PQ)为永真式。 公式法：因为(PQ)(PQ)(PQ)(QP)(PQ)(PQ) (PQ)(PQ)(PQ)(PQ)T 所以，公式(PQ)(PQ)为永真式。 (7)真值表法： P Q PQ PQ (PQ)(PQ) 0 0 0 1 1 0 1 1 0 0 0 1 0 1 1 1 0 0 0 0 由真值表可知，公式(PQ)(PQ)为矛盾式。 公式法：因为(PQ)(PQ)(PQ)(PQ)F，所以，公式(PQ)(PQ)为矛盾 式。 6.分别用真值表法和公式法证明下列各等价式： (1)(PQ)PPQ。 (2)(PQ)(PQ)P。 (3)(PQ)PPQ。 (4)P(QR)(PQ)(PR)。 (5)(PQ)(RQ)(PR)Q)。 (6)(PQAC)(APQC)(A(PQ)C。 (7)(PQ)PQ。 (8)(PQ)PQ。 证明 (1)真值表法： P Q PQ (PQ)P PQ 0 0 0 1 1 0 1 1 0 1 1 1 0 1 0 0 0 1 0 0 由真值表可知，(PQ)PPQ。 公式法：(PQ)P(PP)(QP)PQ。 (2)真值表法： P Q PQ (PQ)(PQ) P 0 0 0 1 1 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 由真值表可知，(PQ)(PQ)P。 公式法：(PQ)(PQ)(PQ)(PQ)P(QQ)P。 (3)真值表法： P Q PQ (PQ)P PQ 0 0 0 1 1 0 1 1 0 0 0 1 1 1 0 1 1 1 0 1 由真值表可知，(PQ)PPQ。 公式法：(PQ)P(PP)(QP)PQ。 (4)真值表法： P Q R PQ PR (PQ)(PR) P( QR) 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 0 1 1 1 1 1 0 0 0 1 1 1 1 1 0 0 0 1 由真值表可知，P(QR)(PQ)(PR)。 公式法：P(QR)P(QR)(PQ)(PR)(PQ)(PR)。 (5)真值表法： P Q R PQ RQ (PQ)(RQ) ( PR)Q 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 1 1 1 0 0 1 1 1 0 1 1 1 0 1 1 1 0 1 1 0 0 1 1 1 0 1 1 0 0 1 1 由真值表可知，(PQ)(RQ)(PR)Q)。 公式法：(PQ)(RQ)(PQ)(RQ)(PR)Q (PR)Q(PR)Q)。 (6)真值表法： P Q A C PQ (PQA C)(A PQC) (A(PQ)C 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 由真值表可知，(PQAC)(APQC)(A(PQ)C。 公式法：(PQAC)(APQC)(PQAC)(APQC) (PQAC)(APQC) (PQA)(APQ)C (PQA)(APQ)C ( A(PQ)(PQ)C ( A(PQ)C (A(PQ)C。 (7)真值表法： P Q PQ ( PQ) PQ 0 0 0 1 1 0 1 1 1 1 1 0 0 0 0 1 0 0 0 1 由真值表可知，(PQ)PQ。 公式法：(PQ)(PQ)(PQ)PQ。 (8)真值表法： P Q PQ (PQ) PQ 0 0 0 1 1 0 1 1 1 0 0 0 0 1 1 1 0 1 1 1 由真值表可知，(PQ)PQ。 公式法：(PQ)(PQ)(PQ)PQ。 7.设 A、B、C 为任意的三个命题公式，试问下面的结论是否正确？ (1)若 ACBC，则 AB。 (2)若 ACBC，则 AB。 (3)若AB，则 AB。 (4)若 ACBC，则 AB。 (5)若 ACBC，则 AB。 解 (1)不正确。例如，设有一赋值：AT，BF，CT，则 ACBC，但 AB 不成立。 (2)不正确。例如，设有一赋值：AT，BF，CF，则 ACBC，但 AB 不成立。 (3)正确。因为AB(AB)(BA)(AB)(BA)(B A)(AB) AB，所以，若AB，则 AB。 (4)不正确。例如，设有一赋值：AT，BF，CT，则 ACBC，但 AB 不成立。 (5)正确。因为，若 ACBC，则 AC 与 BC 等值。当 AC 与 BC 都为真时，A 和 C 等值 且 B 和 C 等值，从而 A 和 B 等值，此时 AB；当 AC 与 BC 都为假时，A 和 C 不等值且 B 和 C 也不 等值，从而 A 和 B 等值，此时 AB。 总之有，若 ACBC，则 AB。 8.试给出下列命题公式的对偶式： (1)(PQ)R。 (2)T(PQ)。 (3)(PQ)F。 (4)(PQ)(PQ)。 解 (1)对偶式为(PQ)R。 (2)对偶式为 F(PQ)。 (3)对偶式为(PQ)T。 (4)对偶式为(PQ)(PQ)。 9.分别用真值表法、分析法和公式法证明下列蕴涵式： (1)(PQ)P。 (2)(PQ)QPQ。 (3)PQP(PQ)。 (4)(PQ)(QR)(PR)。 证明 (1)真值表法： P Q PQ (PQ) P 0 0 0 1 1 0 1 1 1 1 0 1 0 0 1 0 0 0 1 1 由真值表可知，(PQ)P。 分析法：若(PQ)为真，则 PQ 为假，从而 P 为真，而 Q 为假。故(PQ)P。 公式法：因为(PQ)P(PQ)PT，所以(PQ)P。 (2)真值表法： P Q PQ (PQ)Q PQ 0 0 0 1 1 0 1 1 1 1 0 1 0 1 1 1 0 1 1 1 由真值表可知，(PQ)QPQ。 分析法：若 PQ 为假，都 P 和 Q 为假，于是 PQ 为真，从而(PQ)Q 为假。故(PQ)QP Q。 公式法：因为(PQ)Q)(PQ) (PQ)Q)(PQ) (PQ)Q)(PQ) (PQ)(QQ)(PQ) (PQ)(PQ) T 所以，(PQ)QPQ。 (3)真值表法： P Q PQ PQ P(PQ) 0 0 0 1 1 0 1 1 0 0 0 1 1 1 0 1 1 1 0 1 由真值表可知，PQP(PQ)。 分析法：若 P(PQ)为假，则 P 为真且 PQ 为假，于是 P 为真且 Q 为假，从而 PQ 为假。故 PQP(PQ)。 公式法：因为(PQ)(P(PQ)(PQ)(P(PQ) (PQ)(P(PQ) (PQ)(PQ) (PQ)(PQ) T 所以，PQP(PQ)。 (4)真值表法： P Q R PQ QR (PQ)(QR) PR 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 0 1 1 1 0 1 0 0 0 1 1 1 1 1 0 1 0 1 由真值表可知，(PQ)(QR)(PR)。 分析法：若 PR 为假，则 P 为真而 R 为假。当 Q 为真时，QR 为假；当 Q 为假时，PQ 为假。 从而不管 Q 取什么值，都有(PQ)(QR)为假。故(PQ)(QR)(PR)。 公式法：因为(PQ)(QR)(PR)(PQ)(QR)(PR) (PQ)(QR)PR (PQ)(QPR)(RPR) (PQ)(QPR) (PQPR)(QQPR) T 所以，(PQ)(QR)(PR)。 10.将下列命题公式化成与之等价的仅含联结词或的公式： (1)P(QR)。 (2)(P(QR)P。 解 因为 P(PP)PP PQ(PQ)(PQ)(PQ) PQ(PQ)PQ(PP)(QQ) P(PP)PP PQ(PQ)(PQ)(PQ) PQPQ(PP)(QQ) 所以 (1)P(QR)P(QR) P(Q)(Q)(RR) P(QQ)( QQ)(RR) (P(QQ)( QQ)(RR)(P(QQ)( QQ)(RR) P(QR) P(QR) P(Q)PR)(Q)PR) P(QQ)PR)( QQ)PR) (PP)(QQ)PR)( QQ)PR)(QQ)PR)( QQ)PR) (2)(P(QR)P(P(QR)P ( PP)(QR)(QR)P ( PP)(QR)(QR)P ( PP)(PP)(QR)(QR)(QR)(QR)P ( PP)(PP)(QR)(QR)(QR)(QR)( P P)(PP)(QR)(QR)(QR)(QR)(PP) (P(QR)P(P(QR)P ( PP)(QQ)(RR)P ( PP)(QQ)(RR)( PP)(QQ)(RR)P ( PP)(QQ)(RR)( PP)(QQ)(RR)P)( PP)(QQ)(RR)( PP)(QQ)(RR)P) 11.证明，和都不是全功能联结词组。 证明 命题 P 经联结词和反复运算只能得出 P，不能得出P，所以，不是全功能联结词 组。 命题 P 经联结词反复运算只能得出 P，不能得出P，所以不是全功能联结词组。 命题 P 经联结词反复运算只能得出 P 和P，不能得出 PQ，所以不是全功能联结词组。 12.证明，是最小全功能联结词组。 证明 因为 PQ(PQ) PQPQ(PQ) PQ(PQ)(QP)(PQ)(QP) 所以，是最小全功能联结词组。 13.完成定理 1.8 的证明。 证明 设 A 为简单析取式，其包含的所有命题变元为 p1、p2、pn。 若 A 为永真式， 但不同时含有某个命题变元及其否定， 则不妨设 Ap1p2pipi1pn， 于是当 p1、p2、pi的真值都是假，而 pi1、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 的合取范式，即 AA。若 A的某个简单析取式 Ai中不含命题变元 P 及其否定P， 将 Ai展成形式 AiAiTAi(PP)(AiP)(AiP)，继续这个过程，直到所有的简单析取式成 为大项。然后，消去重复的项及永真式之后，得到 A 的主合取范式。 下面证明其惟一性。 若 A 有两个与之等价的主合取范式 B 和 C，则 BC。由 B 和 C 是 A 的不同的主合取范式，不妨设大 项 Mi只出现在 B 中而不在 C 中，于是 i 的二进制为 B 的成假赋值，C 的成真赋值，与 BC 矛盾。因而 A 的主合取范式是惟一的。 17.完成定理 1.15 的证明。 证明 设命题公式 A 的真值为 F 的赋值所对应的大项为 M1、M2、Mk，令 BM1M2Mk。 下证 AB。 若 A 为假，则其赋值所对应的小项一定是 M1、M2、Mk中的某一项，不妨设为 Mi，因为 Mi为假， 而 M1、M2、Mi1、Mi1、Mk都为真，故 B 也为假。 若 A 为真，则其赋值所对应的大项一定不是 M1、M2、Mk中的某一项，此时 M1、M2、Mk都 为真，故 B 也为假。 因此，AB。 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(QR)。 (2)(PQ)R。 (3)(P(QR)(P(QR)。 (4)(PQ)Q)R。 (5)(PQ)(PQ)。 (6)(PQ)(P(QR)。 (7)(PQ)(RP)(RQ)P)。 (8)(P(PQ)(QR)(PR)。 解 (1)公式法：因为 P(QR)PQR 6 M 0 m 1 m 2 m 3 m 4 m 6 m 7 m 所以，公式 P(QR)为可满足式，其相应的成真赋值为 000、001、010、011、100、101、111：成 假赋值为：110。 真值表法： P Q R QR P(QR) 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 1 0 1 1 1 0 1 1 1 1 1 1 1 0 1 由真值表可知，公式 P(QR)为可满足式，其相应的成真赋值为 000、001、010、011、100、101、 111：成假赋值为：110。 (2)公式法：因为(PQ)R(PQ)R(PQ)R (P(QQ)R)(PP)QR) (PQR)(PQR)(PQR)(PQR) 2 M 4 M 6 M 0 m 1 m 3 m 5 m 所以，公式(PQ)R 为可满足式，其相应的成真赋值为 000、001、011、101、111：成假赋值为： 010、100、110。 真值表法： P Q R PQ (PQ)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 0 0 1 1 1 1 1 1 1 1 0 1 0 1 0 1 由真值表可知，公式(PQ)R 为可满足式，其相应的成真赋值为 000、001、011、101、111：成假 赋值为：010、100、110。 (3)公式法：因为(P(QR)(P(QR) (PQR)(P(QR)(QR) (PQR)(PQ)(PR)(QR) (PQR)(PQQ)(PQR)(PRQ)(PRR) (PQR)(PQR)(PQR) 4 M 5 M 6 M 0 m 1 m 2 m 3 m 7 m 所以，公式(P(QR)(P(QR)为可满足式，其相应的成真赋值为 000、001、010、011、 111：成假赋值为：100、101、110。 真值表法： P Q R QR P(QR) P(QR) (P(QR)(P(QR) 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 0 0 1 1 0 0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 0 1 1 1 1 1 0 0 0 1 由真值表可知， 公式(P(QR)(P(QR)为可满足式， 其相应的成真赋值为 000、 001、 010、 011、111：成假赋值为：100、101、110。 (4)公式法：因为(PQ)Q)R(PQ)Q)R (PQQ)R R (QQ)R (QR)(QR) (PP)QR)(PP)QR) (PQR)(PQR)(PQR)(PQR) 1 m 3 m 5 m 7 m 0 M 2 M 4 M 6 M 所以，公式(PQ)Q)R 为可满足式，其相应的成真赋值为 001、011、101、111：成假赋值为： 000、010、100、110。 真值表法： P Q R PQ (PQ)Q (PQ)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 1 1 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 由真值表可知，公式(PQ)Q)R 为可满足式，其相应的成真赋值为 001、011、101、111：成 假赋值为：000、010、100、110。 (5)公式法：因为(PQ)(PQ)(PQ)(PQ)(PQ) (PQ)(PQ)(PQ) 1 m 2 m 3 m 0 M 所以，公式(PQ)(PQ)为可满足式，其相应的成真赋值为 01、10、11：成假赋值为：00。 真值表法： P Q PQ PQ (PQ)(PQ) 0 0 0 1 1 0 1 1 1 1 1 0 0 1 1 0 0 1 1 1 由真值表可知，公式(PQ)(PQ)为可满足式，其相应的成真赋值为 01、10、11：成假赋值 为：00。 (6)公式法：因为(PQ)(P(QR)( PQ)(PQR) (PQ)(PQR) (PQP)(PQQ)(PQR) (PQ)(PQR) (PQ(RR)(PQR) (PQR)(PQR)(PQR) 0 M 1 M 2 m 3 m 4 m 5 m 6 m 7 m 所以，公式(PQ)(P(QR)为可满足式，其相应的成真赋值为 010、011、100、101、110、 111：成假赋值为：000、001。 真值表法： P Q R QR P(QR) PQ (PQ)(P(QR) 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 0 1 1 1 0 1 1 0 0 0 0 1 0 1 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 由真值表可知， 公式(PQ)(P(QR)为可满足式， 其相应的成真赋值为 010、 011、 100、 101、 110、111：成假赋值为：000、001。 (7)公式法：因为(PQ)(RP)(RQ)P) (PQ)(RP)(RQ)P) (PQ)(RP)(RQ)P) (PQ)(RP)(RP)(QP) (PQ)(PR)(PR) (PQ(RR)(P(QQ)R)(P(QQ)R) (PQR)(PQR)(PQR)(PQR)(PQR)(PQR) (PQR)(PQR)(PQR)(PQR)(PQR) 1 m 3 m 4 m 5 m 6 m 0 M 2 M 7 M 所以，公式(PQ)(RP)(RQ)P)为可满足式，其相应的成真赋值为 001、011、 100、101、110：成假赋值为：000、010、111。 真值表法： P Q R (PQ)(RP) (RQ)P) (PQ)(RP)(RQ)P) 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 0 1 1 1 0 0 0 0 0 0 1 1 1 0 0 1 0 1 1 1 1 0 由真值表可知， 公式(PQ)(RP)(RQ)P)为可满足式， 其相应的成真赋值为 001、 011、100、101、110：成假赋值为：000、010、111。 (8)公式法：因为(P(PQ)(QR)(PR) (PPQ)(QR)(PR) (QR)(PR) (QR(PR)(QR)(PR) (QRP)(QRR)(QR)PR) (PQR)(QR)(QPR)(RPR) (PQR)(PQR)(PQR)(PQR)(PQR)(PQR) (PQR)(PQR)(PQR)(PQR) 3 m 4 m 6 m 7 m 0 M 1 M 2 M 5 M 所以，公式(P(PQ)(QR)(PR)为可满足式，其相应的成真赋值为 011、100、110、 111：成假赋值为：000、001、010、101。 真值表法： P Q R P(PQ) (P(PQ)(QR) PR (P(PQ)(QR)(PR) 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 0 0 0 1 1 1 1 1 0 1 0 1 0 0 0 1 1 0 1 1 由真值表可知， 公式(P(PQ)(QR)(PR)为可满足式， 其相应的成真赋值为 011、 100、 110、111：成假赋值为：000、001、010、101。 20.使用将命题公式化为主范式的方法，证明下列各等价式： (1)(PQ)(PQ)(QP)(PQ)。 (2)PQ(PQ)PQ(PQ)。 (3)(PQ)(PQ)(PQ)。 (4)(PQ)(PR)(QR)(PQ)(PR)。 解 (1)因为(PQ)(PQ)(PQ)(PQ) (PQ)(PQ) (QP)(PQ)(QP)(PQ) (PQ)(QQ)(PP) (PQ) (PQ)P (PQ)(P(QQ) (PQ)(PQ)(PQ) (PQ)(PQ) 所以，(PQ)(PQ)(QP)(PQ)。 (2)因为 PQ(PQ)(P(QQ)(PP)Q)(PQ) (PQ)(PQ)(PQ)(PQ)(PQ) (PQ)(PQ)(PQ)(PQ) PQ(PQ)(P(QQ)(PP)Q)(PQ) (PQ)(PQ)(PQ)(PQ)(PQ) (PQ)(PQ)(PQ)(PQ) (PQ)(PQ)(PQ)(PQ) 所以，PQ(PQ)PQ(PQ)。 (3)因为(PQ)(PQ)(PQ) (PQ)(PQ) (PQ)(PQ) (PQ)(PQ) (PQ)(PQ)(PQ)(PQ) 所以，(PQ)(PQ)(PQ)。 (4)(PQ)(PR)(QR) (PQ(RR)(P(QQ)R)(PP)QR) (PQR)(PQR)(PQR)(PQR)(PQR)(PQR) (PQR)(PQR)(PQR)(PQR) (PQ)(PR) (PQ(RR)(P(QQ)R) (PQR)(PQR)(PQR)(PQR) (PQR)(PQR)(PQR)(PQR) 所以，(PQ)(PR)(QR)(PQ)(PR)。 21.设计一盏电灯的开关电路，要求受 3 个开关 A、B、C 的控制：当且仅当 A 和 C 同时关闭或 B 和 C 同时关闭时灯亮。设 F 表示灯亮。 (1)写出 F 在全功能联结词组中的命题公式。 (2)写出 F 的主析取范式与主合取范式。 解 (1)设 A：开关 A 关闭；B：开关 B 关闭；C：开关 C 关闭；F(AC)(BC)。 在全功能联结词组中： A(AA)AA AC( AC)( AC)(AC)(AC) AB(AB)( AA)(BB)( AA)(BB) 所以 F(AC)(AC)(BC)(BC) (AC)(AC)(AC)(AC)(BC)(BC)(BC)(BC) (2)F(AC)(BC) (A(BB)C)(AA)BC) (ABC)(ABC)(ABC)(ABC) 3 m 5 m 7 m 主析取范式 0 M 1 M 2 M 4 M 6 M 主合取范式 22.证明下列推理： 1)PQ，QR，RSPS。 2)P，P(Q(RS)QS。 3)(PQ)R(PQ)R。 4)A(BC)，B(CD)A(BD)。 5)AB，AC，CB，RBR。 6)B，CA，BA，CDD。 7)(AB)(PQ)，P，(BA)PA。 8)P(QR)，SQP(SR)。 9)(PQ)，QR，RP。 证明 1)(1)P 附加前提 (2)PQ P (3)Q T(1)(2)，I (4)QR P (5)R T(3)(4)，I (6)RS P (7)S T(5)(6)，I (8)PS CP 2)(1)P P (2)P(Q(RS) P (3)Q(RS) T(1)(2)，I (4)Q 附加前提 (5)RS T(3)(4)，I (6)S T(5)，I (7)QS CP 3)(1)PQ 附加前提 (2)PQ T(1)，I (3)(PQ)R P (4)R T(2)(3)，I (5)(PQ)R CP 4)(1)A 附加前提 (2)A(BC) P (3)BC T(1)(2)，I (4)B 附加前提 (5)C T(3)(4)，I (6)B(CD) P (7)CD T(4)(6)，I (8)D T(5)(7)，I (9)A(BD) CP 5)(1)AC P (2)AB P (3)CB P (4)B T(1)(2)(3)，I (5)RB P (6)R T(4)(5)，I 6)(1)B P (2)BA P (3)A T(1)(2)，I (4)CA P (5)C T(3)(4)，I (6)CD P (7)D T(5)(6)，I 7)(1)(AB)(PQ) P (2)(PQ)(AB) T(1)，E (3)P P (4)AB T(2)(3)，I (5)(BA)P P (6)BA T(3)(5)，I (7)AB T(6)，E (8)(AB)(AB) T(4)(7)，I (9)A(BB) T(8)，E (10)A T(9)，E 8)(1)P(QR) P (2)P 附加前提 (3)QR T(1)(2)，I (4)SQ P (5)SR T(3)(4)，I (6)P(SR) CP 9)(1)QR P (2)R P (3)Q T(1)(2)，I (4)(PQ) P (5)PQ T(4)，E (6)P T(3)(5)，I 23.证明 RM、RS、M 和S 是不相容的。 证明 (RM)(RS)MS(RM)(RMS)(SMS) (RM)(RMS) (RRMS)(MRMS) F 所以，RM、RS、M 和S 是不相容的。 24.某项工作需要派 A、 B、 C 和 D 4 个人中的 2 个人去完成， 按下面 3 个条件， 有几种派法？如何派？ (1)若 A 去，则 C 和 D 中要去 1 个人； (2)B 和 C 不能都去； (3)若 C 去，则 D 留下。 解 设 A：A 去工作；B：B 去工作；C：C 去工作；D：D 去工作。则根据题意应有：ACD，(B C)，CD 必须同时成立。因此