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

作业答案：数理逻辑部分

P14：习题一
1、下列句子中，哪些是命题？在是命题的句子中，哪些是简单命题？哪些是真命题？哪些命题的真值现在还不知道？
（3）是无理数。
答：简单命题，真命题。
（9）吸烟请到吸烟室去！
答：不是命题。
（12）8是偶数的充分必要条件是8能被3整除。
答：复合命题，假命题。

14、讲下列命题符号化。
（6）王强和刘威都学过法语。
答：王强学过法语；刘威学过法语。
符号化为：
（10）除非天下大雨，他就乘班车上班。
答：天下大雨；他乘班车上班。
符号化为：
（13）“2或4是素数，这是不对的”是不对的。
答：2是素数；4是素数。
符号化为：

15、设2+3=5.
大熊猫产在中国。
太阳从西方升起。
求下列复合命题的真值。
（2）
（4）
解答：真值为1；真值为1；真值为0.
（2）真值为1；真值为1；真值为0；
所以真值为0.
（4）真值为1，真值为0，真值为1；
所以真值为1.

19、用真值表判断下列公式的类型。
（4）

0
0
1
1
1
1
1
0
1
1
0
1
1
1
1
0
0
1
0
0
1
1
1
0
0
1
1
1
所以为重言式。
（7）

0
0
0
0
1
1
1
0
0
0
1
1
0
0
0
0
1
0
1
0
0
0
0
1
1
1
1
1
0
1
0
0
1
1
1
0
1
0
1
1
0
0
0
1
1
0
1
0
0
0
1
1
1
1
1
1
1
0
0
0
0
1
0
1
0
0
1
0
0
1
1
0
1
0
0
0
1
1
0
1
1
0
1
0
1
1
0
0
1
1
1
1
1
0
1
1
0
0
1
1
1
0
1
0
0
1
1
1
1
1
1
1

所以为可满足式。

P36:习题二
3、用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出其成真赋值。
（1）
解答：

所以为永假式。
（2）
解答：

所以因为永真式。

（3）
解答：

为可满足式。
真值表为

0
0
0
0
0
1
0
0
1
1
0
0
0
1
0
1
0
0
0
1
1
1
0
0
1
0
0
1
0
0
1
0
1
1
0
0
1
1
0
1
0
0
1
1
1
1
1
1

4、用等值演算法证明下面的等值式。
（2）
解答：

（4）
解答：

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

所以成真赋值为00，10，11
（3）
解答：

所以为永真式，成真赋值为000，001，010，011，100，101，110，111

6、求下列公式的主合取范式，并求它们的成假赋值。
（1）
解答:

为永假式，成假赋值为00，01，10，11

（3）
解答：

永真式，无成假赋值

7、求下列公式的主析取范式，再用主析取范式求主合取范式。
（1）
解答：
8、求下列公式的主合取范式，再用主合取范式求主析取范式。
（2）
解答：

13、已知公式A含3个命题变项，并且它的成假赋值为010，011，110，111，求A的主析取范式和主合取范式。
解答：成真赋值为000,001,100,101
所以主析取范式为
而主合取范式为
15、用主析取范式判断下列公式是否等值。
（2）和
解答：

所以两式并不等值。
18、将下列公式化成和之等值且仅含有中联结词的公式
（3）
解答：

29、在某班班委成员的选举中，已知王小红、李强、丁金生3位同学被选进了班委会。该班的的甲、乙、丙3位同学预言：
甲说：王小红为班长，李强为生活委员；
乙说：丁金生为班长，王小红为生活委员。
丙说：李强为班长，王小红为学习委员。
班委会分工名单公布后发现，甲乙丙三人都恰好猜对了一半。问王小红、李强、丁金生各任何职？（用等值演算求解）
解答：命题符号化：
王小红为班长；李强为生活委员；丁金生为班长；王小红为生活委员；
李强为班长；王小红为学习委员。
设；；；；；；
由题意可知：
所以

所以

所以选举结果为：李强为生活委员；丁金生为班长；王小红为学习委员。

30、某公司要从赵、钱、孙、李、周5名新毕业的大学生中选派一些人出国学习。选派必须满足条件：
（1）若赵去，钱也去；
（2）李、周两人中必有一人去；
（3）钱、孙两人中去且仅去一人；
（4）孙、李两人同去或同不去；
（5）若周去，则赵、钱也同去。
用等值演算法分析该公司该如何选派他们出国。
解答：命题符号化：
赵去；钱去；孙去；李去；周去。
所满足的条件即为
（1）若赵去，钱也去：；
（2）李、周两人中必有一人去：；
（3）钱、孙两人中去且仅去一人：；
（4）孙、李两人同去或同不去：；
（5）若周去，则赵、钱也同去：。
将所有条件进行合取，然后求其主析取范式

（过程省略）
所以最终方案有两套：
（1）赵钱周不去，孙李去；（2）赵钱周去，孙李不去。

P50:习题三

9、用3种方法（真值表、等值演算、主析取范式）证明下面推理是正确的。
若a是奇数，则a不能被2整除。若a是偶数，则a能被2整除。因此，如果a是偶数，则a不是奇数。
解答：命题符号化：a为奇数；a为偶数；a能被2整除
推理的形式结构：
前提：；；
结论：
推理的形式结构的另外一种描述：

证明：（1）真值表法：

0
0
0
1
1
1
1
0
1
0
0
1
1
0
1
1
0
1
0
1
0
1
1
1
0
0
1
0
1
1
1
0
1
1
1
1
1
0
0
0
1
1
1
0
1
1
0
1
0
0
0
1
0
1
1
1
0
0
1
1
0
0
1
1
1
1
0
0
0
1
0
1
所以为永真式；推理是正确的。
（2）等值演算：

（3）主析取范式

12、填充下面推理证明中没有写出的推理规则。
前提：，
结论：
证明：
① 附加前提引入
②①化简
③①化简
④ 前提引入
⑤②④假言推理
⑥③⑤假言推理
⑦ 前提引入
⑧③⑦假言推理
⑨⑥⑧假言推理
14、在自然推理系统P中构造下面推理的证明：
（2）前提：
结论：
证明：
①前提引入
②①置换
③ 前提引入
④②③析取三段论
⑤ 前提引入
⑥④⑤拒取式
（4）前提：
结论：
证明：
① 前提引入
②①化简
③①化简
④ 前提引入
⑤④置换
⑥⑤化简
⑦前提引入
⑧⑦置换
⑨⑧化简
⑩⑥⑨假言三段论
②⑩假言推理
前提引入
假言推理
⑨合取

15、在自然推理系统P中用附加前提法证明下面推理：
（1）前提：
结论：
证明：
① 附加前提引入
② 前提引入
③①②假言推理
④ 前提引入
⑤③④假言推理
⑥ 前提引入
⑦⑤⑥假言推理
16、在自然推理系统P中用归谬法证明下面推理：
（1）前提：
结论：
证明：
① 结论否定引入
②①置换
③②化简
④②化简
⑤ 前提引入
⑥ 前提引入
⑦④⑤拒取式
⑧③⑥拒取式
⑨⑦⑧合取
⑩⑨置换
前提引入
⑩矛盾。
17：在自然推理系统P中构造下面推理的证明：
只要A曾到过受害者房间并且11点以前没有离开，A就是谋杀嫌疑犯。A曾到过受害者房间。如果A在11点以前离开，看门人会看见过他。看门人没有看见他。所以，A是谋杀嫌疑犯。
解答：
（1） 命题符号化：A曾到过受害者房间；A在11点以前离开；
A就是谋杀嫌疑犯；看门人会看见过A；

（2） 推理的形式结构：
前提：
结论：
（3） 证明
① 前提引入
② 前提引入
③①②拒取式
④ 前提引入
⑤③④合取
⑥ 前提引入
⑦⑤⑥假言推理。

P63:习题四

5、在一阶逻辑中讲下列命题符号化。
（3）不存在比所有火车都快的汽车。
（4）凡是汽车就比火车慢是不对的。
解答：
（3）
（4）
6、将下列命题符号化，个体域为实数集合R，并指出各命题的真值。
（1）对所有的，都存在使得。
（3）对所有的，都存在使得。
解答：
（1），真值为1；
（3），真值为1；
9、给定解释I如下。
（a）个体域为实数集合R。
（b）特定元素。
（c）函数
（d）谓词。
给出下列公式在I下的解释，并指出它们的真值。
（1）
（3）
解答：（1）对任意的x和y，如果,那么。真值为1；
（3）对任意的x和y，如果,那么。真值为1；

11、判断下列各式的类型。
（2）
（4）
解答：（2）真值为1；真值为0；
所以真值为0，所以为永假式。
（4）和真值相同，所以为永真式。

13、给出下列各公式的一个成真解释和一个成假解释。
（1）
（2）
（3）
解答：
（1）成真解释：
成假解释：
（2）成真解释：
成假解释：
（3）成真解释：
成假解释：