离散数学及其应用数理逻辑部分课后习题答案

1、 | HYPERLINK / 百度首页 HYPERLINK /v2/?login 登录 HYPERLINK /cashier/browse/vipcashier?dqStatCode=topnav_joinvip&cashier_code=topnav_joinvip VIP意见反馈 HYPERLINK /apps?fr=1011 下载客户端4/13/2019离散数学及其应用数理逻辑部分课后习题答案- 百度文库 HYPERLINK /?fr=nav 首页 HYPERLINK javascript:void(0); 分类 HYPERLINK javascript:void(0); 精品内容 HY

2、PERLINK /wenkuverify?from=1 申请认证 HYPERLINK javascript:void(0); 机构合作 HYPERLINK javascript:void(0); 频道专区 HYPERLINK /xtopic/wkback 百度智慧课堂 HYPERLINK /user/browse/vip/ 百度教育VIP HYPERLINK /?fr=crumbs 百度文库 HYPERLINK /?fr=crumbs HYPERLINK /edu/index 教育专区 HYPERLINK /edu/index HYPERLINK /list/10 高等教育 HYPERLINK

3、 /list/10 HYPERLINK /list/108 理学P141、下列句子中，哪些是命题？在是命题的句子中，哪些是简单命题？哪些是真命题？哪些命题的真值现在还不知道？（3） 5 是无理数。答：简单命题，真命题。（9）吸烟请到吸烟室去！答：不是命题。（12）8 是偶数的充分必要条件是 8 能被3 整除。答：复合命题，假命题。14、讲下列命题符号化。（6）王强与刘威都学过法语。答： :王强学过法语； : 刘威学过法语。pq符号化为： p q（10）除非天下大雨，他就乘班车上班。答： p :天下大雨；q : 他乘班车上班。符号化为： p q（13）“2 或4 是素数，这是不对的”是不对的。答

4、： p :2 是素数；q : 4 是素数。符号化为：( p q)15、设 p :2+3=5.: 大熊猫产在中国。qr :太阳从西方升起。求下列复合命题的真值。（2）(r (p q) p（4）( ) ( ) )p qrpqr解答： p 真值为1；q 真值为1；r 真值为0.（2） p q 真值为1；r (p q) 真值为1；p 真值为0；( ( ) p q所以 r（4） p q r 真值为1，p q 真值为0， p1.p 真值为0.( ) r 真值为1；q( ) ( ) )r 真值为所以 p qrpq/view/ae163ad2b1717fd5360cba1aa8114431b80d8e0d.h

5、tml1/14 4/13/2019离散数学及其应用数理逻辑部分课后习题答案- 百度文库19、用真值表判断下列公式的类型。（4）(p q) (q p)1101qq p (p q) (q p)pqp qp0 0 10 1 11 0 01 1 0101011011111所以为重言式。（7）(p q) (r s)qr s (p q) (r s)pqr sp1 1 0 11 1 1 01 1 1 1111001001所以为可满足式。/view/ae163ad2b1717fd5360cba1aa8114431b80d8e0d.html2/14 4/13/2019离散数学及其应用数理逻辑部分课后习题答案-

6、百度文库P36:3、用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出其成真赋值。（1）(p q q)解答：( )p qq ( ) )p qq ( ) )pqq ( )q qp 1 0所以为永假式。( ( ) ( )（2） pp qpr解答：( ( ) ( )p qppr ( ( ) ( )pp q p r ( ) ( )p p qp r 1 ( )p r 1所以因为永真式。（3）(p q) (p r)解答：( ) ( )p qp q p r ( ) ( )p r ( ) ( )pqp r为可满足式。真值表为pqr( ) ( )p q p r1 0 01 0 11 1 0

7、1 1 1111100010001/view/ae163ad2b1717fd5360cba1aa8114431b80d8e0d.html3/14 4/13/2019离散数学及其应用数理逻辑部分课后习题答案- 百度文库4、用等值演算法证明下面的等值式。（2）(p q) (p r) (p (q r)解答：( ) ( )pqpr ( ) ( )p qp r ( )pq r ( )q rp（4）( ) ( ) ( ) ( )pqp q p qp q解答：( ) ( )p qpq ( ) ( ) ( ) ( )ppp q q p q q ( ) ( )p qqp ( ) ( )p qqp5、求下列公式的

8、主析取范式，并求它们的成真赋值。（1）(p q) (q p)解答：( ) ( )pqqp ( ) ( )p qqp ( ) ( )p qqp ( ) ( )pqqp ( ) (析取范式）pqqp ( ) ( ) ) ( ( )pqppqpq q ( ) ( ) ( ) ( ) ( )pqpqpqpqp q ( ) ( ) ( )p qpqpqm0 m2 m3所以成真赋值为 00，10，11（3）(p (q r) (p q r)解答：( ( ) ( )pq rp q r ( ( ) ( )pq r p q r ( ( ) ( )q r p q rp q rp ( ( ) ( )pqr ( ) (

9、 ) (析取范式)pqprp q r/view/ae163ad2b1717fd5360cba1aa8114431b80d8e0d.html4/14 4/13/2019离散数学及其应用数理逻辑部分课后习题答案- 百度文库 (p q (r r) (p (q q) r) ( p (q q) (r r) (p p) q (r r) (p p) (q q) r) (p q r) (p q r) (p q r) (p q r) ( p q r) ( p q r) ( p q r) ( p q r) (p q r) (p q r) ( p q r) ( p q r) (p q r) (p q r) ( p

10、q r) ( p q r) (p q r) (p q r) (p q r) (p q r)( p q r) ( p q r) ( p q r) ( p q r) m m m m m m m m01234567所以为永真式，成真赋值为 000，001，010，011，100，101，110，1116、求下列公式的主合取范式，并求它们的成假赋值。（1）(q p) p解答:(q p) p (q p) p (q p) p p p q(合取范式) ( p (q q) (p (q q) ( p p) q) ( p q) ( p q) (p q) (p q) ( p q) (p q) ( p q) ( p

11、q) (p q) (p q) M M M M3012为永假式，成假赋值为 00，01，10，11（3）(p (p q) r解答：( p ( p q) r (p ( p q) r (p p q) r 1永真式，无成假赋值/view/ae163ad2b1717fd5360cba1aa8114431b80d8e0d.html5/14 4/13/2019离散数学及其应用数理逻辑部分课后习题答案- 百度文库7、求下列公式的主析取范式，再用主析取范式求主合取范式。（1）(p q) r解答：( p q) r(已经是析取范式) ( p q (r r) (p p) (q q) r) ( p q r) ( p q

12、 r) (p q r) (p q r) ( p q r) ( p q r) (p q r) (p q r) ( p q r) ( p q r) ( p q r) m m m m m13 M M M4028、求下列公式的主合取范式，再用主合取范式求主析取范式。（2）(p q) r解答：( p q) r ( p q) (q p) r (p q) (q p) r (p q) (q p) r ( p q) (q p) r ( p q r) ( p p r) (q q r) (q p r) ( p q r) (q p r) ( p q r) (p q r) M M06 m m m m m m712345

13、13、已知公式 A 含3 个命题变项 p,q,r ，并且它的成假赋值为 010，011，110，111，求 A的主析取范式和主合取范式。解答：成真赋值为 000,001,100,101所以主析取范式为m m m m5014而主合取范式为M M M M723615、用主析取范式判断下列公式是否等值。（2）( p q)和( p q)解答：( p q) p q (p (q q) (p p) q) (p q) (p q) (p q) ( p q) (p q) (p q) ( p q) m m m012/view/ae163ad2b1717fd5360cba1aa8114431b80d8e0d.html

14、6/14 4/13/2019离散数学及其应用数理逻辑部分课后习题答案- 百度文库( p q) p q m0所以两式并不等值。18、将下列公式化成与之等值且仅含有,中联结词的公式（3）(p (q r) p解答：( p (q r) p (p (q r) p p p (q r) 129、在某班班委成员的选举中，已知王小红、李强、丁金生 3 位同学被选进了班委会。该班的的甲、乙、丙 3 位同学预言：甲说：王小红为班长，李强为生活委员；乙说：丁金生为班长，王小红为生活委员。丙说：李强为班长，王小红为学习委员。班委会分工名单公布后发现，甲乙丙三人都恰好猜对了一半。问王小红、李强、丁金生各任何职？（用等值演

15、算求解）解答：命题符号化：p :王小红为班长；q : 李强为生活委员；r :丁金生为班长；s:王小红为生活委员；u:李强为班长；v:王小红为学习委员。设A : p q ；A :p q ；B : r s ；B :r s ；C :u v；C :u v ；121212由题意可知：p r 0; p s 0; p u 0; p v 0;q s 0;q u 0;r u 0;s v 0所以A B 0; A B 0; A C 0; A C 0; A B 0; A C 0;111211122221B C 0,B C 01122所以(A A ) (B B ) (C C )121212 (A B C ) (A B

16、C ) (A B C ) (A B C ) 111112121122(A B C ) (A B C ) (A B C ) (A B C )211212221222 0 0 0 0 0 (A B C ) 0 0212 A B C221所以选举结果为：李强为生活委员；丁金生为班长；王小红为学习委员。/view/ae163ad2b1717fd5360cba1aa8114431b80d8e0d.html7/14 4/13/2019离散数学及其应用数理逻辑部分课后习题答案- 百度文库30、某公司要从赵、钱、孙、李、周 5 名新毕业的大学生中选派一些人出国学习。选派必须满足条件：（1）若赵去，钱也去；（2

17、）李、周两人中必有一人去；（3）钱、孙两人中去且仅去一人；（4）孙、李两人同去或同不去；（5）若周去，则赵、钱也同去。用等值演算法分析该公司该如何选派他们出国。解答：命题符号化：p :赵去；q : 钱去；r:孙去； :李去； :周去。s t所满足的条件即为（1）若赵去，钱也去： p q ；（2）李、周两人中必有一人去： s t ；（3）钱、孙两人中去且仅去一人：(q r) (q r)；（4）孙、李两人同去或同不去：(r s) (r s)；（5）若周去，则赵、钱也同去：t (p q) 。将所有条件进行合取，然后求其主析取范式( ) ( ) ( ) ( ) ( ) ( ) ( ( )pqs tqr

18、q rr srstp q ( ) ( )pq r s t p qrs t（过程省略）所以最终方案有两套：（1）赵钱周不去，孙李去；（2）赵钱周去，孙李不去。P50:9、用3 种方法（真值表、等值演算、主析取范式）证明下面推理是正确的。若a 是奇数，则 a 不能被2 整除。若a 是偶数，则 a 能被2 整除。因此，如果 a 是偶数，则a 不是奇数。解答：命题符号化： p :a 为奇数；q : a 为偶数；r :a 能被2 整除推理的形式结构：前提： p r ；q r ；q结论：q推理的形式结构的另外一种描述：( ) ( ) prqrqp/view/ae163ad2b1717fd5360cba1a

19、a8114431b80d8e0d.html8/14 4/13/2019离散数学及其应用数理逻辑部分课后习题答案- 百度文库证明：（1）真值表法： ( ) ( ) ( ) ( ) pqrprprqr1prrqprqrqp0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 110101010111111111110000111101010111010010000( ) ( ) ( ) ( ) p 是正所以 prqrqp 为永真式；推理 prqrq确的。（2）等值演算：( ) ( ) prqrqp ( ) ( ) q rprqp ( ) ( ) ) q rprqp ( )

20、( ) ) p rqrqp ( ) ( ) p rqrqp ( ) ) ( ) )p rprqprq ( ) ( ) ( ) ( )ppqqrq (1 ( ) (1 ( )rprq ( ) ( )rprq ( ) ( )rprq rrpq 1（3）主析取范式( ) ( ) prqrqp ( ) ( ) q rprqp ( ) ( ) ) q rprqp ( ) ( ) ) p rqrqp ( ) ( ) p rqrqp ( ( ) ) ( ) ) ( ) ( ) ( ( ) ( )pq qrppqrppqr rpq qr r. m m6 m70m1m2m3m4m5/view/ae163ad2b

21、1717fd5360cba1aa8114431b80d8e0d.html9/14 4/13/2019离散数学及其应用数理逻辑部分课后习题答案- 百度文库12、填充下面推理证明中没有写出的推理规则。前提： p (q r) ，q (r s)结论：(p q) s证明： p q p附加前提引入化简q化简 p (q r)q r前提引入假言推理r假言推理前提引入q (r s)r ss假言推理假言推理14、在自然推理系统 P 中构造下面推理的证明：（2）前提： p q,(q r),r结论：p证明：(q r)前提引入q rr置换前提引入q析取三段论前提引入 p qp拒取式（4）前提：q p,q s,s t,t

22、 r结论： p q证明：t rt前提引入化简r化简s t前提引入( ) ( ) stts 置换t s化简q s前提引入( ) ( )q 置换 qss/view/ae163ad2b1717fd5360cba1aa8114431b80d8e0d.html10/14 4/13/2019离散数学及其应用数理逻辑部分课后习题答案- 百度文库s qt q化简假言三段论假言推理前提引入q11q p12 p13假言推理11 12 p q合取12 1315、在自然推理系统 P 中用附加前提法证明下面推理：（1）前提： p (q r),s p,q结论：s r证明：s s p p附加前提引入前提引入假言推理 p (

23、q r)q r前提引入假言推理q前提引入r 假言推理16、在自然推理系统 P 中用归谬法证明下面推理：（1）前提： p q, p r,q s结论：r s证明：(r s)结论否定引入r ss置换化简r化简 p rq sp前提引入前提引入拒取式拒取式合取置换qp q( p q) p q 11前提引入矛盾。11/view/ae163ad2b1717fd5360cba1aa8114431b80d8e0d.html11/14 4/13/2019离散数学及其应用数理逻辑部分课后习题答案- 百度文库17：在自然推理系统 P 中构造下面推理的证明：只要A 曾到过受害者房间并且 11 点以前没有离开，A 就是谋杀嫌疑犯。A 曾到过受害者房间。如果A 在11 点以前离开，看门人会看见过他。看门人没有看见他。所以，A 是谋杀嫌疑犯。解答：（1） 命题符号化： p :A 曾到过受害者房间；q : A 在11 点以前离开；r : A 就是谋杀嫌疑犯；s:看门人会看见过 A；（2） 推理的形式结构：前提：(p q) r; p;q s;s结论：r（3） 证明s前提引入前提引入拒取式前提引入合取前提引入q sq p p q(p q) rr 假言推理。P63:5、在一阶逻辑中讲下列命题符号化。（3）