《离散数学习题答案.doc》由会员分享，可在线阅读，更多相关《离散数学习题答案.doc（16页珍藏版）》请在金锄头文库上搜索。
1、离散数学习题答案 习题一及答案：（P14-15） 14、将下列命题符号化： （5）李辛与李末是兄弟 解：设p：李辛与李末是兄弟，则命题符号化的结果是p （6）王强与刘威都学过法语 pq解：设p：王强学过法语；q：刘威学过法语；则命题符号化的结果是 （9）只有天下大雨，他才乘班车上班 qp解：设p：天下大雨；q：他乘班车上班；则命题符号化的结果是 （11）下雪路滑，他迟到了 解：设p：下雪；q：路滑；r：他迟到了；则命题符号化的结果是(pq)r 15、设p：2+3=5. q：大熊猫产在中国. r：太阳从西方升起. 求下列复合命题的真值： (pqr)(pq)r)（4） 解：p=1，q=1，r=0，
2、 (pqr)(110)1， (pq)r)(11)0)(00)1 (pqr)(pq)r)111 19、用真值表判断下列公式的类型： (pp)q（2） 解：列出公式的真值表，如下所示： ppqq (pp)(pp)q 0 0 1 1 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 1 0 0 0 1 由真值表可以看出公式有3个成真赋值，故公式是非重言式的可满足式。 20、求下列公式的成真赋值： （4）(pq)q 解：因为该公式是一个蕴含式，所以首先分析它的成假赋值，成假赋值的条件是： p0(pq)1 q0q0成真赋值有：01，10，11。 所以公式的 习题二及答案：（P38） 5、求下列
3、公式的主析取范式，并求成真赋值： （2） (pq)(qr)解：原式 (pq)qr(pp)qrqr ，此即公式的主析取范式， mm(pqr)(pqr)37所以成真赋值为011，111。 *6、求下列公式的主合取范式，并求成假赋值： （2） (pq)(pr)解：原式，此即公式的主合取范式， M(ppr)(pqr)(pqr)4所以成假赋值为100。 7、求下列公式的主析取范式，再用主析取范式求主合取范式： （1） (pq)r解：原式 pq(rr)(pp)(qq)r) (pqr)(pq)r(pq)r(pq)r(pq)r(pqr (pqr)(pq)r(pq)r(pq)r(pqr ，此即主析取范式。 mm
4、mmm13567主析取范式中没出现的极小项为，所以主合取范式中含有三个极大项，MMmmm02024，故原式的主合取范式。 MMMM4024 9、用真值表法求下面公式的主析取范式： （1） (pq)(pr)解：公式的真值表如下： pppqprq r (pq)(pr) 0 0 0 1 0 0 0 0 0 1 1 0 1 1 0 1 0 1 1 0 1 0 1 1 1 1 1 1 1 0 0 0 1 0 1 1 0 1 0 1 0 1 1 1 0 0 1 0 1 1 1 1 0 1 0 1 由真值表可以看出成真赋值的情况有7种，此7种成真赋值所对应的极小项的析取即为主析取范式，故主析取范式 mmmm
5、mmm1234567 习题三及答案：（P52-54） 11、填充下面推理证明中没有写出的推理规则。 前提： pq,qr,rs,p结论：s 证明： p 前提引入 前提引入 pq q 析取三段论 前提引入 qr r 析取三段论 rs 前提引入 s 假言推理 15、在自然推理系统P中用附加前提法证明下面推理： （2）前提： (pq)(rs),(st)u 结论： pu证明：用附加前提证明法。 p 附加前提引入 附加 pq 前提引入 (pq)(rs)rs 假言推理 s 化简 附加 st 前提引入 (st)u u 假言推理 故推理正确。 16、在自然推理系统P中用归谬法证明下面推理： rs（1）前提：，
6、pqrq 结论： p证明：用归谬法 p 结论的否定引入 前提引入 pq 假言推理 q 前提引入 rq 析取三段论 rrs 前提引入 r 化简 合取 rr由于，所以推理正确。 rr017、在自然推理系统P中构造下面推理的证明： 只要A曾到过受害者房间并且11点以前没离开，A就是谋杀嫌犯。A曾到过受害者房间。如果A在11点以前离开，看门人会看见他。看门人没有看见他。所以，A是谋杀嫌犯。 解：设p：A到过受害者房间，q：A在11点以前离开，r：A是谋杀嫌犯，s：看门人看见过A。 s则前提：， pqs(pq)r 结论： r证明： 前提引入 qss 前提引入 拒取式 q 前提引入 p 合取引入 pq 前
7、提引入 (pq)r 假言推理 r 习题四及答案：（P65-67） 5、在一阶逻辑中将下列命题符号化： （2）有的火车比有的汽车快。 解：设F(x)：x是火车，G(y)：y是汽车，H(x,y)：x比y快；则命题符号化的结果是： $x$y(F(x)G(y)H(x,y) （3）不存在比所有火车都快的汽车。 解：方法一： 设F(x)：x是汽车，G(y)：y是火车，H(x,y)：x比y快；则命题符号化的结果是： $x(F(x)y(G(y)H(x,y)x(F(x)$y(G(y)H(x,y)或 方法二： 设F(x)：x是火车，G(y)：y是汽车，H(x,y)：x比y快；则命题符号化的结果是： $x(G(x)
8、y(F(y)H(x,y)$xy(G(x)(F(y)H(x,y)或 9、给定解释I如下： (a) 个体域为实数集合R。 -a=0 (b) 特定元素。-f(x,y)=x-y,x,yR (c) 函数。-F(x,y):x=y,G(x,y):xy,x,yR (d) 谓词。 给出以下公式在I下的解释，并指出它们的真值： xy(F(f(x,y),a)G(x,y)（2） xy(x-y=0xy)解：解释是：，含义是：对于任意的实数x，y，若x-y=0则xy。 该公式在I解释下的真值为假。14、证明下面公式既不是永真式也不是矛盾式： x(F(x)$y(G(y)H(x,y)（1） I解：取解释如下：个体域为全总个体
9、域， F(x)H(x,y)G(y)：x是兔子，：y是乌龟，：x比y跑得快，则该公式在解释I下真值是1； IIH(x,y)取解释如下：x比y跑得慢，其它同上，则该公式在解释下真值是0； 故公式（1）既不是永真式也不是矛盾式。 此题答案不唯一，只要证明公式既不是永真式也不是矛盾式的每个解释合理即可。 习题五及答案：（P79-81） 5、给定解释I如下： (a) 个体域D=3,4 -f(x):f(3)=4,f(4)=3 (b) -F(x,y):F(3,3)=F(4,4)=0,F(3,4)=F(4,3)=1 (c) 试求下列公式在I下的真值： x$yF(x,y) (1) 解：方法一：先消去存在量词 x
10、$yF(x,y)x(F(x,3)F(x,4) (F(3,3)F(3,4)F)(4F,3) (01)(10) 1 15、在自然推理系统中，构造下面推理的证明： Nx（3）前提：， x(F(x)G(x)$xG(x) 结论： $xF(x)证明： 前提引入 $xG(x) 置换 xG(x) UI规则 G(c) 前提引入 x(F(x)G(x) UI规则 F(c)G(c) 析取三段论 F(c) EG规则 $xF(x)*22、在自然推理系统中，构造下面推理的证明： Nx（2）凡大学生都是勤奋的。王晓山不勤奋。所以王晓山不是大学生。 解：设F(x)：x为大学生，G(x)：x是勤奋的，c：王晓山 则前提：， x(
11、F(x)G(x)G(c) 结论： F(c)证明： 前提引入 x(F(x)G(x) UI规则 F(c)G(c) 前提引入 G(c) 拒取式 F(c)25、在自然推理系统中，构造下面推理的证明： Nx每个科学工作者都是刻苦钻研的，每个刻苦钻研而又聪明的人在他的事业中都将获得成功。王大海是科学工作者，并且是聪明的。所以，王大海在他的事业中将获得成功。（个体域为人类集合） 解：设F(x)：x是科学工作者，G(x)：x是刻苦钻研的，H(x)：x是聪明的，I(x)：x在他的事业中获得成功，c：王大海 则前提：， x(F(x)G(x)x(G(x)H(x)I(x)F(c)H(c) 结论： I(c)证明： 前提
12、引入 F(c)H(c) 化简 F(c) 化简 H(c) 前提引入 x(F(x)G(x) UI规则 F(c)G(c) 假言推理 G(c) 合取引入 G(c)H(c) 前提引入 x(G(x)H(x)I(x) UI规则 G(c)H(c)I(c) 假言推理 I(c)习题六及答案（P99-100） 28、化简下述集合公式： (A-B)-C)(A-B)C)(AB)-C)(AB)C)（3） (A-B)-C)(A-B)C)(AB)-C)(AB)C)解： =(A-B)(AB) =A 30、设A,B,C代表任意集合，试判断下面命题的真假。如果为真，给出证明；如果为假，给出反例。 (AB)-A=B（6） (AB)-A=B-AB-A=BBA=，如果，则解：该命题为假，否则B-A=BB-AB，故为假。 (AB)-A=3BA=1,2,B=1,3,举反例如下：则 。AB=ACB=C（8） AB=AC一定成立，解：该命题为假，举反例如下：如果B，C都是A的子集，则B=1C=21
