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

则 I ( x(P(x) Q( x)) (4)

xP (x) xQ ( x)) 0 。

xP( x, x) x yP( x, y) 是非永真的可满足式。给定解释

I

I 如下。

DI

{d}

则 I ( xP( x, x) 给定解释 I 如下。

I

I

， P (d, d) 1

x yP( x, y)) 1。

P，

I

(a ,b) PI (b,a) 0

DI

则 I ( xP( x, x) (5) ( xP( x)

{a, b} ， P (a, a) P (b ,b) 1

x yP( x, y)) 0 。 xQ( x))

x(P( x)

Q( x)) 是非永真的可满足式。给定解释

I

， Q

I 如下。

I (d) 1

DI

则 I (( xP( x)

{d} ， P (d) 1

x(P( x)

Q( x))) 1。

xQ( x))

给定解释 I 如下。

I

P，

I

(b) 0， QI (a) 0， QI (b) 1

{a, b} DI

则 I (( xP(x) (6)

P ，

xQ( x)) xQ( x))

(a) 1

x( P( x) x( P( x)

Q( x))) 0 。

Q(x )) 是 永 真 式 。 若 解 释 I 使 得

I

I

，因此 P

( xP( x)

I (d) 1

且

( x(P(x

I ) Q x)))

(

0

，则存在

d DI 使得 P (d)

Q (d) 0

xQ( x))) 0。

QI

， I ( xP(x )) 1且 I ( xQ( x)) 0， I (( xP (x)

(d) 0

(7)

x(P( x) Q( x)) ( xP( x) xQ (x)) 是 永 真 式 。 若 解 释 I

使 得

I

(( xP( x)

， 则 I ( xP( x)) 1 且 I ( xQ( x)) 0 。 存 在 d DI 使 得

xQ (x))) 0

0 ，所以 QI (d) 0 ， PI (d)

PI

，又因为 I ( xQ( x))

QI (d) 0 。因此，

(d) 1

I ( x( P( x)

Q (x))) 0。

12. 设 A, B 是任意公式，证明以下公式是永真式。

(1)

Ax

t

xA

, 其中项 t 对于 A 中的 x 是可代入的。

(2) (3)

xA xA

x A x A

(4) x( A B) xA xB

(5) xA xB x(A B) (6)

x( A

B)

(A

xB) ，其中 x 不是 A 的自由变元。

x

x 解 (1)

任取解释 I 和 I 中赋值 v，若

I( At )(v) 1, 则 I (A )( v) I (A)(v[ x / I (t)(v)] ) 1

t

所以 I ( xA)( v) 1。这表明 Ax

xA

t

是永真式。

(2)

任取解释 I 和I

中赋值 v，

( xA)( v) 1

I

当且仅当

I ( xA)(v) 0

当且仅当 存在d DI 使得 I ( A)( v[ x/ d]) 0 当且仅当 存在d

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

当且仅当 I ( x A)(v) 1 这表明 xA

x A 是永真式。

(3)

任取解释 I 和I

中赋值 v，

I (

xA)(v) 0

当且仅当

I ( xA)( v) 1

当且仅当 存在d DI 使得 I ( A)( v[ x/ d]) 1 当且仅当 存在d

DI 使得 I ( A)( v[ x/ d]) 0

当且仅当 I ( x A)(v) 0 这表明 xA

x A 是永真式。

(4)

任 取 解 释

I 和

I 中 赋 值 v ， 若 I ( x(A B) ) v() 1 ， 则 存 在 d DI 使 得

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

xB)( v ) 1。这表明 x( A B) xA xB 是永真式。

(5)

任 取 解 释 I 和

I 中 赋 值 v， 若 I ( x( A B) )v() 0 ， 则 存 在

d DI 使 得，

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

这表明 (6)

I (B)(v[ x / d ] ) 0 ， I ( xA xB)( v) 0 。

xA xB x( A B) 是永真式。

x( A

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

d

I 和 I 中赋v，若 I ( 任取解释值

D ，

I

I ( A

B)(v[ x / d ]) 1，因为x 不是 A 的自由变A)(v[ x/ d] ) I ( A)( v) 1， 元，所以 I (

x(A

B)

( A

xB)是永真式。

因此 I ( B)(v[ x/ d ] ) 1 ， I ( xB )(v) 1。这表明 13.A设1 是公式 (1) (2) 明证

A 的闭包， A2 是 x1

xnA，其中 Var ( A) { x1, , xn} 。证明：

A 是永真式当且仅当 A1是永真式； A 是可满足式当且仅当

(1)

（

A 是可满足式。 2

A 是永真式，则xA 是永真式。设A 是永真式。任取解

）首先证明：若

I 和 I 中赋v，任取 d DI ，因为v[ x/ d] 值，所以 I ( A)(v[ x / d ]) 1， 释值也是 I 中赋

I ( xA v 。 xA是永真式。 若 A 是永真式，则xnA 是永真式， ?

)( ) 1

永真式。 （

，

x1 xn A

是

x1 ）因为

A ）因为

xn A

x1

A

是永真式，所以若

x1 xn AA 是永真式。是永真式，则

(2) （ 足满

xn AI 和 I 中赋v满I 和 v 是永真式，所以若解释值足 A，则

x

1

x A

。

n

（

I 和 ） 若 解释

I

v满中赋值足

x x A

1

n

，则有

d1, ,d

n

使 得

D

I

I( A v[ x1 d1 xn dn ，I 和 I 中赋值v[ x1 / d1, ,xn / dn]满足 A。 )( / , , / ]) 1

14. 判断以下等值式是否成立，并说明理由。 (1) (2) (3) (4) (5) (6)

x( P(x) x( P(x) xP( x) x xP (x) x( P(x) x( P(x)

Q( x)) Q( x)) P(x)

xP( x) yQ( y)) yQ( y))

xP( x) xP( x)

xQ( x) xQ( x)

xP( x) xP (x)

yQ( y) yQ( y)