内容发布更新时间 : 2024/6/18 21:05:17星期一 下面是文章的全部内容请认真阅读。
离散数学习题答案
离散数学习题答案
习题二及答案:(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?M2?M4。
9、用真值表法求下面公式的主析取范式: (1)(p?q)?(?p?r) 解:公式的真值表如下:
p 0 0 0 0 1 1 1 q 0 0 1 1 0 0 1 r 0 1 0 1 0 1 0 ?p 1 1 1 1 0 0 0 p?q 0 0 1 1 1 1 1 ?p?r 0 1 0 1 0 0 0 (p?q)?(?p?r) 0 1 1 1 1 1 1 离散数学习题答案
1 1 1 0 1 0 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 前提引入
r?s 前提引入
③ q ①②析取三段论 ⑤ r ③④析取三段论 ⑥
⑦ s ⑤⑥假言推理
15、在自然推理系统P中用附加前提法证明下面推理: (2)前提:(p?q)?(r?s),(s?t)?u 结论:
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 证明: ① ② ③ ④ ⑤ ⑥ ⑦
p,q?s,?s
q?s 前提引入
?s 前提引入
?q ①②拒取式 p 前提引入
p??q ③④合取引入
(p??q)?r 前提引入 r ⑤⑥假言推理
习题五及答案:(P80-81)
15、在自然推理系统N?中,构造下面推理的证明: (3)前提:?x(F(x)?G(x)),??xG(x) 结论:?xF(x) 证明: ① ② ③ ④ ⑤ ⑥ ⑦
??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) ②⑤假言推理 G(c)?H(c) ③⑥合取引入 ?x(G(x)?H(x)?I(x)) 前提引入 G(c)?H(c)?I(c) ⑧UI规则 I(c) ⑦⑨假言推理
习题七及答案:(P132-135) 22、给定
A??1,2,3,4?,A上的关系R??1,3,1,4,2,3,2,4,3,4?,试
离散数学习题答案
(1)画出R的关系图; (2)说明R的性质。 解:(1)
1 ● ● ● ● 2 3 4 (2)R的关系图中每个顶点都没有自环,所以R就是反自反的,不就是自反的;
R的关系图中任意两个顶点如果有边的都就是单向边,故R就是反对称的,不就是对称的;
R的关系图中没有发生顶点x到顶点y有边、顶点y到顶点z有边,但顶点x到顶点z没有边的情况,故R就是
传递的。 26 设
A??1,2,3,4,5,6?,R为A上的关系,R的关系图如图7、13所示:
2(1)求R,R3的集合表达式;
(2)求r(R), s(R), t(R)的集合表达式。 解:(1)由R的关系图可得R?所以R可得R2?1,5,2,5,3,1,3,3,4,5?
?R?R??3,1,3,3,3,5?,R3?R2?R??3,1,3,3,3,5?,
n??3,1,3,3,3,5?,当n>=2;
??1,5,2,5,3,1,3,3,4,5,1,1,2,2,4,4,5,5,6,6(2)r(R)=RUIA?,
s(R)?RUR?1??1,5,5,1,2,5,5,2,3,1,1,3,3,3,4,5,5,4t(R)?RUR2UR3U...?RUR2??1,5,2,5,3,1,3,3,4,5,3,546、分别画出下列各偏序集(1)R?? ?
A,R?的哈斯图,并找出A的极大元、极小元、最大元与最小元。
??a,d,a,c,a,b,a,e,b,e,c,e,d,e?UIA
解:哈斯图如下:
e b c d a
A的极大元为e、极小元为a; A的最大元为e、最小元为a。