1、离散数学习题答案习题一1. 判断下列句子是否为命题？若是命题说明是真命题还是假命题。（1）3 是正数吗？（2）x1=0。（3）请穿上外衣。（4）210。（5）任一个实数的平方都是正实数。（6）不存在最大素数。（7）明天我去看电影。（8）9512。（9）实践出真知。（10）如果我掌握了英语、法语，那么学习其他欧洲语言就容易多了。解：（1） 、 （2） 、 （3）不是命题。（4） 、 （8）是假命题。（5） 、 （6） 、 （9） 、 （10）是真命题。（7）是命题，只是现在无法确定真值。2. 设 P 表示命题“天下雪 ”，Q 表示命题“我将去书店” ，R 表示命题“我有时间” ，以符号形式写出下
2、列命题。（1）如果天不下雪并且我有时间，那么我将去书店。（2）我将去书店，仅当我有时间。（3）天不下雪。（4）天下雪，我将不去书店。解：（1） （PR）Q。（2）QR。（3）P。（4）PQ。3. 将下列命题符号化。（1）王皓球打得好，歌也唱得好。（2）我一边看书，一边听音乐。（3）老张和老李都是球迷。（4）只要努力学习，成绩会好的。（5）只有休息好，才能工作好。（6）如果 a 和 b 是偶数，那么 a+b 也是偶数。（7）我们不能既游泳又跑步。（8）我反悔，仅当太阳从西边出来。（9）如果f(x)在点x 0处可导，则f (x)在点x 0处可微。反之亦然。（10）如果张老师和李老师都不讲这门课，那
3、么王老师就讲这门课。（11）四边形 ABCD 是平行四边形，当且仅当 ABCD 的对边平行。（12）或者你没有给我写信，或者信在途中丢失了。解：（1）P：王皓球打得好，Q：王皓歌唱得好。原命题可符号化：PQ。（2）P：我看书，Q：我听音乐。原命题可符号化：PQ。（3）P：老张是球迷，Q：老李是球迷。原命题可符号化：PQ。（4）P：努力学习，Q：成绩会好。原命题可符号化：PQ。（5）P：休息好，Q：工作好。原命题可符号化：QP。（6）P：a 是偶数，Q：b 是偶数，R ：a+ b 是偶数。原命题可符号化：（ PQ）R 。（7）P：我们游泳，Q：我们跑步。原命题可符号化：（PQ） 。（8）P：我反
4、悔，Q：太阳从西边出来。原命题可符号化：PQ。（9）P：f( x)在点 x0处可导， Q：f(x)在点x 0处可微。原命题可符号化：P Q。（10）P：张老师讲这门课，Q：李老师讲这门课，R ：王老师讲这门课。原命题可符号化：（PQ）R。（11）P：四边形 ABCD 是平行四边形，Q：四边形 ABCD 的对边平行。原命题可符号化：P Q。（12）P：你给我写信，Q：信在途中丢失了。原命题可符号化：P （PQ） 。4. 判断下列公式哪些是合式公式，哪些不是合式公式。（1）(QR S) （2）(P (RS)（3）(PQ) ( QP)（4）(RSF )（5）(P(QR)(PQ) ( PR )解：（1
5、） 、 （2） 、 （5）是合式公式， （3） 、 （4）不是合式公式。5. 否定下列命题： （1） 桂林处处山清水秀。（2） 每一个自然数都是偶数。解：（1）桂林并非处处山清水秀。（2）并不是每一个自然数都是偶数。或：有些自然数不是偶数。6. 给出下述每一个命题的逆命题、否命题和逆否命题。（1） 如果天下雨，我将不去。（2） 仅当你去我才不去。（3） 如果=b 24ac0，则方程ax 2+bx+c=0无实数解。（4） 如果我不获得奖学金，我就不能完成学业。解：（1）逆命题：如果我不去，那么天下雨。否命题：如果天不下雨，我就去。逆否命题：如果我去，那么天不下雨。（2）逆命题：如果你去，我将不去
6、。否命题：如果我去，你将不去。逆否命题：如果你不去，我就去。（3）逆命题：如果方程 ax2+bx+c=0 无实数解，则 =b24ac0。否命题：如果 =b24ac0，则方程 ax2+bx+c=0 有实数解。逆否命题：如果方程 ax2+bx+c=0 有实数解，则 =b24ac0。（4）逆命题：如果我不能完成学业，那么我没有获得奖学金。否命题：如果我获得奖学金，我就能完成学业。逆否命题：如果我就能完成学业，那么我就获得奖学金。7. 求下列各式的真值表。（1）P( RS) （2）(PR) (PQ)（3）(PQ) (QP)（4）(PQ) R（5）(P( QR)(PQ) ( PR)解：（1）P( RS)
7、P R S RS P(RS)1 1 1 1 11 1 0 1 11 0 1 1 11 0 0 0 00 1 1 1 10 1 0 1 10 0 1 1 10 0 0 0 1（2）(PR) (PQ)P Q R PR PQ (PR) (PQ)1 1 1 1 1 11 1 0 0 1 11 0 1 1 0 11 0 0 0 0 00 1 1 0 1 10 1 0 0 1 10 0 1 0 1 10 0 0 0 1 1（3）(PQ) (QP)P Q PQ QP (PQ) (QP)1 1 1 1 11 0 1 1 10 1 1 1 10 0 0 0 1（4）(PQ) RP Q R Q PQ (PQ) R
8、1 1 1 0 1 11 1 0 0 1 01 0 1 1 1 11 0 0 1 1 00 1 1 0 0 00 1 0 0 0 00 0 1 1 1 10 0 0 1 1 0（5）(P( QR)(PQ) ( PR)P Q R QR P( QR) P Q PR (P Q) ( PR) 原公式1 1 1 1 1 1 1 1 11 1 0 0 0 1 0 0 11 0 1 1 1 0 1 1 11 0 0 1 1 0 0 1 10 1 1 1 1 1 1 1 10 1 0 0 1 1 1 1 10 0 1 1 1 1 1 1 10 0 0 1 1 1 1 1 18. 用真值表判断下列公式的类型：(
9、1) P QQ(2) (PQ) (RS)(PR)( QS) 解：(1) P QQP Q Q PQ PQQ1 1 0 1 11 0 1 1 00 1 0 0 10 0 1 1 0（1）为可满足式。(2) (PQ) (RS)(PR)( QS)P Q R S PQ RS (PQ) (RS) PR QS (PR)(Q S) 原公式1 1 1 1 1 1 1 1 1 1 11 1 1 0 1 0 1 1 1 1 11 1 0 1 1 1 1 1 1 1 11 1 0 0 1 1 1 1 1 1 11 0 1 1 0 1 1 1 1 1 11 0 1 0 0 0 0 1 0 0 11 0 0 1 0 1
10、1 1 1 1 11 0 0 0 0 1 1 1 0 0 00 1 1 1 1 1 1 1 1 1 10 1 1 0 1 0 0 1 1 1 10 1 0 1 1 1 1 0 1 1 10 1 0 0 1 1 1 0 1 1 10 0 1 1 1 1 1 1 1 1 10 0 1 0 1 0 1 1 0 0 00 0 0 1 1 1 1 0 1 1 10 0 0 0 1 1 1 0 0 1 1（2）为可满足式。9. 证明下列等价式。（1）P( QP ) P(PQ )（2）(P Q) (PQ) (PQ)（3）(P Q) P Q（4）(P Q) (PQ) (PQ)（5）P( QR) (PQ) R（
11、6）(PR) (QR) (PQ) R（7）(P Q)R) (Q(SR) ( Q(SP) R证明：（1）P( QP ) P(QP) P(PQ)P(P Q)（2）(P Q)(PQ) (PQ) (PQ) (PQ) (PQ) (PQ)（3）(P Q) (P Q) PQ（4）(P Q) (PQ) (QP ) (PQ) (QP) (PQ) (PQ)（5）P( QR) P(QR) (PQ) R (PQ) R（6）(PR) (QR) (PR) (QR) (PQ)R(PQ)R (PQ) R（7）(P Q)R) (Q(SR) (PQ ) R) (Q(SR) Q(PS)R(Q(SP) R (Q(SP) R (Q(S
12、P) R10. 使用恒等式证明下列各式，并写出它们对偶的公式。（1）( P Q)(PQ) P（2）(PQ) (PQ)( PQ )(PQ)（3）Q( PQ)P) T证明：（1）( P Q)(PQ) (PQ )( PQ )P(QQ) PTP（2）(PQ) ( PQ)(PQ)P(Q Q)( PQ)PF(PQ) P( P Q)(PP) (PQ ) F(PQ)(PQ ) (P Q)（3）Q( PQ)P) Q( PQ )P) Q(PQ )P( QP P ) ( QP Q) TT T11. 试证明，不是全功能联结词集合。证明：若 是最小联结词组，则 P( P.)对所有命题变元指派 T，则等价式左边为 F，右
13、边为 T，等价式矛盾。若是最小联结词组，则 P P ( P( P.).)对所有命题变元指派 T，则等价式左边为 F，右边为 T，等价式矛盾。12. 证明下列蕴涵式：（1）PQ (PQ) （2）P (Q P) （3）(P(QR) ( PQ) (PR)证明：（1）P Q( PQ)( PQ) (PQ ) (PQ)(PQ)P(QQ)T因为PQ( PQ)为永真式，所以PQ (PQ )。（2）P ( QP) P(QP) Q(PP) T因为P ( QP) 为永真式，所以P (QP )。（3）(P(QR) ( PQ) (PR) (P(QR)(PQ) (PR)(P(QR) (PQ) (PR) (PQR )(PP
14、R)(Q PR)(PQR)( PQR)(P(PQR)( Q(PQR)( R(PQR) ) T因为(P(QR) ( PQ) (PR)为永真式，所以(P(QR) ( PQ ) (PR) 。13. 对下列各公式，试仅用或表示。（1）P（2）PQ（3）PQ（4）PQ解：（1）P(P P) PP（2）PQ(PQ)(P Q)（3）PQ(P Q) (PQ ) (PP)(QQ)（4）PQPQ (P P)Q (PP)(PP)(QQ)14. 将下列公式化成与之等值且仅含， 中联结词的公式。（1）(PQ) R（2）P (QR )P解：（1）(PQ) R(PQ )R (PR )(Q R)(PR)( QR)(RP)(R
15、Q)( RP)( RQ )（2）P (QR)P(P (QR)P)(QR) P)P )(P(Q R)P)( (QR)P) P) T(QR)P)P )(QR) P) P(QR)P(Q R) P( QR)15. 如果 A(P，Q，R) 由 R(Q(RP) )给出，求它的对偶 A*(P，Q，R) ，并求出与 A 及 A*等价且仅包含联接词“” ， “”及“”的公式。解：A*(P，Q，R )：R (Q( RP)R(Q(R P)( R(Q (RP)RQ ( RP)R (Q(R P)R Q (RP)16. 把 PQ 表示为只含有“ ”的等价公式。解：PQ (PQ)(PP)(QQ) (PP)(QQ)(PP)(
16、QQ)17. 证明：（1）(P Q)PQ（2）(P Q)PQ证明：（1）(P Q)(P Q) ( PQ )(PQ )PQ（2）(P Q)(P Q) ( PQ )(PQ )PQ18. 求公式 P(P Q)的析取范式和合取范式。解：P( PQ ) P(P Q) 合取范式 (P P)(PQ) 析取范式19. 求下列公式的主析取范式和主合取范式。（1）(P Q) (QP) （2）(P (P Q) R（3）(P QR )( P ( QR)解：（1）真值表法P Q PQ Q P (PQ)( QP )1 1 1 1 11 0 1 1 10 1 1 0 00 0 0 1 1主析取范式为：(PQ) (P Q)(
17、 PQ )主合取范式为：PQ公式化归法(PQ)( QP) (PQ )(Q P) ( P Q)(Q P)(P QP)(QQP) PQ 主合取范式(P Q)(PQ) (PQ ) 主析取范式（2）真值表法(P ( PQ) RP Q R PQ P (PQ) (P (P Q) R1 1 1 1 1 11 1 0 1 1 11 0 1 1 1 11 0 0 1 1 10 1 1 1 1 10 1 0 1 1 10 0 1 0 1 10 0 0 0 1 1原式为永真式，其主析取范式为所有小项的析取，即：m000m 001m 010m 011m 100m 101m 110m 111不能表示为主合取范式。公式化
18、归法(P ( PQ) R(P(P Q )RTR T（3）真值表法(P QR )(P ( QR)P Q R QR P QR QR P (Q R) 原公式1 1 1 1 1 0 1 11 1 0 0 0 0 1 01 0 1 0 0 0 1 01 0 0 0 0 1 1 00 1 1 1 1 0 0 00 1 0 0 1 0 0 00 0 1 0 1 0 0 00 0 0 0 1 1 1 1主析取范式为：(PQR )(PQ R) m111m 000m7m 0主合取范式为：M 1M 2M 3M 4M 5M 6 M001M 010M 011M 100M 101M 110(PQ R )(P Q R)(P
19、Q R)(PQR )( PQR)(PQR )20. 求下列公式的主析取范式和主合取范式，并指出该公式的类型。（1）(P Q)(P Q)（2）Q(P Q)（3）P( P(Q(QR)（4）(P(QR) ( P(QR )（5）P( P(Q P)（6）(QP )(PQ)解：（1）P Q P Q P Q (PQ)(P Q)1 1 0 0 11 0 1 1 10 1 1 1 10 0 1 0 0主析取范式为：(PQ) (P Q)( PQ )主合取范式为：PQ公式为可满足式。（2）P Q P Q Q( PQ)1 1 1 11 0 1 00 1 0 00 0 1 0主析取范式为：PQ主合取范式为：(PQ) (
20、 PQ )( PQ )公式为可满足式。（3）P( P(Q(QR) P(P(Q (QR) PQR 主合取范式 M000M0 m1m 2m 3 m4m 5m 6m 7 主析取范式公式为可满足式。（4）(P(QR) ( P(QR )(P( QR)( P(QR) (PQ )(PR) (PQ)( PR) (PQR )(PQR) (PQR) (PQR ) (PQR) (PQR ) M100M 101M 111M 010M 011M 001M4M 5M 7M 2M 3M 1 主合取范式 m0 m6 m000m 110 主析取范式公式为可满足式。（5）P( P(Q P)P (P(Q P)( PP )(P( Q
21、P) T主析取范式为：m 0m 1m 2m 3公式为永真式。（6）(QP )(PQ) (Q P)(PQ )(QPQ)( PPQ) F主合取范式为：M 0M 1M 2M 3公式为永假式。21. 用将合式公式化为范式的方法证明下列各题中两式是等价的。（1）(PQ)(PR) ，P (QR )（2）(PQ)(PQ)，( P Q )(Q P)（3）PQ(P Q)，P Q (PQ)（4）P( P(PQ)，PQ (PQ )证明：（1）(PQ)(PR) (P Q )( PR) P(QR) P(Q R) (PQ)(PR)（2）(PQ)(PQ) (PQ )(PQ )(PQ)(P Q)P( QQ) P(PQ)( Q
22、P) (PQ)(Q P)P( QQ) P（3）PQ(P Q) (PQP)(PQQ ) FPQ( PQ) (P QP)(PQQ ) F（4）P( P(PQ) P (P(PQ ) T( PQ) TPQ( PQ) (P QP)(PQQ ) T22. 用推理规则证明以下各式。（1）(P Q)，QR，R P（2）A( BC )，(DE) A，D E BC（3）BC，(B C)( DE )DE（4）PQ，(QR )R，( PS) S证明：（1）(P Q)，QR，R P证明：(1) R P(2) QR P(3) Q T(1)(2) I(4) (P Q) P(5) PQ T(4) E(6) P T(3)(5)
23、 I（2）A( BC )，(DE) A，D E BC证明：(1) DE P(2) (DE) A P(3) A T(1)(2) I(4) A( BC ) P(5) BC T(3)(4) I（3）BC，(B C)( DE )DE证明：(1) BC P(2) B C T(1) I(3) (B C)( DE) P (4) DE T(2)(3) I（4）PQ，(QR )R，( PS) S证明：(1) (QR) R P(2) QR T(1) I(3) R T(1) I(4) Q T(2)(3) I(5) (PS) P(6) S P T(5) E(7) PQ P(8) SQ T(6) (7) I(9) QS
24、 T(8) E(10) S T(4) (8) I23. 仅用规则 P 和 T，推证以下公式。（1）AB ，CB A C（2）A( BC )，(CD)E，F(D E) A(BF)（3）AB CD，DE F， AF（4）A( BC )，BD， (EF) D ，B(AE)BE（5）(AB) (CD)，(BE)(D F)，( EF )，AC A证明：（1）AB ，CB A C证明：(1) AB P(2) AB T(1) E(3) CB P(4) BC T(3) E(5) AC T(2) (4) I（2）A( BC )，(CD)E，F(D E) A(BF)证明：(1) A( BC ) P(2) ABC
25、T(1) E(3) (AB)C T(2) E(4) (CD)E P(5) C(DE) T(4) E(6) (DE) C T(5) E(7) F(DE ) P(8) FC T(6) (7) I(9) CF T(8) E(10) (AB)F T(3) (9) I(11) ABF T(10) E(12) A( BF) T(11) E（3）AB CD，DE F AF证明：(1) ABCD P(2) ABD T(1) I(3) DEF P(4) DF T(3) I(5) ABF T(2)(4) I(6) AF T(5) I（4）A( BC )，BD， (EF) D ，B(AE)BE证明：(1) BD P(2) BD T(1)E
