谓词逻辑合式公式及解释
重点：(1) 掌握合式公式的概念，
(2) 掌握量词的辖域，约束变项，自由变项的概念，
(3) 掌握逻辑有效式，矛盾式，可满足式的概念。
1、字母表。
(1)个体常项： 
；
(2)个体变项： 
；
(3)函数符号： 
；
(4)谓词符号： 
；
(5)量词符号： 
；
(6)联结词符： 
；
(7)括号和逗号：( ，)， ， 。
2、项的递归定义。
(1) 个体常项和变项是项。
(2) 若 
是任意 
元函数， 
是项，则 
是项。
(3) 只有有限次地使用(1)、(2)生成的符号串才是项。
其中 
是字母表中没有的符号，这里表示任意函数。
例如： 
等都是项。
3、原子公式。
设 
是任意的 元谓词， 是项，则称 
为原子公式。
4、合式公式的递归定义。
(1) 原子公式是合式公式；
(2) 若 
是合式公式，则 
也是合式公式；
(3) 若 
是合式公式，则 
也是合式公式；
(4) 若 是合式公式，则 
也是合式公式；
(5) 只有有限次地应用(1)－(4)构成的符号串才是合式公式(也称谓词公式)，简称公式。
5、约束出现，自由出现。
在合式公式 中，称 
为指导变项，称 为相应量词的辖域，在辖域中，
的所有出项称为约束出现(即 受相应量词指导变项的约束)， 中不是约束出现的其它变项的出现称为自由出现。
例1、指出下列各合式公式中的指导变项，量词的辖域，个体变项的自由出现和约束出现。
(1) 
解： 
中， 
为指导变项， 
的辖域为 
，其中 是约束出现， 是自由出现， 中， 是指导变项， 
的辖域为 
， 
都是约束出现。
(2) 
解： 
中， 为指导变项， 的辖域为 
， 是约束出现的， 
中， 都是自由出现的，因此，在整个公式中， 是约束出现，又是自由出现， 是自由出现。
(3) 
解：在
中， 为指导变项，量词的辖域为 
， 约束出现， 
自由出现，在 
中， 为指导变项， 的辖域为 ， 约束出现， 自由出现，在整个公式中， 是约束出现， 是约束出现，又是自由出现， 是自由出现。
闭式(封闭的合式公式)——无自由出现的个体变项的合式公式。
换名规则——将量词辖域中的约束变项及对应的指导变项同时更换成公式中未出现的变项，公式的其余部分不变。
例如： 换成 
代替规则——将公式中的自由变项(所有出现)更换成公式中未出现的变项。
例如：
换成 
对公式中各种变项(个体变项，函数变项，谓词变项)，指定特殊的常项去代替，就构成了公式的一个解释。
1、解释 
由以下4部分组成：
(1) 非空个体域 
；
(2) 中一部分特定元素；
(3) 上一些特定的函数；
(4) 上一些特定的谓词。
例2、给定解释 
如下：
1) 个体域为自然数集合 
2) 中特定元素 
3) 上特定函数 
4) 上特定谓词 
为 
。
在解释 下，下面哪些公式为真？哪些公式为假？
(1) 
；
(2) 
；
(3) 
；
(4) 
；
(5) 
解：在解释
下，公式分别化为：
(1) 
真值为0
(2) 
真值为1
(3) 
真值为1
(4) 
真值为0
(5) 
真值不确定(不是命题)
2、逻辑有效式(永真式)，矛盾式(永假式)，可满足式。
逻辑有效式——在任何解释下都取值为真的合式公式。
矛盾式——在任何解释下都取值为假的合式公式。
可满足式——至少存在一种解释使其取值为真的合式公式。
对命题公式，有多种方法可判断其类型，可是对逻辑公式，却没有一种可行的办法。只有某些特殊的公式可判断。
还有一些公式，可以利用命题公式的结论。
代换实例——设
是含 个命题变项 
的命题公式，将 个谓词 
取代 所得的谓词公式称为 的代换实例。
例如： 
等都是 
的代换实例。
注意到命题公式中重言式，矛盾式的代换实例在谓词公式中仍是重言式(逻辑有效式)，矛盾式。
例3、判断下列公式中哪些是逻辑有效式，哪些是矛盾式。
(1) 
；
(2) 
；
(3) 
；
(4) 
；
解：(1) 设 是任意的解释，设其个体域为 。若存在 
， 
为假，则 
为假，从而 为真；若对任意 
，都有 为真，则 
均为真，所以 为真。由以上，原公式是逻辑有效的。
(2) 原公式是命题公式 
的代换实例，而且 
(重言式)，所以原公式是逻辑有效的。
(3) 原公式是命题公式 
的代换实例，而且 
(重言式)，所以原公式是逻辑有效的。
(4) 原公式是命题公式 
的代换实例，而且 
(矛盾式)，所以原公式是矛盾式。