第5章谓词逻辑

5.1谓词逻辑的基本概念

命题逻辑的基本研究单位是简单命题，所研究的是命题之间的逻辑关系和推理。换言之，命题逻辑对自然语言的事实陈述及其推理只解析到简单命题为止，而无法研究简单命题的内部结构及命题间的内在关系。由此，导致一些简单而又常见的推理过程往往无法处理。例如，著名的苏格拉底三段论： 
· 所有的人都是要死的； 
· 苏格拉底是人； 
· 所以，苏格拉底是要死的。
显然，这个推理是正确的推理。从命题逻辑的观点看，上述推理过程含有3个简单命题，若分别用符号p、q、r表示“所有的人都是要死的”“苏格拉底是人”和“苏格拉底是要死的”，则r应该是p和q的有效结论，即p，qr。根据命题逻辑公式的解释，在p取1、q取1和r取0下，命题公式p∧q→r的真值为0。所以，命题公式p∧q→r不是永真公式，即r不是p和q的有效结论。因此，命题逻辑无法正确表述这一推理过程。
产生上述问题的原因在于： 这类推理中，各命题之间的逻辑关系不仅体现在简单命题之间，而且体现在简单命题的内部成分之间。命题逻辑无法对简单命题的内部成分及其之间的逻辑结构进行描述和推理，这是命题逻辑的局限性。因此，有必要对简单命题作进一步的解析，分析其中更细节的要素，即分解出其中的个体词(individual)、谓词(predicate)、量词(quantifier)和函词(function)，研究它们的形式结构及逻辑关系。这就是一阶谓词逻辑(first order predicate logic)所研究的内容。一阶谓词逻辑简称为谓词逻辑(predicate logic)或一阶逻辑(first order logic)。
5.1.1个体词
命题是具有真假意义的陈述句。从自然语言的语法角度，一个陈述句的主要结构形式为“主语+谓语”或“主语+谓语+宾语”。可以把陈述句所含有的各个句子成分作为基本单元，进行简单命题的进一步解析。
例如，陈述句“离散数学是计算机科学与技术专业本科生的必修课程”属于“主语+谓语”的句子结构，其中，主语为“离散数学”，谓语为“是计算机科学与技术专业本科生的必修课程”； 陈述句“x大于5”属于“主语+谓语+宾语”的句子结构，其中，主语为“x”，谓语为“大于”，宾语为“5”。
定义5.1在陈述句中，可以独立存在的具体的或抽象的客体(句子中的主语、宾语等)，称为个体词(individual)。表示具体或特定的客体的个体词称为个体常量或个体常元(individual constant)。没有赋予具体内容或泛指的个体词称为个体变元或个体变量(individual variable)。个体变元的所有可能取值组成的集合称为个体域(individual field)。
一般地，个体常量用小写英文字母a、b、c等表示，个体变元用小写英文字母x、y、z等表示，个体域用D表示。个体域可以是有限集合，也可以是无限集合。当个体词遍及宇宙中的一切客体时，个体域特称为全总个体域(universal individual field)。
例如，在陈述句“3是质数”中，“3”和“质数”是个体词，“3”是个体常量，“质数”是个体变元，其个体域是所有质数的集合； 在陈述句“所有人都需要呼吸氧气”中，“人”和“氧气”是个体词，“氧气”是个体常量，“人”是个体变元，其个体域是所有人的集合； 在陈述句“x<y+1，x∈Z，y∈N且y<6”中，“1”“x”和“y”都是个体词，“1”是个体常量，“x”和“y”都是个体变元，个体变元x的个体域为整数集合Z，个体变元y的个体域为有限集合{0，1，2，3，4，5}。





5.1.2谓词
谓语是构成一个句子必有的成分单元，在这里用下述定义对其进行形式化描述。
定义5.2在陈述句中，用来刻画个体词性质以及个体词之间相互关系的词(句子中的谓语)，称为谓词。表示具体或特定的性质或关系的谓词称为谓词常量或谓词常元(predicate constant)。没有赋予具体内容或泛指的谓词称为谓词变量或谓词变元(predicate variable)。表示一个个体词性质的谓词称为一元谓词，表示n个个体词之间关系的谓词称为n元谓词(nary predicate)。
无论是谓词变元还是谓词常量都用大写英文字母P、Q、R、G、B等表示。含有n个个体变元x1，x2，…，xn的n元谓词用P(x1，x2，…，xn)表示。一元谓词P(x)表示x具有性质P； 二元谓词P(x，y)表示x和y具有关系P； 三元谓词P(x，y，z)表示x、y和z具有关系P。实质上，n元谓词P(x1，x2，…，xn)可看成以个体域的笛卡儿积D1×D2×…×Dn(Di为xi的个体域)为定义域、以{0，1}为值域的n元函数。不含有个体变元的谓词称为0元谓词。0元谓词实际上就是一般的命题。
对于n元谓词P(x1，x2，…，xn)，如果个体变元x1，x2，…，xn没有赋予确切的个体词，那么，该n元谓词就没有确切的真值，即并非一个命题。只有当个体变元x1，x2，…，xn被赋予确定的个体词后，才能确定P(x1，x2，…，xn)的真假值，此时，P(x1，x2，…，xn)才是一个命题。
例5.1用谓词表示下列命题：
① “离散数学”是一门重要的计算机课程； 
② 张兰和王强是同班同学； 
③ 桂林位于北京和南宁之间； 
④ 老李是小李的父亲。
解① 用一元谓词S(x)表示“x是一门重要的计算机课程”，用个体常量a 表示“离散数学”，那么命题①可用谓词S(a)表示。
② 用二元谓词P(x，y)表示“x和y是同班同学”，用个体常量a和b 分别表示“张兰”和“王强”，那么命题②可用谓词P(a，b)表示。
③ 用三元谓词Q(x，y，z)表示“x位于y和z之间”，用个体常量a、b和c 分别表示“桂林”“北京”和“南宁”，那么命题③可用谓词Q(a，b，c)表示。
④ 用二元谓词H(x，y)表示“x是y的父亲”，用个体常量a和b 分别表示“老李”和“小李”，那么命题④可用谓词H(a，b)表示。
注意： 谓词中个体词的顺序是十分重要的，不能随意变更。例如，对于例5.1 中命题④，H(b，a)表示的是“小李是老李的父亲”，显然，不同于H(a，b)的含义。再如，例5.1中命题③，Q(b，a，c)表示的是“北京位于桂林和南宁之间”，Q(c，a，b) 表示的是“南宁位于桂林和北京之间”，显然，它们都不同于Q(a，b，c)的含义。
5.1.3函词
在许多陈述句中，含有类似于“集合的幂集”“张山的父亲”“键盘的字符”等形式的句子成分。这些句子成分是个体词到个体词的映射，可以通过下述函词(function)来描述。
定义5.3个体词到个体词的映射称为函词(function)，用小写字母f、g、h等表示。以个体域的笛卡儿积D1×D2×… ×Dn(Di为xi的个体域)为定义域，以个体域D为值域的n元函数，称为n元函词(nary function)，含有n个个体变元x1，x2，…，xn的n元函词用f(x1，x2，…，xn)表示。
实质上，函词就是一般意义上的函数，n元函词就是n元函数。只不过，函词的定义域为个体域的笛卡儿积，函词的值域是个体域。因此，函词也就具有了函数的一些特征。对应于函数中的复合函数，函词也有复合函词。
例5.2用谓词和函词表示下列命题：
① 大连的海滩和北海的海滩一样漂亮； 
② 桂林的漓江是5A级旅游风景区； 
③ 周宏的“离散数学”任课老师是教授； 
④ 刘芳的妹妹喜欢唱歌； 
⑤ 唐钢和李红的女儿在弹琵琶。
解① 用一元函词g(x)表示“x的海滩”，用二元谓词H(x，y)表示“x和y一样漂亮”，用个体常量a和b分别表示“大连”和“北海”。那么，命题①的谓词和函词表示为H(g(a)，g(b))。
② 用一元函词f(x)表示“x的漓江”，用一元谓词Q(x)表示“x是5A级旅游风景区”，用个体常量a表示“桂林”。那么，命题②的谓词和函词表示为Q(f(a))。
③ 用一元函词f(x)表示“x的‘离散数学’任课老师”，用一元谓词R(x)表示“x是教授”，用个体常量a表示“周宏”。那么，命题③的谓词和函词表示为R(f(a))。
④ 用一元函词g(x)表示“x的妹妹”，用二元谓词R(x，y)表示“x喜欢y”，用个体常量a和b分别表示“刘芳”和“唱歌”。那么，命题④的谓词和函词表示为R(g(a)，b)。
⑤ 用二元函词f(x，y)表示“x和y的女儿”，用二元谓词R(x，y)表示“x在弹y”，用个体常量a、b和c分别表示“唐钢”“李红”和“琵琶”。那么，命题⑤的谓词和函词表示为R(f(a，b)，c)。
注意： n元谓词也是一个n元函数。n元谓词和n元函词的区别在于前者的值域为{0，1}，而后者的值域为某一个体域。不要引起混淆。
5.1.4量词
在n元谓词P(x1，x2，…，xn)中，对所有个体变元x1，x2，…，xn都赋予确定的个体词，就可以得到一个命题。将n元谓词转换为一个命题的另一种方式是对个体变元进行量化。
定义5.4将谓词中个体变元的取值限定为其个体域的每一个元素，称为个体变元的全称量化(universal quantification)，所用的量词称为全称量词(universal quantifier)，用符号表示。并用x、y、z等表示所有个体，而用(x)P(x)、(y)P(y)、(z)P(z)等表示个体域中的所有个体具有性质P。
全称量词对应于自然语言或数学中的“一切”“所有”“每一个”“任意”“凡”“都”等词。
定义5.5将谓词中个体变元的取值限定为其个体域的某一个或多个元素，称为个体变元的存在量化(existential quantification)，所用的量词称为存在量词(existential quantifier)，用符号表示，并用x、y、z等表示个体域中有的个体，而用(x)P(x)、(y)P(y)、(z)P(z)等表示个体域中有的个体具有性质P。
存在量词对应于自然语言或数学中的“存在”“有的”“有一个”“至少有一个”“某一个”“某些”等词。全称量词和存在量词统称为量词。
在命题的谓词逻辑表示中，明确地给出个体变元的个体域是非常重要的事情。例如，对于命题“所有人都是要呼吸的”，设谓词B(x)： x是要呼吸的，命题表示为(x)B(x)。如果个体域为所有人的集合时，(x)B(x)的真值为真。但当个体域为自然数集合时，(x)B(x)的真值为假。为此，在讨论带有量词的命题时，必须确定其个体域。为了方便，在没有给定个体变元的个体域的情况下，将所有命题的个体域全部统一，使用全总个体域。用了这个全总个体域后，对每一个个体变元的变化范围，通过定义特性谓词(particular predicate)来实现对个体域的规范和表示。
例5.3用谓词和量词符号表示下列命题：
① 任何人都是要死的；
② 空集包含于任意集合； 
③ 所有自然数非负； 
④ 每一个计算机专业学生都要修离散数学； 
⑤ 所有鸟都会飞； 
⑥ 每一个大学生都要熟练使用计算机。
解① 用一元谓词D(x)表示“x是要死的”，用特性谓词M(x)表示“x是人”。那么，命题①可符号化地表示为(x)(M(x)→D(x))。
② 用二元谓词P(x，y)表示“x包含于y”，用特性谓词S(x)表示“x是集合”，用个体常量a表示“空集”。那么，命题②可符号化地表示为(x)(S(x)→P(a，x))。
③ 用一元谓词Q(x)表示“x是负数”，用特性谓词N(x)表示“x是自然数”。那么，命题③可符号化地表示为(x)(N(x)→�瘙
綈Q(x))。
④ 用二元谓词R(x，y)表示“x要修y”，用特性谓词C(x)表示“x是计算机专业学生”，用个体常量b表示“离散数学”。那么，命题④可符号化地表示为(x)(C(x)→R(x，b))。
⑤ 用一元谓词P(x)表示“x会飞”，用特性谓词B(x)表示“x是鸟”。那么，命题⑤可符号化地表示为(x)(B(x)→P(x))。 
⑥ 用二元谓词H(x，y)表示“x熟练使用y”，用特性谓词S(x)表示“x是大学生”，用个体常量a表示“计算机”。那么，命题⑥可符号化地表示为(x)(S(x)→H(x，a))。
例5.4用谓词和量词符号表示下列命题：
① 有的人活百岁以上；
② 有些人登上过月球； 
③ 有的自然数是素数； 
④ 有些学生没有认真完成离散数学作业； 
⑤ 某些人用左手写字； 
⑥ 至少完成一次综合实验； 
⑦  某一个星球存在生命。
解① 用一元谓词L(x)表示“x活百岁以上”，用特性谓词M(x)表示“x是人”。那么，命题①可符号化地表示为(x)(M(x)∧L(x))。
②  用二元谓词P(x，y)表示“x登上过y”，用特性谓词M(x)表示“x是人”，用个体常量a表示“月球”。那么，命题②可符号化地表示为(x)(M(x)∧P(x，a))。
③ 用一元谓词Q(x)表示“x是素数”，用特性谓词N(x)表示“x是自然数”。那么，命题③可符号化地表示为(x)(N(x)∧Q(x))。
④ 用二元谓词R(x，y)表示“x认真完成y”，用特性谓词S(x)表示“x是学生”，用个体常量b表示“离散数学作业”。那么，命题④可符号化地表示为(x)(S(x)∧�瘙
綈R(x，b))。
⑤ 用二元谓词Q(x，y)表示“x用y写字”，用特性谓词M(x)表示“x是人”，用个体常量a表示“左手”。那么，命题⑤可符号化地表示为(x)(M(x)∧Q(x，a))。
⑥ 用一元谓词Q(x)表示“完成x”，用特性谓词E(x)表示“x是综合实验”。那么，命题⑥可符号化地表示为(x)(E(x)∧Q(x))。
⑦ 用二元谓词H(x，y)表示“x存在y”，用特性谓词S(x)表示“x是星球”，用特性谓词L(x)表示“x是生命”。那么，命题⑦可符号化地表示为(x)(y) (S(x)∧L(y)∧H(x，y))。
5.1.5命题的谓词逻辑符号化
在命题的谓词逻辑符号化中，对每个语句中个体变元的个体域统一为全总个体域，而对各语句中的个体变元的变化范围则用一元特性谓词刻画，特性谓词在添加到谓词逻辑符号化中时必须遵循以下原则： 
①  对于全称量词(x)，刻画其对应个体域的特性谓词作为蕴含式的前件加入； 
②  对于存在量词(x)，刻画其对应个体域的特性谓词通过合取加入。
例5.5用谓词逻辑符号化下列命题：
① 每一个苹果都是红色的； 
② 任意一个整数都是正整数或负整数； 
③ 有一些实数是有理数； 
④ 有一些人很聪明； 
⑤ 有一些实数，使得x+5=3； 
⑥ 所有实验设备都要放在工作台D1上。
解① 用一元谓词R(x)表示“x是红色的”，用特性谓词A(x)表示“x是苹果”。那么，命题①可谓词逻辑符号化为(x)(A(x)→R(x))。
② 用一元谓词P(x)表示“x是正数”，一元谓词N(x)表示“x是负数”，用特性谓词Z(x)表示“x是整数”。那么，命题②可谓词逻辑符号化为(x)(Z(x)→(P(x)∨N(x)))。
③ 用一元谓词Q(x)表示“x是有理数”，用特性谓词R(x)表示“x是实数”。那么，命题③可谓词逻辑符号化为(x) (R(x)∧Q(x))。 
④ 用一元谓词C(x)表示“x很聪明”，用特性谓词M(x)表示“x是人”。那么，命题④可谓词逻辑符号化为(x) (M(x)∧C(x))。 
⑤ 用一元谓词E(x)表示“x+5=3”，用特性谓词R(x)表示“x是实数”。那么，命题⑤可谓词逻辑符号化为(x) (R(x)∧E(x))。 
⑥ 用二元谓词F(x，y)表示“x要放到y上”，用特性谓词D(x)表示“x是实验设备”。个体常量a表示“工作台D1”，那么，命题⑥可谓词逻辑符号化为(x)(D(x)→F(x，a))。
自然语言的谓词逻辑符号化表示，较之于命题逻辑符号化表示要复杂得多。在自然语言的谓词逻辑符号表示中，不仅需要考虑语句之间的关联词，而且要将语句拆开分析其句子成分，考虑谓词、量词、函词、个体词等。这些工作的开展关键在于词性翻译，以下给出一些常用规则。
(1) 代词： 对应于个体常量。例如，人称代词“你”“我”“他”，指示代词“这个”“那个”等。
(2) 专有名词： 对应于个体常量。例如，人名“钱学森”，地名“北京”等。
(3) 普通名词： 一般对应于特性谓词，表示为“x是……”； 没有任何修饰词时，一般还需要引入量词，如“人需要呼吸氧气”中的“人”就要引入全称量词； 如果被名词所有格或物主代词限制或修饰时，相当于专有名词，则对应于函词，如“他的书”就要引入函词； 名词的所有格或物主代词，一般对应于函词的个体变元。
(4) 动词： 对应于谓词，如“我喜欢书”中的动词“喜欢”。
(5) 形容词： 对应于特性谓词，表示为“x是……的”。
(6) 数量词： 对应于量词，如“所有的植物”中的“所有”和“有些动物”中的“有些”。
(7) 副词： 与其所修饰的词合并，不进行单独分析。
(8) 前置词： 与其所修饰的词合并，不进行单独分析。
例5.6给出下列语句的谓词逻辑符号化表示：
① 沃尔玛超市供应一切简易办公用品； 
② 没有以0为后继的自然数； 
③ 有会说话的机器人； 
④ 每个实数都存在比它大的另外的实数； 
⑤ 每个人都有某些专长； 
⑥ 尽管有人很聪明，但未必一切人都聪明。
解① 分析语句①的成分如下： 

沃尔玛超市供应一切简易办公用品

专用名词动词数量词形容词普通名词

用个体常量a表示“沃尔玛超市”； 用二元谓词S(x，y)表示“x供应y”； 用特性谓词N(x)表示“x是简易的”； 用特性谓词W(x)表示“x是办公用品”。那么，语句①可谓词逻辑符号化为(x)(N(x)∧W(x)→S(a，x))。
② 分析语句②的成分如下： 

没有以0为后继的自然数

关联词数量词专有名词动词普通名词

用个体常量a表示“0”； 用二元谓词A(x，y)表示“x以y为后继”； 用特性谓词N(x)表示“x是自然数”。那么，语句②可谓词逻辑符号化为�瘙
綈(x)(N(x)∧A(x，a))。
③ 分析语句③的成分如下： 

有会说话的机器人

数量词动词普通名词

用一元谓词S(x)表示“x会说话”； 用特性谓词R(x)表示“x是机器人”。那么，语句③可谓词逻辑符号化为(x)(R(x)∧S(x))。
④ 分析语句④的成分如下： 

每个实数都存在比它大的另外的实数

数量词普通名词数量词代词动词普通名词

用二元谓词L(x，y)表示“x比y大”； 用特性谓词R(x)表示“x是实数”。那么，语句④可谓词逻辑符号化为(x)(R(x)→(y)(R(y)∧L(y，x)))。
⑤ 分析语句⑤的成分如下： 

每个人都有某些专长

数量词普通名词动词数量词普通名词

用二元谓词H(x，y)表示“x有y”； 用特性谓词P(x)表示“x是人”； 用特性谓词S(x)表示“x是专长”。那么，语句⑤可谓词逻辑符号化为(x)(P(x)→(y)(S(y)∧H(x，y)))。
⑥  分析语句⑥的成分如下： 

尽管有人很聪明，但未必一切人都聪明

联结词数量词普通名词动词关联词数量词普通名词动词

用一元谓词C(x)表示“x很聪明”； 用特性谓词P(x)表示“x是人”。那么，语句⑥可谓词逻辑符号化为(x)(P(x)∧C(x))∧�瘙
綈(x)(P(x)→C(x))。

5.2谓词逻辑公式
5.2.1谓词公式的定义
自然语言形式表示的任何可判断真假的陈述句都可以分解为简单陈述句和关联词的连接形式，而简单陈述句又可以依据语句的结构和成分进一步解析为个体词、谓词、函词、量词等。这样自然语言的表示和推理，就可以转化为基于联结词、个体词、谓词、函词、量词等符号的形式表示和推理。由联结词、个体变元、个体常量、谓词、函词、量词等组成的用以表示复杂命题的符号串，称为一阶谓词逻辑公式(first order predicate logic formula)，简称为谓词逻辑公式(predicate logic formula)或一阶逻辑公式(first order logic formula)。下面给出谓词逻辑公式的严格数学定义。
定义5.6个体变元、个体常量和函词按照一定规则组成的符号串，称为谓词逻辑的项(term)。 项按以下规则生成： 
① 个体变元或个体常量是项； 
② 如果f(x1，x2，…，xn)为n元函词，t1，t2，…，tn为项，那么f(t1，t2，…，tn)是项； 
③ 有限次使用①和②后所得到的符号串才是项。
项的定义使得可以用函词来表示具有某些特定性质或某些特定形式的个体。例如，个体常量a和b是项； 个体变元x和y是项； 函词f(x，y)=x+y和g(x，y)=x-y是项； 函词f(a，f(x，y))=a+(x+y)和g(x，f(a，b))=x-(a+b)也是项。
定义5.7设P(x1，x2，…，xn)为n元谓词，t1，t2，…，tn为项，则称P(t1，t2，…，tn)为原子谓词逻辑公式(atomic predicate logic formula)，简称为原子谓词公式或原子公式(atomic formula)。
例如，用二元谓词H(x，y)表示“x在y的北方”，用个体常量a和b 分别表示“北京”和“上海”。那么，H(a，b)表示“北京在上海的北方”，H(a，b)是一个原子公式。
再如，用二元函词f(x，y)表示“x和y的老乡”，用一元谓词R(x)表示“x是学习委员”，用个体常量a和c分别表示“周强”和“江川”。那么，R(f(a，c))表示“周强和江川的老乡是学习委员”，R(f(a，c))是一个原子公式。
定义5.8原子公式、量词和联结词按照一定规则组成的符号串，称为谓词逻辑合适公式(wellformed predicate logic formula)，简称为谓词逻辑公式或谓词公式(predicate formula)。谓词公式按以下规则生成： 
① 原子公式是谓词公式； 
② 如果A是谓词公式，则(�瘙
綈A)是谓词公式； 
③ 如果A和B是谓词公式，则(A∨B)，(A∧B)，(A→B)，(AB)是谓词公式； 
④ 如果A是谓词公式，则(x)A、(x)A是谓词公式； 
⑤ 有限次使用①～④后所得到的符号串才是谓词公式。
例如，字符串�瘙
綈H(x，y)、H(x，y)∨G(x)、(y)(H(x，y)∨G(x))、(y)H(x，y)∨G(x)、(y)(x)H(x，y)、(x)(y)(A(x，y)∧B(x))→H(x)、
�瘙
綈(y)H(x，y)、(x)�瘙
綈H(x，y)都满足谓词公式定义中的规则，所以，它们都是谓词公式； 字符串�瘙
綈H(x，y、�瘙
綈(H→∧y、H(，y)∨G(x)、()(H(x，y)∨G(x))、(y)H(x，y)∨、(x)()(A(x，y)、�瘙
綈(y)(x，A(y)、(x)�瘙
綈H(x→y)都不满足谓词公式定义中的规则，所以，这些符号串都不是谓词公式。
定义5.9在形如(x)A(x)或(x)A(x)的谓词公式中，称A(x)为量词的辖域(scope)或作用域(function field)，或者个体变元x的约束域(bound field)，并称x为量词或的作用变元(function variable)或指导变元(directed variable)。在辖域中，指导变元x的一切出现称为x在公式中的约束出现(bound occurrence)，并称该个体变元为约束变元(bound variable)。在谓词公式中，除约束变元外出现的个体变元称为自由变元(free variable)，或者个体变元的自由出现(free occurrence)。
例5.7判断下列谓词公式中的约束变元和自由变元，并指出约束变元的约束域；
① (x)(y)(A(x，y)∧B(x))→H(x)； 
② (x)(y)(A(x，y)∧B(x)→H(x))； 
③ (y)(A(x，y)∧B(x)→H(x))； 
④ (x)(y)(A(x，y)∧B(x)H(x)∧G(z))； 
⑤ (x)(y)(z)(A(x，y)∧B(x)H(x)∧G(z))； 
⑥ (x)(y)(z)(A(x，y)∧B(x)H(u)∧G(z))。
解① 个体变元y是约束变元，其约束域为A(x，y)∧B(x)； 个体变元x既有约束出现，又有自由出现，其约束域为(y)(A(x，y)∧B(x))。
② 个体变元x是约束变元，其约束域为(y)(A(x，y)∧B(x)→H(x))； 个体变元y是约束变元，其约束域为A(x，y)∧B(x)→H(x)。
③ 个体变元x是自由变元； 个体变元y是约束变元，其约束域为A(x，y)∧B(x)→H(x)。
④ 个体变元x和y是约束变元，它们的约束域分别为(y)(A(x，y)∧B(x)H(x)∧G(z))和A(x，y)∧B(x)H(x)∧G(z)； 个体变元z是自由变元。
⑤ 个体变元x、y和z是约束变元，它们的约束域分别为(y)(z)(A(x，y)∧B(x)H(x)∧G(z))和(z)(A(x，y)∧B(x)H(x)∧G(z))及A(x，y)∧B(x)H(x)∧G(z)。
⑥ 个体变元x、y和z是约束变元，它们的约束域分别为(y)(z)(A(x，y)∧B(x)H(u)∧G(z))和(z)(A(x，y)∧B(x)H(u)∧G(z))及A(x，y)∧B(x)H(u)∧G(z)； 个体变元u是自由变元。
从例5.7可知，在一个谓词公式中，某一个个体变元的出现既可以是自由的又可以是约束的。例如，谓词公式(x)A(x)∧B(x)中的个体变元x； 谓词公式(x)(y)(A(x，y)∧B(x))→H(x)中的个体变元x； 谓词公式(x)(y)(A(x，y)∧B(x))(u)(H(y)∧G(u))中的个体变元y。
为了使表示和推理过程中不致引起混淆，我们希望一个个体变元在同一个谓词公式中只以自由或约束中的一种形式出现，即不同含义的个体变元总是以不同的变元符号来表示。为此，引入以下两个规则。
规则1(约束变元的换名规则)： 
① 在量词的辖域中，对该量词的作用变元及其约束出现用一个新的个体变元替换； 
② 新的个体变元一定要有别于换名辖域中的其他所有个体变元。
规则2(自由变元的代替规则)： 
① 在谓词公式中，对某自由变元的所有自由出现都用未曾出现过的个体变元替换； 
② 新的个体变元在原谓词公式中不能有任何形式的约束出现。
例5.8对下列谓词公式进行个体变元替换，使每一个个体变元有唯一的出现形式：
① (x)A(x)∧B(x)； 
② (x)(y)(A(x，y)∧B(x))→H(x)； 
③ (x)(y)A(x，y)(u)(H(y)∧G(u))； 
④  (x)(A(x，y)∧B(x))→(y)H(x，y)； 
⑤  (x)(y)(A(x，z)∧B(y))(y)(H(y)∧G(x))； 
⑥  (x)A(x)∧(x)B(x)∧(x)C(x)∧G(x)。
解① 在谓词公式①中，个体变元x既有约束出现又有自由出现。利用规则2，对B(x)中自由出现的个体变元x用个体变元y替换。所以，谓词公式①进行个体变元替换后的形式为(x)A(x)∧B(y)。
②  在谓词公式②中，个体变元x既有约束出现又有自由出现。利用规则2，对H(x)中自由出现的个体变元x用个体变元z替换。所以，谓词公式②进行个体变元替换后的形式为(x)(y)(A(x，y)∧B(x))→H(z)。
③ 在谓词公式③中，个体变元y既有约束出现又有自由出现。利用规则2，对H(y)中自由出现的个体变元y用个体变元z替换。所以，谓词公式③进行个体变元替换后的形式为(x)(y)A(x，y)(u)(H(z)∧G(u))。
④ 在谓词公式④中，个体变元x和个体变元y都既有约束出现，又有自由出现。利用规则2，对A(x，y)中自由出现的个体变元y用个体变元z替换，对H(x，y)中自由出现的个体变元x用个体变元u替换。所以，谓词公式④进行个体变元替换后的形式为(x)(A(x，z)∧B(x))→(y)H(u，y)。
⑤ 在谓词公式⑤中，个体变元x既有约束出现，又有自由出现； 个体变元y出现在不同的辖域。利用规则2，对G(x)中自由出现的个体变元x用个体变元w替换； 利用规则1，对(y)(H(y)∧G(x))中约束出现的个体变元y用个体变元u替换。所以，谓词公式⑤进行个体变元替换后的形式为(x)(y)(A(x，z)∧B(y))(u) (H(u)∧G(w))。
⑥ 在谓词公式⑥中，个体变元x既有约束出现，又有自由出现，且约束出现在不同的辖域。利用规则2，对G(x)中自由出现的个体变元x用个体变元w替换； 利用规则1，对(x)B(x)中约束出现的个体变元x用个体变元y替换； 对(x)C(x)中约束出现的个体变元x用个体变元z替换。所以，谓词公式⑥进行个体变元替换后的形式为(x)A(x)∧(y) B(y)∧(z)C(z)∧G(w)。
5.2.2谓词公式的解释
谓词公式是自然语言中事实的符号表示，当然谓词公式的表示也有正确与否的区分。谓词公式所表示的事实为真，则称谓词公式的取值为真； 谓词公式所表示的事实为假，则称谓词公式的取值为假。谓词公式的真或假的取值称为谓词公式的真值(value)。谓词公式是由原子公式、逻辑联结词、量词等组成的符号串，只有对它们给予确切或具体的解释后，才能对谓词公式的真值进行分析。
定义5.10对谓词公式G中一些符号表示的含义进行明确的规定，称为谓词公式的一个赋值(evaluation)或者解释(explanation)，记为I。谓词公式G的一个解释通常由以下4部分组成： 
① 非空的个体域集合D； 
② 对谓词公式G中的个体常量，指定D中的某个特定的元素； 
③ 对谓词公式G中的n元函词，指定Dn到D中的某个特定的函词； 
④ 对谓词公式G中的n元谓词，指定Dn到{0，1}的某个特定的谓词。
定义5.11对谓词公式G和解释I，如果在解释I下谓词公式G的真值为真，则称I为G的成真解释(true explanation)或成真赋值(true evaluation)； 如果在解释I下谓词公式G的真值为假，则称I为G的成假解释(false explanation)或成假赋值(false evaluation)。
例5.9对于谓词公式(x)(y)�瘙
綈(z)(�瘙
綈A(f(x，z)，y))，说明它在以下解释中的具体含义。
解释I1： 
个体域D1={0，1，2，…}； 
函词f(x，y)=x+y；  
谓词A(x，y)： x=y。
解释I2： 
个体域D2为正有理数集合； 
函词f(x，y)=x·y；  
谓词A(x，y)： x=y。
解在解释I1下，谓词公式的含义为： 对于D1中所有的x和y，并非对D1中的每个z，都有x+z≠y。换言之，对于D1中所有的x和y，存在D1中的z，使得x+z=y。显然，当x取3和y取1时，不存在D1中的z，使得3+z=1。所以，谓词公式在解释I1下的取值为假，即解释I1是该谓词公式的一个成假解释。 
在解释I2下，谓词公式的含义为： 对于D2中所有的x和y，存在D2中的z，使得x·z=y。显然，谓词公式在解释I2下的取值为真，即解释I2是该谓词公式的一个成真赋值。
例5.10对于谓词公式(x)(P(f(x))∧Q(x，f(a)))，给出它在以下解释I下的真值。
解释I： 
个体域D={α，β}； 
个体常量a指定为α；  
函词指定为： f(α)=β，f(β)=α； 
谓词P(x)指定为： P(α)=1，P(β)=0； 
谓词Q(x，y)指定为： Q(α，α)=0，Q(α，β)=1，Q(β，α)=1，Q(β，β)=1。
解由于谓词公式是由存在量词加以限制，根据存在量词的定义，只要个体域中有一个x使得P(f(x))∧Q(x，f(a))为真，则原谓词公式为真； 否则，只有当个体域中全部的x都使得P(f(x))∧Q(x，f(a))为假，则原谓词公式为假。为此，分别考察x=β和x=α时的真值情况。
当x=β时，有
f(β)=α
P(f(x))=P(f(β))=P(α)=1
f(a)=f(α)=β
Q(x，f(a))=Q(β，f(α))=Q(β，β)=1
P(f(x))∧Q(x，f(a))=P(f(β))∧Q(β，f(α))=1∧1=1
即存在x=β，使得P(f(x))∧Q(x，f(a))=1。所以，谓词公式(x)(P(f(x))∧Q(x，f(a)))的真值为1。
例5.11给定解释I： 
个体域D为非负整数集合； 
个体常量a指定为2； 
函词指定为： f(x，y)=x+y，g(x，y)=x·y； 
谓词Q(x，y)指定为： x=y。
给出下列谓词公式的含义：
① (x)Q(g(x，y)，x)； 
② (x)(y)(Q(f(x，a)，y)→Q(f(y，a)，x))； 
③ (x)(y)(z)Q(f(x，y)，z)； 
④ (x)Q(f(x，x)，g(x，x))。
解① 谓词公式①的含义为： 对于任意非负整数x，都有x·y=x。由于x·y=x是否成立，取决于y的取值。如果y的取值为1，则x·y=x为真； 否则，x·y=x为假。所以，无法确定谓词公式①的真值，即谓词公式①不是一个命题。
② 谓词公式②的含义为： 对于任意非负整数x和y，如果x+2=y，则有y+2=x。显然，当x和y的取值分别为0和2时，x+2=y成立，但y+2=x不成立。所以，谓词公式②的真值为假。
③ 谓词公式③的含义为： 对于任意非负整数x和y，都存在非负整数z，使得x+y=z。显然，谓词公式③的真值为真。
④ 谓词公式④的含义为： 存在非负整数x，使得x+x=x·x。显然，x的取值为0或2时，x+x=x·x成立。所以，谓词公式④的真值为真。
从上述例子可以看出，谓词公式在不同的解释下可能有不同的真值。同时，并不是所有的解释下都可以得到谓词公式的真值，换言之，在某些解释下，谓词公式不一定是一个命题，如例5.11中谓词公式(x)Q(g(x，y)，x)在解释I下就不是一个命题。
5.2.3谓词公式的分类
在谓词逻辑中，有的谓词公式在任何解释下真值都为真，有些谓词公式在任何解释下真值都为假，而又有些谓词公式既存在成真解释，又存在成假解释。
定义5.12如果谓词公式A在所有解释下的真值都为真，则称A为永真谓词公式，或者A是永真的，简称为永真公式(always true formula)或重言式(tautology)，用1表示。
例5.12判断下列谓词公式是否为重言式：
① (x)(y)P(x，y)→(y)(x)P(x，y)； 
② (x)(y)Q(x，y)→(y)(x)Q(x，y)； 
③ ((x)P(x)∨(x)Q(x))→(x)(P(x)∨Q(x))； 
④ (x)(P(x)∨Q(x))→((x)P(x)∨(x)Q(x))。
解① 定义解释I： 个体域D为整数集合，P(x，y)指定为“x+y=0”。在解释I下(x)(y)P(x，y)成立。但是，(y)(x)P(x，y)并不成立。所以，谓词公式①不是重言式。
② 如果(x)(y)Q(x，y)成立，那么，存在a使得(y)Q(a，y)成立，即对于y的任意取值，Q(a，y)都成立。从而，(y)(x)Q(x，y)成立。所以，谓词公式②是重言式。
③ 如果(x)(P(x)∨Q(x))为假，则存在a使得�瘙
綈(P(a)∨Q(a))成立，而�瘙
綈(P(a)∨Q(a))�瘙
綈P(a)∧�瘙
綈Q(a)，从而，(x)P(x)为假且(x)Q(x)为假，即(x)P(x)∨(x)Q(x)为假。所以，谓词公式③是重言式。
④ 定义解释I： 个体域D为自然数集合，P(x)指定为“x是奇数”，Q(x)指定为“x是偶数”。在解释I下，(x)(P(x)∨Q(x))成立，但是，(x)P(x)∨(x)Q(x)并不成立。所以，谓词公式④不是重言式。
定义5.13如果至少存在一组解释使谓词公式A的真值为真，则称A为可满足谓词公式，或者A是可满足的，简称为可满足公式(satisfiable formula)。
例5.13判断下列谓词公式哪些是可满足公式：
① (x)(P(x)→Q(x))； 
② (x) (F(x)∧G(x))； 
③ (x)(F(x)∨G(x))→(x)F(x)∨(x)G(x)； 
④ (x)(F(x)∧G(x))→(x)F(x)∧(x)G(x)。 
解① 定义解释I： 个体域D为实数集合，P(x)指定为“x是整数”，Q(x)指定为“x是有理数”。在解释I下，(x)(P(x)→Q(x))成立。所以，谓词公式①是可满足公式。
② 定义解释I： 个体域D为自然数集合，F(x)指定为“x是自然数”，G(x)指定为“x是整数”。在解释I下，(x)(F(x)∧G(x))成立。所以，谓词公式②是可满足公式。
③ 如果(x)(F(x)∨G(x))为真，则存在a使得F(a)∨G(a)成立，即F(a)为真或者G(a)为真，从而(x)F(x)成立或者(x)G(x)成立，即(x)F(x)∨(x)G(x)为真。所以，谓词公式③是可满足公式，也是重言式。
④ 如果(x)(F(x)∧G(x))为真，则存在a使得F(a)∧G(a)成立，即F(a)为真且G(a)为真，从而(x)F(x)成立且(x)G(x)成立，即(x)F(x)∧(x)G(x)为真。所以，谓词公式④是可满足公式，也是重言式。
定义5.14如果谓词公式A在所有解释下的真值都为假，则称A为永假谓词公式，或者A是永假的，简称为永假公式或矛盾式(contradiction)或不可满足公式(unsatisfiable formula)，用0表示。
例5.14判断下列谓词公式哪些是不可满足公式。 
① (x)P(x)∧(x)�瘙
綈P(x)； 
② (x)P(x)∧(x)�瘙
綈P(x)； 
③ (x)F(x)∧(x)G(x)→(x)(F(x)∧G(x))。 
解① 如果(x)�瘙
綈P(x)成立，那么存在a使得�瘙
綈P(a)为真，即存在a使得P(a)为假。从而，(x)P(x)不成立。如果(x)P(x)成立，那么不存在a使得P(a)为假，即不存在a使得�瘙
綈P(a)为真。从而，(x)�瘙
綈P(x)不成立。所以，谓词公式①是不可满足公式。
②  如果(x)�瘙
綈P(x)成立，则不存在a使得�瘙
綈P(a)为假，即不存在a使得P(a)为真。从而，(x)P(x)不成立。如果(x)P(x)成立，那么存在a使得P(a)为真，即存在a使得�瘙
綈P(a)为假。从而，(x)�瘙
綈P(x)不成立。所以，谓词公式②是不可满足公式。
③ 定义解释I： 个体域D为实数集合，F(x)指定为“x是整数”，G(x)指定为“x是自然数”。在x 取值为3时，F(3)为真且G(3)为真，从而(x)F(x)∧(x)G(x)成立且(x)(F(x)∧G(x))成立，即(x)F(x)∧(x)G(x)→(x)(F(x)∧G(x))为真。所以，谓词公式③是可满足公式，不是矛盾式。
从上述3个例子可以看出，判定一个谓词公式是否为重言式或矛盾式，都要求判断所有的解释满足或不满足该谓词公式。而解释依赖于个体域，个体域可以是有限集合，也可以是无限集合。这样解释的“所有”含义实际上是无法考虑的，这使得判断谓词公式是永真的或者永假的实际上异常困难。
5.2.4谓词公式的等值式
不同的谓词公式，在相同解释下的真值不一定相同。如果在所有可能的解释下，两个谓词公式的真值都相同，那么，从逻辑解释角度，它们所表述的含义是相同的，或者说是逻辑等价的。
定义5.15如果谓词公式A和B的等价式AB是重言式，则称谓词公式A与B是逻辑等值的(equivalent)，或者是谓词公式的等值式，简称为等值式(equivalent formula)，记为AB。
例5.15判断下列谓词公式是否逻辑等值：
① �瘙
綈(x)F(x)和(x)�瘙
綈F(x)； 
② �瘙
綈(x)F(x)和(x)�瘙
綈F(x)。
解① 判断�瘙
綈(x)F(x)和(x)�瘙
綈F(x)是否为等值式，就是判断�瘙
綈(x)F(x)(x)�瘙
綈F(x)是否为重言式，也就是判断是否�瘙
綈(x)F(x)→(x)�瘙
綈F(x)为重言式且(x)�瘙
綈F(x)→�瘙
綈(x)F(x)为重言式。
如果�瘙
綈(x)F(x)为真，则存在a使得F(a)为假，即存在a使得�瘙
綈F(a)为真，从而(x)�瘙
綈F(x)为真； 如果(x)�瘙
綈F(x)为真，则存在a使得�瘙
綈F(a)为真，即存在a使得F(a)为假，从而�瘙
綈(x)F(x)为真。所以，�瘙
綈(x)F(x)(x)�瘙
綈F(x)。
② 判断�瘙
綈(x)F(x)和(x)�瘙
綈F(x)是否为等值式，就是判断�瘙
綈(x)F(x)(x)�瘙
綈F(x)是否为重言式，也就是判断是否�瘙
綈(x)F(x)→(x)�瘙
綈F(x)为重言式且(x)�瘙
綈F(x)→�瘙
綈(x)F(x)为重言式。
如果�瘙
綈(x)F(x)为真，则不存在a使得F(a)为真，即所有x使得F(x)为假，从而(x)�瘙
綈F(x)为真； 如果(x)�瘙
綈F(x)为真，则所有x使得F(x)为假，即不存在a使得F(a)为真，从而�瘙
綈(x)F(x)为真。所以，�瘙
綈(x)F(x)(x)�瘙
綈F(x)。
定义5.16设P是含有命题变元p1，p2，p3，…，pn的命题公式，A1，A2，A3，…，An是n 个谓词公式，用谓词公式Ai(i=1，2，…，n)替换P中命题变元pi(i=1，2，…，n)的所有出现，所得到的谓词公式称为P的代换实例(substitute instance)。
例如，(x)F(x)→(x)G(x)，F(x)→(x)G(x)和(x)F(x)→(x)G(x)都是p→q的代换实例。但是，(x)(F(x)→(x)G(x))、(x)(F(x)→G(x))和(x)(F(x)→G(x))则不是p→q的代换实例。
定理5.1重言式的代换实例是重言式，矛盾式的代换实例是矛盾式。
定理5.1的证明从略。
例5.16判断下列谓词公式是否逻辑等值：
① (x)F(x)→(x)G(x)和�瘙
綈(x)F(x)∨(x)G(x)； 
② (x)F(x)∨�瘙
綈(x)G(x)和�瘙
綈(x)F(x)→�瘙
綈(x)G(x)； 
③ �瘙
綈((x)F(x)∨(x)G(x))和�瘙
綈(x)F(x)∧�瘙
綈(x)G(x)； 
④ �瘙
綈((x)F(x)∧(x)G(x))和�瘙
綈(x)F(x)∨�瘙
綈(x)G(x)。
解① 在命题公式(p→q)(�瘙
綈p∨q)中，将p替换为(x)F(x)，将q替换为(x)G(x)，可得代换实例((x)F(x)→(x)G(x))(�瘙
綈(x)F(x)∨(x)G(x))。由于，(p→q)(�瘙
綈p∨q)为重言式，所以，((x)F(x)→(x)G(x))(�瘙
綈(x)F(x)∨(x)G(x))为重言式，即(x)F(x)→(x)G(x)�瘙
綈(x)F(x)∨(x)G(x)。
② 在命题公式(p∨�瘙
綈q)(�瘙
綈p→�瘙
綈q)中，将p替换为(x)F(x)，将q替换为(x)G(x)，可得代换实例((x)F(x)∨�瘙
綈(x)G(x))(�瘙
綈(x)F(x)→�瘙
綈(x)G(x))。由于(p∨�瘙
綈q)(�瘙
綈p→�瘙
綈q)为重言式，所以，((x)F(x)∨�瘙
綈(x)G(x))(�瘙
綈(x)F(x)→
�瘙
綈(x)G(x))为重言式，即
(x)F(x)∨�瘙
綈(x)G(x)�瘙
綈(x)F(x)→�瘙
綈(x)G(x)。
③ 在命题公式�瘙
綈(p∨q)(�瘙
綈p∧�瘙
綈q)中，将p替换为(x)F(x)，将q替换为(x)G(x)，可得代换实例�瘙
綈((x)F(x)∨(x)G(x))
(�瘙
綈(x)F(x)∧�瘙
綈(x)G(x))。由于，�瘙
綈(p∨q)(�瘙
綈p∧�瘙
綈q)为重言式，所以，�瘙
綈((x)F(x)∨(x)G(x))
(�瘙
綈(x)F(x)∧�瘙
綈(x)G(x))为重言式，即�瘙
綈((x)F(x)∨(x)G(x))
�瘙
綈(x)F(x)∧�瘙
綈(x)G(x)。
④ 在命题公式�瘙
綈(p∧q)(�瘙
綈p∨�瘙
綈q)中，将p替换为(x)F(x)，将q替换为(x)G(x)，可得代换实例
�瘙
綈((x)F(x)∧(x)G(x))(�瘙
綈(x)F(x)∨�瘙
綈(x)G(x))。由于，�瘙
綈(p∧q)(�瘙
綈p∨�瘙
綈q)为重言式，所以，
�瘙
綈((x)F(x)∧(x)G(x))(�瘙
綈(x)F(x)∨�瘙
綈(x)G(x))为重言式，即
�瘙
綈((x)F(x)∧(x)G(x))�瘙
綈(x)F(x)∨�瘙
綈(x)G(x)。
类似于命题逻辑的等值式，人们已经证明了一些重要的谓词逻辑等值式。利用这些等值式，就可以推演出更多的等值式，这一过程称为谓词逻辑的等值演算，简称为等值演算(equivalent calculus)。
下面给出一些基本的等值式(设A(x)、B(x)是含有个体变元x的自由出现的谓词公式，B中不含有x的出现，P(x，y)是含有个体变元x和y的自由出现的谓词公式)。
(1) 命题逻辑中等值式的推广： 命题公式中的重言式的代换实例都是谓词公式的重言式，因此命题逻辑中的所有基本等值式的代换实例都是谓词公式的等值式。举例如下。 
幂等律： 
① (x)A(x)∨(x)A(x)  (x)A(x)；
② (x)A(x)∧(x)A(x)  (x)A(x)；
③ (x)A(x)∨(x)A(x)  (x)A(x)；
④ (x)A(x)∧(x)A(x)  (x)A(x)。
排中律： 
① (x)A(x)∨�瘙
綈(x)A(x) 1；
② (x)A(x)∨�瘙
綈(x)A(x) 1。
矛盾律： 
① (x)A(x)∧�瘙
綈(x)A(x) 0；
② (x)A(x)∧�瘙
綈(x)A(x) 0。
(2) 量词消去律(设个体域为有限集D={a1，a2，a3，…，an})：
① (x)A(x)  A(a1)∧A(a2)∧…∧A(an)；
② (x)A(x)  A(a1)∨A(a2)∨…∨A(an)。
(3) 量词与否定的交换律：
① �瘙
綈(x)A(x)(x)�瘙
綈A(x)；
② �瘙
綈(x)A(x)(x)�瘙
綈A(x)。
(4) 量词辖域的收缩与扩张律：
①  (x)(A(x)∨B)  (x)A(x)∨B； 
②  (x)(A(x)∧B)  (x)A(x)∧B；
③  (x)(A(x)∨B)  (x)A(x)∨B；
④  (x)(A(x)∧B)  (x)A(x)∧B；
⑤  (x)(A(x)→B)  (x)A(x)→B；
⑥  (x)(B→A(x))  B→(x)A(x)；
⑦ (x)(A(x)→B)  (x)A(x)→B；
⑧ (x)(B→A(x))  B→(x)A(x)。
(5) 量词分配律：
① (x)A(x)∧(x)B(x)  (x)(A(x)∧B(x))；
② (x)A(x)∨(x)B(x)  (x)(A(x)∨B(x))；
③ (x)A(x)∨(x)B(x)  (x)(y)(A(x)∨B(y))；
④ (x)A(x)∧(x)B(x)  (x)(y)(A(x)∧B(y))；
⑤ (x)(A(x)→B(x))  (x)A(x)→(x)B(x)。
(6) 双量词交换律：
① (x)(y)P(x，y) (y)(x)P(x，y)；
② (x)(y)P(x，y) (y)(x)P(x，y)。
谓词公式的等值演算，除了要使用上述这些基本等值式外，还要用到以下规则。 
(1) 置换规则： 在含有谓词公式A的谓词公式Φ(A)中，将所有谓词公式A的出现用谓词公式B来替换，得到新的谓词公式Φ(B)，如果AB，那么Φ(A)Φ(B)。
(2) 换名规则： 在谓词公式A中，对某量词辖域内的某约束变元的所有约束出现及相应的指导变元用该量词辖域中未曾出现过的个体变元替换，得到谓词公式B，则AB。
(3) 代替规则： 在谓词公式A中，对某自由出现的个体变元的所有自由出现用A中未曾出现过的个体变元替换，得到谓词公式B，则AB。
例5.17证明下列谓词公式的等值式：
① (x)(A(x)∨B)  (x)A(x)∨B； 
② (x)(A(x)∧B)  (x)A(x)∧B； 
③ (x)(A(x)∧B)  (x)A(x)∧B； 
④ (x)(A(x)→B)  (x)A(x)→B； 
⑤ (x)A(x)∧(x)B(x)  (x)(A(x)∧B(x))； 
⑥ (x)A(x)∨(x)B(x)  (x)(A(x)∨B(x))；  
⑦ (x)(B→A(x))  B→(x)A(x)； 
⑧ (x)(A(x)→B(x))  (x)A(x)→(x)B(x)。
证明① (x)A(x)∨B0，当且仅当(x)A(x)0且B0，当且仅当B0且任意a使得A(a)0，当且仅当 (x)(A(x)∨B)0。
所以，(x)(A(x)∨B)  (x)A(x)∨B。
②  (x)A(x)∧B1，当且仅当(x)A(x)1且B1，当且仅当B1且任意a使得A(a)1，当且仅当(x)(A(x)∧B)1。
所以，(x)(A(x)∧B)  (x)A(x)∧B。
③ (x)(A(x)∧B) 
 �瘙
綈�瘙
綈((x)(A(x)∧B))
 �瘙
綈(�瘙
綈(x)(A(x)∧B))
 �瘙
綈((x)(�瘙
綈A(x)∨�瘙
綈B))
 �瘙
綈((x)�瘙
綈A(x)∨�瘙
綈B)
 �瘙
綈(x)�瘙
綈A(x)∧�瘙
綈�瘙
綈B
 (x)�瘙
綈�瘙
綈A(x)∧B
 (x)A(x)∧B
④ (x)(A(x)→B) 
 (x)(�瘙
綈A(x)∨B)
 (x)�瘙
綈A(x)∨B
 �瘙
綈(x)A(x)∨B
 (x)A(x)→B
⑤  (x)(A(x)∧B(x))  1，当且仅当任意a使得A(a)∧B(a)  1，当且仅当任意a使得A(a)  1且B(a)  1，当且仅当 (x)A(x) 1且(x)B(x) 1，当且仅当 (x)A(x)∧(x)B(x)  1。
所以，(x)A(x)∧(x)B(x)  (x)(A(x)∧B(x))。
⑥ (x)(A(x)∨B(x))
 �瘙
綈�瘙
綈(x)(A(x)∨B(x))
 �瘙
綈(�瘙
綈(x)(A(x)∨B(x)))
 �瘙
綈((x)(�瘙
綈A(x)∧�瘙
綈B(x)))
 �瘙
綈((x)�瘙
綈A(x)∧(x)�瘙
綈B(x))
 �瘙
綈(x)�瘙
綈A(x)∨�瘙
綈(x)�瘙
綈B(x)
 (x)�瘙
綈�瘙
綈A(x)∨(x)�瘙
綈�瘙
綈B(x)
 (x)A(x)∨(x)B(x)
⑦  (x)(B→A(x)) 
 (x)(�瘙
綈B∨A(x))
 (x)�瘙
綈B∨(x)A(x)
 �瘙
綈B∨(x)A(x)
 B→(x)A(x)
⑧  (x)(A(x)→B(x)) 
 (x)(�瘙
綈A(x)∨B(x)) 
 (x)�瘙
綈A(x)∨(x)B(x) 
 �瘙
綈(x)A(x)∨(x)B(x)
 (x)A(x)→(x)B(x)
例5.18设个体域为D={a，b，c}，消去下列谓词公式中的量词：
① (x)A(x)→(x)B(x)；  
② (x)(A(x)∨(y)B(y))； 
③ (x)(y)P(x，y)； 
④ (x)(y)P(x，y)； 
⑤ (x)(y)(A(x)∨B(y))； 
⑥ (x)(A(x)→(x)B(x))。
解① (x)A(x)→(x)B(x) 
 (A(a)∨A(b)∨A(c))→(B(a)∧B(b)∧B(c))
②  (x)(A(x)∨(y)B(y)) 
 (x)(A(x)∨(B(a)∨B(b)∨B(c))) 
 (A(a)∨(B(a)∨B(b)∨B(c)))∧(A(b)∨(B(a)∨B(b)∨B(c)))∧(A(c)∨(B(a)∨B(b)∨B(c)))
 (A(a)∧A(b)∧A(c))∨(B(a)∨B(b)∨B(c))
③  (x)(y)P(x，y) 
 (x)(P(x，a)∨P(x，b)∨P(x，c)) 
 (P(a，a)∨P(a，b)∨P(a，c))∨(P(b，a)∨P(b，b)∨P(b，c))∨(P(c，a)∨P(c，b)∨P(c，c))
④  (x)(y)P(x，y) 
 (x)(P(x，a)∧P(x，b)∧P(x，c)) 
 (P(a，a)∧P(a，b)∧P(a，c))∨(P(b，a)∧P(b，b)∧P(b，c))∨(P(c，a)∧P(c，b)∧P(c，c))
⑤  (x)(y)(A(x)∨B(y))
 (x)((A(x)∨B(a))∨(A(x)∨B(b))∨(A(x)∨B(c)))
 (x)(A(x)∨B(a)∨B(b)∨B(c))
 (A(a)∨B(a)∨B(b)∨B(c))∧(A(b)∨B(a)∨B(b)∨B(c))∧(A(c)∨B(a)∨B(b)∨B(c))
(A(a)∧A(b)∧A(c))∨(B(a)∨B(b)∨B(c))
⑥  (x)(A(x)→(x)B(x)) 
 (x)(A(x)→(B(a)∨B(b)∨B(c))) 
 (A(a)→(B(a)∨B(b)∨B(c)))∧(A(b)→(B(a)∨B(b)∨B(c)))∧(A(c)→(B(a)∨B(b)∨B(c)))
例5.19给定解释I： 
个体域D={2，3}； 
个体常量a指定为2； 
函词f(x) 指定为f(2)=3，f(3)=2； 
谓词P(x，y)指定为P(2，2)=P(2，3)=P(3，2)=1，P(3，3)=0； 
谓词Q(x，y)指定为Q(2，2)=Q(3，3)=1，Q(2，3)=Q(3，2)=0； 
谓词G(x)指定为G(2)=0，G(3)=1。
求下列各谓词公式的真值：
① (x)(G(x)∨P(a，x))； 
② (x)(G(f(x))∨Q(f(x)，x))； 
③ (x)(y)Q(x，y)； 
④ (y)(x)Q(x，y)。
解① (x)(G(x)∨P(a，x)) 
 (x)(G(x)∨P(2，x)) 
 (G(2)∨P(2，2))∧(G(3)∨P(2，3)) 
 (0∨1)∧(1∨1) 
 1
② (x)(G(f(x))∨Q(f(x)，x)) 

 (G(f(2))∨Q(f(2)，2))∨(G(f(3))∨Q(f(3)，3))

 (G(3)∨Q(3，2))∨(G(2)∨Q(2，3)) 

 (1∨0)∨(0∨0) 

 1
③ (x)(y)Q(x，y)

 (x)(Q(x，2)∨Q(x，3)) 

 (Q(2，2)∨Q(2，3))∧(Q(3，2)∨Q(3，3))

 (1∨0)∧(0∨1) 

 1
④ (y)(x)Q(x，y)

 (y)(Q(2，y)∧Q(3，y))

 (Q(2，2)∧Q(3，2))∨(Q(2，3)∧Q(3，3)) 

 (1∧0)∨(0∧1) 

 0
在解释I下，谓词公式(x)(y)Q(x，y)和(y)(x)Q(x，y)的真值不同。由此可以看出，量词的次序并不一定能随意调换。
例5.20证明下列谓词公式的等值式：
① �瘙
綈(x)(A(x)∧B(x))  (x)(A(x)→�瘙
綈B(x))； 
② �瘙
綈(x)(A(x)→B(x))  (x)(A(x)∧�瘙
綈B(x))； 
③ �瘙
綈(x)(y)(A(x)∧B(y)→P(x，y)) (x)(y)(A(x)∧B(y)∧�瘙
綈P(x，y))； 
④ �瘙
綈(x)(y)(A(x)∧B(y)∧P(x，y))  (x)(y)(A(x)∧B(y)→�瘙
綈P(x，y))； 
⑤ (x)A(x)→B(x)  (y)(A(y)→B(x))； 
⑥ �瘙
綈(x)(A(x)∨B(x)→B(x))  (x)(A(x)∧�瘙
綈B(x))。
证明① �瘙
綈(x)(A(x)∧B(x)) 
 (x)�瘙
綈(A(x)∧B(x)) 
 (x)(�瘙
綈A(x)∨�瘙
綈B(x))
 (x)(A(x)→�瘙
綈B(x))
② �瘙
綈(x)(A(x)→B(x)) 

 (x)�瘙
綈(A(x)→B(x)) 

 (x)�瘙
綈(�瘙
綈A(x)∨B(x)) 

 (x)(�瘙
綈�瘙
綈A(x)∧�瘙
綈B(x)) 

 (x)(A(x)∧�瘙
綈B(x))
③ �瘙
綈(x)(y)(A(x)∧B(y)→P(x，y))

 (x)�瘙
綈(y)(A(x)∧B(y)→P(x，y))

 (x)(y)�瘙
綈(A(x)∧B(y)→P(x，y)) 

 (x)(y)�瘙
綈(�瘙
綈(A(x)∧B(y))∨P(x，y)) 

 (x)(y)(�瘙
綈�瘙
綈(A(x)∧B(y))∧�瘙
綈P(x，y)) 

 (x)(y)(A(x)∧B(y)∧�瘙
綈P(x，y))
④ �瘙
綈(x)(y)(A(x)∧B(y)∧P(x，y)) 

 (x)�瘙
綈(y)(A(x)∧B(y)∧P(x，y)) 

 (x)(y)�瘙
綈(A(x)∧B(y)∧P(x，y)) 

 (x)(y)(�瘙
綈(A(x)∧B(y))∨�瘙
綈P(x，y)) 

 (x)(y)(A(x)∧B(y)→�瘙
綈P(x，y))
⑤ (x)A(x)→B(x) 

 �瘙
綈(x)A(x)∨B(x) 

 (x)�瘙
綈A(x)∨B(x) 

 (y)�瘙
綈A(y)∨B(x) 

 (y)(�瘙
綈A(y)∨B(x)) 

 (y)(A(y)→B(x))
⑥  �瘙
綈(x)(A(x)∨B(x)→B(x)) 

 (x)�瘙
綈(�瘙
綈(A(x)∨B(x))∨B(x)) 

 (x)((A(x)∨B(x))∧�瘙
綈B(x)) 

 (x)((A(x)∧�瘙
綈B(x))∨(B(x)∧�瘙
綈B(x))) 

 (x)((A(x)∧�瘙
綈B(x))∨0) 

(x)(A(x)∧�瘙
綈B(x))
5.2.5谓词公式的范式
在命题逻辑中，命题公式都可以转换为与之等值的规范型或范式，范式对于命题公式的研究具有重要的作用。类似地，对于谓词公式来说，也有规范型，即谓词公式的范式(normal form)。
定义5.17对于谓词公式G，如果G中的所有量词都位于表达式的最左端，且量词的辖域都延伸到该公式的末端，即具有形式
(Q1x1)(Q2x2)…(Qnxn) M(x1，x2，…，xn)

式中，Qi (i=1，2，…，n)为量词或； M(x1，x2，…，xn)中不含有量词，则称G为谓词公式的前束范式，简称为前束范式(prenex normal form)，并称M(x1，x2，…，xn)为G的母式(matrix)。
例如，(x)(y)(A(x)∨B(y)→�瘙
綈P(x，y))和(x)(y)(z)(A(x)∧B(y，z)∧P(x，y，z))及(x)(y)(P(x，y)→A(x，y))都是前束范式，而(x)(y)(A(x)∧B(y)→�瘙
綈(y)P(x，y))和(x)�瘙
綈(y)P(x，y，z)以及(y)(z)(A(x)∧B(y，z)∧(x)P(x，y，z))和(y)(P(y)→(x)A(x，y))都不是前束范式。
定理5.2任意谓词公式都存在与之等值的前束范式。
证明对于任意谓词公式G，可通过下述步骤将其转化为与之等值的前束范式： 
步骤一，消去谓词公式中的联结词“→”“”； 
步骤二，运用德·摩根律，将“�瘙
綈”移到原子谓词公式的前端； 
步骤三，通过谓词等值公式将所有量词移到公式的前端。
经过上述步骤，便可求得谓词公式G的前束范式，由于每一步骤都是采用谓词公式的等值演算，所以，得到的前束范式与原谓词公式G等值。证毕。
例5.21求下列谓词公式的前束范式：
① (x)A(x)∧�瘙
綈(x)B(x)； 
② (x)(A(x)∨�瘙
綈(y)B(x，y))； 
③ (x)(y)A(x，y)→(x)B(x)； 
④ �瘙
綈(x)A(x，y)→(y)�瘙
綈B(x，y)； 
⑤ (x)A(x)→((y)B(y)→(x)B(x))； 
⑥ (x)(P(x，y)→(y)B(y))→(x)Q(x，y)。
解① (x)A(x)∧�瘙
綈(x)B(x) 

 (x)A(x)∧(x)�瘙
綈B(x) 

 (x)(A(x)∧�瘙
綈B(x))
② (x)(A(x)∨�瘙
綈(y)B(x，y)) 

 (x)(A(x)∨(y)�瘙
綈B(x，y)) 

 (x)(y)(A(x)∨�瘙
綈B(x，y))
③ (x)(y)A(x，y)→(x)B(x) 

 �瘙
綈(x)(y)A(x，y)∨(x)B(x) 

 (x)�瘙
綈(y)A(x，y)∨(x)B(x) 

 (x)(y)�瘙
綈A(x，y)∨(x)B(x) 

 (x)((y)�瘙
綈A(x，y)∨B(x)) 

 (x)(y)(�瘙
綈A(x，y)∨B(x))
④ �瘙
綈(x)A(x，y)→(y)�瘙
綈B(x，y) 

 �瘙
綈�瘙
綈(x)A(x，y)∨(y)�瘙
綈B(x，y)

 (x)A(x，y)∨(y)�瘙
綈B(x，y)

 (x)A(x，u)∨(y)�瘙
綈B(v，y)

 (x)(y)(A(x，u)∨�瘙
綈B(v，y))
⑤ (x)A(x)→((y)B(y)→(x)B(x)) 

 �瘙
綈(x)A(x)∨(�瘙
綈(y)B(y)∨(x)B(x)) 

 (x)�瘙
綈A(x)∨(y)�瘙
綈B(y)∨(z)B(z) 

 (x)(y)(z)(�瘙
綈A(x)∨�瘙
綈B(y)∨B(z))
⑥ (x)(P(x，y)→(y)B(y))→(x)Q(x，y) 

 �瘙
綈(x)(�瘙
綈P(x，y)∨(y)B(y))∨(x)Q(x，y)

 (x)�瘙
綈(�瘙
綈P(x，y)∨(y)B(y))∨(x)Q(x，y)

 (x)(�瘙
綈�瘙
綈P(x，y)∧�瘙
綈(y)B(y))∨(x)Q(x，y) 

 (x)(P(x，y)∧(y)�瘙
綈B(y))∨(x)Q(x，y) 

 (x)(P(x，z)∧(y)�瘙
綈B(y))∨(u)Q(u，z) 

 (x)(y)(P(x，z)∧�瘙
綈B(y))∨(u)Q(u，z) 

 (x)(y)(u) ((P(x，z)∧�瘙
綈B(y))∨Q(u，z))
例5.22举例说明谓词公式的前束范式并不唯一。
解考察谓词公式(x)A(x)∨�瘙
綈(x)B(x)，进行以下等值演算： 
(x)A(x)∨�瘙
綈(x)B(x) 
 (x)A(x)∨(x)�瘙
綈B(x) 
 (x)A(x)∨(y)�瘙
綈B(y) 
 (x)(A(x)∨(y)�瘙
綈B(y)) 
 (x)(y)(A(x)∨�瘙
綈B(y))
(x)A(x)∨�瘙
綈(x)B(x)
 (x)A(x)∨(x)�瘙
綈B(x) 
 (x)(A(x)∨�瘙
綈B(x))
显然，(x)(y)(A(x)∨�瘙
綈B(y))和(x)(A(x)∨�瘙
綈B(x))都是谓词公式(x)A(x)∨�瘙
綈(x)B(x)的前束范式。所以，谓词公式的前束范式不一定唯一。
定义5.18对于谓词公式G的前束范式(Q1x1)(Q2x2)… (Qnxn)M(x1，x2，…，xn)，通过下列方式消去G中的存在量词，所得到的不含有存在量词的表达式称为G的斯柯伦标准型(Skolem standard form)或斯柯伦范式(Skolem normal form)。
① 如果Qi是存在量词，且Qi的左边没有全称量词，则直接用一个不同于M(x1，x2，…，xn)中任何其他个体常量的个体常量a来取代xi在M(x1，x2，…，xn)中的一切出现。 
② 如果Qi是存在量词，且Qi的左边有全称量词(xj)，(xk)，…，(xr)，则直接用一个不同于M(x1，x2，…，xn)中任何其他函词的函词f(xj，xk，…，xr)来取代xi在M(x1，x2，…，xn)中的一切出现。
例5.23求下列谓词公式的斯柯伦范式：
① (x)(y)(�瘙
綈A(x，y)∨B(x))； 
② (x)(y)(z)(A(x)∧B(y，z)∧P(x，y，z))； 
③ (x)(y)(z)(u)(v)(w)P(x，y，z，u，v，w)。
解① 由于(y)左边有全称量词(x)，所以用一个函词f(x)来代替谓词公式中的y，并消去(y)。可得谓词公式①的斯柯伦范式为
(x)(�瘙
綈A(x，f(x))∨B(x))
② 由于(x)左边没有全称量词，所以直接用一个个体常量a来代替谓词公式中的x，并消去(x)； 由于(z)左边有全称量词(y)，所以用一个函词f(y)来代替谓词公式中的z，并消去(z)。可得谓词公式②的斯柯伦范式为
(y)(A(a)∧B(y，f(y))∧P(a，y，f(y)))
③ 由于(x)左边没有全称量词，所以直接用一个个体常量a来代替谓词公式③中的x，并消去(x)； 由于(u)左边有全称量词(y)和(z)，所以用一个函词f(y，z)来代替谓词公式③中的u，并消去(u)； 由于(w)左边有全称量词(y)和(z)及(v)，所以用一个函词g(y，z，v)来代替谓词公式③中的w，并消去(w)。可得谓词公式③所对应的斯柯伦范式为
(y)(z)(v)P(a，y，z，f(y，z)，v，g(y，z，v))
值得说明的是，前束范式并不一定与其斯柯伦范式等值。例如，(x)A(x)的斯柯伦范式为A(a)，但(x)A(x)和A(a)不等值。因为，对于解释I： 个体域D={1，2}，A(1)=0，A(2)=1，显然，当a指定为1时，A(a)和(x)A(x)的真值不同。尽管如此，斯柯伦范式有定理5.3和定理5.4表述的重要性质。
定理5.3设S是谓词公式G的斯柯伦范式，G是可满足公式当且仅当S是可满足公式。
证明对于谓词公式G的前束范式(Q1x1)(Q2x2)…(Qnxn)M(x1，x2，…，xn)，设Qr是G中从最左端开始第一个出现的存在量词，令

G1=(x1)…(xr-1)(Qr+1xr+1) … (Qnxn)M(x1，…，xr-1，
f(x1，…，xr-1)，xr+1，…，xn)

式中，f(x1，…，xr-1)为替换xr的函词。
设个体域为D，取一个使G1为真的解释I。那么，对每一组(x′1，…，x′r-1)∈Dr-1，都有f(x′1，…，x′r-1)∈D，使得(Qr+1xr+1)…(Qnxn)M(x′1，…，x′r-1，f(x′1，…，x′r-1)，…，xn)在解释I下真值为真。从而，(x1)…(xr-1)(xr)(Qr+1xr+1) … (Qnxn) M(x1，x2，…，xn)在解释I下真值为真。
反之，取一个使G为真的解释I。那么，对每一组(x′1，…，x′r-1)∈Dr-1，都存在x′r∈D，使得(Qr+1xr+1) … (Qnxn)M(x′1，…，x′r-1，x′r，…，xn)在解释I下真值为真。现将解释I扩展为解释I′，使其包含对函词f(x1，…，xr-1)的以下指定： 对于每一组(x′1，…，x′r-1)∈Dr-1，f(x′1，…，x′r-1)=x′r。于是，在解释I′下G1的真值为真。
同理，对G1从左往右找下一个存在量词，用定义5.18中的方式构造函词，进行个体变元代替得到G2，则G1的可满足性等价于G2的可满足性。以此类推，可以证明谓词公式G的可满足性等价于其斯柯伦范式S的可满足性。证毕。
例如，谓词公式G=(x)(y)A(x，y)的斯柯伦范式为S=(x)A(x，f(x))。设个体域D={1，2}，取解释I： 
函词f(x)指定为f(1)=2，f(2)=1；
谓词A(x，y)指定为A(1，1)=0，A(1，2)=1，A(2，1)=1，A(2，2)=0。显然，在解释I下，S的真值为

(x)A(x，f(x))A(1，f(1))∧A(2，f(2))A(1，2)∧A(2，1)1∧11

在解释I下，G的真值为

(x)(y)A(x，y)(x)(A(x，1)∨A(x，2))

(A(1，1)∨A(1，2))∧(A(2，1)∨A(2，2))1∧11

反之，取解释I： 
谓词A(x，y)指定为A(1，1)=1，A(1，2)=0，A(2，1)=1，A(2，2)=0。
显然，在解释I下，G的真值为

(x)(y)A(x，y)(x)(A(x，1)∨A(x，2))(A(1，1)∨A(1，2))∧

(A(2，1)∨A(2，2))1∧11

扩展解释I为I′： 
函词f(x)指定为f(1)=1,f(2)=1； 
谓词A(x，y)指定为A(1，1)=1，A(1，2)=0，A(2，1)=1，A(2，2)=0。
在解释I下，S的真值为

(x)A(x，f(x))A(1，f(1))∧A(2，f(2))A(1，1)∧A(2，1)1∧1  1。

由上述知，谓词公式G=(x)(y)A(x，y)与其斯柯伦范式为S=(x)A(x，f(x))的可满足性等价。
定理5.4设S是谓词公式G的斯柯伦范式，G是不可满足的当且仅当S是不可满足的。
定理5.4的证明从略。

5.3谓词逻辑推理
谓词逻辑是命题逻辑的进一步发展，因此命题逻辑的推理理论在谓词逻辑中几乎可以完全照搬，只不过谓词逻辑所涉及的是谓词公式。谓词逻辑推理(predicate logic reasoning)是由已知的谓词公式为前提推出作为结论的谓词公式的过程。
定义5.19对于谓词公式A和B，如果蕴含式A→B是永真的，那么称该蕴含式为谓词公式的永真蕴含式或谓词公式的重言蕴含式，简称为永真蕴含式(always true implication)或重言蕴含式(tautology implication)，记为AB。
例5.24判断下列谓词公式的蕴含式是否为永真蕴含式：
① (x)A(x) →(x)A(x)∨B(x，y)； 
② (x)A(x)∧(�瘙
綈(x)A(x)∨B(x)) →(x)A(x)； 
③ �瘙
綈((x)A(x)∧(y)B(y)) →�瘙
綈(x)A(x)∨�瘙
綈(y)B(y)； 
④ (x)(A(x)∨B(x)) →(x)A(x)∨(x)B(x)。
解 ① (x)A(x) →(x)A(x)∨B(x，y) 

 �瘙
綈(x)A(x)∨((x)A(x)∨B(x，y)) 

 (�瘙
綈(x)A(x)∨(x)A(x))∨B(x，y) 

 1∨B(x，y) 

 1
所以，(x)A(x)  (x)A(x)∨B(x，y)。
② (x)A(x)∧(�瘙
綈(x)A(x)∨B(x)) →(x)A(x)

 �瘙
綈((x)A(x)∧(�瘙
綈(x)A(x)∨B(x)))∨(x)A(x)

 (�瘙
綈(x)A(x)∨�瘙
綈(�瘙
綈(x)A(x)∨B(x)))∨(x)A(x)

 (�瘙
綈(x)A(x)∨(x)A(x))∨�瘙
綈(�瘙
綈(x)A(x)∨B(x)) 

 1∨�瘙
綈(�瘙
綈(x)A(x)∨B(x)) 

 1
所以，(x)A(x)∧(�瘙
綈(x)A(x)∨B(x))  (x)A(x)。
③ �瘙
綈((x)A(x)∧(y)B(y)) →�瘙
綈(x)A(x)∨�瘙
綈(y)B(y) 

 �瘙
綈�瘙
綈((x)A(x)∧(y)B(y))∨�瘙
綈(x)A(x)∨�瘙
綈(y)B(y) 

 ((x)A(x)∧(y)B(y))∨�瘙
綈(x)A(x)∨�瘙
綈(y)B(y) 

 (((x)A(x)∨�瘙
綈(x)A(x))∧((y)B(y)∨�瘙
綈(x)A(x)))∨�瘙
綈(y)B(y) 

 (1∧((y)B(y)∨�瘙
綈(x)A(x)))∨�瘙
綈(y)B(y) 

 ((y)B(y)∨�瘙
綈(y)B(y))∨�瘙
綈(x)A(x) 

 1∨�瘙
綈(x)A(x) 

 1
所以，�瘙
綈((x)A(x)∧(y)B(y))  �瘙
綈(x)A(x)∨�瘙
綈(y)B(y)。 
④ 取解释I： 个体域D为自然数集合，谓词A(x)表示“x是偶数”，谓词B(x)表示“x是奇数”。显然，在解释I下，(x)(A(x)∨B(x))为真，(x)A(x)为假，(x)B(x)为假。从而，(x)A(x)∨(x)B(x)为假，即(x)(A(x)∨B(x))→(x)A(x)∨(x)B(x)的真值为假。所以，蕴含式④不是永真蕴含式。 
命题逻辑中介绍的重言蕴含式，在谓词逻辑中的代换实例都是谓词逻辑的永真蕴含式。同时，由于等价式和蕴含式之间的关系，每一个等值式均可当作两个永真蕴含式来使用。例如，下列都是永真蕴含式。
(x)A(x)  (x)A(x)∨(y)B(y)(附加式)
(x)A(x)∧((x)A(x)→(y)B(y)) (y)B(y)(假言推论)
�瘙
綈(y)B(y)∧((x)A(x)→(y)B(y))  �瘙
綈(x)A(x) (拒取式)
�瘙
綈((x)A(x)∧(x)B(x，y))  �瘙
綈(x)A(x)∨�瘙
綈(x)B(x，y)(德·摩根律)
�瘙
綈(x)A(x)∨�瘙
綈(x)B(x，y)  �瘙
綈((x)A(x)∧(x)B(x，y))(德·摩根律)
在谓词逻辑中，增加了量词这一新要素，为此下面给出关于量词分配的几个常用的永真蕴含式： 
① (x)A(x)∨(x)B(x)  (x)(A(x)∨B(x))； 
② (x)(A(x)∧B(x))  (x)A(x)∧(x)B(x)； 
③ (x)(A(x)→B(x))  (x)A(x)→(x)B(x)； 
④ (x)(A(x)→B(x))  (x)A(x)→(x)B(x)； 
⑤ (x)(y)A(x，y)  (x)A(x，x)； 
⑥ (x)A(x，x)  (x)(y)A(x，y)； 
⑦ (x)(y)A(x，y)  (y)(x)A(x，y)。
例5.25证明下列永真蕴含式：
① (x)(A(x)→B(x))  (x)A(x)→(x)B(x)； 
② (x)(y)A(x，y)  (x)A(x，x)； 
③ (x)A(x，x)  (x)(y)A(x，y)； 
④ (x)(y)(A(x) B(y))  (x)A(x)  (y)B(y)。
证明① 如果(x)(A(x)→B(x))为真，那么必有a使A(a)→B(a)为真。进而，如果A(a)为真，则B(a)为真，即(x)A(x)→(x)B(x)为真。所以，(x)(A(x)→B(x))(x)A(x)→(x)B(x)。
② 如果(x)(y)A(x，y)为真，那么任意x和y使得 A(x，y)为真，从而任意x使得A(x，x)为真，即(x)A(x，x)为真。所以，(x)(y)A(x，y)  (x)A(x，x)。
③ 如果(x)A(x，x)为真，那么存在a使得A(a，a)为真，从而(x)(y)A(x，y)为真。所以，(x)A(x，x)  (x)(y)A(x，y)。
④ (x)(y)(A(x) B(y)) 

 (x)(A(x) B(x))

 (x)((A(x)→B(x))∧(B(x)→A(x)))

 (x)(A(x)→B(x))∧(x)(B(x)→A(x)) 

 ((x)A(x)→(x)B(x))∧((x)B(x)→(x)A(x))

 (x)A(x)  (y)B(y)
定义5.20对于谓词公式A1，A2，…，An和B，如果A1∧A2∧…∧An→B是永真蕴含式，则称谓词公式A1，A2，…，An到谓词公式B是一个有效推理(effective reasoning)，或者称谓词公式A1，A2，…，An到谓词公式B的推理是有效的(effective)或正确的。并称谓词公式A1，A2，…，An是推理的前提(premise)，谓词公式B是以谓词公式A1，A2，…，An为前提的推理的逻辑结果(logic conclusion)或有效结论(effective conclusion)，并记为A1，A2，…，AnB，或A1∧A2∧…∧AnB。
例如，对于谓词公式(x)A(x)和(x)A(x)→(y)B(y)及(y)B(y)，由于(x)A(x)∧((x)A(x)→(y)B(y))(y)B(y)，所以，谓词公式(y)B(y)是谓词公式(x)A(x)和(x)A(x)→(y)B(y)的有效结论，或者，谓词公式(x)A(x)和(x)A(x)→(y)B(y)到谓词公式(y)B(y)是一个有效推理，并记为 (x)A(x)，(x)A(x)→(y)B(y)(y)B(y)。
在谓词逻辑推理中，推理的前提和结论中可能存在受到量词约束的个体变元。为了确立前提和结论之间的内在联系，必须适时地消去和添加量词。下面给出几个量词有关的量词消去或引入规则。
全称量词消去规则(Universal Specification，US)： (x)A(x)  A(y)。
全称量词引入规则(Universal Generalization,UG)： A(y)  (x)A(x)。
存在量词消去规则(Existential Specification,ES)： (x)A(x)  A(c)。
存在量词引入规则(Existential Generalization,EG)： A(c)  (x)A(x)。 
全称量词消去规则的含义在于： 若个体域中所有个体x都具有性质A，则个体域中任意一个个体y也必具有性质A。当A(x)中不再含有量词和其他个体变元时，这条规则明显成立。但当A(x)中还含有量词和其他个体变元时，运用该规则的条件是： 限制y不是A(x)中的约束变元。该规则还有一个推广形式： (x)A(x)  A(c)，其中c为一个个体常量。
全称量词引入规则的含义在于： 若个体域中任意一个个体y都具有性质A，则个体域中所有个体x也都具有性质A。运用该规则的条件是： y是个体域中的任意一个个体，且y取任何值时A都为真； 个体变元x不是A(y)中的约束变元。
存在量词消去规则的含义在于： 若个体域中存在个体x具有性质A，则个体域中必有某个体c具有性质A。运用该规则的条件是： c 是个体域中某个确定的个体常量，且使A为真；  c不在A(x)中出现过； (x)A(x)中没有自由变元。
存在量词引入规则的含义在于： 若个体域中存在个体c具有性质A，则(x)A(x)必为真。运用该规则的限制条件是： x不在A(c)中出现。
在谓词逻辑中，谓词公式的解释依赖于个体域，求取谓词公式在所有解释下的真值往往非常烦琐甚至异常困难，这就导致命题逻辑中的简单证明推理在谓词逻辑中不容易实施。谓词逻辑推理通常采用的是基于永真蕴含式或推理规则的构造证明推理。
例5.26证明以下推理： “所有计算机科学与技术专业的本科生都要修离散数学，王强是计算机科学与技术专业的本科生。所以，王强要修离散数学。”
证明对命题进行符号化。 
谓词C(x)： x是计算机科学与技术专业的本科生。
谓词D(x)： x要修离散数学。
个体常量a： 王强。
前提： (x)(C(x)→D(x))，C(a)。
结论： D(a)。
(1) (x)(C(x)→D(x))前提引入
(2) C(a)→D(a)(1)US规则
(3) C(a)前提引入
(4) D(a)(2)(3)假言推论
例5.27证明以下推理： “一切科学规律都具有客观性。所有政治经济学规律是科学规律。按劳分配规律是政治经济学规律。所以，按劳分配规律具有客观性。”
证明对命题进行符号化。 
谓词S(x)： x是科学规律。
谓词P(x)： x具有客观性。
谓词R(x)： x是政治经济学规律。
个体常量a： 按劳分配规律。
前提： (x)(S(x)→P(x))，(x) (R(x)→S(x))，R(a)。
结论： P(a)。
(1) (x) (S(x)→P(x))前提引入
(2) S(a)→P(a)(1)US规则
(3) (x) (R(x)→S(x))前提引入
(4) R(a)→S(a)(3)US规则 
(5) R(a)→P(a)(2)(4)条件三段论
(6) R(a)前提引入
(7) P(a)(5)(6)假言推论
例5.28证明 �瘙
綈(x)(A(x)∧C(x))，(x)(B(x)→C(x))(x)(B(x)→�瘙
綈A(x))。
证明(1) �瘙
綈(x)(A(x)∧C(x))前提引入

(2) (x)�瘙
綈 (A(x)∧C(x))(1)量词与否定的交换律

(3) (x) (�瘙
綈A(x)∨�瘙
綈C(x))(2)德·摩根律

(4) (x) (�瘙
綈C(x)∨�瘙
綈A(x))(3)交换律

(5) (x) (C(x) →�瘙
綈A(x)) (4)蕴含等值式

(6) C(y) →�瘙
綈A(y)(5)US规则

(7) (x)(B(x) →C(x))前提引入

(8) B(y) →C(y)(7)US规则

(9) B(y) →�瘙
綈A(y)(6)(8)条件三段论

(10)  (x)(B(x)→�瘙
綈A(x)) (9)UG规则
定理5.5谓词公式B是谓词公式A1，A2，…，An的有效结论当且仅当谓词公式A1∧A2 ∧…∧An∧�瘙
綈B是矛盾式。
证明由定义5.20知，谓词公式B是谓词公式A1，A2，…，An的有效结论当且仅当谓词公式A1∧A2 ∧…∧An→B是重言式。由于
A1∧A2 ∧…∧An→B
 �瘙
綈(A1∧A2 ∧…∧An)∨B
 �瘙
綈(A1∧A2 ∧…∧An∧�瘙
綈B)
所以，谓词公式A1∧A2 ∧…∧An→B是重言式当且仅当谓词公式A1∧A2 ∧…∧An∧�瘙
綈B是矛盾式，即谓词公式B是谓词公式A1，A2，…，An的有效结论当且仅当谓词公式A1∧A2 ∧…∧An∧�瘙
綈B是矛盾式。证毕。
定理5.5是谓词逻辑推理的理论基础。一方面，根据定义5.20，只要证明谓词公式A1∧A2 ∧…∧An→B是重言式，那么谓词公式A1，A2，…，An的有效结论就是谓词公式B； 另一方面，谓词公式A1，A2，…，An的有效结论是谓词公式B，也可以通过证明谓词公式A1∧A2 ∧…∧An∧�瘙
綈B是矛盾式而得到证明。前者称为谓词逻辑推理的直接方法(direct method)，后者称为谓词逻辑推理的间接方法(indirect method)或反证法。
例5.29用反证法证明以下推理： “学术委员会的每个成员都是博士并且是教授。有些学术委员会成员是青年人。因而，有的成员是青年教授。”
证明对命题进行符号化。 
谓词F(x)： x是学术委员会成员。
谓词G(x)： x是教授。
谓词H(x)： x是博士。
谓词R(x)： x是青年人。
前提： (x)(F(x)→(G(x)∧H(x)))，(x)(F(x)∧R(x))。
结论： (x)(F(x)∧R(x)∧G(x))。
(1) �瘙
綈(x)(F(x)∧R(x)∧G(x))结论的否定引入
(2) (x)(F(x)∧R(x))前提引入
(3) F(c)∧R(c)(2)ES规则
(4) (x)(F(x)→(G(x)∧H(x)))前提引入
(5) F(c)→(G(c)∧H(c))(4)US规则
(6) F(c)(3)化简式
(7) G(c)∧H(c) (5)(6)假言推论
(8) G(c) (7)化简式
(9) F(c)∧R(c)∧G(c)(3)(8)合取引入
(10) (x)(F(x)∧R(x)∧G(x)) (9)EG规则
(11) (�瘙
綈(x)(F(x)∧R(x)∧G(x)))∧((x)(F(x)∧R(x)∧G(x)))
(1)(10)合取引入
(12) 0(11)矛盾律
例5.30用反证法证明 (x)(F(x)→G(x))(x)((y)(F(y)∧H(x，y))→(z)(G(z)∧H(x，z)))。
证明(1) �瘙
綈(x)((y)(F(y)∧H(x，y))→(z)(G(z)∧H(x，z)))
结论的否定引入

(2) (x)�瘙
綈((y)(F(y)∧H(x，y)) →(z)(G(z)∧H(x，z)))(1)量词与否定的交换律

(3) �瘙
綈((y)(F(y)∧H(a，y))→(z)(G(z)∧H(a，z)))(2)ES规则

(4) �瘙
綈(�瘙
綈(y)(F(y)∧H(a，y))∨(z)(G(z)∧H(a，z)))(3)蕴含等值式

(5) �瘙
綈�瘙
綈(y)(F(y)∧H(a，y))∧�瘙
綈(z)(G(z)∧H(a，z))(4)德·摩根律

(6) (y)(F(y)∧H(a，y))∧�瘙
綈(z)(G(z)∧H(a，z))(5)双重否定律

(7) (y)(F(y)∧H(a，y))(6)化简式

(8) F(b)∧H(a，b)(7)ES规则

(9) F(b)(8)化简式

(10) (x)(F(x)→G(x))前提引入

(11) F(b)→G(b)(10)US规则

(12) G(b)(9)(11)假言推论

(13) �瘙
綈(z)(G(z)∧H(a，z))(6)化简式

(14) (z)�瘙
綈(G(z)∧H(a，z))(13)量词与否定的交换律

(15) (z)(�瘙
綈G(z)∨�瘙
綈H(a，z）)(14)德·摩根律

(16) �瘙
綈G(b)∨�瘙
綈H(a，b)(15)US规则

(17) H(a，b)(8)化简式

(18) �瘙
綈�瘙
綈H(a，b)(17)双重否定律

(19) �瘙
綈G(b)(16)(18)析取三段论

(20) G(b)∧�瘙
綈G(b)(12)(19)合取引入

(21) 0(20)矛盾律
归结推理也是谓词逻辑推理的一种重要方法。在谓词逻辑中，首先需要进行量词的消去，然后才能按照命题逻辑中归结推理的步骤实施。在这里，斯柯伦范式有着重要的作用。在前面已经证明，谓词公式的不可满足性和该谓词公式的斯柯伦范式的不可满足性等价。这正是谓词逻辑中归结推理的理论依据。
采用间接归结推理证明A1，A2，…，AnB的一般步骤如下。 
步骤1，将A1∧A2 ∧…∧An∧�瘙
綈B等值演算为前束范式(Q1x1)(Q2x2)…(Qnxn)M(x1，x2，…，xn)。
步骤2，将M(x1，x2，…，xn)等值演算为合取范式M′(x1，x2，…，xn)。
步骤3，消去(Q1x1)(Q2x2)…(Qnxn)M′(x1，x2，…，xn)中的存在量词，得到斯柯伦范式。
步骤4，将斯柯伦范式的母式中所有的析取式作为推理的前提进行推演。
例5.31用归结推理证明 (x)(P(x)∨Q(x))，(x)(Q(x)→�瘙
綈R(x))，(x)R(x)(x)P(x)。
证明令G=(x)(P(x)∨Q(x))∧(x)(Q(x)→�瘙
綈R(x))∧(x)R(x)∧�瘙
綈(x)P(x)。首先，将G转化为与之等值的前束范式，即 
(x)(P(x)∨Q(x))∧(x)(Q(x)→�瘙
綈R(x))∧(x)R(x)∧�瘙
綈(x)P(x)
 (x)(P(x)∨Q(x))∧(x)(Q(x)→�瘙
綈R(x))∧(x)R(x)∧(x)�瘙
綈P(x)
 (x)((P(x)∨Q(x))∧(Q(x)→�瘙
綈R(x))∧R(x))∧(x)�瘙
綈P(x)
 (x)�瘙
綈P(x)∧(x)((P(x)∨Q(x))∧(Q(x)→�瘙
綈R(x))∧R(x))
 (y)�瘙
綈P(y)∧(x)((P(x)∨Q(x))∧(Q(x)→�瘙
綈R(x))∧R(x)) 
 (y)(x)(�瘙
綈P(y)∧(P(x)∨Q(x))∧(Q(x)→�瘙
綈R(x))∧R(x))
 (y)(x)(�瘙
綈P(y)∧(P(x)∨Q(x))∧(�瘙
綈Q(x)∨�瘙
綈R(x))∧R(x))
上面前束范式的母式已经是合取范式。
其次，消去存在量词，可以得到以下斯柯伦范式，即 
G′=(x)(�瘙
綈P(a)∧(P(x)∨Q(x))∧(�瘙
綈Q(x)∨�瘙
綈R(x))∧R(x))
最后，得到推理的前提为�瘙
綈P(a)，P(x)∨Q(x)，�瘙
綈Q(x)∨�瘙
綈R(x)，R(x)。
归结推理如下： 
(1) �瘙
綈P(a)前提引入
(2) P(x)∨Q(x)前提引入
(3) �瘙
綈Q(x)∨�瘙
綈R(x)前提引入
(4) R(x)前提引入
(5) Q(a)(1)(2)归结
(6) �瘙
綈R(a)(3)(5)归结
(7) 0(4)(6)矛盾律
例5.32用归结推理证明 (x)(P(x)∧S(x))，(x)(P(x)→Q(x))，(x)(R(x)∧�瘙
綈Q(x))(x)(S(x)∧�瘙
綈P(x))。
证明令G=(x)(P(x)∧S(x))∧(x)(P(x)→Q(x))∧(x)(R(x)∧�瘙
綈Q(x))∧�瘙
綈(x)(S(x)∧�瘙
綈P(x))。首先，将G转化为与之等值的前束范式，即 
(x)(P(x)∧S(x))∧(x)(P(x)→Q(x))∧(x)(R(x)∧�瘙
綈Q(x))∧�瘙
綈(x)(S(x)∧�瘙
綈P(x))
 (x)(P(x)∧S(x))∧(x)(P(x)→Q(x))∧(x)(R(x)∧�瘙
綈Q(x))∧
(x)�瘙
綈(S(x)∧�瘙
綈P(x))
 (y)(P(y)∧S(y))∧(x)(P(x)→Q(x))∧(x)(R(x)∧�瘙
綈Q(x))∧
(x)(�瘙
綈S(x)∨�瘙
綈�瘙
綈P(x))
 (y)(P(y)∧S(y))∧(x)(P(x)→Q(x))∧(x)(R(x)∧�瘙
綈Q(x))∧
(x)(�瘙
綈S(x)∨P(x))
 (y)(x)((P(y)∧S(y))∧(P(x)→Q(x))∧(R(x)∧�瘙
綈Q(x))∧
(�瘙
綈S(x)∨P(x)))
再将上述前束范式的母式化为合取范式，即 
(y)(x)((P(y)∧S(y))∧(P(x)→Q(x))∧(R(x)∧�瘙
綈Q(x))∧(�瘙
綈S(x)∨P(x)))
(y)(x)(P(y)∧S(y)∧(�瘙
綈P(x)∨Q(x))∧R(x)∧�瘙
綈Q(x)∧(�瘙
綈S(x)∨P(x)))
其次，消去存在量词，可以得到以下斯柯伦范式，即
G′=(x)(P(a)∧S(a)∧(�瘙
綈P(x)∨Q(x))∧R(x)∧�瘙
綈Q(x)∧(�瘙
綈S(x)∨P(x)))
最后，得到推理的前提为P(a)，S(a)，�瘙
綈P(x)∨Q(x)，R(x)，�瘙
綈Q(x)，�瘙
綈S(x)∨P(x)。
归结推理如下： 
(1) P(a)前提引入
(2) �瘙
綈P(x)∨Q(x)前提引入
(3) Q(a)(1)(2)归结
(4) �瘙
綈Q(x)前提引入
(5) 0(3)(4)矛盾律
例5.33证明以下推理： “参加比赛者都是计算机系的学生并且是高级程序员。有些参赛者是女生。所以，有的参赛者是女高级程序员。”
证明对命题进行符号化。 
谓词M(x)： x是参赛者。
谓词S(x)： x是计算机系的学生。
谓词P(x)： x是高级程序员。
谓词G(x)： x是女生。
前提： (x)(M(x)→S(x)∧P(x))，(x)(M(x)∧G(x))。
结论： (x)(M(x)∧G(x)∧P(x))。
令G=(x)(M(x)→S(x)∧P(x))∧(x)(M(x)∧G(x))∧�瘙
綈(x)(M(x)∧G(x)∧P(x))。
首先，将G转化为与之等值的前束范式，即 
(x)(M(x)→S(x)∧P(x))∧(x)(M(x)∧G(x))∧�瘙
綈(x)(M(x)∧G(x)∧(P(x))
 (x)(M(x)→S(x)∧P(x))∧(x)(M(x)∧G(x))∧
(x)�瘙
綈(M(x)∧G(x)∧P(x))
 (y)(M(y)∧G(y))∧(x)(M(x)→S(x)∧P(x))∧
(x)(�瘙
綈M(x)∨�瘙
綈G(x)∨�瘙
綈P(x))
 (y)(x)((M(y)∧G(y))∧(M(x)→S(x)∧P(x))∧
(�瘙
綈M(x)∨�瘙
綈G(x)∨�瘙
綈P(x)))
再将上述前束范式的母式化为合取范式，即
(y)(x)((M(y)∧G(y))∧(M(x)→S(x)∧P(x))∧(�瘙
綈M(x)∨�瘙
綈G(x)∨�瘙
綈P(x)))
 (y)(x)(M(y)∧G(y)∧(�瘙
綈M(x)∨(S(x)∧P(x)))∧(�瘙
綈M(x)∨
�瘙
綈G(x)∨�瘙
綈P(x)))
 (y)(x) (M(y)∧G(y)∧(�瘙
綈M(x)∨S(x))∧(�瘙
綈M(x)∨P(x))∧
(�瘙
綈M(x)∨�瘙
綈G(x)∨�瘙
綈P(x)))
其次，消去存在量词，可以得到以下斯柯伦范式，即 
G′=(x)(M(a)∧G(a)∧(�瘙
綈M(x)∨S(x))∧(�瘙
綈M(x)∨P(x))∧

(�瘙
綈M(x)∨�瘙
綈G(x)∨�瘙
綈P(x)))
最后，得到推理的前提为M(a)，G(a)，�瘙
綈M(x)∨S(x)，�瘙
綈M(x)∨P(x)，�瘙
綈M(x)∨�瘙
綈G(x)∨�瘙
綈P(x)。
归结推理如下： 
(1) M(a)前提引入
(2) �瘙
綈M(x)∨P(x)前提引入
(3) P(a)(1)(2)归结
(4) �瘙
綈M(x)∨�瘙
綈G(x)∨�瘙
綈P(x)前提引入
(5) �瘙
綈M(a)∨�瘙
綈G(a)(3)(4)归结
(6) �瘙
綈G(a)(1)(5)归结
(7) G(a)前提引入
(8) 0(6)(7)矛盾律

5.4谓词逻辑的应用

自动规划是人工智能应用领域中一种重要的问题求解技术。与一般问题求解相比，自动规划更注重问题的求解过程，而不是求解结果。此外，自动规划要解决的问题往往是具体现实世界问题，如机器人路径规划等，而不是抽象的数学模型问题。自动规划将现实世界问题用状态、操作、动作等相关概念来描述，并从某个特定的问题状态出发，寻求一系列行为动作，建立一个操作序列(问题的解)，直至达到目标状态为止。基于谓词逻辑及推理的现实世界问题表示和规划求解是一种重要的自动规划方法。
图5.1所示为一个简单的机器人规划问题。工具箱、工作台、机器人分别放置于不同的位置L1、L2和L3，电子仪器放置于工作箱内。机器人的任务是完成打开工具箱，并把电子仪器搬放到工作台上。自动规划所要解决的就是给出机器人完成这一任务的操作序列。


图5.1机器人搬运示意图


为了表示自动规划问题，定义以下相关个体常量和谓词。 
个体常量R： 机器人。
个体常量B： 工具箱。
个体常量A： 电子仪器。
个体常量D： 工作台。
个体常量L1： 位置L1。
个体常量L2： 位置L2。
个体常量L3： 位置L3。
EMPTY(x)： x上面是空的。
H_EMPTY(x)： x手中是空的。
HOLDING(x，y)： x手中拿着y。
ON(x，y)： x在y的上面。
NEAR(x，y)： x在y的附近。
IN(x，y)： x在y的里面。
AT(x，y)： x在y处。
ISCLOSE(x)： x处于关闭状态。
ISOPEN(x)： x处于打开状态。
OPEN(x，y)： x把y打开。
CLOSE(x，y)： x把y关闭。
GOTO(x，y)： x走到y旁边。
PICKDOWN(x，y，z)： x把y放在z上。
PICKUP(x，y)： x把y拿起。
这样，机器人搬运问题的初始状态(s0)可以描述为
AT(B，L1)∧IN(A，B)∧ISCLOSE(B)∧AT(D，L2)∧EMPTY(D)∧
AT(R，L3)∧H_EMPTY(R)
目标状态(sf)可以描述为
AT(B，L1)∧�瘙
綈IN(A，B)∧ISCLOSE(B)∧AT(D，L2)∧ON(A，D)∧
NEAR(R，D)∧H_EMPTY(R)
自动规划所要解决的是： 找出一个操作序列，然后把这些操作序列告诉机器，机器就可以按预定的操作序列完成相应的任务。这里，谓词OPEN(x，y)、CLOSE(x，y)、GOTO(x，y)、PICKDOWN(x，y，z)和PICKUP(x，y)等都表示的是操作。
任何操作的执行都要满足一定的条件，称为先决条件(precondition)。操作执行的同时会产生相应的状态或条件的改变，称为行为动作(action)。下面给出这些操作的先决条件和行为动作： 
OPEN(x，y)
先决条件： H_EMPTY(x)∧NEAR(x，y)∧ISCLOSE(y)
行为动作： 消去ISCLOSE(y)； 添加ISOPEN(y)
CLOSE(x，y)
先决条件： H_EMPTY(x)∧NEAR(x，y)∧ISOPEN(y)
行为动作： 消去ISOPEN(y)； 添加ISCLOSE(y)
GOTO(x，y)
先决条件： �瘙
綈NEAR(x，y)
行为动作： 消去�瘙
綈NEAR(x，y)； 添加NEAR(x，y)
PICKDOWN(x，y，z)
先决条件： NEAR(x，z)∧HOLDING(x，y)∧EMPTY(z)
行为动作： 消去HOLDING(x，y)∧EMPTY(z)； 添加ON(y，z)∧H_EMPTY(x)
PICKUP(x，y)
先决条件： NEAR(x，z)∧IN(y，z)∧ISOPEN(z)∧H_EMPTY(x)
行为动作： 消去IN(y，z)∧H_EMPTY(x)； 添加�瘙
綈IN(y，z)∧HOLDING(x，y)
下面的问题是依据谓词逻辑推理，确定各操作的具体执行顺序，以使问题从初始状态到达目标状态。目前已开发出了许多自动规划推理系统，如STRIPS(Stanford Research Institute Problem Solver)等。这里仅从谓词逻辑推理的机理角度，给出操作序列的求解过程。
在初始状态s0，AT(R，L3)满足。那么，操作GOTO(R，B) 的先决条件�瘙
綈NEAR(R，B)成立。所以，操作GOTO(R，B)可以执行，产生的行为动作是： 消去AT(R，L3)； 添加NEAR(R，B)。得到新的状态s1，即 
AT(B，L1)∧IN(A，B)∧ISCLOSE(B)∧AT(D，L2)∧EMPTY(D)∧
NEAR(R，B)∧H_EMPTY(R)
在状态s1，操作OPEN(R，B)的先决条件H_EMPTY(R)∧NEAR(R，B)∧ISCLOSE(B)成立。所以，操作OPEN(R，B)可以执行，产生的行为动作是： 消去ISCLOSE(B)； 添加ISOPEN(B)。得到新的状态s2，即 
AT(B，L1)∧IN(A，B)∧ISOPEN(B)∧AT(D，L2)∧EMPTY(D)∧
NEAR(R，B)∧H_EMPTY(R)

在状态s2，操作PICKUP(R，A)的先决条件IN(A，B)∧ISOPEN(B)∧NEAR(R，B)∧H_EMPTY(R)成立。所以，操作PICKUP(R，A)可以执行，产生的行为动作是： 消去IN(A，B)∧H_EMPTY(R)； 添加�瘙
綈IN(A，B)∧HOLDING(R，A)。得到新的状态s3，即 
AT(B，L1)∧ISOPEN(B)∧AT(D，L2)∧EMPTY(D)∧NEAR(R，B)∧
�瘙
綈IN(A，B)∧HOLDING(R，A)
在状态s3，NEAR(R，B)满足，那么操作GOTO(R，D) 的先决条件�瘙
綈NEAR(R，D)成立。所以，操作GOTO(R，D)可以执行，产生的行为动作是： 消去NEAR(R，B)； 添加NEAR(R，D)。得到新的状态s4，即 
AT(B，L1)∧ISOPEN(B)∧AT(D，L2)∧EMPTY(D)∧NEAR(R，D)∧
�瘙
綈IN(A，B)∧HOLDING(R，A)
在状态s4，操作PICKDOWN(R，A，D)的先决条件NEAR(R，D)∧HOLDING(R，A)∧EMPTY(D)成立。所以，操作PICKDOWN(R，A，D)可以执行，产生的行为动作是： 消去HOLDING(R，A)∧EMPTY(D)； 添加ON(A，D)∧H_EMPTY(R)。得到新的状态s5，即 
AT(B，L1)∧ISOPEN(B)∧AT(D，L2)∧NEAR(R，D)∧�瘙
綈IN(A，B)∧

ON(A，D)∧H_EMPTY(R)
在状态s5，NEAR(R，D)满足，那么操作GOTO(R，B)的先决条件�瘙
綈NEAR(R，B)成立。所以，操作GOTO(R，B)可以执行，产生的行为动作是： 消去NEAR(R，D)； 添加NEAR(R，B)。得到新的状态s6，即 
AT(B，L1)∧ISOPEN(B)∧AT(D，L2)∧NEAR(R，B)∧�瘙
綈IN(A，B)∧

ON(A，D)∧H_EMPTY(R)
在状态s6，操作CLOSE(R，B)的先决条件H_EMPTY(x)∧ISOPEN(B)∧NEAR(R，B)成立。所以，操作CLOSE(R，B)可以执行，产生的行为动作是： 消去ISOPEN(B)； 添加ISCLOSE(B)。得到新的状态s7，即 
AT(B，L1)∧ISCLOSE(B)∧AT(D，L2) ∧NEAR(R，B)∧�瘙
綈IN(A，B)∧

ON(A，D)∧H_EMPTY(R)
在状态s7，NEAR(R，B)满足，那么操作GOTO(R，D)的先决条件�瘙
綈NEAR(R，D)成立。所以，操作GOTO(R，D)可以执行，产生的行为动作是： 消去NEAR(R，B)； 添加NEAR(R，D)。得到新的状态s8，即 
AT(B，L1)∧ISCLOSE(B)∧AT(D，L2) ∧NEAR(R，D)∧�瘙
綈IN(A，B)∧
ON(A，D)∧H_EMPTY(R)
状态s8就是目标状态sf。由此，可得到该机器人搬运任务的操作序列为 
GOTO(R，B) →OPEN(R，B) →PICKUP(R，A) →GOTO(R，D) →
PICKDOWN(R，A，D) →GOTO(R，B) →CLOSE(R，B) →GOTO(R，D)。

习题

5.1用谓词表示下列命题：
① 王强不是计算机专业的学生； 
② 李阳会讲英语、法语和德语； 
③ 机器人搬运货物到仓库； 
④ 王强喜欢足球和网球； 
⑤ 北京、上海、天津和重庆都是直辖市； 
⑥ 京沪高铁穿过济南和南京； 
⑦ 深圳在广州和香港之间； 
⑧ 张宏和刘伟是朋友。
5.2用谓词和函词表示下列命题：
① 空集属于它的幂集； 
② 小张的叔叔和小刘的爸爸是朋友； 
③ 王强的离散数学任课老师是张辉的女朋友的研究生导师； 
④ π的平方大于5； 
⑤ 小明的父亲和母亲都是科学家。
5.3用谓词和量词符号表示下列命题：
① 每一个有理数都是实数； 
② 某些实数是自然数； 
③ 有些学生完成了所有习题； 
④ 没有人登上过喜马拉雅山的所有山峰； 
⑤ 火星上存在生命； 
⑥ 中国短道速滑队获得过冬奥会金牌； 
⑦ 中国乒乓球队包揽了2010年乒乓球世界锦标赛所有金牌； 
⑧ 任意三点确定一个平面。
5.4设S(x，y，z)表示“x+y=z”，E(x，y)表示“x=y”，M(x，y，z)表示“x·y=z”，L(x，y)表示“x＜y”，个体域为自然数集，给出下列命题的符号表示：
① 并非一切x都有x≤y； 
② 对任意x，x+y=y当且仅当y=0； 
③ 如果x·y≠0，则x≠0且y≠0； 
④ 存在x，使得对所有y，x·y=y成立； 
⑤ 没有x<0且x>0； 
⑥ 对于x，必有y，满足y>x。
5.5设个体域为自然数集，给出下列命题的符号表示：
① x是两数平方之和； 
② x是y和z的最大公约数； 
③ 任何数被2除时余数为0或1； 
④ 任意3个数有最小公倍数； 
⑤ 并非任何自然数都有比它小的自然数； 
⑥ 两个奇数之和是偶数。
5.6设个体域为实数集，给出下列命题的符号表示：
① 不存在某数的平方小于零； 
② 方程x=f(x)的解是f(x)的不动点； 
③ 任何两实数之间必存在一个实数； 
④ 非零实数都是另外两个不同实数的积； 
⑤ 有些一元二次方程有两个不同的实根； 
⑥ 闭区间的连续函数一定有上界和下界。
5.7用谓词逻辑符号化下列命题：
① 我为人人，人人为我； 
② 有些乌龟比有些兔子跑得快； 
③ 不管白猫黑猫，抓住老鼠都是好猫； 
④ 如果R是集合A上的自反、对称和传递关系，则该关系是集合A上的等价关系； 
⑤ 任何实数都有比它小的后继实数； 
⑥ 不存在最大的自然数； 
⑦ 只要功夫深，铁棒磨成针； 
⑧ 天下乌鸦一般黑； 
⑨ 吃一堑长一智； 
⑩ 空集是任何集合的子集合。
5.8判断下列符号串哪些是谓词公式：
① H(x，y)∨�瘙
綈(y)G(x)； 
② (x)�瘙
綈H(x，f(y))； 
③ (x)�瘙
綈(y)�瘙
綈H(x，f(y))； 
④ (x)�瘙
綈(y)(�瘙
綈H(x，f(y))∨�瘙
綈(y)G(x)； 
⑤ (x)�瘙
綈(y)(�瘙
綈H(x，f(y))∨�瘙
綈(y))G(x)； 
⑥ (x)�瘙
綈(y)(�瘙
綈H(x，f(y))∨�瘙
綈(y)G(x))； 
⑦ H(，y)∨G(x)x)�瘙
綈(y)(�瘙
綈H(x，； 
⑧ (x)(y)(A(x，y)∧B(x))→H(x)； 
⑨ (x)(y)A(x，y，z)∧(z)B(x)； 
⑩ (x)�瘙
綈H(x→y)； 
5.9给出下列谓词公式的自然语言表述：
① (x)(y)A(x，y)，其中A(x，y)表示x·y＝y； 
② (x)(y)F(x，y)，其中F(x，y)表示x+y＝y； 
③ (x)(y)N(x，y)，其中N(x，y)表示y＝2x； 
④ (x)(y)M(x，y)，其中M(x，y)表示x·y=1； 
⑤ (x)(y)(z)B(x，y，z)，其中B(x，y，z)表示x≤y＜z； 
⑥ (x)(y)(z)C(x，y，z)，其中C(x，y，z)表示x2+y2=z。
5.10对于谓词，有 
P(x)： x是素数； E(x)： x是偶数； O(x)： x是奇数； N(x，y)： x可以整除y。
给出下列谓词公式的自然语言表述：
① (x)(N(2，x)→E(x))； 
② (x)(N(x，6)∧E(x))； 
③ (x)(�瘙
綈E(x)→�瘙
綈N(2，x))； 
④ (x)(E(x)→(y)(N(x，y)→E(y)))； 
⑤ (x)(P(x)→(y)(N(y，x)∧O(y)))； 
⑥ (x)(O(x)→(y)(�瘙
綈N(y，x)∧E(y)))。
5.11指出下列各谓词公式中的自由变元、约束变元及量词的辖域：
① (x)(P(x)→R(x)∧S(x))→(x)(R(x)∧Q(x，y))； 
② (x)(�瘙
綈P(x)→R(x)∧S(x))(x)R(x)∧Q(x，y)； 
③ (x)(y)(P(x)R(x)∧S(y))R(x)∧(x)Q(x，y)； 
④ (x)P(x) (y)(R(x)∧�瘙
綈S(y))∧(x)R(x)∧(y)Q(x，y)； 
⑤ (x)(y)(z)�瘙
綈B(x，y，z)∨(x)P(x)→(y)(y)(R(x)∧S(y))∧(x)G(x)∧(y)Q(y)； 
⑥ (x)(y)(z)B(x，y，z)∨(x)P(x)→(x)(y)(�瘙
綈R(x)∧S(y，w))∧(x)Q(x)。
5.12对下列谓词公式进行个体变元替换，使得每一个个体变元有唯一的出现形式：
① (x)S(x)→(x)(R(x)∧Q(x，y))； 
② �瘙
綈(x)P(x)→(R(x，y)∧S(x)(x)M(x，y))； 
③ (x)(y)(P(x)R(x)∧S(y))∨R(x)∧(y)F(x，y)； 
④ (x)P(x，y)(y)(R(x)∧�瘙
綈S(y))∧(y)Q(x，y)； 
⑤ (x)(y)�瘙
綈(z)H(x，y，z)→(y)(x)(R(x，y)∧S(y))∧(x)G(x)； 
⑥ ((x)(y)N(x，y，z)∨(x)P(x，y)∨(x)R(x，z))∧(x)Q(x)。
5.13设P(x)表示“x=x2”，个体域为整数集，求下列各谓词公式的真值：
① P(0)∧P(1)； ② P(-1)→P(2)； 
③ (x)P(x)； ④ (x)P(x)； 
⑤ P(3)→(x)P(x)； ⑥ (x)P(x)→(y)P(y)。
5.14设个体域为自然数集，个体常量a=0，函词f(x，y)=x+y，函词g(x，y)=x·y，谓词P(x，y)为x=y。求使得下列各谓词公式的真值为真或假的个体变元的取值：
① P(f(x，y)，g(y，z))； 
② P(f(x，a)，y)→ P(f(x，y)，z)； 
③ �瘙
綈P(g(x，y)，g(y，z))； 
④ (x)P(g(x，y)，z)； 
⑤ (x)P(g(x，a)，x)→ P(x，y)； 
⑥ (x)(y)(P(f(x，y)，a)→P(x，g(x，y)))。
5.15设个体域为实数集，个体常量a=0，函词f(x，y)=x-y，谓词Q(x，y)为x=y。求使得下列各谓词公式的真值为真或假的个体变元的取值：
① Q(x，a)； 
② Q(f(x，y)，x)→Q(a，f(x，y))； 
③ �瘙
綈Q(x，f(x，f(x，y)))； 
④ (x)Q(f(x，y)，z)； 
⑤ (x)Q(f(x，a)，x)→ Q(x，y)； 
⑥ (x)(y)(Q(f(x，a)，y)→Q(x，f(a，y)))。
5.16设Q(x，y)表示“x+y＝x-y”，个体域为整数集合，求下列各谓词公式的真值：
① Q(0，1)； ② (x)Q(0，x)； 
③ (x)(y)Q(x，y)； ④ (x)Q(x，2)； 
⑤ (x)(y)Q(x，y)； ⑥ (x)(y)Q(x，y)。
5.17设个体域为整数集，求下列各语句的真值：
① (x)(x2=2)； ② (x)(y)(x+y=x·y)； 
③ (x)(y)(x+1=y2)； ④ (x)(y)((x+y=1)∧(2x+y=3))； 
⑤ (x)(y)(z)(x+y=z-y)； ⑥ (x)(y)(z)((x+y)/2=z)。
5.18对于解释I： 
个体域D={a，b}； 
谓词P(x，y)： P(a，a)=1，P(a，b)=0，P(b，a)=0，P(b，b)=1。
给出下列谓词公式在解释I下的真值：
① (x)(y)P(x，y)； ② (x)(y)P(x，y)； 
③ (x)(y)P(x，y)； ④ (x)P(x，x)； 
⑤ (y)P(b，y)； ⑥ (x)(y)P(x，y)。
5.19对于解释I： 
个体域D={1，2}； 
个体常量a=1，b=2； 
函词f(x)： f(1)=2，f(2)=1； 
谓词P(x，y)： P(1，1)=1，P(1，2)=1，P(2，1)=0，P(2，2)=1。
给出下列谓词公式在解释I下的真值：
① P(a，f(a))∧P(b，f(b))； ② (x)(y)P(x，f(y))； 
③ (x)(y)(P(f(x)，y)∨P(x，x))；  ④ (x)P(x，x)∧(x)P(x，f(x))； 
⑤ (y)P(b，y)→(x)P(x，f(x))；  ⑥ (x)(y)P(f(x)，f(y))。
5.20对于谓词公式G=(x)P(x)→(x)P(x)，如果解释I的个体域仅包含一个元素，那么G的真值是什么？如果个体域为D={a，b}，试找出G的成假解释。
5.21对于个体域为D={1，2}，给出使得谓词公式(x)(P(x)→Q(x))和(x)(P(x)∧Q(x))的真值同时为真和同时为假的两个解释。
5.22对于解释I： 
个体域D为整数集； 
个体常量a=0； 
函词f(x，y)=x-y； 
谓词P(x，y)： x=y； 
谓词Q(x，y)： x<y。
说明下列各谓词公式在解释I下的意义及其真值，并求另一解释I′，使相应谓词公式取相反的真值：
① (x)(y)(Q(f(x，y)，a)→Q(x，y))； 
② (x)(y)(P(f(x，y)，a)→Q(x，y))；  
③ (x)(y)(Q(x，y)→�瘙
綈P(x，y))； 
④ (x)(y)(Q(f(x，y)，a)→Q(x，y))； 
⑤ (x)(y)(P(f(x，y)，a)→Q(x，y))； 
⑥ (x)(y)(Q(f(x，y)，a)→Q(x，y))。
5.23判断下列谓词公式是否为永真公式：
① (x)(y)P(x，y) (y)(x)P(x，y)； 
② (x)(y)P(x，y)(y)(x)P(x，y)； 
③ (x)(y)P(x，y) (y)(x)P(x，y)； 
④ ((x)A(x)→(x)B(x))(x)(A(x)→B(x))； 
⑤ ((x)A(x)→(x)B(x))→(x)(A(x)→B(x))； 
⑥ (x)(A(x)→B(x))→((x)A(x)→(x)B(x))。
5.24判断下列谓词公式是否为永真公式：
① (x)(y)P(x，y)∧(y)(x)P(x，y)； 
② (x)(y)P(x，y)∧(y)(x)P(x，y)； 
③ (x)(y)P(x，y)∧(y)(x)P(x，y)； 
④ ((x)A(x)∧(x)B(x))→(x)(A(x)∧B(x))； 
⑤ ((x)A(x)∧(x)B(x))→(x)(A(x)∧B(x))； 
⑥ (x)(A(x)∧B(x))→((x)A(x)∧(x)B(x))。
5.25判断下列谓词公式是否为永真公式：
① (x)(y)P(x，y)∨(y)(x)P(x，y)； 
② (x)(y)P(x，y)∨(y)(x)P(x，y)； 
③ (x)(y)P(x，y)∨(y)(x)P(x，y)； 
④ ((x)A(x)∨(x)B(x))→(x)(A(x)∨B(x))； 
⑤ ((x)A(x)∨(x)B(x))→(x)(A(x)∨B(x))； 
⑥ (x)(A(x)∨B(x))→((x)A(x)∨(x)B(x))。
5.26判断下列谓词公式哪些是永真公式、哪些是可满足公式、哪些是不可满足公式：
① (x)A(x)→(x)A(x)； 
② (x)�瘙
綈A(x)→�瘙
綈(x)A(x)； 
③ (x)A(x)→(x)A(x)； 
④ (x)(y)P(x，y)→(y)(x)P(x，y)； 
⑤ (x)(y)P(x，y)→(y)(x)P(x，y)； 
⑥ (x)(y)P(x，y)→(y)(x)P(x，y)；  
⑦ ((x)A(x)∧(x)B(x))(x)(A(x)∧B(x))； 
⑧ ((x)A(x)∨(x)B(x))(x)(A(x)∨B(x))； 
⑨ ((x)A(x)→(x)B(x))→(x)(A(x)→B(x))； 
⑩ (x)(A(x)∨B(x))→((x)A(x)∨(y)B(y))。
5.27将下列谓词公式中的否定联结词移动，使其只出现在谓词的前面：
① �瘙
綈(x)(y)P(x，y)∨(y)�瘙
綈(x)P(x，y)； 
② �瘙
綈(x)�瘙
綈A(x)→�瘙
綈(x)B(x)； 
③ �瘙
綈(x)(A(x)→(x)A(x))； 
④ (x)�瘙
綈(y)(P(x，y)→�瘙
綈(y)(x)P(x，y))； 
⑤ �瘙
綈((x)(y)P(x，y)→(y)�瘙
綈(x)P(x，y))； 
⑥ (x)�瘙
綈(y)(P(x，y)→B(x))∨�瘙
綈(y)(x)P(x，y)。
5.28设个体域为D={a，b}，消去以下谓词公式中的量词：
① (x)(y)P(x，y)∧P(a，z)； 
② (x)(y)P(x，y)∧(y)(x)P(x，y)； 
③ (x)(y)P(x，y)→(x)A(x)； 
④ (x)(A(x)→B(x))； 
⑤ (x)(y)(P(x，y)→B(y))∨(x)A(x)； 
⑥ (x)(y)(P(x，y)∧B(z))∨(x)G(x，y)。
5.29设解释I的个体域由a、b和c组成，试将下列谓词公式写成在解释I中不含量词的形式：
① (x)P(x)∧(y)Q(y)； 
② (x)(P(x)→(y)A(y))； 
③ (x)(P(x)∧(y)Q(y))； 
④ (y)P(y)∧(y)(x)Q(x，y)； 
⑤ (x)(y)(z)(P(x，y)→B(z))∨(x)A(x)； 
⑥ (x)(y)(P(x，y)∧B(y))∨(x)(y)G(x，y)。
5.30证明下列谓词公式的等值式：
① (x)A(x)∧((x)A(x)∨(x)A(x))(x)A(x)； 
② (x)A(x)→(y)B(y) (x)�瘙
綈A(x)∨(y)B(y)； 
③ �瘙
綈((x)A(x)∧(y)B(y))  (x)�瘙
綈A(x)∨(y)�瘙
綈B(y)； 
④ ((x)A(x)→(y)P(x，y))∧((x)A(x)→�瘙
綈(y)P(x，y))(x)�瘙
綈A(x)； 
⑤ �瘙
綈((x)(y)P(x，y)∨(x)A(x)) (x)(y)�瘙
綈P(x，y)∧�瘙
綈(x)A(x)； 
⑥ (x)(y)P(x，y)→(y)B(y)(y)�瘙
綈B(y)→�瘙
綈(x)(y)P(x，y)。
5.31证明下列谓词公式的等值式：
① (x)(�瘙
綈A(x)∨B)(x)A(x)→B； 
② (x)(�瘙
綈A(x)→B)(x)A(x)∨B； 
③ (x)A(x)∧�瘙
綈(x)�瘙
綈B(x)(x)(y)(A(x)∧B(y))； 
④ (x)(�瘙
綈A(x)∨B(x))(x)A(x)→(x)B(x)； 
⑤ (x)(A(x)∧B)�瘙
綈(x)�瘙
綈A(x)∧B； 
⑥ (x)(y)P(x，y)(y)�瘙
綈(x)�瘙
綈P(x，y)。
5.32求下列谓词公式的前束范式：
① �瘙
綈(x)(y)G(x，y)∨(y)P(x，y)； 
② �瘙
綈(x)A(x，y)→(x)B(x)； 
③ �瘙
綈(x)(G(x)→(y)A(x，y))； 
④ (x)(y)(P(x，y)→(y)(x)G(x，y))； 
⑤ (x)(y)P(x，y)→(y)(z)G(x，z)； 
⑥ (x)(y)(A(x)→B(y))∨(y)(x)P(x，y)。
5.33求习题5.23中各谓词公式的前束范式。
5.34求习题5.24中各谓词公式的前束范式。
5.35假设(x)(y)M(x，y)是谓词公式G的前束范式，其中，M(x，y)是仅仅包含变量x和y的母式。试证明： G是重言式当且仅当(x)M(x，f(x))是重言式，其中，f是不出现在M(x，y)中的函词。
5.36求下列谓词公式的斯柯伦范式：
① (y)(G(x)→(y)Q(x，y))； 
② (x)(y)(z)(u)(v)(w)M(x，y，z，u，v，w)； 
③ (x)(G(x，y)→(y)(z)A(x，y，z))； 
④ (x)(y)(N(x，y)∨(y)(x)G(x，y))； 
⑤ (x)(y)N(x，y)∧(y)(z)G(x，z)； 
⑥ (x)(y)(A(x)∧B(y))→(y)(x)G(x，y)。 
5.37求习题5.28中谓词公式的斯柯伦范式。
5.38判断下列谓词公式的蕴含式是否为永真蕴含式：
① (x)A(x)∨(x)B(x)→(x)(A(x)∨B(x))； 
② (x)A(x，x)→(x)(y)A(x，y)； 
③ (x)(A(x)∧B(x))→(x)A(x)∧(x)B(x)； 
④ (x)A(x，x)→(x)(y)A(x，y)； 
⑤ (x)(A(x)→B(x)) →((x)A(x)→(x)B(x))； 
⑥ (x)A(x) →(x)A(x)∨(y)B(y)。
5.39证明下列谓词公式的永真蕴含式：
① (x)(A(x)→B(x))  (x)A(x)→(x)B(x)； 
② (x)(y)A(x，y)  (x)A(x，x)； 
③ (x)(A(x)∧B(x))  (x)A(x)∧(x)B(x)； 
④ (x)A(x)∧((x)�瘙
綈A(x)∨(y)B(y))  (x)A(x)； 
⑤ (y)�瘙
綈B(y)∧((x)�瘙
綈A(x)→(y)B(y))  (x)A(x)； 
⑥ (x)(y)A(x，y)  (y)(x)A(x，y)。
5.40设个体域由两个元素组成，如果谓词公式(x)(A(x)∧B(x))和(y)(A(y)∧C(y))在某解释I下真值为真，则(z)(B(z)∧C(z))是否在该解释I下真值为真？如果将谓词公式中的存在量词换成全称量词，结果如何？
5.41证明下列推理：
① (x)(P(x)→(Q(y)∧R(a)))，(x)P(x)Q(y)∧(x)(P(x)∧R(x))； 
② (x)(�瘙
綈P(x)→Q(x))，(x)�瘙
綈Q(x)(x)P(x)； 
③ (x)P(x)→(y)((P(y)∨Q(y))→R(y))，(x)P(x)(x)R(x)； 
④ (x)(P(x)→(Q(x)∧R(x)))，(x)P(x)(x)(P(x)∧R(x))。
5.42每一个自然数不是奇数就是偶数。自然数是偶数当且仅当它能被2整除。并不是所有自然数都能被2整除。因此，有的自然数是奇数。符号化表示该命题，并给出推理的证明。
5.43如果一个人怕困难，那么他就不会获得成功。每个人或者获得成功或者失败过。有些人未曾失败过。所以，有些人不怕困难。符号化表示该命题，并给出推理的证明。
5.44两个三角形全等当且仅当它们的3条边分别相等。如果两个三角形全等则它们的3个内角分别相等。三角形A和三角形B的3条边相等。所以，三角形A和三角形B的3个内角相等。符号化表示该命题，并给出推理的反证法证明。
5.45用归结推理证明习题5.41中的推理。
5.46用归结推理证明习题5.42中的推理。
5.47用归结推理证明习题5.43中的推理。
5.48用归结推理证明习题5.44中的推理。




第3篇抽象代数



代数学(algebra)历史悠久。早期代数学的研究对象是具体的，是以方程根的计算为其研究中心。早在公元前1700年左右，人们就发现了求解一次方程的方法。到了公元前几世纪，巴比伦人实际上已经使用配方法得到了二次方程的求根公式。而寻找三次方程的求根公式经历了2000多年的漫长岁月，直到16世纪欧洲文艺复兴时期才由意大利数学家找到，这就是通常所说的卡丹(Gerolamo Cardano，1501—1576)公式。在三次方程求解问题解决不久，费尔拉里(Ludovico Ferrari，1522—1565)又得到了四次方程的求解方法，主要思路是将求四次方程的根化为求一个三次方程和两个二次方程的根。既然有了这个突破，数学家们就以极大的兴趣和自信致力于寻找五次方程的求解方法。当时一些著名的数学家，如欧拉(Leonhard Euler，1707—1783)、范德蒙德(Alexandre Theophile Vandermonde，1735—1796)、拉格朗日(Joseph Louis Lagrange，1735—1813)、阿贝尔(Niels Henrik Abel，1802—1829)和高斯(Carl Friedrich Gauss，1777—1855)等都曾尽力寻找，但都以失败告终。
19世纪30年代，在寻找五次方程求解方法的过程中，法国青年数学家伽罗瓦(variste Galois，1811—1832)于1832年提出了群(group)的概念，运用群的思想证明了高于四次的一般代数方程的不可解性，而且还建立了具体数字系数的代数方程可用根号求解的判别规则，并举出了不能用根号求解的数字系数代数方程的实例。这样，伽罗瓦就彻底解决了这个在长达200多年的时间使不少数学家伤透脑筋的问题。但是，当时他的思想不被人理解和接受，直到他去世38年后，他的超越时代的天才思想才逐渐被人们所承认。之所以说伽罗瓦是超越时代的人才，不仅仅是因为他在方程求解上的贡献，还因为他所发现的结果，他的奇特思想和巧妙方法，使得代数学由作为解方程的科学转变为研究代数运算结构，即代数结构(algebraic structure)的科学。尤其重要的是，群论开辟了全新的研究领域，以结构研究代替计算，把从偏重计算研究的思维方式转变为用结构观念研究的思维方式，并把数学运算归类，使群论迅速发展成为一门崭新的数学分支，即把代数学由初等代数时期推向抽象代数(abstract algebra)即近世代数(modern algebra)时期，对近世代数的形成和发展产生了巨大影响。同时这种理论对于物理学、化学的发展，甚至对于20世纪结构主义哲学的产生和发展都产生了巨大的影响。因此，伽罗瓦被认为是近世代数的创始人。
1843年，哈密顿(William Rowan Hamilton，1805—1865)发明了一种乘法交换律不成立的代数——四元数代数。次年，格拉斯曼(Hermann Günther Grassmann，1809—1877)推演出更有一般性的几类代数。1857年，凯莱(Arthur Cayley，1812—1895)设计出另一种不可交换的代数——矩阵代数。他们的研究打开了抽象代数的大门。实际上，减弱或删去普通代数的某些假定，或将某些假定代之以别的假定(与其余假定是兼容的)，就能研究出许多种代数体系。凯莱在1849年对群作了抽象定义，提出了抽象群的概念，可惜没有引起反响。“过早的抽象落到了聋子的耳朵里”。直到1878年，凯莱又写了抽象群的4篇文章才引起注意。1870年，克隆尼克(Leopold Kronecker，1823—1891)给出了有限阿贝尔群(Abel group)的抽象定义； 戴德金(Julius W.R.Dedekind，1831—1916)开始使用“体”的说法，并研究了代数体。1874年，挪威数学家索甫斯·李(Marius Sophus Lie，1842—1899)在研究微分方程时，发现某些微分方程解对一些连续变换群是不变的，一下子接触到连续群。1882年，英国的戴克(Walther von Dyck，1856—1934)把群论的3个主要来源——方程式论、数论和无限变换群纳入统一的概念中，并提出“生成元”概念。
群论的研究在20世纪沿着各个不同方向展开。例如，找出给定阶的有限群的全体； 群分解为单群、可解群等问题一直被研究着。有限单群的分类问题在20世纪70—80年代才获得可能是最终的解决。伯恩赛德(William Burnside，1852—1927)曾提出过许多问题和猜想。例如，他在1902年提出： 一个群G是有限生成且每个元素都是有限阶，G是不是有限群？并猜想每一个非交换的单群是偶数阶的。前者至今尚未解决，后者于1963年解决。舒尔(Issai Schur，1875—1941)于1901年提出有限群表示的问题。庞加莱(Jules Henri Poincaré，1854—1912)对群论抱有特殊的热情，他说： “群论就是摒弃其内容而化为纯粹形式的整个数学。”这当然是过分夸大了群的影响。
1910年施泰尼茨(Ernst Steinitz，1871—1928)在“域的代数理论”中，提出了域(domain)的概念，并总结了包括群、代数、域等在内的代数体系的研究，开创了抽象代数学，成为抽象代数的重要里程碑。环(ring)论是抽象代数中较晚成熟的。尽管环和理想(ideal)的构造在19世纪就可以找到，但抽象理论却完全是20世纪的产物。韦德伯恩(Joseph Wedderburn，1882—1948)在“论超复数”一文中研究了线性结合代数，这种代数实际上就是环。环和理想的系统理论由诺特(Amalie Emmy Noether，1881—1935)给出。她开始工作时，环和理想的许多结果都已经有了，但当她将这些结果给予适当的确切表述时，就得到了抽象理论。诺特把多项式环的理想论包括在一般理想论之中，为代数整数的理想论和代数整函数的理想论建立了共同的基础。诺特对环和理想作了十分深刻的研究。人们认为这一总结性的工作在1926年终于完成，因此，可以认为抽象代数形成的时间为1926年。
英国数学家布尔(George Boole，1800—1864)为了研究思维规律于1847提出了一种数学模型，1854年对这种数学模型进行了完善。此后，戴德金把该数学模型作为一种特殊的格。由于缺乏物理背景，所以研究缓慢，到了20世纪30—40年代才有了新的进展。斯通(Marshall Harvey Stone，1903—1989)于1935年首先指出布尔代数与环之间有明确的联系，同时得出了所谓的斯通表示定理： 任意一个布尔代数一定同构于某个集上的一个集域，任意一个布尔代数也一定同构于某个拓扑空间的闭开代数。这使布尔代数在理论上有了一定的发展。
迄今为止，数学家们已经研究过200多种代数结构，其中最主要的若当代数(Jordan algebra)和李代数(Lie algebra)是不服从结合律的代数的例子。这些工作的绝大部分属于20世纪，它们使一般化和抽象化的思想在现代数学中得到了充分的反映。
抽象代数是研究各种抽象的公理化代数系统(algebraic system)或代数结构的数学学科。计算机科学及其应用中的自动机理论、形式语言、逻辑电路设计与验证、编码理论、程序设计语义学、抽象数据结构、程序验证等都离不开代数系统的理论。