新版离散数学答案（尹宝林版）第二章习题解答课件 doc - 图文

第二章 谓词逻辑

习题与解答

1. 将下列命题符号化：

(1) 所有的火车都比某些汽车快。 (2) 任何金属都可以溶解在某种液体中。 (3) 至少有一种金属可以溶解在所有液体中。 (4) 每个人都有自己喜欢的职业。 (5) 有些职业是所有的人都喜欢的。 解 (1) 取论域为所有交通工具的集合。令

T (x): x 是火车， C (x) : x 是汽车， F ( x, y) : xy 跑得快。比

“所有的火车都比某些汽车快”可以符号化为 (2) 取论域为所有物质的集合。令

x(T (x) y(C( y) F (x, y))) 。

M (x) : x是金属， L(x): x 是液体，

D (x, y) : x 可以溶解在 y 中。 x(M (x)

y( L( y) D( x, y))) 。

可以符号化为

“任何金属都可以溶解在某种液体中” 可以符号化为

(3) 论域和谓词与 (2) 同。“至少有一种金属可以溶解在所有液体中”

x(M (x) y( L( y) D (x, y ))) 。

(4) 取论域为所有事物的集合。令

M (x) : x是人，

“每个人都有自己喜欢的职业”

J (x): x 是职业，

L(x, y) : x 喜欢 y。

y( J( y) L(x, y)))

可以符号化为

x(M ( x)

(5) 论 域 和 谓 词 与 (4) 同 。“ 有 些 职 业 是 所 有 的 人 都 喜 欢 的 ” 可 以 符 号 化 为

x(J(x) y(M ( y) L (y,x))) 。

（加法）， （乘法）和谓词

， 将下列命题符号化：

2. 取论域为正整数集，用函数

(1) 没有既是奇数，又是偶数的正整数。 (2) 任何两个正整数都有最小公倍数。 (3) 没有最大的素数。

(4) 并非所有的素数都不是偶数。

解 先引进一些谓词如下：

D( x, y) : x 能被 y 整除， D( x, y) 可表示为 v(v y x) 。 J( x) : x 是奇数， J(x) 可表示为

v(v 2 x) 。

E( x) : x 是偶数， E( x) 可表示为 v(v 2 x) 。

P(x): x 是素数， P( x) 可表示为 (x 1) u( v(v u x) u 1 u x) 。

(1) “没有既是奇数，又是偶数的正整数”可表示为 并可进一步符号化为

x(J (x) E(x)) ，

x( v(v 2 x) v(v 2 x)) 。

(2) “任何两个正整数都有最小公倍数”可表示为

x y z(D (z, x) D (z, y)

并可进一步符号化为

u(D (u, x) D (u, y) z u z u )) ，

x y z( v(v x z) v(v y z) u( v(v x u)

y( P( y)

v(v y u) y x y

z u z u ))

(3) “没有最大的素数”可表示为 并可进一步符号化为

x( P(x) x)) ，

x( (x 1)

y( ( y 1)

u( v(v u x)

y)

u 1 u x)

y)

y x

y x))

u( v(v u u 1 u x( P(x) u 1 u

(4) “并非所有的素数都不是偶数”可表示为

E( x)) ，并可进一步符号化为 x)

v(v 2 x))

x( (x 1)

3. 取论域为实数集合，用函数 (1) 没有最大的实数。

u( v(v u x)

，－（减法）和谓词 ， 将下列命题符号化：

(2) 任何两个不同的实数之间必有另一实数。 (3) 函数 f (x) 在点 a 处连续。 (4) 函数 f (x) 恰有一个根。 (5) 函数 f (x) 是严格单调递增函数。 解 (1) “没有最大的实数”符号化为

x y( y x y x) 。

符号化为

(2)“任何两个不同的实数之间必有另一实数” (3) “函数 f (x) 在点 a 处连续”的定义是： 任给

x y(x y z(x z z y)) 。

0 ，总可以找到 0 ，使得只要 | x a | 就有 | f (x) f (a) |

。

“函数 f (x) 在点 a 处连续”符号化为

(0 (0 x(a x x a f (a) f (x) f (x) f (a) )))

(4) “函数 f (x) 恰有一个根”符号化为 x( f (x) 0 y( f (y) 0

f (x)

y x)) 。 f ( y)) 。

(5) “函数 f (x) 是严格单调递增函数”符号化为 x y(x y

4. 指出下列公式中变元的约束出现和自由出现，并对量词的每次出现指出其辖域。 (1) (2) (3) (4) (5)

x(P( y, x) xP(x)

P(x, a)) zQ( x, y)

xP( x) Q (x) xP( z, g (x, y ))) xR( x )) R(x)

P( x, a)) 中三次出现都是约束出现，

x 的唯一出现的辖

x(P( x) R( x)) y(P( f (x, y), x) x(P( x)

Q( x)

解 (1) 变元 x 在 x( P( y, x) 域是 P(y, x)

P(x, a)。

(2) 变元 x 在 xP(x) 变 元

y 在

zQ( x, y) 中的头两次出现是约束出现，第三次出现是自由出现。 zQ( x, y) 中 的 唯 一 出 现 是 自 由 出 现 。 变 元 z 在

x 的唯一出现的辖域是

P(x )， z 的唯

xP( x)

xP (x) zQ( x, y) 中的唯一出现是约束出现。

一出现的辖域是 Q( x, y)。 (3) 变元 x 在 x(P(x) R( x)) 现是自由出现。

xP( x) Q( x) 中的头五次出现是约束出现，第六次出

P(x) R(x)，第二次出现的辖域是

P(x)。

x 的第一次出现的辖域是

(4) 变元 x 在 y( P( f (x, y), x) 现是约束出现。 P(f (x, y), x)

xP( z, g (x, y ))) 中的头两次出现是自由出现， 后两次出

P( z, g( x, y))， y 的唯一出现的辖域是

x 的唯一出现的辖域是 xP( z, g( x, y))。

(5) 变元 x 在 x( P( x) Q( x) xR( x )) R(x) 中的头五次出现是约束出现， 第六次出现

Q(x)

xR(x)， x 的唯一出现的辖域是 R( x)。

是自由出现。 x 的唯一出现的辖域是 P( x) 5. 归纳证明：若

t， t 是项，则

x

t

t 也是项。

证明 ① 若 t 是 x，则 t x 是 t ， x

t 是项。

t

t

② 若 t 是不同于 x 的变元 y，则 ttx 仍是 y，ttx 是项。 ③ 若 t 是常元 a，则 t x 仍是 a， x

t 是项。

t

④若 t 是 f (t1,

t

,tn) ，则

t

x x

f (( t1)t 是

, ,(t ) )，由归纳假设知

n t

x

x x

t

(t1) , ,( ) 都是项，

t t

n t

x

所以

t

t 是项。

6. 归纳证明：若 证明

t 是项， A 是公式，则 Atx 也是公式。

,tn ) ，则

① 若 A 是 P( t1,

x ，由上题知 P x

A 是 (( 1) , ,( ) )

t t t

x x

x

t

(t1) , , ( ) 都是

t

n t

t n t

项，所以

x t

A 是公式。

xB ，由归纳假设知

xB 是公式，所以

x② 若 A 是 B ，则 A是

x

A 是公式。

t

t

t

x ，由归纳假设知

t

xxB 和 C 都是公式，所以

③ 若 A 是 B

xC ，则 A是B

x

x t

t

C

t

t

t

A 是公

t

式。

④ 若 A 是

xB ，则

x

x

A 仍是 A， A 是公式。

t

t

⑤ 若 A 是

yB ，其中 y 是不同于 x 的变元，则 Ax是 yBx，由归纳假设知

t

t

x

B 是公式，

t

x

所以

A 是公式。

t

7.

I 中赋值 v 如下：给定解释 I 和

D

I

，aI

1， bI

2 ， f I(1) 2 ， f I(2) 1

{1, 2}

PI ( PI ， PI( 2,1) PI(2, 2) 0 ，v(x) 1， v( y) 1

1,1) (1, 2) 1

计算下列公式在解释 (1) P(a, f ( x)) (2) (3)

I 和赋值 I 中 v 下的真值。

P(x, f (b)) P( f ( y), x)

x yP( y, x) x y( P( x, y)

P( f ( x), f ( y)))

解 (1)

I ( P(a, f ( x)) P( x, f (b)) P( f ( y), x))( v)

IP

I I I I I I I

(a , f (v( x))) P (v( x), f (b )) P ( f (v( y)), v( x))