从广义上讲，数理逻辑属于形式逻辑，是研究演绎推理的一门学科，又称为符号逻辑、理论逻辑，它既是数学的一个分支，也是逻辑学的一个分支。是用数学方法研究逻辑或形式逻辑的学科。其研究对象是对证明和计算这两个直观概念进行符号化以后的形式系统。
数理逻辑是数学基础的一个不可缺少的组成部分，它主要是对思维的形式结构和规律进行研究的类似于语法的一门工具性学科。思维的形式结构包括了概念、判断和推理之间的结构和联系，根据概念进行判断；由判断进行推理，从而得出新的结论。
数理逻辑是用数学方法来研究推理的规律，其主要内容包含逻辑演算、集合论、证明论、模型论、递归函数论五大部分。本篇仅介绍计算机科学领域中所需的数理逻辑知识：命题逻辑和谓词逻辑，讨论它的基本概念。

第一章：命题逻辑

1.1.命题及其表示

1.命题的定义：能表达判断的陈述句。

2.命题的真值：对某个可以判断的陈述句的肯定或否定的回答，也即是一个可以判断的陈述句总是具有一个“值”，称为该陈述句的真值。
真值可以是“真”或“假”两种，分别用符号T和F表示，也可以用1和0表示。

3.命题的分类：
（1）原子命题：不能分解为更简单的陈述句的命题。
（2）复合命题：由联结词、标点符号和原子命题复合而成的命题。

4.命题的表示：在命题逻辑中，一般可以使用大写字母A，B，…，P，Q，…或用带下标的大写字母A1或用数字[6]等符号来表示一个命题，表示命题的符号也称为命题标识符。
例如
A：我是大学生。
[6]：我是大学生。
A1：我是大学生
4.命题常量：一个命题标识符若表示确定的命题，就称为命题常量。
5.命题变元：若只表示任意命题的位置标志，就称为命题变元。
6.原子变元：若命题变元表示原子命题时，该变元称为原子变元。
7.指派：用特定命题取代某个命题变元P的过程称为对命题变元P进行指派。

1.2.联结词

在自然语言中，常用“或”、“与”、“但是”，“如果…那么…”等联结词将简单陈述句联结起来组合成较为复杂的语句。
在数理逻辑中，通过联结词将原子命题联结起来就组合成了复合命题，联结词是复合命题中的重要组成部分，为了便于书写和进行推演，必须对联结词作出明确规定并符号化。

1.2.1 否定

1.定义 ：设P为一命题，P的否定命题是一个新的命题，记为¬P，“¬”为否定联结词，若P为T，则¬P为F，若P为F，则¬P为T。
2.真值表：

否定联结词仅修改了命题的内容，是一元联结词，相当于“非”、“不”、“否”等词。命题的否定可以看成是非运算符作用在命题上的结果，非运算符从一个已有的命题构造出一个新命题。

1.2.2 合取

1.定义：若P和Q是任意的两个命题，则P和Q的合取命题是一个复合命题，记作P∧Q。“∧”为合取联结词，当且仅当P和Q同时为T时，P∧Q为T，在其他情况下，P∧Q的真值都是F。
2.真值表：

1.2.3 析取

1.定义：若P和Q是任意的两个命题，则P和Q的析取命题是一个复合命题，记作P∨Q。“∨”为合取联结词，当且仅当P和Q同时为F时，P∨Q为F，在其他情况下，P∨Q的真值都是T。
2.真值表

“析取”是个二元联结词，相当于自然语言中的“或”，但又与“或”不完全相同，因为“或”可以是“可兼或”，还可以是“排斥或”，还有些“或”只表示大约的意思，并不是联结词。

1.2.4 条件

1.定义：若P和Q是任意的两个命题，则P和Q的条件命题是一个复合命题，记作P→Q，读作“若P，则Q”或“如果P，那么Q”。
我们称P为前件，Q为后件，“→”为条件联结词，当且仅当P的真值为T而Q的真值为F时，P→Q为F，在其他情况下，P→_Q的真值都是_T。
2.真值表

“条件”是二元联结词，相当于自然语言中的“如果…那么…”或“若…则…”，但又与这些表示因果关系的联结词不完全相同，因为对条件P→Q命题来说，只要P，Q是命题，有确定真值，则P→Q就是复合命题，P和Q之间不一定具有自然语言里的因果关系。
另外，自然语言中的“如果…那么…”句型，若前提是假的，结论无论真假，整个语句是无法判断其意义，而在数理逻辑中，将这种情况规定为“善意的推定”，即当条件命题的前件为假时，条件的后件无论真假 ，条件命题的真值都是真的。

1.2.5 双条件

1.定义：若P和Q是任意的两个命题，则P和Q的双条件命题是一个复合命题，记作P«Q，读作“P当且仅当Q”，当P和Q的真值相同时，P«Q的真值为T，否则，P«Q的真值为F。
2.真值表：

1.3.命题公式与翻译

1.3.1 命题公式

任何语句都可以通过原子命题或原子命题和联结词构成的合法符号串表示，若合法符号串中是原子命题，则该符号串就是命题，若合法符号串中是原子命题变元，则该符号串就是命题公式。
1.定义：命题公式 也叫命题演算的合式公式，可以按以下规则形成：
（1）单个命题变元本身是一个合式公式；
（2）若A是一个合式公式，则┐A也是一个合式公式；
（3）若A、B是合式公式，则(A∧B)、(A∨B)、(A→B)和(A«B)都是合式公式；
（4）有限次地使用（1）、（2）和（3）生成的公式是合式公式。

合式公式可以很简单，比如原子命题变元就是最简单的合式公式，称为原子合式公式，简称原子公式；合式公式也可以比较复杂， 当合式公式比较复杂时，常常使用很多圆括号，为了减少圆括号的使用量，可作以下约定： （1）规定联结词的优先级由高到低的次序为：┐、∧、∨、→、«； （2）相同的联结词按从左至右次序计算时，圆括号可省略； （3）否定联结词┐可以直接作用于命题变元前面； （4）最外层的圆括号可以省略。

1.3.2 翻译

1.定义将自然语言用联结词和符号变成合式公式的过程，称为翻译。
关于语句的翻译，下面给出几个例子。
例题2 她既美丽又大方。
解：设P：她美丽；Q：她大方。
则该语句可以翻译如为P∧Q。
例题3 张三和李四两人至少有一人要出差。
解：设P：张三出差；Q：李四出差。
则该语句可以翻译为P∨Q。

将命题的翻译总结为以下几步： ①将自然语言分解成一个个的原子命题， ②将原子命题符号化， ③分析原子命题之间的逻辑关系，选用合适的联 结词将符号化后的原子命题联结起来。

自然语言中的一些联结词，如，“与”“且”“或”“除非…则…”等在不同的语义环境中含义不同，有时会与数理逻辑中的联结词不能直接对应，这就需要在翻译时要具体问题具体分析，找到正确的联结词。
为了便于正确表达命题间的互相关系，有时也常常采用列出“真值表”的方法，进一步分析各原子命题，以此找到逻辑联结词，使原来的命题能够正确地用形式符号予以表达

小结 学习本节要深刻理解命题公式的定义，能够把用自然语言中的有些语句，翻译成数理逻辑中的符号形式。 合式公式：命题演算的合式公式(wff) 规定为： (1)单个命题变元本身是一个合式公式。 (2)如果A是合式公式，那么┐A是合式公式。 (3)如果A和B是合式公式，那么(A∧B)，(A∨B)，(A→B）和(A↔ B)都是合式公式。 (4)当且仅当能够有限次地应用(1)、(2)、(3)所得到的包含命题变元，联结词和括号的符号串是合式公式。

1.4.真值表与等价式

1.4.1 真值表

命题公式没有确定的真值，不是命题，但若对命题公式中的命题变元都指定一定的真值，则命题公式就变成了一个具有确切真值的命题。
定义1.4.1 解释 设是出现在合式公式A中的所有原子命题变元，指定一组真值，则这组真值称为合式公式A的一种解释，合式公式A中若有n个原子命题变元，则会有种解释。
定义1.4.2 真值表 在合式公式中，对原子命题变元进行的各种真值指派的组合，就确定了这个命题公式的各种解释，把这些解释汇列成表，就是合式公式的真值表。
任何一个合式公式都有相应的真值表。

合式公式中命题变元的个数决定了合式公式真值的取值数目，2个命题变元有4种真值指派，合式公式分别在这4种真值指派下取值，3个命题变元有8种真值指派，合式合式公式分别在这8种真值指派下取值，一般说来，n个命题变元有种真值组合，合式公式分别在这2n种真值指派下取值。

定义1.4.3 等价式 给定合式公式A和B，设是出现在A和B中的原子命题变元，若对的任意一种真值指派，A和B的真值都相同，则称A和B是等价式。记作

1.4.2 等价式

如下表中所示的合式公式┐(P∨Q)与┐P∧┐Q，在4种不同的指派下，这两个式子的真值始终相等。这样的式子称为等价式。

命题定律

对合律	┐┐P P	1
幂等律	P∨P P，P∧P P	2
结合律	(P∨Q）∨R P∨（Q∨R） (P∧Q）∧R P∧（Q∧R）	3
交换律	P∨Q Q∨P P∧Q Q∧P	4
分配律	P∨（Q∧R） （P∨Q）∧（P∨R） P∧（Q∨R） （P∧Q）∨（P∧R）	5
吸收律	P∨（P∧Q） P P∧（P∨Q） P	6
德摩根律	┐(P∨Q) ┐P∧┐Q ┐(P∧Q) ┐P∨┐Q	7
同一律	P∨F P，P∧T P	8
零律	P∨T T，P∧F F	9
否定律	P∨┐P T，P∧┐P F	10

证明两个命题等价，可以使用真值表，但真值表并不是唯一的方法，有了这些基本的命题定律，结合相关的定理，也可以证明两个命题等价。

定义 1.4.4 子公式 给定合式公式A和X，X是A的一部分，则称X是A的子公式。
定理 1.4.1 X是A的子公式，并有X Y，若用Y取代A中的X，得到新的命题公式B，则A B。这个定理叫替换定理。
证明 因为X Y，所以对命题公式A和B中的命题变元不管作何种真值指派，A和B总是有相同的真值，所以A B。

1.5.重言式、蕴含式与对偶式

1.5.1重言式

从1.4节中可以看到，有些命题公式，无论对原子命题变元做何种指派，其对应的真值都是逻辑真（T）或都是逻辑假（F），这两类特殊的命题在后面的命题演算中用途极大，下面作较为详细的讨论。
定义1.5.1重言式 给定一命题公式，若无论对命题变元作何种指派，其对应的真值永为真（T），则称该命题公式为重言式，或永真式。
定义1.5.2矛盾式 给定一命题公式，若无论对命题变元作何种指派，其对应的真值永为假（F），则称该命题公式为矛盾式，或永假式。
定义1.5.3 可满足式 给定一命题公式，若对命题变元作各种指派，其对应的真值至少有一个为真（T），则称该命题公式为可满足式。
矛盾式与重言式一样重要，不过将重言式研究清楚了，矛盾式的特性也出来了，所以本小结只研究重言式。下面是与重言式有关的三个定理。
定理1.5.1 任何两个重言式的合取或析取或条件或双条件，仍是一个重言式。

定理1.5.2一个重言式，对同一分量用任何合式公式置换，其结果仍为一重言式。
证明：因为重言式的真值与命题变元和分量的指派无关，所以对同一分量用任何合式公式置换后，其结果仍为一重言式。

定理1.5.3 设P和Q是两个命题公式，当且仅当是重言式。

1.5.2 蕴含式

定义1.5.4 蕴含式 蕴含当且仅当是重言式。蕴含记作。
定义1.5.5 逆换式 若是原式，则是其逆换式。
定义1.5.6 反换式 若是原式，则是其反换式。
定义1.5.7 逆反式 若是原式，则是其逆反式。

从蕴含式的定义可知，考察是否蕴含，只需要考察在不同真值指派时，当的真值为真时，的真值是否为真（前真看后真）。又因为，所以，也可以考察在的真值为假时，的真值是否为假（后假看前假）

正如“”与“”之间有关联一样，等价式与蕴含式之间也有关联。下面的定理给出了等价式与蕴含式之间的关系。
定理1-5.4 设P、Q为任意两个命题公式，的充分必要条件是且。

根据蕴含式的定义，很容易导出蕴含关系的几个常用性质。
性质1 。（自反性）
性质1反映了蕴含关系的自反性，根据蕴含关系的定义很容易证明，留给读者自己证明。
性质2 且是重言式，则必为重言式。
证明：因为，则为逻辑真值，又因为是重言式，则的值为真，所以的值必为真，则必为重言式。
性质3 且，则。 （传递性）
证明：因为 且，所以为真且也为真，则为重言式，根据假言三段论可知，根据性质2可知为重言式，则成立。
性质4 且，则。
证明：因为且，则为真且也为真，则为重言式，而，则成立。
性质5 且，则。
证明：因为且，则为真且也为真，则为重言式，而,则成立。

1.5.3对偶式

定义1.5.8 对偶式 若命题公式仅含联结词及逻辑值则将与互换，与互换，得到新的命题公式，则与互为对偶式。

关于对偶式有如下的两个定理，这两个定理所描述的事实常称为对偶原理。
定理1.5.5设和是对偶式，是出现在A和A*中的原子变元，则

定理1.5.6设和是只含有联结词的命题公式，是出现在和中的原子变元，若，则。
利用对偶原理，可以从已知的重言式构建出新的重言式，从已知的蕴含式、等价式作出新的蕴含式和等价式。

小结 本节主要内容 1. 深刻理解以下概念 重言式 给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为T，则称该命题公式为重言式或永真公式。 矛盾式 给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为F，则称该命题公式为矛盾式或永假公式。 蕴含式 当且仅当是一个重言式时，称蕴含，并记作。 逆换式 对来说，称作它的逆换式。 反换式 对来说，称为它的反换式。 逆反式 对来说，称为它的逆反式。 2. 掌握以下定理 定理1 任何两个重言式的合取或析取，仍然是一个重言式。 定理2 一个重言式，对同一分量都用任何合式公式置换，其结果仍为一重言式。 定理3 设为两个命题公式，当且仅当为一个重言式。 定理4 设为任意两个命题公式，的充分必要条件是且。 3. 会证明重言式、蕴含式

1.6.联结词的完备集

这5个基本的联结词与自然语言中的联结词紧密相关，易于理解，但还不能比较广泛地直接表示命题之间的联系，为此，本小节再定义另外的4个联结词。

1.6.1 不可兼析取

定义1.6.1不可兼析取 若和是任意的两个命题，则和的不可兼析取命题是一个复合命题，记作，当和的真值不相同时，的真值为，否则，的真值为。其真值情况如表所示

设为命题公式，根据对不可兼析取的定义可知，不可兼析取有如下性质：

1.6.2 条件的否定

定义1.6.2条件的否定 若和是任意的两个命题，则P和Q的条件的否定命题是一个复合命题，记作，当 为真而为假时，的真值为真，否则，为假。其真值情况如表1-19所示。

|

P |

Q | PQ | | —- | —- | —- | | T | T | F | | T | F | T | | F | T | F | | F | F | F |

1.6.3 与非

定义1.6.3与非 若和是任意的两个命题，则P和Q的与非命题是一个复合命题，记作，当P和Q的真值均为真时，的真值为假，否则，为真。其真值情况如表1-20所示。

1.6.4 或非

定义1.6.4或非 若和是任意的两个命题，则和的或非命题是一个复合命题，记作，当和的真值均为假时，的真值为真，否则，为假。其真值情况如表1-21所示。

定义1.6.4 联结词最小完备集 设是联结词集合，如果对任一命题公式，都有中的联结词表示出来的命题公式与之等价，则是联结词的完备集。
若对于任何一个命题公式，都能由仅含这些联结词的命题公式等价代换，则由这些联结词构成的集合称为联结词最小完备集。

1.7.命题公式的范式

1.7.1 合取范式与析取范式
定义1.7.1原子命题变元或原子命题变元的否定称为文字。有限个文字的析取称为析取式或子句，有限个文字的合取称为合取式或短语，原子命题变元与其否定称为互补对。

定义1.7.2合取范式 有限个析取式的合取称为合取范式。即合取范式具有以下形式：

• 
• 其中为析取式。
• 例如为合取范式。

定义1.7.3析取范式 有限个合取式的析取称为析取范式。即析取范式具有以下形式：

• 
• 其中为合取式。
• 例如为析取范式。

求范式的步骤： 1.将公式中的联结词归化为和 。 2.利用德·摩根律将否定联结词直接移到各个命题变元之前。 3.利用分配律、结合律和交换律将公式归约为合取范式或析取范式。

1.7.2 主析取范式

1．小项及其性质
定义1.7.4小项 n 个命题变元的合取式，称作布尔合取或小项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次。
例如，两个命题变元和，则其小项有4个，分别为：

若是三个命题变元，则其小项有8个，分别为： 。 对于有个命题变元的合式公式，其小项则有个。

定义1.7.5小项的二进制编码 约定命题变元按字典顺序排列，命题变元与1对应，命题变元的否定与0对应，则得到小项的二进制编码，记为，其下标i是由二进制转化的十进制数。n个命题变元形成的个小项，分别记为：

两个命题变元P和Q的小项真值表与编码如表

若两个命题变元P和Q，则对应的小项与编码之间的关系如下：

（1）各个小项的真值都不相同，没有两个小项是等价的。
（2）每个小项只有当赋值与其对应的二进制编码相同时，其真值为真，且其真值1位于主对角线上，其余的2n-1种真值指派情况下均为0__。
（3）任意两个小项的合取式是永假式。
（4）所有小项的析取式为永真式。

1.7.2 主析取范式

2.主析取范式

定义1.7.6 主析取范式 对于一个给定的命题公式，如果有一个等价公式，它仅由小项的析取所组成，则该等价式称作原式的主析取范式。
定理1.7.1任何一个非永假命题公式A都存在唯一与其等价的主析取范式。
假设B和C是A的两个不同的主析取范式，则且存在某个小项只出现在B中而不出现在C中，于是i的二进制在B中赋值为真，在C中赋值为假，这与矛盾。所以一个非永假命题公式A只有唯一与其等价的主析取范式（唯一性）。

3.求主析取范式的方法

（1）真值表法
定理1.7.2 在真值表中，一个公式的真值为T的指派所对应的小项的析取，即为此公式的主析取范式。
（2）公式法
①将命题公式化归为析取范式
②除去析取范式中所有永假的析取项
③将析取式中重复出现的合取项和相同的变元合并
④对合取项补入没有出现的命题变元，即添加（P∨┐P）式，再应用分配律展开公式即可。

1.7.3 主合取范式

1．大项及其性质

定义1.7.7大项n个命题变元的析取式，称作布尔析取或大项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次。
定义1.7.8大项的二进制编码 约定命题变元按字典顺序排列，命题变元与0对应，命题变元的否定与1对应，则得到大项的二进制编码，记为Mi，其下标i是由二进制转化的十进制数。n个命题变元形成的个大项，分别记为：

两个命题变元P和Q的大项真值表与编码如表所示

大项具有如下性质：
（1）各个大项的真值都不相同，没有两个大项是等价的。
（2）每个大项只有当赋值与其对应的二进制编码相同时，其真值为假，且其真值0
位于主对角线上，其余的2n-1种真值指派情况下均为1。
（3）任意两个大项的析取式是永真式。
（4）所有大项的合取式为永假式。

2.主合取范式

定义1.7.9 主合取范式 对于一个给定的命题公式，如果有一个等价公式，它仅由大项的合取所组成，则该等价式称作原式的主合取范式。
定理1.7.3任何一个非永真命题公式A都存在唯一与其等价的主合取范式。

3.求主合取范式的方法

（1）真值表法
定理1.7.4 在真值表中，一个公式的真值为F的指派所对应的大项的合取，即为此公式的主合取范式。
证明过程与定理1.7.2相同。
（2）公式法
①将命题公式化归为合取范式，
②除去合取范式中所有永真的合取项，
③将合取式中重复出现的析取项和相同的变元合并
④对析取项补入没有出现的命题变元，即添加（P∧┐P）式，再应用分配律展开公式即可。

1.7.4 主析取范式与主合取范式之间的联系
由于主析取范式由小项构成，而主合取范式由大项构成，由小项和大项的定义可知两者之间有下列关系：¬mi=Mi，¬Mi=mi，其中i是小项或大项的编码，由此可知主析取范式和主合取范式之间有着“互补”的关系。

1.8.推理理论

• 在数学中经常要考虑从某些前提得出什么结论，并经常假设这些前提是真的，尽管这些前提不一定为真。
• 使用前提和相应的规则，得到另外的命题，形成结论，这个过程就是推理。
• 推理过程中只关心结论是否有效，而不是关心结论是否真实。有效的结论不一定是真实的结论，因为形成有效结论的前提不一定永真。只是我们在推理过程中将这些前提当成真的。不过，若前提永真，则结论一定既是有效的也是真的。

• P规则（前提引入规则）：在推理过程中引入前提的规则。
• T规则（结论引入规则）：在推理过程中引入中间结论的规则，中间结论可以利用等价式或蕴含式产生。
• CP规则（附加前提规则）：如果要推导的结论是形如的公式，则把作为附加前提，与给定的前提一起推导出的规则。

1.8.2 判断有效结论的常用方法

判断有效结论方法很多，常用的有真值表技术、直接证明法、间接证明法。

1.真值表技术

设是出现在前提和结论C中的原子命题变元，对进行种真值指派，则可得到前提和结论的对应真值，列出该真值表。从真值表中找出为真的行，对于每一个这样的行，若结论的真值也为真，则C是前提的有效结论；或者找出结论的真值为假的行，若前提的真值中至少有一个为假，则也是前提的有效结论。

2.直接证明

直接证明就是由一组前提，利用一些公认的推理规则，根据已知的等价式或蕴含式，推演出有效结论的过程。在推演过程中会用到P规则和T规则，使用T规则时，若推导中依据的是等价式，规则应标明为，若依据的是蕴含式，则规则应标明为。

3.间接证明

设是出现在前提中的原子命题变元，对进行种真值指派，其中有些指派使得的真值为真，则称是相容的。若对进行种真值指派，每种指派都使得的真值为假，则称是不相容的。我们可以利用不相容的性质对命题公式进行间接证明。

4.CP规则

若要证明形如，即要证明的有效结论是形如的命题公式，则可以使用另外一种间接证明方法。令，则要证明，也就是要证明为永真式，即要证明为永真式，故为永真式，则为永真式。因此若，则必成立。由成立得到成立称为规则。

第二章：谓词逻辑

命题逻辑主要是研究命题和命题演算，研究命题与命题之间的逻辑关系，其基本组成单位是原子命题，并将原子命题看作是不可再分解的，因此它无法揭示原子命题内部的特征。但其实一个具有确定真值的陈述句还可以分解为主语与谓语部分，通过分解原子命题，可以刻画不同命题内部的逻辑结构，并找出不同命题之间的一些共同特性，这就需要一种更强类型的逻辑，即谓词逻辑。 命题逻辑除了不能充分地表达数学语言和自然语言中语句的意思外，其逻辑推理也存在一定的局限性，有些简单的论断也无法用命题逻辑进行推理。 比如苏格拉底的三段论：人都是要死的，苏格拉底是人，所以苏格拉底是要死的。

2.1 谓词的概念与表示

命题是可以判断真假的陈述句，一般地，一个陈述句由主语与谓语两部分组成。例如，离散数学是计算机科学的核心基础课程。其中“离散数学”是主语，而“是计算机科学的核心基础课程”是谓语。

这两个陈述句，若用命题逻辑来解释，就是两个不同的命题，但这两个命题除了主语不同外，谓语部分是完全相同的。若将句子分解为主语+谓语，则可以抽取这两个命题的谓语部分，刻画出这两个命题的共同属性。

2.1.1 谓词

定义2.1.1 谓词

• 原子命题中，主语部分一般是客体，而刻画客体的性质或客体之间关系的就是谓词。
• 表示具体的或特定的谓词，称为谓词常量；表示抽象的或泛指的谓词，称为谓词变量。

客体也称为个体词，它可以独立存在，可以是具体的，也可以是抽象的。表示具体或特定的客体，称为客体常量；表示抽象的或泛指的客体，称为客体变量。

2.1.2 n元谓词

• 有一个客体的是一元谓词，有两个客体的是二元谓词， 有三个客体的是三元谓词，则把有n个客体，形如的称为元谓词。

注意：

• （1）一元谓词刻画了客体的“性质”，而多元谓词则表达了客体之间的“关系”。
• （2）代表客体的字母在多元谓词中出现的次序与事先约定有关，不能随意改变。例如“a是大于b”，表示为 P(a,b)，若将客体a、b的顺序换掉，表示为P(b,a)，则意味着“b是大于 a”，是两个不同的命题了。
• （3）若谓词是变元或客体是变元，或是只有谓词部分，则都不能称为命题。
• （4）若一个n元谓词，其谓词是常元，并且n个客体也是常元，则它可以称为一个命题。
• （5）单独的谓词不能称为命题，将谓词字母后面填以客体所得到的式子称为谓词填式。谓词填式与谓词是两个不同的概论。

• （6）若谓词中没有客体变元，则是0元谓词，它就是一个命题。

  2.2 命题函数与量词

  2.2.1命题函数

  定义2.2.1 命题函数

• 由一个谓词和一些客体变元组成的表达式，称为简单命题函数；由一个或多个简单命题函数以及逻辑联结词组合而成的表达式，称为复合命题函数。

• 例如上面的P(x)、H(x,y)、B(x,y,z)是简单命题函数，而则是复合命题函数。
• 复合命题函数中用到的联结词与命题逻辑中的联结词含义相同。

定义2.2.2 个体域

• 在命题函数中，客体变元的论述范围称为个体域（或论域）。所有个体域的集合称为全总个体域。
• 根据个体域中元素是否有限，可以将个体域分为有限个体域和无限个体域两种。

  对于命题函数，因为存在客体变元，所以无法判断真假，它不是命题。只有对命题函数中的客体变元进行指派后，命题函数才能成为命题。 在对客体变元进行指派的过程中，客体变元的取值范围及客体变元取什么值，对命题函数是否可以成为命题及成为命题后真值如何有一定的影响。

  在命题函数中讨论论域中的客体时，若只用前面介绍过的概念，并不能很准确地表达出各种命题，例如R(x)表示x聪明，x的论域是某个班级的学生，那么这个命题函数里的客体是指某个班级的所有学生都聪明呢，还是指某个班级有部分学生聪明呢？为了更准确地表达出各类命题的含义，这里需要引入量词。在命题函数中，除了可用具体的客体常量对客体变量进行指派得到具有确定真值的陈述句外，还可以用量化个体变量的方法获得命题。

定义2.2.3量词 在命题函数中，限定客体数量的词，称为量词。限定所有客体变量的量词称为全称量词，用符号“”表示;限定部分客体变量的量词称为存在量词，用符号“”表示。
从上面的例子可以看出:w

1. 量词要放在谓词的前面，它限定的是谓词后面的客体。全称量词表示“所有的x”、“一切的x”、“任意的x”、“每个x””;存在量词表示“有些×”、“存在x”、“有的x”、“至少有一个×”等等。
2. 每个由量词确定的表达式都与个体域有关。在讨论带量词的命题函数时，必须确定其个体域。全总个体域可以描述命题函数中所有客体的变化范围，若对全总个体域中的每个客体的变化范围加以限制，可以使用特性谓词。

2.3 谓词公式与翻译

2.3.1 谓词公式

• 命题逻辑中的逻辑联结词在谓词逻辑中具有同样的含义，用逻辑联结词将简单的命题函数联结起来可以形成谓词表达式。不是所有的谓词表达式都能成为谓词公式，只有符合谓词演算合式公式定义的谓词表达式才能叫谓词公式。下面介绍谓词演算合式公式的定义。

定义2.3.1 谓词公式（合式公式）：

满足下列条件的表达式，称为谓词公式（合式公式）。

1. 简单命题函数是谓词公式（合式公式）。
2. 若P是谓词公式，则是谓词公式。
3. 若P、Q都是谓词公式，则是谓词公式。
4. 若P是谓词公式，是出现在P中的客体变元，则也是合式公式。
5. 仅由有限次地应用（1）、（2）、（3）、（4）所产生的表达式是谓词公式。

   根据上述定义可知，谓词公式是按上述规则，由简单命题函数、联结词、量词及括号组成，与命题公式类似，谓词公式中最外层的括号可以省略不写。 但量词后面的括号一般会指出量词的作用范围，不能省略。

2.3.2 谓词公式的翻译

自然语言中的一些命题可以用谓词公式来表达。把自然语言用谓词公式表示的过程，称为翻译。翻译的步骤为：

1. 先将自然语言分解为一个个地原子命题；
2. 分析每个原子命题的客体和谓词部分；
3. 分析每个客体的论域范围，选择合适的量词；
4. 将原子命题符合化；
5. 分析原子命题之间的逻辑关系，找到合适的联结词将原子命题联结起来。

   2.4 变元的约束

   由谓词公式的定义可知，一般地，量词和个体变元可能都会出现在谓词公式中，谓词公式中量词的作用在于对变元加以约束和限制，若某个变元受到量词的约束，则会被量化，被量化的变元就失去了变元的作用，没被量词量化的变元才能起到变元的作用。 要正确地理解谓词公式，必须分清楚那些是被量化的变元，那些是没被量化的变元。

2.4.1 约束变元与自由变元

• 定义2.4.1在谓词公式中，若有形如的部分，则这里后面所跟的叫做量词的指导变元或作用变元，叫做相应量词的作用域或辖域。在作用域中x的一切出现，称为在谓词公式中的约束出现，是约束变元。在谓词公式中除了约束变元外，所出现的其他变元不受指导变元的约束，称为自由变元。
• 

  一般地，一个量词的辖域是某个谓词公式的子公式，可以通过找出位于某个量词之后的紧邻的子公式的方法，找出该量词的辖域。具体方法如下：

  1. 若量词后面有括号，则括号内的子公式就是该量词的辖域；
  2. 若量词后无括号，则与量词紧邻的子公式为该量词的辖域。

定义2.4.2 闭式：

• 设α为任一合式公式，若α中无自由出现的个体变元，则α称为封闭的合式公式，简称闭式。

2.4.2 约束变元的换名与自由变元的代入

• 在合式公式中有的个体变元既是自由变元又是约束变元，容易引起混淆，为此，可以对约束变元换名或对自由变元进行代入，从而使得一个变元在一个合式公式中只以一种变元的状态出现，即要么是自由变元要么是约束变元。

  因此，可以对合式公式中的约束变元进行换名，也可以对合式公式中的自由变元进行代入。对约束变元换名或对自由变元进行代入都需要遵守一定的规则，换名规则如规则1，代入规则如规则2。 规则1（约束变元的换名规则）：将量词后面的指导变元及量词辖域的约束变元改成合式公式中没出现过的个体变元，公式中的其他部分不变。 规则2（自由变元的代入规则）：将合式公式中的某自由变元用合式公式中没出现过的新的个体变元取而代之，且处处代入，公式中的其他部分不变。

2.4.3 有限论域客体变元的枚举

• 合式公式中，当客体变元的论域有限，量词作用域中约束变元的所有可能的取代是可以枚举的。

  2.5 谓词演算的等价式与蕴含式

  2.5.1 谓词公式的赋值及分类

  定义2.5.1 谓词公式的赋值：

• 在客体变元论域范围内，把谓词公式中的客体变元用客体常元取代，命题变元用命题常元取代，这个过程就称为谓词公式的赋值，也叫谓词公式的解释。

• 一个谓词公式经过赋值后，就成为具有确定真值的命题。

定义2.5.2 给定任何两个谓词公式和，设它们有共同的个体域，若对A和B的任一组变元进行赋值，所得命题的真值都相同，则称谓词公式和在上是等价的，并记作：

与命题公式真值讨论类似，可以描述谓词公式在指定变量（包含非量化的个体变量和谓词变量）后的真值情况，进而划分出永真公式或永假公式。

定义2.5.3 给定任意谓词公式wffA，其个体域为E，对于A的所有赋值， wffA都为真，则称wffA在E上是有效的（或永真的）。
定义2.5.4 一个谓词公式wffA，如果在所有赋值下都为假，则称wffA为不可满足的（或永假的）。
定义2.5.5 一个谓词公式wffA，如果至少在一种赋值下为真，则称wffA为可满足的。

（1）命题公式的推广 在命题演算中，任一永真公式，其中同一命题变元，用同一公式取代时，其结果也是永真公式。可以把这个情况推广到谓词公式之中，当谓词演算中的公式代替命题演算中永真公式的变元时，所得的谓词公式即为有效公式，故命题演算中的等价公式表和蕴含公式表都可推广到谓词演算中使用。
命题演算的等价式

谓词演算的等价式

（2）量词与联结词¬之间的关系 将量词前面¬的移到量词后面去时，存在量词改为全称量词，全称量词改为存在量词，反之，将量词后面的¬移到量词前面去时，也要做相应的改变。
（3）量词扩张/收缩律

（4）量词与命题联结词之间的一些等价式 量词分配律

（5）量词与命题联结词之间的一些蕴含式

2.5.4 多个量词之间的等价关系与蕴含关系

2.6 前束范式