文档介绍：谓词公式与翻译
一、项和原子公式
定义1、项的定义
(1) 个体变元是项；
(2)个体常元是项；
(3) f是n元运算符号，t1， t2，… tn是项，
则f ( t1， t2，… tn )是项
(4) 当且仅当有限次地使用以上三条得到的
是项。
定义2、原子公式定义
P是n元谓词，t1， t2，… tn是项，
称P（ t1， t2，… tn ）为原子公式
定义3 谓词公式，由如下递归定义构成：
(1) 原子公式是谓词公式；
(2) 若 A 是谓词公式，则﹁A 也是谓词公式；
(3) 若 A 和 B 都是谓词公式，则 (A∧B), (A∨B), (AB), (AB) 都是谓词公式；
(4) 若 A 是谓词公式，x 是任何个体变元，则 xA 和 xA 都是谓词公式；
(5) 当且仅当有限次地应用规则 (1), (2), (3), (4)所得到的公式是谓词公式。
二、一阶公式（谓词公式）
定义4 对于谓词公式 xP(x) 或 xP(x) 来说，x 称为量词 x 或量词 x 的指导变元或作用变元。P(x)称为相应量词的辖域。
定义5 在一个谓词公式中，若 x 出现于 x 或 x的辖域中则称 x 的出现是约束的；若 x 的出现不是约束的，则称是自由的。
( x) A( x ) 或 ( x) A( x )
指导变元
辖域
约束变元
例如 xy(A(x,y)∧B(y,z))∧xA(x,y)
注：1）一个变元在同一个公式中:
既可以为约束出现，又为自由出现。
2）公式 xP(x)、yP(y) 和 zP(z)
在相同的个体域中具有相同的意义
可将谓词公式中的约束变元更改名称符号，这一过程称为约束变元换名。约束变元换名要遵循一定的规则：
(1) 换名时，更改的对象是量词中的指导变元，以及该量词辖域中所出现的所有该变元，其余不变；
(2) 换名时换为公式中未出现的变元名称。
例如 x(P(x)R(x,y) ∧Q(x,y))
自由变元的代入规则:
(1) 对公式中出现该自由变元的每一处都
用新的个体变元替换.
(2) 新变元与原公式中所有变元名称不同。
如： x(A(y)∧B(x,y))
注：当个体域中元素的个数是有限时，对量词辖域中的约束变元的所有可能的取代是可枚举的，即：
若设个体域为 {a1, a2, …, an} 则：
(1) (x)A(x)A(a1)∧A(a2)∧…∧A(an)
(2) (x)A(x)A(a1)∨A(a2)∨…∨A(an )
定义6 闭式:不含自由变元的公式.
否则称为非闭式
谓词公式的真值与那些因素有关?谓词公式的真值能否像命题逻辑那样总可由真值表给出?
例
xy (P(x) Q( f(x,a), y ,z )) 的真值
给出个体域
指定谓词
指定运算具体含义和个体
指定自由变元
三、谓词公式的解释