离散数学习题答案

离散数学习题答案

习题一及答案：（P14-15） 14、将下列命题符号化：

（5）李辛与李末是兄弟

解：设p：李辛与李末是兄弟，则命题符号化的结果是p （6）王强与刘威都学过法语

解：设p：王强学过法语；q：刘威学过法语；则命题符号化的结果是（9）只有天下大雨，他才乘班车上班

解：设p：天下大雨；q：他乘班车上班；则命题符号化的结果是q p （11）下雪路滑，他迟到了

解：设p：下雪；q：路滑；r：他迟到了；则命题符号化的结果是(p q) r

15、设p：2+3=5.

q：大熊猫产在中国. r：太阳从西方升起. 求下列复合命题的真值：

（4）(p q r) (( p q) r) 解：p=1，q=1，r=0，

p q

(p q r) (1 1 0) 1，

(( p q) r) (( 1 1) 0) (0 0) 1 (p q r) (( p q) r) 1 1 1

19、用真值表判断下列公式的类型： （2）(p p) q

解：列出公式的真值表，如下所示：

20、求下列公式的成真赋值：

（4） (p q) q

解：因为该公式是一个蕴含式，所以首先分析它的成假赋值，成假赋值的条件是：

(p q) 1 p 0

q 0q 0

所以公式的成真赋值有：01，10，11。

习题二及答案：（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) ( p q r) M4，此即公式的主合取范式， 所以成假赋值为100。

7、求下列公式的主析取范式，再用主析取范式求主合取范式： （1）(p q) r

解：原式 p q ( r r) (( p p) ( q q) r) (p q r) (p q )r ( p q r)

(p q

( p q ) r( p q )r ( p) r( p

q )r ( p

q

) r (

q )r ( p q r

pq r

m1 m3 m5 m6 m，此即主析取范式。 7

主析取范式中没出现的极小项为m0，m2，m4，所以主合取范式中含有三个极大项M0，M2，

M4，故原式的主合取范式 M0 M2 M4。

9、用真值表法求下面公式的主析取范式：

（1）(p q) ( p r) 解：公式的真值表如下：

由真值表可以看出成真赋值的情况有7种，此7种成真赋值所对应的极小项的析取即为主析取范式，故主析取范式 m1 m2 m3 m4 m5 m6 m7

习题三及答案：（P52-54）

11、填充下面推理证明中没有写出的推理规则。 前提： p q, q r,r s,p 结论：s 证明：

① p 前提引入 ② p q 前提引入 ③ q ①②析取三段论 ④ q r 前提引入

⑤ r ③④析取三段论 ⑥ r s 前提引入

⑦ 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中用归谬法证明下面推理： （1）前提：p q， r q，r s 结论： p

证明：用归谬法

① 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，p，q s， s 结论：r 证明：

① q s 前提引入 ② s 前提引入 ③ q ①②拒取式 ④ p 前提引入

⑤ p q ③④合取引入 ⑥ (p q) r 前提引入 ⑦ r ⑤⑥假言推理

习题四及答案：（P65-67）

5、在一阶逻辑中将下列命题符号化： （2）有的火车比有的汽车快。

解：设F(x)：x是火车，G(y)：y是汽车，H(x,y)：x比y快；则命题符号化的结果是：

x y(F(x) G(y) H(x,y))

（3）不存在比所有火车都快的汽车。 解：方法一：

设F(x)：x是汽车，G(y)：y是火车，H(x,y)：x比y快；则命题符号化的结果是：

x(F(x) y(G(y) H(x,y)))或 x(F(x) y(G(y) H(x,y)))

方法二：

设F(x)：x是火车，G(y)：y是汽车，H(x,y)：x比y快；则命题符号化的结果是：

x(G(x) y(F(y) H(x,y)))或 x y(G(x) (F(y) H(x,y)))

9、给定解释I如下：

(a) 个体域为实数集合R。 (b) 特定元素a

0。

(c) 函数

f(x,y) x y,x,y R。

(d) 谓词F(x,y):x y,G(x,y):x y,x,y R。

给出以下公式在I下的解释，并指出它们的真值：

（2） x y(F(f(x,y),a) G(x,y))

解：解释是： x y(x

y 0 x y)，含义是：对于任意的实数x，y，若x-y=0则x<y。

该公式在I解释下的真值为假。

14、证明下面公式既不是永真式也不是矛盾式： （1） x(F(x) y(G(y) H(x,y)))

解：取解释I如下：个体域为全总个体域，

F(x)：x是兔子，G(y)：y是乌龟，H(x,y)：x比y跑得快，则该公式在解释I下真值是1；

取解释I如下：H(x,y)：x比y跑得慢，其它同上，则该公式在解释I下真值是0；

'

'

故公式（1）既不是永真式也不是矛盾式。

此题答案不唯一，只要证明公式既不是永真式也不是矛盾式的每个解释合理即可。

习题五及答案：（P79-81）

5、给定解释I如下： (a) 个体域D={3,4}

(b)

f(x):f(3) 4,f(4) 3

(c) F(x,y):F(3,3) F(4,4) 0,F(3,4) F(4,3) 1 试求下列公式在I下的真值： (1)

x yF(x,y)

x yF(x,y) x(F(x,3) F(x,4))

解：方法一：先消去存在量词

(F(3,3 )F(3, 4)F)( (4F,3)

(0 1) (1 0)

1

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)：x是勤奋的，c：王晓山 则前提： x(F(x) G(x))， G(c) 结论： F(c) 证明：

① x(F(x) G(x)) 前提引入 ② F(c) G(c) ① …… 此处隐藏：7378字，全部文档内容请下载后查看。喜欢就下载吧 ……