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

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)如果天下雨，我就不去新华书店。2(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)PQP∨Q(P∨Q)0001101110110100由真值表可知，公式(P∨Q)的成真赋值为：01，成假赋值为00、10、11。(2)PQRQ∨RP∧(Q∨R)30000010100111001011101110111011100000111由真值表可知，公式P∧(Q∨R)的成真赋值为：101、110、111，成假赋值为000、001、010、011、100。(3)PQ(P∨Q)P∧Q(P∨Q)(P∧Q)00011011100010001111由真值表可知，公式(P∨Q)(P∧Q)的成真赋值为：00、01、10、11，没有成假赋值。(4)PQQPP(QP)0001101110111011由真值表可知，公式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)真值表法：PQP∨QP∧Q(P∨Q)(P∧Q)00011011011100011001由真值表可知，公式(P∨Q)(P∧Q)为可满足式。公式法：因为(P∨Q)(P∧Q)(P∨Q)∨(P∧Q)(P∧Q)∨(P∧Q)，所以，公式(P∨Q)(P∧Q)为可满足式。4(2)真值表法：PQP∧QP∨Q(P∧Q)(P∨Q)00011011000101111111由真值表可知，公式(P∧Q)(P∨Q)为重言式。公式法：因为(P∧Q)(P∨Q)(P∧Q)∨(P∨Q)P∨Q∨P∨QT，所以，公式(P∧Q)(P∨Q)为重言式。(3)真值表法：PQRP∨QQ∨RR∨P∨Q(P∨Q)∧(Q∨R)∧(R∨P∨Q)00000101001110010111011111110011101110111111110100000000由真值表可知，公式(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)真值表法：PQRP∧QRP∧R∧Q(P∧QR)(P∧R∧Q)000001010011100101110111111111010000001000000010由真值表可知，公式(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)真值表法：PQQPP∧Q(QP)∧(P∧Q)00011011101101000000由真值表可知，公式(QP)∧(P∧Q)为可矛盾式。公式法：因为(QP)∧(P∧Q)(Q∨P)∧(P∧Q)(Q∧P)∧(P∧Q)F，所以，公式为5可矛盾式。(6)真值表法：PQPQ(PQ)(PQ)(PQ)00011011011001101111由真值表可知，公式(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)真值表法：PQP∧QP∨Q(P∧Q)∧(P∨Q)00011011000101110000由真值表可知，公式(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)真值表法：PQP∨Q(P∨Q)∧PP∧Q00011011011101000100由真值表可知，(P∨Q)∧PP∧Q。公式法：(P∨Q)∧P(P∧P)∨(Q∧P)P∧Q。(2)真值表法：PQP∧Q(P∨Q)∨(P∧Q)P600011011110011001100由真值表可知，(P∨Q)∨(P∧Q)P。公式法：(P∨Q)∨(P∧Q)(P∧Q)∨(P∧Q)P∧(Q∨Q)P。(3)真值表法：PQP∧Q(P∧Q)∨PP∨Q00011011000111011101由真值表可知，(P∧Q)∨PP∨Q。公式法：(P∧Q)∨P(P∨P)∧(Q∨P)P∨Q。(4)真值表法：PQRPQPR(PQ)∧(PR)P(Q∧R)00000101001110010111011111110011111101011111000111110001由真值表可知，P(Q∧R)(PQ)∧(PR)。公式法：P(Q∧R)P∨(Q∧R)(P∨Q)∧(P∨R)(PQ)∧(PR)。(5)真值表法：PQRPQRQ(PQ)∧(RQ)(P∨R)Q00000101001110010111011111110011101110111011001110110011由真值表可知，(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)真值表法：PQACPQ(P∧Q∧AC)∧(AP∨Q∨C)(A∧(PQ))C70000000100100011010001010110011110001001101010111100110111101111111100000000111111011111111111011101111111111101由真值表可知，(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)真值表法：PQPQ(PQ)PQ00011011111000010001由真值表可知，(PQ)PQ。公式法：(PQ)((P∧Q))(P∨Q))PQ。(8)真值表法：PQPQ(PQ)PQ00011011100001110111由真值表可知，(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。8(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)真值表法：PQPQ(PQ)P00011011110100100011由真值表可知，(PQ)P。分析法：若(PQ)为真，则PQ为假，从而P为真，而Q为假。故(PQ)P。公式法：因为(PQ)