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

作业答案：数理逻辑部分

P14：习题一

1、下列句子中，哪些是命题？在是命题的句子中，哪些是简单命题？哪些是真命题？哪些命题的真值现在还不知道？ （3）5是无理数。 答：简单命题，真命题。 （9）吸烟请到吸烟室去！ 答：不是命题。

（12）8是偶数的充分必要条件是8能被3整除。 答：复合命题，假命题。

14、讲下列命题符号化。 （6）王强与刘威都学过法语。

答：p:王强学过法语；q:刘威学过法语。

符号化为：p?q

（10）除非天下大雨，他就乘班车上班。 答：p:天下大雨；q:他乘班车上班。

符号化为：p?q

（13）“2或4是素数，这是不对的”是不对的。 答：p:2是素数；q:4是素数。

15、设p:2+3=5.

q:大熊猫产在中国。 r:太阳从西方升起。 符号化为：?(?(p?q))

求下列复合命题的真值。 （2）(r?(p?q))??p

（4）(p?q??r)?((?p??q)?r) 解答： p真值为1；q真值为1；r真值为0.

（2）p?q真值为1；r?(p?q)真值为1；?p真值为0；

所以(r?(p?q))??p真值为0.

（4）p?q??r真值为1，?p??q真值为0，(?p??q)?r真值为1；

所以(p?q??r)?((?p??q)?r)真值为1.

19、用真值表判断下列公式的类型。 （4）(p?q)?(?q??p)

p q ?p ?q 0 0 1 1 0 1 0 1 1 1 0 0 1 0 1 0 p?q ?q??p (p?q)?(?q??p) 1 1 0 1 1 1 0 1 1 1 1 1 所以为重言式。

（7）(p?q)?(r?s)

p q r s 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 p?q r?s (p?q)?(r?s) 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 0 1 1 0 1 0 0 1 所以为可满足式。

P36:习题二

3、用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出其成真赋值。

（1）?(p?q?q) 解答：

?(p?q?q)??(?(p?q)?q)??((?p??q)?q)

??(?p??q?q)??1?0所以为永假式。

（2）(p?(p?q))?(p?r) 解答：

(p?(p?q))?(p?r)?(?p?(p?q))?(?p?r)?(?p?p?q)?(?p?r) ?1?(?p?r)?1所以因为永真式。

（3）(p?q)?(p?r) 解答：

(p?q)?(p?r) ??(p?q)?(p?r)

?(?p??q)?(p?r)为可满足式。 真值表为

p q r p?q 0 0 0 0 1 1 1 1

p?r 0 0 0 0 0 0 0 1 (p?q)?(p?r)

1 0 0 0 0 0 0 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 4、用等值演算法证明下面的等值式。 （2）((p?q)?(p?r))?(p?(q?r)) 解答：

((p?q)?(p?r))?(?p?q)?(?p?r)??p?(q?r)?p?(q?r)

（4）(p??q)?(?p?q)?(p?q)??(p?q) 解答：

(p??q)?(?p?q)?(p??p)?(p?q)?(?q??p)?(?q?q)?(p?q)?(?q??p)?(p?q)??(q?p)

5、求下列公式的主析取范式，并求它们的成真赋值。 （1）(?p?q)?(?q?p) 解答：

(?p?q)?(?q?p)?(p?q)?(?q?p)??(p?q)?(?q?p)?(?p??q)?(?q?p)?(?p??q)??q?p(析取范式）?(?p??q)?((?p?p)??q)?(p?(?q?q))?(?p??q)?((?p??q)?(p??q))?((p??q)?(p?q))?(?p??q)?(p??q))?(p?q)?m0?m2?m3所以成真赋值为00，10，11 （3）(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)?(?p??r)?p?q?r(析取范式)

?(?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??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)?m0?m1?m2?m3?m4?m5?m6?m7所以为永真式，成真赋值为000，001，010，011，100，101，110，111

6、求下列公式的主合取范式，并求它们的成假赋值。 （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??q)?(?p?q)?(?p??q)?M0?M1?M2?M3为永假式，成假赋值为00，01，10，11

（3）(p?(p?q))?r 解答：

(p?(p?q))?r?(?p?(p?q))?r

?(?p?p?q)?r?1永真式，无成假赋值

7、求下列公式的主析取范式，再用主析取范式求主合取范式。 （1）(p?q)?r 解

答

：

(p?q)?r(已经是析取范式)?(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)?m1?m?m?m?m?M0?M2?M4

8、求下列公式的主合取范式，再用主合取范式求主析取范式。 （2）(p?q)?r 解答：

3(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)?M0?M6?m1?m2?m3?m4?m5?m713、已知公式A含3个命题变项p,q,r，并且它的成假赋值为010，011，110，111，求A的主析取范式和主合取范式。 解答：成真赋值为000,001,100,101 所以主析取范式为m0?m1?m4?m5 而主合取范式为M2?M3?M6?M7 15、用主析取范式判断下列公式是否等值。 （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)?m0?m1?m2

?(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位同学预言：

甲说：王小红为班长，李强为生活委员； 乙说：丁金生为班长，王小红为生活委员。 丙说：李强为班长，王小红为学习委员。

班委会分工名单公布后发现，甲乙丙三人都恰好猜对了一半。问王小红、李强、丁金生各任何职？（用等值演算求解） 解答：命题符号化：

p:王小红为班长；q:李强为生活委员；r:丁金生为班长；s:王小红为生活委员；

u:李强为班长；v:王小红为学习委员。

设A1:p??q；A2:?p?q；B1:r??s；B2:?r?s；C1:u??v；C2:?u?v； 由题意可知：

p?r?0;p?s?0;p?u?0;p?v?0;q?s?0;q?u?0;r?u?0;s?v?0所以A1?B1?0;A1?B2?0;A1?C1?0;A1?C2?0;A2?B2?0;A2?C1?0;

B1?C1?0,B2?C2?0

所以

(A1?A2)?(B1?B2)?(C1?C2)?(A1?B1?C1)?(A1?B1?C2)?(A1?B2?C1)?(A1?B2?C2)?(A2?B1?C1)?(A2?B1?C2)?(A2?B2?C1)?(A2?B2?C2) ?0?0?0?0?0?(A2?B1?C2)?0?0?A2?B1?C2所以选举结果为：李强为生活委员；丁金生为班长；王小红为学习委员。

30、某公司要从赵、钱、孙、李、周5名新毕业的大学生中选派一些人出国学习。选派必须满足条件：

（1）若赵去，钱也去； （2）李、周两人中必有一人去； （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)。 将所有条件进行合取，然后求其主析取范式

(p?q)?(s?t)?((q??r)?(?q?r))?((r?s)?(?r??s))?(t?(p?q))

?(?p??q?r?s??t)?(p?q??r??s?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

推理的形式结构的另外一种描述：

(p??r)?(q?r)?q??p

证明：（1）真值表法：

p q r ?p ?r 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 1 1 1 1 0 0 0 0 1 0 1 0 1 0 1 0 p??r 1 1 1 1 1 0 1 0 q?r 1 1 0 1 1 1 0 1 (p??r)?(q?r)?q 0 0 0 1 0 0 0 0 (p??r)?(q?r)?q??p 1 1 1 1 1 1 1 1 所以(p??r)?(q?r)?q??p为永真式；推理(p??r)?(q?r)?q??p是正确的。

（2）等值演算：

(p??r)?(q?r)?q??p?(?p??r)?(?q?r)?q??p??((?p??r)?(?q?r)?q)??p?((p?r)?(q??r)??q)??p?(p?r)?(q??r)??q??p?((p?r)??p)?((q??r)??q)

?((p??p)?(r??p))?((q??q)?(?r??q))?(1?(r??p))?(1?(?r??q))?(r??p)?(?r??q)?(r??p)?(?r??q)?r??r??p??q?1（3）主析取范式

(p??r)?(q?r)?q??p?(?p??r)?(?q?r)?q??p??((?p??r)?(?q?r)?q)??p?((p?r)?(q??r)??q)??p?(p?r)?(q??r)??q??p?(p?(?q?q)?r)?((?p?p)?q??r)?((?p?p)??q?(?r?r))?(?p?(?q?q)?(?r?r))........?m0?m1?m2?m3?m4?m5?m6?m7

12、填充下面推理证明中没有写出的推理规则。 前提：p?(q?r)，q?(r?s) 结论：(p?q)?s 证明： ①p?q ②p ③q

附加前提引入 ①化简 ①化简 前提引入 ②④假言推理 ③⑤假言推理 前提引入 ③⑦假言推理 ⑥⑧假言推理

④p?(q?r) ⑤q?r ⑥r

⑦q?(r?s) ⑧r?s ⑨s

14、在自然推理系统P中构造下面推理的证明： （2）前提：p?q,?(q?r),r

结论：?p 证明： ①?(q?r) ②?q??r ③r

前提引入 ①置换 前提引入 ②③析取三段论 前提引入 ④⑤拒取式

④?q ⑤p?q ⑥?p

（4）前提：q?p,q?s,s?t,t?r

结论：p?q 证明： ①t?r ②t ③r

前提引入 ①化简 ①化简 前提引入

④s?t

⑤(s?t)?(t?s) ④置换 ⑥t?s ⑦q?s

⑤化简 前提引入

⑧(q?s)?(s?q) ⑦置换

⑨s?q ⑩t?q

11q ○

⑧化简 ⑥⑨假言三段论

②⑩假言推理

前提引入

11○12假言推理 ○12○13合取 ○

12q?p ○13p ○

⑨p?q

15、在自然推理系统P中用附加前提法证明下面推理： （1）前提：p?(q?r),s?p,q

结论：s?r 证明： ①s

附加前提引入 前提引入 ①②假言推理 前提引入 ③④假言推理 前提引入 ⑤⑥假言推理

②s?p ③p

④p?(q?r) ⑤q?r ⑥q ⑦r

16、在自然推理系统P中用归谬法证明下面推理： （1）前提：p?q,p?r,q?s

结论：r?s 证明： ①?(r?s) ②?r??s ③?s ④?r

结论否定引入 ①置换 ②化简 ②化简 前提引入 前提引入 ④⑤拒取式 ③⑥拒取式 ⑦⑧合取 ⑨置换 前提引入

⑤p?r ⑥q?s ⑦?p ⑧?q

⑨?p??q ⑩?(p?q)

11p?q ○

11矛盾。 ⑩○

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?s ③?q ④p

⑤p??q

⑥(p??q)?r ⑦r

P63:习题四

5、在一阶逻辑中讲下列命题符号化。 （3）不存在比所有火车都快的汽车。 （4）凡是汽车就比火车慢是不对的。

解答：F(x):x为火车；G(y)：y为汽车；H(x,y)：y比x快。

（3）?(?y?x(G(y)?F(x)?H(x,y))) （4）??y?x(G(y)?F(x)?H(y,x))

6、将下列命题符号化，个体域为实数集合R，并指出各命题的真值。 （1）对所有的x，都存在y使得x?y?0。 （3）对所有的x，都存在y使得y?x?1。 解答：F(x,y):x?y?0;G(x,y):y?x?1 （1）?x?yF(x,y)，真值为1； （3）?x?yG(x,y)，真值为1；

9、给定解释I如下。 （a）个体域为实数集合R。 （b）特定元素a?0。

（c）函数f(x,y)?x?y,x,y?R

（d）谓词F(x,y):x?y,G(x,y):x?y,x,y?R。 给出下列公式在I下的解释，并指出它们的真值。 （1）?x?y(G(x,y)??F(x,y)) （3）?x?y(G(x,y)??F(f(x,y),a))

解答：（1）对任意的x和y，如果x?y,那么x?y。真值为1；

11、判断下列各式的类型。

（2）?x(F(x)?F(x))??y(G(y)??G(y)) （4）?x?yF(x,y)??y?xF(x,y)

解答：（2）?x(F(x)?F(x))真值为1；?y(G(y)??G(y))真值为0；

所以?x(F(x)?F(x))??y(G(y)??G(y))真值为0，所以为永假式。 （4）?x?yF(x,y)与?y?xF(x,y)真值相同，所以为永真式。

13、给出下列各公式的一个成真解释和一个成假解释。 （1）?x(F(x)?G(x)) （2）?x(F(x)?G(x)?H(x)) （3）?x(F(x)??y(G(y)?H(x,y)) 解答：

（1）成真解释：F(x):x为偶数；G(x):x为奇数

成假解释：F(x):x为偶数；G(x):x为素数

（3）对任意的x和y，如果x?y,那么x?y?0。真值为1；

（2）成真解释：F(x):x能被2整除；G(x):x能被3整除；H(x):x能被5整除。

成假解释：F(x):x为偶数；G(x):x为奇数，H(x):x为素数

（3）成真解释：F(x):x为正数；G(x):x负数；H(x，y):x?y。

成假解释：F(x):x为正数；G(x):x负数；H(x，y):x?y。

本文来源：https://www.bwwdw.com/article/kcha.html