第二章 谓词逻辑
? § 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) ? P??x(A(x) ? P)
(Q7) ?xA(x) ? P??x(A(x) ? P)
E28(Q9) ?xA(x) ? P??x(A(x) ? P)
(Q8) ?xA(x) ? P? ?x(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)?B? ?x(A(x)?B)
E31 (Q15) ?xA(x)?B? ?x(A(x)?B)
E32(Q16) A??xB(x)? ?x(A?B (x))
E33 (Q17) A??x 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) ?B ? ??x(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) ??x? ?y?zP(x,y,z)
??x?y??zP(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) ? P??x(A(x) ? P)
(Q7) ?xA(x) ? P??x(A(x) ? P)
E28(Q9) ?xA(x) ? P??x(A(x) ? P)
(Q8) ?xA(x) ? P? ?x(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)?B? ?x(A(x)?B)
E31 (Q15) ?xA(x)?B? ?x(A(x)?B)
E32(Q16) A??xB(x)? ?x(A?B (x))
E33 (Q17) A??x 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) ?B ? ??x(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) ??x? ?y?zP(x,y,z)
??x?y??zP(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)
