第二章 谓词逻辑
§ 1 谓词的概念与表示法
§ 2 命题函数与量词
§ 3 谓词公式与翻译
§ 4 变元的约束
§ 5 谓词演算的等价式与蕴含式
§ 6 前束范式
§ 7 谓词演算的推理理论
§ 1 谓词的概念与表示法在研究命题逻辑中，
原子命题是命题演算中最基本的单位，不再对原子命题进行分解，
这样会产生二大缺点：
（ 1）不能研究命题的结构，成分和内部逻辑的特征；
（ 2）也不可能表达二个原子命题所具有的共同特征，甚至在命题逻辑中无法处理一些简单又常见的推理过程。
例：苏格拉底论证是正确的，但不能用命题逻辑的推理规则推导出来。
“所有的人总是要死的。 A
“苏格拉底是人。 B
“所以苏格拉底是要死的。” C
§ 1 谓词的概念与表示法
1.谓词：
,定义,,用以刻划客体的性质或关系的即是 谓词 。
我们可把陈述句分解为二部分：
主语（名词，代词）和谓语（动词）。
例：张华是学生，李明是学生。则可把它表示成：
H:表示“是学生”,j:表示“张华”,m:表示“李明”，
则可用下列符号表示上述二个命题,H(j),H(m)。
H作为“谓词”（或者谓词字母）用大写英文字母表示，
j,m为主语，称为“客体”或称“个体”。
§ 1 谓词的概念与表示法
（ 1）谓词填式,谓词字母后填以客体所得的式子。
例,H(a,b)
（ 2） 若谓词字母联系着一个客体，则称作 一元谓词 ；若谓词字母联系着二个客体，则称作 二元谓词 ；若谓词字母联系着 n个客体，则称作 n元谓词 。
（ 3） 客体的次序必须是有规定的。
例：河南省 北接 河北省。
n L b
写成二元谓词为,L(n,b)，但不能写成 L(b,n) 。
§ 2 命题函数与量词
1,命题函数客体在谓词表达式中可以是任意的名词。
例,C—“总是要死的。”
j：张三； t：老虎； e：桌子。
则 C(j),C(t),C(e)均表达了命题。
在上面的例子中,C：表示“总是要死的”； x：表示变元
（客体变元），则 C(x)表示,x总是要死的”，则称 C(x)
为命题函数。
,定义,由一个谓词字母和一个非空的客体变元的集合所组成的表达式，称为简单命题函数。
§ 2 命题函数与量词讨论定义：
（ a）当简单命题函数仅有一个客体变元时，称为一元简单命题函数；
（ b）若用任何客体去取代客体变元之后，则命题函数就变为命题；
（ c）命题函数中客体变元的取值范围称为个体域（论述域）。
例,P(x)表示 x是质数。这是一个命题函数。
其值取决于个体域。
可以将命题函数?命题，有两种方法：
§ 2 命题函数与量词
a)将 x取定一个值。如,P(4),P(5)
b)将谓词量化。如,?xP(x),?xP(x)
个体域的给定形式有二种：
①具体给定。
如：｛ j,e,t｝
②全总个体域?任意域：所有的个体从该域中取得。
§ 2 命题函数与量词
2.量词
（ 1） 全称量词
,?”为全称量词符号，读作“对于所有的”，“对任一个”，“对一切”。
例：“这里所有的都 是苹果,
可写成,?xA(x)或 (?x)A(x)
几种形式的读法：
·?xP(x)：,对所有的 x,x是 …” ；
·?x?P(x),,对所有 x,x不是 …” ；
·xP(x),,并不是对所有的 x,x是 …” ；
·x?P(x),,并不是所有的 x,x不是 …” 。
§ 2 命题函数与量词例：将“对于所有的 x和任何的 y，如果 x高于 y，那么 y不高于 x”写成命题表达形式。
解,?x?y(G(x,y) G(y,x))
G(x,y),x高于 y
（ 2） 存在量词
,?”为存在量词符号，读作“存在一个”，“对于一些”，“对于某些”，“至少存在一个”，“这里存在着这样的”等等。
,?”表达式的读法：
·? x A(x),存在一个 x,使 x是 … ；
·? x?A(x),存在一个 x,使 x不是 … ；
· x A(x),不存在一个 x,使 x是 … ；
· x?A(x),不存在一个 x,使 x不是 … 。
§ 2 命题函数与量词例：（ a）存在一个人；
（ b）某个人很聪明； （ c）某些实数是有理数将（ a）,（ b）,（ c）写成命题。
解：规定,M(x),x是人； C(x),x是很聪明；
R1(x),x是实数 (特性谓词 )
R2(x),x是有理数。
则 （ a）? x M(x) ；
（ b）? x (M(x)?C(x))；
（ c）? x (R1(x)? R2(x)) 。
（ 3） 量化命题的真值：决定于给定的个体域给定个体域,{a1…a n}以 {a1…a n}中的每一个代入
xP(x)?P(a1)?…? P(an)
xQ(x)?Q(a1)?…? Q(an)
§ 3谓词公式与翻译
1.谓词公式原子谓词公式：不出现命题联结词和量词的谓词命名式称为原子谓词公式，并用 P(x1…x n)来表示。（ P称为 n元谓词,x1…x n称为客体变元），当 n=0时称为零元谓词公式。
,定义,（谓词公式的归纳法定义）
⑴原子谓词公式是谓词公式；
⑵若 A是谓词公式，则?A也是谓词公式；
⑶若 A,B都是谓词公式，则 (A?B),(A?B),(A?B),(A?B)都是谓词公式；
⑷若 A是谓词公式,x是任何变元，则?xA,?xA也都是谓词公式；
§ 3谓词公式与翻译
⑸ 只有按⑴ -⑷ 所求得的那些公式才是谓词公式（谓词公式又简称“公式”）。
例 1：任何整数或是正的，或是负的。
解：设,I(x),x是整数； R1(x),x是正数； R2(x),x是负数。
此句可写成,?x(I(x)?(R1(x)? R2(x) )。
例 2：试将苏格拉底论证符号化：“所有的人总是要死的。
因为苏格拉底是人，所以苏格拉底是要死的。”
解：设 M(x),x是人； D(x),x是要死的；
M(s)：苏格拉底是人； D(s)：苏格拉底是要死的。
§ 3谓词公式与翻译写成符号形式：
x(M(x)? D(x)),M(s)? D(s)
2.由于对个体描述性质的刻划深度不同，可翻译成不同形式的谓词公式。
§ 4变元的约束
1.辖域：紧接在量词后面括号内的谓词公式。
例,?xP(x),?x(P(x)?Q(x)) 。
若量词后括号内为原子谓词公式，则括号可以省去。
2.自由变元与约束变元约束变元：在量词的辖域内，且与量词下标相同的变元。
自由变元：当且仅当不受量词的约束。
例,?xP(x,y),?x(P(x)y(P(x,y)) 。
§ 4变元的约束
3.约束变元的改名规则任何谓词公式对约束变元可以改名。
我们认为?xP(x,y)和?zP(z,y)是一等价的谓词公式，但是需注意，不能用同一变元去表示同一谓词公式中的二个变元。
例如,?yP(y,y)是不正确的。
下面介绍约束变元的改名规则：
（ a）在改名中要把公式中所有相同的约束变元全部同时改掉；
（ b）改名时所用的变元符号在量词辖域内未出现的。
§ 4变元的约束例,?xP(x)yR(x,y)可改写成?xP(x)zR(x,z),但不能改成?xP(x)xR(x,x),?xR(x,x)中前面的 x原为自由变元，现在变为约束变元了。
4.区别是命题还是命题函数的方法
（ a）若在谓词公式中出现有自由变元，则该公式为命题函数；
（ b）若在谓词公式中的变元均为约束出现，则该公式为命题。
例,?xP(x,y,z)是二元谓词，
y?xP(x,y,z)是一元谓词，
而谓词公式中如果没有自由变元出现，则该公式是一个命题。
§ 4变元的约束举例：
例 1：“没有不犯错的人。”
解：设 F(x)为,x犯错误”,M(x)为,x是人”（特性谓词）。
可把此命题写成,?(?x(M(x)? F(x)))
x(M(x)?F(x))
例 2：,x是 y的外祖父”?,x是 z的父亲且 z是 y的母亲”
设 P(z),z是人； F(x,z),x是 z的父亲； M(z,y),z是 y的母亲。
则谓词公式可写成,?z(P(z)? F(x,z)? M(z,y)) 。
5.代入规则,对公式中的自由变元的更改叫做代入。
(a)对公式中出现该自由变元的每一处进行代入，
(b)用以代入的变元与原公式中所有变元的名称不能相同。
§ 4变元的约束
6.个体域（论述域，客体域）,用特定的集合表示的被约束变元的取值范围。
(1)个体域不同，则表示同一命题的谓词公式的形式不同。
例：“所有的人必死。”令 D(x),x是要死的。
下面给出不同的个体域来讨论：
(ⅰ )个体域为,{人类 }，
则可写成?xD(x)；
(ⅱ )个体域为任意域（全总个体域），则人必须首先从任意域中分离出来，
设 M(x),x是人，称 M(x)为特性谓词。
命题可写成
x(M(x)? D(x))
§ 4变元的约束
（ 2） 个体域不同，则表示同一命题的值不同。 Q(x),x<5
{-1,0,3} {-3,6,2} {15,30}
xQ(x) T F F
xQ(x) T T F
（ 3） 对于同一个体域，用不同的量词时，特性谓词加入的方法不同。
对于全称量词，其特性谓词以前件的方式加入；
对于存在量词，其特性谓词以与的形式加入。
§ 4变元的约束例：设个体域为,
{白虎（白猫），黄咪（黄猫）,?,?}，
同时令 C(x),x是猫（特性谓词）； B(x),x是黑色的； A(x),x是动物。
（ ⅰ ）描述命题：“所有的猫都是动物”。
即,?x(C(x)? A(x))（ T）（真命题）
写成?x(C(x)? A(x)) （ F）则为假命题了。
∵?x(C(x)? A(x))?T?T?T?T?T
x(C(x)? A(x))?T?T? F? F?F
（ ⅱ ）描述命题：“一些猫是黑色的” 。
x(C(x)? B(x))?F?F? F? F?F
而?x(C(x)? B(x))?F? F? T? T?T
§ 4变元的约束
7.量词对变元的约束，往往与量词的次序有关。
例：
y?x(x<y-2))表示任何 y均有 x，使得 x<y-2。
§ 5谓词演算的等价式与蕴含式基本定义
,定义,A,B为二个谓词公式,E为它们共同个体域，若对
A和 B的任一组变元进行赋值，使得 A和 B的值相同，则称
A和 B遍及 E是互为等价的，记为 A?B或
A
E
B
,定义,给定谓词公式 A,E是 A的个体域。若给 A中客体变元指派 E中的每一个客体名称所得命题的值均为真，则称 A在 E中是永真的。若 E为任意域则称 A是永真的。
§ 5谓词演算的等价式与蕴含式
,定义,给定谓词公式 A,E是 A的个体域。若给 A中客体变元指派 E中每一个客体名称，在 E中存在一些客体名称，
使得指派后的真值为,T”，则 A称是可满足的。
,定义,若给 A中客体变元指派个体域中任一客体名称，使命题的值均为,F”，则称 A是永假的。
1.不含量词的谓词公式的永真式,
只要用原子谓词公式去代命题公式的永真式中的原子命题变元,则在第一章中永真蕴含式和等价公式均可变成谓词演算中的永真式：
§ 5谓词演算的等价式与蕴含式命题逻辑 谓词逻辑
Ｐ?ＰＰ (x)?Ｐ (x)
Ｐ ∨ Ｐ?Ｐ Ｐ (x)∨ Ｐ (x)?Ｐ (x)
.,
.,
Ｐ → ＱＱ →?Ｐ Ｐ (x)→ Ｑ (x)Ｑ (x)→?Ｐ (x)
Ｐ?Ｐ ∨ Ｑ Ｐ (x)?Ｐ (x)∨ Ｑ (x)
Ｐ ΛＱ? Ｐ Ｐ (x)ΛＱ (x)? Ｐ (x)
.,
.,
.,
§ 5谓词演算的等价式与蕴含式
2.含有量词的等价式和永真蕴含式设个体域为,S={a1,a2,…a n}，我们有：
xA(x)?A(a1)? A(a2)?…? A(an)
xA(x)?A(a1)?A(a2)? …? A(an)
上例说明：
若个体域是有限的，则可省掉量词。
若个体域是无限的，则可将上述概念推广从而省去量词，不过要注意这是由无限项组成的命题。
§ 5谓词演算的等价式与蕴含式例：设个体域为,N={0,1,2…},
P(x)表示,x>3,则可写出：
xP(x)?P(0)? P(1)?…? P(i)?…
xP(x)?P(0)?P(1)?…? P(i)?…
下面分类介绍在谓词公式中含有量词的等价式和永真蕴含式。
（ 1） 量词转换律：
E25(Q3)xP(x)x?P(x)
E26(Q4)xP(x)x?P(x)
下面证明：设个体域为,S={a1,a2,…a n}
§ 5谓词演算的等价式与蕴含式
xP(x)( P(a1)? P(a2)? …? P(an))
P(a1)P (a2)?…P (an)x?P(x)
下面举例说明量化命题和非量化命题的差别,否定形式不同例,否定下列命题：
(a)上海是一个小城镇 A(s)
(b)每一个自然数都是偶数?x(N(x)?E(x))
上述二命题的否定为：
(a)上海不是一个小城镇?A(s)
(b)有一些自然数不是偶数
x(N(x)?E(x))x?(N(x)?E(x))
x?(N(x)?E(x))x (N(x)E(x))
§ 5谓词演算的等价式与蕴含式结论：对于非量化命题的否定只需将动词否定，而对于量化命题的否定不但对动词进行否定而且对量词同时进行否定，其方法是,?x的否定变为?x,?x的否定变为
x 。
（ 2） 量词辖域的扩张及其收缩律
E27(Q6)?xA(x)? Px(A(x)? P)
(Q7)?xA(x)? Px(A(x)? P)
E28(Q9)?xA(x)? Px(A(x)? P)
(Q8)?xA(x)? Px(A(x)? P)
P为不含有变元Ｘ的任何谓词公式
§ 5谓词演算的等价式与蕴含式证明 E27(Q6)，设个体域为,S={a1,a2,…a n}
xA(x)? P?(A(a1)? A(a2)?…? A(an))? P
(A(a1)?P)?(A(a2)?P)?…?(A(an)?P )
x(A(x)? P)
E30 (Q14)?xA(x)?Bx(A(x)?B)
E31 (Q15)?xA(x)?Bx(A(x)?B)
E32(Q16) AxB(x)x(A?B (x))
E33 (Q17) Ax B(x)x(A?B (x))
证明 E30 (Q14),设个体域为,S={a1,a2,…a n}
x(A(x)?B)? (A(a1)?B)?…? (A(an)?B)
(?A(a1)? B)?…? (?A(an)? B)
§ 5谓词演算的等价式与蕴含式
(?A(a1)?…A(an))?B
x?A(x)?Bx(A(x)?B)
xA(x)?B
（ 3） 量词分配律
E24(Q10)?x(A(x)?B(x))xA(x)xB(x)
E23 (Q11)?x (A(x)?B(x))xA(x)xB(x)
I18(Q12)?x (A(x)? B(x))xA(x)xB(x)
I17(Q13)?xA(x)xB(x)x(A(x)? B(x))
E29(Q18)?x (A(x)? B(x))xA(x)xB(x)
I19(Q19)?xA(x)xB(x)x(A(x)? B(x))
§ 5谓词演算的等价式与蕴含式证明 E24(Q10)和 I19(Q19)，设个体域为,S={a1,a2,…a n}
E24(Q10)?x(A(x)?B(x))
(A(a1)?B(a1))?…,? (A(an)?B(an))
(A(a1)?…? A(an))? (B(a1)?…? B(an))
xA(x)x B(x)
I19(Q19)?xA(x)xB(x)
xA(x)xB(x)x?A(x)xB(x)
(?A(a1)?…A(an))? (B(a1)?…? B(an))
(?A(a1)? B(a1))?…? (?A(a1)? B(an))
…
…
(?A(an)? B(a1))?…? (?A(an)? B(an))
§ 5谓词演算的等价式与蕴含式
(?A(a1)? B(a1))?…?(?A(an)? B(an))
x(?A(x)?B(x))
x(A(x)?B(x))
（ 4） 量词的添加和除去的永真蕴含式
Q1?xP(x)?P(y)
Q2 P(y)xP(x)
Q5?xP(x)xP(x)
xP?P?xP?P (P为不含 x变元）
Y是ｘ个体域中任一元素
§ 5谓词演算的等价式与蕴含式
（ 5） 含有多个量词的永真式：
（ ⅰ ）量词出现的次序直接关系到命题的含义：
,?x?y”表示：“无论选定一个什么样的 x值总能找到一个 y能使 x和 y…”
“?y?x”表示：“只选取一个 y值，以致无论怎样选定一个 x，
能够使 y和 x…”
下面列出对应的表达式可以看出其不同处：
设 x的个体域为,{a1,a2,…a n},
y的个体域为,{b1,b2,…b n},
则,?x?yP(x,y)yP(a1,y)?…yP(an,y)
§ 5谓词演算的等价式与蕴含式
(P(a1,b1)? …? P(a1,bn))?…?
(P(an,b1)?…? P(an,bn))
y?xP(x,y)
xP(x,b1)?…xP(x,bn)
(P(a1,b1)?…? P(an,b1))?…?
(P(a1,bn)?…? P(an,bn))
例,x,y的个体域 {鞋子 },P(x,y):Ｘ和Ｙ配成一双鞋子。
x?yP(x,y)?T
y?xP(x,y)?F
§ 5谓词演算的等价式与蕴含式
（ ⅱ ）在含有多个量词的谓词公式中,
x?y,?x?y的位置是可以改变的,且不影响命题的真值。
例,x,y的个体域为 N={0,1,2…},则
x?yP(x,y)yP(0,y)?…yP(i,y)?…
(P(0,0)? P(0,1)?… P(0,j)?…)
…?
(P(i,0)? P(i,1)?… P(i,j)?…)?…
(P(0,0)? P(1,0)?…? P(i,0)?…)
(P(0,1)? P(1,1)?…? P(i,1)?…)
…
xP(x,0)xP(x,1)?…xP(x,j)?…
y?xP(x,y)
§ 5谓词演算的等价式与蕴含式同样,?x?yP(x,y)y?xP(x,y)
（ ⅲ ）量词转换律的推广应用,把?深入到谓词公式前面去的方法。
x?y?zP(x,y,z)xy?zP(x,y,z)
x?yzP(x,y,z)
x?y?z?P(x,y,z)
（ ⅳ ）两个量词?,?所组成的谓词公式的等价式和永真蕴含式（ 8个）
x?yP(x,y)y?xP(x,y)
x?yP(x,y)y?xP(x,y)
y?xP(x,y)x?yP(x,y)
y?xP(x,y)x?yP(x,y)
§ 5谓词演算的等价式与蕴含式
x?yP(x,y)y?xP(x,y)
x?yP(x,y)y?xP(x,y)
y?xP(x,y)x?yP(x,y)
x?yP(x,y)y?xP(x,y)
（ 6） 谓词公式的对偶式
,定义,在一个谓词公式 A中（其中不出现?,?词）把公式 A中?,?,F,T,?,?,变为公式 A*中?,?,T,F,?,?,
则称 A*是 A的对偶式。
,定理,若谓词公式 A? B，则 A*? B* ；若谓词公式 A
B,则 B*?A* （ 这里 A,B有同样的个体域）。
§ 5谓词演算的等价式与蕴含式例：
I17(Q13)?xA(x)xB(x)x(A(x)?B(x))
I18(Q12)?xA(x)xB(x)x(A(x)? B(x))
§ 6 前束范式
,定义,一个公式，如果量词均非否定地在全式的开头，它们的作用域延伸到整个公式的末尾，则称此公式叫前束范式。
例,?x?y?z(? Q(x,y)? R(z)) (前束范式 )
,定理,任何一个谓词公式均和一个前束范式等价。
证明：①利用量词转换把?深入到原子谓词公式前,
② 利用约束变元的改名规则，
③利用量词辖域的扩张收缩律,把量词移到全式的最前面，这样一定可得到等价的前束范式。
§ 6 前束范式例：
xP(x)? R(x)yP(y)? R(x)
y(P(y)? R(x))
例：把?xP(x)xQ(x) 变成前束范式。
xP(x)xQ(x)xP(x)xQ(x)
x?P(x)xQ(x)
x(?P(x)?Q(x))
§ 7谓词演算的推理理论
1.含有量词的特殊永真式
,定义,设 A(x)是一个谓词公式,x是其中的自由变元，若把 y代入到 A(x)里而不会产生变元的新的约束出现，则称
A(x)对于 y是自由的。
例：下面 A(x)对于 y是自由的：
① A(x)zP(z)?Q(x,z),这里 x为自由变元,若用 y去取代
A(x)中的 x,
A(y)zP(z)?Q(y,z),这里 y也仍为自由变元；
§ 7 谓词演算的推理理论
② 下面 A(x)对于 y不是自由的：
A(x)y(S(x)?S(y)),x为自由变元，
若用 y代入 A(x)的 x中去得：
A(y)y(S(y)?S(y)),y变为约束变元了，产生了新的约束出现。
如有必要代入 y，则应先将式中的约束变元 y改名。
z(S(x)?S(z))然后代入 y
z(S(y)?S(z))y仍为自由变元。
归结,判定 A(x)对于 y是自由的，只要看公式 A(x)中?y,?y的辖域内有没有 x的自由出现就行：若有 x的自由出现则 A(x)
对于 y不是自由的，若无的 x自由出现则一定可以肯定 A(x)
对于 y是自由的。
§ 7 谓词演算的推理理论下面分别介绍四个推理规则
（ 1） 全称指定规则（ US规则）。
如果对个体域中所有客体 x,A(x)成立，则对个体域中某个任意客体 c,A(c) 成立。该规则表示成：
xA(x)?A(c) (x,c?个体域 )
（ 2） 全称推广规则（ UG规则）
如果能够证明对个体域中每一个客体 c，命题 A(c) 都成立，
则可得到结论?xA(x) 成立。该规则表示成：
A(x)xA(x)
§ 7 谓词演算的推理理论
（ 3） 存在指定规则（ ES规则）
如果对于个体域中某些客体 A(x)成立，则必有某个特定的客体 c，使 A(c)成立。该规则表示成：
xA(x)?A(c)
例,x的个体域为 I={整数 },P(x):x是偶数,Q(x),x是奇数。
xP(x)xQ(x)?T 但
P(c)?Q(c)?F
§ 7 谓词演算的推理理论
（ 4） 存在推广规则（ EG规则）
如果对个体域中某个特定客体 c，有 A(c) 成立，则在个体域中，必存在 x，使 A(x)成立。该规则表示成：
A(c)xA(x)
2 推论规则及使用说明命题逻辑中的 P,T,CP规则和简接证明法，都可以引用到谓词逻辑的推论规则中来，不过要注意对量词做适当处理，
其方法是：用 US,ES在推导中去掉量词，用 UG,EG使结论量化。
§ 7谓词演算的推理理论规则使用说明：
（ 1） 在使用 ES,US时一定要是前束范式
（ 2） 推导中连续使用 US规则可用相同变元
xP(x)?P(y),?xQ(x)?Q(y),
（ 3） 推导中既 ES用，又用 US,则必须先用 ES,后用
US方可取相同变元，反之不行。
xP(x)?P(y)
xQ(x)?Q(y)
（ 4） 推导中连续使用 ES规则时，使用一次更改一个变元。
§ 7谓词演算的推理理论例：证明苏格拉底论证
x(M(x)?D(x))?M(s)? D(s)
(1) M(s) P
(2)?x(M(x)?D(x)) P
(3) M(s)?D(s) US
(4) D(s) T
例：证,?x(H(x)?M(x)),?xH(x)xM(x)
§ 7谓词演算的推理理论
(1)?xH(x) P
(2) H(c) ES
(3)?x(H(x)?M(x)) P
(4) H(c)?M(c) US
(5) M(c) T
(6)?xM(x) EG
例：证,?x (P(x)?Q(x))x P(x)xQ(x)
(1)?x P(x) 引入前件
(2)?x (P(x)?Q(x)) P
(3)P(c)?Q(c) ES
§ 7谓词演算的推理理论
(4) P(c) US
(5) Q(c) T
(6)?xQ(x) EG
(7)?x P(x)xQ(x) CP
例：证明：
x(P(x)?Q(x)),?xP(x)xQ(x)
(1)xQ(x) 假设前提
(2)?xQ(x) T
(3) Q(c) US
(4)?xP(x) P
§ 7谓词演算的推理理论
(5) P(c) US
(6) P(c)?Q(c) T
(7)?x(P(x)?Q(x)) UG
(8)x(P(x)?Q(x)) P
(9)?x(P(x)?Q(x))x(P(x)?Q(x)) T
(10) F
例：下列结论能否从前提中推出：
x (P(x)?Q(x)),?Q(a)x? P(x)
a为 x个体域中一个元素
(1)?Q(a) P
(2)?x (P(x)?Q(x)) P
§ 7谓词演算的推理理论
(3) P(a)?Q(a) US
(4)?P(a) T
(5)?x? P(x) UG
在使用 US,ES,UG,EG这四条规则时,要注意严格按照它们的规定去使用。
§ 7谓词演算的推理理论书中例 4证明：
(1)?x(?y(S(x,y)?M(y))z(P(z)?R(x,z)) P
(2)?y(S(b,y)?M(y))z(P(z)?R(b,z)) US(1)
(3)?(?z)P(z) 附加前提
(4)?z(?P(z)) T(3)
(5)?P(a) US(4)
(6)?P(a)R(b,a) T(5)
(7)?(P(a)?R(b,a)) T(6)
(8)?z?(P(z)?R(b,z)) UG(7)
(9)z(P(z)?R(b,z)) T(8)
§ 7谓词演算的推理理论
(10)y(S(b,y)?M(y)) T(2)(9)
(11)?y?(S(b,y)?M(y)) T(10)
(12)?(S(b,c)?M(c)) US(11)
(13)?S(b,c)M(c) T(12)
(14) S(b,c)M(c) T(13)
(15)?y(S(b,y)M(y)) UG(14)
(16)?x?y(S(x,y)M(y)) UG(15)
(17)?(?z)P(z)x?y(S(x,y)M(y)) CP(3)(16)
§ 7谓词演算的推理理论例,二个量词的推理比较复杂：
xP(x)x(P(x)?Q(x)?R(x)),?xP(x),?xQ(x)
x?y(R(x)?R(y))
(1)?xP(x) P
(2) P(w) ES
(3) P(w)?Q(w) T
(4)?xP(x)x(P(x)?Q(x)?R(x)) P
(5)?x(P(x)?Q(x)?R(x)) T
§ 7谓词演算的推理理论
(6) P(w)?Q(w)?R(w) US
(7) R(w) T
(8)?xR(x) EG
(9)?xQ(x) P
(10) Q(z) ES
(11) P(z)?Q(z) T
(12) P(z)?Q(z)?R(z) US
§ 7谓词演算的推理理论
(13) R(z) T
(14)?yR(y) EG
(15)?xR(x)yR(y) T
(16)?x?y(R(x)?R(y)) T
三个量词的推理过程更为复杂第二章小结学习第二章要注意以下几点：
(1)同一个命题在不同个体域内可能有不同的符号化形式，同时也可能有不同的真值，因而在将一个命题符号化之前，
必须弄清个体域。
(2)在将命题符号化时，要特别注意量词与联结词的搭配。经常的情况是全称量词?与蕴含词?搭配，存在量词?与合取词?搭配。因此有下面两种形式的公式：
x(A(x)?B(x)) ①
x(A(x)? B(x)) ②
而?x(A(x)? B(x)) ③
x(A(x)? B(x)) ④
第二章小结
③ 与①，④与②的含义完全不同。
(3)记住主要的等价式。会用约束变元和自由变元换名规则进行等价演算，求出给定公式的前束范式。
(4)在谓词演算的推理证明中，要特别注意 US,UG,ES,EG
规则成立的条件。
例题选讲例 1.符号化下列命题：
(1)没有不犯错误的人；
(2)发光的不都是金子；
(3)在南京高校学习的学生，未必都是南京籍的学生。
解：
(1)设 M(x),x是人。 Q(x),x犯错误。
本题符号化为,?x(M(x)?Q(x))
或者,?(?x)(M(x)Q(x))
(2)设 L(x),x是发光的东西。 G(x),x是金子。
x(L(x)G(x)) 或x(L(x)?G(x))
例题选讲
(3)设 S(x),x是南京高校学习的学生。
F(x),x是南京籍的学生。
则?x(S(x)F(x))
本题也可加深刻划,S(x),x是学生。 L(x),x在学习。
H(x),x在南京高校。
G(x),x是南京籍的人。
则?(?x)(S(x)?L(x)?H(x)?G(x)?S(x))
例题选讲例 2.写出?x(F(x)?G(x))?(?xF(x)xG(x))的前束范式。
解：原式x(?F(x)?G(x))?(?(?x)F(x)? (?x)G(x))
(?x)(?F(x)?G(x))?(?(?x)F(x)? (?x)G(x))
(?x)((F(x) G(x))?G(x))? (?x)?F(x)
(?x)((F(x)?G(x))? (?x)?F(x)
(?x)((F(x)?G(x))? (?y)?F(y)
(?x) (?y) (F(x)?G(x)F(y))
作业
P8 1,5
P11 1,5
P18 4(c),6,7(a),(b)
P23 1,2,6,8(c),(d)
P29 2,3
P39 1,2(b),3(b),4(c),(f),5(b)
P46 1(a),(b),2(a),4(a)
P59 1(d)(g)(h),2(d)(i)(l)
P62 1(f)(g),5
作业
P65 1(c),2(c),4
P72 6,7
P75 1(b)(c)
P79 1(a)(d),2(a),3(b)
§ 1 谓词的概念与表示法
§ 2 命题函数与量词
§ 3 谓词公式与翻译
§ 4 变元的约束
§ 5 谓词演算的等价式与蕴含式
§ 6 前束范式
§ 7 谓词演算的推理理论
§ 1 谓词的概念与表示法在研究命题逻辑中，
原子命题是命题演算中最基本的单位，不再对原子命题进行分解，
这样会产生二大缺点：
（ 1）不能研究命题的结构，成分和内部逻辑的特征；
（ 2）也不可能表达二个原子命题所具有的共同特征，甚至在命题逻辑中无法处理一些简单又常见的推理过程。
例：苏格拉底论证是正确的，但不能用命题逻辑的推理规则推导出来。
“所有的人总是要死的。 A
“苏格拉底是人。 B
“所以苏格拉底是要死的。” C
§ 1 谓词的概念与表示法
1.谓词：
,定义,,用以刻划客体的性质或关系的即是 谓词 。
我们可把陈述句分解为二部分：
主语（名词，代词）和谓语（动词）。
例：张华是学生，李明是学生。则可把它表示成：
H:表示“是学生”,j:表示“张华”,m:表示“李明”，
则可用下列符号表示上述二个命题,H(j),H(m)。
H作为“谓词”（或者谓词字母）用大写英文字母表示，
j,m为主语，称为“客体”或称“个体”。
§ 1 谓词的概念与表示法
（ 1）谓词填式,谓词字母后填以客体所得的式子。
例,H(a,b)
（ 2） 若谓词字母联系着一个客体，则称作 一元谓词 ；若谓词字母联系着二个客体，则称作 二元谓词 ；若谓词字母联系着 n个客体，则称作 n元谓词 。
（ 3） 客体的次序必须是有规定的。
例：河南省 北接 河北省。
n L b
写成二元谓词为,L(n,b)，但不能写成 L(b,n) 。
§ 2 命题函数与量词
1,命题函数客体在谓词表达式中可以是任意的名词。
例,C—“总是要死的。”
j：张三； t：老虎； e：桌子。
则 C(j),C(t),C(e)均表达了命题。
在上面的例子中,C：表示“总是要死的”； x：表示变元
（客体变元），则 C(x)表示,x总是要死的”，则称 C(x)
为命题函数。
,定义,由一个谓词字母和一个非空的客体变元的集合所组成的表达式，称为简单命题函数。
§ 2 命题函数与量词讨论定义：
（ a）当简单命题函数仅有一个客体变元时，称为一元简单命题函数；
（ b）若用任何客体去取代客体变元之后，则命题函数就变为命题；
（ c）命题函数中客体变元的取值范围称为个体域（论述域）。
例,P(x)表示 x是质数。这是一个命题函数。
其值取决于个体域。
可以将命题函数?命题，有两种方法：
§ 2 命题函数与量词
a)将 x取定一个值。如,P(4),P(5)
b)将谓词量化。如,?xP(x),?xP(x)
个体域的给定形式有二种：
①具体给定。
如：｛ j,e,t｝
②全总个体域?任意域：所有的个体从该域中取得。
§ 2 命题函数与量词
2.量词
（ 1） 全称量词
,?”为全称量词符号，读作“对于所有的”，“对任一个”，“对一切”。
例：“这里所有的都 是苹果,
可写成,?xA(x)或 (?x)A(x)
几种形式的读法：
·?xP(x)：,对所有的 x,x是 …” ；
·?x?P(x),,对所有 x,x不是 …” ；
·xP(x),,并不是对所有的 x,x是 …” ；
·x?P(x),,并不是所有的 x,x不是 …” 。
§ 2 命题函数与量词例：将“对于所有的 x和任何的 y，如果 x高于 y，那么 y不高于 x”写成命题表达形式。
解,?x?y(G(x,y) G(y,x))
G(x,y),x高于 y
（ 2） 存在量词
,?”为存在量词符号，读作“存在一个”，“对于一些”，“对于某些”，“至少存在一个”，“这里存在着这样的”等等。
,?”表达式的读法：
·? x A(x),存在一个 x,使 x是 … ；
·? x?A(x),存在一个 x,使 x不是 … ；
· x A(x),不存在一个 x,使 x是 … ；
· x?A(x),不存在一个 x,使 x不是 … 。
§ 2 命题函数与量词例：（ a）存在一个人；
（ b）某个人很聪明； （ c）某些实数是有理数将（ a）,（ b）,（ c）写成命题。
解：规定,M(x),x是人； C(x),x是很聪明；
R1(x),x是实数 (特性谓词 )
R2(x),x是有理数。
则 （ a）? x M(x) ；
（ b）? x (M(x)?C(x))；
（ c）? x (R1(x)? R2(x)) 。
（ 3） 量化命题的真值：决定于给定的个体域给定个体域,{a1…a n}以 {a1…a n}中的每一个代入
xP(x)?P(a1)?…? P(an)
xQ(x)?Q(a1)?…? Q(an)
§ 3谓词公式与翻译
1.谓词公式原子谓词公式：不出现命题联结词和量词的谓词命名式称为原子谓词公式，并用 P(x1…x n)来表示。（ P称为 n元谓词,x1…x n称为客体变元），当 n=0时称为零元谓词公式。
,定义,（谓词公式的归纳法定义）
⑴原子谓词公式是谓词公式；
⑵若 A是谓词公式，则?A也是谓词公式；
⑶若 A,B都是谓词公式，则 (A?B),(A?B),(A?B),(A?B)都是谓词公式；
⑷若 A是谓词公式,x是任何变元，则?xA,?xA也都是谓词公式；
§ 3谓词公式与翻译
⑸ 只有按⑴ -⑷ 所求得的那些公式才是谓词公式（谓词公式又简称“公式”）。
例 1：任何整数或是正的，或是负的。
解：设,I(x),x是整数； R1(x),x是正数； R2(x),x是负数。
此句可写成,?x(I(x)?(R1(x)? R2(x) )。
例 2：试将苏格拉底论证符号化：“所有的人总是要死的。
因为苏格拉底是人，所以苏格拉底是要死的。”
解：设 M(x),x是人； D(x),x是要死的；
M(s)：苏格拉底是人； D(s)：苏格拉底是要死的。
§ 3谓词公式与翻译写成符号形式：
x(M(x)? D(x)),M(s)? D(s)
2.由于对个体描述性质的刻划深度不同，可翻译成不同形式的谓词公式。
§ 4变元的约束
1.辖域：紧接在量词后面括号内的谓词公式。
例,?xP(x),?x(P(x)?Q(x)) 。
若量词后括号内为原子谓词公式，则括号可以省去。
2.自由变元与约束变元约束变元：在量词的辖域内，且与量词下标相同的变元。
自由变元：当且仅当不受量词的约束。
例,?xP(x,y),?x(P(x)y(P(x,y)) 。
§ 4变元的约束
3.约束变元的改名规则任何谓词公式对约束变元可以改名。
我们认为?xP(x,y)和?zP(z,y)是一等价的谓词公式，但是需注意，不能用同一变元去表示同一谓词公式中的二个变元。
例如,?yP(y,y)是不正确的。
下面介绍约束变元的改名规则：
（ a）在改名中要把公式中所有相同的约束变元全部同时改掉；
（ b）改名时所用的变元符号在量词辖域内未出现的。
§ 4变元的约束例,?xP(x)yR(x,y)可改写成?xP(x)zR(x,z),但不能改成?xP(x)xR(x,x),?xR(x,x)中前面的 x原为自由变元，现在变为约束变元了。
4.区别是命题还是命题函数的方法
（ a）若在谓词公式中出现有自由变元，则该公式为命题函数；
（ b）若在谓词公式中的变元均为约束出现，则该公式为命题。
例,?xP(x,y,z)是二元谓词，
y?xP(x,y,z)是一元谓词，
而谓词公式中如果没有自由变元出现，则该公式是一个命题。
§ 4变元的约束举例：
例 1：“没有不犯错的人。”
解：设 F(x)为,x犯错误”,M(x)为,x是人”（特性谓词）。
可把此命题写成,?(?x(M(x)? F(x)))
x(M(x)?F(x))
例 2：,x是 y的外祖父”?,x是 z的父亲且 z是 y的母亲”
设 P(z),z是人； F(x,z),x是 z的父亲； M(z,y),z是 y的母亲。
则谓词公式可写成,?z(P(z)? F(x,z)? M(z,y)) 。
5.代入规则,对公式中的自由变元的更改叫做代入。
(a)对公式中出现该自由变元的每一处进行代入，
(b)用以代入的变元与原公式中所有变元的名称不能相同。
§ 4变元的约束
6.个体域（论述域，客体域）,用特定的集合表示的被约束变元的取值范围。
(1)个体域不同，则表示同一命题的谓词公式的形式不同。
例：“所有的人必死。”令 D(x),x是要死的。
下面给出不同的个体域来讨论：
(ⅰ )个体域为,{人类 }，
则可写成?xD(x)；
(ⅱ )个体域为任意域（全总个体域），则人必须首先从任意域中分离出来，
设 M(x),x是人，称 M(x)为特性谓词。
命题可写成
x(M(x)? D(x))
§ 4变元的约束
（ 2） 个体域不同，则表示同一命题的值不同。 Q(x),x<5
{-1,0,3} {-3,6,2} {15,30}
xQ(x) T F F
xQ(x) T T F
（ 3） 对于同一个体域，用不同的量词时，特性谓词加入的方法不同。
对于全称量词，其特性谓词以前件的方式加入；
对于存在量词，其特性谓词以与的形式加入。
§ 4变元的约束例：设个体域为,
{白虎（白猫），黄咪（黄猫）,?,?}，
同时令 C(x),x是猫（特性谓词）； B(x),x是黑色的； A(x),x是动物。
（ ⅰ ）描述命题：“所有的猫都是动物”。
即,?x(C(x)? A(x))（ T）（真命题）
写成?x(C(x)? A(x)) （ F）则为假命题了。
∵?x(C(x)? A(x))?T?T?T?T?T
x(C(x)? A(x))?T?T? F? F?F
（ ⅱ ）描述命题：“一些猫是黑色的” 。
x(C(x)? B(x))?F?F? F? F?F
而?x(C(x)? B(x))?F? F? T? T?T
§ 4变元的约束
7.量词对变元的约束，往往与量词的次序有关。
例：
y?x(x<y-2))表示任何 y均有 x，使得 x<y-2。
§ 5谓词演算的等价式与蕴含式基本定义
,定义,A,B为二个谓词公式,E为它们共同个体域，若对
A和 B的任一组变元进行赋值，使得 A和 B的值相同，则称
A和 B遍及 E是互为等价的，记为 A?B或
A
E
B
,定义,给定谓词公式 A,E是 A的个体域。若给 A中客体变元指派 E中的每一个客体名称所得命题的值均为真，则称 A在 E中是永真的。若 E为任意域则称 A是永真的。
§ 5谓词演算的等价式与蕴含式
,定义,给定谓词公式 A,E是 A的个体域。若给 A中客体变元指派 E中每一个客体名称，在 E中存在一些客体名称，
使得指派后的真值为,T”，则 A称是可满足的。
,定义,若给 A中客体变元指派个体域中任一客体名称，使命题的值均为,F”，则称 A是永假的。
1.不含量词的谓词公式的永真式,
只要用原子谓词公式去代命题公式的永真式中的原子命题变元,则在第一章中永真蕴含式和等价公式均可变成谓词演算中的永真式：
§ 5谓词演算的等价式与蕴含式命题逻辑 谓词逻辑
Ｐ?ＰＰ (x)?Ｐ (x)
Ｐ ∨ Ｐ?Ｐ Ｐ (x)∨ Ｐ (x)?Ｐ (x)
.,
.,
Ｐ → ＱＱ →?Ｐ Ｐ (x)→ Ｑ (x)Ｑ (x)→?Ｐ (x)
Ｐ?Ｐ ∨ Ｑ Ｐ (x)?Ｐ (x)∨ Ｑ (x)
Ｐ ΛＱ? Ｐ Ｐ (x)ΛＱ (x)? Ｐ (x)
.,
.,
.,
§ 5谓词演算的等价式与蕴含式
2.含有量词的等价式和永真蕴含式设个体域为,S={a1,a2,…a n}，我们有：
xA(x)?A(a1)? A(a2)?…? A(an)
xA(x)?A(a1)?A(a2)? …? A(an)
上例说明：
若个体域是有限的，则可省掉量词。
若个体域是无限的，则可将上述概念推广从而省去量词，不过要注意这是由无限项组成的命题。
§ 5谓词演算的等价式与蕴含式例：设个体域为,N={0,1,2…},
P(x)表示,x>3,则可写出：
xP(x)?P(0)? P(1)?…? P(i)?…
xP(x)?P(0)?P(1)?…? P(i)?…
下面分类介绍在谓词公式中含有量词的等价式和永真蕴含式。
（ 1） 量词转换律：
E25(Q3)xP(x)x?P(x)
E26(Q4)xP(x)x?P(x)
下面证明：设个体域为,S={a1,a2,…a n}
§ 5谓词演算的等价式与蕴含式
xP(x)( P(a1)? P(a2)? …? P(an))
P(a1)P (a2)?…P (an)x?P(x)
下面举例说明量化命题和非量化命题的差别,否定形式不同例,否定下列命题：
(a)上海是一个小城镇 A(s)
(b)每一个自然数都是偶数?x(N(x)?E(x))
上述二命题的否定为：
(a)上海不是一个小城镇?A(s)
(b)有一些自然数不是偶数
x(N(x)?E(x))x?(N(x)?E(x))
x?(N(x)?E(x))x (N(x)E(x))
§ 5谓词演算的等价式与蕴含式结论：对于非量化命题的否定只需将动词否定，而对于量化命题的否定不但对动词进行否定而且对量词同时进行否定，其方法是,?x的否定变为?x,?x的否定变为
x 。
（ 2） 量词辖域的扩张及其收缩律
E27(Q6)?xA(x)? Px(A(x)? P)
(Q7)?xA(x)? Px(A(x)? P)
E28(Q9)?xA(x)? Px(A(x)? P)
(Q8)?xA(x)? Px(A(x)? P)
P为不含有变元Ｘ的任何谓词公式
§ 5谓词演算的等价式与蕴含式证明 E27(Q6)，设个体域为,S={a1,a2,…a n}
xA(x)? P?(A(a1)? A(a2)?…? A(an))? P
(A(a1)?P)?(A(a2)?P)?…?(A(an)?P )
x(A(x)? P)
E30 (Q14)?xA(x)?Bx(A(x)?B)
E31 (Q15)?xA(x)?Bx(A(x)?B)
E32(Q16) AxB(x)x(A?B (x))
E33 (Q17) Ax B(x)x(A?B (x))
证明 E30 (Q14),设个体域为,S={a1,a2,…a n}
x(A(x)?B)? (A(a1)?B)?…? (A(an)?B)
(?A(a1)? B)?…? (?A(an)? B)
§ 5谓词演算的等价式与蕴含式
(?A(a1)?…A(an))?B
x?A(x)?Bx(A(x)?B)
xA(x)?B
（ 3） 量词分配律
E24(Q10)?x(A(x)?B(x))xA(x)xB(x)
E23 (Q11)?x (A(x)?B(x))xA(x)xB(x)
I18(Q12)?x (A(x)? B(x))xA(x)xB(x)
I17(Q13)?xA(x)xB(x)x(A(x)? B(x))
E29(Q18)?x (A(x)? B(x))xA(x)xB(x)
I19(Q19)?xA(x)xB(x)x(A(x)? B(x))
§ 5谓词演算的等价式与蕴含式证明 E24(Q10)和 I19(Q19)，设个体域为,S={a1,a2,…a n}
E24(Q10)?x(A(x)?B(x))
(A(a1)?B(a1))?…,? (A(an)?B(an))
(A(a1)?…? A(an))? (B(a1)?…? B(an))
xA(x)x B(x)
I19(Q19)?xA(x)xB(x)
xA(x)xB(x)x?A(x)xB(x)
(?A(a1)?…A(an))? (B(a1)?…? B(an))
(?A(a1)? B(a1))?…? (?A(a1)? B(an))
…
…
(?A(an)? B(a1))?…? (?A(an)? B(an))
§ 5谓词演算的等价式与蕴含式
(?A(a1)? B(a1))?…?(?A(an)? B(an))
x(?A(x)?B(x))
x(A(x)?B(x))
（ 4） 量词的添加和除去的永真蕴含式
Q1?xP(x)?P(y)
Q2 P(y)xP(x)
Q5?xP(x)xP(x)
xP?P?xP?P (P为不含 x变元）
Y是ｘ个体域中任一元素
§ 5谓词演算的等价式与蕴含式
（ 5） 含有多个量词的永真式：
（ ⅰ ）量词出现的次序直接关系到命题的含义：
,?x?y”表示：“无论选定一个什么样的 x值总能找到一个 y能使 x和 y…”
“?y?x”表示：“只选取一个 y值，以致无论怎样选定一个 x，
能够使 y和 x…”
下面列出对应的表达式可以看出其不同处：
设 x的个体域为,{a1,a2,…a n},
y的个体域为,{b1,b2,…b n},
则,?x?yP(x,y)yP(a1,y)?…yP(an,y)
§ 5谓词演算的等价式与蕴含式
(P(a1,b1)? …? P(a1,bn))?…?
(P(an,b1)?…? P(an,bn))
y?xP(x,y)
xP(x,b1)?…xP(x,bn)
(P(a1,b1)?…? P(an,b1))?…?
(P(a1,bn)?…? P(an,bn))
例,x,y的个体域 {鞋子 },P(x,y):Ｘ和Ｙ配成一双鞋子。
x?yP(x,y)?T
y?xP(x,y)?F
§ 5谓词演算的等价式与蕴含式
（ ⅱ ）在含有多个量词的谓词公式中,
x?y,?x?y的位置是可以改变的,且不影响命题的真值。
例,x,y的个体域为 N={0,1,2…},则
x?yP(x,y)yP(0,y)?…yP(i,y)?…
(P(0,0)? P(0,1)?… P(0,j)?…)
…?
(P(i,0)? P(i,1)?… P(i,j)?…)?…
(P(0,0)? P(1,0)?…? P(i,0)?…)
(P(0,1)? P(1,1)?…? P(i,1)?…)
…
xP(x,0)xP(x,1)?…xP(x,j)?…
y?xP(x,y)
§ 5谓词演算的等价式与蕴含式同样,?x?yP(x,y)y?xP(x,y)
（ ⅲ ）量词转换律的推广应用,把?深入到谓词公式前面去的方法。
x?y?zP(x,y,z)xy?zP(x,y,z)
x?yzP(x,y,z)
x?y?z?P(x,y,z)
（ ⅳ ）两个量词?,?所组成的谓词公式的等价式和永真蕴含式（ 8个）
x?yP(x,y)y?xP(x,y)
x?yP(x,y)y?xP(x,y)
y?xP(x,y)x?yP(x,y)
y?xP(x,y)x?yP(x,y)
§ 5谓词演算的等价式与蕴含式
x?yP(x,y)y?xP(x,y)
x?yP(x,y)y?xP(x,y)
y?xP(x,y)x?yP(x,y)
x?yP(x,y)y?xP(x,y)
（ 6） 谓词公式的对偶式
,定义,在一个谓词公式 A中（其中不出现?,?词）把公式 A中?,?,F,T,?,?,变为公式 A*中?,?,T,F,?,?,
则称 A*是 A的对偶式。
,定理,若谓词公式 A? B，则 A*? B* ；若谓词公式 A
B,则 B*?A* （ 这里 A,B有同样的个体域）。
§ 5谓词演算的等价式与蕴含式例：
I17(Q13)?xA(x)xB(x)x(A(x)?B(x))
I18(Q12)?xA(x)xB(x)x(A(x)? B(x))
§ 6 前束范式
,定义,一个公式，如果量词均非否定地在全式的开头，它们的作用域延伸到整个公式的末尾，则称此公式叫前束范式。
例,?x?y?z(? Q(x,y)? R(z)) (前束范式 )
,定理,任何一个谓词公式均和一个前束范式等价。
证明：①利用量词转换把?深入到原子谓词公式前,
② 利用约束变元的改名规则，
③利用量词辖域的扩张收缩律,把量词移到全式的最前面，这样一定可得到等价的前束范式。
§ 6 前束范式例：
xP(x)? R(x)yP(y)? R(x)
y(P(y)? R(x))
例：把?xP(x)xQ(x) 变成前束范式。
xP(x)xQ(x)xP(x)xQ(x)
x?P(x)xQ(x)
x(?P(x)?Q(x))
§ 7谓词演算的推理理论
1.含有量词的特殊永真式
,定义,设 A(x)是一个谓词公式,x是其中的自由变元，若把 y代入到 A(x)里而不会产生变元的新的约束出现，则称
A(x)对于 y是自由的。
例：下面 A(x)对于 y是自由的：
① A(x)zP(z)?Q(x,z),这里 x为自由变元,若用 y去取代
A(x)中的 x,
A(y)zP(z)?Q(y,z),这里 y也仍为自由变元；
§ 7 谓词演算的推理理论
② 下面 A(x)对于 y不是自由的：
A(x)y(S(x)?S(y)),x为自由变元，
若用 y代入 A(x)的 x中去得：
A(y)y(S(y)?S(y)),y变为约束变元了，产生了新的约束出现。
如有必要代入 y，则应先将式中的约束变元 y改名。
z(S(x)?S(z))然后代入 y
z(S(y)?S(z))y仍为自由变元。
归结,判定 A(x)对于 y是自由的，只要看公式 A(x)中?y,?y的辖域内有没有 x的自由出现就行：若有 x的自由出现则 A(x)
对于 y不是自由的，若无的 x自由出现则一定可以肯定 A(x)
对于 y是自由的。
§ 7 谓词演算的推理理论下面分别介绍四个推理规则
（ 1） 全称指定规则（ US规则）。
如果对个体域中所有客体 x,A(x)成立，则对个体域中某个任意客体 c,A(c) 成立。该规则表示成：
xA(x)?A(c) (x,c?个体域 )
（ 2） 全称推广规则（ UG规则）
如果能够证明对个体域中每一个客体 c，命题 A(c) 都成立，
则可得到结论?xA(x) 成立。该规则表示成：
A(x)xA(x)
§ 7 谓词演算的推理理论
（ 3） 存在指定规则（ ES规则）
如果对于个体域中某些客体 A(x)成立，则必有某个特定的客体 c，使 A(c)成立。该规则表示成：
xA(x)?A(c)
例,x的个体域为 I={整数 },P(x):x是偶数,Q(x),x是奇数。
xP(x)xQ(x)?T 但
P(c)?Q(c)?F
§ 7 谓词演算的推理理论
（ 4） 存在推广规则（ EG规则）
如果对个体域中某个特定客体 c，有 A(c) 成立，则在个体域中，必存在 x，使 A(x)成立。该规则表示成：
A(c)xA(x)
2 推论规则及使用说明命题逻辑中的 P,T,CP规则和简接证明法，都可以引用到谓词逻辑的推论规则中来，不过要注意对量词做适当处理，
其方法是：用 US,ES在推导中去掉量词，用 UG,EG使结论量化。
§ 7谓词演算的推理理论规则使用说明：
（ 1） 在使用 ES,US时一定要是前束范式
（ 2） 推导中连续使用 US规则可用相同变元
xP(x)?P(y),?xQ(x)?Q(y),
（ 3） 推导中既 ES用，又用 US,则必须先用 ES,后用
US方可取相同变元，反之不行。
xP(x)?P(y)
xQ(x)?Q(y)
（ 4） 推导中连续使用 ES规则时，使用一次更改一个变元。
§ 7谓词演算的推理理论例：证明苏格拉底论证
x(M(x)?D(x))?M(s)? D(s)
(1) M(s) P
(2)?x(M(x)?D(x)) P
(3) M(s)?D(s) US
(4) D(s) T
例：证,?x(H(x)?M(x)),?xH(x)xM(x)
§ 7谓词演算的推理理论
(1)?xH(x) P
(2) H(c) ES
(3)?x(H(x)?M(x)) P
(4) H(c)?M(c) US
(5) M(c) T
(6)?xM(x) EG
例：证,?x (P(x)?Q(x))x P(x)xQ(x)
(1)?x P(x) 引入前件
(2)?x (P(x)?Q(x)) P
(3)P(c)?Q(c) ES
§ 7谓词演算的推理理论
(4) P(c) US
(5) Q(c) T
(6)?xQ(x) EG
(7)?x P(x)xQ(x) CP
例：证明：
x(P(x)?Q(x)),?xP(x)xQ(x)
(1)xQ(x) 假设前提
(2)?xQ(x) T
(3) Q(c) US
(4)?xP(x) P
§ 7谓词演算的推理理论
(5) P(c) US
(6) P(c)?Q(c) T
(7)?x(P(x)?Q(x)) UG
(8)x(P(x)?Q(x)) P
(9)?x(P(x)?Q(x))x(P(x)?Q(x)) T
(10) F
例：下列结论能否从前提中推出：
x (P(x)?Q(x)),?Q(a)x? P(x)
a为 x个体域中一个元素
(1)?Q(a) P
(2)?x (P(x)?Q(x)) P
§ 7谓词演算的推理理论
(3) P(a)?Q(a) US
(4)?P(a) T
(5)?x? P(x) UG
在使用 US,ES,UG,EG这四条规则时,要注意严格按照它们的规定去使用。
§ 7谓词演算的推理理论书中例 4证明：
(1)?x(?y(S(x,y)?M(y))z(P(z)?R(x,z)) P
(2)?y(S(b,y)?M(y))z(P(z)?R(b,z)) US(1)
(3)?(?z)P(z) 附加前提
(4)?z(?P(z)) T(3)
(5)?P(a) US(4)
(6)?P(a)R(b,a) T(5)
(7)?(P(a)?R(b,a)) T(6)
(8)?z?(P(z)?R(b,z)) UG(7)
(9)z(P(z)?R(b,z)) T(8)
§ 7谓词演算的推理理论
(10)y(S(b,y)?M(y)) T(2)(9)
(11)?y?(S(b,y)?M(y)) T(10)
(12)?(S(b,c)?M(c)) US(11)
(13)?S(b,c)M(c) T(12)
(14) S(b,c)M(c) T(13)
(15)?y(S(b,y)M(y)) UG(14)
(16)?x?y(S(x,y)M(y)) UG(15)
(17)?(?z)P(z)x?y(S(x,y)M(y)) CP(3)(16)
§ 7谓词演算的推理理论例,二个量词的推理比较复杂：
xP(x)x(P(x)?Q(x)?R(x)),?xP(x),?xQ(x)
x?y(R(x)?R(y))
(1)?xP(x) P
(2) P(w) ES
(3) P(w)?Q(w) T
(4)?xP(x)x(P(x)?Q(x)?R(x)) P
(5)?x(P(x)?Q(x)?R(x)) T
§ 7谓词演算的推理理论
(6) P(w)?Q(w)?R(w) US
(7) R(w) T
(8)?xR(x) EG
(9)?xQ(x) P
(10) Q(z) ES
(11) P(z)?Q(z) T
(12) P(z)?Q(z)?R(z) US
§ 7谓词演算的推理理论
(13) R(z) T
(14)?yR(y) EG
(15)?xR(x)yR(y) T
(16)?x?y(R(x)?R(y)) T
三个量词的推理过程更为复杂第二章小结学习第二章要注意以下几点：
(1)同一个命题在不同个体域内可能有不同的符号化形式，同时也可能有不同的真值，因而在将一个命题符号化之前，
必须弄清个体域。
(2)在将命题符号化时，要特别注意量词与联结词的搭配。经常的情况是全称量词?与蕴含词?搭配，存在量词?与合取词?搭配。因此有下面两种形式的公式：
x(A(x)?B(x)) ①
x(A(x)? B(x)) ②
而?x(A(x)? B(x)) ③
x(A(x)? B(x)) ④
第二章小结
③ 与①，④与②的含义完全不同。
(3)记住主要的等价式。会用约束变元和自由变元换名规则进行等价演算，求出给定公式的前束范式。
(4)在谓词演算的推理证明中，要特别注意 US,UG,ES,EG
规则成立的条件。
例题选讲例 1.符号化下列命题：
(1)没有不犯错误的人；
(2)发光的不都是金子；
(3)在南京高校学习的学生，未必都是南京籍的学生。
解：
(1)设 M(x),x是人。 Q(x),x犯错误。
本题符号化为,?x(M(x)?Q(x))
或者,?(?x)(M(x)Q(x))
(2)设 L(x),x是发光的东西。 G(x),x是金子。
x(L(x)G(x)) 或x(L(x)?G(x))
例题选讲
(3)设 S(x),x是南京高校学习的学生。
F(x),x是南京籍的学生。
则?x(S(x)F(x))
本题也可加深刻划,S(x),x是学生。 L(x),x在学习。
H(x),x在南京高校。
G(x),x是南京籍的人。
则?(?x)(S(x)?L(x)?H(x)?G(x)?S(x))
例题选讲例 2.写出?x(F(x)?G(x))?(?xF(x)xG(x))的前束范式。
解：原式x(?F(x)?G(x))?(?(?x)F(x)? (?x)G(x))
(?x)(?F(x)?G(x))?(?(?x)F(x)? (?x)G(x))
(?x)((F(x) G(x))?G(x))? (?x)?F(x)
(?x)((F(x)?G(x))? (?x)?F(x)
(?x)((F(x)?G(x))? (?y)?F(y)
(?x) (?y) (F(x)?G(x)F(y))
作业
P8 1,5
P11 1,5
P18 4(c),6,7(a),(b)
P23 1,2,6,8(c),(d)
P29 2,3
P39 1,2(b),3(b),4(c),(f),5(b)
P46 1(a),(b),2(a),4(a)
P59 1(d)(g)(h),2(d)(i)(l)
P62 1(f)(g),5
作业
P65 1(c),2(c),4
P72 6,7
P75 1(b)(c)
P79 1(a)(d),2(a),3(b)
