第5章
一阶谓词逻辑
在命题逻辑中，将简单命题作为基本研究单位，不再对它进行分解，从而无法揭示原子命题内部的特征。因此，命题逻辑的推理中存在着很大的局限性，如要表达“某两个原子公式之间有某些共同的特点”或者是要表达“两个原子公式的内部结构之间的联系”等，命题逻辑就无法将其表示出来。此外，有些简单的推理形式，如典型的逻辑三段论，用命题演算的推理理论也无法验证它。例如，苏格拉底三段论：
前提： 所有的人都是要死的；
苏格拉底是人。
结论： 所以，苏格拉底是要死的。
上述三个命题有着密切的关系，当前两个命题为真时，第三个命题必定是真。但是，在命题逻辑中，设P： 所有的人都是要死的； Q： 苏格拉底是人； R： 苏格拉底是要死的。则苏格拉底三段论符号化为
P，QR
根据逻辑蕴涵关系，命题公式表示为
P∧Q→R
应为永真公式，即在任何解释下，公式的取值应为真，但实际上并非如此。如当P取“1”，Q取“1”，R取“0”时：
P∧Q→R0
也就是说，命题公式P∧Q→R不是永真公式，即P，QR不能成立。所以用命题逻辑已无法正确地描述上述情况，这就显示了命题逻辑的局限性。
出现这类问题的主要原因是在这类推理中，各命题之间的逻辑关系不是体现在原子命题之间，而是体现在构成原子命题的内部组成成分之间，即体现在命题结构的更深层次上，而命题逻辑无法将这种内在联系反映出来，要反映这种内在联系，就必须对简单命题做进一步的分析，分析出其中的个体词、谓词和量词等，研究它们的形式结构及逻辑关系，总结出正确的推理形式和规则
。例如：
“所有人都要死的”
这句话可以分解“所有的” “人” “都要死的”三个部分，这样就有可能考虑任意一个特定的人。此时，就可以研究它们的形式结构和逻辑关系、正确的推理形式和规则，这正是一阶逻辑研究的基本内容，一阶逻辑也称谓词逻辑。
本章在命题逻辑的基础上，引入量词的概念、谓词公式及其解释，讨论在一阶谓词逻辑中谓词公式的等价与蕴涵关系及范式，并介绍相应的推理理论。
本章主要包括如下内容。
一阶逻辑的基本概念(谓词、个体、量词)。
谓词公式及其解释。
谓词公式之间的关系与范式表示。
谓词演算的推理理论。
5.1一阶谓词逻辑的基本概念
第
5
章
一阶谓词逻辑
离散数学（第3版）
在命题逻辑中，命题是能够判断真假的陈述句，从语法上分析，一个陈述句由主语和谓语两部分组成。例如句子：
“张明是上海财经大学的学生。”
可分解成两个部分： “张明”是主语，“是上海财经大学的学生”是谓语。
再例如：
“李天是大学生。”
“张明是大学生。”
此时，在命题逻辑中，若用命题P、Q分别表示上述两句话，则P、Q显然是两个毫无关系的命题，无法来显示它们之间的共同特征。但是，由这两句话可以看出这两个命题所表达的一个共同的特征：
“是大学生”
因此，若将句子分解成
“主语+谓语”
同时将相同的谓词部分抽取出来，则可表示这一类的语句。此时，若用P表示：
P： 是大学生。
P后紧跟
“某某人”
则上述两个句子可写为： P(李天)； P(张明)。
因此，为了揭示命题内部结构及其命题的内部结构的关系，就按照这两部分对命题进行分析，分解成主语和谓语。
5.1.1谓词、个体词和个体域
定义5.1个体词是指所研究对象中可以独立存在的具体的或抽象的客体。表示具体的、特指的个体词，称为个体常元，常用小写字母a，b，c，… 来表示。表示抽象的、泛指的或在一定范围内变化的个体词，称为个体变元，常用小写字母x，y，z，… 来表示。
个体变元的取值范围为个体域(或称论域)，常用符号D表示。个体域可以是有限个体的集合，如{1，2，3}，{a，b，c}，{上海财经大学全体在校学生}； 也可以是无限个体的集合，如自然数全体、整数全体。
最大的个体域是包含宇宙中全体事物的个体域，称为全总个体域。当无特殊声明时，默认个体域为全总个体域。
例5.1上海、北京、李天、张明、计算机班、定理、熊猫等都是个体常元。
例5.2(1) 上海是一座美丽的城市。
(2) 离散数学是计算机专业的基础课程。
(3) 李天是大学生。
(4) 人会学习。
其中，“上海”“离散数学”和“李天”是个体常元，“人”是个体变元。
定义5.2用来刻画一个个体的性质或多个个体之间关系的词，称为谓词。谓词中包含个体的数目称为谓词的元数。谓词常用大写字母P，Q，R，… 来表示。
如P(x)即是一个一元谓词，其中，x为个体变元； P(a，b)为二元谓词，其中，a，b为个体常元。
表示有具体确定意义的性质或关系的谓词，称为谓词常元，常用大写字母A，B，C，…表示，否则称为谓词变元，即表示抽象的和泛指的谓词。
通常情况下，一元谓词用来刻画个体的性质，而多元谓词则用来描述多个个体之间的关系。
例5.3将下列命题符号化。
(1) x是有理数。
(2) 小王与小李同岁。
(3) 上海位于南京与杭州之间。
(4) 2是偶数且是素数。
解： (1) x是个体变元，“……是有理数”是谓词，记为G，命题符号化形式为G(x)。
(2) 小王、小李都是个体常元，“…… 与…… 同岁”是谓词，记为H，命题符号化形式为H(a，b)，其中，a： 小王，b： 小李。
(3) 上海、南京与杭州是个体常元，“……位于……与……之间”是谓词，记为M，命题符号化形式为M(a，b，c)，其中，a： 上海，b： 南京，c： 杭州。
(4) 2是个体常元，“…是偶数”是谓词，记为E，“…是素数”也是谓词，记为P，命题符号化形式为E(2)∧P(2)。
定义5.3一个由n个个体和n元谓词所组成的命题可以表示为P(a1，a2，…，an)，其中，P表示n元谓词，a1，a2，…，an分别表示n个个体。a1，a2，…，an的排列次序非常重要，不能随便交换。不含个体的谓词称为零元谓词。
例5.4将下列命题符号化。
(1) 张三是李四的表哥。
(2) 李明选修了离散数学与机器学习课程。
(3) 李明是一个认真学习的学生。
解： (1) a： 张三； b： 李四； P： ……是……的表哥。因此，该命题可以符号化为： P(a，b)，为二元谓词。
(2) a： 李明； L(x)： x选修了离散数学； J(x)： x选修了机器学习。因此，该命题可以符号化为：
L(a)∧J(a)，为二元谓词。
(3) a： 李明； L(x)： x是一个认真学习的学生。因此，该命题可以符号化为：
L(a)为一元谓词。
使用谓词时要注意如下事项。
（1） n元谓词中，个体项的次序很重要，不能交换。
例5.5上海位于南京与杭州之间。
a： 上海； b： 南京； c： 杭州。
F(a，b，c)表示上海位于南京与杭州之间。其真值为1。若写成F(b，a，c)表示南京位于上海与杭州之间，则有F(b，a，c)的真值为0。
(2) 在讨论一个问题时，必须先确定好个体域D。如不做限制，均指全总个体域。
(3) 同一个n元谓词，取不同的个体，真假会不同。
例5.6A(x)： x是大学生。
若a表示小明，并且小明只有3岁，则A(a)真值为假。
若b表示小李，并且小李20岁，当小李确实是大学生时，有A(b)真值为真，否则A(b)真值为假。
(4) 对于同一谓词，个体域D不同，真值可能也不同。
例5.7对于A(x)，x是大学生。
如D={大学生全体}，A(x)是重言式。
如D={学生全体}，A(x)是仅可满足式。
如D={计算机全体}，A(x)是永假式。
定义5.4由一个谓词和若干个体变元组成的表达式称为
简单命题函数。由n元谓词和n个个体变元x1，x2，…，xn组成的命题函数，表示为P(x1，x2，…，xn)。由有限个简单命题函数以及逻辑连接词组成的命题形式称为复合命题函数。简单命题函数和复合命题函数统称为命题函数。
命题逻辑中的连接词在谓词逻辑中都可以使用。
例5.8(1) P(x，y)是一个简单命题函数。
(2) P(x，y)∧Q(x)是一个复合命题函数。
在命题逻辑中，简单命题用一个大写的符号表示，因此，命题逻辑中的简单命题可以看成是0元谓词，即作为谓词的一种特殊情况。
在谓词逻辑中，与个体有关的全体和个别的概念是用量词符号“”和“”来表达的，这就涉及量词的概念。
5.1.2量词
定义5.5称表示数量的词为量词。量词有两种，包括“全称量词”和“存在量词”。
全称量词： 表示日常语言中的“所有的”“任意的”“一切”“全部”等词，用符号“”表示。x表示个体域中的所有个体，x为全称性变元。xA(x)表示个体域中的所有个体都具有性质A。
例5.9符号化下列命题。
(1) 所有人都要呼吸。
(2) 每个学生都要参加离散数学课程的期末考试。
(3) 所有大学生都热爱祖国。
(4) 每个有理数都是实数。
解： 可以有两种表示方式。
限定个体域的方法：
(1) 个体域为人，H(x)： x要呼吸，则命题符号化为： xH(x)。
(2) 个体域为学生全体，D(x)： x参加离散数学课程期末考试，则命题符号化为： xD(x)。
(3) 个体域为大学生全体，L(x)： x热爱祖国，则命题符号化为： xL(x)。
(4) 个体域为有理数全体，R(x)： x是实数，则命题符号化为： xR(x)。
不限定个体域的方法：
(1) 设M(x)： x是人； H(x)： x要呼吸。则命题符号化为： x(M(x)→H(x))。
(2) 设M(x)： x是学生； D(x)： x参加离散数学课程期末考试。则命题符号化为： x(M(x)→D(x))。
(3) 设S(x)： x是大学生； L(x)： x热爱祖国。则命题符号化为： x(S(x)→L(x))。
(4) 设N(x)： x是有理数； R(x)： x是实数。则命题符号化为： x(N(x)→R(x))。
例5.9中的谓词M(x)、S(x)与N(x)称为特性谓词。为了讨论个体域中某部分个体的性质，就要引入刻画这部分个体性质的谓词，称为特性谓词。对全称量词后的特性谓词应作为蕴涵式的前件； 对存在量词后的特性谓词应作为合取式的一项。
存在量词： 表示日常语言中的“存在着”“有些”“至少存在一个”“有一个”等的词，用符号“”表示，x表示个体域中的个体，x为存在性变元。xA(x)表示存在着个体域中的个体具有性质A。
例5.10符号化下列命题。
(1) 有些学生要参加离散数学课程的期末考试。
(2) 有的自然数是素数。
(3) 有人早饭吃面包。
(4) 有人坐地铁上班。
解： 限定个体域的表示方法：
(1) 个体域为学生全体，Y(x)： x参加离散数学课程期末考试，则命题符号为： xY(x)。
(2) 个体域为自然数集，P(x)： x是素数，则命题符号化为： xP（x)。
(3) 个体域为人，E(x)： x早饭吃面包，则命题符号化为： xE(x)。
(4) 个体域为人，T(x)： x坐地铁上班，则命题符号化为： xT(x)。
不限定个体域的表示方法：
(1) 设Y(x)： x参加离散数学课程期末考试； R(x)： x是学生。则命题符号化为： x(R(x)∧Y(x))。
(2) 设N(x)： x是自然数； P(x)： x是素数。则命题符号化为： x(N(x)∧P(x))。
(3) 设M(x)： x是人； E(x)： x是早饭吃面包。则命题符号化为： x(M(x)∧E(x))。
(4) 设M(x)： x是人； T(x)： x坐地铁上班。则命题符号化为： x(M(x)∧T(x))。
在例5.9与例5.10中出现的逻辑表达式，也称为谓词公式，关于谓词公式的严格定义，将在5.2节中给出。
定义5.6在谓词公式中，xA(x)或
xA(x)称为x的约束部分，变元x称为指导变元，A(x)称为相应量词的辖域。而x在公式的x约束部分的任一出现都称为x的约束出现。当x不是约束出现时，称x的出现是自由出现。公式中约束出现的变元是约束变元，即与指导变元相同的变元。自由出现的变元是自由变元，即与指导变元不同的变元。
例5.11指出各公式的指导变元、辖域、约束变元和自由变元。
(1) x(P(x)→yQ(x，y))
(2) xP(x)→yQ(x，y)
解： (1) x中的x与y中的y是指导变元，P(x)与Q(x，y)中的个体变元x与y是约束变元，x的辖域是P(x)→yQ(x，y)，y的辖域是Q(x，y)。
(2) x中的x与y中的y是指导变元，xP(x)中的x是约束变元，x的辖域是P(x)； Q(x，y)中的y是约束变元，x是自由变元，y的辖域是Q(x，y)。
在例5.11的(2)中，可以看到xP(x)中的约束变元x与yQ(x，y)中的自由变元x重名了，这就使得我们在使用公式的时候，容易引起混淆。为了避免这种情况的发生，必须将其中的一个变元换名，可以运用换名规则与代入规则来替换掉公式中的重名变元。
5.1.3换名规则与代入规则
换名规则对约束变元进行换名。
量词辖域内出现的某个约束变元及其相应量词中的指导变元，可以换成别的变元，该变元不能与本辖域内的其他变元同名，最好也不要与辖域内的其他约束变元同名，公式中的其他部分不改变。
例5.12对下面的公式使用换名规则，将重名的约束变元替换掉。
(1) xF(x，y)∧xG(x，y)
(2) x(F(x，y)→P(x))∧y(Q(x，y)→R(x))
解： 使用换名规则。
(1) xF(x，y)∧zG(z，y)或zF(z，y)∧xG(x，y)
(2) u(F(u，y)→P(u))∧v(Q(x，v)→R(x))
在运用换名规则时不能改变整个公式中个体变元的属性，原公式中的约束变元在换名后依然是约束变元，自由变元换名后依然是自由变元。
代入规则对自由变元进行代入。
整个谓词公式中同一个自由变元是指同一个个体名词，因此可以用其他符号来代替，且要求整个公式中该自由变元同时用同一个符号代替，该符号不能与原公式中其余的任何变元相同。
例5.13对下面的公式使用代入规则，将重名的自由变元替换掉。
(1) xF(x，y)∧yG(u，y)
(2) x(F(x，y)→P(x))∧y(Q(x，y)→R(x))
解： 使用代入规则。
(1) xF(x，z)∧yG(u，y)
(2) x(F(x，u)→P(x))∧y(Q(v，y)→R(v))
在替换重名的约束变元或自由变元时，两种规则可以同时使用。
例5.14替换下面的公式中重名的变元。
(1) xF(x，y)∧xyG(x，y)
(2) x(F(x，y)→P(x))∧y(Q(x，y)→R(x))
解： (1) uF(u，v)∧xyG(x，y)
(2) u(F(u，v)→P(u))∧y(Q(x，y)→R(x))
自由变元换名后不能改变整个公式中的个体变元的属性，要保证原公式中自由出现的变元在使用代入规则后依然是自由变元，约束变元依然是约束变元。
说明：
(1) 不含量词的谓词公式G(x)，它不是命题，而是命题函数，其真值依赖于x从个体域中取的个体词的不同而不同。
例5.15D表示某班全体学生，G(x)表示x是男生。如果李刚是男生，王芳是女生，则G(李刚)是真，而G(王芳)是假。而xG(x)与xG(x)是命题，x仅是一个“指导变元”，xG(x)与yG(y)意义完全相同。
xG(x)： 全班每个人均是男生。
xG(x)： 班里存在一个人是男生。
即含量词的谓词公式的真值不再依赖于x的选取。
(2) 对于一个谓词，如其每个变量均在量词的管辖下，则该表达式不是命题函数，而是命题，它有确定的真值。
例5.16假设个体域D={a，b，c}，则
xG(x)G(a)∧G(b)∧G(c)与xG(x)G(a)∨G(b)∨G(c)
具有确定的真值了，变成命题，而不再是命题函数。
(3) xG(x)的真值规定如下。
① xG(x)的命题是“对任意x∈D，均有G(x)”。
② xG(x)的真值为1，当且仅当对一切x∈D，G(x)真值均为1。
③ xG(x)的真值为0，当且仅当存在x0∈D，G(x0)真值为0。
(4) xG(x)的真值规定如下。
① xG(x)的命题是“存在x0∈D，使得G(x0)成立”。
② xG(x)的真值为1，当且仅当存在x0∈D，G(x0)的真值为1。
③ xG(x)的真值为0，当且仅当对一切x∈D，G(x)的真值为0。
(5) 当多个量词连续出现，它们之间如果没有括号分隔时，约定按照从左到右的次序读出，后面的量词在前面量词的辖域之中。
例如，xy(x<y)，x，y的个体域为实数集。
则有全称量词的辖域为y(x<y)，存在量词的辖域为x<y，存在量词在全称量词的辖域内。
(6) 量词不能随便换顺序。对于和这两个量词交换位置，其意义就不同了，相应真值也可能改变。
例5.17D为实数全体； G(x，y)： x小于y。
解： xyG(x，y)表示任意一个实数x，总存在实数y，使得x小于y，该命题是真命题。
yxG(x，y)表示存在一个实数y，使得对一切实数x，有x小于y，即y是最大的实数。该命题是假命题。
例5.18将“有人在唱歌”符号化为谓词表达式。
解： 取个体域D为全总个体域，令M(x)： x是人； F(x)： x在唱歌。则“有人在唱歌”可符号化为
x(M(x)∧F(x))，M(x)即是特性谓词。
例5.19将“每个自然数都有后继数”符号化为谓词表达式。
解： 取个体域D为全总个体域，令N(x)： x是自然数； H(x，y)： y是x的后继数。则“每个自然数都有后继数”可符号化为
x(N(x)→y(N(y)∧H(x，y)))，N(x)即是特性谓词。
例5.20将“有的整数是自然数”符号化为谓词表达式。
解： 取个体域D为全总个体域，令Z(x)： x是整数； E(x)： x是自然数。则“有的整数是自然数”可符号化为
x(Z(x)∧E(x))，Z(x)即是特性谓词。
例5.21将苏格拉底三段论符号化。
解： 取个体域D为全总个体域，令A(x)： x是人； B(x)： x会死的； a： 苏格拉底。则苏格拉底三段论可符号化为：
前提： x(A(x)→B(x))∧A(a)
结论： B(a)
其中的A(x)即是特性谓词。
在一阶逻辑中，对量词的使用做如下小结。
(1) 在不同的个体域中，命题符号化的形式可能不一样。
(2) 若没有说明个体域，则应以全总个体域为个体域。
(3) 在引入特性谓词后，使用全称量词与存在量词符号化的形式是不同的。
(4) 个体域和谓词的含义确定后，n元谓词要转换为命题至少需要n个量词。
(5) 当个体域有限时，全称量词可看作合取连接词的推广。
(6) 当个体域有限时，存在量词可看作析取连接词的推广。
(7) 当个体域有限时，一个谓词公式包含多个量词，可从里到外按上述(5)与(6)的方法将量词逐个消去。
(8) 约定： 出现在量词前面的否定，不是否定该量词，而是否定被量化了的整个命题。
例5.22设个体域为{0，1}，将x(yF(x，y)∨G(x))转换成不含量词的形式。
解： x(yF(x，y)∨G(x))
x((F(x，0)∧F(x，1))∨G(x))
((F(0，0)∧F(0，1))∨G(0))∨((F(1，0)∧F(1，1))∨G(1))
在命题逻辑中可以有多种方法来判断命题公式的性质，如真值表法、等值演算法、主范式的方法等，但是在谓词逻辑中由于引入了个体变元、谓词和量词等概念，而且个体域常是无限的，使研究变得更复杂，从而难以判断谓词公式的性质。下面将讨论谓词公式的定义及其解释。
5.2谓词公式及其解释
在命题逻辑中，我们定义了命题公式，从而可以让我们进行演算和推理。与命题演算一样，在谓词逻辑中也同样包含命题变元和命题连接词，为了能够进行演绎和推理，需要对谓词逻辑中关于谓词的表达式加以形式化，这就要利用连接词、谓词与量词一起来构成符合要求的谓词公式。
在形式化中，将使用如下四种符号。
(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)可以是Dn→D的任意一个函数。
(4) 谓词符号： 用带或不带下标的大写英文字母P，Q，R，…或P1，Q1，R1，…来表示。当个体域名称集合D给出时，n元谓词符号P(x1，x2，…，xn)可以是Dn→{0，1}的任意一个谓词。
为了能够更形式化地描述谓词的构成，首先引入“项”的概念。
5.2.1谓词公式的定义
定义5.7项可以按如下方式递归定义而成：
(1) 个体变元和常元都是项。
(2) 若f是n元函数，且t1，t2，…，tn是项，则f(t1，t2，…，tn)也是项。
(3) 只有经过有限次使用(1)和(2)所得到的符号串才是项。
注： (1) 从中可以看出，项也可以出现在谓词的变量位置，相当于名词，可以做句子的主语或宾语。
(2) 函数f(t1，t2，…，tn)不是句子，仅是词，因而不是公式仅是项。项的结果仍是个体名称集中的名词，而公式的结果(真值)是成立或不成立(是1或0)。
例5.23常元符号a，π，1都是项； 变元符号x1，y2，z…都是项； 函数sin(x)是项； a+b也是项。
例5.24复合函数f(g(x)，h(a，g(x)，y))是项。
有了项的定义，函数的概念就可用来表示个体常量和个体变量了。
例5.25设： f(x，y)=2x+y-1；
N(x)： x是实数。
则f(1，2)表示个体常量“3”，而N(f(1，2))表示“3”是实数。
定义5.8若P(x1，x2，…，xn)是n元谓词，x1，x2，…，xn都是项，则称P(x1，x2，…，xn)为原子谓词公式。
在原子谓词公式概念的基础上，就可以定义谓词公式了。
定义5.9谓词公式(也称合式公式)的递归定义如下。
(1) 原子谓词公式是谓词公式。
(2) 如果A、B是谓词公式，则�瘙綈A，A∧B，A∨B，A→B，AB，AB也是谓词公式。
(3) 如果A是谓词公式，x是A中出现的任意个体变元，则xA(x)，xA(x)也是谓词公式。
(4) 只有经过有限次使用(1)(2)(3)生成的符号串才是谓词公式。
例5.26H(a，b)，C(x)∧B(x)，x(M(x)→H(x))，x(M(x)∧C(x)∧B(x))等均是谓词公式。
注： 一阶谓词逻辑的限定量词仅作用于个体变元，不允许量词作用于命题变元、谓词变元和函数变元。
有了谓词公式的定义，就可以将一些自然语言的语句用谓词公式表示出来。而且个体域设置不同，表达方式也会有所不一样。
例5.27所有的狮子都是吃肉的。
解： 设个体域为全总个体域，T(x)： x是狮子； A(x)： x是吃肉的。则原语句可符号化为
x(T(x)→A(x))
如果设个体域为狮子的集合，则原语句可符号化为xA(x)。
例5.28将命题“如果任意两个实数的乘积为0，则其中必有一个实数是0”符号化成谓词公式。
解： 设个体域为全总个体域，A(x)： x是实数； P(x，y)： x与y的乘积； E(x，y)： x=y。则命题可符号化为
xy(A(x)∧A(y)∧(E(P(x，y)，0)→(E(x，0)∨E(y，0))))
如果设个体域为实数域R，则命题符号化为
xy(E(P(x，y)，0)→(E(x，0)∨E(y，0)))
例5.29将命题“没有最大的自然数”符号化。
解： 命题中“没有最大的”是对所有自然数而言的，所以可理解为“对所有的x，如果x是自然数，则一定还有比x大的自然数”，即“对所有的x，如果x是自然数，则一定存在y，y也是自然数，并且y比x大。”
设个体域为全总个体域，令N(x)： x 是自然数； G(x，y)： x>y。则原命题可符号化为
x(N(x)→y(N(y)∧G(y，x)))
例5.30函数f(x)在点a连续的定义为： 对任意的ε>0，存在一个δ>0，使得对所有x，若|x-a|<δ，则|f(x)-f(a)|<ε，符号化此定义。
解： 设个体域为实数集，令R(x)： x是实数； G(x，y)： x大于y。则原命题可符号化为
ε((R(ε)∧G(ε，0))→
δ(R(δ)∧G(δ，0)∧x((R(x)∧G(δ，|x-a|))→G(ε，|f(x)-f(a)|))))
此命题如果将个体域设定为实数集，则可符号化为
ε(G(ε，0)→δ(G(δ，0)∧x(G(δ，|x-a|))→G(ε，|f(x)-f(a)|))))
5.2.2谓词公式的解释
若给定一个文字叙述的命题，可以将它符号化为谓词公式； 反之，若给定一个谓词公式，也可以将它用文字表示出来。但是在表示的时候涉及谓词逻辑的语义问题，它既涉及对项的解释，也涉及对谓词标识符的解释。谓词公式的解释的定义如下。
定义5.10谓词逻辑中公式G的每一个解释I由如下四部分组成。
(1) 非空的个体域为D(这也必须指定)。
(2) 个体常元用D中确定的个体代入。
(3) 对每个谓词变元，分别指定为D上一个确定的命题函数。
(4) 对每个命题函数，分别指定为D上一个确定的函数。
根据上面的定义可知，只有不包括自由变元的公式才可能求出其真值，此时的谓词公式就成为一个有确切意思的命题，而任何
包含自由变元的公式都不能求值。因此，为以后讨论的方便，对公式做如下的假定： 公式中无自由变元，或将自由变元看成是常量符号。
例5.31分别对个体域D1={3，4}，把P(x)解释为“x是质数”，a=3，讨论P(a)∧xP(x)的真值。
解： P(a)∧xP(x)
P(3)∧(P(3)∨P(4))
1∧(1∨0)
1∧1
1
例5.32已知指定一个解释I如下。
(1) 个体域为自然数集合N。
(2) 指定常项a=0。
(3) 指定谓词F(x，y)为x=y。
(4) N上的指定函数f(x，y)=x+y，g(x，y)=x×y。
在以上指定的解释I下，说明下列公式的真值。
(1) xF(g(x，a)，x)
(2) xy(F(f(x,a),y)→F(f(y,a),x))
(3) F(f(x，y)，f(y，z))
(4) F(g(x，y)，g(y，x))
解： (1) xF(g(x，a)，x)
xF(x×a=x)
x(x×0=x)为假
即xF(g(x，a)，x)为假命题。
(2) xy(F(f(x,a),y)→F(f(y,a),x))
xy(F(x+a，y)→F(y+a，x))
xy(x+a=y→y+a=x)
xy(x=y→y=x)为真
即xy(F(f(x,a),y)→F(f(y,a),x))为真命题。
(3) F(f(x，y)，f(y，z))
F(x+y，y+z)
x+y=y+z
x=z
因为x，z均为自由变元，解释不对自由变元进行指定。因此x=z的真值不确定，所以F(f(x，y)，f(y，z))是命题函数，不是命题。
(4) F(g(x，y)，g(y，x))
F(x×y，y×x)
x×y=y×x
解释I下虽然不对自由变元进行指定。但x×y=y×x的真值确定，为1，因此F(g(x，y)，g(y，x))为真命题。
例5.33设有公式： xy(P(x，y)→Q(x，y))。在如下给定的解释下，判断该公式的真值。
解： (1) 解释I为：
① 个体域为N(自然数集)。
② P(x，y)指定为“y≥x”。
③ Q(x，y)指定为“y≥0”。
则原公式的真值为“真”。因为可以找到一个x∈N，使得对任意y，都有y≥x和y≥0。
此时蕴涵公式的前件为真，后件也为真，所以整个公式为真。
(2) 解释I为：
① 个体域为N(自然数集)。
② P(x，y)指定为“x×y=0”。
③ Q(x，y)指定为“x=y”。
则原公式的真值为“假”。
因对任意的x≠0，当y=0时，有P(x，y)→Q(x，y)为“假”，即有
y(P(x，y)→Q(x，y)) 为“假”
而对x=0，当y≥1时，有P(x，y)→Q(x，y)为“假”。即有
y(P(x，y)→Q(x，y))为“假”
所以，对任意x∈N，都有
y(P(x，y)→Q(x，y))为“假”
即有
xy(P(x，y)→Q(x，y))为“假”
(3) 解释I为：
① 个体域为N。
② P(x，y)指定为“x+y=0”。
③ Q(x，y)指定为“x>y”。
则原公式的真值为“真”。
因为对任意的x≠0，任意y∈N，有“x+y=0”为“假”，所以无论后件如何，都有
P(x，y)→Q(x，y)为“真”
即有
y(P(x，y)→Q(x，y))为“真”
所以
xy(P(x，y)→Q(x，y))为“真”
5.2.3谓词公式的分类
一般地，公式的取值依赖于个体域D及所做出的解释，因此可以在这个意义上，定义谓词公式的永真式和矛盾式。
定义5.11设A为一个谓词公式，如果A在任一组解释下均为真，称A为永真式(或称重言式)； 如果A在任一组解释下均为假，称A为矛盾式(或称永假式、不可满足式)； 如果至少存在一个解释使A为真，则称A为可满足式。
说明： 对于一阶逻辑公式判断其类型至今没有一般的方法。
例5.34�瘙綈P(x)∨P(x)是永真式；
�瘙綈P(x)∧P(x)是永假式。
例5.35�瘙綈xP(x)∨xP(x)是永真式；
�瘙綈xP(x)∧xP(x)是永假式。
例5.36G(x，y)是二元谓词，如指定D为实数域，G(x，y)表示“x小于y”，则G(x，y)有了确定的含义，但还不是命题。如再指定x为4，y为5，则G(x，y)就是命题“4小于5”，其真值为1。
注： (1) 一个谓词公式如果不含自由变元，则在一个解释下，可以得到确定的真值，不同的解释下可能得到不同的真值。
(2) 公式的解释并不对自由变元进行指定，如果公式中含有自由变元，即使对公式进行了一个指派，也不一定得到确定的真值，不一定是命题。
(3) 由公式的解释定义可以看出，当D为无限集时，公式有无限多个解释，根本不可能将其全部列出，因而谓词逻辑的公式不可能列出真值表。
5.3谓词公式之间的关系与范式表示
5.3.1谓词公式之间的关系
与在命题逻辑中一样，在一阶谓词逻辑中，一个谓词公式也可以有多种不同的表现形式。并且，公式之间也有等价关系与蕴涵关系。
定义5.12设A，B是个体域D上的两个公式，若对于A和B的任意一组解释，两公式都具有相同的真值，则称公式A和B在D上等值，记作AB。
例5.37设个体域D为整数集，谓词G(x，y)表示x<y，则公式xyG(x，y)与�瘙綈xyG(y，x)等价。
定义5.13对于公式A和B，若A→B1，则称公式A蕴涵公式B，记作AB。
当个体域是有限集时，理论上可以用真值表技术来验证一个公式是否是永真式，也可以用来验证两个公式是否等值。但是当个体域中个体数目比较多时，真值表技术就比较麻烦，不大可行了，就需要寻求其他的方法，如演算法等。
在命题逻辑中成立的基本等值式和基本重言蕴涵式及其代换实例都是谓词逻辑的等值式和重言蕴涵式。如下面的例子。
例5.38xA(x)∧xA(x)xA(x)（幂等律）
x(A(x)→B)x(�瘙綈A(x)∨B)（蕴涵律）
例5.39在P∨�瘙綈P中，若用xP(x)代替P，得到永真公式
xP(x)∨�瘙綈xP(x)
同理，在P∧�瘙綈P中，若用xP(x)代替P，得到永假公式
xP(x)∧�瘙綈xP(x)
我们将在谓词逻辑中用到的等值式和蕴涵式归纳如下。
1. 量词否定等值式
(1) �瘙綈xA(x)x�瘙綈A(x)
(2) �瘙綈xA(x)x�瘙綈A(x)
例5.40在D={a，b，c}时，验证上述两个公式。
(1)式左边�瘙綈xA(x)�瘙綈(A(a)∧A(b)∧A(c))
(1)式右边x�瘙綈A(x)�瘙綈A(a)∨�瘙綈A(b)∨�瘙綈A(c)
�瘙綈(A(a)∧A(b)∧A(c))
因此(1)式成立。
(2)式左边�瘙綈xA(x)�瘙綈(A(a)∨A(b)∨A(c))
(2)式右边x�瘙綈A(x)�瘙綈A(a)∧�瘙綈A(b)∧�瘙綈A(c)
�瘙綈(A(a)∨A(b)∨A(c))
因此(2)式成立。
例5.41设P(x)： x今天上离散数学课，个体域为信息管理与工程学院2006级全体同学的集合，则
(1) xP(x)表示所有同学今天都来上离散数学课了；
�瘙綈xP(x)表示不是所有的同学今天都来上离散数学课了；
x�瘙綈P(x)表示今天有同学没来上离散数学课。
所以，�瘙綈xP(x) x�瘙綈P(x)。
(2) xP(x)表示有同学今天来上离散数学课了；
�瘙綈xP(x)表示今天没有同学来上离散数学课；
x�瘙綈P(x)表示所有同学今天都没来上离散数学课。
所以，�瘙綈xP(x)x�瘙綈P(x)。
满足德摩根律，两边等价； 对于无穷个体域，可用语义解释。
2. 量词辖域的扩张与收缩等值式
(1) x(A(x)∧B)xA(x)∧B
(2) x(A(x)∨B)xA(x)∨B
(3) x(A(x)∧B)xA(x)∧B
(4) x(A(x)∨B)xA(x)∨B
说明： ，在∧、∨连接词下，辖域可以扩充到一切不含该指导变元的任意原子公式上。
条件：
(1) B中不含指导变元x；
(2) 只能对连接词∧、∨。
若A不含个体变元，则xAA，xAA。
例5.42证明xA(x)→Bx(A(x)→B)。
证明： xA(x)→B�瘙綈xA(x)∨B
x�瘙綈A(x)∨B
x(�瘙綈A(x)∨B)
x(A(x)→B)
对于量词辖域的扩张与收缩，还有以下关系成立。
推广： (5) xA(x)∨B(y)x(A(x)∨B(y))
(6) x(A(x)→B)xA(x)→B
(7) x(B→A(x))B→xA(x)
(8) x(A(x)→B)xA(x)→B
(9) x(B→A(x))B→xA(x)
(10) x(A(x)→B(x))xA(x)→xB(x)
(11) x(A(x)→B(x))xA(x)→xB(x)
(12) x(A(x)→B(x))xA(x)→xB(x)
(13) xA(x)→xB(x)x(A(x)→B(x))
(14) x(A(x)B(x))xA(x)xB(x)
3. 量词分配等值式
(1) x(A(x)∧B(x))xA(x)∧xB(x)
(2) x(A(x)∨B(x))xA(x)∨xB(x)
注意： x不能对∨分配，x不能对∧分配，即
x(A(x)∨B(x))与xA(x)∨xB(x)不等
x(A(x)∧B(x))与xA(x)∧xB(x)不等
但是成立： xA(x)∨xB(x)x(A(x)∨B(x))
x(A(x)∧B(x))xA(x)∧xB(x)
有了这些等值式，就可以用来判断谓词公式的类别，或者是两个谓词公式之间的等值与蕴涵关系了。
例5.43证明x(A(x)→B(x))xA(x)→xB(x)。
证明： x(A(x)→B(x))
x(�瘙綈A(x)∨B(x))
x�瘙綈A(x)∨xB(x)
�瘙綈xA(x)∨xB(x)
xA(x)→xB(x)
例5.44证明xy(P(x)Q(y))xP(x)xQ(x)
证明： xy(P(x)Q(y))
xy((P(x)→Q(y))∧(Q(y)→P(x)))
xy(P(x)→Q(y))∧xy(Q(y)→P(x))
xy(�瘙綈P(x)∨Q(y))∧xy(�瘙綈Q(y)∨P(x))
(x�瘙綈P(x)∨yQ(y))∧(y�瘙綈Q(y)∨xP(x))
(x�瘙綈P(x)∨xQ(x))∧(x�瘙綈Q(x)∨xP(x))
(�瘙綈xP(x)∨xQ(x))∧(�瘙綈xQ(x)∨xP(x))
(xP(x)→xQ(x))∧(xQ(x)→xP(x))
x(P(x)→Q(x))∧x(Q(x)→P(x))
x((P(x)→Q(x))∧(Q(x)→P(x)))
x(P(x)Q(x))
xP(x)xQ(x)
所以xy(P(x)Q(y))xP(x)xQ(x)。
例5.45证明xy(A(x)→B(y))xA(x)→yB(y)
证明： xy(A(x)→B(y))
x(A(x)→yB(y))
xA(x)→yB(y)
注： 在谓词公式中，如果有多个量词，相同量词间的次序可以任意互换，不同量词的次序不能随便交换。
例5.46设个体域D={a，b}，验证下面两个公式。
(1) xyA(x，y)yxA(x，y)
(2) xyA(x，y)yxA(x，y)
解： (1) xyA(x，y)yA(a，y)∧yA(b，y)
(A(a，a)∧A(a，b))∧(A(b，a)∧A(b，b))
A(a，a)∧A(a，b)∧A(b，a)∧A(b，b)
yxA(x，y)xA(x，a)∧xA(x，b)
(A(a，a)∧A(b，a))∧(A(a，b)∧A(b，b))
A(a，a)∧A(a，b)∧A(b，a)∧A(b，b)
所以xyA(x，y)yxA(x，y)。
(2) xyA(x，y)yA(a，y)∨yA(b，y)
A(a，a)∨A(a，b)∨A(b，a)∨A(b，b)
yxA(x，y)xA(x，a)∨xA(x，b)
A(a，a)∨A(a，b)∨A(b，a)∨A(b，b)
所以xyA(x，y)yxA(x，y)。
例5.47验证： (1) xyA(x，y)yxA(x，y)成立。
(2) xyA(x，y)xyA(x，y)不成立。
解： 令D={1，2}，A(1，1)=1，A(1，2)=1，A(2，1)=0，A(2，2)=0
xyA(x，y)(A(1，1)∧A(1，2))∨(A(2，1)∧A(2，2))
(1∧1)∨(0∧0)
1∨0
1
yxA(x，y)(A(1，1)∨A(2，1))∧(A(1，2)∨A(2，2))
(1∨0)∧(1∨0)
1∧1
1
xyA(x，y)(A(1，1)∨A(1，2))∧(A(2，1)∨A(2，2))
(1∨1)∧(0∨0)
1∧0
0
所以(1)成立，但(2)不成立。
例5.48设个体域为鞋子集合，A(x，y)表示“x与y成双”。
我们有：
yxA(x，y)： 存在一只鞋子，它与每只鞋都成双，这是一个假命题。
xyA(x，y)： 对于任意一只鞋子，存在一只鞋子与它成双，这是一个真命题。
由此可见，不同的量词不能随便交换次序。
5.3.2范式
范式是一种统一的表达形式，在命题逻辑里，每一公式都有与之等值的范式，当研究一个公式的特点(如永真、永假)时，范式起着重要作用。对一阶谓词逻辑的公式来说，也有相应的范式，但是在一阶谓词逻辑中，因为命题连接词与量词的出现，
就使得公式有可能是很复杂的，因此一阶谓词逻辑中的范式与命题逻辑中的范式有所区别，这里主要介绍前束范式和斯柯林范式两种，重点研究前束范式。其中，前束范式是与原公式是等值的，而斯柯林范式与原公式只有较弱的关系。
定义5.14一个谓词公式，如果它的所有量词均以肯定形式出现在公式的最前面，且它们的辖域一直延伸到公式的末尾，则称这种形式的公式为前束范式。记作下述形式：
Q1x1Q2x2…QkxkB(k≥0)
其中，每个Qi(1≤i≤k)为量词或，也称为前束公式的首标； B为不含量词的谓词公式，也称为公式的尾部。特别地，若A中无量词，则A也看作前束范式。
例5.49xy(P(x，y)∧Q(x，y))与R(x，y)均是前束范式。xyP(x，y)∧Q(x，y)就不是前束范式，因为量词的辖域没有作用到公式的末尾。
例5.50判断下列各式是否是前束范式。
(1) xyz(P(x，y，z)→Q(x，y))
(2) xyzP(x，y，z)→Q(x，y)
(3) xyzP(x，y，z)→xyQ(x，y)
(4) xy(P(x，y，z)→Q(x，y))
解： (1)和(4)是前束范式，(2)与(3)不是前束范式。
定理5.1任何一个公式都可以转换为与它等值的前束范式。
证明： 该定理的证明过程也就是任意给定一个谓词公式如何求出它的前束范式的过程，这种证明方法，
也称为构造法。具体步骤如下。
第一步： 消去连接词→，。
第二步： 将连接词�瘙綈向内深入，使之只作用于原子公式。
第三步： 利用换名规则或代入规则使所有约束变元的符号均不同，并且自由变元与约束变元的符号也不同。
第四步： 利用量词辖域的扩张和收缩等值式，将所有量词以在公式中出现的顺序移到公式最前面，扩大量词的辖域至整个公式。
例5.51将下列公式化为前束范式。
(1) (xP(x)∨yQ(y))→xR(x)
(2) (xP(x，y)→yQ(y))→xR(x，y)
解： (1) (xP(x)∨yQ(y))→xR(x)
�瘙綈(xP(x)∨yQ(y))∨xR(x)消去连接词→
(�瘙綈xP(x)∧�瘙綈yQ(y))∨xR(x)德摩根律
(x�瘙綈P(x)∧y�瘙綈Q(y))∨zR(z)换名，量词转换
xyz((�瘙綈P(x)∧�瘙綈Q(y))∨R(z))量词辖域扩张
(2) (xP(x，y)→yQ(y))→xR(x，y)
(xP(x，t)→yQ(y))→xR(x，t)代入规则
(xP(x，t)→yQ(y))→zR(z，t)换名规则
�瘙綈(�瘙綈xP(x，t)∨yQ(y))∨zR(z，t)消去连接词→
(xP(x，t)∧�瘙綈yQ(y))∨zR(z，t) �瘙綈向内深入
(xP(x，t)∧y�瘙綈Q(y))∨zR(z，t)量词转换
xy(P(x，t)∧�瘙綈Q(y))∨zR(z，t)量词辖域扩张
xyz((P(x，t)∧�瘙綈Q(y))∨R(z，t))量词辖域扩张
由于量词前移的顺序不同，可得到不同的并且都是等价的前束范式，因此，前束范式一般不是唯一的。
例5.52将公式xP(x)→x(zQ(x，z)∨zR(x，y，z))化为前束范式。
解： xP(x)→x(zQ(x，z)∨zR(x，y，z))
�瘙綈xP(x)∨x(zQ(x，z)∨zR(x，y，z))
x�瘙綈P(x)∨x(zQ(x，z)∨uR(x，y，u))
v�瘙綈P(v)∨x(zQ(x，z)∨uR(x，y，u))
vxzu(�瘙綈P(v)∨(Q(x，z)∨R(x，y，u)))
vxzu(�瘙綈P(v)∨Q(x，z)∨R(x，y，u))
定义5.15在前束范式Q1x1Q2x2…QkxkB中，如果B是合取范式(析取范式)，则称这个前束范式为前束合取(析取)范式。
由定义可知，要求一个谓词公式的前束合取范式或前束析取范式，只需先求出前束范式，然后按照要求将前束范式转换为合取或析取范式即可。这在命题逻辑中已经介绍过。
例5.53将公式x(P(x)Q(x，y))→(�瘙綈xR(x)∧zS(z))化为前束合取范式和前束析取范式。
解： x(P(x)Q(x，y))→(�瘙綈xR(x)∧zS(z))
x((P(x)→Q(x，y))∧(Q(x，y)→P(x)))→(�瘙綈xR(x)∧zS(z))
�瘙綈x((�瘙綈P(x)∨Q(x，y))∧(�瘙綈Q(x，y)∨P(x)))∨(�瘙綈xR(x)∧zS(z))
(消去连接词→，)
x(�瘙綈(�瘙綈P(x)∨Q(x，y))∨�瘙綈(�瘙綈Q(x，y)∨P(x)))∨(x�瘙綈R(x)∧zS(z))
x((P(x)∧�瘙綈Q(x，y))∨(Q(x，y)∧�瘙綈P(x)))∨(x�瘙綈R(x)∧zS(z))
(将连接词�瘙綈深入至原子谓词公式)
x((P(x)∧�瘙綈Q(x，y))∨(Q(x，y)∧�瘙綈P(x)))∨(t�瘙綈R(t)∧zS(z))(换名)
x((P(x)∧�瘙綈Q(x，y))∨(Q(x，y)∧�瘙綈P(x)))∨tz(�瘙綈R(t)∧S(z))
xtz((P(x)∧�瘙綈Q(x，y))∨(Q(x，y)∧�瘙綈P(x))∨(�瘙綈R(t)∧S(z)))
(将量词提到公式前，得前束析取范式)
xtz(((P(x)∨Q(x，y))∧(�瘙綈Q(x，y)∨�瘙綈P(x)))∨(�瘙綈R(t)∧S(z)))
xtz((P(x)∨Q(x，y)∨�瘙綈R(t))∧(P(x)∨Q(x，y)∨S(z))∧
(�瘙綈Q(x，y)∨�瘙綈P(x)∨�瘙綈R(t))∧(�瘙綈Q(x，y)∨�瘙綈P(x)∨S(z)))
(得前束合取范式)
例5.54将公式xy(P(x)→zQ(y，z))→�瘙綈yR(y，a)转换为前束合取范式与前束析取范式。
解： xy(P(x)→zQ(y，z))→�瘙綈yR(y，a)
xy(P(x)→zQ(y，z))→�瘙綈uR(u，a)(换名)
�瘙綈xy(�瘙綈P(x)∨zQ(y，z))∨�瘙綈uR(u，a)
xy(P(x)∧�瘙綈zQ(y，z))∨u�瘙綈R(u，a)
xy(P(x)∧z�瘙綈Q(y，z))∨u�瘙綈R(u，a)
xyzu((P(x)∧�瘙綈Q(y，z))∨�瘙綈R(u，a))(前束析取范式)
xyzu((P(x)∨�瘙綈R(u，a))∧(�瘙綈Q(y，z)∨�瘙綈R(u，a)))(前束合取范式)
5.3.3斯柯林范式
定义5.16设公式G是一个前束范式，如消去G中所有的存在量词，只剩全称量词，所得到的公式称为斯柯林(Skolem)范式。
由于任一公式都有前束范式，因此要得到没有存在量词的范式，只需考虑如何消去前束范式中的存在量词即可，
有如下定理。
定理5.2任意一个公式A都有相应的斯柯林范式存在，但此斯柯林范式不一定与原公式等值。
证明： 由定理5.1知任一谓词公式A均可以变换为与它等值的前束范式，因此可假定公式A已是前束范式： AQ1x1Q2x2…QnxnG(x1，x2，…，xn)，其中，首标Qixi为xi或xi(1≤i≤n)，公式G中不含量词。现可进行如下的斯柯林变换消去首标中的存在量词。
(1) 若xi(1≤i≤n)左边没有全称量词，则取不在G中出现过的个体常元c替换G中所有的xi，并删除首标中的xi。
(2) 若xi(1≤i≤n)左边有全称量词
xs1，xs2，…，xsk(1≤k，1≤s1<s2<…<sk<i)
则取不在G中出现过的k元函数fk(xs1，xs2，…，xsk)，替换G中所有的xi，并删除首标中的xi。
反复使用上述(1)~(2)，可消去前束范式中的所有存在量词，此时得到的公式为该公式的斯柯林范式，而且该标准形
式显然不一定与原公式等值。
例5.55求公式x((�瘙綈P(x)∨yQ(y，z))→�瘙綈zR(y，z))的斯柯林范式。
解： 原式x(�瘙綈(�瘙綈P(x)∨yQ(y，z))∨�瘙綈zR(y，z))
x((P(x)∧�瘙綈yQ(y，z))∨�瘙綈zR(y，z))
x((P(x)∧y�瘙綈Q(y，z))∨z�瘙綈R(y，z))
x((P(x)∧u�瘙綈Q(u，z))∨v�瘙綈R(y，v))（换名）
xuv((P(x)∧�瘙綈Q(u，z))∨�瘙綈R(y，v))(量词前移，得前束范式)
x((P(x)∧�瘙綈Q(a，z))∨�瘙綈R(y，b))
(用常元a替换变元u，常元b替换变元v得斯柯林范式)
斯柯林范式是一种重要的范式形式，机器定理证明和逻辑程序设计都是以这种范式为基础的，下面的定理说明了斯柯林范式的重要性。
定理5.3设公式G是谓词公式A的斯柯林范式，则公式A是永假式当且仅当公式G是永假式。
证明：
设AQ1x1Q2x2…QnxnG，且Qr是从左往右的第一个存在量词，使用函数f(x1，x2，…，xr-1)代替存在变元xr，得到公式
A1x1x2…xr-1Qr+1xr+1…QnxnG(x1，x2，…，xr-1，f(x1，x2，…，xr-1)，xr+1，…，xn)
要证明A为永假式当且仅当A1为永假式：
(1) 首先假设A为永假式。如果A1不是永假式，必然存在个体域D上的解释I使得A1取值为1，即对于所有的D中的个体x1，x2，…，xr-1，至少存在D中的元素f(x1，x2，…，xr-1)，使得
Qr+1xr+1…QnxnG(x1，x2，…，xr-1，f(x1，x2，…，xr-1)，xr+1，…，xn)
取值为1，于是这个解释也使得A取值为1，与假设矛盾。
(2) 其次假设A1是永假式。如果A1不是永假式，则存在个体域D上的解释I使得A取值为1，即对于所有的个体域中的x1，x2，…，xr-1，存在D中的个体xr使得
Qr+1xr+1…QnxnG(x1，x2，…，xr-1，f(x1，x2，…，xr-1)，xr+1，…，xn)
取值为1。我们将解释I扩充为新的解释J，使在I的基础上增加一个函数f，对任意一组D中的个体x1，x2，…，xr-1都有xr=f(x1，x2，…，xr-1)，且xr也是D中的个体，于是，在解释J下A1也取值1，与假设矛盾。
因此A是永假式当且仅当A1是永假式。
如果A的前束范式中有m个存在量词，令A0=A，并且Ak+1是把Ak中从左往右出现的第一个存在量词用斯柯林函数取代后得到的新公式，其中，k=1，2，…，m，于是Am是A的斯柯林范式，即GAm。
由以上的证明，有： 对所有的k=1，2，…，m，Ak-1是永假式当且仅当Ak是永假式，即A是永假式当且仅当G是永假式。
一般来说，如果公式A不是永假式，则A与它的斯柯林范式G不等值。
例5.56设谓词公式A为x(P(x)∨Q(x))，设其斯柯林范式G为P(k)∨Q(k)，给定A和G的指派E如下：
(1) 个体域D={a，b}。
(2) D中特定元素k=a。
(3) 谓词P(x)为P(a)=0，P(b)=1； Q(a)=0，Q(b)=1。
则Ax(P(x)∨Q(x))
(P(a)∨Q(a))∨(P(b)∨Q(b))
(0∨0)∨(1∨1)
0∨1
1
GP(k)∨Q(k)
P(a)∨Q(a)
0∨0
0
于是，A在E下为真，而G在E下为假。所以A与G不等价，即斯柯林范式不一定与原公式等价。
5.4谓词演算的推理理论
与在命题逻辑中一样，在一阶逻辑中也可以用推理的方法来证明一个公式是否是永真式。由于命题逻辑是一阶谓词逻辑的特殊情形，因此命题逻辑中的推理规则都可以用于谓词逻辑的推理，但是因为谓词逻辑中有了量词，所以还要增加一些与量词有关的推理规则。下面列出在谓词逻辑中要用到的推理规则。
5.4.1推理规则
1. US规则——全称量词消去规则
xA(x)A(y)或xA(x)A(c)
US规则成立的条件：
(1) y是A(y)中自由出现的个体变元。
(2) 当A(x)中可出现量词和变项时，y是任意不在A(x)中受约束出现的个体变元。
(3) c是个体域中的任意一个个体常元。
US规则的意思是指如果个体域中的所有个体x都具有性质A，则个体域中任意一个给定的个体y也必具有性质A，即“每一个均成立，其中任一个也必成立。”
在使用US规则的时候，要注意使用条件，如果使用不当，就会得出错误的结论。
例5.57公式x(yP(x，y)→Q(x))中A(x)yP(x，y)→Q(x)，其中的y不是自由变元，故不能用US规则，否则将得到yP(y，y)→Q(y)，使原来不是约束变元的x现在变成了约束变元y，改变了约束关系，这是不正确的。然而，对A(x)中约束变元y换名z，得到zP(x，z)→Q(x)，它对y是自由的，这时就可以使用US规则，得到如下结果。
x(yP(x，y)→Q(x))
x(zP(x，z)→Q(x))
zP(y，z)→Q(y))
例5.58设个体域D为实数集，考虑二元谓词L(x，y)： x>y，则xyL(x，y)： 对任意的实数x，都存在实数y，使x>y，这是真命题。
由于y在yL(x，y)中是约束出现，而不能xyL(x，y)yL(y，y)，使得y>y，得出错误的结论。
由此可见，在使用US规则时，若要去掉公式中的全称量词，则最好选用公式中未出现的符号，这样可以避免得出错误结论。
例5.59证明“凡人要死，苏格拉底是人，所以苏格拉底要死。”
证明： 符号化： M(x)： x是人； N(x)： x要死； a： 苏格拉底。
前提： x(M(x)→N(x))，M(a)结论： N(a)。
(1) x(M(x)→N(x))规则P
(2) M(a)→N(a)规则US
(3) M(a)规则P
(4) N(a)规则T
2. UG规则——全称量词一般化规则
A(y)xA(x)
UG规则成立的条件：
(1) y在A(y)中是自由出现的，并且y取任意y∈D时，A(y)均为真。
(2) 取代y的x不能在A(y)中约束出现，否则会产生错误。
即： 对每个y，A(y)均成立，所以“xA(x)”成立。
注意： US规则不是UG规则的逆命题。
例5.60请看下述推导：
(1) yG(z，y)P
(2) yyG(z，y)UG，(1)
上述推导是错误的。因为在(1)中，y已经是约束变元，不能再对此加量词。
正确的量词加入为：
(1) yG(z，y)P
(2) zyG(z，y)UG，(1)
也就是说，加量词时最好用公式中未出现的变元。
例5.61设个体域D为实数集，仍取L(x，y)： x>y，则对任意给定的y，A(y)xL(x，y)是真命题。A(y)满足条件(1)，若用UG规则，用x代替y，得xA(x)xxL(x，x)，即使得x>x，这是假命题，出错的原因是违背了条件(2)，正确的加法应该是yA(y)yxL(x，y)。
例5.62设前提为： x(P(x)→R(x))，x(Q(x)→R(x))，x(S(x)→�瘙綈R(x))；
结论： x(S(x)→�瘙綈P(x)∧�瘙綈Q(x))。
证明： (1) x(P(x)→R(x))P
(2) P(u)→R(u)(1)，US
(3) x(Q(x)→R(x))P
(4) Q(u)→R(u)(3)，US
(5) x(S(x)→�瘙綈R(x))P
(6) S(u)→�瘙綈R(u)(5)，US
(7) R(u)→�瘙綈S(u)(6)，E
(8) P(u)→�瘙綈S(u)(2)，(7)，I
(9) Q(u)→�瘙綈S(u)(4)，(6)，I
(10) S(u)→�瘙綈P(u)(8)，E
(11) S(u)→�瘙綈Q(u)(9)，E
(12) S(u)→(�瘙綈P(u)∧�瘙綈Q(u))(10)，(11)，I
(13) x(S(x)→�瘙綈P(x)∧�瘙綈Q(x))(12)，UG
证毕。
3. ES规则——存在量词消去规则
xA(x)A(c)
ES规则的成立条件是：
(1) c是使A为真的特定的个体常项。
(2) c没有在A(x)中出现过。
(3) A(x)中除x外，还有其他自由变项时，不可以用此规则。
注意： 尤其第一条，c不是任取一个，而是某些特定的个体。
例5.63在自然数集合中，设F(x)： x是奇数，G(x)： x是偶数，xF(x)∧xG(x)是真命题，但F(c)∧G(c)是假命题，其中，c为自然数变元，可以代表某自然数。看下面的错误推导。
(1) xF(x)P
(2) F(c)(2)，ES
(3) xG(x)P
(4) G(c)(3)，ES
(5) F(c)∧G(c)(2)，(4)
所得结果表明，在自然数集合中，存在既是奇数又是偶数的自然数，显然，这是错误的。出错的主要原因是违背了ES规则成立条件中的(1)，即在(4)步中用了在前面第(2)步中出现的自由变元c，作为本步应用ES规则引入的个体变元，从而得到了错误的结论。此题可以进行如下推导。
(1) xF(x)P
(2) F(c)(2)，ES
(3) xG(x)P
(4) G(d)(3)，ES
(5) F(c)∧G(d)(2)，(4)
其中的个体c是代表奇数的个体，d是代表偶数的个体。
例5.64设个体域D为实数集，仍取L(x，y)： x>y，如果xy(x>y)，则x(x>c)，这是假命题。
(1) xy(x>y)P
(2) y(u>y)(1)，US
(3) u>c(2)，ES
(4) x(x>c)(3)，UG
结论(4)是错误的，出错原因是违背了条件（3），对(2)使用ES规则时，u为自由出现的个体变元。
4. EG规则——存在量词一般化规则
A(c)yA(y)或A(x)yA(y)
此规则成立的条件是：
(1) c是某个个体变项。
(2) 取代c的y没有在A(c)中出现过。
(3) A(x)对y是自由的。
(4) 若A(x)是推导过程中的公式，且x是由于使用ES引入的，那么不能用A(x)中除x外的个体变元作约束变元，或者说，y不可以成为A(x)中的个体变元。
例5.65设个体域D为实数集，仍取L(x，y)： x>y，并取A(1)=xL(x，1)，则A(1)是真命题。
由于x已在A(1)中出现，因此若用x替换(1)得到xL(x，x)是假命题，使得x>x，出错的原因是违背了条件（2）。
例5.66设前提为： x(N(x)→Q(x))，x(R(x)∧N(x))；
结论： x(R(x)∧Q(x))。
证明： (1) x(R(x)∧N(x))P
(2) R(a)∧N(a)(1)，ES
(3) R(a)(2)，I
(4) N(a)(2)，I
(5) x(N(x)→Q(x))P
(6) N(a)→Q(a)(5)，US
(7) Q(a)(6)，I
(8) R(a)∧Q(a)(3)，(7)，I
(9) x(R(x)∧Q(x))(8)，EG
证毕。
在一阶逻辑中，推理过程通常是先用ES或US规则将公式转换为没有量词的公式，然后使用类似命题逻辑的方法进行推理，最后用EG或UG规则引入量词最终推理出所要的结论。但是在使用上面所介绍的四个推理规则时，一定要注意它们的限制条件，总的来说，可以归纳如下。
(1) 在推导的过程中，可以引用命题演算中的P规则、T规则、E规则和I规则。
(2) 如果结论是以条件的形式(或析取形式)给出，还可以使用CP规则。
(3) 为了在推导过程中消去量词，可以引用US规则和ES规则来消去量词。
(4) 当所要求的结论可能被定量时，此时可引用UG规则和EG规则将其量词加入。
(5) 证明时可采用如命题演算中的直接证明方法和间接证明方法。
(6) 在推导过程中，对消去量词的公式或公式中不含量词的子公式，完全可以引用命题演算中的基本等价公式和基本蕴涵公式。
(7) 在推导过程中，对含有量词的公式可以引用谓词中的基本等价公式和基本蕴涵公式。
(8) 在推导过程中，如既要使用US规则又要使用ES规则消去公式中的量词，而且选用的个体是同一个符号，则必须先使用ES规则，再使用US规则。然后再使用命题演算中的推理规则，最后使用UG规则或EG规则引入量词，得到所要的结论。
(9) 如一个变量是用ES规则消去量词，对该变量在添加量词时，则只能使用EG规则，而不能使用UG规则； 如使用US规则消去量词，对该变量在添加量词时，则可使用EG规则和UG规则。
(10) 如有两个含有存在量词的公式，当用ES规则消去量词时，不能选用同样的一个常量符号来取代两个公式中的变元，而应用不同的常量符号来取代它们。
(11) 在用US规则和ES规则消去量词时，此量词必须位于整个公式的最前端，并且其辖域延伸到公式的末端。
(12) 在添加的量词x、x时，所选用的x不能在公式G(c)或G(y)中以任何约束出现。
5.4.2推理规则实例
例5.67证明xA(x)→xB(x)x(A(x)→B(x))。
证明：
前提： xA(x)→xB(x)；
结论： x(A(x)→B(x))。
用反证法：
(1) �瘙綈x(A(x)→B(x))CP
(2) x�瘙綈(A(x)→B(x))(1)，E
(3) �瘙綈(A(a)→B(a))(2)，ES
(4) A(a)∧�瘙綈B(a)(3)，I
(5) A(a)(4)，I
(6) �瘙綈B(a)(4)，I
(7) xA(x)(5)，EG
(8) xA(x)→xB(x)P
(9) xB(x)(7)，(8)，I
(10) B(a)(9)，US
(11) B(a)∧�瘙綈B(a)(5)(10)矛盾
因此假设错误，原结论成立。
例5.68证明x(C(x)→W(x)∧R(x))∧x(C(x)∧Q(x))x(Q(x)∧R(x))。
证明：
前提： x(C(x)→W(x)∧R(x))，x(C(x)∧Q(x))；
结论： x(Q(x)∧R(x))。
证明过程如下。
(1) x(C(x)∧Q(x))P
(2) C(a)∧Q(a)(1)，ES
(3) x(C(x)→W(x)∧R(x))P
(4) C(a)→W(a)∧R(a)(3)，US
(5) C(a)(2)，I
(6) W(a)∧R(a)(4)，(5)，I
(7) R(a)(6)，I
(8) Q(a)(2)，I
(9) Q(a)∧R(a)(5)，(7)，I
(10) x(Q(x)∧R(x))(9)，EG
例5.69证明推理：
每个大学生不是文科生就是理工科学生； 有的大学生不是三好学生； 小明不是理工科学生，但他是三好学生。如果小明是大学生，则他是文科生。
证明：
令G(x)： x是大学生； W(x)： x是文科生； L(x)： x是理工科学生； S(x)： x是三好生； 个体常元a： 小明。则上述推理符号化为：
前提： x(G(x)→W(x)L(x))，x(�瘙綈S(x))，�瘙綈L(a)∧S(a)；
结论： G(a)→W(a)。
运用推理理论，证明过程如下。
(1) G(a)CP
(2) �瘙綈L(a)∧S(a)P
(3) �瘙綈L(a)(2)，I
(4) S(a)(2)，I
(5) x(G(x)→W(x)L(x))P
(6) G(a)→W(a)L(a)(5)，US
(7) W(a)L(a)(1)，(6)，I
(8) W(a)(3)，(7)，I
(9) G(a)→W(a)(1)，(8)，CP
例5.70证明推理：
所有的哺乳动物都是脊椎动物； 并非所有的哺乳动物都是胎生动物。故有些脊椎动物不是胎生的。
证明： 令P(x)： x是哺乳动物； Q(x)： x 是脊椎动物； R(x)： x 是胎生动物。
则上述推理符号化为：
前提： x(P(x)→Q(x))，�瘙綈x(P(x)→R(x))；
结论： x(Q(x)∧�瘙綈R(x))。
运用推理理论，证明过程如下。
(1) �瘙綈x(P(x)→R(x))P
(2) x�瘙綈(�瘙綈P(x)∨R(x))(1)，E
(3) �瘙綈(�瘙綈P(c)∨R(c))(2)，ES
(4) P(c)∧�瘙綈R(c)(3)，E
(5) P(c)(4)，I
(6) �瘙綈R(c)(4)，I
(7) x(P(x)→Q(x))P
(8) P(c)→Q(c)(7)，US
(9) Q(c)(5)，(8)，I
(10) Q(c)∧�瘙綈R(c)(6)，(9)，I
(11) x(Q(x)∧�瘙綈R(x))(10)，EG
例5.71证明推理：
有些病人相信所有医生； 病人均不相信江湖骗子； 则医生不是骗子。
证明： 令R(x)： x是病人； D(x)： x是医生； S(x)： x是江湖骗子； L(x，y)： x相信y。则上述推理符号化为：
前提： x(R(x)∧y(D(y)→L(x，y)))，x(R(x)→y(S(y)→�瘙綈L(x，y)))；
结论： x(D(x)→�瘙綈S(x))。
运用推理理论，证明过程如下。
(1) x(R(x)∧y(D(y)→L(x，y)))P
(2) R(a)∧y(D(y)→L(a，y))(1)，ES
(3) y(D(y)→L(a，y))(2)，I
(4) D(t)→L(a，t)(3)，US
(5) x(R(x)→y(S(y)→�瘙綈L(x，y)))P
(6) R(a)→y(S(y)→�瘙綈L(a，y))(5)，US
(7) R(a)(2)，I
(8) y(S(y)→�瘙綈L(a，y))(6)(7)，I
(9) S(t)→�瘙綈L(a，t)(8)，US
(10) L(a，t)→�瘙綈S(t)(9)，E
(11) D(t)→�瘙綈S(t)(4)，(10)，I
(12) x(D(x)→�瘙綈S(x))(11)，UG
例5.72证明推理：
如果一个人害怕困难，那么他就不会获得成功。每个人或者获得成功或者失败过。有些人未曾失败过，所以有些人不怕困难。
证明： 令M(x)： x是人； D(x)： x害怕困难； S(x)： x获得成功； F(x)： x失败。
故上述推理符号化为：
前提： x(M(x)∧D(x)→�瘙綈S(x))，x(M(x)→(S(x)∨F(x)))；
结论： x(M(x)∧�瘙綈F(x))→x(M(x)∧�瘙綈D(x))。
运用推理理论，证明过程如下。
(1) x(M(x)∧�瘙綈F(x))CP
(2) M(a)∧�瘙綈F(a)ES，(1)
(3) M(a)(2)，I
(4) �瘙綈F(a)(2)，I
(5) x(M(x)→(S(x)∨F(x)))P
(6) M(a)→(S(a)∨F(a))(3)，US
(7) S(a)∨F(a)(3)，(6)，I
(8) S(a)(4)，(7)，I
(9) x(M(x)∧D(x)→�瘙綈S(x))P
(10) M(a)∧D(a)→�瘙綈S(a)(9)，US
(11) S(a)→�瘙綈(M(a)∧D(a))(9)，E
(12) �瘙綈(M(a)∧D(a))(8)，(11)，I
(13) �瘙綈M(a)∨�瘙綈D(a)(12)，E
(14) �瘙綈D(a)(3)，(13)，I
(15) M(a)∧�瘙綈D(a)(3)，(14)，I
(16) x(M(x)∧�瘙綈D(x))(15)，ES
(17) x(M(x)∧�瘙綈F(x))→x(M(x)∧�瘙綈D(x))(1)，(16)，CP
习题
1. 将下列命题符号化。
(1) 不存在最大的自然数。
(2) 有的人喜欢看科幻片。
(3) 并非每个人都喜欢吃甜食。
(4) 有的人对某些药品过敏。
(5) 并不是每个人都会来参加这次会议。
(6) 每个大学生都热爱祖国。
2. 用谓词S(x，y，z)表示x+y=z，G(x，y)表示x=y，L(x，y)表示x<y，其中，个体域为自然数集，用以上符号表示下列命题。
(1) 没有x<0，且若x>0当且仅当有这样的y，使得x≥y。
(2) 并非对一切x，都存在y，使得x≤y。
(3) 对任意的x，若x+y=x，当且仅当y=0。
3. 指出下列谓词公式的约束变元与自由变元，并指出相应的辖域。
(1) x(P(x)→yQ(y))∧xR(x，y)
(2) xP(x)→Q(x)
(3) xy((P(x)→Q(x))∧�瘙綈R(x，y))
(4) xy(P(x)→Q(x，y))∨x(P(x)→R(x，y))
4. 对下列谓词公式中的约束变元进行换名。
(1) xP(x)→xQ(x)
(2) x(P(x)→Q(x))∧R(x，y)
(3) xP(x)∨xy(Q(x)→�瘙綈R(x，y))
5. 对下列谓词公式中的自由变元进行代入。
(1) xP(x)→Q(x)
(2) xP(x，y)→y(Q(y)∧R(x，y))
(3) xP(x，y)∨(zQ(x，z)→yR(x，y))
6. 设个体域是{1，2}，消去下列谓词公式中的量词。
(1) x(P(x)∧Q(x))
(2) xP(x)→xQ(x)
(3) x(P(x)→yQ(y))
7. 设个体域是{1，2，3，4，5}，令P(x)： x≥2，Q(x)： x<5，
R（x,y）： x<y，求下列谓词公式的真值。
(1) x(P(x)→y(Q(y)∧�瘙綈R(x，y)))
(2) x(P(x)∧y(Q(y)∨�瘙綈R(x，y)))
8. 求下列谓词公式的前束范式。
(1) x(P(x)→yQ(x，y))
(2) x(y(P(x，y)→Q(y))∧zR(x，y，z))
(3) xyP(x，y)∨(xzQ(x，z)→yR(y))
(4) �瘙綈(xP(x，y)→yG(x，y))∨xH(x)
9. 求下列谓词公式的前束合取与前束析取范式。
(1) x(P(x)yQ(x，y))
(2) x(y(P(x，y)→Q(y))→zR(x，y，z))
(3) xyP(x，y)→(xzQ(x，z)∧yR(y))
10. 利用推理规则证明以下各式。
(1) x(G(x)∨Q(x))，�瘙綈xG(x)xQ(x)
(2) x(P(x)→(Q(y)∧R(x)))，xP(x)Q(y)∧x(P(x)∧R(x))
11. 证明如下推理。
前提： xF(x)，x(R(x)∧�瘙綈T(x))，
z((F(z)∧xyQ(x，y))→y(R(x)→T(y)))
结论： yx�瘙綈Q(x，y)
12. 设F(x)： x喜欢绘画； G(x)： x富有想象力； H(x)： x是人。在一阶谓词逻辑中，构造推理证明： “所有喜欢绘画的人都很富有想象力，有的人喜欢绘画，因此，有的人很富有想象力”。
13. 构造下面的推理证明。
(1) 任何人如果喜欢打游戏，那他就不喜欢看电影； 每一个人或者喜欢看电影或者喜欢逛街； 有的人不喜欢逛街，因此有的人不喜欢打游戏。
(2) 学术委员会成员都是教授，并且是博士生导师，有些成员是院士，所以有的成员是博士生导师且是院士。