离散数学习题答案
习题二及答案：（P38）
5、求下列公式的主析取范式，并求成真赋值： （2）(?p?q)?(q?r) 解：原式?(p?q)?q?r
?q?r?(?p?p)?q?r
?(?p?q?r)?(p?q?r)?m3?m7，此即公式的主析取范式，
所以成真赋值为011，111。
6、求下列公式的主合取范式，并求成假赋值： （2）(p?q)?(?p?r)
解：原式?(p??p?r)?(?p?q?r)所以成假赋值为100。
7、求下列公式的主析取范式，再用主析取范式求主合取范式： （1）(p?q)?r 解：原式?
?(?p?q?r)?M4，此即公式的主合取范式，
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?m3?m5?m6?m7，此即主析取范式。
主析取范式中没出现的极小项为m0，m2，m4，所以主合取范式中含有三个极大项M0，M2，M4，故原式的主合取范式?M0
9、用真值表法求下面公式的主析取范式： （1）(p?q)?(?p?r) 解：公式的真值表如下： ?M2?M4。
p 0 0 q 0 0 r 0 1 ?p 1 1 p?q 0 0 ?p?r 0 1 (p?q)?(?p?r) 0 1 0 0 1 1 1 1
1 1 0 0 1 1 0 1 0 1 0 1 1 1 0 0 0 0 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1 1 1 1 由真值表可以看出成真赋值的情况有7种，此7种成真赋值所对应的极小项的析取即为主析取范式，故主析取范式
?m1?m2?m3?m4?m5?m6?m7
习题三及答案：（P52-54）
11、填充下面推理证明中没有写出的推理规则。 前提：?p?q,?q?r,r结论：s 证明：
① p 前提引入 ② ④
?s,p
?p?q 前提引入 ?q?r 前提引入
③ q ①②析取三段论 ⑤ r ③④析取三段论 ⑥
15、在自然推理系统P中用附加前提法证明下面推理： （2）前提：(p?q)?(r?s),(s?t)?u 结论：
r?s 前提引入
⑦ s ⑤⑥假言推理
p?u
证明：用附加前提证明法。 ① p 附加前提引入 ② ③ ④ ⑥ ⑦
p?q ①附加
(p?q)?(r?s) 前提引入
r?s ②③假言推理
⑤ s ④化简
s?t ⑤附加
(s?t)?u 前提引入
⑧ u ⑥⑦假言推理 故推理正确。
16、在自然推理系统P中用归谬法证明下面推理：
p??q，?r?q，r??s 结论：?p
（1）前提：
证明：用归谬法
① p 结论的否定引入 ② ③ ④ ⑤ ⑥
p??q 前提引入 ?q ①②假言推理 ?r?q 前提引入
?r ③④析取三段论 r??s 前提引入
⑦ r ⑥化简 ⑧r??r ⑤⑦合取 由于r??r?0，所以推理正确。
17、在自然推理系统P中构造下面推理的证明：
只要A曾到过受害者房间并且11点以前没离开，A就是谋杀嫌犯。A曾到过受害者房间。如果A在11点以前离开，看门人会看见他。看门人没有看见他。所以，A是谋杀嫌犯。
解：设p：A到过受害者房间，q：A在11点以前离开，r：A是谋杀嫌犯，s：看门人看见过A。 则前提：(p??q)?r， 结论：r 证明： ① ② ③ ④ ⑤ ⑥ ⑦
习题五及答案：（P80-81）
15、在自然推理系统N?中，构造下面推理的证明： （3）前提：?x(F(x)?G(x))，??xG(x) 结论：?xF(x) 证明： ① ② ③ ④
p，q?s，?s
q?s 前提引入
?s 前提引入
?q ①②拒取式
p 前提引入
p??q ③④合取引入
(p??q)?r 前提引入
r ⑤⑥假言推理
??xG(x) 前提引入 ?x?G(x) ①置换 ?G(c) ②UI规则 ?x(F(x)?G(x)) 前提引入
⑤ ⑥ ⑦
F(c)?G(c) ④UI规则 F(c) ③⑤析取三段论
?xF(x) ⑥EG规则
22、在自然推理系统N?中，构造下面推理的证明：
（2）凡大学生都是勤奋的。王晓山不勤奋。所以王晓山不是大学生。 解：设F(x)：x为大学生，G(x)：想是勤奋的，c：王晓山 则前提：?x(F(x)?G(x))，?G(c) 结论：?F(c) 证明： ① ② ③ ④
?x(F(x)?G(x)) 前提引入 F(c)?G(c) ①UI规则 ?G(c) 前提引入 ?F(c) ②③拒取式
25、在自然推理系统N?中，构造下面推理的证明：
每个科学工作者都是刻苦钻研的，每个刻苦钻研而又聪明的人在他的事业中都将获得成功。王大海是科学工作者，并且是聪明的。所以，王大海在他的事业中将获得成功。（个体域为人类集合）
解：设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) 证明： ① ② ③ ④ ⑤ ⑥
F(c)?H(c) 前提引入 F(c) ①化简
H(c) ①化简 ?x(F(x)?G(x)) 前提引入 F(c)?G(c) ④UI规则 G(c) ②⑤假言推理