2024年7月15日发(作者：哈鸿远)
量词的辖域
定义:量词的辖域是邻接量词之后的最小子公式，故除非辖域是个原子公式，否
则应在该子公式的两端有括号。
例：XP(X)→Q(X)
X的辖域是P(X)
X(P(X,Y)→Q(X，Y) ) P(Y,Z)
X的辖域是P(X，Y)→Q(X，Y)
有限个体域上消去量词
例15: 个体域D={a,b,c}, 则消去下面公式中的量词xyF(x,y)
x (F(x,a)∧F(x,b)∧F(x,c))
(F(a,a)∧F(a,b)∧F(a,c))∨ (F(b,a)∧F(b,b)∧F(b,c))∨ (F(c,a)∧F(c,b)∧F(c,c))
例16：设个体域D={a,b}，消去下面各公式中的量词：
(1) ∀x∃y(F(x) G(y)) ∀x(F(x) ∃yG(y))
∃xF(x) ∃yG(y) (F(a)∨F(b)) (G(a)∨G(b))
(2) ∀x∃y(F(x,y) G(x,y))
∀x((F(x,a) G(x,a))∨(F(x,b)G(x,b))
((F(a,a) G(a,a))∨(F(a,b)G(a,b)))∧
((F(b,a) G(b,a))∨(F(b,b)G(b,b)))
注：(1)中量词辖域可以缩小，先缩小量词辖域，再消量词，演算简单；但在(2)
中，因为全称量词和存在量词均约束F与G中个体变量，因而它们的辖域不能
缩小，消去量词后的公式也不易化的更简单。
例17 将下面命题用两种形式符号化, 并证明两者等值:
(1) 没有不犯错误的人
解 令
F
(
x
)：
x
是人，
G
(
x
)：
x
犯错误.
x
(
F
(
x
)
G
(
x
)) 或
x
(
F
(
x
)
G
(
x
x
(
F
(
x
)
G
(
x
))
x
(
F
(
x
)
G
(
x
)) 量词否定等值式
x
(
F
(
x
)
G
(
x
)) 置换
x
(
F
(
x
)
G
(
x
)) 置换
(2) 不是所有的人都爱看电影
解 令
F
(
x
)：
x
是人，
G
(
x
)：爱看电影.
x
(
F
(
x
)
G
(
x
)) 或
x
(
F
(
x
)
G
(
x
))
x
(
F
(
x
)
G
(
x
))
x
(
F
(
x
)
G
(
x
)) 量词否定等值式
x
(
F
(
x
)
G
(
x
)) 置换
x
(
F
(
x
)
G
(
x
)) 置换
例18 求下列公式的前束范式
(1)
x
(
M
(
x
)
F
(
x
))
解
x
(
M
(
x
)
F
(
x
))
x
(
M
(
x
)
F
(
x
)) （量词否定等值式）
x
(
M
(
x
)
F
(
x
))
后两步结果都是前束范式，说明公式的前束范式不惟一.
(2)
xF
(
x
)
xG
(
x
)
解
xF
(
x
)
xG
(
x
)
xF
(
x
)
x
G
(
x
) （量词否定等值式）
x
(
F
(
x
)
G
(
x
)) （量词分配等值式）
或
xF
(
x
)
xG
(
x
)
xF
(
x
)
x
G
(
x
) 量词否定等值式
xF
(
x
)
y
G
(
y
) 换名规则
x
y
(
F
(
x
)
G
(
y
)) 辖域收缩扩张规则
(3)
xF
(
x
)
y
(
G
(
x
,
y
)
H
(
y
))
解
xF
(
x
)
y
(
G
(
x
,
y
)
H
(
y
))
zF
(
z
)
y
(
G
(
x
,
y
)
H
(
y
)) 换名规则
z
y
(
F
(
z
)(
G
(
x
,
y
)
H
(
y
))) 辖域收缩扩张规则
或
xF
(
x
)
y
(
G
(
z
,
y
)
H
(
y
)) 代替规则
x
y
(
F
(
x
)(
G
(
z
,
y
)
H
(
y
)))
推理定理
第一组 命题逻辑推理定理的代换实例
如,
xF
(
x
)
yG
(
y
)
xF
(
x
)
第二组 基本等值式生成的推理定理
如,
xF
(
x
)
xF
(
x
),
xF
(
x
)
xF
(
x
)
xF
(
x
)
x
F
(
x
),
x
F
(
x
)
xF
(
x
)
第三组 其他常用推理定律
(1)
xA
(
x
)
xB
(
x
)
x
(
A
(
x
)
B
(
x
))
(2)
x
(
A
(
x
)
B
(
x
))
xA
(
x
)
xB
(
x
)
(3)
x
(
A
(
x
)
B
(
x
))
xA
(
x
)
xB
(
x
)
(4)
x
(
A
(
x
)
B
(
x
))
xA
(
x
)
xB
(
x
)
一个公式如果它的所有量词均非否定的出现在公式的最前面，且它们
的辖域一直延伸到公式的末尾，此种形式的公式就叫前束范式。
定义 设
A
为一个一阶逻辑公式，若
A
具有如下形式
Q
1
x
1
Q
2
x
2
„
Q
k
x
k
B
则称
A
为前束范式，其中
Q
i
(1
i
k
)为或，
B
为不含量词的公式.
例如，
x
(
F
(
x
)
G
(
x
))
x
y
(
F
(
x
)(
G
(
y
)
H
(
x
,
y
))) 是前束范式
而
x
(
F
(
x
)
G
(
x
))
x
(
F
(
x
)
y
(
G
(
y
)
H
(
x
,
y
))) 不是前束范式
注: 任何公式的前束范式都是存在的，但一般说来并不是唯一的。
四条重要的推理规则
A.全称量词消去规则，简记为UI
B.存在量词消去规则，简记为EI
C.存在量词引入规则，简记为EG
2024年7月15日发(作者：哈鸿远)
量词的辖域
定义:量词的辖域是邻接量词之后的最小子公式，故除非辖域是个原子公式，否
则应在该子公式的两端有括号。
例：XP(X)→Q(X)
X的辖域是P(X)
X(P(X,Y)→Q(X，Y) ) P(Y,Z)
X的辖域是P(X，Y)→Q(X，Y)
有限个体域上消去量词
例15: 个体域D={a,b,c}, 则消去下面公式中的量词xyF(x,y)
x (F(x,a)∧F(x,b)∧F(x,c))
(F(a,a)∧F(a,b)∧F(a,c))∨ (F(b,a)∧F(b,b)∧F(b,c))∨ (F(c,a)∧F(c,b)∧F(c,c))
例16：设个体域D={a,b}，消去下面各公式中的量词：
(1) ∀x∃y(F(x) G(y)) ∀x(F(x) ∃yG(y))
∃xF(x) ∃yG(y) (F(a)∨F(b)) (G(a)∨G(b))
(2) ∀x∃y(F(x,y) G(x,y))
∀x((F(x,a) G(x,a))∨(F(x,b)G(x,b))
((F(a,a) G(a,a))∨(F(a,b)G(a,b)))∧
((F(b,a) G(b,a))∨(F(b,b)G(b,b)))
注：(1)中量词辖域可以缩小，先缩小量词辖域，再消量词，演算简单；但在(2)
中，因为全称量词和存在量词均约束F与G中个体变量，因而它们的辖域不能
缩小，消去量词后的公式也不易化的更简单。
例17 将下面命题用两种形式符号化, 并证明两者等值:
(1) 没有不犯错误的人
解 令
F
(
x
)：
x
是人，
G
(
x
)：
x
犯错误.
x
(
F
(
x
)
G
(
x
)) 或
x
(
F
(
x
)
G
(
x
x
(
F
(
x
)
G
(
x
))
x
(
F
(
x
)
G
(
x
)) 量词否定等值式
x
(
F
(
x
)
G
(
x
)) 置换
x
(
F
(
x
)
G
(
x
)) 置换
(2) 不是所有的人都爱看电影
解 令
F
(
x
)：
x
是人，
G
(
x
)：爱看电影.
x
(
F
(
x
)
G
(
x
)) 或
x
(
F
(
x
)
G
(
x
))
x
(
F
(
x
)
G
(
x
))
x
(
F
(
x
)
G
(
x
)) 量词否定等值式
x
(
F
(
x
)
G
(
x
)) 置换
x
(
F
(
x
)
G
(
x
)) 置换
例18 求下列公式的前束范式
(1)
x
(
M
(
x
)
F
(
x
))
解
x
(
M
(
x
)
F
(
x
))
x
(
M
(
x
)
F
(
x
)) （量词否定等值式）
x
(
M
(
x
)
F
(
x
))
后两步结果都是前束范式，说明公式的前束范式不惟一.
(2)
xF
(
x
)
xG
(
x
)
解
xF
(
x
)
xG
(
x
)
xF
(
x
)
x
G
(
x
) （量词否定等值式）
x
(
F
(
x
)
G
(
x
)) （量词分配等值式）
或
xF
(
x
)
xG
(
x
)
xF
(
x
)
x
G
(
x
) 量词否定等值式
xF
(
x
)
y
G
(
y
) 换名规则
x
y
(
F
(
x
)
G
(
y
)) 辖域收缩扩张规则
(3)
xF
(
x
)
y
(
G
(
x
,
y
)
H
(
y
))
解
xF
(
x
)
y
(
G
(
x
,
y
)
H
(
y
))
zF
(
z
)
y
(
G
(
x
,
y
)
H
(
y
)) 换名规则
z
y
(
F
(
z
)(
G
(
x
,
y
)
H
(
y
))) 辖域收缩扩张规则
或
xF
(
x
)
y
(
G
(
z
,
y
)
H
(
y
)) 代替规则
x
y
(
F
(
x
)(
G
(
z
,
y
)
H
(
y
)))
推理定理
第一组 命题逻辑推理定理的代换实例
如,
xF
(
x
)
yG
(
y
)
xF
(
x
)
第二组 基本等值式生成的推理定理
如,
xF
(
x
)
xF
(
x
),
xF
(
x
)
xF
(
x
)
xF
(
x
)
x
F
(
x
),
x
F
(
x
)
xF
(
x
)
第三组 其他常用推理定律
(1)
xA
(
x
)
xB
(
x
)
x
(
A
(
x
)
B
(
x
))
(2)
x
(
A
(
x
)
B
(
x
))
xA
(
x
)
xB
(
x
)
(3)
x
(
A
(
x
)
B
(
x
))
xA
(
x
)
xB
(
x
)
(4)
x
(
A
(
x
)
B
(
x
))
xA
(
x
)
xB
(
x
)
一个公式如果它的所有量词均非否定的出现在公式的最前面，且它们
的辖域一直延伸到公式的末尾，此种形式的公式就叫前束范式。
定义 设
A
为一个一阶逻辑公式，若
A
具有如下形式
Q
1
x
1
Q
2
x
2
„
Q
k
x
k
B
则称
A
为前束范式，其中
Q
i
(1
i
k
)为或，
B
为不含量词的公式.
例如，
x
(
F
(
x
)
G
(
x
))
x
y
(
F
(
x
)(
G
(
y
)
H
(
x
,
y
))) 是前束范式
而
x
(
F
(
x
)
G
(
x
))
x
(
F
(
x
)
y
(
G
(
y
)
H
(
x
,
y
))) 不是前束范式
注: 任何公式的前束范式都是存在的，但一般说来并不是唯一的。
四条重要的推理规则
A.全称量词消去规则，简记为UI
B.存在量词消去规则，简记为EI
C.存在量词引入规则，简记为EG