第3章
谓 词 逻 辑


命题逻辑研究命题与命题之间的逻辑关系，其基本研究单位是原子命题，命题逻辑具有一整套完备的演算与推理理论体系，并且在数字电路设计与优化等多个领域有着广泛应用。但当两个命题之间在概念层次上具有某些共同特征或具有某种逻辑上的联系时，命题逻辑无法揭示这些特征与联系。例如，逻辑学中著名的三段论方法，是由一个大前提、一个小前提推出结论的方法。这方面的例子如：
凡是人都要死。
苏格拉底是人。
所以苏格拉底是要死的。
又如：
所有的自然数都是有理数。
100是自然数。
所以100是有理数。
显然这都是正确的推理。因为三段论中每句话均是原子命题，可分别用表示，这样，三段论方法用命题符号表示应为P, Q?R，这在命题逻辑中却无法得到证明。
命题逻辑只能进行命题间关系的推理，无法解决与命题的结构和成分有关的推理问题。为此，著名数学家弗雷格在1879年出版了一部名为《概念文字：一种模仿算术语言构造的纯思维形式语言》的著作，提出一整套相对完备的谓词逻辑演算与推理理论，轰动了整个逻辑学界和数理逻辑学界，被誉为自亚里士多德以来人类在逻辑学方面取得的最大进展。弗雷格通过在命题逻辑中引入个体词、谓词、量词与约束变元等概念，在保持命题逻辑知识体系架构基本不变的情况下，将命题层次上的逻辑演算与推理，推进到更为深入复杂的概念层次，使得数理逻辑能够在概念层次上进行推演。谓词逻辑在数据库与网络通信协议的模型设计、词法分析与代码编译、知识发现与数据挖掘、专家系统的知识表示与推理、自然语言理解与人机交互等多个领域都有着广泛应用。
本章介绍谓词演算与推理的基本知识，包括谓词和量词的基本概念与性质、谓词公式与等价演算、谓词公式的范式、谓词逻辑的推理理论等内容。
3.1  谓词逻辑的基本概念
谓词逻辑的核心思想是将作为命题的陈述句分解成个体词与谓词这两个更为基本的要素。个体词表示各种具体或抽象的对象，相当于陈述句中的主语或宾语部分；谓词则表示对象的属性或对象之间的联系，相当于陈述句中的谓语部分。例如，“离散数学是计算机专业的必修课程”可分解成两个部分：“离散数学”和“是计算机专业的必修课程”，前者是主语而后者是谓语。
3.1.1  个体词与谓词
对于任一给定的原子命题，其主语或宾语是一种可以独立存在的确定对象，我们称之为个体常量，将个体常量抽象成含义不确定的变量后，则称之为个体变量。相关定义如下：
定义3.1.1  客观世界中可以独立存在的具体或抽象对象称为个体（客体）（individual），表示个体的词称为个体词。用以描述个体的性质或个体之间关系的部分称为谓词（predicate）。
分解下列原子命题：
（1）广州是广东省的省会；
（2）离散数学是计算机相关专业的必修课程；
（3）任正非是华为技术有限公司的创始人；
（4）武汉位于广州和北京之间。
以上四个句子都是命题，其中，“广州”“离散数学”“任正非”“武汉”“北京”等都是个体词，而“是广东省的省会”“是计算机专业的必修课程”“是华为技术有限公司的创始人”“位于广州和北京之间”等都是谓词。但在上述例子的描述中，“是……”是描述个体的性质，而“位于……和……之间”是描述多个个体之间的关系。
单独的个体词或单独的谓词都无法构成一个完整的逻辑含义，只有将它们结合起来时才能构成一个完整的、独立的逻辑断言。
定义3.1.2  （1）表示具体的或特定的个体词称为个体常量（individual constant），一般个体词常量用带或不带下标的小写英文字母a, b, c, …, a1, b1, c1, …等表示；
（2）表示抽象的或泛指的个体词称为个体变量（individual variable），一般用带或不带下标的小写英文字母x, y, z, …, x1, y1, z1, …等表示。
定义3.1.3  （1）个体词的取值范围称为个体域（或论域）（individual field），常用D表示；
（2）宇宙间的所有个体域聚集在一起所构成的个体域称为全总个体域（universal individual field）。
个体变量的个体域可根据问题的实际状况或需要来确定。例如，对于含变量语句“x 是大学生”，其中个体变量x的变化范围，可以确定为全体人类，也可以确定为某单位的全体职工，还可以确定为某个大学的全班同学或者某个中学的全班同学，等等。显然，个体变量的个体域的不同，其相应含变量语句的含义也会有所不同。
定义3.1.4  设x1,x2,…,xn为n个个体变量，其个体域均为非空集合D，定义在Dn上取值于{0,1}的n元函数称为n元命题函数或n元谓词（propositional function），记为P(x1,x2,…,xn)，P(x1,x2,…,xn)的值域为{0,1}。
当个体变量x1,x2,…,xn没有赋予确切的个体词时，P(x1,x2,…,xn)就没有确切的真值，即P(x1,x2,…,xn) 不是命题。只有当x1,x2,…,xn指定为具体的个体词或确定了x1,x2,…,xn的某些特定的取值范围时，才能确定P(x1,x2,…,xn)的真假值，此时，P(x1,x2,…,xn)才是一个命题。
例3.1.1  将以下命题用n元谓词进行表示。
P：梁栋是一个运动员；
Q：杨树是杨树苗的父亲；
R：张子江与张子河是兄弟；
S：东莞位于广州和深圳之间。
解  设S(x)：x是一个运动员；
    F(x, y)：x是y的父亲；
    H(x, y)：x与y是兄弟； 
    G(x, y, z)：x位于y和z之间。
个体词：a：梁栋；b：杨树；c：杨树苗；d：张子江；e：张子河；f：东莞；g：广州；h：深圳。则上述命题用n元谓词分别表示为：
P：S(a)；Q：F(b, c)；R：H(d, e)；S：G(f, g, h)。
从上述例子可知，谓词有以下一些特点：
（1） n元谓词中个体词的顺序是十分重要的，不能随意变更。如命题F(b, c)为“真”，但命题F(c, b)为“假”。
（2） 一元谓词用以描述某一个个体的某种特性，而n元谓词则用以描述n个个体之间的关系。
（3） 0元谓词（不含个体词的）实际上就是一般的命题。
（4） 具体命题的谓词表示形式和n元命题函数是不同的，前者是有真值的，而后者不是命题，它的真值是不确定的。如上例中S(a)是有真值的，但S(x)却没有真值。
（5） 一个n元谓词不是一个命题，但将n元谓词中的个体变元都用个体域中具体的个体取代后，才有可能成为一个命题。而且，个体变元在不同的个体域中取不同的值对是否成为命题及命题的真值有很大的影响。 
3.1.2  量词
例如，对于前述三段论中的命题“所有人都是要死的”，句中的主语“人”其实并不是一个具体的个体常量，而是一个变量，但是整个句子却是一个真命题。原因是句中的“人”受到“所有的”这个词的限定，使得整个语句具有明确的含义。
例3.1.2  用谓词符号表示下述命题：
（1）每一个大学生都会说英语；
（2）所有的人都长着黑头发；
（3）有些人登上过月球；
（4）有些自然数是素数。
解  设P(x)：x会说英语；
     Q(x)：x长着黑头发；
     R(x)：x登上过月球；
     S(x)：x是素数。 
则有：（1）每一个x，P(x)，x∈{大学生}；
     （2）所有的x，Q(x)，x∈{人}；
     （3）有些x，R(x)，x∈{人}；
     （4）有些x，S(x)，x∈{自然数}。
在上述例子中，句子中的“每一个”“所有的”“有些”等无法用谓词来表示，这些都是与个体词的数量有关，包括数量的有和无，全体与部分这两种。为此，需要在n元谓词的前端加入一个限制词，这个限制词就是量词，用于刻画个体中量的特性。表示“所有的x”“任意的x”“每一个x”“一切x”等称全称量词，表示“有些x”“至少有一个x”“某一些x”“存在x”等称存在量词。具体定义如下：
定义3.1.5  称为全称量词（universal quantifier），为存在量词（existential quantifier），其中的x称为作用变量，一般将量词加在谓词F(x)之前，分别记为F(x)，F(x)。此时，F(x)称为全称量词和存在量词的辖域（scope）。
因此，上述句子可符号化为：
（1）P(x)，x∈{大学生}；
（2）Q(x)，x∈{人}；
（3）R(x)，x∈{人}；
（4）S(x)，x∈{自然数}。
谓词逻辑符号化过程中，如将命题(1)和(4)的合取为一个新命题，其中中的x∈{大学生}，而中的x∈{自然数}，该谓词式的个体域就比较含糊和混乱。如果有多个类似的命题谓词式进行复杂的逻辑运算，那么个体域的确定是一件非常麻烦的事情。
另一方面，对于一个命题的谓词表达式，其个体域的确定又是非常重要的。因为个体域的差异往往会导致其真值取值的不同。例如对于命题“所有人都是大学生”，如果个体域是某大学的某个班，那么该命题显然为真；如果个体域是某中学的某个班，那么该命题显然为假；如果个体域为某电影院某场电影的全体观众，那么命题的真值就比较难以确定。
为此需要将个体域统一，在未加特殊说明情况下个体域均指全总个体域，让所有的谓词和命题函数共用全总个体域，不同的个体变量通过设立与其含义相对应的特性谓词来确定其个体域。
例如，设特性谓词(x)表示：x是大学生，则命题“每一个大学生都会说英语”，就可符号化为：((x)→P(x))。该谓词式准确而完整地表达了命题的含义，可理解为：对于全总个体域中的每个x，如果x是大学生，则x一定会说英语。
如果将命题“每一个大学生都会说英语”符号化为：((x)∧P(x))。则这种表达显然是错误的，因为该式的含义是：“对于任意的一个对象x，x是大学生，并且x会说英语”，这与命题所表达的逻辑含义不符。
同理，可以设定特性谓词H(x)表示：x是人，则命题“有些人登上过月球”，就可以符号化为：(H(x)R(x))。该谓词式准确而完整地表达了命题的含义，可理解为：在全总个体域中存在一些x，这些x不仅是人，而且登上过月球。
如果将命题“有些人登上过月球”符号化为：(H(x) → R(x))。则这种表达显然是错误的，因为该式的含义是：“存在一些对象x，只要x是人，则x一定登上过月球”，这与命题所表达的逻辑含义不符。
综上所述可知，特性谓词的使用与量词类型有着密切关系，具体方法如下：
（1）对于全称量词，刻画其作用变量 x的个体域的特性谓词作为条件式前件加入；
（2）对于存在量词，刻画其作用变量 x的个体域的特性谓词作为合取项加入。
设特性谓词U(x)：x是大学生； 
          M(x)：x是人；
          N(x)：x是自然数。
以此类推，例3.1.2中的命题可符号化为：
（1）
（2）
（3）
（4）
在用谓词逻辑对语句进行符号化时，没有特别说明的情况下，总是假定个体域为全总个体域。首先找出每个语句中所有具体的个体域，分别用一元特性谓词表示它；然后确定语句中反应个体性质或者个体之间关系的谓词，并用合适的n元谓词表示它；最后确定量词是全称量词还是存在量词。
例3.1.3  用谓词逻辑符号化下述命题：
（1）有的鱼会飞；
（2）尽管有人很聪明，但未必一切人都聪明；
（3）天下乌鸦一般黑。
解  （1）设谓词F(x)：x会飞，特性谓词H(x)：x是鱼，则命题可符号化为：
(H(x)F(x))。
（2）设谓词 (x)：x聪明，特性谓词M(x)：x是人，则命题可符号化为：
     (M(x)C(x))(M(x)C(x))
（3）设谓词G(x,y)：x与y一般黑，特性谓词U(x)：x是乌鸦，则命题可符号化为：
     (U(x)U(y)G(x,y))
例3.1.4  用谓词逻辑符号化下述命题：
（1）兔子比乌龟跑得快；
（2）有的兔子比所有乌龟跑得快；
（3）并不是所有的兔子都比乌龟跑得快；
（4）不存在跑得同样快的两只兔子。 
解  谓词设定如下：
P(x)：x是兔子；Q(x)：x是乌龟；
R(x, y)：x比y跑得快；
T(x, y)：x与y跑得同样快。 
那么命题可以符号化为：
（1）(P(x)∧Q(y)→R(x, y)) ；
（2）(P(x)∧(Q(y)→R(x, y))) ；
（3）(P(x)∧Q(y)→R(x, y))
     或者(P(x)∧Q(y)∧R(x, y))；
（4）(P(x)∧Q(y)∧T(x, y))
     或者(P(x)∧Q(y)→T(x, y))。
例3.1.5  符号化下述一组语句：
只要是需要室外活动的课，郝亮都喜欢；所有的公共体育课都是需要室外活动的课；篮球是一门公共体育课；郝亮喜欢篮球这门课。
解  设谓词O(x)：x是需要室外活动的课；L (x, y)：x喜欢y；
S (x)：x是一门公共体育课；Hao：郝亮；Ball：篮球。
上述句子可符号化为：
(O(x)→L(Hao, x))；
(S(x)→O(x))；
S(Ball)；L(Hao, Ball)。
3.1.3  谓词的语言翻译
从前面的例子可知，若设G(x)是关于x的一元谓词，D是其个体域。
由全称量词定义可知，P(x)表示这样的一个命题：“对于D中任意一个个体x，P(x)均为真”。因此，P(x)作为一个具体命题，其真值应按如下方式确定：
G(x)取值“真”当且仅当对任意一个个体x∈D，G(x)都取“真”值；
G(x)取值“假”当且仅当至少存在一个个体x0∈D，使G(x0)取“假”值。
类似地，由存在量词定义可知，G(x)表示这样的一个命题："D中至少一个个体x0，使得G(x0)的取值为真"。因此，G(x)作为一个具体命题，其真值应按如下方式确定：
G(x)取值“真”，当且仅当至少存在一个个体x0∈D，使得G(x0)的取值为“真”；
G(x)取值“假”，当且仅当对于任意一个个体x∈D，都使得G(x)的取值为“假”。
例3.1.6  设个体域D = {2, 3, 4}，谓词P(x): x > 3。试判断P(x)与P(x)的真值。
解  由于个体域D = {2, 3, 4}中存在个体2、3，使得P(2)、P(3)为假，故有命题P(x)为假。
由于个体域D = {2, 3, 4}中存在个体4，使得P(4)为真，故有命题P(x)为真。
例3.1.7  设P(x)：x是素数；I(x)：x是整数；Q(x，y)：x+y=0。用自然语句描述下述谓词式，并判断其真假值。
（1）(I(x)P(x))；
（2）(I(x)P(x))；
（3）(I(x)I(y)Q(x,y))；
（4）(I(x)(I(y)Q(x,y)))
（5）(I(x)I(y)Q(x,y))。
解  上述式子可描述为：
（1）“对任意的整数x，x一定是素数”，真值为“假”；
（2）“存在一些整数x，x也是素数”，真值为“真”；
（3）“对任意的整数x，y，都有x+y=0”，真值为“假”；
（4）“对任意的整数x，都存在着整数y，使得x+y=0”，真值为“真”；
（5）“存在着整数x，使得对任意的整数y，都有x+y=0”，真值为“假”。
从上面的例子可知，如有多个量词，则按从左到右的顺序读出，另外，量词对变元的约束，往往与量词的次序有关，不同的量词次序，可以产生不同的真值。当多个量词同时出现时，不能随意颠倒它们的顺序。在后续相关部分将对此内容做进一步分析讨论。
3.2  谓词公式与解释
谓词逻辑的问题求解思路与命题逻辑类似，首先通过符号化将现实问题抽象成谓词符号形式，然后使用谓词逻辑的符号演算机制实现对问题的求解。因此，谓词符号的表达系统和演算机制是谓词逻辑理论的核心内容。本节学习谓词公式的概念、自由变元与约束变元、谓词公式的解释与分类、谓词公式的等价关系与演算等。
3.2.1  谓词公式的概念
类似于命题逻辑，谓词逻辑采用谓词公式对命题进行表达。但谓词公式的定义比命题公式更复杂，因为谓词公式的表达要深入到概念层次，需要用到更多种类的特殊符号来表达命题在概念层次上的各种组件。具体地说，除了前述两种量词符号之外，还有四种特殊符号，即表示个体的个体常量符号、个体变量符号、个体函数符号，以及表示谓词的谓词符号。这四种符号的表达方式如下：
（1）个体常量符号：用带或不带下标的小写英文字母a，b，c，…，a1，b1，c1，等表示。当个体域D给定时，它可以是D中的某个元素。
（2）个体变量符号：用带或不带下标的小写英文字母x，y，z，…，x1，y1，z1，等表示。当个体域D给定时，它可以是D中的任意元素。
（3）个体函数符号：用带或不带下标的小写英文字母f，g，h，…，f1，g1，h1等表示。当个体域D给定时，n元函数符号f(x1,x2,…,xn)是DnD的任意一个函数。
（4）谓词符号：用带或不带下标的大写英文字母P，Q，R，…，P1，Q1，R1等来表示。当个体域D给定时，n元谓词符号P(x1, x2, …, xn)可以是Dn{0,1}的任意一个谓词。
为何需要个体函数符号？
例如：（1）符号化“周红的父亲是教授”。
设f(x)：x的父亲；P(x)：x是教授；c：周红
P(f(c))表示“周红的父亲是教授”。
（2）“周红和他的父亲及祖父一起去看电影”怎么符号化呢？
令谓词R(x,y,z): x和y及z一起去看电影。那么该命题可符号化为：R(c, f(c), f(f(c)))。
个体函数的使用为谓词逻辑中个体之间关系的表达带来了方便，大大提升了谓词逻辑符号系统的表达能力。基于个体函数，可按如下方式定义一个称之为个体项的概念来专门表达谓词逻辑中的个体之间复杂的映射关系：
定义3.2.1  谓词逻辑中的个体项，被递归地定义为： 
（1）个体常量符号是个体项；
（2）个体变量符号是个体项； 
（3）若f(x1,x2,…,xn)是n元函数符号，t1,t2,…,tn是个体项，则f(t1,t2,…,tn)是个体项；
（4）有限次使用（1），（2），（3）生成的符号串才是个体项。
例如下面符号串是个体项：
（1）复合函数f(g(x, y)，h(a, g(x, y), z))是一个个体项。
（2）设f(x)：x的父亲；P(x)：x是教授；c：吴良。则f(c)是一个项，此时P(f(c))表示命题“吴良的父亲是教授”。
由定义3.2.1可知，个体项具有强大的表达能力，能有效地表达个体以及个体之间复杂的映射关系，谓词中的个体常量、个体变量和个体函数都可以统一用个体项的概念进行表达。例再如，令g(x)表示“x的叔叔”；P(x)表示“x是医生”；c表示“周红”，则P(g(x))表示命题“周红的叔叔是医生”。
在谓词逻辑中也包含命题变元和命题联结词，谓词公式是由联结词、谓词与量词按照一定规则构成的。有了个体项的概念，可在元谓词的基础上得到如下原子谓词公式的定义：
定义3.2.2  若P(x1, x2,…, xn)是n元谓词，t1, t2,…, tn是个体项，则称P(t1, t2,…, tn)是原子谓词公式，简称原子公式。
定义3.2.3  谓词合式公式亦称为谓词公式，按下列递归方式定义：
（1）原子公式是谓词公式；
（2）若G，H是谓词公式，则G，H，GH，GH，GH，GH也是谓词公式；
（3）若G是谓词公式，x是个体变量，则G，G也是谓词公式；
（4）仅仅有限次使用（1）、（2）、（3）产生的符号串才是谓词公式。 
由上述定义可知，谓词公式是原子公式、命题联结词、量词、圆括号等按上述规则组成的符号串，且命题公式是谓词公式的特例。为方便起见，谓词公式中的括号可以像命题公式那样约定省略最外层括号。
例如：(P(x, y) → (Q(x, y)?R(x, a, f(z))))，(P(x)R(x, y))等都是谓词公式；(P(x) →R(x),(P(x, y))等则都不是公式，前者括号不配对，后者联结词无联结对象。
例3.2.1  说明下列公式中哪些是谓词公式，哪些不是谓词公式。
（1）Q(x, y)P(x) )R(x, y, z)；
（2）Q(x, y)P(a)；
（3）P(f(y), z)；
（4）(Q(x, y)P(x, z))(R(f(x), x3) → S(x1))。
解  （1）Q(x, y)P(x) )R(x, y, z)不是谓词公式，因为少了括号。
（2）Q(x, y)P(a)中全称量词虽无效，但不影响它满足定义，故是谓词公式。
（3）P(f(y), z)中存在量词有效，是谓词公式。
（4）(Q(x, y)P(x, z))(R(f (x), x3) → S(x1))是谓词公式。
3.2.2  自由变元和约束变元
对于谓词公式P(x)Q(x,y)，量词的辖域为P(x)，而谓词Q(x,y)中的变元x，y不受量词的约束，为此需要对谓词公式中的变元是否受到约束加以区分。首先给出量词辖域的相关概念。
定义3.2.4  假设G是任意一个含有个体变量x的谓词公式，在公式G或G中，称G为量词或的辖域，辖域即是量词或的作用变量x在G中存在的范围。如果辖域不是原子谓词公式，其两侧必须有圆括号，否则不需要圆括号。
例如：在谓词公式(P(x, y) → Q(x, y))P(y, z)中，的辖域是(P(x, y) → Q(x, y))。
在谓词公式P(x) → Q(x)中，的辖域是P(x)。
一般来说，一个量词的辖域是某个谓词公式的子公式。因此，确定一个量词的辖域就是要找出位于该量词之后与之相邻接的子公式，具体方法如下：
（1）若量词后面有括弧，则括弧内的子公式就是该量词的辖域；
（2）若量词后面无括弧，则与该量词邻接的子公式为该量词的辖域。
定义3.2.5  设G是任一谓词公式，x是G的任意一个个体变量，若变量x出现在或的辖域之内，则称x在公式G中的该次出现是约束出现，称变量x为约束变量（变元）；若x在公式G中的某次出现不是约束出现，则称x在公式G中的该次出现为自由出现，称变量x为自由变量（变元）。
例3.2.2  指出下列谓词公式中的约束变元和自由变元。
（1）；
（2）	；
（3）。
解  在（1）中，全称量词的辖域为，而的辖域为，因此变元x是约束变元，但在前、后两个子式中约束方式不同；变元y在子式中是约束出现，但在子式是自由出现，所以y既是谓词公式的约束变元又是自由变元。变元z是谓词公式的自由变元。
在（2）中，全称量词第一次出现的辖域为，第二次出现的辖域为，而公式最后的变元x是自由出现，所以x是该公式的约束变元又是自由变元。
在（3）中，公式中除了最后的变元x是自由出现，其他变元均受约束，所以x是该公式的约束变元又是自由变元。
从上例可知，在一个公式中，某一个变元的出现既可以是自由的，又可以是约束的。为了使得研究更方便，而不致引起混淆，对于表示不同含义的个体变元，用不同的变量符号来表示之。对于任意一个含有量词的谓词公式，以约束方式出现的个体变量到底用哪一个字母表示其实是无关紧要的。
约束变元的换名规则：
（1）将量词中出现的变元以及该量词辖域中的所有约束变元都用新的个体变元替换。
（2）新的变元一定要有别于该辖域中的所有其他变元名。
自由变元的代入规则：
（1）将公式中出现该自由变元的每一处都用新的个体变元替换；
（2）新变元不允许在原公式中以任何约束形式出现。
例3.2.3  （1）将公式中的约束变元x进行改名；
（2）将公式中的自由变元x进行代入。
解  （1）利用约束变元的换名规则，将约束变元x改名为y，改名后的谓词公式。
（2）利用自由变元的代入规则, 将自由变元x的位置用y进行代入，得到谓词公式：。
例3.2.4  对于公式(P(x) →Q(x,y)) ∧R(x,y)，试通过使用换名规则和代入规则，将其中的自由变元和约束变元加以区分。
解  使用约束变量改名规则对x进行改名，则合法的改名可以是(P(z)→Q(z, y)) R(x, y)。不合法的改名有(P(z) → Q(x, y))R(x, y), (P(y) → Q(y, y))R(x, y)等。使用自由变元代入规则对y进行代入，则合法的代入有(P(x) → Q(x, z))R(x, z)，但这个公式中x既约束变元又自由变元，为了达到可区分，将那个自由变元x用w代入，则到公式(P(x) → Q(x, z))R(w, z)。
定义3.2.6  设G是一个公式，若G中无自由出现的个体变元，则称G为封闭的合式公式，简称闭式。
例如，(P(x) →R(x, y))就是一个闭式。显然，要想使得含有n个自由变量的谓词公式变成闭式，需要添加n个量词。
3.2.3  谓词公式的解释
对于一个命题公式，确定其真值取值状态是比较简单的，只需对命题公式中各个变量逐个指派真值便可得到命题公式的真值，且命题变量不多时，可对命题变量真值指派的各种状态进行枚举列出命题公式的真值表。然而，要确定一个谓词公式的真值取值状态，通常就没有这么简单了。
例如，要确定谓词公式(H(x)→D(x))的真值，首先要确定其个体域，然后还要确定谓词H(x)和D(x)的具体含义。如果使用全总个体域，H(x)：x是人，D(x)：x会死的，则该谓词公式的取值为真；若D(x)：x会骑马，则谓词公式的取值为假。
一般来说，对于任意给定的谓词公式，其含义与真值取值不仅依赖于个体域，依赖于公式中各个个体变量的取值状况，还依赖于对公式中谓词符号、函数符号、常量符号具体含义的确认，这些所有的依赖信息构成对谓词公式的解释。下面给出关于谓词公式解释的具体定义：
定义3.2.7  谓词逻辑中公式G的每一个解释I由如下四部分组成：
（1）非空的个体域集合D；
（2）G中的每个常量符号的含义，指定D中的某个特定的元素；
（3）G中的每个n元函数符号的具体形式，指定Dn到D中的某个特定的函数；
（4）G中的每个n元谓词符号的具体形式，指定Dn到{0,1}中的某个特定的谓词。
易知，对于任意一个给定的谓词公式，如果该公式是封闭公式，即不含有任何自由个体变量，则该公式在任何解释下均有确定的真值，此时的谓词公式就成为一个有确切意思的命题。而任何包含有自由变元的公式都不能求值。
例3.2.5  给定解释I如下：
设个体域D为有理数集，f、g和h是二元运算符号，具体为：，，；a =0，b=1，谓词公式P(x,y): x=y。
那么以下谓词公式在解释I下为真值是真还是假。
（1）；
（2）；
（3）。
解  （1）在解释I下，公式的含义为：。
当x=y=2时，公式为真；当x=1，y=0时，公式为假。故公式在解释I下无确切真值。
（2）在解释I下，公式的含义为：。
无论x取什么有理数，等式均成立。所以公式在解释I下为真。
（3）在解释I下，的含义为：存在x使得。当y取非0有理数时，命题为真；当y取0时，命题为假。因此公式无确切真值。
例3.2.6  设有解释I为：
（1）个体域为D={,}；
（2）c指定为；
（3）f ()指定为，f ()指定为；
（4）P()指定为1，P()指定为0；Q(,)指定为0，Q(,)指定为l，Q(,)指定为1，Q(,)指定为1。
判断公式在解释I下的真值。
解  由于公式是由存在量词加以限制的，根据存在量词的定义，只要个体域中有一个x使得为真，则谓词公式的真值为真。只有当个体域中全部的x代入后，都使得为假，则该公式为假。
当x=时，有
f()=，P(f(x))= P(f())=P()=1,
f(c)= f()=, 
所以，
所以存在x=，使得为真，即公式在解释I下的真值为真。
例3.2.7  求公式((x)(P→Q(x))(R(a)的真值，其中P：2>1，Q(x)：x≤3，R(x)：x>5，a：5，论域是{(2，3，6}。
解  由于P为真，Q(6)为假，所以P→Q(6)为假，根据全称量词的定义可得((x)(P→Q(x))为假。而R(a)为假，从而((x)(P→Q(x))(R(a)的真值为假。
3.2.4  谓词公式的分类
例3.2.8  对于谓词公式：P(a) → ((x)P(x)和((x)P(x) → P(a)，判断其在任意解释下的真值结果。
解  对于公式：P(a) → ((x)P(x)，其前件P(a)在指定个体词 a 后，必出现在谓词((x)P(x)中；当P(a)取值为真时，((x)P(x)必为真。此时谓词公式P(a) → ((x)P(x)的真值为真。当P(a)为假时，((x)P(x)无论真假，均有P(a) → ((x)P(x)为真。
对于公式((x)P(x) → P(a)，其后件P(a)在指定个体词 a 后，也必然出现在谓词((x)P(x)中。当((x)P(x)真时，P(a)必为真，此时((x)P(x) → P(a)的真值为真。当((x)P(x)假时，P(a)无论真假，公式((x)P(x) → P(a)的真值必为真。
因此，对于任何的解释I，根据P(a)，((x)P(x)，((x)P(x)的真值结果，即可判断公式P(a) → ((x)P(x)和((x)P(x) → P(a)的真值取值永远为真。所以，公式P(a) → ((x)P(x)和((x)P(x) → P(a)在一切解释下恒为真。
由上述例题可知，与命题公式一样，有些谓词公式在有些解释下为真，在另外一些解释下为假；而有些谓词公式则在所有解释下均为真；还有一些谓词公式在所有解释下均为假。
定义3.2.8  （1）对于任意一个给定的谓词公式G，如果G在所有的解释I下取值都为“真”。则称谓词公式G为永真式，也称为有效公式。
（2）谓词公式G称为矛盾公式，如果G在所有的解释I下取值都为“假”，则称谓词公式G为永假式。
（3）谓词公式G称为可满足公式，如果至少有一种解释I使得G取值为“真”。
从上述定义可知三种特殊公式之间的关系：有效公式的否定为矛盾公式；矛盾公式的否定为有效公式；有效公式一定为可满足公式。
例3.2.9  分析以下谓词公式的类型。
（1）
（2）
（3） 
解  （1）要使得公式在解释I下为假，只需当为真时，为假。为真要求在个体域中每个元素都具有性质P。为假，就是个体域中每个元素都不具有性质P。当为真时，不可能为假。所以公式是永真式，即是有效公式。
（2）要使公式在任何解释I下为真，必然有和同时为真。而为真的含义为“在个体域中的任何元素都没有性质P”；为真的含义为“个体域中存在一些元素具有性质P”。这两个要求相互矛盾，所以公式为永假式，即为矛盾公式。
（3）公式既不是永真式也不是永假式。首先给出一个使前件为假的解释，令个体域D表示“自然数”。 
P(x)：x为奇数，Q(x)：x为偶数。
因此，的含义为“存在x既是奇数也是偶数”。
故前件为假，所以公式为真，即不是永假式。
另外，假设个体域D表示“正整数”，
P(x) ：x为素数，Q(x)：x为偶数。
的含义为“存在x既是素数又是偶数”，当x=2时，该式为真。同时的含义为“所有x都是素数”为假。所以，为假，即该公式不是永真式。
3.2.5  谓词公式的等价关系
在命题逻辑中，命题公式之间的等价关系和永真蕴含关系是两种非常重要的基本关系， 使用这两种关系，不仅可以对命题公式进行化简和适当的变形，而且还可以进行有效的命题推理。类似于命题逻辑，在谓词逻辑中也需要定义谓词公式之间的等价关系和永真蕴含关系来实现对谓词公式进行化简或适当的变形，更需要这两种关系进行谓词逻辑的推理。下面介绍和讨论谓词公式的等价关系。
定义3.2.9  谓词公式G，H称为等价的，记为GH，如果谓词公式GH是有效公式（永真式）。
由上述定义可知，判断两个谓词公式G和H是否等值，关键在于证明谓词公式GH为有效公式，这种思路与证明命题公式等价关系的基本思路是一致的。
当个体域D={x1,x2,…,xn}是有限集合时，则G(x)，G(x)的真值可以用与之等价的谓词公式来表示。
有限论域上量词的消去律：个体域D={x1,x2,…,xn}，则 
                        	G(x)G(x1)G(x2)…G(xn)   
                        G(x)G(x1)G(x2)…G(xn)
定义3.2.10  设G(P1,P2,…,Pn)是命题演算中的命题公式，而P1,P2,…,Pn是出现在G中的命题变元，当用任意的谓词公式Gi(1≤i≤n)分别代入Pi后，得到的新谓词公式G(G1,G2,…,Gn)称为原公式的代入实例。
定理3.2.1  永真公式的任意一个代入实例必为有效公式（永真公式）。 
根据定理3.2.1，永真公式的代入实例必为有效公式，这样就可以将命题演算中的永真公式“移植”到谓词逻辑中来。即命题演算中的24组基本的等值式E1-E24在谓词演算中仍然成立，除此以外，由于谓词公式本身的特殊性（引进了谓词和量词的概念），除了上述有效公式以外，还有以下基本的一些基本等值式。
假设G(x)，H(x)是只含自由变元x的公式，S是不含x的公式，则在全总个体域中，有如下等价公式：
（1）更名规则
     E25：  
     E26：
（2）量词转换律
     E27：
     E28：
（3）量词辖域的扩张与收缩律
     E29：
     E30：
     E31：
     E32：
（4）量词分配律
     E33：
     E34：
（5）量词交换律
     E35：
     E36：
但是需要注意，相对于公式E33和E34，下列等值式
         
         
是不成立的。但是有：
             
	         
上述基本的等价关系式很多可以互相推导。特别是当个体域为有限集时，很容易证明和理解上述等价关系的合理性。
例如，设P(x)：x今天上课，个体域为计算机学院全体学生的集合，则：
((x)P(x)：今天所有学生都上课了；?((x)P(x)：今天不是所有学生上课了；((x)?P(x)：今天有学生没上课。即有：?((x)P(x) ( ((x)?P(x)。
((x)P(x)：今天有学生上课；?((x)P(x)：今天没有学生上课；((x)?P(x)：今天所有学生都没上课。即有：?((x)P(x) ( ((x)?P(x)。
再如，设谓词G(x)：x 勤奋学习，H(x)：x喜欢体育运动，个体域是某大学里的全体学生。则有：
谓词公式((x)(G(x)H(x))：“某大学里的所有学生既勤奋学习又喜欢体育运动”； 
谓词公式((x)G(x)((x)H(x)：“某大学里的所有学生都勤奋学习且大学里的所有学生都喜欢体育运动”。
两者含义显然相同，即有((x)(G(x)(H(x)) ( ((x)G(x)(((x)H(x)。
谓词公式 ((x)(G(x) ( H(x))：“某大学里有些学生勤奋学习或喜欢体育运动”；
谓词公式((x)G(x) ( ((x)H(x)表示：“某大学里有些学生勤奋学习或大学里有些学生喜欢体育运动”。
两者的含义显然相同，即有((x)(G(x) (H(x)) ( ((x)G(x) ( ((x)H(x)。
例3.2.10  设个体域D={a,b,c}，将下列各公式的量词消去。
（1）
（2）
（3）
解  （1）
  （2）
  					                        
（3）
          				     	
                      				
例3.2.11  证明下列各等式。
（1）
（2）
证明  （1）  
          
（2）   
     
例3.2.12  证明下列关系表达式
（1）((x)(G(x)(H(x))  ((x)G(x) ( ((x)H(x)；
（2）((x)(G(x)(H(x))  ((x)G(x) ( ((x)H(x)；
证明  只需证明((x)(G(x) ( H(x))?((x)G(x) ( ((x)H(x)不是有效谓词公式即可。为此，需要举出一个反例。现取解释I为：个体域为自然数集合，G(x)：x是奇数，H(x)：x是偶数。则在上述解释下，((x)(G(x) ( H(x))显然是一个真命题，而((x)G(x) ( ((x)H(x)则显然是一个假命题。故((x)(G(x) ( H(x))?( (x)G(x) ( ((x)H(x)不是有效谓词公式。故关系式（1）成立。关系式（2）可类似证明。
上述例题表明，全称量词(对析取运算(没有分配律，存在量词(对合取运算 ( 没有分配律。
3.3  谓词公式的范式
	命题逻辑中每个命题公式都有一种统一的范式表达方式，当考察一个命题公式性质时， 其范式表达方式通常起着非常重要的作用，有时候甚至是决定性作用。类似于命题逻辑，谓词逻辑也希望建立谓词公式的范式。由于谓词公式中存在个体变量和量词，因此其范式的建立比命题公式要复杂得多，而且所建立范式不满足唯一性要求，有的范式甚至不能满足等价。
3.3.1  谓词公式的前束范式
定义3.3.1  称谓词公式G是一个前束范式，如果G中的一切量词都位于公式的最前端（不含否定词）且这些量词的辖域都延伸到公式的末端，即若G具有如下形式： 

其中Wi为量词或(i=1,2,…,n)，而是不含任何量词的谓词公式，称为公式G的母式（基式）。
例如，是前束范式，而不是前束范式。
定理3.3.1  谓词逻辑中的任一谓词公式都可转化为与之等价的前束范式，但前束范式不唯一。
证明  设G是任一谓词公式，通过下述步骤可将其转化为与之等价的前束范式：
（1）如公式中有联结词“”“”，则消去联结词“”“”；
（2）反复运用德摩根定律，直接将“”移到原子公式的前端；
（3）使用谓词的等价公式将所有量词提到公式的最前端。
经过这几步，便可求得任一谓词公式的前束范式，由于每一步变换都保持着等价的关系，所以，所得到的前束范式与原公式是等价的。
例3.3.1  求下列公式的前束范式。
（1）
（2）
解  （1）
    
（2）
 
例3.3.2  求公式((x)(((y)P(x) ( ((z)Q(z, y) →((y)R(x, y))的前束范式。
解  具体求解过程如下：
? ((x)(((y)P(x) (((z)Q(z, y) →((y)R(x, y))
( ((x)(P(x) ( ((z)Q(z, y) →((y)R(x, y))
( ((x)(P(x) ( ((z)Q(z, y) → ((w)R(x, w))
( ((x)((P(x) ( ((z)Q(z, y)) ( ((w)R(x, w))
( ((x)((P(x) (((z)Q(z, y)) ( ((w)R(x, w))
( ((x)((P(x) ( ((z)Q(z, y))( ((w)R(x, w))
( ((x) ((z) ((w)((P(x) (Q(z, y)) ( R(x, w))
( ((x) ((z) ((w)((P(x) ( R(x, w)) ( (Q(z, y) ( R(x, w)))
由于前束范式中量词的顺序可以不同，因此其前束范式可能不唯一。
3.3.2  Skolem标准型
定义3.3.2  设谓词公式G是一个前束范式，消去G中所有的存在量词和全称量词，所得到的公式称为Skolem标准型，简称S范式。
定理3.3.2  任意一个谓词公式G都有相应的Skolem标准型存在，但此Skolem标准型不一定与原公式等价。
证明  由定理3.3.1知谓词公式G必有与之等价的前束范式，设G的前束范式为：。
（1）如果Wi是存在量词，且Wi的左边没有全称量词，则直接用一个常量符号a来取代xi在中一切出现处，且该a不同于H中的任何其他常量符号；
（2）如果Wi是存在量词，且Wi的左边有全称量词, , ,，则直接用一个函数来取代xi在H中一切出现处，该函数符号f不同于H中的任何其他函数符号；
（3）如果Wi是全称量词，则直接用一个变量符号x来取代x在H中一切出现处，且该x不同于H中的任何其他变量符号。
有限次的使用上述（1）~（3）之后，可消除前束范式中所有存在量词和全称量词，此时得到的公式为该谓词公式的Skolem标准型。该S标准型与原公式不等价的，但在不可满足性方面，二者是等价的。也就是说，如果原式是不可满足的，则其对应的S范式也一定是不可满足的。反之亦成立。
例3.3.3  求谓词公式的Skolem标准型。 
解  （1）消去：由于其左边没有全称量词，所以直接用一个常量符号a来取代P中的x；
（2）消去：直接用一个变元符号y取代P中的y；
（3）消去：直接用一个变元符号z取代P中的z；
（4）消去：由于其左边有全称量词、，所以直接用-个函数符号来取代P中的u；
（5）消去：直接用一个变元符号v取代P中的v；
（6）消去：由于其左边有全称量词y，z，v，所以直接用一个函数符号来取代P中的w。
故得谓词公式的Skolem标准型为

3.4  谓词逻辑推理理论
与命题逻辑类似，谓词逻辑的演绎推理是学习和研究谓词逻辑的主要目的。谓词逻辑的推理演算方法可以看成是命题逻辑推理演算方法的自然延伸。命题逻辑推理系统中的很多概念、等价式、永真蕴含式、推理规则和推证策略都可以在谓词逻辑推理中得到直接应用或类似应用。与命题逻辑推理不同的是，谓词公式中含有个体词、谓词、量词等新概念，具有比命题公式更加丰富、深刻、复杂的表达形式。因此，谓词逻辑推理需要引入一些新的规则来处理这些概念，从而得到比命题逻辑推理更加精细的推理结论。
3.4.1  谓词公式的蕴含关系
谓词公式的逻辑演算与推理不仅要用到谓词公式之间的等价关系，还要用到谓词公式之间的蕴含关系。具体地说，所谓两个谓词公式之间存在蕴含关系，其实就是两个谓词公式在任何解释下，其中一个谓词公式的真值永远不会大于另外一个谓词公式的真值。
定义3.4.1  假设G和H是任意两个谓词公式，如果谓词公式G→H是有效公式，则称谓词公式G逻辑蕴含谓词公式H，亦称G与H之间具有逻辑蕴含关系，通常简称为蕴含关系，记作G(H，并称该式为谓词公式的逻辑蕴含式，通常简称为蕴含式。
由上述定义可知，判断两个谓词公式G和H是否具有逻辑蕴含关系，关键在于证明谓词公式G→H为有效公式，这种思路与证明命题公式永真蕴含关系的基本思路是一致的。推广到前提是多个谓词公式的逻辑蕴含关系，定义如下：
定义3.4.2  设G1,G2,…,Gn，H是谓词公式，如果谓词公式G1G2…Gn→H是有效公式，则称谓词公式G1,G2,…,Gn逻辑蕴含谓词公式H，记为G1,G2,…,GnH。G1,G2,…,Gn称为一组前提，记={G1,G2,…,Gn}，H称为结论，又称H是前提集合的逻辑结果，记为H。
在谓词公式的逻辑蕴含演算系统中，通常也是先证明出一些重要的谓词公式蕴含式，然后将这些重要谓词蕴含式作为基本蕴含式进一步推演出更多的谓词公式蕴含式，这种推演过程构成了谓词公式蕴含演算的主要内容。下面不加证明地给出这些重要而基本的谓词公式蕴含式，读者可自行给出证明。
谓词逻辑基本蕴含式：
假设G(x)，H(x)是只含自由变元x的公式，则在全总个体域中，有：
（1）I16：
（2）I17：
     I18：
（3）I19：
     I20：
对于多个量词的公式，也有如下的一些基本等价公式和蕴含公式。设G(x, y)是含有自由变元x，y 的谓词公式，则有：
（4）I21：
     I22：
     I23：
     I24：
     I25：
     I26：
3.4.2  谓词公式推理系统
谓词公式的推演系统与命题公式的推演系统非常类似，主要由有效推理的基本概念、事实库、公理库和推理规则这几个部分组成。事实库和公理库构成谓词公式推理的基本依据，推理规则是谓词公式推理的核心机制。谓词公式推演系统的公理库和推理规则不仅涵盖了命题公式的推演系统的所有相关内容，而且更加丰富、复杂。
定义3.4.3  设G1, G2,…,Gn，H是一些谓词公式，如果它们满足下列性质：对于这些公式的任意一个解释I，G1, G2 ,…,Gn在该解释下同时为真的情况下H在该解释下也为真，则称公式G1, G2 ,…,Gn可有效推出公式H，或称由G1, G2,…,Gn得到H的逻辑推理为有效推理，并称G1, G2,…, Gn为推理前提，H为G1,G2,…,Gn的逻辑结论。
定理3.4.1  公式H可从前提集合={G1,G2,…,Gn}有效推出当且仅当G1G2… Gn H为有效公式。
谓词公式的推理依据主要是谓词公式推演系统中的事实库和公理库。事实库由具体谓词逻辑推理实例的所有前提条件以及推理过程中产生的有效中间结论组成；公理库不仅包含命题逻辑推演系统的公理库，即关于命题公式的基本等价式和基本永真蕴含式，而且还包含了关于谓词公式的所有基本等价式和基本逻辑蕴含式等。
现在着重介绍谓词公式的推理规则。由于在谓词合式公式中含有大量的量词，直接对其进行推理显然十分不便。为此，谓词公式推演系统引入一些专门处理量词的规则，以便在需要的时候可以方便地增加或消除量词。谓词逻辑中主要有全称特指、存在特指、全称推广和存在推广这四条基本的量词处理规则，其中全称特指和存在特指消除量词的规则，全称推广和存在推广则是添加量词的规则。
1. 消除量词的规则
US规则（全称特指规则）：，其中c为任意个体常量。
ES规则（存在特指规则）：，其中c为特定个体常量。
US 规则中的是将中的处处代以得到的。其基本含义是：如果为真，那么对于个体域中任何指定的个体c，必有G(c)为真。它体现了人们在逻辑推理中的由一般到特殊的推导方法。
ES规则中的是个体域中的某个确定的个体常量而非变元。其基本含义是：如果为真，则至少有个体域中某个确定的个体c，有G(c)为真。
2. 引入量词的规则
UG规则（全称推广规则）：。
EG规则（存在推广规则）：。
UG规则的基本含义是：如果个体变量y在个体域内取到每一个个体时都有G(y)为真，那么必有为真。它说明，如果对于任意的个体c，都有G(c)，就可以引入全称量词。
EG规则的基本含义是：如果对于个体域中某个指定的个体c满足G(c)为真，那么必有为真。
3.4.3  谓词逻辑推理的基本方法
谓词逻辑是命题逻辑的一种自然扩展，谓词逻辑的知识体系完全涵盖了命题逻辑的知识体系，或者说命题逻辑是谓词逻辑的一种特例。因此，可以将命题推理的T规则，P规则和CP规则，以及命题推理的基本策略，如直接证明法和间接证明法等，直接应用于谓词逻辑的推理。
另外，由于谓词逻辑引进了个体域、个体词、量词，以及由此而产生的约束变量和自由变量。因此，在考虑和处理谓词推理问题时，还需要根据谓词逻辑的特点采用适当的方法。其中最为关键的是：
第一、在谓词逻辑中，一般无法在不同个体域基础上衡量两个谓词公式之间的等价关系或逻辑蕴含关系，就像两种不同类型的东西无法进行比较一样。因此，在谓词逻辑演算和推理过程中，总是假定所有的谓词公式具有相同的个体域，一般默认为全总个体域。
第二、谓词逻辑推演的基本思路，一般是首先根据US和ES规则消除谓词公式中的量词，把谓词公式的推理问题转化为命题公式的推理问题，再使用命题公式的推理策略和方法完成相关的推理，最后根据具体需要使用UG和EG规则，将基于命题公式的推理结论还原成谓词公式的推理结论。
第三、在谓词逻辑的推演过程中，可以引用命题演算中的P规则和T规则，如果结论是以蕴含形式或析取形式给出，还可使用CP规则。对含有量词的公式可以引用谓词中的基本等价公式和基本蕴涵公式，对于已经消去量词的谓词公式或谓词公式中不含量词的子公式，完全可以引用命题演算中的基本等价公式和基本蕴涵公式。
在谓词演算的推证过程中，必须注意遵守所使用各项推理规则的限制条件，正确合理地使用推理规则。当既需要消除存在量词，又需要消除全称量词的时候，一般都是先消除存在量词，后消除全称量词。被消除或新添加的量词必须位于谓词公式的最左边。当需要推证的结论为蕴含式的时候，可以考虑使用CP规则证明法。当证明给出的前提条件较少且多为蕴含式或析取式时，可以考虑使用反证法，将结论的否定作为附加前提引入，以增加可用的前提。
下面结合实例介绍谓词逻辑推证的基本方法。
例3.4.1  证明苏格拉底三段论。
所有的人都是要死的，苏格拉底是人，所以苏格拉底是要死的。
证明  设H(x)：x是人；M(x)：x是要死的；s是苏格拉底。
前提：，H(s)；
结论：M(s)。
即要证明，H(s)M(s)。具体推理过程如下：
（1）
P
（2）
US，(1)
（3）H(s)
P
（4）M(s)
T，(2)，(3)，I
例3.4.2  构造下面前提到结论的有效推理。