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

证 明 (1)

若解释 I I ( 和 I 中赋 值 v 使得 x( A B))( v) 1 ， d DI 使 得则有

I ( A B )(v[ x/ d]) 1 ， I ( A)(v[ x/ d ]) I ( xB)( v) 1， I ( xA

I ( B)(v[ x / d ]) 1 ， I ( xA)( v ) 1

xB 。

d

且

xB)( v ) 1。这表明 x( A B) | xA

(2) 若解释 I 和 I 中赋值 v 使得 I ( x( A

B))( v) I ( xA)( v) 1，则对于每个

D ，

I

I ( A x( A

(3)

B)(v[ x /d]) I ( A)(v[ x / d ]) 1 ， I (B)( v[ x / d ]) 1 ， I ( xB)( v) 1 。 这 表 明 B), xA |

xB 。

I 中赋值 v 使得 I ( 若解释 I 和

xAy )(v) 1

y

x

，则有 d

DI 使得 I( A )(v[ x/ y]) 1

x

，

Ay)(v[x / d]) 因 为 I(

x

I ( A)(v[ x/ d][ y/ I ( x)(v[ x / d])]) I( A)(v[ x / d][ y / d])

， 所 以

I ( A)(v[ x / d][ y/ d]) 1 ， I ( yA)( v[ x /d]) 1 ， I ( x yA)( v) 1 。 这 表 明

x Ax |

y

x yA。

I

I ( 中 赋值 v 使 得

x(A

B))( v) 0 ， d DI ， 则 对于 每 个

0 ，因此 I ( xA)(v ) 1 且 x( A

B) 。

(4) 若解释 I 和

I ( A B)(v[ x / d]) 0 ， I ( A)( v[ x/ d]) 1 且 I (B)(v[ x / d ])

xB)( v) 0 。所以 x A

xB |

I ( xB)( v) 0， I ( xA

18. 设变元 x 既不是公式 B 中的自由变元， 也不是公式集 式。若 证明

中任何公式的自由变元，

A 是公

{ A} | B ，则

设解释

{ x A} | B 。

I

和 I 中赋值 v

满足

{ x A} ，则 I ( xA)( v) 1 ，有 d

中任何公式的自由变元，

DI 使得

，

I ( A v x d]) 1。因为 x不是公式集

)( [ /

I 和 v[ x / d]也满足 所以

I 和 v[ x / d] 满足 { A} 。又因为 { A} | B ，所以 I (B)(v[ x / d]) 1，因为 x 不是 B

{ x A} | B 。

{ A} 不可满足。

{ A} ，则 I

和 v 满足

中的自由变元，因此 I ( B)(v) 1。这表明 19. 设

是公式集合， A 是公式，则

| A 当且仅当

证明 设

{ A} 可满足，解释 I

I 中赋值 v 满足 和

且

I ( A)( v) 0 ，所以 | / A 。

设 |/ A ，则有解释 因此，

I 和 I 中赋值 v 满足 且 I ( A)( v) 0 ，所以 I 和 v 满足

{ A} 。

{ A} 可满足。

20. 判断以下公式集合是否可满足，并说明理由。 (1)

{ P(t) | t是项} { xP( x)}

P( y, z)

如下。

(2) { x P(x, x), x y z( P( x, y) 解 (1) 可满足。取解释

P(x, z)) , x yP( x, y)}

I 和 I 中赋值 v

I

I

D

{1, 2} ， P (1) 0， P (2) 1，

I

对每个常元 a，a

I 1；

I

x x

对每个 n 元函数符号 f， f ( , , ) 1；

1

n

对每个变元 x，

v(x) 1。

可归纳证明：对每个项

t， I (t)(v) 1。

I 和 v满足 { P(t) | t是项} { xP(x)} 。

(2) 可满足。取解释 I 和 I 中赋值 v 如下。

I

D 为自然数集，

P (x, y) 1

I

则I

和 v 满足{ x P( x, x) , x y z( P( x, y) P( y, z)

当且仅当

P( x,z)) , x y

x yP( x, y)} 。