离散数学习题答案 习题一及答案：
（P14-15） 14、将下列命题符号化： （5）李辛与李末是兄弟 解：设p：李辛与李末是兄弟，则命题符号化的结果是p （6）王强与刘威都学过法语
解：设p：王强学过法语；q：
刘威学过法语；则命题符号化的结果是 （9）只有天下大雨，
他才乘班车上班 qp解：设p：天下大雨；q：他乘班车
上班；则命题符号化的结果是 （11）下雪路滑，他迟到了 解：设p：下雪；q：路滑；r：他迟到了；则命题符号化的结果是
15、设p：2+3=5. q：大熊猫产在中国. r：
太阳从西方升起. 求下列复合命题的真值：
（4） 解：p=1，q=1，r=0，
，
19、用真
值表判断下列公式的类型：
（2） 解：列出公
式的真值表，如下所示：
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）
值的条件是：
解：因为该公式是一个蕴含式，所以首先分析它的成假赋值，成假赋
成真赋值有：01，
10，11。 所以公式的 习题二及答案：（P38） 5、求下列公式的主析取范式，并求成真赋值： （2）
解：原式
，此即公式的主析取范式， 所以成真赋值为011，111。 *6、
求下列公式的主合取范式，并求成假赋值： （2）
解：原式，此即公式的主合取范式，
所以成假赋值为100。 7、
求下列公式的主析取范式，再用主析取范式求主合取范式： （1）
解：原式 ，此即主
析取范式。 主析取范式中没出现的极
9、用
小项为，，，所以主合取范式中含有三个极大项，，
MMmmm02024
，故原式的主合取范式。
真值表法求下面公式的主析取范式： （1）
解：公式的真值表如下：
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种成真赋值所对应的极小项的析取即为主析取范式，故主析取范式
567 习题三及答
案：（P52-54） 11、填充下面推理证明中没有写出的推理规则。 前提：
明： ① p 前提引入 ② 前提引入 ①②析取三段论 ③④析取三段论
结论：s 证
④ 前提引入
前提引入 ⑦ s ⑤⑥（2）前提：
证明：用附
假言推理 15、在自然推理系统P中用附加前提法证明下面推理：
结论：
② ①附加 ④化简 ⑥ ⑤附加
加前提证明法。 ① p 附加前提引入
③ 前提引入 ⑦ 前提引入
④ ②③假言推理 ⑤ s
⑧ u ⑥⑦假言推理 故推理正确。 16、
在自然推理系统P中用归谬法证明下面推理： （1）前提：，，
结论： p证明：用
④ 前提引入
⑥ 前
由
归谬法 ① p 结论的否定引入 ② 前提引入
③ ①②假言推理 ⑤ ③④析取三段论 于，所以推理正确。
提引入 ⑦ r ⑥化简 ⑧ ⑤⑦合取
17、在自然推理系统P
中构造下面推理的证明： 只要A曾到过受害者房间并且11点以前没离开，A就是谋杀嫌犯。A曾到过
受害者房间。如果A在11点以前离开，看门人会看见他。看门人没有看见他。所以，A是谋杀嫌犯。 解：设p：A到过受害者房间，q：A在11点以前离开，r：A是谋杀嫌犯，s：看门人看见过A。 前提：，，， 前提引入 取式
则
结论： r证明： ①
② 前提引入 ③ ①②拒
⑥ 前提引入
⑦
④ 前提引入 p
⑤ ③④合取引入
⑤⑥假言推理 r 习题四及答案：（P65-67） 5、在一阶逻辑中将下列命题符号化： （2）有的火车比有的汽车快。 解：设F(x)：x是火车，G(y)：y是汽车，H(x,y)：x比y快；则命题符号化的结果是：
（3）不存在比所有火车都快的汽车。 解：方法一： 设F(x)：x是汽车，G(y)：y是火车，H(x,y)：x比y快；则命题符号化的结果是：
或 方法二：
设F(x)：x是
火车，G(y)：y是汽车，H(x,y)：x比y快；则命题符号化的结果是：
给定解释I如下： (a) 个体域为实数集合R。 (c) 函数。的真值：
或 9、
(b) 特定元素。
解：解释是：，含义是：
谓词。 给出以下公式在I下的解释，并指出它们
（2）
对于任意的实数x，y，若x-y=0则x 该公式在I解释下的真值为假。14、证明 下面公式既不是永真式也不是矛盾式： （1） I F(x)H(x,y)G(y)：x是兔子，：y是乌龟，：x''IIH(x,y)取解释如下：：x 解：取解释如下：个体域为全总个体域， 比y跑得快，则该公式在解释I下真值是1； 比y跑得慢，其它同上，则该公式在解释下真值是0； 故公式（1）既不是永真式也不是矛盾式。 此题答案不唯一，只要证明公式既不是永真式也不是矛盾式的每个解释合理即可。 习题五及答案：（P79-81） 5、给定解释I如下： (a) 个体域 D={3,4} (b) (c) 试求下列公式在I下的真值： 方 法 一 ： 先 消 (1) 解： 去 存 在 量 词 结论： ② ①置换 ④ 前提引入 ⑥ 15、在自然推理系统中，构造下面推理的证明： N（3）前提：， 证明： ① 前提引入 ③ ②UI规则 ⑤ ④UI规则 ③⑤析取三段论 F(c)⑦ ⑥EG规则 *22、在自然推理系统中，构造下面推理的证明： （2）凡大学生都是勤奋的。王晓山不勤奋。所以王晓山不是大学生。 解：设F(x)：x为大学生，G(x)：x是勤奋的，c：王晓山 则前提：，