数理逻辑习题答案.doc

P184 习题10.110.1.1 解： PRQ ； QR ； PQ 我去镇上，当且仅当我有时间且天不下雪。 我若去镇上则我有时间，并且我若有时间则去镇上。 我有时间或我去镇上，此话不对。（并非如此）10.1.2 解： TTF TF T TTF(TT(FF) F(TTF) FF F (FTT)F(TT)T) F(FT) T (TT)T( ) T (TF)(FF) FT F T( )TT TT T10.1.3 解： P：天下雨；Q：我不去； 正：PQ ； 逆：QP ； 反：PQ 。 P：你去； Q：我逗留； 正：QP ； 逆：PQ ； 反：QP 。 P：n是大于2的正整数； Q：方程xn+yn=zn无正整数解。 正：PQ ； 逆：QP ； 反：PQ。P201 习题10.2P QPQ(PQ)P全式0 01000 11001 00101 111110.2.1 解：P Q RQRPQPR(PQR)(PQ)(PR)全式0 0 00001000 0 10011000 1 00101000 1 11110101 0 00110101 0 10110101 1 00110101 1 1111010 P Q RPQQRPQQR(PQQR)PR全式0 0 00010100 0 10010000 1 01001110 1 11110001 0 01001111 0 11001001 1 01001111 1 1111100 P Q RPQPRQ全式0 0 0001010 0 1001000 1 0001110 1 1001111 0 0110011 0 1111001 1 0010011 1 101111 10.2.2 解： 否。无论基础条款还是归纳条款都不能产生P，Q连在一起的情况。 是。根据基础，P，Q，R 是； 根据归纳，P，(PQ) 皆是； 又根据归纳，P(PQ) 是； 又根据归纳，(P(PQ)R 是。 否。无论基础条款还是归纳条款都不能产生。 是。根据基础，P，Q，R 是； 根据归纳，RP 是； 又根据归纳，Q(RP) 是； 又根据归纳，(Q(RP)P 是。10.2.3 解： P(PQ)Q(P(PQ)Q(PP)(PQ)Q (F(PQ)Q(PQ)Q(PQ)QP(QQ) PTT (PQ)(QR)(PR)(PQ)(QR)(PR) (PQ)(PR)(QQ)(QR)(PR) (PQ)(PR)F(QR)(PR) (PQ)(PR)(QR)(PR) (PQ)(PR)(QR)(PR) (PQ)(PR)(QR)(PR) (PQPR)(PRPR)(QRPR) (TQR)(TT)(TQP)TTT T (PQ)(PQ)(PQ)(PQ)T (PQ)(PQPQ)(PQ)(PQ)TP189 习题10.310.3.1 解：P PP PQ (PP)(QQ) PQ (PQ)(PQ) PQ (PPQ)(PPQ) PQ (PPQ)(QQP)10.3.2 解：P PP PQ (PQ)(PQ) PQ (PP)(QQ) PQ P(QQ) P(PQ) PQ (PQ)(PP)(QQ)10.3.3 解：PQ (PQ) (PQ) PQ PQ PQ (PQ)(QP)(PQ)(QP) (PQ)(QP) T PP F (PP)10.3.4 解：PQ (PQ) (PQ) (P(QF)F PQ PQ (PF) Q P PF T PP PQ (PQ)(QP) (PQ)(QP)F)F10.3.5 解：P TP PQ P(TQ) PQ T(TP)Q) PQ (T(PQ)(T(T(QP) F TT10.3.6 证： PQ(PQ)(QP)QP。同样方法可证得 PQ QP。 令 P=Q=T，S=F， P(QS) (P(QS) (T(TF) F (PQ)S (PQ)S) (TT)F) T 不可结合。同样方法可证得也不可结合。 10.3.7 证： PQ(PQ)(QP)(QP)(PQ)QP P(QR)(P(QR)(RQ)(QR)(RQ)P) (PQR)(PRQ)(QR)(RQ)P) (PQR)(PRQ)(QR)(RQ)P) (PQR)(PQR)(PQR)(PQR) (PQ)R(PQ)(QP)R)(PQ)(QP)R) (PQ)(QP)R)(PQR)(QPR) (PQ)(QP)R) (PQR)(QPR) (PQR)(PQR)(PQR)(QPR) P(QR) (PQ)R 。 P(QR)P(QR)(RQ)(PQR)(PQR) (PQ)(PR)(PQ)(PR)(PQ)(PR) (PQ)(PR)(PQ)(PR) (PQR)(PQR) P(QR)(PQ)(PR) 。 10.3.8 证： PQ(PQ)(QP)(QP)(PQ)QP P(QR)(P(QR)(RQ)(QR)(RQ)P) (PQR)(PQR)(QR)(QR)P) (PQR)(PQR)(QR)(QR)P) (PQR)(PQR)(PQR)(PQR) (PQ)R(PQ)(PQ)R)(PQ)(PQ)R) (PQ)(PQ)R)(PQR)(PQR) (PQ)(PQ)R)(PQR)(PQR) (PQR)(PQR)(PQR)(PQR) P(QR) (PQ)R 。 P(QR)P(QR)(RQ)(PQR)(PQR) (PQ)(PR)(PQ)(PR)(PQ)(PR) (PQ)(PR)(PQ)(PR) (PQR)(PQR) P(QR) (PQ)(PR) 。 P192 习题10.410.4.1 解：永真：1，4，6，10； 永假：9，11； 偶然：2，3，5，7，8，12。10.4.2 解： PQR(PQR) P(QRP)P(QR)P)P(QR)P) P(P(QR)(PP)(QR)P(QR) (P(QR)(PQR) P(QP)P(QP)P(PQ)(PP)QTQT10.4.3 证： (PQ)P)T(PQ)P(PQ)P(PQ)P P(PQ)(PP)QTQT (QP)(PQ)(QQ)P(QP)(PQ)TP (QP)(PQ)P(QP)(PQ)P(PQ)(QP)P (PQ)(PQ)PP(QQ)PPFPPPT (PQ)P)F(PQ)P)(PQ)P (PQ)PP(QP)P(PQ)(PP)QTQT (PP)(PP)F(PP)(PP)(PP)(PP) (PP)FT P QPPQQPP(QP)P(PQ)0 0111110 1110111 0001111 101111PQQP00101010111110.4.4 证： P QPQPQ0 0010 1011 0001 111P QQPQ(PQ)PQ0 011000 101001 010111 10100 P Q RPQRQPR(PQ)(RQ)PRQ0 0 0110110 0 1101000 1 0110110 1 1111111 0 0011001 0 1001001 1 0111111 1 111111 P Q RQRPQPRP(QR)(PQ)(PR)0 0 0111110 0 1111110 1 0011110 1 1111111 0 0100111 0 1101111 1 0010001 1 111111 P Q(PQ)(PQ)(PQ)(PQ)PQPQ(PQ)(PQ)0 00100000 11110111 01111011 1100000 10.4.5 证： PPQP(PQ)(PP)(PQ) T(PQ)PQPQ (PQ)(PQ)(PQ) (P(QQ)(PQ)(PF)(PQ)P(PQ) (PP)(PQ)F(PQ)PQ(PQ) (PQ)Q(PQ)Q(PQ)Q(PQ)(QQ) (PQ)TPQ (Q(PP)(R(PP)(QF)(RF)QRRQ Q(PQ)P)Q(PP)(QP)Q(F(QP) Q(QP)Q(QP)(QQ)PTPT (PQ)(PQ)(PQ)(PQ)P(QQ)PTP10.4.6 解： PP(QQ)(PP)(QQ) TF T (PP)Q)(PP)R)(RQ)(TQ)(TR)(RQ) (QR)(RQ)QR (PQ)(QP)R(PQ)(PQ)RTRR (P(QS)(P(QS)(PP)(QS)T(QS)(QS)。P195 习题10.510.5.1 解：永假式代入后仍为永假式。 偶然式代入后不必为偶然式。如P为偶然，但用QQ代入P后，为永真。 永假式置换后仍为永假式。偶然式置换后仍为偶然式。10.5.2 解： (PQ)(PQ)R)(PQ)(PQ) (Q(PP)(PP)Q)10.5.3 解： 是 的置换实例。10.5.4 证：(PQ)* (PQ)* (PQ) PQ (PQ)* (PQ)* (PQ) PQ P198 习题10.610.6.1 解： (PQ)(PQ) (PQ)(PQ)(PQ) (PQ)(PQ)(PQ) m3m1m2 (1,2,3) 主析取范式 PQ M0 (0) 主合取范式 P(P(Q(QR)P(P(Q(QR)PQR(0) 主合 (PQR)(PQR)(PQR)(PQR) (PQR)(PQR)(PQR) (1,2,3,4,5,6,7) 主析： (PQR)(P(QR)(P(QR)(P(QR) (PQR)(PQR) (0,7) 主析取范式 (PQR)(PQR)(PQR)(PQR) (PQR)(PQR) (1,2,3,4,5,6) 主合取范式 (PQS)(PQR) (PQRS)(PQRS)(PQRS)(PQRS) (6,7,9,11) 主析取范式 主合取范式(0,1,2,3,4,5,8,10,12,13,14,15)10.6.2 解：设 A1表示“A第一”，A2表示“A第二”，以此类推。 甲说 乙说 丙说 (A1B2)(A1B2)(C2D4)(C2D4)(A2D4)(A2D4) (A1B2)(A1B2)(A2C2D4)(A2C2D4) (A1A2B2C2D4)(A1A2B2C2D4) (A1A2B2C2D4)(A1A2B2C2D4) 分析：第一项：A第一同时又第二，不可能。 第二项：A第一，D第四，B和C都不第二，第二无人，不可能。 第三项：A,B,C都第二，不可能。 第四项：无矛盾。B第二，D第四，A不第一，只有C第一，A第三。 结果：C，B，A，D 。 注：也可进一步把显而易见的约束条件列出，并与上面的结果相合取。 约束条件： (A1A2)(A2B2)(A2C2)(B2C2)(A2B2C2D4) (A1A2)(A2B2)(A2C2)(B2C2)(A2B2C2D4) (A1B2)A2)(A2B2)C2)(A2B2C2D4) (A1A2B2)(A2B2)(A1B2C2)(A2C2)(A2B2C2D4) (A2B2)(A1B2C2)(A2C2)(A2B2C2D4) (A1A2B2C2)(A2B2C2)(A2B2C2) (A2B2D4)(A1B2C2D4)(A2C2D4) (A1A2B2C2)(A2B2C2)(A2B2C2) (A2B2D4)(A1B2C2D4)(A2C2D4) 将这六项与前面结果的四项相交 (A1A2B2C2D4)(A1A2B2C2D4) (A1A2B2C2D4)(A1A2B2C2D4) (A1A2B2C2)(A2B2C2)(A2B2C2) (A2B2D4)(A1B2C2D4)(A2C2D4) FFFFFFF(A1A2B2C2D4) FFFFFFFFFFFFFFFF A1A2B2C2D4P204 习题10.710.7.1 证：P Q RPQ(QR)RP0 0 011110 0 111010 1 010110 1 111011 0 001101 0 101001 1 010101 1 11100 P QPQPPQ0 0110 1111 0001 111P QPPQPQ0 01000 11101 00101 1011P QQPQ0 0110 1011 0101 10110.7.2 无效。 无效。P Q RP(QR)PQ0 0 0100 0 1100 1 0100 1 1101 0 0101 0 1101 1 0011 1 111P Q RPQPRQR0 0 00110 0 10110 1 01100 1 11111 0 01011 0 11111 1 01001 1 1111 有效。 有效。10.7.3 证： 给出(A,B,C,D,E)一组指派：(F,F,T,F,T)。 给出(A,B,C)一组指派：(F,T,F)。10.7.4 符号化：M：煤将涨价；D：大米将涨价；S：铁路中断运输； (MD)，SM S 证： (MD) P MD T E14 M T I1 SM P S T I12 符号化：A：今天下雨；B：明天下雨；C：后天下雨； A(BC)，B(CA) A 证： B(CA) P (BC)(BA) T E8 BA T I2 BA T E36 A(BC) P (AB)(AC) T E8 AB T I1 BA T E1 BA T E36 BB T E20 永真式引入 A T I15 符号化：A：李敏来通讯工程学院； C：王军看望李敏； D：利民出差到南京； B：王军生病； (AB)C，DA，B DC 证： D P (附加) DA P A T I10 B P AB T I9 (AB)C P C T I10 DC CP10.7.5 证： (AB)(AC)，(BC)，DA D (AB)(AC) P AB T I1 AC T I2 BA T E36 CA T E36 (BC) P BC T E11 A T I15 DA P AD T E1 D T I11 PQR，RS，S PQ S P RS P SR T E1 R T I11 PQR P (PQ) T I12 PQ T E11 BC，(BC)(HG) GH BC P B T I1 C T I2 CB T I6 BC T I6 (BC)(CB) T I9 BC T E37 (BC)(HG) P HG T I10 GH T E1 (PQ)R，QS R QS P Q T I1 PQ T I6 (PQ)R P R T I1010.7.6 证： PQ，QR，RS PS P P(附加) PQ P Q T I11 QR P R T I11 RS P S T I10 PS CP PQ P(PQ) P P(附加) PQ P Q T I10 PQ T I9 P(PQ) CP PQR PQR PQ P(附加) P T I1 PQ T I3 PQR P R T I10 PQR CP P(QR)，Q(RS) P(QS) P P(附加) P(QR) P QR T I10 Q P(附加) R T I10 Q(RS) P RS T I10 S T I10 QS CP P(QS) CP10.7.7 证： RQ，RS，SQ，PQ P (P) P(附加) P T E10 RQ P SQ P RS P Q T I15 PQ P Q T I10 QQ T I9 SQ，SR，RQ R RQ P (RQ)(QR) T E37 RQ T I1 SR P RS T E1 R P(附加) Q T I10 S T I11 SQ P Q T I10 QQ T I9 PQ，(QR)R，(PS) S (S) P(附加) (PS) P PS T E13 SP T E1 P T I11 PQ P Q T I10 (QR)R P QR T I1 RQ T E1 R T I2 Q T I11 QQ T I9 A(BC)，D(BC) (AD) AD P(附加) A T I1 D T I2 A(BC) P BC T I10 BC T E36 D(BC) P BC T I10 (BC) T E14 (BC)(BC) T I9P209 习题11.111.1.1 解： 原式(P(1)Q(1)(P(2)Q(2) TTT 原式(TQ(-2)(TQ(3)(TQ(3)(TQ(3)F (TTFF)FF 原式 (P(1)Q(1)T (P(1)Q(1) FT T11.1.2 解： (x)(y)($z)S(x,y,z) (x)(y)(M(x,y,0)E(x,0)E(y,0) (y)(E(y,1)(x)M(x,y,x) (x)(M(2,x,6)E(x,3) (x)(y)(G(y,0)E(y,0)M(x,x,y) (x)(y)(z)(G(y,x)G(0,z)($u)($v)(M(x,z,u)M(y,z,v)G(u,v) ($x)(y)(z)($u)($v)(M(x,y,u)M(x,z,v)G(u,v) (x)(y)(E(x,y)G(y,x)11.1.3 解： 原式 (R(a)R(b)R(c)(S(a)S(b)S(c) 原式 (P(a)Q(a)(P(b)Q(b)(P(c)Q(c)11.1.4 解： 设 P(x)：x是质数；Q(x)：x是偶数；E(x,y)：x=y。 ($x)(P(x)Q(x)($y)(E(x,y)P(y)Q(y) 设 P(x)：x是奇数。 Q(x)：x是偶数。 ($x)(P(x)Q(x) 设 P(x)：x是卡车； Q(x)：x是一列火车； K(x,y)：x快于y 。 (x)(Q(x)($y)(P(y)K(x,y) 设 P(x)：x是卡车； Q(x)：x是一列火车； K(x,y)：x快于y 。 ($x)(P(x)(y)(Q(y)K(y,x)($y)(Q(y)(x)(P(x)K(y,x) 设 P(x)：x是人；Q(x)：x将淋湿；M：明天下雨。 M($x)(P(x)Q(x) 设 个体域：人类； A(x)：x步行；B(x)：x骑马；C(x)：x乘车； D(x)；x口渴；E(x)：x喝泉水。 (x)(A(x)B(x)C(x)(D(x)E(x) (x)(A(x)B(x)C(x)D(x)E(x)11.1.5 解：($a)($b)(P(a)P(b)($c)(F(a,c)M(c,b)P211 习题11.211.2.1 解： (x)(P(x)Q(x)(x)P(x)Q(x) 第一个(x)的辖域为 P(x)Q(x)，其中x为约束变元； 第二个(x)的辖域为 P(x)，其中x为约束变元；Q(x)中的x为自由变元。 (x)(P(x)($x)Q(x)(x)P(x)Q(x) 第一个(x)的辖域为 P(x)($x)Q(x)，其中x为约束变元； ($x)的辖