I ( f I I f I I f I(1) PP, 1) P I 1, (1) ) (1, (2)) (( f I PI f I PI f I III(2 ,1) 1 1 0 0 ( PP P
1, 2) (1, 1)I
I( PPI
(2)
I ( x yP( y, x))( v) I ( yP( y, x))(v[ x / 1])
I ( yP( y, x))(v[ x / 2])
(I (P( y, x))( v[ x/ 1][ y /1]) I (P( y, x))( v[ x /1][ y / 2]))
(I (P( y, x))( v[ x/ 2][ y / 1])
I (P(y, x))( v[ x / 2][ y / 2]))
(PI
PI
PI PI (2, 2))
(1, 1)
(2,1)) ( (1 , 2)
(1 0) (1 0) 1
(3) I ( x y(P(x, y)
P( f ( x), f ( y))))( v)
(PI
PI f I f I PI PI f I f I ( 2))) (1, 1)
( (1) , (1))) ( (1 , 2) ( (1) , (PI
PI f I f I PI PI f I f I ( 2))) (2,1)
( (2), (1))) ( (2, 2) ( ( 2),
( PI
PI
PI
PI
PI PI PI
P I(1, 1)
(2, 2)) ( (1, 2)
(2 ,1)) ( (2 ,1) (1, 2)) (
(2, 2)
(1 0) (1 0) (0 1) (0 1) 0 0 1 1 0
7. 给定解释
I 如下：
I
，
PI (a , b) PI (b , a) 0
I
DI { a b ， P (a, a) P (b, b) 1
, }
判断
I 是不是以下语句的模型。
(1) x yP( x, y) (2) x yP( x, y) (3) x yP( x, y) (4) x y P( x, y) (5) x y( P( x, y) P( y, x))
(6)
xP( x, x)
解 (1) I ( x yP( x, y))
(PI a a PI a b PI b a PI b b (1 0) (0 1) 1
( , ) ( , )) ( ( , ) ( , ))
(2) I ( x yP( x, y))
PI
I I I
1 0 0 1 0
(a,a) P (a,b) P (b, a) P (b, b)
(3) I ( x yP( x, y))
(PI a a PI a b PI b a PI b b (1 0) (0 1) 0 ( , ) ( , )) ( ( , ) ( , ))
(1, 1))
(4) I ( x y P( x, y))
PI
(a, a)
I I I
0 1 1 0 1
P ( a,b) P (b,a) P (b, b)
(5) I ( x y(P(x, y)
I(P
P( y, x)))
IP
a a ( , ) b a ( , )
1) (0
IP
a a
( , )) ( a b
( , )) (
a b ( , ) b b ( , )
IP
b a ( , )) b b ( , ))
I(P IP IP IP
(1
(6) 9.
0) (0
IP(a, a)
0) (1 1) 1
I ( xP(x, x))
IP(b, b)
1 1 1
写出一个语句
A，使得 A 有模型，并且 A 的每个模型的论域至少有三个元素。
x P( x, x) P (a,b) P (b,c) P(c,a)。给定解释 I 如下。
解
A 为 语句 D
I
为自然数集合，
PI (x, y) 1当且仅当 x
y ， aI
1， bI 2， cI
3
则 I
A 的模型， A 有模型。是
A
I，则 PI (aI , bI ) PI (bI , cI ) PI (cI , aI ) 1 ，又因为
I 中三个不同元素，论域
任取满足语句
的解释
I
( x P(x, x)) 1
元素。
10. 写出一个语句 解
语句 A 为
III，所以 a，b，c是论域 D
DI 中至少有三个
A，使得 A 有模型，并且 A 的每个模型的论域有无穷多个元素。
x y( P(x, y) P( y, z)
P( x, z))
x yP( x, y) 。给定解
x P( x, x)
释 I 如下。
D
I
为自然数集合，
IP
( x, y) 1
当且仅当 x y
则 I
A 的模型， A 有模型。是
A
DI ，因为 I ( x yP( x, y)) 1 ，所以有 d2 DI 使得
d 。因为 I ( x yP( x, y)) 1，所以
2
任取满足语句 PI
d1 的解释 I，取
(d1 , d2
) 1 DI
，又因为 I ( x P( x, x)) 1，故 d1
I
有 d3
使 得 P
(d2 , d3) 1
， 又 因 为 I ( x P( x, x)) 1 ， 故 d3 d2 。 因 为
I
I ( (
( x y P(x, y) P y, z)
P ，所以
P( x, z))) 1
(d1 , d3 ) 1
，故 d3
d 。因此， d1 ，
1
d
2
，d3 是论域中的三个不同元素。
这个过程可以不断进行下去，
d1 , d2 , d3 , 得到
因此，
论域 DI 中必然有无穷多个元素。
11. 判断以下公式是不是永真式、永假式、可满足式，并说明理由。
(1) xP (x) xQ( x) x( P(x) Q( x)) (2) xP (x)
xQ( x)
x( P(x) Q( x)) (3) x(P( x) Q( x)) xP( x)
xQ( x)
(4)
xP(x, x)
x yP( x, y) (5) ( xP( x) xQ ( x)) x( P( x) Q( x)) (6) ( xP( x) xQ(x )) x( P(x) Q (x)) (7) x(P( x)
Q(x)) ( xP( x) xQ( x))
解
(1)
xP( x)
xQ( x)
x( P(x) Q( x)) 是 永 真 式 。 若 解 释 I I ( xP( x) xQ (x)) 1 ，则 I ( xP( x)) 1或 I ( xQ( x)) 1。
① 若 I ( xP (x)) 1，则存在 d DI 使得 PI (d) 1， PI (d) QI (d) 1。 ② 若 I ( xQ(x )) 1，则存在 d
DI 使得 QI (d) 1， PI (d) QI (d) 1。
因此， I ( x( P( x) Q( x))) 1。 (2)
xP (x) xQ( x) x( P( x) Q(x)) 是非永真的可满足式。给定解释
I 如下。
I
， Q
I (d) 1
DI
{d} ， P (d) 1
则 I ( xP(x)
xQ (x) x(P(x) Q (x))) 1。
给定解释 I 如下。
DI
，P
I
(a) 1， PI (b) 0， QI (a) 0， QI (b) 1
{a, b}
则 I ( xP( x) xQ( x) x(P( x) Q( x))) 0 。 (3)
x( P(x) Q( x))
xP (x)
xQ (x) 是非永真的可满足式。给定解释
I 如下。I
，
QI (d) 1
DI
， P (d) 1
{d}
则 I ( x( P( x) Q( x)) xP (x) xQ(x )) 1。
给定解释 I 如下。
DI
，P
I
(a) 1， PI (b) 0， QI (a) 0， QI (b) 1
{a, b}
使 得
