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

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(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)如果天下雨，我就不去新华书店。 2 (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) 3 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)为可满足式。 4 (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，所以，公式为 5 可矛盾式。 (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 6 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 7 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 由真值表可知，