发布时间 : 星期三 文章新版离散数学答案（尹宝林版）第二章习题解答课件 doc - 图文更新完毕开始阅读639ac59e876fb84ae45c3b3567ec102de3bddf29
证 明 (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)} 。