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

练习6.11. 判断下列语句哪些是命题，若是命题其真值是什么？（1）a+b+c。（2）x 0 。（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：他去了机房。 PQ（2）P：今晚我去书店。 Q：今晚我去图书馆。 PQ（3）P：我昨天去超市。 P（4）P：我们看电视。 Q：我们看电影。 (PQ)（5）P：我买到飞机票。 Q：我去海南。 PQ（6）P：小王坐飞机去上海。 Q：小王坐高铁去上海。 （PQ）(PQ) 或者(PQ)（7）原子命题（8）P：小李生病。 Q：小李每天都会练习书法。 PQ（9）P：侈。 Q：惰。 R：贫。 （(PQ)R）（(PQ) R）3. 判定下列符号串是否为命题公式。（1）PQ （2）(PQR)S（3）(PQ)P （4）P(PQ（5）P(PQ)(PQ)（6） (PQ) （QP）（7）（PR）（PQ）解：（1）不是（2）不是（3）是（4）不是（5）是（6）是（7）是4. 请给出下列命题公式的真值表。（1）PQPQPPQ0011011110001101（2）（PQ）（PQ）PQPQPQPQ（PQ）（PQ）0011000011010110010111100000（3）（PQ）RPQRPQ（PQ）（PQ）R000010001011010101011101100101101101110101111101（4）（PQ）（PQ）PQPQPQ（PQ）（PQ）00100011001001011100（5）（PQ）PPQPQ（PQ）P0011011110011111练习6.21. 试判定下列各式是重言式、可满足式还是矛盾式。（1）(PQ)(QP)PQPQQP(PQ)(QP)00111011001001111111由表中最后一列可以看出，原式为可满足式。（2）P(PQ)PQPPQP(PQ)00111011111000111011由表中最后一列可以看出，原式为重言式。（3）Q(PQ)PQPQ(PQ)Q(PQ)00100011001001011100由表中最后一列可以看出，原式为矛盾式。（4）PQ(PQ)PQPQPQPQ(PQ)00011010011000111111由表中最后一列可以看出，原式为重言式。（5）(PQ)(RQ)(PR)Q)PQRPQRQ(PQ)(RQ)PR(PR)Q(PQ)(RQ)(PR)Q)000111011001101100010111011011111111100011100101000101110111111111111111由表中最后一列可以看出，原式为可满足式。2.证明下列逻辑等价式： （1）AB (AB)(AB)证明：方法一 (AB)(AB)(AA)(AB) (BA)(BB)T(AB)(BA)T(BA)(AB)(BA)(AB)AB方法二：ABA BABABAB( (AB) (AB)(A B) ( (AB) (AB)001011111010010001100001001111100011由此真值表可见(A B) ( (AB) (AB) 是永真式，所以AB (AB)(AB)成立。方法三 假设为一指派。若(A B)=1，则(A)= (B)。(i)若(A)= (B)=0。则(A)= (B)=1,从而(AB)=1，进而(AB)(AB)=1.(ii)若(A)= (B)=1。则(AB)=1，进而（(AB)(AB)）=1。若(A B)=0，则(A)和(B)不相等。从而(A)和(B)也不相等。则(AB)=0且(AB)=0，从而（(AB)(AB)）=0。所以(A B) (AB) (AB)（2）A(BC) B(AC)证明：方法一A(BC) A(BC)A(BC)B(AC)B(AC)B(AC)方法二：ABCBCA(BC)ACB(AC)A(BC) B(AC)0001111100111111010011110111111110011011101111111100000111111111由此真值表可见A(BC) B(AC)是永真式，所以A(BC) B(AC)成立。方法三: 假设为一指派。若(A(BC)=1,分以下二种情况：（i）(A)=1，则(BC)=1. 若(B)=0，则(B(AC)=1.若(B)=1，则(C)=1,从而(B(AC)=1.(ii) (A)=0, 则(AC)=1。从而(B(AC)=1。若(A(BC)=0,则(A)=1, (B)=1, (C)=0,从而(B(AC)=0。所以：A(BC) B(AC)（3）A(BC) (AB)(AC)证明：(AB)(AC) (AB)(AC) (AB)(AC) (AB)(AC) (AAC)(BAC)BACB(AC)B(AC)（4）(AB)(AB) A 证明：(AB)(AB)(AB)(AB) A(BB) ATA3. 证明下列逻辑蕴涵式： （1）AB AB证明：（方法一）假设任一指派a ，使得a( AB)=1，要证a( AB)=1。由于a( AB)=1，于是a(A)=a(B)=1从而得到a( AB)=1。故AB AB得证。（方法二）AB (AB)(AB) AB（方法三）由于ABABABAB(AB)00011010011000111111所以AB(AB)是永真式，所以AB AB。（2）(AB)AA证明：假设任一指派a ，使得a( A)= 0，要证a(AB)A)=0。由于a(A)=0，于是无论B为真还是为假，都有a(AB)=1。从而a(AB)A)=0。故(AB)AA得证。（3）(AB)(AC)(BC) C 证明：(方法一)假设任一指派a ，使得a(C)=0要证a(AB)(AC)(BC)= 0（1）若a(A)= a(B)=0于是a(AB)= 0，此时a(AB)(AC)(BC)= 0（2）若a(A)=1 且 a(B)=0于是a( AC)= 0，此时a(AB)(AC)(BC)= 0（3）若a(A)=0 且 a(B)=1于是a( BC)= 0，此时a(AB)(AC)(BC)= 0（4）若a(A)=1 且 a(B)=1于是a( BC)= a( AC)= 0，此时a(AB)(AC)(BC)= 0故(AB)(AC)(BC) C得证。（方法二）假设任一指派a ，使得a(AB)(AC)(BC)= 1要证a(C)=1。由于a(AB)(AC)(BC)= 1, 所以a(AB)=1, 且a(AC)=1且a (BC)= 1。由a(AB)=1,得到a(A)=1或者a(B)=1。（1）若a(A)=1，则由a(AC)=1得到a(C)=1。（2）若a(B)=1，则由a(BC)=1得到a(C)=1.故(AB)(AC)(BC) C得证。(方法三) (AB)(AC)(BC) (AB)(AC)(BC) (AB)(AC)(BC) (AB)(AB)C) (AB)(AB)C)(AB)(AB) (AB)C)F(AB)C) (AB)C) C4. 化简下列各式：（1）(AB)(AB)(AB)解：(AB)(AB)(AB)(A(BB)(AB)(AF)(AB)A(AB)(AA)(AB)F(AB) AB（2）(QP)(PQ)解：(QP)(PQ)(QP)(PQ)(QP) (PQ)(QP) (PQ)(QPQ) (PPQ)T (PQ)(PQ) (PQ)（3）(PQ) (QP)解：(PQ) (QP)(PQ) (QP)(PQ) (PQ)T （4）B(AB)A)解：B(AB)A) B(AB)A) B(AB)A) B(AA) (AB) B(T(AB) B (AB)T（5）(Q(PQ)P)(QP)解：(Q(PQ)P)(QP)(Q(PQ)P)(QP)(Q(PQ)P)(QP)(QP)(QQ)P)(QP)(QP)FP)(QP)(QP)P)(QP)(QP) P)(QP)(QPP)(QP)(QP)(QP)(QQP) (P)QP)FFF练习6.31. 把下列各式化为析取范式：（1）(PQ)R解：(PQ)R(PQ)R (PQ)R（2）(PQ)R解：(PQ)R(PQ)R(PQ)RPQR（3）(PQ)(PQ)解：(PQ)(PQ)(PQ)(PQ) (PQ)(PQ) (PP)(PQ) (QP )(QQ) F(PQ) (QP )F (PQ) (PQ)（4）(QP)(PQ)解：(QP)(PQ)(QP)(PQ)(QP)(PQ) (QP)PQ 2. 把下列各式化为合取范式：（1）(PQ)R解：(PQ)R(PQ)R (PQ)R(PR)(QR)（2）B(AB)A)解：B(AB)A) B(AB)A) B(AB) A) (BA)(AB)(BAA) (BAB)(BT)(BAB)T(AB)(AB)（3）P(P(PQ)解：P(P(PQ) P(P(PQ)(QP) P(P(PQ)(QP)(PP)(PPQ) (PQP)（4）(P(QR)S解：(P(QR)S (P(QR)(QR)S (PQQ)(PQR)(PRQ)(PRR)S3. 求下列公式的主析取范式、主合取范式，并据主析取范式直接确定使该公式为真指派，据主合取范式直接确定使该公式为假指派。（1）(PQ) (PQR)解：求主析取范式(PQ) (PQR)(PQ(RR) (PQR)(PQR) (PQR) (PQR)使公式为真的指派有：(1,1,1)、(1,1,0)、(0,1,1)求主合取范式(PQ) (PQR)(PP ) (PQ) (PR) (QP) (QQ) (QR)(PQ) (PR) (PQ) Q (QR)(PQ(RR)(P(QQ)R)(PQ(RR)(PP)Q(RR)(PP)QR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR) (PQR)(PQR)(PQR)(PQR)(PQR)(PQR)使公式为假的指派有：(0,0,0)、(0,0,1)、(0,1,0)、(1,0,0)、(1,0,1)（2）(PQ)(PQ)解：求主析取范式(PQ)(PQ)(PQ)(PQ)(PQP)(PQQ)PQ(P(QQ)(PP)Q)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)使公式为真的指派有：(1,1)、(1,0) 、(0,1)求主合取范式(PQ)(PQ)(PQ)(PQ)(PQP)(PQQ)PQ使公式为假的指派有：(0,0)（3）P(P(Q(QR)解：求主析取范式P(P(Q(QR) P(P(Q(QR)P(P(QR)P(PQR)PQR(P(QQ) (RR)(PP) Q(RR)（(PP) (QQ) R）(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR)(PQR) (PQR)(PQR) (PQR) (PQR)使公式为真的指派有：(1,1,1)、(1,0,1)、(1,1,0)、(1,0,0)、(0,1,1)、(0,1,0)、(0,0,1)求主合取范式P(P(Q(QR) P(P(Q(QR)P(P(QR)P(PQR)PQR使公式为假的指派有：(0,0,0)（4）(P(QR)S解：求主合取范式(P(QR)S (P(QR)(QR)S (PQQ)(PQR)(PRQ)(PRR)S(PQR)(PRQ)S(PQR(SS)(PQR(SS)(PP)(QQ)(RR)S)(PQRS)(PQRS)(PQRS)(PQRS)(PQRS)(PQRS)(PQRS)(PQRS)(PQRS)(PQRS) (PQRS)(PQRS)(PQRS)(PQRS)(PQRS)(PQRS)(PQRS)(PQRS)(PQRS)(PQRS)(PQRS)(PQRS)使公式为假的指派有：(0,0,0,0)、(0,0,1,0)、(0,0,1,1)、(0,1,0,0)、(0,1,0,1)、(0,1,1,0) 、(1,0,0,0)、(1,0,1,0)、(1,1,0,0)、 (1,1,1,0) 使公式为真的指派有：(0,0,0,1)、(0,1,1,1)、(1,0,0,1)、(1,0,1,1)、(1,1,0,1)、(1,1,1,1)主析取范式为(PQRS)(PQRS)(PQRS)(PQRS)(PQRS)(PQRS) 4. A、B、C、D四个人中要派两个人出差，按下述三个条件有几种派法？如何派？（1）若去则C和D中要去一个人；（2）B和C不能都去；（3）C去则D要留下。解：设 A:A去出差。 B:B去出差。 C:C去出差。 D:D去出差。将题目中的三个条件进行形式化：A(CD) (BC) CD于是将下面的命题公式转化为析取范式：（A(CD)）(BC)(CD)(A(CD)(CD)）(BC)(CD)(A(CD)(CD)）(BC)(BD)(CC)(CD)(ABC)(ABD)(AC) (ACD)(CDBC)(CDBD) (CDC) (CDCD) (CDBC) (CDBD) (CDC) (CDCD)在析取范式中，有些项不符合题意，已用下划线标出，将这些项从始终删除，得到下式：(AC) (CDBC) (CDC) (CDBC) (CDC) (CDBD)(AC)(CDB)(CD)(CDB)(CDB)根据此式可以得到以下结论： 可以派B和D，或者A和D，或者A和C。练习6.41. 运用直接证法证明下列各式：（1）(PQ), QR, R P证明：Q R 引入前提R 引入前提Q 由析取三段论(PQ) 引入前提PQ 由置换 （据(AB) AB）P 由析取三段论（2）J(MN),(HG) J, HG MN证明：J(MN) 引入前提(HG) J 引入前提(HG) (MN) 由假言三段论HG 引入前提MN 由假言推理（3）BC,(BC)(HG)HG证明：BC 引入前提B 由化简C 由化简BC 由附加CB 由附加CB 由置换BC 由置换(CB)(BC) 由合取引入BC 由置换(BC)(HG) 引入前提(HG 由假言推理（4）PQ,(QR)R,(PS)S证明：(QR)R 引入前提QR 由化简QR 由置换PQ 引入前提PR 由假言三段论R 由化简P 由拒取(PS) 引入前提 PS 由置换S 由析取三段论2. 运用归谬法证明下列各式