第二章 谓词逻辑在 Ls中,把命题分解到原子命题为止,认为原子命题是不能再分解的,仅仅研究以原子命题为基本单位的复合命题之间的逻辑关系和推理 。 这样,有些推理用命题逻辑就难以确切地表示出来 。 例如,著名的亚里士多德三段论苏格拉底推理：
退出所有的人都是要死的，
苏格拉底是人，
所以苏格拉底是要死的。
根据常识，认为这个推理是正确的。但是，
若用 Ls来表示，设 P,Q和 R分别表示这三个原子命题，则有
P,Q?R
然而,(P∧ Q)→ R并不是永真式,故上述推理形式又是错误的 。 一个推理,得出矛盾的结论,问题在哪里呢? 问题就在于这类推理中,
各命题之间的逻辑关系不是体现在原子命题之间,而是体现在构成原子命题的内部成分之间,
即体现在命题结构的更深层次上 。 对此,Ls是无能为力的 。 所以,在研究某些推理时,有必要对原子命题作进一步分析,分析出其中的个体词,谓词和量词,研究它们的形式结构的逻辑关系,正确的推理形式和规则,这些正是谓词逻辑 （ 简称为 Lp） 的基本内容 。
2.1 个体、谓词和量词
2.2 谓词公式与翻译
2.3 约束变元与自由变元
2.4 公式解释与类型
2.5 等价式与蕴涵式
2.6 谓词公式范式
2.7 谓词逻辑的推理理论
2.1 个体、谓词和量词在 Lp中,命题是具有真假意义的陈述句 。
从语法上分析,一个陈述句由主语和谓语两部分组成 。 在 Lp中,为揭示命题内部结构及其不同命题的内部结构关系,就按照这两部分对命题进行分析,并且把主语称为个体或客体,把谓语称为谓词 。
１,个体、谓词和命题的谓词形式定义 2.1.1 在原子命题中，所描述的对象称为个体；用以描述个体的性质或个体间关系的部分，称为谓词。
个体，是指可以独立存在的事物，它可以是具体的，也可以是抽象的，如张明，计算机，
精神等。表示特定的个体，称为个体常元，以 a，
b,c… 或带下标的 ai,bi,ci… 表示；表示不确定的个体，称为个体变元，以 x,y,z… 或 xi,yi，
zi… 表示。
谓词，当与一个个体相联系时，它刻划了个体性质；当与两个或两个以上个体相联系时，
它刻划了个体之间的关系。表示特定谓词，称为谓词常元，表示不确定的谓词，称为谓词变元，都用大写英文字母，如 P,Q,R,…,或其带上、下标来表示。在本书中，不对谓词变元作更多地讨论。
对于给定的命题，当用表示其个体的小写字母和表示其谓词的大写字母来表示时，规定把小写字母写在大写字母右侧的圆括号 ( )内。
例如，在命题“张明是位大学生”中，“张明”
是个体，“是位大学生”是谓词，它刻划了
“张明”的性质。设 S：是位大学生,c：张明，
则“张明是位大学生”可表示为 S(c)，或者写成
S(c)：张明是位大学生。又如，在命题“武汉位于北京和广州之间”中，武汉、北京和广州是三个个体，而,… 位于 … 和 … 之间”是谓词，
它刻划了武汉、北京和广州之间的关系。设
P,… 位于 … 和 … 之间,a：武汉,b：北京,c：
广州，则 P(a,b,c)：武汉位于北京和广州之间。
定义 2.1.2 一个原子命题用一个谓词 (如 P)
和 n个有次序的个体常元 (如 a1,a2,…,an)表示成 P(a1,a2,…,an)，称它为该原子命题的谓词形式或命题的谓词形式。
应注意的是，命题的谓词形式中的个体出现的次序影响命题的真值，不是随意变动，否则真值会有变化。如上述例子中,P(b,a,c)是假。
２,原子谓词公式原子命题的谓词形式还可以进一步加以抽象，比如在谓词右侧的圆括号内的 n个个体常元被替换成个体变元，如 x1,x2,··,xn，这样便得了一种关于命题结构的新表达形式，称之为 n元原子谓词。
定义 2.1.3 由一个谓词 (如 P)和 n个体变元
(如 x1,x2,…,xn)组成的 P(x1,x2,…,xn)，
称它为 n元原子谓词或 n元命题函数，简称 n元谓词。而个体变元的论述范围，称为个体域或论域。
当 n=1时，称一元谓词；当 n=2时，称为二元谓词,… 。特别地，当 n=0，称为零元谓词。
零元谓词是命题，这样命题与谓词就得到了统一。
n元谓词不是命题，只有其中的个体变元用特定个体或个体常元替代时，才能成为一个命题。但个体变元在哪些论域取特定的值，对命题的真值极有影响。例如，令 S(x),x是大学生。
若 x的论域为某大学的计算机系中的全体同学，
则 S(x)是真的；若 x的论域是某中学的全体学生，
则 S(x)是假的；若 x的论域是某剧场中的观众，
且观众中有大学生也有非大学生的其它观众，
则 S(x)是真值是不确定的。
通常，把一个 n元谓词中的每个个体的论域综合在一起作为它的论域，称为 n元谓词的全总论域。定义了全总论域，为深入研究命题提供了方便。当一个命题没有指明论域时，一般都从全总论域作为其论域。而这时又常常要采用一个谓词如 P(x)来限制个体变元 x的取值范围，
并把 P(x)称为特性谓词。
３,量词利用 n元谓词和它的论域概念，有时还是不能用符号来很准确地表达某些命题，例如 S(x)
表示 x是大学生，而 x的个体域为某单位的职工，
那么 S(x)可表示某单位职工都是大学生，也可表示某单位有一些职工是大学生，为了避免理解上的歧义，在 Lp中，需要引入用以刻划“所有的”、“存在一些”等表示不同数量的词，
即量词，其定义如下：
定义 2.1.4 ① 符号?称为全称量词符，用来表达“对所有的”、“每一个”、“对任何一个”、“一切”等词语；?x称为全称量词，称 x
为指导变元。
②符号?称为存在量词符，用来表达“存在一些”、“至少有一个”、“对于一些”、
“某个”等词语；?x称为存在量词,x称为指导变元。
③ 符号?!称为存在唯一量词符，用来表达
“恰有一个”、“存在唯一”等词语；?!x称为存在唯一量词，称 x为指导变元。
全称量词、存在量词、存在唯一量词统称量词。量词记号是由逻辑学家 Fray引入的，有了量词之后，用逻辑符号表示命题的能力大大加强了。
例 2.1.1 试用量词、谓词表示下列命题：
① 所有大学生都热爱祖国；
② 每个自然数都是实数；
③ 一些大学生有远大理想；
④ 有的自然数是素数。
解 令 S(x),x是大学生,L(x),x热爱祖国，
N(x),x是自然数,R(x),x是实数,I(x),x有远大理想,P(x),x是素数。
则例中各命题分别表示为：
① (?x)(S(x)?L(x)) ② (?x)(N(x)?R(x))
③ (?x)(S(x)?I(x)) ④ (?x)(N(x)?P(x))
在该例的解答中，由于命题中没有指明个体域，这便意味着各命题是在全总论域中讨论，
因而都使用了特性谓词，如 S(x),N(x)。而且还可以看出，量词与特性谓词的搭配还有一定规律，即全称量词后跟一个条件式，而特性谓词作为其前件出现；存在量词后跟一个合取式，
特性谓词作为一个合取项出现。
如果在解答时，指明了个体域，便不用特性谓词，例如在①、③中令个体域为全体大学生，②和④中的个体域为全部自然数，则可符号化为：
① (?x)L(x) ② (?x)R(x)
③ (?x)I(x) ④ (?x)P(x)
谓词前加上了量词，称为谓词的量化。若一个谓词中所有个体变元都量化了，则该谓词就变成了命题。这是因为在谓词被量化后，可以在整个个体域中考虑命题的真值了。这如同数学中的函数 f(x),的值是不确定的，
但 可确定其值。
2.2 谓词公式与翻译
１,谓词公式为了方便处理数学和计算机科学的逻辑问题及谓词表示的直觉清晰性,将引进项的概念 。
定义 2.2.1 项由下列规则形成：
① 个体常元和个体变元是项；
② 若 f是 n元函数,且 t1,t2,…,tn是项,
则 f(t1,t2,…,tn)是项；
③ 所有项都由 ① 和 ② 生成 。
有了项的定义，函数的概念就可用来表示个体常元和个体变元。例如，令 f(x,y)表示 x+y，
谓词 N(x)表示 x是自然数，那么 f(2,3)表示个体自然数 5，而 N(f(2,3))表示 5是自然数。这里函数是就广义而言的，例如 P(x):x是教授,f(x):x的父亲,c:张强，那么 P(f(c))便是表示“张强的父亲是教授”这一命题。
函数的使用给谓词表示带来很大方便。例如，用谓词表示命题：对任意整数 x,x2-
1=(x+1)(x-1)是恒等式。令 I(x):x是整数，
f(x)=x2-1,g(x)=(x+1)(x-1),E(x,y):x=y，则该命题可表示成,(?x)(I(x)?E(f(x),g(x)))。
定义 2.2.2 若 P(x1,x2,…,xn)是 n元谓词，
t1,t2,…,tn是项，则称 P(t1,t2,…,tn)为 Ls
中原子谓词公式，简称原子公式。
下面，由原子公式出发，给出 Lp中的合式谓词公式的归纳定义。
定义 2.2.3 合式谓词公式当且仅当由下列规则形成的符号串
① 原子公式是合式谓词公式；
② 若 A是合式谓词公式，则 (?A)是合式谓词公式；
③ 若 A,B是合式谓词公式，则 (A∧ B)，
(A∨ B),(A→ B)和 (A?B)都是合式谓词公式；
④ 若 A是合式谓词公式,x是个体变元，则
(?x)A,(?x)A都是合式谓词公式；
⑤ 仅有有限项次使用①、②、③和④形成的才是合式谓词公式。
２,谓词逻辑的翻译把一个文字叙述的命题,用谓词公式表示出来,称为谓词逻辑的翻译或符号化；反之亦然 。 一般说来,符号化的步骤如下：
① 正确理解给定命题 。 必要时把命题改叙,
使其中每个原子命题,原子命题之间的关系能明显表达出来 。
② 把每个原子命题分解成个体、谓词和量词；在全总论域讨论时，要给出特性谓词。
③找出恰当量词。应注意全称量词 (?x)后跟条件式，存在量词 (?x)后跟合取式。
④用恰当的联结词把给定命题表示出来。
例 2.2.2 将命题,没有最大的自然数,符号化 。
解 命题中,没有最大的,显然是对所有的自然数而言,所以可理解为,对所有的 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)))。
例 2.2.3 将语句“今天有雨雪，有些人会跌跤”符号化。
解 本语句可理解为“若今天下雨又下雪，
则存在 x,x是人且 x会跌跤”。令 R:今天下雨，
S:今天下雪,M(x):x是人,F(x):x会跌跤，则本语句可表示为,R?S?(?x)(M(x)?F(x))。
由于人们对命题的文字叙述含意理解的不同，强调的重点不同，会影响到命题符号化的形式不同。
2.3 约束变元与自由变元定义 2.3.1 给定一个谓词公式 A,其中有一部分公式形如 (?x)B(x)或 (?x)B(x),则称它为 A
的 x约束部分,称 B(x)为相应量词的作用域或辖域 。 在辖域中,x的所有出现称为约束出现,x
称为约束变元； B中不是约束出现的其它个体变元的出现称为自由出现,这些个体变元称自由变元 。
对于给定的谓词公式，能够准确地判定它的辖域、约束变元和自由变元是很重要的。
通常，一个量词的辖域是某公式 A的一部分，称为 A的子公式。因此，确定一个量词的辖域即是找出位于该量词之后的相邻接的子公式，
具体地讲：
① 若量词后有括号，则括号内的子公式就是该量词的辖域；
②若量词后无括号，则与量词邻接的子公式为该量词的辖域。
判定给定公式 A中个体变元是约束变元还是自由变元，关键是要看它在 A中是约束出现，
还是自由出现。
今后常用元语言符号 A(x)表示 x是其中的一个个体变元自由出现的任意公式,如 A(x)可为
P(x)?Q(x),P(x)?(?y)Q(x,y)等 。 一旦在 A(x)前加上量词 (?x)或 (?x),即得公式 (?x)A(x),或
(?x)A(x)。 这时,x即是约束出现了 。 类似地,
用 A(x,y)表示 x和 y是自由出现的公式 。
定义 2.3.2 设 A为任意一个公式，若 A中无自由出现的个体变元，则称 A为封闭的合式公式，
简称闭式。
由闭式定义可知，闭式中所有个体变元均为约束出现。例如,(?x)(P(x)?Q(x))和
(?x)(?y)(P(x)?Q(x,y))是闭式，而
(?x)(P(x)?Q(x,y))和 (?y)(?z)L(x,y,z)不是闭式。
从下面讨论可以看出，在一公式中，有的个体变元既可以是约束出现，又可以是自由出现，这就容易产生混淆。为了避免混淆，采用下面两个规则：
①约束变元改名规则，将量词辖域中某个约束出现的个体变元及相应指导变元，改成本辖域中未曾出现过的个体变元，其余不变。
②自由变元代入规则，对某自由出现的个体变元可用个体常元或用与原子公式中所有个体变元不同的个体变元去代入，且处处代入。
改名规则与代入规则的共同点都是不能改变约束关系,而不同点是：
① 施行的对象不同 。 改名是对约束变元施行,代入是对自由变元施行 。
② 施行的范围不同 。 改名可以只对公式中一个量词及其辖域内施行,即只对公式的一个子公式施行；而代入必须对整个公式同一个自由变元的所有自由出现同时施行,即必须对整个公式施行 。
③ 施行后的结果不同。改名后，公式含义不变，因为约束变元只改名为另一个个体变元，
约束关系不改变。约束变元不能改名为个体常元；代入，不仅可用另一个个体变元进行代入，
并且也可用个体常元去代入，从而使公式由具有普遍意义变为仅对该个体常元有意义，即公式的含义改变了。
上面讲了约束变元改名规则和自由变元代入规则。有时在一公式 A(x)中，也会用项 t替代个体变元 x，那么如何做才能不引起量词和辖域间关系发生变化？或者说，替代后结果与替代前在直觉解释上没有区别这就需要引入项 t对
A(x)中的 x是自由的概念。
定义 2.3.3 令 A是任意合式公式,x为自由出现。如果 x不出现 A中项 t所含的任意个体变元
y的量词 (?y)或 (?y)的辖域内，称项 t对 A中的 x是自由的。
例如，取 A为 (?x)B(x,y)?(?z)C(x,z)，则项
f(x,w)对 y不是自由的，项 g(y,z)对 y是自由的，项
h(x,z)不是自由的，项 y对 x是自由的。
由定义可知，对任何公式 A和任意个体变元 x，不管 x在 A中是否自由出现,x对 A中的 x是自由的。
2.4 公式解释与类型
1,公式解释一般情况下,Lp中的公式含有：个体常元,
个体变元 （ 约束变元或自由变元 ）,函数变元,
为谓词变元等,对各种变元用指定的特殊常元去代替,就构成了一个公式的解释 。 当然在给定的解释下,可以对多个公式进行解释 。 下面给出解释的一般定义 。
定义 2.4.1 一个解释 I由下面 4部分组成：
① 非空个体域 DI。
② DI中部分特定元素 a’,b’,… 。
③ DI上的特定一些函数 f’,g’,… 。
④ DI上特定谓词,P’,Q’,… 。
在一个具体解释中，个体常元、函数符号、
谓词符号的数量一般是有限的，并且其解释一旦确定下来就不再改变，只是个体变元的值在个体域 DI内变化，量词符?或?仅作用于 DI中的元素。
2,公式类型定义 2.4.2 ① 若一公式在任何解释下都是真的,称该公式为逻辑有效的,或永真的 。
② 若一公式在任何解释下都是假的,称该公式为矛盾式,或永假式 。
③ 若一公式至少存在一个解释使其为真,
称该公式为可满足式 。
从定义可知，逻辑有效式为可满足式，反之未必成立。
与命题公式中分类一样，谓词公式也分为三种类型，即逻辑有效式（或重言式）、矛盾式（或永假式）和可满足式。
由于谓词公式的复杂性和解释的多样性，
至今还没有一个可行的算法判定任何公式的类型。早在 1936年,Churen和 Turing各自独立地证明了：对于 Lp，其判定问题是不可解的。但是,Lp是个半个可判定的，即若 Lp中公式是重言式，则存在算法在有限步骤内能验证它。当然，对于一些较为简单的公式，或某些特殊公式，还是可以判定其类型的。
下面讨论代入规则的扩展，因为它对判定重言式这种公式类型是很有用的。
在 2.3节中，介绍了自由变元的代入规则，
实际上代入规则并非只局限于自由变元，对公式中命题变元、谓词变元均可实施代入，其关键是不能因为代入而改变原有公式的约束关系。
今将谓词变元（包括命题变元）代入规则叙述如下：
在一公式中，一个 n元 (n≥0)谓词变元
P(x1,x2,··,xn)可以代至少有 n个自由变元的公式
B(y1,y2,··,yn,yn+1,yn+2,··,yn+r)，其中 r≥0,y1,y2,··,yn
是分别对应于 x1,x2,··,xn的任意选定的 n个自由变元，且对 P出现进行处处代入,B中的 r个自由变元不允许在原公式中以约束出现,P中的个体变元也不允许在 B中以约束出现。
为保证代入规则顺利而正确地实行，常常对约束变元改名而适应之。
2.5 等价式与蕴涵式
1,等价式定义 2.5.1 设 A,B为任意两个公式,若
A?B为逻辑有效的,则称 A与 B是等价的,记为
A?B,称 A?B为等价式 。
由于重言式 (永真式 )都是逻辑有效的,可见 1.3节中的命题定律 （ 基本等价式 ） 都是 Lp 等价式 。
此外，还有一置换规则：
设?(A)是含有 A出现的公式,?(B)是用公式
B替换若干个公式 A的结果。若 A?B，则?(A)?
(B)。
显然，若?(A)为重言式，则?(B)也是重言式。
下面给出涉及量词的一些等价式，它们的证明略去了。
(1) 量词否定等价式：
(a)?(?x)A?(?x)?A
(b)?(?x)A?(?x)?A
这两个等价式，可用量词的定义给予说明。
由于“并非对一切 x,A为真”等价于“存在一些 x,?A为真”，故 (a)成立。由于“不存在一些
x,A为真”等价于“对一切 x,?A为真”，所以
(b)成立。这两个等价式的意义是：否定联结词可通过量词深入到辖域中。对比这两个式子，
容易看出，将 (?x)与 (?x)两者互换，可从一个式子得到另一个式子，这表明 (?x)与 (?x)具有对偶性。另外，由于这两个公式成立也表明了，两个量词是不独立的，可以互相表示，所以只有一个量词就够了。
对于多重量词前置,?”，可反复应用上面结果，逐次右移?。例如，
(?x)(?y)(?z)P(x,y,z)?(?x)(?y)(?z)?P(x,y,z)
（ 2） 量词辖域缩小或扩大等价式设 B是不含 x自由出现,A(x)为有 x自由出现的任意公式，则有：
(a) (?x)(A(x)∧ B)?(?x)A(x)∧ B
(b) (?x)(A(x)∨ B)?(?x)A(x)∨ B
(c) (?x)(A(x)→ B)?(?x)A(x)→ B
(d) (?x)(B→ A(x))?B→(?x)A(x)
(e) (?x)(A(x)∧ B)?(?x)A(x)∧ B
(f) (?x)(A(x)∨ B)?(?x)A(x)∨ B
(g) (?x)(A(x)→ B)?(?x)A(x)→ B
(h) (?x)(B→ A(x))?B→(?x)A(x)。
(3) 量词分配律等价式：
(a) (?x)(A(x)∧ B(x))?(?x)A(x)∧ (?x)B(x)
(b) (?x)(A(x)∨ B(x))?(?x)A(x)∨ (?x)B(x)
其中,A(x),B(x)为有 x自由出现的任何公式。
(4) 多重量词等价式
(a) (?x)(?y)A(x,y)?(?y)(?x)A(x,y)
(b) (?x)(?y)A(x,y)?(?y)(?x)A(x,y)
其中 A(x,y)为含有 x自由出现的任意公式。
2,蕴涵式由于 Ls中蕴涵式 （ 或永真条件式 ） 在 Lp中都是逻辑有效的,而且使用代入规则得到蕴涵式也都是 Lp中逻辑有效的 。
例如,(?x)P(x)?(?x)P(x)∨ (?y)Q(y)
附加
((?x)P(x)→ Q(x,y))∧ (?x)P(x)? Q(x,y)
假言推理下面将给出 Lp中的一些蕴涵式，其证明省略了。
(1)
(a)(?x)A(x)∨ (?x)B(x)?(?x)(A(x)∨ B(x))
(b) (?x)(A(x)∧ B(x))?(?x)A(x)∧ (?x)B(x)
(c) (?x)(A(x)→ B(x))?(?x)A(x)→(?x)B(x)
(d) (?x)(A(x)→ B(x))?(?x)A(x)→(?x)B(x)
其中,A(x)和 B(x)为含有 x自由出现的任意公式。
(2) (a) (?x)(?y)A(x,y)?(?x)A(x,x)
(b) (?x)A(x,x)?(?x)(?y)A(x,y)
(c) (?x)(?y)A(x,y)?(?y)(?x)A(x,y)
(d) (?y)(?x)A(x,y)?(?x)(?y)A(x,y)
(e) (?x)(?y)A(x,y)?(?y)(?x)A(x,y)
其中,A(x,y)为含有 x,y的自由出现的任意公式。
2.6 谓词公式范式
１,前束范式定义 2.9.1 一个合式公式称为前束范式,如果它有如下形式：
(Q1x1)(Q2x2)… (Qkxk)B
其中 Qi(1≤i≤k)为?或?,B为不含有量词的公式 。 称 Q1x1Q2x2… Qkxk为公式的首标 。
特别地,若 Ａ 中无量词,则 Ａ 也看作是前束范式 。
可见，前束范式的特点是，所有量词均非否定地出现在公式最前面，且它的辖域一直延伸到公式之末。
例如,(?x)(?y)(z)(P(x,y)?Q(y,z)),R(x,y)
等都是前束范式，而 (?x)P(x)?(?y)Q(y)，
(?x)(P(x)?(?y)Q(x,y))不是前束范式。
定理 2.6.1 (前束范式存在定理 ) Lp中任意公式 A都有与之等价的前束范式。
２,斯柯林范式前束范式的的优点是全部量词集中在公式前面,其缺点是各量词的排列无一定规则,这样当把一个公式化归为前束范式时,其表达形式会显现多种情形,不便应用 。 1920年斯柯林
(Skolem)提出对前束范式首标中量词出现的次序给出规定：每个存在量词均在全称量词之前 。
按此规定得到的范式形式,称为斯柯林范式 。
显然,任一公式均可化为斯柯林范式 。 它的优点是：全公式按顺序可分为三部分,公式的所有存在量词,所有全称量词和辖域 。 这给 Lp的研究提供了一定的方便 。
2.7 谓词逻辑的推理理论
Lp是 Ls的进一步深化和发展,因此 Ls的推理理论在 Lp中几乎可以完全照搬,只不过这时涉及的公式是 Lp的公式罢了 。 在 Lp中,某些前提和结论可能受到量词的约束,为确立前提和结论之间的内部联系,有必要消去量词和添加量词,因此正确理解和运用有关量词规则是 Lp
推理理论中十分重要的关键所在 。
下面在介绍有关量词规则之前做些必要准备。作为定义 2.3.3的一种特例，将给出 A(x)对 y
是自由的这个概念。其目的是，允许用 y代入 x
后得到 A(y)，它不改变原来公式 A(x)的约束关系。
定义 2.7.1 在谓词公式 A(x)中，若 x不自由出现在量词 (?y)或 (?y)的辖域,则称 A(x)对于 y
是自由的。
由定义可知，若 y在 A(x)中不是约束出现，
则 A(x)对于 y一定是自由的。
１,有关量词消去和产生规则量词消去规则：
(1) 全称量词消去规则 (简称 UI或 US规则 )
有两种形式,(?x)A(x)?A(c)
其中 c为任意个体常元
(?x)A(x)?A(y)
A(x)对 y是自由的
(2) 存在量词消去规则 (简称 EI或 ES规则 )
有两种形式,(?x)A(x)?A(c) 其中 c为特定个体常元
(?x)A(x)?A(y)
成立充分条件是,① c或 y不得在前提中或者居先推导公式中出现或自由出现； ② 若 A(x)
中有其它自由变元时,不能应用本规则 。
值得注意的是,A(y)只是新引入的暂时假设,它不是对 y的一切值都是成立的 。 y是一个暂时的,表面上的自由变元 。
量词产生规则：
(3) 存在量词产生规则 (简称 EG规则 )
有两种形式,A(c)?(?y)A(y)
其中 c为特定个体常元
A(x)?(?y)A(y)
成立充分条件：①取代 c的个体变元 y不在
A(c)中出现；② A(x)对 y 是自由的；③若 A(x)是推导行中的公式，且 x是由使用 EI引入的，那么不能用 A(x)中除 x外的个体变元作约束变元，或者说,y不得为 A(x)中的个体变元。
(4) 全称量词产生规则 (简称 UG规则 )
A(x)?(?y)A(y)
成立条件,① 前提 A(x)对于 x的任意取值都成立； ② A(x)对 y是自由的； ③ 对于由于使用 EI
规则所得到的公式中原约束变元及与其在同一个原子公式的自由变元,都不能使用本规则而成为指导变元,否则将产生错误推理 。
２,Lp中推理实例
Lp的推理方法是 Ls推理方法的扩展，因此在 Lp中利用的推理规则也是 T规则,P规则和 CP
规则，还有已知的等价式，蕴涵式以及有关量词的消去和产生规则。使用的推理方法是直接构造法和间接证法。
例 2.7.7 试证明下面苏格拉底论证：
所有人都是要死的，
苏格拉底是人，
因此，苏格拉底是要死的。
证明 令 M(x):x是人,D(x):x是要死的,s:
苏格拉底，原题可符号化为：
(?x)(M(x)?D(x)),M(s)?D(s)
推证如下：
{1} （ 1） (?x)(M(x)?D(x)) P
{1} （ 2） M(s)?D(s) UI，（ 1）
{3} （ 3） M(s) P
{1,3} （ 4） D(s) T,(2),(3),I
退出所有的人都是要死的，
苏格拉底是人，
所以苏格拉底是要死的。
根据常识，认为这个推理是正确的。但是，
若用 Ls来表示，设 P,Q和 R分别表示这三个原子命题，则有
P,Q?R
然而,(P∧ Q)→ R并不是永真式,故上述推理形式又是错误的 。 一个推理,得出矛盾的结论,问题在哪里呢? 问题就在于这类推理中,
各命题之间的逻辑关系不是体现在原子命题之间,而是体现在构成原子命题的内部成分之间,
即体现在命题结构的更深层次上 。 对此,Ls是无能为力的 。 所以,在研究某些推理时,有必要对原子命题作进一步分析,分析出其中的个体词,谓词和量词,研究它们的形式结构的逻辑关系,正确的推理形式和规则,这些正是谓词逻辑 （ 简称为 Lp） 的基本内容 。
2.1 个体、谓词和量词
2.2 谓词公式与翻译
2.3 约束变元与自由变元
2.4 公式解释与类型
2.5 等价式与蕴涵式
2.6 谓词公式范式
2.7 谓词逻辑的推理理论
2.1 个体、谓词和量词在 Lp中,命题是具有真假意义的陈述句 。
从语法上分析,一个陈述句由主语和谓语两部分组成 。 在 Lp中,为揭示命题内部结构及其不同命题的内部结构关系,就按照这两部分对命题进行分析,并且把主语称为个体或客体,把谓语称为谓词 。
１,个体、谓词和命题的谓词形式定义 2.1.1 在原子命题中，所描述的对象称为个体；用以描述个体的性质或个体间关系的部分，称为谓词。
个体，是指可以独立存在的事物，它可以是具体的，也可以是抽象的，如张明，计算机，
精神等。表示特定的个体，称为个体常元，以 a，
b,c… 或带下标的 ai,bi,ci… 表示；表示不确定的个体，称为个体变元，以 x,y,z… 或 xi,yi，
zi… 表示。
谓词，当与一个个体相联系时，它刻划了个体性质；当与两个或两个以上个体相联系时，
它刻划了个体之间的关系。表示特定谓词，称为谓词常元，表示不确定的谓词，称为谓词变元，都用大写英文字母，如 P,Q,R,…,或其带上、下标来表示。在本书中，不对谓词变元作更多地讨论。
对于给定的命题，当用表示其个体的小写字母和表示其谓词的大写字母来表示时，规定把小写字母写在大写字母右侧的圆括号 ( )内。
例如，在命题“张明是位大学生”中，“张明”
是个体，“是位大学生”是谓词，它刻划了
“张明”的性质。设 S：是位大学生,c：张明，
则“张明是位大学生”可表示为 S(c)，或者写成
S(c)：张明是位大学生。又如，在命题“武汉位于北京和广州之间”中，武汉、北京和广州是三个个体，而,… 位于 … 和 … 之间”是谓词，
它刻划了武汉、北京和广州之间的关系。设
P,… 位于 … 和 … 之间,a：武汉,b：北京,c：
广州，则 P(a,b,c)：武汉位于北京和广州之间。
定义 2.1.2 一个原子命题用一个谓词 (如 P)
和 n个有次序的个体常元 (如 a1,a2,…,an)表示成 P(a1,a2,…,an)，称它为该原子命题的谓词形式或命题的谓词形式。
应注意的是，命题的谓词形式中的个体出现的次序影响命题的真值，不是随意变动，否则真值会有变化。如上述例子中,P(b,a,c)是假。
２,原子谓词公式原子命题的谓词形式还可以进一步加以抽象，比如在谓词右侧的圆括号内的 n个个体常元被替换成个体变元，如 x1,x2,··,xn，这样便得了一种关于命题结构的新表达形式，称之为 n元原子谓词。
定义 2.1.3 由一个谓词 (如 P)和 n个体变元
(如 x1,x2,…,xn)组成的 P(x1,x2,…,xn)，
称它为 n元原子谓词或 n元命题函数，简称 n元谓词。而个体变元的论述范围，称为个体域或论域。
当 n=1时，称一元谓词；当 n=2时，称为二元谓词,… 。特别地，当 n=0，称为零元谓词。
零元谓词是命题，这样命题与谓词就得到了统一。
n元谓词不是命题，只有其中的个体变元用特定个体或个体常元替代时，才能成为一个命题。但个体变元在哪些论域取特定的值，对命题的真值极有影响。例如，令 S(x),x是大学生。
若 x的论域为某大学的计算机系中的全体同学，
则 S(x)是真的；若 x的论域是某中学的全体学生，
则 S(x)是假的；若 x的论域是某剧场中的观众，
且观众中有大学生也有非大学生的其它观众，
则 S(x)是真值是不确定的。
通常，把一个 n元谓词中的每个个体的论域综合在一起作为它的论域，称为 n元谓词的全总论域。定义了全总论域，为深入研究命题提供了方便。当一个命题没有指明论域时，一般都从全总论域作为其论域。而这时又常常要采用一个谓词如 P(x)来限制个体变元 x的取值范围，
并把 P(x)称为特性谓词。
３,量词利用 n元谓词和它的论域概念，有时还是不能用符号来很准确地表达某些命题，例如 S(x)
表示 x是大学生，而 x的个体域为某单位的职工，
那么 S(x)可表示某单位职工都是大学生，也可表示某单位有一些职工是大学生，为了避免理解上的歧义，在 Lp中，需要引入用以刻划“所有的”、“存在一些”等表示不同数量的词，
即量词，其定义如下：
定义 2.1.4 ① 符号?称为全称量词符，用来表达“对所有的”、“每一个”、“对任何一个”、“一切”等词语；?x称为全称量词，称 x
为指导变元。
②符号?称为存在量词符，用来表达“存在一些”、“至少有一个”、“对于一些”、
“某个”等词语；?x称为存在量词,x称为指导变元。
③ 符号?!称为存在唯一量词符，用来表达
“恰有一个”、“存在唯一”等词语；?!x称为存在唯一量词，称 x为指导变元。
全称量词、存在量词、存在唯一量词统称量词。量词记号是由逻辑学家 Fray引入的，有了量词之后，用逻辑符号表示命题的能力大大加强了。
例 2.1.1 试用量词、谓词表示下列命题：
① 所有大学生都热爱祖国；
② 每个自然数都是实数；
③ 一些大学生有远大理想；
④ 有的自然数是素数。
解 令 S(x),x是大学生,L(x),x热爱祖国，
N(x),x是自然数,R(x),x是实数,I(x),x有远大理想,P(x),x是素数。
则例中各命题分别表示为：
① (?x)(S(x)?L(x)) ② (?x)(N(x)?R(x))
③ (?x)(S(x)?I(x)) ④ (?x)(N(x)?P(x))
在该例的解答中，由于命题中没有指明个体域，这便意味着各命题是在全总论域中讨论，
因而都使用了特性谓词，如 S(x),N(x)。而且还可以看出，量词与特性谓词的搭配还有一定规律，即全称量词后跟一个条件式，而特性谓词作为其前件出现；存在量词后跟一个合取式，
特性谓词作为一个合取项出现。
如果在解答时，指明了个体域，便不用特性谓词，例如在①、③中令个体域为全体大学生，②和④中的个体域为全部自然数，则可符号化为：
① (?x)L(x) ② (?x)R(x)
③ (?x)I(x) ④ (?x)P(x)
谓词前加上了量词，称为谓词的量化。若一个谓词中所有个体变元都量化了，则该谓词就变成了命题。这是因为在谓词被量化后，可以在整个个体域中考虑命题的真值了。这如同数学中的函数 f(x),的值是不确定的，
但 可确定其值。
2.2 谓词公式与翻译
１,谓词公式为了方便处理数学和计算机科学的逻辑问题及谓词表示的直觉清晰性,将引进项的概念 。
定义 2.2.1 项由下列规则形成：
① 个体常元和个体变元是项；
② 若 f是 n元函数,且 t1,t2,…,tn是项,
则 f(t1,t2,…,tn)是项；
③ 所有项都由 ① 和 ② 生成 。
有了项的定义，函数的概念就可用来表示个体常元和个体变元。例如，令 f(x,y)表示 x+y，
谓词 N(x)表示 x是自然数，那么 f(2,3)表示个体自然数 5，而 N(f(2,3))表示 5是自然数。这里函数是就广义而言的，例如 P(x):x是教授,f(x):x的父亲,c:张强，那么 P(f(c))便是表示“张强的父亲是教授”这一命题。
函数的使用给谓词表示带来很大方便。例如，用谓词表示命题：对任意整数 x,x2-
1=(x+1)(x-1)是恒等式。令 I(x):x是整数，
f(x)=x2-1,g(x)=(x+1)(x-1),E(x,y):x=y，则该命题可表示成,(?x)(I(x)?E(f(x),g(x)))。
定义 2.2.2 若 P(x1,x2,…,xn)是 n元谓词，
t1,t2,…,tn是项，则称 P(t1,t2,…,tn)为 Ls
中原子谓词公式，简称原子公式。
下面，由原子公式出发，给出 Lp中的合式谓词公式的归纳定义。
定义 2.2.3 合式谓词公式当且仅当由下列规则形成的符号串
① 原子公式是合式谓词公式；
② 若 A是合式谓词公式，则 (?A)是合式谓词公式；
③ 若 A,B是合式谓词公式，则 (A∧ B)，
(A∨ B),(A→ B)和 (A?B)都是合式谓词公式；
④ 若 A是合式谓词公式,x是个体变元，则
(?x)A,(?x)A都是合式谓词公式；
⑤ 仅有有限项次使用①、②、③和④形成的才是合式谓词公式。
２,谓词逻辑的翻译把一个文字叙述的命题,用谓词公式表示出来,称为谓词逻辑的翻译或符号化；反之亦然 。 一般说来,符号化的步骤如下：
① 正确理解给定命题 。 必要时把命题改叙,
使其中每个原子命题,原子命题之间的关系能明显表达出来 。
② 把每个原子命题分解成个体、谓词和量词；在全总论域讨论时，要给出特性谓词。
③找出恰当量词。应注意全称量词 (?x)后跟条件式，存在量词 (?x)后跟合取式。
④用恰当的联结词把给定命题表示出来。
例 2.2.2 将命题,没有最大的自然数,符号化 。
解 命题中,没有最大的,显然是对所有的自然数而言,所以可理解为,对所有的 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)))。
例 2.2.3 将语句“今天有雨雪，有些人会跌跤”符号化。
解 本语句可理解为“若今天下雨又下雪，
则存在 x,x是人且 x会跌跤”。令 R:今天下雨，
S:今天下雪,M(x):x是人,F(x):x会跌跤，则本语句可表示为,R?S?(?x)(M(x)?F(x))。
由于人们对命题的文字叙述含意理解的不同，强调的重点不同，会影响到命题符号化的形式不同。
2.3 约束变元与自由变元定义 2.3.1 给定一个谓词公式 A,其中有一部分公式形如 (?x)B(x)或 (?x)B(x),则称它为 A
的 x约束部分,称 B(x)为相应量词的作用域或辖域 。 在辖域中,x的所有出现称为约束出现,x
称为约束变元； B中不是约束出现的其它个体变元的出现称为自由出现,这些个体变元称自由变元 。
对于给定的谓词公式，能够准确地判定它的辖域、约束变元和自由变元是很重要的。
通常，一个量词的辖域是某公式 A的一部分，称为 A的子公式。因此，确定一个量词的辖域即是找出位于该量词之后的相邻接的子公式，
具体地讲：
① 若量词后有括号，则括号内的子公式就是该量词的辖域；
②若量词后无括号，则与量词邻接的子公式为该量词的辖域。
判定给定公式 A中个体变元是约束变元还是自由变元，关键是要看它在 A中是约束出现，
还是自由出现。
今后常用元语言符号 A(x)表示 x是其中的一个个体变元自由出现的任意公式,如 A(x)可为
P(x)?Q(x),P(x)?(?y)Q(x,y)等 。 一旦在 A(x)前加上量词 (?x)或 (?x),即得公式 (?x)A(x),或
(?x)A(x)。 这时,x即是约束出现了 。 类似地,
用 A(x,y)表示 x和 y是自由出现的公式 。
定义 2.3.2 设 A为任意一个公式，若 A中无自由出现的个体变元，则称 A为封闭的合式公式，
简称闭式。
由闭式定义可知，闭式中所有个体变元均为约束出现。例如,(?x)(P(x)?Q(x))和
(?x)(?y)(P(x)?Q(x,y))是闭式，而
(?x)(P(x)?Q(x,y))和 (?y)(?z)L(x,y,z)不是闭式。
从下面讨论可以看出，在一公式中，有的个体变元既可以是约束出现，又可以是自由出现，这就容易产生混淆。为了避免混淆，采用下面两个规则：
①约束变元改名规则，将量词辖域中某个约束出现的个体变元及相应指导变元，改成本辖域中未曾出现过的个体变元，其余不变。
②自由变元代入规则，对某自由出现的个体变元可用个体常元或用与原子公式中所有个体变元不同的个体变元去代入，且处处代入。
改名规则与代入规则的共同点都是不能改变约束关系,而不同点是：
① 施行的对象不同 。 改名是对约束变元施行,代入是对自由变元施行 。
② 施行的范围不同 。 改名可以只对公式中一个量词及其辖域内施行,即只对公式的一个子公式施行；而代入必须对整个公式同一个自由变元的所有自由出现同时施行,即必须对整个公式施行 。
③ 施行后的结果不同。改名后，公式含义不变，因为约束变元只改名为另一个个体变元，
约束关系不改变。约束变元不能改名为个体常元；代入，不仅可用另一个个体变元进行代入，
并且也可用个体常元去代入，从而使公式由具有普遍意义变为仅对该个体常元有意义，即公式的含义改变了。
上面讲了约束变元改名规则和自由变元代入规则。有时在一公式 A(x)中，也会用项 t替代个体变元 x，那么如何做才能不引起量词和辖域间关系发生变化？或者说，替代后结果与替代前在直觉解释上没有区别这就需要引入项 t对
A(x)中的 x是自由的概念。
定义 2.3.3 令 A是任意合式公式,x为自由出现。如果 x不出现 A中项 t所含的任意个体变元
y的量词 (?y)或 (?y)的辖域内，称项 t对 A中的 x是自由的。
例如，取 A为 (?x)B(x,y)?(?z)C(x,z)，则项
f(x,w)对 y不是自由的，项 g(y,z)对 y是自由的，项
h(x,z)不是自由的，项 y对 x是自由的。
由定义可知，对任何公式 A和任意个体变元 x，不管 x在 A中是否自由出现,x对 A中的 x是自由的。
2.4 公式解释与类型
1,公式解释一般情况下,Lp中的公式含有：个体常元,
个体变元 （ 约束变元或自由变元 ）,函数变元,
为谓词变元等,对各种变元用指定的特殊常元去代替,就构成了一个公式的解释 。 当然在给定的解释下,可以对多个公式进行解释 。 下面给出解释的一般定义 。
定义 2.4.1 一个解释 I由下面 4部分组成：
① 非空个体域 DI。
② DI中部分特定元素 a’,b’,… 。
③ DI上的特定一些函数 f’,g’,… 。
④ DI上特定谓词,P’,Q’,… 。
在一个具体解释中，个体常元、函数符号、
谓词符号的数量一般是有限的，并且其解释一旦确定下来就不再改变，只是个体变元的值在个体域 DI内变化，量词符?或?仅作用于 DI中的元素。
2,公式类型定义 2.4.2 ① 若一公式在任何解释下都是真的,称该公式为逻辑有效的,或永真的 。
② 若一公式在任何解释下都是假的,称该公式为矛盾式,或永假式 。
③ 若一公式至少存在一个解释使其为真,
称该公式为可满足式 。
从定义可知，逻辑有效式为可满足式，反之未必成立。
与命题公式中分类一样，谓词公式也分为三种类型，即逻辑有效式（或重言式）、矛盾式（或永假式）和可满足式。
由于谓词公式的复杂性和解释的多样性，
至今还没有一个可行的算法判定任何公式的类型。早在 1936年,Churen和 Turing各自独立地证明了：对于 Lp，其判定问题是不可解的。但是,Lp是个半个可判定的，即若 Lp中公式是重言式，则存在算法在有限步骤内能验证它。当然，对于一些较为简单的公式，或某些特殊公式，还是可以判定其类型的。
下面讨论代入规则的扩展，因为它对判定重言式这种公式类型是很有用的。
在 2.3节中，介绍了自由变元的代入规则，
实际上代入规则并非只局限于自由变元，对公式中命题变元、谓词变元均可实施代入，其关键是不能因为代入而改变原有公式的约束关系。
今将谓词变元（包括命题变元）代入规则叙述如下：
在一公式中，一个 n元 (n≥0)谓词变元
P(x1,x2,··,xn)可以代至少有 n个自由变元的公式
B(y1,y2,··,yn,yn+1,yn+2,··,yn+r)，其中 r≥0,y1,y2,··,yn
是分别对应于 x1,x2,··,xn的任意选定的 n个自由变元，且对 P出现进行处处代入,B中的 r个自由变元不允许在原公式中以约束出现,P中的个体变元也不允许在 B中以约束出现。
为保证代入规则顺利而正确地实行，常常对约束变元改名而适应之。
2.5 等价式与蕴涵式
1,等价式定义 2.5.1 设 A,B为任意两个公式,若
A?B为逻辑有效的,则称 A与 B是等价的,记为
A?B,称 A?B为等价式 。
由于重言式 (永真式 )都是逻辑有效的,可见 1.3节中的命题定律 （ 基本等价式 ） 都是 Lp 等价式 。
此外，还有一置换规则：
设?(A)是含有 A出现的公式,?(B)是用公式
B替换若干个公式 A的结果。若 A?B，则?(A)?
(B)。
显然，若?(A)为重言式，则?(B)也是重言式。
下面给出涉及量词的一些等价式，它们的证明略去了。
(1) 量词否定等价式：
(a)?(?x)A?(?x)?A
(b)?(?x)A?(?x)?A
这两个等价式，可用量词的定义给予说明。
由于“并非对一切 x,A为真”等价于“存在一些 x,?A为真”，故 (a)成立。由于“不存在一些
x,A为真”等价于“对一切 x,?A为真”，所以
(b)成立。这两个等价式的意义是：否定联结词可通过量词深入到辖域中。对比这两个式子，
容易看出，将 (?x)与 (?x)两者互换，可从一个式子得到另一个式子，这表明 (?x)与 (?x)具有对偶性。另外，由于这两个公式成立也表明了，两个量词是不独立的，可以互相表示，所以只有一个量词就够了。
对于多重量词前置,?”，可反复应用上面结果，逐次右移?。例如，
(?x)(?y)(?z)P(x,y,z)?(?x)(?y)(?z)?P(x,y,z)
（ 2） 量词辖域缩小或扩大等价式设 B是不含 x自由出现,A(x)为有 x自由出现的任意公式，则有：
(a) (?x)(A(x)∧ B)?(?x)A(x)∧ B
(b) (?x)(A(x)∨ B)?(?x)A(x)∨ B
(c) (?x)(A(x)→ B)?(?x)A(x)→ B
(d) (?x)(B→ A(x))?B→(?x)A(x)
(e) (?x)(A(x)∧ B)?(?x)A(x)∧ B
(f) (?x)(A(x)∨ B)?(?x)A(x)∨ B
(g) (?x)(A(x)→ B)?(?x)A(x)→ B
(h) (?x)(B→ A(x))?B→(?x)A(x)。
(3) 量词分配律等价式：
(a) (?x)(A(x)∧ B(x))?(?x)A(x)∧ (?x)B(x)
(b) (?x)(A(x)∨ B(x))?(?x)A(x)∨ (?x)B(x)
其中,A(x),B(x)为有 x自由出现的任何公式。
(4) 多重量词等价式
(a) (?x)(?y)A(x,y)?(?y)(?x)A(x,y)
(b) (?x)(?y)A(x,y)?(?y)(?x)A(x,y)
其中 A(x,y)为含有 x自由出现的任意公式。
2,蕴涵式由于 Ls中蕴涵式 （ 或永真条件式 ） 在 Lp中都是逻辑有效的,而且使用代入规则得到蕴涵式也都是 Lp中逻辑有效的 。
例如,(?x)P(x)?(?x)P(x)∨ (?y)Q(y)
附加
((?x)P(x)→ Q(x,y))∧ (?x)P(x)? Q(x,y)
假言推理下面将给出 Lp中的一些蕴涵式，其证明省略了。
(1)
(a)(?x)A(x)∨ (?x)B(x)?(?x)(A(x)∨ B(x))
(b) (?x)(A(x)∧ B(x))?(?x)A(x)∧ (?x)B(x)
(c) (?x)(A(x)→ B(x))?(?x)A(x)→(?x)B(x)
(d) (?x)(A(x)→ B(x))?(?x)A(x)→(?x)B(x)
其中,A(x)和 B(x)为含有 x自由出现的任意公式。
(2) (a) (?x)(?y)A(x,y)?(?x)A(x,x)
(b) (?x)A(x,x)?(?x)(?y)A(x,y)
(c) (?x)(?y)A(x,y)?(?y)(?x)A(x,y)
(d) (?y)(?x)A(x,y)?(?x)(?y)A(x,y)
(e) (?x)(?y)A(x,y)?(?y)(?x)A(x,y)
其中,A(x,y)为含有 x,y的自由出现的任意公式。
2.6 谓词公式范式
１,前束范式定义 2.9.1 一个合式公式称为前束范式,如果它有如下形式：
(Q1x1)(Q2x2)… (Qkxk)B
其中 Qi(1≤i≤k)为?或?,B为不含有量词的公式 。 称 Q1x1Q2x2… Qkxk为公式的首标 。
特别地,若 Ａ 中无量词,则 Ａ 也看作是前束范式 。
可见，前束范式的特点是，所有量词均非否定地出现在公式最前面，且它的辖域一直延伸到公式之末。
例如,(?x)(?y)(z)(P(x,y)?Q(y,z)),R(x,y)
等都是前束范式，而 (?x)P(x)?(?y)Q(y)，
(?x)(P(x)?(?y)Q(x,y))不是前束范式。
定理 2.6.1 (前束范式存在定理 ) Lp中任意公式 A都有与之等价的前束范式。
２,斯柯林范式前束范式的的优点是全部量词集中在公式前面,其缺点是各量词的排列无一定规则,这样当把一个公式化归为前束范式时,其表达形式会显现多种情形,不便应用 。 1920年斯柯林
(Skolem)提出对前束范式首标中量词出现的次序给出规定：每个存在量词均在全称量词之前 。
按此规定得到的范式形式,称为斯柯林范式 。
显然,任一公式均可化为斯柯林范式 。 它的优点是：全公式按顺序可分为三部分,公式的所有存在量词,所有全称量词和辖域 。 这给 Lp的研究提供了一定的方便 。
2.7 谓词逻辑的推理理论
Lp是 Ls的进一步深化和发展,因此 Ls的推理理论在 Lp中几乎可以完全照搬,只不过这时涉及的公式是 Lp的公式罢了 。 在 Lp中,某些前提和结论可能受到量词的约束,为确立前提和结论之间的内部联系,有必要消去量词和添加量词,因此正确理解和运用有关量词规则是 Lp
推理理论中十分重要的关键所在 。
下面在介绍有关量词规则之前做些必要准备。作为定义 2.3.3的一种特例，将给出 A(x)对 y
是自由的这个概念。其目的是，允许用 y代入 x
后得到 A(y)，它不改变原来公式 A(x)的约束关系。
定义 2.7.1 在谓词公式 A(x)中，若 x不自由出现在量词 (?y)或 (?y)的辖域,则称 A(x)对于 y
是自由的。
由定义可知，若 y在 A(x)中不是约束出现，
则 A(x)对于 y一定是自由的。
１,有关量词消去和产生规则量词消去规则：
(1) 全称量词消去规则 (简称 UI或 US规则 )
有两种形式,(?x)A(x)?A(c)
其中 c为任意个体常元
(?x)A(x)?A(y)
A(x)对 y是自由的
(2) 存在量词消去规则 (简称 EI或 ES规则 )
有两种形式,(?x)A(x)?A(c) 其中 c为特定个体常元
(?x)A(x)?A(y)
成立充分条件是,① c或 y不得在前提中或者居先推导公式中出现或自由出现； ② 若 A(x)
中有其它自由变元时,不能应用本规则 。
值得注意的是,A(y)只是新引入的暂时假设,它不是对 y的一切值都是成立的 。 y是一个暂时的,表面上的自由变元 。
量词产生规则：
(3) 存在量词产生规则 (简称 EG规则 )
有两种形式,A(c)?(?y)A(y)
其中 c为特定个体常元
A(x)?(?y)A(y)
成立充分条件：①取代 c的个体变元 y不在
A(c)中出现；② A(x)对 y 是自由的；③若 A(x)是推导行中的公式，且 x是由使用 EI引入的，那么不能用 A(x)中除 x外的个体变元作约束变元，或者说,y不得为 A(x)中的个体变元。
(4) 全称量词产生规则 (简称 UG规则 )
A(x)?(?y)A(y)
成立条件,① 前提 A(x)对于 x的任意取值都成立； ② A(x)对 y是自由的； ③ 对于由于使用 EI
规则所得到的公式中原约束变元及与其在同一个原子公式的自由变元,都不能使用本规则而成为指导变元,否则将产生错误推理 。
２,Lp中推理实例
Lp的推理方法是 Ls推理方法的扩展，因此在 Lp中利用的推理规则也是 T规则,P规则和 CP
规则，还有已知的等价式，蕴涵式以及有关量词的消去和产生规则。使用的推理方法是直接构造法和间接证法。
例 2.7.7 试证明下面苏格拉底论证：
所有人都是要死的，
苏格拉底是人，
因此，苏格拉底是要死的。
证明 令 M(x):x是人,D(x):x是要死的,s:
苏格拉底，原题可符号化为：
(?x)(M(x)?D(x)),M(s)?D(s)
推证如下：
{1} （ 1） (?x)(M(x)?D(x)) P
{1} （ 2） M(s)?D(s) UI，（ 1）
{3} （ 3） M(s) P
{1,3} （ 4） D(s) T,(2),(3),I
