(F(x,y,z)y(G(x,y)H(x,y,z))). y中的y是指导变元, 辖域为(G(x,y)H(x,y,z)). x的3次出
现都是约束出现, y的第一次出现是自由出现, 后2次是约束出现, z的2次出现都是自由出现。
定义 若公式A中不含自由出现的个体变项，则称A为封闭的公式，简称闭式. 例如，
xy(F(x)G(y)H(x,y)) 为闭式，而x(F(x)
G(x,y)) 不是闭式。
定义 设L 是L生成的一阶语言, L 的解释I由4部分组成： (a) 非空个体域 DI .
(b) 对每一个个体常项符号aL, 有一个aDI, 称a为a在I中的解释.
n (c) 对每一个n元函数符号fL, 有一个DI上的n元函数f:DI?DI, 称f为f在I中
的解释.
(d) 对每一个n元谓词符号FL, 有一个DI上的n元谓词常项F,称F为F在I中的解释.
设公式A, 取个体域DI , 把A中的个体常项符号a、函数符号f、谓词符号F分别替换成它们在I中的解释a、f、F, 称所得到的公式A为A在I下的解释, 或A在I下被解释成A.
例6 给定解释 I 如下： (a) 个体域 D=R； (b) a?0；
(c)f(x,y)?x?y,g(x,y)?x?y； (d) F(x,y):x?y 写出下列公式在I下的解释, 并指出它的真值.
(1)
xF(f(x,a),g(x,a))
x(x+0=x0) 真
(2)
xy(F(f(x,y),g(x,y))F(x,y)) xy(x+y=xyx=y) 假
(3)
xF(g(x,y),a)
x(xy=0) 真值不定, 不是命题
2.公式的类型
定理 闭式在任何解释下都是命题.
注意: 不是闭式的公式在解释下可能是命题, 也可能不是命题. 定义 若公式A在任何解释下均为真, 则称A为永真式(逻辑有效式).
若A在任何解释下均为假, 则称A为矛盾式(永假式). 若至少有一个解释使A为真, 则称A为可满足式.
几点说明：
永真式为可满足式，但反之不真；
判断公式是否是可满足的(永真式, 矛盾式)是不可判定的。
定义 设A0是含命题变项 p1, p2, …, pn的命题公式，A1, A2, …, An是n个谓词公式，用Ai (1
i
n) 处处代替A0中的pi，所得公式A称为A0的代换实例.
G(x), xF(x)
yG(y)等都是pq的代换实例.
例如， F(x)
定理 重言式的代换实例都是永真式，矛盾式的代换实例都是矛盾式.
例7 判断下列公式中，哪些是永真式，哪些是矛盾式 (1)
xF(x)
(xyG(x,y)
xF(x))
重言式 p(qp) 的代换实例，故为永真式. (2)
(xF(x)
yG(y))
yG(y)
矛盾式 (3)
(pq)q 的代换实例，故为永假式. G(x))
x(F(x)
解释I1: 个体域N, F(x):x>5, G(x): x>4, 公式为真 解释I2: 个体域N, F(x):x<5, G(x):x<4, 公式为假 结论: 非永真式的可满足式
第四章一阶逻辑基本概念
