网站地图
【www.arisingsemi.com--语言培训】
刻苦钻研 离散数学习题答案习题一及答案：（P14-15）
14、将下列命题符号化：
（5）李辛与李末是兄弟
解：设p：李辛与李末是兄弟，则命题符号化的结果是p
（6）王强与刘威都学过法语
解：设p：王强学过法语；q：刘威学过法语；则命题符号化的结果是
（9）只有天下大雨，他才乘班车上班
解：设p：天下大雨；q：他乘班车上班；则命题符号化的结果是
（11）下雪路滑，他迟到了
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、求下列公式的成真赋值：
所以公式的成真赋值有：01，10，11。
习题二及答案：（P38）
5、求下列公式的主析取范式，并求成真赋值：
（2）
解：原式
，此即公式的主析取范式，
所以成真赋值为011，111。
*
6、求下列公式的主合取范式，并求成假赋值：
（2）
解：原式，此即公式的主合取范式，
所以成假赋值为100。
7、求下列公式的主析取范式，再用主析取范式求主合取范式：
（1）
解：原式
，此即主析取范式。
主析取范式中没出现的极小项为，，，所以主合取范式中含有三个极大项，，，故原式的主合取范式。
9、用真值表法求下面公式的主析取范式：
（1）
解：公式的真值表如下：
0
0
0
1
0
0
0
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种成真赋值所对应的极小项的析取即为主析取范式，故主析取范式
习题三及答案：（P52-54）
11、填充下面推理证明中没有写出的推理规则。
前提：
结论：s
证明：
① p 前提引入
② 前提引入
③ q ①②析取三段论
④ 前提引入
⑤ r ③④析取三段论
⑥ 前提引入
⑦ s ⑤⑥假言推理
15、在自然推理系统P中用附加前提法证明下面推理：
（2）前提：
结论：
证明：用附加前提证明法。
① p 附加前提引入
② ①附加
③ 前提引入
④ ②③假言推理
⑤ s ④化简
⑥ ⑤附加
⑦ 前提引入
⑧ u ⑥⑦假言推理
故推理正确。
16、在自然推理系统P中用归谬法证明下面推理：
（1）前提：，，
结论：
证明：用归谬法
① p 结论的否定引入
② 前提引入
③ ①②假言推理
④ 前提引入
⑤ ③④析取三段论
⑥ 前提引入
⑦ r ⑥化简
⑧ ⑤⑦合取
由于，所以推理正确。
17、在自然推理系统P中构造下面推理的证明：
只要A曾到过受害者房间并且11点以前没离开，A就是谋杀嫌犯。A曾到过受害者房间。
如果A在11点以前离开，看门人会看见他。看门人没有看见他。所以，A是谋杀嫌犯。
解：设p：A到过受害者房间，q：A在11点以前离开，r：A是谋杀嫌犯，s：看门人看见过A。
则前提：，，，
结论：
证明：
① 前提引入
② 前提引入
③ ①②拒取式
④ 前提引入
⑤ ③④合取引入
⑥ 前提引入
⑦ ⑤⑥假言推理
习题四及答案：（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快；则命题符号化的结果是：
(b) 特定元素。
(c) 函数。
该公式在I解释下的真值为假。
14、证明下面公式既不是永真式也不是矛盾式：
习题五及答案：（P79-81）
5、给定解释I如下：
(a) 个体域D={3,4}
(b)
试求下列公式在I下的真值：
解：方法一：先消去存在量词
15、在自然推理系统中，构造下面推理的证明：
（3）前提：，
结论：
证明：
① 前提引入
② ①置换
③ ②UI规则
④ 前提引入
⑤ ④UI规则
⑥ ③⑤析取三段论
⑦ ⑥EG规则
*
22、在自然推理系统中，构造下面推理的证明：
（2）凡大学生都是勤奋的。王晓山不勤奋。所以王晓山不是大学生。
解：设F(x)：x为大学生，G(x)：x是勤奋的，c：王晓山
则前提：，
结论：
证明：
① 前提引入
② ①UI规则
③ 前提引入
④ ②③拒取式
25、在自然推理系统中，构造下面推理的证明：
每个科学工作者都是刻苦钻研的，每个刻苦钻研而又聪明的人在他的事业中都将获得成功。王大海是科学工作者，并且是聪明的。所以，王大海在他的事业中将获得成功。（个体域为人类集合）
解：设F(x)：x是科学工作者，G(x)：x是刻苦钻研的，H(x)：x是聪明的，I(x)：x在他的事业中获得成功，c：王大海
则前提：，，
结论：
证明：
① 前提引入
② ①化简
③ ①化简
④ 前提引入
⑤ ④UI规则
⑥ ②⑤假言推理
⑦ ③⑥合取引入
⑧ 前提引入
⑨ ⑧UI规则
⑩ ⑦⑨假言推理
习题六及答案（P99-100）
28、化简下述集合公式：
30、设A,B,C代表任意集合，试判断下面命题的真假。
如果为真，给出证明；如果为假，给出反例。
解：该命题为假，，如果，则，否则，故为假。
举反例如下：则。
但。
33、证明集合恒等式：
习题七及答案：（P132-135）
26 设，R为A上的关系，R的关系图如图7.13所示：
（1）求的集合表达式；
（2）求r(R), s(R), t(R)的集合表达式。
解：
（1）由R的关系图可得
所以，，
可得；
（2），
（1）只需证明R具有自反性、对称性和传递性即可，证明过程如下：
46、分别画出下列各偏序集的哈斯图，并找出A的极大元、极小元、最大元和最小元。
（1）
解：哈斯图如下：
A的极大元为e、f，极小元为a、f；
A的最大元和最小元都不存在。
*
22、给定，A上的关系，试
（1）画出R的关系图；
（2）说明R的性质。
● ●
● ●
（2）R的关系图中每个顶点都没有自环，所以R是反自反的，不是自反的；
R的关系图中任意两个顶点如果有边的都是单向边，故R是反对称的，不是对称的；
R的关系图中没有发生顶点x到顶点y有边、顶点y到顶点z有边，但顶点x到顶点z没有边的情况，故R是传递的。
*
48、设为偏序集，在集合上定义关系T如下：
证明T为上的偏序关系。
证明：
（1）自反性：
（2）反对称性：
（3）传递性：
综合
（1）
（2）
（3）知T具有自反性、反对称性和传递性，故T为上的偏序关系。
习题九及答案：（P179-180）
8、
（1）
（2）。
解：
（1）
（2）
11、
（3）；
解：
（3）由*运算的定义可知：，
16、
习题十一及答案：（P218-219）
1、图11.11给出了6个偏序集的哈斯图。判断其中哪些是格。
如果不是格，说明理由。