文档介绍：主要内容
一阶逻辑等值式与基本的等值式
置换规则、换名规则、代替规则
前束范式
自然推理系统NL 及其推理规则
第五章一阶逻辑等值演算与推理
1
一阶逻辑等值式与置换规则
设A, B是两个谓词公式, 如果AB是永真式, 则称A
与B等值, 记作AB, 并称AB是等值式
基本等值式
第一组命题逻辑中16组基本等值式的代换实例
例如,xF(x)xF(x),
xF(x)yG(y) xF(x)yG(y) 等
第二组
(1) 消去量词等值式
设D ={a1, a2, …, an}
①xA(x)  A(a1)A(a2)…A(an)
②xA(x)  A(a1)A(a2)…A(an)
2
基本等值式
(2) 量词否定等值式
①xA(x) xA(x)
②xA(x) xA(x)
(3) 量词辖域收缩与扩张等值式.
A(x) 是含 x 自由出现的公式,B 中不含 x 的自由出现
关于全称量词的:
①x(A(x)B) xA(x)B
②x(A(x)B) xA(x)B
③x(A(x)B) xA(x)B
④x(BA(x))  BxA(x)
3
基本等值式
关于存在量词的:
①x(A(x)B) xA(x)B
②x(A(x)B) xA(x)B
③x(A(x)B) xA(x)B
④x(BA(x))  BxA(x)
(4) 量词分配等值式
①x(A(x)B(x)) xA(x)xB(x)
②x(A(x)B(x)) xA(x)xB(x)
注意:对,对无分配律
4
置换规则、换名规则、代替规则
1. 置换规则
设(A)是含A的公式, 那么, 若AB, 则(A)(B).
2. 换名规则
设A为一公式,将A中某量词辖域中个体变项的所有约束
出现及相应的指导变元换成该量词辖域中未曾出现过的个
体变项符号,其余部分不变,设所得公式为A,则AA.
3. 代替规则
设A为一公式,将A中某个个体变项的所有自由出现用A中
未曾出现过的个体变项符号代替,其余部分不变,设所得
公式为A,则AA.
5
实例
例1 将下面命题用两种形式符号化, 并证明两者等值:
(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)) 置换
6
实例
(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)) 置换
7
实例
例2 将公式化成等值的不含既有约束出现、又有自由出现
的个体变项: x(F(x,y,z)yG(x,y,z))
解x(F(x,y,z)yG(x,y,z))
x(F(x,y,z)tG(x,t,z)) 换名规则
xt(F(x,y,z)G(x,t,z)) 辖域扩张等值式
或者
x(F(x,y,z)yG(x,y,z))
x(F(x,u,z)yG(x,y,z)) 代替规则
xy(F(x,u,z)G(x,y,z)) 辖域扩张等值式
8
实例
例3 设个体域D={a,b,c}, 消去下述公式中的量词:
(1) xy(F(x)G(y))
解xy(F(x)G(y))
(y(F(a)G(y)))(y(F(b)G(y)))(y(F(c)G(y)))
((F(a)G(a))(F(a)G(b))(F(a)G(c)))
((F(b)G(a))(F(b)G(b))(F(b)G(c)))
((F(c)G(a))(F(c)G(b))(F(c)G(c)))
9
实例
解法二
xy(F(x)G(y))
x(F(x)yG(y)) 辖域缩小等值式
x(F(x)G(a)G(b)G(c))
(F(a)G(a)G(b)G(c))
(F(b)G(a)G(b)G(c))
(F(c)G(a)G(b)G(c))
例3 设个体域D={a,b,c},