离散数学冯栾石陈编习题答案.doc

1、习题一1、 利用逻辑联结词把下列命题翻译成符号逻辑形式（1） 他既是本片的编剧，又是导演 - P Q（2） 银行利率一降低，股价随之上扬 - P Q（3） 尽管银行利率降低，股价却没有上扬 - P Q（4） 占据空间的、有质量而且不断变化的对象称为物质 - M (SP T)（5） 他今天不是乘火车去北京，就是随旅行团去了九寨沟 - P Q（6） 小张身体单薄，但是极少生病，并且头脑好使 - P Q R（7） 不识庐山真面目，只缘身在此山中 - P Q（解释：因为身在此山中，所以不识庐山真面目）（8） 两个三角形相似，当且仅当他们的对应角相等或者对应边成比例- S (E T)（9） 如果一个整数

2、能被 6 整除，那么它就能被 2 和 3 整除。如果一个整数能被 3 整除，那么它的各位数字之和也能被 3 整除解：设 P 一个整数能被 6 整除 Q 一个整数能被 2 整除 R 一个整数能被 3 整除S 一个整数各位数字之和能被 3 整除翻译为：（P （Q R） ） （R S）2、 判别下面各语句是否命题，如果是命题，说出它的真值（1）BASIC 语言是最完美的程序设计语言 - Y，T/F（2）这件事大概是小王干的 - N（3）x 2 = 64 - N（4）可导的实函数都是连续函数 - Y，T/F（5）我们要发扬连续作战的作风，再接再厉，争取更大的胜利 - N（6）客观规律是不以人们意志为转

3、移的 - Y，T（7）到 2020 年，中国的国民生产总值将赶上和超过美国 - Y，N/A（8）凡事都有例外 - Y，F3、 构造下列公式的真值表，并由此判别哪些公式是永真式、矛盾式或可满足式（1） （P （P Q） ） Q解：P Q P Q P （P Q）（P （P Q） ） Q可满足式0 0 0 0 10 1 1 1 11 0 0 1 01 1 0 1 1（2）（4）略4、 利用真值表方法验证下列各式为永真式（1）（8）略5、 证明下列各等价式（1）（P Q）（P Q） ）（P Q） P证明：左式 （P Q）（P Q） ）（P Q ） P （P Q）（P Q） T （ P Q） P 右式（

4、2） （P Q）（R Q）（P R）Q证明：左式 （PQ）（RQ） （P R）Q （P R）Q （P R）Q 右式（3）P（Q R） （P Q）（P R）证明：左式 PQ R PQP R （PQ）（P R） （P Q）（P R） 右式（4） （P Q）（R Q）（R P） （P Q） （R Q）（R P）证明：左式 (（PR） Q）（R P） (（PR）R) ) (（PR）P) ) （QR）（QP） （P Q）（R Q）（R P） 右式6、 如果 P Q QR,能否断定 P R ？ 如果 P Q QR，能否断定 P R？如果P R，能否断定 P R？解： （1）如果 P Q QR，不能判断 P

5、 R，因为如果 Q = P R, 那么 P Q PP R QR，但 P 可以不等价于 R.（2）如果 P Q QR，不能判断 P R，因为如果 Q = P R, 那么 P Q PP R QR，但 P 可以不等价于 R.（3）如果P R，那么有 P R，因为P R，则P R 为永真式，及有 P R 为永真式，所以 P R.7、 检查和是否满足结合率解： 用真值表方式检查P Q R PQ QR (PQ) R P (Q R)0 0 0 1 1 1 10 0 1 1 1 0 10 1 0 1 1 1 10 1 1 1 0 0 11 0 0 1 1 1 01 0 1 1 1 0 01 1 0 0 1 1

6、 01 1 1 0 0 1 1由上表可知，不满住结合率P Q R PQ QR (PQ) R P (Q R)0 0 0 1 1 0 00 0 1 1 0 0 10 1 0 0 0 1 10 1 1 0 0 0 11 0 0 0 1 1 01 0 1 0 0 0 01 1 0 0 0 1 01 1 1 0 0 0 0由上表可知，不满住结合率8、 把下列各式用等价表示出来（1）(PQ) P解：原式 (PQ) (PQ) (PP) (PQ) (PQ) (PQ) (PQ) (PP) (PP)（2）P（P Q）解：原式 PPQ Q (QQ) (QQ)（3） （P（Q R） ） P解：原式 （ PQ R） P

7、 P（Q P）（R P） (PP) （(QQ) (PP)）（R(PP)） (PP) （(QQ) (PP)）（(QQ) (PP)） ）（R(PP)）（R(PP)） ）设： (PP) = N（(QQ) (PP)）（(QQ) (PP)） ）= L（R(PP)） （R (PP)） ） = M则上式 (NN) (LL) (NN) (LL) (MM)（4） PQ（R P）解：原式 PQ（RP） (PP) (QQ) （(PP) (RR) ） (（(PP) (QQ)）（(PP) (QQ) ）) （(PP) (RR)）设： (（(PP) (QQ)）（(PP) (QQ)）) = N（(PP) (RR)） = M则

8、上式 (NM) (NM)9、 证明： 是最小功能完备集合证明: 因为, 是最小功能完备集合,所以,如果 能表示出,则其是功能完备集合。由于 P Q (P) Q ,所以 是功能完备集合。因为 不能相互表示，所以 是最小功能完备集合；同理可证：非，条件非也能将或表示出来：P Q (P ! Q)10、 证明: ， 不是功能完备集证明： PQ 没有办法通过，的公式表达出来，因为P Q PQ PP ( PP) PQ0 0 0 0 1 00 1 1 0 1 11 0 1 0 1 11 1 1 0 1 0所以，通过，不能表达出真值为三个 1 或 1 个 1 的情况，因此，不能表达出 PQ，所以不是功能完备集

9、。11、 用和把公式 PQR 和（P Q）R 表示出来解：（PQ）R (（PQ）（PQ）) R (（PQ）（PQ）) R) (（PQ）（PQ）) R) (（PQ）（PQ） ）R) （PQ）（PQ） ）R） （(（PQ）（PQ） ）R)）（PQ）（PQ） ）R） ） ）（PQ）R （ (（PQ）（ PQ） ）R)12、 分别利用真值表法和等价变换法求下列公式的主合取范式及主析取范式:(1) P(RQ) S)解：真值表法P Q R S RQ (RQ) S P(RQ) S)0 0 0 0 0 1 10 0 0 1 0 1 10 0 1 0 0 1 10 0 1 1 0 1 10 1 0 0 0 1

10、10 1 0 1 0 1 10 1 1 0 1 0 10 1 1 1 1 1 11 0 0 0 0 1 11 0 0 1 0 1 11 0 1 0 0 1 11 0 1 1 0 1 11 1 0 0 0 1 11 1 0 1 0 1 11 1 1 0 1 0 01 1 1 1 1 1 1所以：主合取范式为 = PQRS = M14主析取范式为 = m1m2m3m4m5m6m7m 8m9m10m11m12m13m14m16等价变换法（略）(2)（PQ）（PQ）解：真值表法P Q PQ PQ （PQ）（PQ）0 0 1 0 00 1 1 1 11 0 1 1 11 1 0 0 1所以：主合取范式为

11、 = PQ = M0主析取范式为 = (PQ)(PQ)(PQ) = m1m2m3等价变换法（略）(3) P(R(QP)解：真值表法P Q R QP R(QP) P(R(QP)0 0 0 1 0 10 0 1 1 1 10 1 0 0 0 10 1 1 0 0 11 0 0 1 0 01 0 1 1 1 11 1 0 1 0 01 1 1 1 1 1所以：主合取范式为 = (PQR) (PQR) = M4M6主析取范式为 = (PQR)(PQR)(PQR)(PQR)(PQR)(PQR) = m0m1m2m3m5m7等价变换法（略）(4) (P(QR) (P(QR)解：真值表法所以：主合取范式为

12、= (PQR) ( PQR) ( PQR) (PQR) ( PQR) ( PQR) = M1M2M3M4M5M6主析取范式为 = (PQR)(PQR) = m0m7等价变换法（略）13、 用转化范式的方法判别下面各组公式是否等价（1） （PQ）（PQ） 和（PQ）（QP）解： （PQ）（PQ） （PQ）（PQ） （PQ）（PQ）-合取范式（PQ）（QP） （PQ）（QP） P(QQ) P （PQ）（PQ） -合取范式两式的合取范式相同，所以等价（2） （PQ）（PR） 和 P（QR）解： （PQ）（PR） （PQ）（PR ） - 合取范式P（QR） P（QR） （PQ）（PR）-合取范式P Q

13、 R QR QR P(QR) P(QR)(P(QR) (P(QR)0 0 0 0 1 1 1 10 0 1 0 0 1 0 00 1 0 0 0 1 0 00 1 1 1 0 1 0 01 0 0 0 1 0 1 01 0 1 0 0 0 1 01 1 0 0 0 0 1 01 1 1 1 0 1 1 1两式的合取范式相同，所以等价14、 从 A,B,C,D 4 个人中派 2 人出差，要求满足下列条件：如果 A 去，则必须在 C 或D 中选一人同去；B 和 C 不能同时去；C 和 D 不能同时去。用构造范式的方法决定选派方案。解：由题设 A：A 去，B：B 去，C：C 去，D：D 去则满足条件

14、的选派应满足如下范式：（A（CD） ）（BC）（CD）构造和以上范式等价的主析取范式（A（CD） ）（BC）（CD）（AB C D ）（ABCD）（ABCD）（ABCD）（ABCD）（ABCD）（ABCD）（ABCD）共有八个极小项，但根据题意，需派两人出差，所以，只有其中三项满足要求：（ABCD） ， （ABCD） ， （ABCD）即有三种方案：A 和 C 去或者 A 和 D 去或者 B 和 D 去。15、 证明下列蕴含试：（1）PQ=P (PQ)证明：PQ P Q T(P Q) (PP) (P Q) P (PQ) P (PQ)所以，这是个等价式，因此也是个蕴含式（2）(PQ) Q= (PQ

15、)证明：(PQ) Q (PQ) Q (PQ) Q (PQ) (QQ) (PQ) T (PQ)所以，这是个等价式，因此也是个蕴含式（3）PPR=S证明：PPR F = S (F 可蕴含任何命题公式)（4）P=QRR证明：P=T QRR16、 证明蕴含关系的性质 1、性质 2 和 3证明：性质 1 A = A因为在任意的解释下，公式 A 的真值显然和自己相同，当然在为真时也相同，所以蕴含成立。性质 2 如果 A=B 且 B=A, 则 A B因为 A=B 且 B=A 及 (AB) (BA) 为永真式，则 A B 为永真式。所以 A B。性质 3 如果 A=B 且 A 永真式，则 B 必为永真式因为

16、(AB)为永真式，且 A 为永真式，那么只有 B 为永真式才能满足(AB)为永真式成立。所以结论为真。17、 证明定理 1.12证明：A=B,当且仅当B=A证明： A=B AB 为永真式 BA 为永真式 B=A A=B,当且仅当B=A18、 一个有钱人生前留下了一笔珍宝，藏在一个隐秘处。在他留下的遗嘱中指出寻找珍宝的线索如下：（1） 如果藏宝的房子靠近池塘，那么珍宝不会藏在东厢房。（2） 如果房子的前院栽有大柏树，那么珍宝就藏在东厢房。（3） 藏宝房子靠近池塘。（4） 要么前院栽有大柏树，要么珍宝埋在花园正中地下。（5） 如果后院栽有香樟树，珍宝藏在附近。请利用蕴含关系找出藏宝处。解：根据给定

17、的条件有下述命题：P：珍宝藏在东厢房Q：藏宝的房子靠近池塘R：房子的前院栽有大柏树S：珍宝藏在花园正中地下T：后院栽有香樟树M：珍宝藏在附近根据题意，得出：（QP）（RP）Q（RS）（TM） ？（QP）（RP）Q（RS）（TM） P（RP）（RS）（TM） R（RS）（TM） S（TM）S 即珍宝藏在花园正中地下19、 判断下列蕴含关系式是否成立：（1）Q(PQ) P解：当左端公式解释为 1 时，Q 必须为 1；Q 为 1，P 比为 1；所以，右端公式也为 1；因此，蕴含关系成立（2）(P(QR) (Q(PR) PR解：左端公式 Q (PR)，当解释为 1 是，分两种情况，PR 与 Q 同为

18、1，那么PR 也为 1；PR 与 Q 同为 0，如果此时 P=1,R = 0, 则 PR 为 0；因此，此蕴含式不成立（3）P (PQ) Q解：左端公式解释为 1 时，P 必为 0；当 P 为 0 时，则 Q 可为 0，也可为 1；因此，此蕴含式不成立（4）(PQ) (PQ) (PR) R解：当左端公式按 P = 0, Q = 1, R = 0 解释时，为 1，但右端不为 1；因此，此蕴含式不成立（5）(PQ) R)(PQ)(QP) R解：当左端公式按 P =1, Q =1, R = 0 解释时，真值为 1，但右端为 0；因此，此蕴含式不成立20、 演绎证明下面各蕴含式：（1）PQ,RQ PR

19、证明：运用 cp 法，将结论条件式的前件作为前提，证明步骤如下1 P p(附加前提)2 PQ p3 Q T 1,2 I4 RQ p5 R T 3,4 I6 PR CP 1,5（2）(PQ) (RS),(SE) B PB证明：运用 cp 法，将结论条件式的前件作为前提，证明步骤如下1 P p（附加前提）2 (PQ) (RS) p3 RS T 1,2 I4 (SE) B p5 B T 3,4 I6 PB CP1,5（3）P(QR),(RS) E, B(SE) P(QB)证明：运用 cp 法，将结论条件式的前件作为前提，先将结论进行等价变换为（PQ）B,因此 PQ 可作为附加前提，证明步骤如下1 P

20、Q p(附加前提)2 P(QR) p3 （PQ）R T 2 E4 R T 1,3 I5 (RS) E p6 E T 4,6 I7 B(SE) p8 B T 6,7 I9 （PQ）B cp 1,8（4）(RQ) (RS),(QE) (SB), (EB),(PR) P证明：运用反证方法，将结论的非纳入前提，证明步骤如下1 P p(附加前提)2 PR p3 R T 1,2 I4 (RQ) (RS) p5 QS T 3,4 I6 (QE) (SB) p7 EB T 5,6 I8 (EB) p9 F(矛盾式) T 7,8 E（5）P(QR),Q(RS) P(QS)证明：运用 cp 法，将结论条件式的前件

21、作为前提，证明步骤如下1 P p(附加前提)2 P(QR) p3 QR T 1,2 I4 Q(RS) p5 R(QS) T 4 E6 QS T 3,5 I7 P(QS) CP 1,621、 把下列句子演绎成逻辑形式，并给出证明（1） 如果资方拒绝增加工资，那么罢工不会结束；除非罢工超过一年，并且资方撤换了经理；现在资方拒绝了增加工资，罢工刚开始。判断罢工能否停止。解：根据题意，有如下命题P: 资方拒绝增加工资Q: 罢工结束R: 罢工超过一年S: 资方撤换了经理所以，前提条件符号化为PQ；QRS；PR因此，推理过程如下：1 PR p2 PQ p3 Q T 1,2 I所以，罢工不会结束（2） 某公

22、司发生了一起盗窃案，经仔细侦察，掌握了如下一些事实： 被盗现场没有留下任何痕迹 失盗时，小花或则小英正在卡拉 ok 厅 如果失窃时小胖正在附近，他就会习惯性地破门而入偷走东西后扬长而去 如果失盗时小花正在卡拉 ok 厅唱歌，那么金刚是最大的嫌疑者 如果失盗时小胖不在附近，那么他的女友小英会和他一起外出旅游 如果失盗时小英正在卡拉 ok 厅唱歌，那么瘦子是最大的嫌疑者根据以上事实，请通过演绎推理找出偷窃者解：根据给定的条件有下述命题：P：现场无任何痕迹Q：失窃时，小花在 OK 厅R：失窃时，小英在 OK 厅S：失窃时，小胖在附近T：金刚是偷窃者M：瘦子是偷窃者则根据案情有如下命题公式：P，Q R

23、，S P，Q T， S R，R M P P SP P S TI SR P R TI QR P Q TI QT P T TI即 金刚是偷窃者22、 设 A1,A2,An 是一组命题公式，如果存在一个解释使 A1A2An 取值真，就称这组公式是相容的，否则称为不相容的。不相容意味着 A1A2An 蕴含一个矛盾式，现在判别下列各命题组是否相容（1）P(QR),S(QR),PS解：根据题意（P(QR)）（S(QR)）（PS） (QR)(QR) RR F所以，这组命题公式不相容（2）PQ, RS, Q, S解：根据题意(PQ) (RS) Q S PR所以,当 P=1，Q=0，R=0，S=0 时，合取式解

24、释为 1，因此这组命题公式相容（3）PQ,QR, RS, PS, S解：根据题意（PQ）（QR） （RS） （PS） S （PQ）（QR）R P（PQ）QP F所以，这组命题公式不相容（4）PQ,PR,QR,P解：根据题意（PQ）（PR）（QR）P QR（QR） RR F所以，这组命题公式不相容23、 利用消解法证明下列各蕴含式：（1）RQ,RS,SQ,PQ P证明： RQ R QSQ S QPQ PQ因此子句集合 = RQ，SQ，RS，PQ，P 消解过程如下：1 RQ p2 SQ p3 RS p4 PQ p5 P p6 Q 由4，5归结7 R 由1，6归结8 S 由2，6归结9 S 由3，7归结10 FLASE 由8，9归结导出空子句（2）(PQ) (RS),(QP) R,R PQ证明： (PQ) (RS) PQRS(QP) R QPR(PQ) （ PQ ）（Q P） ） （PQ）（QP） (P Q) (QP) (PQ) (PQ)因此子句集合 = PQRS，QPR，PQ，PQ，R 消解过程如下：1 PQRS p2 QPR p3 PQ p4 PQ p