离散数学习题答案(耿素云屈婉玲)

离散数学习题答案

习题二及答案:(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) ②⑤假言推理

联系客服:779662525#qq.com(#替换为@)