6逻辑代数(上)命题演算习题答案

练习6.11.判断下列语句哪些是命题，若是命题其真值是什么？（1）a+b+c。（2）x0。（3）请进！（4）离散数学是计算机科学与技术专业的基础课程。（5）2009年7月我们去意大利的米兰旅游。（6）啊！这里真漂亮。（7）今天是星期四吗？（8）我明天或者后天去天津。（9）如果买不到飞机票，我就去不了海南。（10）除非你陪我，否则我不去。（11）本命题是假的。（12）如果雪是黑的，太阳从北边升起。解：（1）不是命题。（2）不是命题。（3）不是命题。（4）是命题。真值是1。（5）是命题。真值是0。（6）不是命题。（7）不是命题。（8）是命题。真值是0。（9）是命题。真值是1。（10）是命题。真值是1。（11）不是命题，是悖论。（12）是命题。真值是1。2.指出下列语句哪些是原子命题，哪些是复合命题？并将复合命题形式化。（1）他去了教室，也去了机房。（2）今晚我去书店或者去图书馆。（3）我昨天没有去超市。（4）我们不能既看电视又看电影。（5）如果买不到飞机票，我就去不了海南。（6）小王不是坐飞机去上海，就是坐高铁去上海。（7）喜羊羊和懒羊羊是好朋友。（8）除非小李生病，否则他每天都会练习书法。（9）侈而惰者贫，而力而俭者富。（韩非：《韩非子显学》）解：（1）P：他去了教室。Q：他去了机房。P∧Q（2）P：今晚我去书店。Q：今晚我去图书馆。P∨Q（3）P：我昨天去超市。P（4）P：我们看电视。Q：我们看电影。(P∧Q)（5）P：我买到飞机票。Q：我去海南。PQ（6）P：小王坐飞机去上海。Q：小王坐高铁去上海。（P∨Q）∧(P∧Q)或者(PQ)（7）原子命题（8）P：小李生病。Q：小李每天都会练习书法。PQ（9）P：侈。Q：惰。R：贫。（(P∧Q)R）∧（(P∧Q)R）3.判定下列符号串是否为命题公式。（1）P∧∨Q（2）(P∨QR)→S（3）(P∨Q)→P（4）P→(P∨Q（5）P∧(P→Q)∧(P→Q)（6）(P∨Q)（Q∧P）（7）（P∧R）∨（P→Q）解：（1）不是（2）不是（3）是（4）不是（5）是（6）是（7）是4.请给出下列命题公式的真值表。（1）P∨QPQPP∨Q0011011110001101（2）（P∧Q）∨（P∧Q）PQPQP∧QP∧Q（P∧Q）∨（P∧Q）0011000011010110010111100000（3）（P∨Q）RPQRP∨Q（P∨Q）（P∨Q）R000010001011010101011101100101101101110101111101（4）（PQ）∧（P∧Q）PQPQP∧Q（PQ）∧（P∧Q）00100011001001011100（5）（PQ）∨PPQPQ（PQ）∨P0011011110011111练习6.21.试判定下列各式是重言式、可满足式还是矛盾式。（1）(P→Q)→(Q→P)PQP→QQ→P(P→Q)→(Q→P)00111011001001111111由表中最后一列可以看出，原式为可满足式。（2）┐P→(P→Q)PQ┐PP→Q┐P→(P→Q)00111011111000111011由表中最后一列可以看出，原式为重言式。（3）Q∧┐(P→Q)PQP→Q┐(P→Q)Q∧┐(P→Q)00100011001001011100由表中最后一列可以看出，原式为矛盾式。（4）P∧Q→(PQ)PQP∧QPQP∧Q→(PQ)00011010011000111111由表中最后一列可以看出，原式为重言式。（5）(PQ)∨(RQ)((P∨R)Q)PQRPQRQ(PQ)∨(RQ)P∨R(P∨R)Q(PQ)∨(RQ)((P∨R)Q)000111011001101100010111011011111111100011100101000101110111111111111111由表中最后一列可以看出，原式为可满足式。2.证明下列逻辑等价式：（1）AB(A∧B)∨(┐A∧┐B)证明：方法一(A∧B)∨(┐A∧┐B)(A∨┐A)∧(A∨┐B)∧(B∨┐A)∧(B∨┐B)T∧(A∨┐B)∧(B∨┐A)∧T(┐B∨A)∧(┐A∨B)(BA)∧(AB)AB方法二：ABABA∧B┐A┐B┐A∧┐B((A∧B)∨(┐A∧┐B))(AB)((A∧B)∨(┐A∧┐B))001011111010010001100001001111100011由此真值表可见(AB)((A∧B)∨(┐A∧┐B))是永真式，所以AB(A∧B)∨(┐A∧┐B)成立。方法三假设α为一指派。若α(AB)=1，则α(A)=α(B)。(i)若α(A)=α(B)=0。则α(┐A)=α(┐B)=1,从而α(┐A∧┐B)=1，进而α(A∧B)∨(┐A∧┐B)=1.(ii)若α(A)=α(B)=1。则α(A∧B)=1，进而α（(A∧B)∨(┐A∧┐B)）=1。若α(AB)=0，则α(A)和α(B)不相等。从而α(┐A)和α(┐B)也不相等。则α(A∧B)=0且α(┐A∧┐B)=0，从而α（(A∧B)∨(┐A∧┐B)）=0。所以(AB)(A∧B)∨(┐A∧┐B)（2）A→(B→C)B→(A→C)证明：方法一A→(B→C)┐A∨(B→C)┐A∨(┐B∨C)┐B∨(┐A∨C)┐B∨(AC)B→(A→C)方法二：ABCB→CA→(B→C)A→CB→(A→C)A→(B→C)B→(A→C)0001111100111111010011110111111110011011101111111100000111111111由此真值表可见A→(B→C)B→(A→C)是永真式，所以A→(B→C)B→(A→C)成立。方法三:假设α为一指派。若α(A→(B→C))=1,分以下二种情况：（i）α(A)=1，则α(B→C)=1.若α(B)=0，则α(B→(A→C))=1.若α(B)=1，则α(C)=1,从而α(B→(A→C))=1.(ii)α(A)=0,则α(A→C)=1。从而α(B→(A→C))=1。若α(A→(B→C))=0,则α(A)=1,α(B)=1,α(C)=0,从而α(B→(A→C))=0。所以：A→(B→C)B→(A→C)（3）A→(B→C)(A→B)→(A→C)证明：(A→B)→(A→C)(┐A∨B)→(┐A∨C)┐(┐A∨B)∨(┐A∨C)(A∧┐B)∨(┐A∨C)(A∨┐A∨C))∧(┐B∨┐A∨C)┐B∨┐A∨C┐B∨(A→C)B→(A→C)（4）┐(┐A∨┐B)∨┐(┐A∨B)A证明：┐(┐A∨┐B)∨┐(┐A∨B)(A∧B)∨(A∧┐B)A∧(B∧┐B)A∧TA3.证明下列逻辑蕴涵式：（1）A∧BAB证明：（方法一）假设任一指派，使得(A∧B)=1，要证(AB)=1。由于(A∧B)=1，于是(A)=(B)=1从而得到(AB)=1。故A∧BAB得证。（方法二）A∧B(A∧B)∨(┐A∧┐B)AB（方法三）由于ABA∧BABA∧B→(AB)00011010011000111111所以A∧B→(AB)是永真式，所以A∧BAB。（2）(A→B)→AA证明：假设任一指派，使得(A)=0，要证((A→B)→A)=0。由于(A)=0，于是无论B为真还是为假，都有(A→B)=1。从而((A→B)→A)=0。故(A→B)→AA得证。（3）(A∨B)∧(A→C)∧(B→C)C证明：(方法一)假设任一指派，使得(C)=0要证((A∨B)∧(A→C)∧(B→C))=0（1）若(A)=(B)=0于是(A∨B)=0，此时((A∨B)∧(A→C)∧(B→C))=0（2）若(A)=1且(B)=0于是(A→C)=0，此时((A∨B)∧(A→C)∧(B→C))=0（3）若(A)=0且(B)=1于是(B→C)=0，此时((A∨B)∧(A→C)∧(B→C))=0（4）若(A)=1且(B)=1于是(B→C)=(A→C)=0，此时((A∨B)∧(A→C)∧(B→C))=0故(A∨B)∧(A→C)∧(B→C)C得证。（方法二）假设任一指派，使得((A∨B)∧(A→C)∧(B→C))=1要证(C)=1。由于((A∨B)∧(A→C)∧(B→C))=1,所以(A∨B)=1,且(A→C)=1且(B→C)=1。由(A∨B)=1,得到(A)=1或者(B)=1。（1）若(A)=1，则由(A→C)=1得到(C)=1。（2）若(B)=1，则由(B→C)=1得到(C)=1.故(A∨B)∧(A→C)∧(B→C)C得证。(方法三)(A∨B)∧(A→C)∧(B→C)(A∨B)∧(┐A∨C)∧(┐B∨C)(A∨B)∧((┐A∨C)∧(┐B∨C))(A∨B)∧((┐A∧┐B)∨C)(A∨B)∧(┐(A∨B)∨C)((A∨B)∧┐(A∨B))∨((A∨B)∧C)F∨((A∨B)∧C)((A∨B)∧C)C4.化简下列各式：（1）(A∨┐B)∧(A∨B)∧(┐A∨┐B)解：(A∨┐B)∧(A∨B)∧(┐A∨┐B)(A∨(┐B∧B))∧(┐A∨┐B)(A∨F)∧(┐A∨┐B)A∧(┐A∨┐B)(A∧┐A)∨(A∧┐B)F∨(A∧┐B)A∧┐B（2）(┐Q→P)→(P→Q)解：(┐Q→P)→(P→Q)(Q∨P)→(┐P∨Q)┐(Q∨P)∨(┐P∨Q)(┐Q∧┐P)∨(┐P∨Q)(┐Q∨┐P∨Q)∧(┐P∨┐P∨Q)T∧(┐P∨Q)(┐P∨Q)(P→Q)（3）(P→Q)(┐Q→┐P)解：(P→Q)(┐Q→┐P)(┐P∨Q)(Q∨┐P)(┐P∨Q)(┐P∨Q)T（4）B∨┐((┐A∨B)∧A)解：B∨┐((┐A∨B)∧A)B∨(┐(┐A∨B)∨┐A)B∨((A∧┐B)∨┐A)B∨((A∨┐A)∧(┐A∨┐B))B∨(T∧(┐A∨┐B))B∨(┐A∨┐B)T（5）(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)∧(Q∧┐P)((Q∧┐P)∨F→P)∧(Q∧┐P)((Q∧┐P)→P)∧(Q∧┐P)(┐(Q∧┐P)∨P)∧(Q∧┐P)(┐Q∨P∨P)∧(Q∧┐P)(┐Q∨P)∧(Q∧┐P)(┐Q∧Q∧┐P)∨(P)∧Q∧┐P)F∨FF练习6.31.把下列各式化为析取范式：（1）(P→Q)→R解：(P→Q)→R┐(┐P∨Q)∨R(P∧┐Q)∨R（2）(┐P∧Q)→R解：(┐P∧Q)→R┐(┐P∧Q)∨R(P∨┐Q)∨RP∨┐Q∨R（3）┐(P∧Q)∧(P∨Q)解：┐(P∧Q)∧(P∨Q)┐(P∧Q)∧(P∨Q)(┐P∨┐Q)∧(P∨Q)(┐P∧P)∨(┐P∧Q)∨(┐Q∧P)∨(┐Q∧Q)F∨(┐P∧Q)∨(┐Q∧P)∨F(┐P∧Q)∨(P∧┐Q)（4）(┐Q→P)→(P→┐Q)解：(┐Q→P)→(P→┐Q)(Q∨P)→(┐P∨┐Q)┐(Q∨P)∨(┐P∨┐Q)(┐Q∧┐P)∨┐P∨┐Q2.把下列各式化为合取范式：（1）(P→Q)→R解：(P→Q)→R┐(┐P∨Q)∨R(P∧┐Q)∨R(P∨R)∧(┐Q∨R)（2）┐B∨┐((┐A∨B)∧A)解：┐B∨┐((┐A∨B)∧A)┐B∨(┐(┐A∨B)∨┐A)┐B∨((A∧┐B)∨┐A)(┐B∨┐A)∨(A∧┐B)(┐B∨┐A∨A)∧(┐B∨┐A∨┐B)(┐B∨T)∧(┐B∨┐A∨┐B)T∧(┐A∨┐B)(┐A∨┐B)（3）P(P∧(PQ))解：P(P∧(PQ))┐P∨(P∧(PQ)∧(QP))┐P∨(P∧(┐P∨Q)∧(Q∨P))(┐P∨P)∧(┐P∨┐