离散数学屈婉玲版课后答案.docx

1、离散数学屈婉玲版课后答案3-习题一1.1.略1.2.略1.3.略1.4.略1.5.略1.6.略1.7.略1.8.略1.9.略1.10. 略略1.11.1.12. 将下列 命题符号化，并给岀各命题的 真值:(1)2+2 = 4当且仅当 3+3 = 6.(2)2+2 = 4的充要条件是3+3飞.(3)2+2 4与3+3 = 6互为充要条件.(4)若 2+2 2,则3+3一6,反之亦然.pp,其中,p: 2+2 = 4, q: 3+3 = 6,真值为 1.(2)p：l_q,其中,p: 2+2 = 4, q: 3+3 = 6,真值为 0. * pp,其中,p: 2+2 = 4, q: 3+3 =6,真

2、值为 0. 一p q,其中,p: 2+2 = 4, q: 3+3 = 6,真值为 1. 将下列命题符号化，并给岀各命题的真值： (1)若今天是星期一，则明天是星期二.一 一(2)只有今天是星期一，明天才是星期二.(3 )今天是星期一当且仅当明天是星期二 .(4)若今天是星期一，则明天是星期三.令p:今天是星期一 ；q:明天是星期二；r:明天是星期三(1)p q 1. qp4 p q 1.(4) pr当p 0时为真;p 1时为假. 将下列命题符号化. (1)刘晓月跑得快，跳得高. (2)老王是山东人或河北人. (3)因为天气冷，所以我穿了羽绒服. (4)王欢与李乐组成一个小组. (5)李辛与李末

3、是兄弟.(6)王强与刘威都学过法语. (7)他一面吃饭，一面听音乐. (8)如果天下大雨，他就乘班车上班. (9)只有天下大雨，他才乘班车上班. (10)除非天下大雨，他才乘班车上班. (11)下雪路滑,他迟到了 .(12)2与4都是素数，这是不对的.(13)或4是素数，这是不对的”是不对的.(1)p q,其中，p:刘晓月跑得快，q:刘晓月跳得高.(2)p q,其中,p:老王是山东人，q:老王是河北人.pq,其中，p:天气冷，q:我穿了羽绒服.(4)p,其中，p:王欢与李乐组成一个小组，是简单命题(5)p,其中，p:李辛与李末是兄弟.(6)p q,其中，p:王强学过法语，q:刘威学过法语.(7

4、)p q,其中，p:他吃饭，q:他听音乐.(8)p q,其中，p:天下大雨，q:他乘班车上班.(9)p q,其中，p:他乘班车上班，q:天下大雨.(10)pp,其中，p:他乘班车上班，q:天下大雨.(11)p-q,其中，p:下雪路滑,q:他迟到了 .(12)(p q)或一pji q,其中，p: 2是素数，q: 4是素数.(13)/ i (p q)或p q,其中,p: 2是素数,q: 4是素数.(1)真值为0.(2)真值为0.(3)真值为0.(4)真值为1.注意：p, q是真命题,r是假命题.1.16.略1.17.略1.18.略1.19.用真值表判断下列公式的类型(1) (pq r)(2)(P_

5、 q厂-q(qr) r(p-q), qJ p)(5)(p r)(pq)(6)(pq) (r) (r)(7)( q) (r s),(4), (6)为重言式.(3)为矛盾式.(2), (5), (7)为可满足式1.20.略1.21.略1.22.略1.23.略1.24.略1.25.略1.26.略1.27.略1.28.略1.29.略1.30.略1.31.将下列一命题符号化，并给岀各命题的真值： (1)若3+= 4,则地球是静止不动的.若3+2 = 4,则地球是运动不止的. (3)若地球上没有树木，则人类不能生存.(4)若地球上没有水，则3是无理数.pp,其中，p: 2+2 = 4, q:地球静止不动真

6、值为0.p-q,其中，p: 2+2 = 4, q:地球运动不止，真值为1.(3):p ：l-q,其中，p:地球上有树木，q:人类能生存，真值为1.:一p q,其中，p:地球上有水，q: 3是无理数，真值为1.习题二2.1.设公式A = p q, B = p.：.q,用真值表验证公式 A和B适合德摩根律 (A B)：_AjB.A =p q B =piq1 0l(A(B)AeB1 1 00 0 11 11因为1 (A B)和：Ai,.B的真值表相同，所以它们等值P q r000001010011100101110111(1) (p qp)w (P q) q)心(pq q) p q：q p 0 0

7、；0.矛盾式.(2)重言式.(p q) (p r) (p q) (p r)，piq p r易见，是可满足式，但不是重言式.成真赋值为：000,001, 101, 111-p 厂q p r1 1 1 0 11 1 1 1 01 0 0 0 01 0 0 0 01 0 10 0 0 0 1 1 10 0 0 0 00 0 0 1 102.4.用等值演算法证明下面等值式(1)P ：(P q) (Pq)(3)J(pq) (P(q) A (PR)(4)(P q) ( P q) (pq) - (p q)(1)(p q) (p：q) p (q q) p 1 p. (pq)(pP) (qp)一(一p q) (

8、-q p)；(p.q) (q.p)(p q) (p -p) (-q q) (p：.q)(p q) (p q)(p ：t) (:p q)(：-p) (p q) (up) d q)(p q) * (p q)2.5.求下列公式的主析取范式，并求成真赋值(1)( Wq)(q(p)(2)Rp冷)田于(3)(P(qD ?s(Pp(r)(1)(pF) q P) ：-(p q) (:q p)z-pjq pp、一q : -q p(吸收律 f (P P)：q P (q q)伽pq科peq ( p可(冲鼻qmio成真赋值为 00,10,11.(2)主析取范式为0,无成真赋值，为矛盾式.(3)m0 m1 m2 m3

9、m4 m5 m6 m7 , 为重言式.(1)：-(q：-p) ；：-p用 Hq i p) - -pq P :- -pq 00 M0 M1 M2 M3这是矛盾式.成假赋值为00, 01, 10, 11.(2)M4 ,成假赋值为100.(3)主合取范式为1,为重言式.2.7.求下列公式的主析取范式，再用主析取范式求合取范式=(1)(p q) r(2)(pP) .gr)(1)mi m3 m5 m6 m Mo M2 M4(2)mo mi m3 mF -M2 M4 M5 M62.8.略2.9.用真值表求下面公式的主析取范式(2)(p-q)(p：_q)p q(p q ) ( p i q )0 0i 0 0

10、 i0 ii i i 0i 00 i i ii ii 0 0 0(2)从真值表可见成真赋值为 01, 10.于是(p q)i(p q) ； mi m2 .(2)(pp)冲 :-e pq) rE-(pq) rTp：hq rp q L r) (p p) (qq) rTpi.：，q r pi.：，q ：Arp q r p Qq rp q rpq r= mioi mioo mm mioi moii mooimi m3 m4 m5 m7=(i, 3, 4, 5, 7).而 q (p r):一 q (ipr) p r C p p) q C r r) - p ( q q) (- r r)(p p) e q

11、q) r e Pqr) (，Prq r) (prq=r) (prq r)C -r) C Pq r) C p qir) ( p q r)(Pq r) ( p q r) (pq r) (p q r)=mo mi m4 m5m m1 m2 m3mi m3 m5 m7 !；“m mi m2 m3 m4 m5 m7(0, 1,2, 3, 4, 5, 7).2.16.用主析取范式判断下列公式是否等值(1)(pq) T 与 q,p”r)(2)*-(P 国)与* (P(q)(i)(pp) r) - mi m3 m4 m5 m7(p r) -mo mi m2 m3 m4 m5 m7 所以(p-q)-r)q -

12、(p-Q(p q) mo mi m2:一 (p q) m0所以 i(p q) :一 (p q)2.18.略2.19.略2.20.将下列公式化成与之等值且仅含 , 中联结词的公式(p q)r.注意到 AB (AB) (BA)和 A B：一(lA：_d B) 1(A：- B)以及 A B：一A“B.(p q) r (p q r) (r p q)(一(P- W) “-(p- q)心-(P q) r) (r 二(p q) 注联结词越少，公式越长.2.21.证明：(1)(p (p), (pq) (q-p).(p- q) 2(p q)用-(q p) ：(q-p). (p-q) w -(p q) w -(q

13、 p) (q p).(1)取 A = p, B = q, C = 1 (重言式),有AC B C,但 A B.取A = p, B = q, C = 0 (矛盾式),有A C B C, 但 A B.好的例子是简单，具体，而又说明问题的一定.2.26.略2.27.某电路中有一个灯泡和三个开关 A,B,C.已知在且仅在下述四种情况下灯亮(1)C的扳键向上，A,B的扳键向下.(2)A的扳键向上，B,C的扳键向下.(3)B,C的扳键向上，A的扳键向下.(4)A,B的扳键向上，C的扳键向下.设F为1表示灯亮，p,q,r分别表示A,B,C的扳键向上.(a)求 F的主析取范式.(b)在联结词完备集1,耳上构造

14、F.(c)在联结词完备集1上构造F.(a)由条件(1)-(4)可知,F的主析取范式为-q r) (pr) ( p q r) (p q.r)m1 m4 m3 m6m1 m3 m4 m6(b)先化简公式F(一P.q r) (p、_q._r) (-p q r) (p q 二一r) 用T (Pr) (Pjr) q (p r) (p)-q q) (pr) (Pjr)：(P r) (p ：:r)(: (:P r) (p ：:r)(已为i, 中公式)(c)F：(pr) (p,：_r)l;& P r) (pr):(P r厂(p r)(P r) 1_(：_p r)(rp) ( r) (已为中公式)2.28.个排

15、队线路，输入为A,B,C,其输出分别为F a,F b,F c.本线路中，在同一时间内只能有一个信号通过 ，若同时有两个和两个以上信号申请输出时 ，则按A,B,C的顺序输出.写出F a,F b,F c在联结词完备集一，中的表达式. 根据题目中的要求，先写岀F a,F b,F c的真值表（自己写）由真值表可先求岀他们的主析取范式，然后化成：_, 中的公式F a -m4 m5 m6 m7F b - m2 m3F c -mi2p r q r (已为：, 中公式)2.29.略2.30.略3.1.略3.2.略3.3.略3.4.略3.5.略3.6.判断下面推理是否正确.先将简单命题符号化，再写出前提，结论，

16、推理的形式结构(以蕴涵式的形式给 出)和判断过程(至少给出两种判断方法一)： (1)若今天是星期一=,则明天是星期三；今天是星期一所以明天是星期三= (2)若今天是星期一，则明天是星期二；明天是星期二.所以今天是星期一.(3)若今天是星期一，则明天是星期三；明天不是星期三=.所以今天不是星期一. (4)若今天是星期一，则明天是星期二；今天不是星期一一.所以明天不是星期二. (5)若今天是星期一=,则明天是星期二或星期三. (6)今天是星期一当且仅当明天是星期三；今天不是星期一 .所以明天不是星期三.设p:今天是星期一，q:明天是星期二，r:明天是星期三.(1)推理的形式结构为(P r) p r

17、此形式结构为重言式，即(p)p：$r所以推理正确.(2)推理的形式结构为(p-q) qp此形式结构不是重言式，故推理不正确.(3)推理形式结构为(pi) r -p此形式结构为重言式，即(pr) ：Ar ：； p故推理正确.(4)推理形式结构为0q) p- q此形式结构不是重言式，故推理不正确.(5)推理形式结构为叭 *p (q r)它不是重言式，故推理不正确.(6)推理形式结构为(p吃r) ：:p； r此形式结构为重言式，即(p： r) ._p：; r故推理正确.推理是否正确，可用多种方法证明.证明的方法有真值表法，等式演算法.证明推理正确还可用构造证明法 下面用构造证明法证明(6)推理正确.

18、前提:p逹r, ip前提引入置换化简律前提引入拒取式结论:r证明:p：$r2(pr) (rp)3r p41 p5r所以，推理正确.3.7.略3.8.略3.9.用三种方法(真值表法，等值演算法，主析取范式法)证明下面推理是正确的：不是奇数.若a是奇数，则a不能被2整除.若a是偶数，则a能被2整除.因此，如果a是偶数，则a令p: a是奇数；q: a能被2整除；r: a是偶数.前提：p q，r q.结论：r p.形式结构：(p :q) (r q) (r :-p).3.10.略3.11.略3.12.略3.13.略3.14.在自然推理系统P中构造下面推理的证明(1)前提：P,q】)，p，q 结论:r(s

19、(2)前提：pp, J (q“ r 结论:*-p(3)前提：p飞结论:p,p可)(4)前提：qp，q還s, s, tsr结论：p可(5)前提：p】,s, p3q证明:P (q r)pq十qrr s前提引入假言推理前提引入假言推理附加律(2)证明:前提引入-(q r)置换q -r前提引入析取三段论Tpp p前提引入拒取式(3)前提引入置换证明：p q:-p q (pq) (pp)-p (p q) p(p q)也可以用附加前提证明法，更简单些.(4)证明:s3t(s t) (t s)t s化简假言推理 前提引入7置换8化简假言推理t r5t6sqWs(s q) (q s)s qo12p13o假言推

20、理11o合取12(5)证明:pr前提引入q s前提引入p q前提引入说明：证明中，附加提前t,前提qs没用上.这仍是正确的推理3.15.在自然推理系统P中用附加前提法证明下面各推理: (1)前提:P,q), s p, q 结论:s r (2)前提：(p q) (r s), (st) u 结论:p - u(1)证明:ssppp (q r) qr6q7r(2)证明:pq(p q) (r s)r s附加前提引入1附加前提引入假言推理4化简st(st) u 附加前提引入假言推理3.16.在自然推理系统P中用归谬法证明下面推理(1)前提：pJq, *-r(q, -s/, I. 、 A结论：p前提:p q

21、, r, q s结论：r s(1)证明:Pp qqr qrr t-s 7rr r 结论否定引入 前提引入假言推理前提引入析取三段论前提引入化简合取8为矛盾式，由归谬法可知，推理正确.(2)证明:一 (r s)pqp rq srsis) (r s)为矛盾式，所以推理正确3.仃.P53 17.在自然推理系统 P中构造下面推理的证明： 只要A曾到过受害者房间并且一11点以前没用离开，A就犯了谋杀罪.A曾到过受害者房间一.如果A在 11点以前离开，看门人会看到他=看门人没有看到他=.所以=A犯了谋杀罪.令p: A曾到过受害者房间；q: A在11点以前离开了 ； r: A就犯了谋杀罪；s:看门人看到 A

22、.前提：r, p, q JS s, -s.结论：r.结论：r.前提：心夕q计，p, q ?ss, .s;证明：1-s前提引入2q s前提引入3：_q拒取前提引入p5p_.：.q合取6p_：q r前提引入7r假言推理3.佃.在自然推理系统P中构造下面推理的证明.(1)如果今天是星期六，我们就要到颐和园或圆明园去玩 .如果颐和园游人太多，我们就不去颐和园玩.今天是星期六.颐和园游人太多.所以我们去圆明园玩.(2)如果小王是理科学生，他的数学成绩一定很好.如果小王不是文科生，他必是理科生.小王的数学成 绩不好.所以小王是文科学生.(3)明天是晴天，或是雨天；若明天是晴天，我就去看电影；若我看电影，我

23、就不看书.所以，如果我看书, 则明天是雨天.(1)令p:今天是星期六；q:我们要到颐和园玩；r:我们要到圆明园玩；s:颐和园游人太多 前提：p(q r), s -q, p, s.结论：r.前提引入前提引入析取三段论(1)的证明树假言推理(2)令p:小王是理科生，q:小王是文科生，r:小王的数学成绩很好前提：p计,iq讳,r结论：q证明：:_r前提引入 ip拒取式-q p前提引入拒取式q令p:明天是晴天，q:明天是雨天，r:我看电影，s:我看书.前提：p q，卩十,r二s结论:s q证明：附加前提引入sL- s前提引入-r拒取式4前提引入ip拒取式p q前提引入析取三段论 q习题四4.1.将下面

24、命题用0元谓词符号化： (1)小王学过英语和法语= (2)除非李建是东北人，否则他一定怕冷.令F(x): x学过英语；F(x): x学过法语；a:小王.符号化为F(a) F(b).或进一步细分，令L(x, y): x学过y; a:小王；bi :英语；b2 :法语.则符号化为L(a, bi ) L(a, b2 ).令F(x): x是东北人；G(x): x怕冷；a:李建.符号化为:_F(a)G(a)或 iG(a厂F(a).或进一步细分，令H(x, y): x是y地方人；G(x): x怕冷；a:小王；b:东北.则符号化为:_H(a, bG(a)或：一G(a厂 H(a, b).(b)中，x(G(x)

25、F(x),其中，G(x): x为有理数，F(x)同(a)中，真值为0.(a)中xF(x),其中，F(x): x能被2整除，真值为1.(b)中，k(G(x) F(x),其中，F(x)同(a)中，G(x): x为有理数，真值为1.4.3.在一阶逻辑中将下面命题符号化 ，并分别讨论个体域限制为(a),(b)时命题的真值(1)对于任意的x,均有x2“2=(x+ 2 )(2 ).存在x,使得x+5=9.其中(a)个体域为自然数集合，(b)个体域为实数集合.(1)(a)中,x(x2“2=(x+ 2 )(2 ),真值为 1.(b)中，x(F(x) (x2=(x+ 2 )(/2 ),其中,F(x): x为实数

26、,真值为 1. (a)中,x(x+5=9),真值为 1.(b)中，x(F(x) (x+5=9),其中，F(x): x为实数，真值为 1.4.4.在一阶逻辑中将下列命题符号化 ：(1)没有不能表示成分数的有理数.(2)在北京卖菜的人不全是外地人.(3)乌鸦都是黑色的.(4)有的人天天锻炼身体 没指定个体域，因而使用全总个体域.(1)：，x(F(x) ：_G(x)或 x(F(x) G(x),其中，F(x): x为有理数，G(x):贿总表示成分数:x(F(x) G(x)或x(F(x) .：G(x),其中，F(x): x在北京卖菜，G(x): x是外地人.(3)x(F(x) G(x)，其中，F(x):

27、 x是乌鸦，G(x): x是黑色的.x(F(x) G(x)，其中，F(x): x是人，G(x): x天天锻炼身体.因为没指明个体域，因而使用全总个体域(1)x y(F(x) G(y厂H(x,y),其中，F(x): x是火车，G(y): y是轮船，H(x,y):x比y快.(2)y(F(x) G(y) H(x,y),其中,F(x): x是火车,G(y): y是汽车,H(x,y):x比y快.=(F(x) y(G(y厂 H(x,y)或 x(F(x) y(G(y) j-H(x,y),其中,F(x): x是汽车,G(y): y是火车,H(x,y):x比y快. x y(F(x) G(y) H(x,y)或xy(F(x) G(y) - H(x,y),其中,F(x): x是汽车,G(y): y是火车,H(x,y):x比y慢.4.