离散数学答案 屈婉玲版 第二版 高等教育出版社课后答案 下载本文

⑩p ⑧⑨假言推理 (11)p?q ⑧⑩合取

15在自然推理系统P中用附加前提法证明下面各推理: (1)前提:p?(q?r),s?p,q 结论:s?r 证明

①s 附加前提引入 ②s?p 前提引入 ③p ①②假言推理 ④p?(q?r) 前提引入 ⑤q?r ③④假言推理 ⑥q 前提引入 ⑦r ⑤⑥假言推理

16在自然推理系统P中用归谬法证明下面各推理:

(1)前提:p??q,?r?q,r??s 结论:?p 证明:

①p 结论的否定引入 ②p?﹁q 前提引入 ③﹁q ①②假言推理 ④¬r?q 前提引入 ⑤¬r ④化简律 ⑥r?¬s 前提引入 ⑦r ⑥化简律 ⑧r?﹁r ⑤⑦ 合取

由于最后一步r?﹁r 是矛盾式,所以推理正确.

第四章部分课后习题参考答案

3. 在一阶逻辑中将下面将下面命题符号化,并分别讨论个体域限制为(a),(b)条件时命

5

题的真值:

(1) 对于任意x,均有

2=(x+

)(x

).

(2) 存在x,使得x+5=9. 其中(a)个体域为自然数集合. (b)个体域为实数集合. 解:

F(x):

2=(x+

)(x

).

G(x): x+5=9.

(1)在两个个体域中都解释为?xF(x),在(a)中为假命题,在(b)中为真命题。 (2)在两个个体域中都解释为?xG(x),在(a)(b)中均为真命题。

4. 在一阶逻辑中将下列命题符号化: (1) 没有不能表示成分数的有理数. (2) 在北京卖菜的人不全是外地人. 解:

(1)F(x): x能表示成分数 H(x): x是有理数

命题符号化为: ??x(?F(x)?H(x)) (2)F(x): x是北京卖菜的人 H(x): x是外地人

命题符号化为: ??x(F(x)?H(x)) 5. 在一阶逻辑将下列命题符号化: (1) 火车都比轮船快.

(3) 不存在比所有火车都快的汽车. 解:

(1)F(x): x是火车; G(x): x是轮船; H(x,y): x比y快 命题符号化为: ?x?y((F(x)?G(y))?H(x,y))

(2) (1)F(x): x是火车; G(x): x是汽车; H(x,y): x比y快 命题符号化为: ??y(G(y)??x(F(x)?H(x,y))) 9.给定解释I如下:

6

(a) 个体域D为实数集合R. (b) D中特定元素=0.

(c) 特定函数(x,y)=xy,x,y?D.

(d) 特定谓词(x,y):x=y,(x,y):x

答:(1) 对于任意两个实数x,y,如果x

(2) 对于任意两个实数x,y,如果x-y=0, 那么x

(a) 个体域D=N(N为自然数集合). (b) D中特定元素=2. (c) D上函数

=x+y,(x,y)=xy.

(d) D上谓词(x,y):x=y.

说明下列各式在I下的含义,并讨论其真值. (1) xF(g(x,a),x)

(2) xy(F(f(x,a),y)→F(f(y,a),x)

答:(1) 对于任意自然数x, 都有2x=x, 真值0.

(2) 对于任意两个自然数x,y,使得如果x+2=y, 那么y+2=x. 真值0.

11. 判断下列各式的类型:

(1) (3)

yF(x,y).

解:(1)因为 p?(q?p)??p?(?q?p)?1 为永真式; 所以

为永真式;

(3)取解释I个体域为全体实数 F(x,y):x+y=5

所以,前件为任意实数x存在实数y使x+y=5,前件真; 后件为存在实数x对任意实数y都有x+y=5,后件假,] 此时为假命题

7

再取解释I个体域为自然数N, F(x,y)::x+y=5

所以,前件为任意自然数x存在自然数y使x+y=5,前件假。此时为假命题。

此公式为非永真式的可满足式。 13. 给定下列各公式一个成真的解释,一个成假的解释。

(1) (F(x)

(2) x(F(x)G(x)H(x)) 解:(1)个体域:本班同学

F(x):x会吃饭, G(x):x会睡觉.成真解释

F(x):x是泰安人,G(x):x是济南人.(2)成假解释 (2)个体域:泰山学院的学生

F(x):x出生在山东,G(x):x出生在北京,H(x):x出生在江苏,成假解释. F(x):x会吃饭,G(x):x会睡觉,H(x):x会呼吸. 成真解释.

第五章部分课后习题参考答案

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)

(3)?x?y(F(x,y)?F(f(x),f(y))) 解:(1) ?x?yF(x,y)??x(F(x,3)?F(x,4))

? (F(3,3)?F(3,4))?(F(4,3)?F(4,4)) ?(0?1)?(1?0)?1

(2) ?x?y(F(x,y)?F(f(x),f(y)))

??x((F(x,3)?F(f(x),f(3)))?(F(x,4)?F(f(x),f(4))))

??x((F(x,3)?F(f(x),4))?(F(x,4)?F(f(x),3)))

8