《离散数学 习题答案》由会员分享，可在线阅读，更多相关《离散数学 习题答案（18页珍藏版）》请在金锄头文库上搜索。
1、第 1 章 命题逻辑1第第 1 章习题答案章习题答案1. 解 在上述 10 个句子中，(3)是感叹句，因此它不是命题。(6)虽然是陈述句，但它没有确定的值，因此它也不是命题。其余语句都是可判断真假的陈述句，所以都是命题。其中：(1)、(4) 、(8) 、(9) 、是简单命题，、(2) 、(5) 、(7)、(10) 是复合命题。2. 解 (1)是命题公式。(2)不是命题公式，因为括号不配对。(3)是命题公式。(4)是命题公式。(5)不是命题公式，因为 QR 没有意义。(6)不是命题公式，因为 R(QR)(PQ) 没有意义。3. 解 (1)符号化为(PQ)，其中，P：我们划船，Q：我们跑步。(2)
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)P
3、QPQ(PQ) 0 0 0 1 1 0 1 11 0 1 10 1 0 0由真值表可知，公式(PQ)的成真赋值为：01，成假赋值为 00、10、11。(2) P Q RQRP(QR) 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 10 1 1 1 0 1 1 10 0 0 0 0 1 1 1由真值表可知，公式 P(QR)的成真赋值为：第 1 章 命题逻辑2101、110、111，成假赋值为 000、001、010、011、100。(3)P Q( PQ)PQ(PQ)(PQ) 0 0 0 1 1 0 1 11 0 0 01 0 0 01 1 1 1由真
4、值表可知，公式(PQ)(PQ)的成真赋值为：00、01、10、11，没有成假赋值。(4)P QQPP(QP) 0 0 0 1 1 0 1 11 0 1 11 0 1 1由真值表可知，公式P(QP)的成真赋值为：00、10、11，成假赋值为：01。5. 解 (1)真值表法：P QPQPQ(PQ)(PQ) 0 0 0 1 1 0 1 10 1 1 10 0 0 11 0 0 1由真值表可知，公式(PQ)(PQ)为可满足式。公式法：因为(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)，所以，公式(PQ)(PQ)为可满足式。(2)真值表法：P QPQPQ(PQ)(PQ) 0 0 0 1 1 0 1 1
5、0 0 0 10 1 1 11 1 1 1由真值表可知，公式(PQ)(PQ)为重言式。公式法：因为(PQ)(PQ)(PQ)(PQ)PQPQT，所以，公式(PQ)(PQ)为重言式。(3)真值表法：P Q RPQQRRPQ(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 11 1 1 1 0 0 1 11 0 1 1 1 0 1 11 1 1 1 1 1 0 10 0 0 0 0 0 0 0第 1 章 命题逻辑3由真值表可知，公式(PQ)(QR)(RPQ)为矛盾式。公式法：因为(PQ)(QR)(RPQ)(PQ)QR(RPQ)F，
6、所以，公式(PQ)(QR)(RPQ)为矛盾式。(4)真值表法：P Q RPQRPRQ(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 11 1 1 1 1 1 0 10 0 0 0 0 0 1 00 0 0 0 0 0 1 0由真值表可知，公式(PQR)(PRQ)为可满足式。公式法：因为(PQR)(PRQ)( PQ)R)(PRQ)( PQR)(PRQ)( PQR)所以，公式(PQR)(PRQ)为可满足式。(5)真值表法：P QQPPQ(QP)(PQ) 0 0 0 1 1 0 1 11 0 1 10 1 0 00 0 0 0由真值表
7、可知，公式(QP)(PQ)为可矛盾式。公式法：因为(QP)(PQ)(QP)(PQ)(QP)(PQ)F，所以，公式为可矛盾式。(6)真值表法：P QPQ(PQ)(PQ)(PQ) 0 0 0 1 1 0 1 10 1 1 00 1 1 01 1 1 1由真值表可知，公式(PQ)(PQ)为永真式。公式法：因为(PQ)(PQ)(PQ)(QP)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)T所以，公式(PQ)(PQ)为永真式。(7)真值表法：P QPQPQ(PQ)(PQ) 0 0 0 1 1 0 1 10 0 0 10 1 1 10 0 0 0由真值表可知，公式(PQ)(PQ)为矛盾 式。第 1 章
8、命题逻辑4公式法：因为(PQ)(PQ)(PQ)(PQ)F，所以，公式(PQ)(PQ)为矛盾式。6. 证明 (1)真值表法：P QPQ(PQ)PPQ 0 0 0 1 1 0 1 10 1 1 10 1 0 00 1 0 0由真值表可知，(PQ)PPQ。公式法：(PQ)P(PP)(QP)PQ。(2)真值表法：P QPQ(PQ)(PQ)P 0 0 0 1 1 0 1 11 1 0 01 1 0 01 1 0 0由真值表可知，(PQ)(PQ)P。公式法：(PQ)(PQ)(PQ)(PQ)P(QQ)P。(3)真值表法：P QPQ(PQ)PPQ 0 0 0 1 1 0 1 10 0 0 11 1 0 11
9、1 0 1由真值表可知，(PQ)PPQ。公式法：(PQ)P(PP)(QP)PQ。(4)真值表法：P Q RPQPR(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 11 1 1 1 0 0 1 11 1 1 1 0 1 0 11 1 1 1 0 0 0 11 1 1 1 0 0 0 1由真值表可知，P(QR)(PQ)(PR)。公式法：P(QR)P(QR)(PQ)(PR)(PQ)(PR)。(5)真值表法：P Q RPQRQ(PQ)(RQ)( PR)Q 0 0 0 0 0 1 0 1 0 0 1 1 1 0 01 1 1 1
10、01 0 1 1 11 0 1 1 01 0 1 1 0第 1 章 命题逻辑51 0 1 1 1 0 1 1 10 1 10 1 10 1 10 1 1由真值表可知，(PQ)(RQ)(PR)Q)。公式法：(PQ)(RQ)(PQ)(RQ)(PR)Q(PR)Q(PR)Q)。(6)真值表法：P Q A CPQ(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
11、11 1 1 1 0 0 0 0 0 0 0 0 1 1 1 11 1 0 1 1 1 1 1 1 1 1 1 1 1 0 11 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 QPQ( PQ)PQ 0 0 0 1 1 0 1 11 1 1 00 0 0 10 0 0 1由真值表可知，(PQ)PQ。公式法：(PQ)(PQ)(PQ)PQ
12、。(8)真值表法：P QPQ(PQ)PQ 0 0 0 1 1 0 1 0 00 1 10 1 1第 1 章 命题逻辑61 1011由真值表可知，(PQ)PQ。公式法：(PQ)(PQ)(PQ)PQ。7. 解 (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 与
13、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)对偶式为 F(PQ)。(3)对偶式为(PQ)T。(4)对偶式为(PQ)(PQ)。9. 证明 (1)真值表法：P QPQ (PQ)P 0 0 0 1 1 0 1 11 1 0 10 0 1 00 0 1 1由真值表可知，(PQ)P。分析法：若(PQ)为真，则 PQ 为假，从而 P 为真，而 Q 为假。故(PQ)P。公式法：因为(PQ)P(PQ)PT，所以(PQ)P。(2)真值表法：P QPQ(PQ)QPQ 0 0 0 1 1 0 1 11 1 0 10 1 1 1
