第二章 谓词逻辑
问题的提出, (即命题逻辑的局限性 )
在第一章,一个原子命题只用一个字母表示，
而不再对命题中的句子成分细分。这样有一些逻
辑问题无法解决。请看下面的例子。
例 1.令Ｐ：小张是大学生。
Ｑ：小李是大学生。
从符号Ｐ、Ｑ中 不能归纳出他们都是大学生的共
性 。我们希望从所使用的符号那里带给我们更多
的信息，比如可以看出他们的共性。这种想法在
第一章是无法实现的。
例 2.令 Ａ：所有自然数都是整数。
Ｂ：８是自然数。
Ｃ：８是整数。
这是著名的三段论推理,A是大前提,B是小前提，
C是结论。显然，由Ａ和Ｂ可以推出结论Ｃ。这
个推理是有效的，但是 这个推理在第一章也是无
法实现的 。
分析,命题Ｐ与Ｑ中的谓语是相同的 (是大学生 ),
只是主语不同。命题Ａ、Ｂ、Ｃ之间在主语谓语
方面也是有联系的，靠这种联系才能由Ａ、Ｂ推
出Ｃ。而从这三个符号上看不出此种联系。
所以就要 另外考虑表示命题的方法 。
解决这个问题的方法,
在表示命题时，既表示出主语，也表示出谓语，
就可以解决上述问题。这就提出了 谓词 的概念。
令 S(x)表示 x是大学生,a:小张,b:小李
命题 P表示成 S(a):小张是大学生。
命题 Q表示成 S(b):小李是大学生。
从符号 S(a),S(b)可看出小张和小李都是大学生的共性,
令 N(x):x是自然数。 I(x):x是整数。
?表示所有的。
A,?x(N(x)→I(x))
B,N(8)
C,I(8)
N(8)→I(8)
N(8)
? I(8)
符号 S(x),N(x),I(x)就是所谓的谓词 。
推理如此实现：
2-1 基本概念
2-1.1 客体与客体变元
? 定义,能够独立存在的事物，称之为 客体,也
称之为 个体 。它可以是具体的，也可以是抽象的
事物。通常用小写英文字母 a,b,c,...表示。
例如，小张、小李,8,a、沈阳、社会主义等等
都是客体。
? 定义,用小写英文字母 x,y,z...表示任何客
体，则称这些字母为 客体变元 。
? 注意：客体变元本身不是客体 。
2-1.2 谓词
? 定义,一个大写英文字母后边有括号，括号内
是若干个客体变元，用以表示客体的属性或者
客体之间的关系，称之为 谓词 。如果括号内有
n个客体变元，称该谓词为 n元谓词 。
? 例如
S(x):表示 x是大学生。 一元谓词
G(x,y)：表示 x>y。 二元谓词
B(x,y,z)：表示 x在 y与 z之间。三元谓词
一般地
P(x1,x2,…,xn) 是 n元谓词。
2-1.3 命题函数
? 谓词本身并不是命题，只有谓词的括号内填入
足够的客体，才变成命题 。
? 例如，
a表示小张,b表示小李，则
S(a):小张是大学生。
S(b):小李是大学生。
Ｇ (7,3)表示,７ >３。
如果 c表示锦州,d表示沈阳,e表示山海关，则
B(c,d,e)表示：锦州在沈阳与山海关之间。
这时 S(a),S(b),G(7,3),B(c,d,e)才是命题。
令谓词 S(x):x是大学生，括号内填入不同的人名，
就得到不同的 命题,故谓词 S(x)相当于一个函数，
称之为 命题函数 。
定义, n元谓词 P(x1,x2,…,xn)称之为 简单命题函数 。
规定,当命题函数 P(x1,x2,…,xn)中 n=0 时，即 0
元谓词，表示不含有客体变元的谓词，它本身就是
一个 命题变元 。
定义,将若干个简单命题函数用逻辑联结词联结起
来，构成的表达式，称之为 复合命题函数 。简单命
题函数与复合命题函数统称为 命题函数 。
? 例如
? 给定简单命题函数：
A(x),x身体好，
B(x),x学习好，
C(x),x工作好，
? 复合命题函数 ?A(x)→( ?B(x)∧ ?C(x))
表示如果 x身体不好，则 x的学习与工作
都不会好。
2-1.4 论域 (个体域 )
? 定义,在 命题函数 中客体变元的取值范
围，称之为 论域,也称之为 个体域 。
例如 S(x):x是大学生，论域是,人类。
G(x,y),x>y,论域是,实数。
论域是一个集合。
? 定义,由所有客体构成的论域，称之为
全总个体域 。它是个, 最大, 的论域。
? 约定,对于一个命题函数，如果没有给定
论域，则 假定该论域是全总个体域 。
2-1.5 量词
? 例如：有些人是大学生。
所有事物都是发展变化的。
,有些,,“所有的,,就是对客体量化的词。
? 定义,在命题中表示对客体数量化的词，称之
为 量词 。
? 定义了两种量词：
(1).存在量词,记作 ?，表示, 有些,,, 一
些,,
,某些,,, 至少一个, 等。
(2).全称量词,记作 ?，表示, 每个,,, 任
何
一个,,, 一切,,, 所有的,,“凡是”、
“任意
? 定义,量词后边要有一个客体变元，指明对哪
个客体变元量化，称此客体变元是 量词后的指
导变元 。
例如 ?x(读作, 任意 x”),?x(读作, 存在 x”)，
其中的 x就是量词后的指导变元。
例题１,所有的自然数都是整数。
设 N(x),x是自然数。 I(x),x是整数。此命
题可以写成 ?x(N(x)→I(x))
例题２,有些自然数是偶数。
设 E(x),x是偶数。
此命题可以写成 ?x(N(x)∧E(x))
? 例题 3,每个人都有一个生母。
设 P(x):x是个人。 M(x,y):y是 x的生母。
此命题可以写成
?x(P(x)→ ?y(P(y)∧M(x,y)))
2-2 谓词公式及命题符号化
命题逻辑中有命题公式，类似地，在谓词逻辑
中，要研究谓词公式。
2-2.1 客体函数
有些命题中，可能有若干个客体，其中有些客体
之间有函数关系，例如
例题 1,如果 x是奇数，则 2x是偶数。
其中客体 x与客体 2x之间就有函数关系，可以设
客体函数 g(x)=2x，
谓词 O(x),x是奇数,E(x),x是偶数，
则此命题可以表示为,?x(O(x)→E(g(x)))
? 例题 2 小王的父亲是个医生。
设函数 f(x)=x的父亲，谓词 D(x):x是个医
生,a:小王，此命题可以表示为 D(f(a)).
? 例题 3 如果 x和 y都是奇数，则 x+y是偶数。
设 h(x,y)=x+y,此命题可以表示为,
?x?y((O(x)∧O(y))→E(h(x,y))
? 像上述的 g(x),f(x),h(x,y)就是客体函
数，一般地用小写的英文字母 f,g,h…,表
示客体函数。
? 注意,客体函数与谓词是不同的，不可混
淆,
要注意区分客体函数与谓词间的区别：
? 设例题 1的论域是自然数集合 N。
? 客体函数中的客体变元用客体带入后的结果依
然 是个客体 (3∈N,g(3)=6,所以 g(3)∈N) 。
? 谓词中的客体变元用确定的客体带入后就 变成
了命题,其真值为Ｔ或者为Ｆ (3∈N,O( ３ )是
个命题,真值为 T)。
? 把它们都看成, 映射, 的话，则
客体函数是论域到论域的映射, g:N→N,如果
指定的客体 a∈N,则 g(a)∈N 。
而谓词是从论域到 {T,F}的映射,即谓词 E(x)可
以看成映射 E:N→{T,F},如果指定客体 a∈N,则
E(a)的真值 ∈ {T,F}。
2-2.2 原子谓词公式
? 定义,称 n元谓词 P(x1,x2,...,xn)为原子
谓词公式。
? 例如 P,Q(x), A(x,f(x)),B(x,y,a)
都是原子谓词公式。
2-2.3 谓词合式公式 (WFF)
(Well Formed formulas)
? 定义,谓词合式公式递归定义如下：
1.原子谓词公式是合式公式。
2.如果 A是合式公式，则 ?A也是合式公式。
3.如果 A,B是合式公式，则 (A∧B), (A∨B),
(A→B), (A?B)都是合式公式。
4.如果 A是合式公式,x是Ａ中的任何客体变元，
则 ?xＡ和 ?xＡ也是合式公式。
5.只有有限次地按规则 (1)至 (4)求得的公式才
是合式公式。
? 谓词合式公式 也叫 谓词公式,简称 公式 。
? 下面都是合式公式：
P,(P→Q), (Q(x)∧P),
?x(A(x)→B(x)), ?xC(x)
? 而下面都不是合式公式：
x?y?P(x), P(?x)∧Q(x) ??x
? 为了方便，最外层括号可以省略，但是
若量词后边有括号，则此括号不能省。
? 注意,公式 ?x(A(x)→B(x) )中 ?x后边的
括号不是最外层括号，所以不可以省略。
2-2.4 量词的作用域 (辖域 )
? 定义,在谓词公式中，量词的作用范围称之为
量词的 作用域,也叫量词的 辖域 。
? 例如 ?xA(x)中 ?x的辖域为 A(x).
? ?x((P(x)∧Q(x))→ ?yR(x,y))中
?x的辖域是 ((P(x)∧Q(x))→ ?yR(x,y))
?y的辖域为 R(x,y)。
? ?x?y?z(A(x,y)→B(x,y,z))∧C(t)
?x的辖域
?z的辖域
?y的辖域
一般地，
? 如果量词后边只是一个原子谓词公式时，
该量词的辖域就是此原子谓词公式。
? 如果量词后边是括号，则此括号所表示
的区域就是该量词的辖域。
? 如果多个量词紧挨着出现，则后边的量
词及其辖域就是前边量词的辖域。
2-2.5 自由变元与约束变元
? 在谓词公式中的客体变元可以分成两种，
一种是受到量词约束的，一种是不受量词
约束的。请看下面公式：
? ?x(F(x,y)→ ?yP(y))∧Q(z)
Ｆ (x,y)中的 x在 ?x的辖域内，受到 ?x的
约束，而其中的 y不受 ?x的约束。
P(y)中的 y在 ?y的辖域内，受 ?y的约束。
Q(z)中的 z不受量词约束。
? 定义,如果客体变元 x在 ?x或者 ?x的辖域
内，则称 x在此辖域内约束出现，并称 x
在此辖域内是 约束变元 。否则 x是自由出
现，并称 x是 自由变元 。
? 上例中
?x(F(x,y)→ ?yP(y))∧Q(z)
F(x,y)中的 x和 P(y)中的 y是约束变元。
而 F(x,y)中的 y和 Q(z)中的 z是自由变元。
? 对约束变元和自由变元有如下几点 说明,
(1).对约束变元用什么符号表示无关紧要。
就是说 ?xA(x)与 ?yA(y)是一样的。这类
似于计算积分与积分变元无关，即积分
∫ f(x)dx 与 ∫ f(y)dy 相同。
(2).一个谓词公式如果无自由变元，它就
表示一个命题 。
例如 A(x)表示 x是个大学生。 ?xA(x)或
者 ?xA(x)就是个命题了，因为它们分别
表示命题, 有些人是大学生, 和, 所有
人都是大学生, 。
(3).一个 n元谓词 P(x1,x2,…,xn)，若在前边添加
k个量词，使其中的 k个客体变元变成约束变
元，则此 n元谓词就变成了 n-k元谓词。
? 例如 P(x,y,z)表示 x+y=z，假设论域是整数集。
?x?yP(x,y,z)表示, 任意给定的整数 x，都可
以找到整数 y，使得 x+y=z” 。
? 如果令 z=1，则 ?x?yP(x,y,1)就变成了命题
,任意给定的整数 x，都可以找到整数 y，使得
x+y=1”,… 。
? 可见每当给 z指定个整数 a后,?x?yP(x,y,a)就
变成了一个命题。所以谓词公式 ?x?yP(x,y,z)
就相当于只含有客体变元 z的一元谓词了。
? 在一个谓词公式中，如果某个客体变元
既以约束变元形式出现，又以自由变元
形式出现，就容易产生混淆。为了避免
此现象发生，可以对客体变元更改名称。
如 ?x(F(x,y)→ ?yP(y))∧Q(z)
? 约束变元的改名规则,
(1).对约束变元可以更改名称，改名的范
围是：量词后的指导变元以及该量词的
辖域内此客体变元出现的各处同时换名。
(2).改名后用的客体变元名称，不能与该
量词的辖域内的其它变元名称相同。
例如 ?x(P(x)→Q(x,y))∨(R(x)∧A(x))
此式中的 x 就是以两种形式出现。可以对 x改名 成
?z(P(z)→Q(z,y))∨(R(x)∧A(x))
对自由变元也可以换名字，此换名叫代入。
对 自由变元的代入规则,
(1).对谓词公式中的自由变元可以作代入。代入
时需要对公式中出现该变元的每一处，同时作
代入。
(2).代入后的变元名称要与公式中的其它变元名
称不同
上例也可以对自由变元 x作代入，改成
?x(P(x)→Q(x,y))∨(R(z)∧A(z))
2-2.6 命题的符号化
在谓词演算中，命题的符号化比较复杂,命题的
符号表达式与论域有关系 。例如
1.每个自然数都是整数。
(1).如果论域是自然数集合 N，令 I(x),x是整
数，则命题的表达式为 ?xI(x)
(2).如果论域扩大为 全总个体域 时，上述表达式
?xI(x)表示, 所有客体都是整数,,显然这是
假的命题，此表达式已经不能表达原命题了。
因此需要添加谓词 N(x),x是自然数,用于表
明 x的特性,于是命题的符号表达式为
?x(N(x)→I(x))
2.有些大学生吸烟。
(1).如果论域是大学生集合 S，令 A(x),x
吸烟，则命题的表达式为 ?xA(x)
(2).如果论域扩大为 全总个体域 时，上述
表达式 ?xA(x)表示, 有些客体吸烟,,
就不是表示此命题了，故需要添加谓词
S(x),x是大学生,用于表明 x的特性,
于是命题的表达式为 ?x(S(x)∧A(x))
? 从上述两个例子可以看出，命题的符号表达式
与论域有关。 当论域扩大时，需要添加用来表
示客体特性的谓词，称此谓词为 特性谓词 。 特
性谓词 往往就是给定命题中量词后边的那个名
词 。如上面两个例子中的, 所有 自然数,,
,有些 大学生, 。
? 如何添加特性谓词，这是个十分重要的问题,
这与前边的量词有关 。
? 特性谓词的添加方法如下：
? 如果 前边是全称量词, 特性谓词后边是蕴含联
结词, →, ； 如果 前边是存在量词, 特性谓词
后边是合取联结词, ∧, 。
? 为什么必须这样添加特性谓词？
分析一下特性谓词和原谓词所表示的概念之间
的关系，得出下面的图，从此图可以得出如此
添加特性谓词的正确性。
? 令 N:自然数集合,I:整数集合，
S:大学生集合,A:烟民的集合。
IN S A
吸烟大学生
I包含 N
?x(N(x)→I(x))
吸烟大学生是 S与 A的交集
?x(S(x)∧A(x))
3.所有大学生都喜欢一些歌星。
令 S(x),x是大学生,X(x),x是歌星，
L(x,y),x喜欢 y。 则命题的表达式为
?x(S(x)→ ?y(X(y)∧L(x,y)))
4.没有不犯错误的人。
此话就是, 没有人不犯错误,,, 没有, 就是, 不存
在, 之意。令 P(x),x是人,F(x),x犯错误，
此命题的表达式为
??x(P(x)∧ ?F(x))或者 ?x(P(x)→F(x))
5.不是所有的自然数都是偶数。
令 N(x),x是自然数,E(x),x是偶数，
命题的表达式为,
??x(N(x)→E(x)) 或者 ?x(N(x)∧ ?E(x))
?6.如果一个人只是说谎话，那么他所说的每句话没有
一句是可以相信的。
令 A(x),x是人,B(x,y),y是 x说的话，
C(x):x是谎话,D(x),x是可以相信的
命题的表达式为,
?x(A(x)→( ?y(B(x,y)→C(y))→ ??z(B(x,z)∧D(z)))
或者 ?x(A(x)→ ?y((B(x,y)∧C(y))→ ?D(y)))
? 7.每个自然数都有唯一的后继数。
令 N(x),x是自然数,A(x,y),y是 x的后继数，
E(x,y),x=y 则命题的表达式为
?x(N(x)→ ?y(N(y)∧A(x,y)∧ ?z((N(z)∧A(x,z))→E(y,z))))
有一个后继数 后继数的唯一性
下面请同学们自己做练习第 60页 (2)
练习 P60(2)
? a) ?x(J(x)→ L(x))
? b) ?x(L(x)∧ S(x))
? c) ?x(J(x)∧ O(x)∧ V(x))
? d) J(j)∧ ?O(j)∧ ?V(j)
? e) ??x(L(x)→ J(x)) 或者 ?x(L(x)∧ ?J(x))
? f) ?x(S(x)∧ L(x)∧ C(x))
? g) ??x(C(x)∧ ?V(x)) 或者 ?x(C(x)→ V(x))
? h) ?x((C(x)∧ O(x))→ L(x))
? i) ??x(W(x)∧ C(x)∧ H(x))
? j) ?x(W(x)∧ J(x)∧ C(x))
? k) ?x(L(x)→ ?y(J(y)∧ A(x,y)))
? l) ?x(S(x)∧ ?y(L(y)→ ?A(x,y)))
小结
1.命题的符号表达式形式与论域有关系。
论域扩大需要用特性谓词对客体进行说明,注意如何添
加特性谓词 (即要注意特性谓词后边是什么联结词 )。
2.如果量词前有否定符号，如“没有,..”,不是所有
的,..”等，可以按照字面直译。如, ??x…”,??x...”
3.命题的符号表达式中所有客体变元必须都是约束变元，
才表示命题。有时给定命题中有些量词没有明确给出，
要仔细分析并写出这隐含的量词。 例如
a) 金子闪光，但闪光的不一定都是金子。 G(x),F(x)
?x(G(x)→ F(x))∧ ??x(F(x) → G(x))
b) 没有大学生不懂外语。 S(x),K(x,y),F(x)
??x(S(x)∧ ?y(F(y)→ ?K(x,y)))
? 作业
? 60页 (2)
? 62页 (2),
? (3) b),c),
? (5) b)
? (6)
? 65页 (4) b)
? (5) a)
2-3谓词演算的等价式与蕴涵式
? 在命题逻辑中，我们是通过对公式的命题变元
赋值来讨论永真式、永真蕴含式及等价公式的。
? 在谓词演算中，也要讨论一些重要的谓词公式。
但是由于谓词公式中可能有命题变元、客体变
元。对命题变元赋值比较容易，因为只有两个
值可赋。而对客体变元作指派却不那么简单，
因为论域中的客体可能有无限个。另外谓词公
式的真值还与论域有关。
2-3.1 对谓词公式赋值
? 定义,若将给定的谓词公式中的命题变元，
用确定的命题代替，对公式中的客体变元
用论域中的客体代替，这个过程就称之为
对谓词公式作指派,或者称之 为 对谓词
公式赋值 。
? 例如公式 P→N(x), N(x),x是自然数，
论域为实数集合 R，
令 P,2>1,x=4 时，此公式变成 P→N(4),
它的真值就是, 真, 。
2-3.2 谓词公式的永真式 定义
? 定义,给定谓词公式 A,E是其论域，如
果不论对公式 A作任何赋值，都使得 A的
真值为真，则称公式 A在论域 E上是永真
式 。如果不论对什么论域 E，都使得公式
A为永真式，则称 A为永真式 。
例如,I(x),x是整数，论域 E为自然数
集合，公式 I(x)在 E上就是永真式。
而公式 I(x)∨ ?I(x)就是与论域无关
的永真式。
2-3.3 谓词公式的等价公式 定义
? 定义,给定谓词公式 A,B,E是它们的论域，
如果不论对公式 A,B作任何赋值，都使得 A与 B
的真值相同 (或者说 A?B是永真式 )，则称公式
A与 B在论域 E上是等价的。如果不论对什么论
域 E，都使得公式 A与 B等价，则称 A与 B等价，
记作 A?B。
? 例如,I(x)：表示 x是整数,N(x)：表示 x是自
然数，假设论域 E是自然数集合，公式 I(x)与
N(x)在 E上是等价的。
而公式 N(x)→I(x) 与 ?N(x)∨I(x) 就是与论域
无关的等价的公式，即
N(x)→I(x) ??N(x)∨I(x) 。
2-3.4 谓词公式的永真蕴含式 定义
? 定义,给定谓词公式 A,B,E是它们的论域，
如果不论对公式 A,B作任何赋值，都使得 A→B
为永真式，则称在论域 E上公式 A永真蕴含 B。
如果不论对什么论域 E，都使得公式 A→B 为永
真式，则称 A永真蕴含 B，记作 A?B。
? 例如,G(x)：表示 x大于 5,N(x)：表示 x是自
然数，论域 E={-1,-2,6,7,8,9,....}，
? 在 E上公式 G(x)→N(x) 是永真式。
? 而公式 (G(x)∧N(x))→N(x) 就是与论域无关的
永真式，所以 (G(x)∧N(x)) ?N(x)。
2-3.5,重要公式
下面讨论重要的谓词等价公式和永真蕴含式。
一,由命题公式推广出的公式
因一个不含自由变元的谓词公式本身如 ?xA(x),?xB(x)
就是命题 。一个含有 n个自由变元的谓词公式，赋予论域
中的 n个指定客体后就变成命题 (例如 S(a),G(3,1)等 )。
因此可以把此公式 看成一个命题变元 。所以在命题演算
的永真式中，将其中的同一个命题变元，用同一个谓词
公式代替，所得到的公式也是永真式。这样就可以将命
题演算中的等价公式和永真蕴含式推广到谓词演算中使
用。例如
A(x)?A(x)∨B(x) P?P∨Q
?x(A(x)→B(x)) ??x(?A(x)∨B(x)) P→Q ??P∨ Q
?(?xA(x)∧ ?xB(x))???xA(x)∨ ??xB(x) 摩根定律
二,带量词的公式在论域内的展开式
? 先看一个例子，令 A(x)：表示 x是整数,B(x)：
表示 x是奇数，设论域是 {1,2,3,4,5}，谓词公
式 ?xA(x)表示论域内所有的客体都是整数，显
然公式 ?xA(x)的真值为真，因为 A(1),A(2)、
A(3),A(4),A(5)都为真，于是有
?xA(x)?A(1)∧A(2)∧A(3)∧A(4)∧A(5)
类似地，谓词公式 ?xB(x)表示论域内有些客体
是奇数，显然公式 ?xB(x)的真值也为真，因为
B(1),B(3),B(5)的真值为真，于是有
?xB(x)?B(1)∨B(2)∨B(3)∨B(4)∨B(5)
一般地，设论域为 {a1,a2,....,an}，则
1,?xA(x)?A(a1)∧A(a 2)∧......∧A(a n)
2,?xB(x)?B(a1)∨B(a 2)∨......∨B(a n)
三,量词否定公式
? 我们还是先用一个例子说明这个问题。令
Ａ (x)表示 x是优等生，论域是某班级的学生集合。
? ??xA(x)表示：不是所有人都是优等生。
?x?A(x)表示：有些人不是优等生。
? ??xA(x)表示：没有人是优等生。
?x?A(x)表示：所有人都不是优等生。
? 从这个例子可以看出
,不是所有人都是优等生。, 与, 有些人不是
优等生。, 是等价的。
,没有人是优等生。, 与, 所有人都不是优等
生。, 是等价的。于是有：
1,??xA(x)??x?A(x)
2,??xA(x)??x?A(x)
对这两个公式可以证明如下：
证明,设论域为 {a1,a2,....,an}，则
??xA(x)??(A(a1)∧A(a 2)∧...∧A(a n))
??A(a1)∨ ?A(a2)∨...∨ ?A(an)??x?A(x)
类似可以证明另一个公式。
从这两个公式，可以总结出如下 规律,将量词前
的, ?” 移到量词的后边，或者将量词后的
,?” 移到量词的前边时，量词也随着改变，
如果原来是全称量词改成存在量词，如果原来
是存在量词改成全称量词。所以我们也把这两
个公式称为量词转换公式。
四,量词辖域的扩充公式
如果 Ｂ是个不含客体变元 x的谓词公式,且不在
?x和 ?x的辖域内，可以将Ｂ放入 ?x和 ?x的辖
域内。即得如下公式：
1,?xA(x)∨B ??x(A(x)∨B)
2,?xA(x)∧B ??x(A(x)∧B)
3,?xA(x)∨B ??x(A(x)∨B)
4,?xA(x)∧B ??x(Ａ (x)∧B)
5,B→ ?xA(x)??x(B→A(x))
6,B→ ?xA(x)??x(B→A(x))
7,?xA(x)→B ??x(A(x)→B)
8,?xA(x)→B ??x(A(x)→B)
上述公式我们只证明三个。
? 证明,设论域为 {a1,a2,....,an}，
?xA(x)∨B ?(A(a1)∧A(a 2)∧...∧A(a n))∨B
?(A(a1)∨B)∧(A(a 2)∨B)∧...∧(A(a n)∨B)
??x(Ａ (x)∨ Ｂ )
B→ ?xA(x)??B∨ ?xA(x)??x(?B∨A(x))
??x(B→A(x))
?xA(x)→B ???xA(x)∨B ??x?A(x)∨B
??x(?A(x)∨B) ??x(A(x)→B)
在使用公式 7.,8.时，要特别注意，量词的辖
域扩充后，量词发生了变化 。
五,量词分配公式
1,?x(A(x)∨B(x)) ??xA(x)∨ ?xB(x)
2,?x(A(x)∧B(x)) ??xA(x)∧ ?xB(x)
3,?x(A(x)∧B(x)) ??xA(x)∧ ?xB(x)
4,?xA(x)∨ ?xB(x)??x(A(x)∨B(x))
证明,设论域为 {a1,a2,....,an}，
?x(A(x)∨B(x))
?(A(a1)∨B(a 1))∨(A(a 2)∨B(a 2))∨ …
∨(A(a n)∨B(a n))
?(A(a1)∨A(a 2)∨...∨A(a n))∨
(B(a1)∨B(a 2)∨...∨B(a n))
??xA(x)∨ ?xB(x)
? 注意 公式 3.和 4.不是等价公式，而是永
真蕴含式。
例如公式 3.由 ?xA(x)∧ ?xB(x)不能推出
?x(A(x)∧B(x)),
? 我们可以举一个反例，设 A(x)和 B(x)分别
表示, x是奇数, 和, x是偶数,,显然命
题 ?xA(x)∧ ?xB(x)为真。而
?x(A(x)∧B(x)) 是表示命题, 存在一些数
既是奇数，也是偶数,,显然不为真。
所以说由 ?xA(x)∧ ?xB(x)不能推出
?x(A(x)∧B(x)).
? 证明公式 3.
?x(A(x)∧B(x)) ??xA(x)∧ ?xB(x)
? 证明,假设前件 ?x(A(x)∧B(x)) 为真，
则论域中至少有一个客体 a，使得
A(a)∧B(a) 为真，于是 A(a)和 B(a)都为
真，所以有 ?xA(x)以及 ?xB(x)为真，进
而得 ?xA(x)∧ ?xB(x)为真。于是有
?x(A(x)∧B(x)) ??xA(x)∧ ?xB(x)
下面利用公式 3.证明公式 4.。
证明,因为公式 3.中的 A(x)和 B(x)是任意
的谓词公式，不妨用 ?A(x)和 ?B(x)分别
代替公式 3.中的 A(x)和 B(x)得
?x(?A(x)∧ ?B(x))??x?A(x)∧ ?x?B(x)
?x?(A(x)∨B(x)) ???xA(x)∧ ??xB(x)
??x(A(x)∨B(x)) ??(?xA(x)∨ ?xB(x))
应用公式 P→ Q??Q→ ?P 得
?xA(x)∨ ?xB(x)??x(A(x)∨B(x))
公式 4.得证。
在使用公式 4.的时候,特别要注意蕴含式
的方向，不要搞错。
六．其它公式
1,?x(A(x)→B(x)) ??xA(x)→ ?xB(x)
2,?xA(x)→ ?xB(x)??x(A(x)→ B(x))
证明 1,?xA(x)→ ?xB(x)
???xA(x)∨ ?xB(x)
??x?A(x)∨ ?xB(x)
??x(?A(x)∨ B(x))
??x(A(x)→ B(x))
证明 2,?xA(x)→ ?xB(x)
???xA(x)∨ ?xB(x)
??x?A(x)∨ ?xB(x) ??x(?A(x)∨ B(x))
??x(A(x)→ B(x))
七．两个量词的公式
? 在 A(x,y)前有两个量词，如果两个量词
是相同的，它们的次序是无关紧要，但
是如果是不同的，它们的次序就不可以
随便交换。例如设
? A(x,y)表示, x+y=0”,论域为：实数集合，
? ?x?yA(x,y)表示, 对于任意给定的一个
实数 x,可以找到一个 y,使得 x+y=0”,这是
一个为, 真, 的命题。而交换量词后
? ?y?xA(x,y) 表示, 存在一个实数 y,与任
意给定的一个实数 x之和都等于 0”,这是
一个为, 假, 的命题。
有如下一些公式：
1,?x?yA(x,y)??y?xA(x,y)
2,?x?yA(x,y)??y?xA(x,y)
3,?y?xA(x,y)??x?yA(x,y)
4,?x?yA(x,y)??x?yA(x,y)
5,?y?xA(x,y)??x?yA(x,y)
6,?x?yA(x,y)??y?xA(x,y)
7,?y?xA(x,y)??x?yA(x,y)
8,?x?yA(x,y)??y?xA(x,y)
注意：下面式子不成立
?x?yA(x,y)??y?xA(x,y)
? 为了便于记忆，用下面图形表示上面八个公式。
?x?yA(x,y) ?y?xA(x,y)
?x?yA(x,y)
?y?xA(x,y) ?x?yA(x,y)
?y?xA(x,y)
?y?xA(x,y) ?x?yA(x,y)
? 实际上，根据 ?具有传递性，还可以派生出一些公式。
下面我们只证明一个等价公式。用谓词逻辑推理方法很
容易证明上面那些永真蕴涵式，在此就不证明了。下面
证明公式 1.。
? 证明,设论域为 {a1,a2,....,an}，则
?x?yA(x,y)??yA(a1,y)∧ ?yA(a2,y)∧ … ∧ ?yA(an,y)
?(A(a1,a1)∧A(a 1,a2)∧ … ∧A(a 1,an))∧
(A(a2,a1)∧A(a 2,a2)∧ … ∧A(a 2,an))∧ … ∧
(A(an,a1)∧A(a n,a2)∧ … ∧A(a n,an))
?(A(a1,a1)∧A(a 2,a1)∧ … ∧A(a n,a1))∧
(A(a1,a2)∧A(a 2,a2)∧ … ∧A(a n,a2))∧ … ∧
(A(a1,an)∧(A(a 2,an)∧ … ∧A(a n,an))
??xA(x,a1)∧ ?xA(x,a2)∧ … ∧ ?xA(x,an)
??y?xA(x,y)
? 本节小结：
? 熟练掌握谓词等价公式和永真蕴涵式的
证明方法及应用。
? 作业题：
? P66 (3) b)
? P71 (2) d),(6)
? 面作做个 练习 P71(1) c)
练习 P71(1) c),论域 D={1,2} a=1 b=2 f(1)=2 f(2)=1
P(1,1)=T P(1,2)=T P(2,1)=F P(2,2)=F
求 ?x?y(P(x,y)?P(f(x),f(y)))
??y(P(1,y) ?P(f(1),f(y)) ) ??y(P(2,y) ?P(f(2),f(y)) )
?((P(1,1) ?P(f(1),f(1))) ? (P(1,2) ?P(f(1),f(2))))?
((P(2,1) ?P(f(2),f(1))) ?(P(2,2) ?P(f(2),f(2))))
?((P(1,1) ?P(2,2)) ? (P(1,2) ?P(2,1)))?
((P(2,1) ?P(1,2)) ?(P(2,2) ?P(1,1)))
?((T ?F ) ? (T ?F))?((F ?T) ? (F ?T))
?(F ? F)?(T ? T)
?F?T ?F
2-4前束范式
与命题公式的范式类似，谓词公式也有规范形式。这
里主要介绍前束范式 --所有量词都在公式前边约束变元 。
1.前束范式定义：
如果一个谓词公式符合下面条件，它就是 前束范式,
所有量词前面都没有联接词；
所有量词都在公式的左面；
所有量词的辖域都延伸到公式的末尾。
例如 ?y?x?z(A(x)→(B(x,y)∨C(x,y,z)) )
?x(Ａ (x)→B(x) )
就是前束范式，而 ?xA(x)∧ ?yB(y)
?x?y(A(x)→(B(x,y)∧ ?zC(z)))
?xA(x)→B(x) 这三个就不是前束范式。
? 2.前束范式的写 法
给定一个带有量词的谓词公式，
1)消去公式中的联接词 → 和 ?(为了便于量
词辖域的扩充 )；
2)如果量词前有, ?”,则用量词否定公式
将, ?” 后移。再用摩根定律或求公式的
否定公式，将,?”后移到原子谓词公式
之前。
3)用约束变元的改名规则或自由变元的代入
规则对变元换名 (为量词辖域扩充作准备 )
4)用量词辖域扩充公式提取量词，使之成为
前束范式形式。
? 例 1,?xA(x)→ ?xB(x)
???xA(x)∨ ?xB(x)
??x?A(x)∨ ?xB(x)
??x?A(x)∨ ?yB(y) (换元 )
??x(?A(x)∨ ?yB(y)) (量词辖域扩充 )
??x?y(?A(x)∨B(y))
? 另一个方法,?xA(x)→ ?xB(x)
???xA(x)∨ ?xB(x)
??x?A(x)∨ ?xB(x)
??x(?A(x)∨B(x)) ( 量词分配公式 )
? 例 2.?x(P(x)∧R(x))→( ??xP(x)∧Q(x))
???x(P(x)∧R(x))∨( ??xP(x)∧Q(x)) (去 → )
??x?(P(x)∧R(x))∨( ?x?P(x)∧Q(x )) (量词转换 )
??x(?P(x)∨ ?R(x))∨( ?x?P(x)∧Q(x )) (后移 ?)
??x(?P(x)∨ ?R(x))∨( ?y?P(y)∧Q(z )) (换变元 )
??x(?P(x)∨ ?R(x))∨ ?y(?P(y)∧Q(z )) (扩量词辖域 )
??x?y((?P(x)∨ ?R(x))∨( ?P(y)∧Q(z )))(扩量词辖域 )
3.前束析取范式与前束合取范式：
前束析取范式,前束范式中量词后的括号内是析取范式形式。
前束合取范式,前束范式中量词后的括号内是合取范式形式。
上例的前束析取范式为,
?x?y(?P(x)∨ ?R(x)∨( ?P(y)∧Q(z )))
上例的前束合取范式为,
?x?y((?P(x)∨ ?R(x)∨ ?P(y))∧( ?P(x)∨ ?R(x)∨Q(z )))
? 本节掌握 前束范式的写法。
? 作业
? P75 (1)b)
? (2)c)
2-5 谓词演算的推理理论
推理方法：
直接推理、条件论证、反证法
所用公式,43页和 70页的 I1~I19,E1~E33
推理规则,P,T,CP,US,ES,EG,UG
? 后四个规则，是处理量词的，因为推理时
要使用不含量词的命题公式，所以要去掉
量词，如果结论有量词，还要添加量词。
? 下面介绍四个新规则：
一,全称特指规则 US
(Universal Specialization)
形式,?xA(x)?A(c)
(其中 c是论域内 指定客体 )
含义：如果 ?xA(x)为真，则在论域内 任
何指定 客体 c,都使得 A(c)为真。
作用：去掉全称量词。
要求,c不是 A(x)中的符号。
二,存在特指规则 ES(Existential Specialization)
形式,?xA(x)?A(c)
(其中 c是论域内 指定客体 )
含义：如果 ?xA(x)为真，则在论域内 指定 客体 c，
都使得 A(c)为真。
作用：去掉存在量词。
要求：⑴ c不是 A(x)中的符号。
⑵ 用 ES指定的客体 c不应该是 在此之前 用
US规则或者用 ES规则所指定的客体 c(即本次用
ES特指客体 c,不应该是以前特指的客体 )。
请看下面两个例子：
例 1,令 A(x)表示 x是自然数,B(x)表示 x是
整数。
⑴ ?x(A(x)→B(x)) P
⑵ A(c)→B(c) US 如 c=0.1
⑶ ?xA(x) P
⑷ A(c) × ES A(0.1)为 F
⑴ ?xB(x) P
⑵ B(c) ES 如 c=-1
⑶ ?xA(x) P
⑷ A(c) × ES A(-1)为 F
三,存在推广规则 EG
(Existential Generalization)
形式,A(c)??xA(x)
(其中 c是论域内 指定客体 )
含义：如果 在论域内 指定 客体 c使得
A(c)为真，则 ?xA(x)为真。
作用：添加存在量词。
要求,x不是 A(c)中的符号 。
四,全称推广规则 UG
(Universal Generalization)
形式,A(c)??xA(x)
(其中 c是论域内 任何 指定客体 )
含义：如果 在论域内 任何指定 客体 c都 使
得 A(c)为真，则 ?xA(x)为真。
作用：添加 全称 量词。
要求,x不是 A(c)中的符号。
c一定是任意 的客体，否则不可 全
称推广 。
例 1 所有金属都导电。铜是金属。
故铜导电。
令 M(x):x是金属。 C(x):x导电。 a:铜。
符号化为：
?x(M(x)→C(x)),M(a) ?C(a)
⑴ ?x(M(x)→C(x)) P
⑵ M(a)→C(a) US ⑴
⑶ M(a) P
⑷ C(a) T ⑵⑶ I11
例 2,所有自然数都是整数。有些数是自然
数。因此有些数是整数。
令 A(x)表示 x是自然数,B(x)表示 x是整数。
?x(A(x)→B(x)), ?xA(x) ? ?xB(x)
⑴ ?xA(x) P
⑵ A(c) ES ⑴
⑶ ?x(A(x)→B(x)) P
⑷ A(c)→B(c) US ⑶
⑸ B(C) T ⑵⑷ I11
⑹ ?xB(x) EG ⑸
例 2中，如果按下面方法推理，是否正确？
?x(A(x)→B(x)), ?xA(x) ? ?xB(x)
⑴ ?x(A(x)→B(x)) P
⑵ A(c)→B(c) US ⑴
⑶ ?xA(x) P
⑷ A(c) ES ⑶
⑸ B(C) T ⑵⑷ I11
⑹ ?xB(x) EG ⑸
问题在哪里？
例 3 不认识错误的人，也不能改正错误。
有些诚实的人改正了错误。所以有些诚
实的人是认识了错误的人。
设 A(x):x是 认识错误的人。
B(x):x改正了错误。 C(x):x是诚实的人。
符号化为：
?x(?A(x)→ ?B(x)),?x(C(x)∧B(x)),
? ?x(C(x)∧A(x))
?x(?A(x)→ ?B(x)),?x(C(x)∧B(x)),
? ?x(C(x)∧A(x))
⑴ ?x(C(x)∧B(x)) P
⑵ C(c)∧B(c) ES ⑴
⑶ C(c) T ⑵ I1
⑷ B(c) T ⑵ I2
⑸ ?x(?A(x)→ ?B(x))P
⑹ ?A(c)→ ?B(c) US ⑸
⑺ ??A(c) T ⑷⑹ I12
⑻ A(c) T ⑺ E1
⑼ C(c)∧A(c) T ⑶⑻ I9
⑽ ?x(C(x)∧A(x)) EG ⑼
例 4 一些病人喜欢所有医生。任何病人都不喜欢庸
医。所以没有医生是庸医。
设, P(x):x是 病人,D(x):x是 医生,
Q(x):x是 庸医,L(x,y),x喜欢 y.
符号化为,?x(P(x)∧ ?y(D(y)→ L(x,y)))，
?x(P(x)→ ?y(Q(y)→ ?L(x,y)))
???y(D(y)∧Q(y))
?x(P(x)∧ ?y(D(y)→ L(x,y))),?x(P(x)→ ?y(Q(y)→ ?L(x,y)))
???y(D(y)∧Q(y))
⑴ ?x(P(x)∧ ?y(D(y)→ L(x,y))) P
⑵ P(a)∧ ?y(D(y)→ L(a,y)) ES ⑴
⑶ P(a) T ⑵ I1
⑷ ?y(D(y)→ L(a,y)) T ⑵ I2
⑸ ?x(P(x)→ ?y(Q(y)→ ?L(x,y))) P
⑹ P(a)→ ?y(Q(y)→ ?L(a,y)) US ⑸
⑺ ?y(Q(y)→ ?L(a,y)) T ⑶ ⑹ I11
⑻ D(b)→ L(a,b) US⑷
⑼ Q(b)→ ?L(a,b) US ⑺
⑽ L(a,b) → ?Q(b) T ⑼ E18
⑾ D(b)→ ?Q(b) T ⑻⑽ I13
⑿ ?D(b)∨ ?Q(b) T ⑾ E16
⒀ ?(D(b)∧Q(b)) T ⑿ E8
⒁ ?y?(D(y)∧Q(y)) UG ⒀
⒂ ??y(D(y)∧Q(y)) T ⒁ E25
课堂练习 P79(1)d)改成：
?x(A(x)∨B(x) ),?x(B(x)→ ?C(x)),?xC(x)??x(A(x)
(1) ?x(A(x)∨B(x) ) P
(2) A(a)∨B(a) ES (1)
(3) ?x(B(x)→ ?C(x)) P
(4) B(a)→ ?C(a)) US (3)
(5) ?xC(x) P
(6) C(a) US (5)
(7 ) ?B(a) T (4)(6) I12
(8) A(a) T (2)(7) I10
(9) ?x(A(x) EG (8)
例 5 ?x(P(x)→Q(x)) ? ?xP(x)→ ?xQ(x)
用条件论证证明：
⑴ ?xP(x) P(附加前提 )
⑵ ?x(P(x)→Q(x)) P
⑶ P(a)→Q(a) ES ⑵
⑷ P(a) US ⑴
⑸ Q(a) T ⑶ ⑷ I11
⑹ ?xQ(x) EG ⑸
⑺ ?xP(x)→ ?xQ(x) CP
用反证法证明例 5：
?x(P(x)→Q(x)) ? ?xP(x)→ ?xQ(x)
⑴ ?(?xP(x)→ ?xQ(x)) P(假设前提 )
⑵ ?(??xP(x)∨ ?xQ(x)) T ⑴ E16
⑶ ?xP(x)∧ ??xQ(x) T⑵ E9
⑷ ?xP(x) T⑶ I1
⑸ ??xQ(x) T⑶ I2
⑹ ?x(P(x)→Q(x)) P
⑺ P(a)→Q(a) ES ⑹
⑻ P(a) US ⑷
⑼ Q(a) T ⑺⑻ I11
⑽ ?xQ(x) EG ⑼
⑾ ??xQ(x)∧ ?xQ(x) T⑸⑽ I9
用推理证明公式：
?y?xA(x,y)??x?yA(x,y)
⑴ ?y?xA(x,y) P
⑵ ?xA(x,b) ES ⑴
⑶ A(a,b) US ⑵
⑷ ?yA(a,y) EG ⑶
⑸ ?x?yA(x,y) UG ⑷
作业,79页 ⑴ c)d) ⑵,⑶
推理时的注意事项：
推理时注意事项：
1.注意使用 ES,US,EG,UG的限制条件。
2.对于同一个客体变元，既有带 ?也有带 ?的前提，去量词
时，应先去 ?后去 ?，这样 才可以特指同一个客体 c.
3.去量词时，该量词必须是公式的最左边的量词，且此量
词的前边 无任何符号,它的辖域作用到公式末尾。
下面的作法是错误的,正确作法是,
⑴ ?xP(x)→ ?yQ(y) P ⑴ ?xP(x)→ ?yQ(y) P
⑵ ?xP(x)→ Q(b) × ES⑴ (2)??xP(x)∨ ?yQ(y) T(1) E
(3)P(a)→ Q(b) × US(2) (3) ?x?P(x)∨ ?yQ(y) T(2) E
(4) ?x?y(?P(x)∨ Q(y)) T(3) E
(5) ?y(?P(a)∨ Q(y)) ES(4)
实际上 ?x的辖域扩 (6) ?P(a)∨ Q(b)) ES(4)
充后量词改成为 ?x (7) P(a)→ Q(b) T(5)E
下面的作法是错误的,正确作法是,
⑴ ??xP(x) P ⑴ ??xP(x) P
⑵ ?P(c) US⑴ (2) ?x?P(x) T(1)E
实际上⑴ 中不是 ?x而是 ?x (3) ?P(c) ES (2)
⑴ ?x?yP(x,y) P ⑴ ?x?yP(x,y) P
⑵ ?xP(x,c) ES⑴ (2) ?yP(a,y) US(1)
令 P(x,y):y是 x的 生母，显然 ⑵是个假命题,
另外 X是公式 A的子公式，且 X?Y,如果用 Y替换 A中 X而得
到 B，那么不一定有 A?B。例如 P∧ Q?P,而 ?(P∧ Q)??P
是不成立的。 US和 ES规则都是蕴涵式，所以不可对一个
子公式用这些规则。
4.添加量词时，也要加在公式的最左边,(即新加的量词
前也无任何符号 ！！ )且其辖域作用到公式的末尾。
第二章 小结
本章重点掌握内容：
1.各基本概念清楚。
2.会命题符号化。
3.熟练掌握等价公式和永真蕴涵式。
4.会写前束范式。
5.熟练掌握谓词逻辑的三种推理方法。
第二章 习题课
一, 命题符号化 60页 (2)
a) ?x(J(x)→ L(x)) b) ?x(L(x)∧ S(x))
c) ?x(J(x)∧ O(x)∧ V(x)) d) J(j)∧ ?O(j)∧ ?V(j)
e) ??x(L(x)→ J(x)) 或者 ?x(L(x)∧ ?J(x))
f) ?x(S(x)∧ L(x)∧ C(x))
g) ??x(C(x)∧ ?V(x)) 或者 ?x(C(x)→ V(x))
h) ?x((C(x)∧ O(x))→ L(x))
i) ??x(W(x)∧ C(x)∧ H(x))
j) ?x(W(x)∧ J(x)∧ C(x))
k) ?x(L(x)→ ?y(J(y)∧ A(x,y)))
l) ?x(S(x)∧ ?y(L(y)→ ?A(x,y)))
62页 (2)
?x?y((P(x)∧ P(y)∧ ?E(x,y))
→ ?z(L(z)∧R(x,y,z)∧ ?t((L(t)∧R(x,y,t))→E(t,z))))
(3)b)设 R(x):x是实数,G(x,y):x＞ y
?x(R(x)→ ?y(R(y)∧ G(y,x)))
c)设 R(x):x是实数,G(x,y):x＞ y
f(x,y)=x+y g(x,y)=xy
?x?y?z(R(x)∧ R(y)∧ R(z)∧ G(f(x,y),g(x,z)))
或者 ?x?y?z(R(x)∧ R(y)∧ R(z)∧ G(x+y,xz))
(5)b)设 N(x):x是数,A(x,y):y是 x的后继数
??x(N(x)∧ A(x,1))
(6)设 A(x):x是戴眼镜的,B(x):x是用功的,C(x):x是大学
生,D(x):x是大的,E(x):x是厚的,F(x):x是巨著,
A(x,y):x在看 y,a:那位,b:这本
A(a)∧ B(a)∧ C(a)∧ D(b)∧ E(b)∧ F(b)∧ A(a,b)
*补充题,
1.每个人的叔叔都是他父亲的弟弟。
设,P(x):x是人,U(x,y):y是 x的叔叔，
B(x,y):x是 y的弟弟,f(x)=x的父亲
?x(P(x)→ ?y(U(x,y)→B (y,f(x)))
2.下面是判定一个年号是否为闰年的命题,
“年号能被 4整除并且不能被 100整除的为闰年, 或者年号
能被 400整除的也是闰年,”
设 Y(x):x是年号 ; D(x,y):x可整除 y; R(x):x是闰年
?x(Y(x)→( ((D(4,x)∧ ?D(100,x))→R(x) )∨ (D(400,x) →R(x) )))
66页 (3)b)P:2>1,Q(x):x≤3,R(x):x>5,a:5,{-2,3,6}
?x(P→ Q(x))∨ R(a)?(P→ ?xQ(x))∨ R(a)
?(P→ (Q(-2)∧ Q(3)∧ Q(6)))∨ R(5)
?(T→ (T ∧ T ∧ F ))∨ F
?(T→ F)∨ F?F∨ F ?F
(4)b)对约束变元换名
?x(P(x)→(R(x)∨Q(x))) ∧ ?xR(x)→ ?zS(x,z)
??y(P(y)→(R( y)∨Q( y)))∧ ?tR(t)→ ?uS(x,u)
(5)a)对自由变元代入
(?yA(x,y)→ ?xB(x,z))∧ ?x?zC(x,y,z)
?(?yA(u,y)→ ?xB(x,v))∧ ?x?zC(x,w,z)
72页 (2)d)论域为 {1,2}
P(1) P(2) Q(1,1) Q(1,2) Q(2,1) Q(2,2)
F T T T F F
?x?y(P(x)∧ Q(x,y))
??y(P(1)∧ Q(1,y))∧ ?y(P(2)∧ Q(2,y))
?((P(1)∧ Q(1,1))∨ (P(1)∧ Q(1,2)))∧
((P(2)∧ Q(2,1))∨ (P(2)∧ Q(2,2)))
?((F∧ T)∨ (F∧ T))∧ ((T∧ F)∨ (T∧ F))
?(F∨ F)∧ (F∨ F)?F
(6)判断下面推证是否正确。
?x(A(x)→B(x))
⑴ ??x(?A(x)∨B(x))
⑵ ??x?(A(x)∧ ?B(x)
⑶ ???x(A(x)∧ ?B(x))
⑷ ??(?xA(x)∧ ?x?B(x))
⑸ ???xA(x)∨ ??x?B(x)
⑹ ???xA(x)∨ ?xB(x)
⑺ ??xA(x)→ ?xB(x)
第⑷步错，由⑶到⑷用的是公式：
?x(A(x)∧ ?B(x))?(?xA(x)∧ ?x?B(x))
无此公式，而是 ?x(A(x)∧ ?B(x))?
?xA(x)∧ ?x?B(x)，应将⑷中的 ?换成 ? 即：
?x(A(x)→B(x))
⑴ ??x(?A(x)∨B(x))
⑵ ??x?(A(x)∧ ?B(x)
⑶ ???x(A(x)∧ ?B(x))
⑷ ??(?xA(x)∧ ?x?B(x))
⑸ ???xA(x)∨ ??x?B(x)
⑹ ???xA(x)∨ ?xB(x)
⑺ ??xA(x)→ ?xB(x)
因为由公式 E18 P→ Q??Q→ ?P
?x(A(x)∧ B(x))? ?xA(x)∧ ?xB(x),
P Q
得 ?(?xA(x)∧ ?xB(x))???x(A(x)∧ B(x))
75页 (1)b)?x(??yP(x,y)→( ?zQ(z)→R(x)) )
??x(?yP(x,y)∨ (??zQ(z)∨ R(x)))
??x(?yP(x,y)∨ (?z?Q(z)∨ R(x)))
??x(?yP(x,y)∨ ?z(?Q(z)∨ R(x)))
??x?y?z(P(x,y)∨ (?Q(z)∨ R(x)))
(2)c)?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)∨ ?zR(x,y,z))
??x?P(x)∨ ?u(?zQ(u,z)∨ ?tR(u,y,t))
??x?u?z?t(?P(x)∨ (Q(u,z)∨ R(u,y,t)))
??x?u?z?t(?P(x)∨ Q(u,z)∨ R(u,y,t))
此式既是前束析取范式，也是前束合取范式。
79页 (2)a)用 CP规则证明
?x(P(x)∨ Q(x)? ?xP(x)∨ ?xQ(x)
因为 ?xP(x)∨ ?xQ(x)? ??xP(x)→ ?xQ(x)
⑴ ??xP(x) P(附加前提 )
⑵ ?x ?P(x) T ⑴ E
⑶ ?P(a) ES ⑵
⑷ ?x(P(x)∨ Q(x) P
⑸ P(a)∨ Q(a) US ⑷
⑹ Q(a) T ⑶⑸ I
⑺ ?xQ(x) EG ⑹
⑻ ??xP(x)→ ?xQ(x) CP
(3)a)所有有理数是实数，某些有理数是整数，
因此某些实数是整数。
设 Q(x):x是有理数 R(x):x是实数 I(x):x是整数
?x(Q(x)→R(x) ),?x(Q(x)∧ I(x))?
?x(R(x)∧ I(x))
⑴ ?x(Q(x)∧ I(x)) P
⑵ Q(a)∧ I(a) ES⑴
⑶ Q(a) T ⑵ I
⑷ I(a) T ⑵ I
⑸ ?x(Q(x)→R(x) ) P
⑹ Q(a)→R(a) US ⑸
⑺ R(a) T ⑶⑹ I
⑻ R(a)∧ I(a) T ⑷⑺ I
⑼ ?x(R(x)∧ I(x)) EG⑻
b)任何人如果他喜欢步行，他就不喜欢乘汽车；
每个人或者喜欢乘汽车或者喜欢骑自行车。有
的人不爱骑自行车，因此有的人不爱步行。
设 A(x):x是人,B(x):x是 喜欢步行,
C(x):x喜欢乘汽车,D(x):x喜欢骑自行车
?x(A(x)→(B(x)→ ?C(x))),
?x(A(x)→(C(x) ∨ D(x))),?x(A(x)∧ ?D(x))
? ?x(A(x)∧ ?B(x))
⑴ ?x(A(x)∧ ?D(x)) P
⑵ A(a)∧ ?D(a)) ES ⑴
⑶ A(a) T ⑵ I
⑷ ?D(a)) T ⑵ I
⑸ ?x(A(x)→(B(x)→ ?C(x))) P
⑹ A(a)→(B(a)→ ?C(a)) US ⑸
⑺ B(a)→ ?C(a)) T ⑶⑹ I
⑻ ?x(A(x)→(C(x) ∨ D(x))) P
⑼ A(a)→(C(a) ∨ D(a))) US⑻
⑽ C(a)∨ D(a) T ⑶⑼ I
⑾ C(a) T ⑷⑽ I
⑿ ?B(a) T ⑺⑾ I
⒀ A(a)∧ ?B(a)) T ⑶⑿ I
⒁ ?x(A(x)∧ ?B(x)) EG ⒀
c)每个大学生不是文科生就是理工科生，
有的大学生是优等生，小张不是理工科
生，但他是优等生，因此如果小张是大
学生，他就是文科生。
设 A(x):x是大学生,B(x):x是 文科生,
C(x):x是理工科生, D(x):x是优等生,
a:小张
?x(A(x)→( ?B(x)→C(x) )),
?x(A(x)∧ D(x))
?C(a)∧ D(a) ? A(a)→B(a)
?x(A(x)→( ?B(x)→C(x) )),?x(A(x)∧ D(x))
?C(a)∧ D(a) ? A(a)→B(A)
⑴ A(a) P(附加前提 )
⑵ ?x(A(x)→( ?B(x)→C(x) )) P
⑶ A(a)→( ?B(a)→C(a) ) US ⑵
⑷ ?B(a)→C(a) ) T ⑴⑶ I
⑸ ?C(a)∧ D(a) P
⑹ ?C(a) T ⑸ I
⑺ ??B(a) T ⑷⑹ I
⑻ B(a) T ⑺ E
⑼ A(a)→B(a) CP
补充题,小杨、小刘和小林为高山俱乐部成员，该俱乐
部的每个成员是个滑雪者或登山者。没有一个登山者喜
欢雨。而所有滑雪者都喜欢雪。凡是小杨喜欢的，小刘
就不喜欢。小杨喜欢雨和雪。试证明该俱乐部是否有个
是登山者而不是滑雪者的成员。如果有，他是谁？
设,M(x):x是高山俱乐部成员。 H(x):x是滑雪者。
D(x):x是登山者。 L(x,y):x喜欢 y。
a:小杨； b:小刘； c:小林； d:雨； e:雪。
命题符号化为：
M(a),M(b),M(c),?x(M(x)→( H(x)∨ D(x))),
??x(D(x)∧ L(x,d)),?x(H(x)→L (x,e))
?x(L(a,x)→ ?L(b,x)),L(a,d)∧ L(a,e)
⑴ L(a,d)∧ L(a,e) P
⑵ L(a,e) T ⑴
⑶ ?x(L(a,x)→ ?L(b,x)) P
⑷ L(a,e)→ ?L(b,e)) US ⑶
⑸ ?L(b,e)) T ⑵ ⑷ I11
⑹ ?x(H(x)→L (x,e)) P
⑺ H(b)→L (b,e)) US ⑹
⑻ ?H(b) T ⑸ ⑺ I12
⑼ ?x(M(x)→( H(x)∨ D(x))) P
⑽ M(b)→( H(b)∨ D(b)) US ⑼
⑾ M(b) P
⑿ H(b)∨ D(b) T ⑽ ⑾ I11
⒀ D(b) T ⑻ ⑿ I10
⒁ D(b)∧ ?H(b) T ⑻ ⒀
第二章 谓词逻辑
到此结束
问题的提出, (即命题逻辑的局限性 )
在第一章,一个原子命题只用一个字母表示，
而不再对命题中的句子成分细分。这样有一些逻
辑问题无法解决。请看下面的例子。
例 1.令Ｐ：小张是大学生。
Ｑ：小李是大学生。
从符号Ｐ、Ｑ中 不能归纳出他们都是大学生的共
性 。我们希望从所使用的符号那里带给我们更多
的信息，比如可以看出他们的共性。这种想法在
第一章是无法实现的。
例 2.令 Ａ：所有自然数都是整数。
Ｂ：８是自然数。
Ｃ：８是整数。
这是著名的三段论推理,A是大前提,B是小前提，
C是结论。显然，由Ａ和Ｂ可以推出结论Ｃ。这
个推理是有效的，但是 这个推理在第一章也是无
法实现的 。
分析,命题Ｐ与Ｑ中的谓语是相同的 (是大学生 ),
只是主语不同。命题Ａ、Ｂ、Ｃ之间在主语谓语
方面也是有联系的，靠这种联系才能由Ａ、Ｂ推
出Ｃ。而从这三个符号上看不出此种联系。
所以就要 另外考虑表示命题的方法 。
解决这个问题的方法,
在表示命题时，既表示出主语，也表示出谓语，
就可以解决上述问题。这就提出了 谓词 的概念。
令 S(x)表示 x是大学生,a:小张,b:小李
命题 P表示成 S(a):小张是大学生。
命题 Q表示成 S(b):小李是大学生。
从符号 S(a),S(b)可看出小张和小李都是大学生的共性,
令 N(x):x是自然数。 I(x):x是整数。
?表示所有的。
A,?x(N(x)→I(x))
B,N(8)
C,I(8)
N(8)→I(8)
N(8)
? I(8)
符号 S(x),N(x),I(x)就是所谓的谓词 。
推理如此实现：
2-1 基本概念
2-1.1 客体与客体变元
? 定义,能够独立存在的事物，称之为 客体,也
称之为 个体 。它可以是具体的，也可以是抽象的
事物。通常用小写英文字母 a,b,c,...表示。
例如，小张、小李,8,a、沈阳、社会主义等等
都是客体。
? 定义,用小写英文字母 x,y,z...表示任何客
体，则称这些字母为 客体变元 。
? 注意：客体变元本身不是客体 。
2-1.2 谓词
? 定义,一个大写英文字母后边有括号，括号内
是若干个客体变元，用以表示客体的属性或者
客体之间的关系，称之为 谓词 。如果括号内有
n个客体变元，称该谓词为 n元谓词 。
? 例如
S(x):表示 x是大学生。 一元谓词
G(x,y)：表示 x>y。 二元谓词
B(x,y,z)：表示 x在 y与 z之间。三元谓词
一般地
P(x1,x2,…,xn) 是 n元谓词。
2-1.3 命题函数
? 谓词本身并不是命题，只有谓词的括号内填入
足够的客体，才变成命题 。
? 例如，
a表示小张,b表示小李，则
S(a):小张是大学生。
S(b):小李是大学生。
Ｇ (7,3)表示,７ >３。
如果 c表示锦州,d表示沈阳,e表示山海关，则
B(c,d,e)表示：锦州在沈阳与山海关之间。
这时 S(a),S(b),G(7,3),B(c,d,e)才是命题。
令谓词 S(x):x是大学生，括号内填入不同的人名，
就得到不同的 命题,故谓词 S(x)相当于一个函数，
称之为 命题函数 。
定义, n元谓词 P(x1,x2,…,xn)称之为 简单命题函数 。
规定,当命题函数 P(x1,x2,…,xn)中 n=0 时，即 0
元谓词，表示不含有客体变元的谓词，它本身就是
一个 命题变元 。
定义,将若干个简单命题函数用逻辑联结词联结起
来，构成的表达式，称之为 复合命题函数 。简单命
题函数与复合命题函数统称为 命题函数 。
? 例如
? 给定简单命题函数：
A(x),x身体好，
B(x),x学习好，
C(x),x工作好，
? 复合命题函数 ?A(x)→( ?B(x)∧ ?C(x))
表示如果 x身体不好，则 x的学习与工作
都不会好。
2-1.4 论域 (个体域 )
? 定义,在 命题函数 中客体变元的取值范
围，称之为 论域,也称之为 个体域 。
例如 S(x):x是大学生，论域是,人类。
G(x,y),x>y,论域是,实数。
论域是一个集合。
? 定义,由所有客体构成的论域，称之为
全总个体域 。它是个, 最大, 的论域。
? 约定,对于一个命题函数，如果没有给定
论域，则 假定该论域是全总个体域 。
2-1.5 量词
? 例如：有些人是大学生。
所有事物都是发展变化的。
,有些,,“所有的,,就是对客体量化的词。
? 定义,在命题中表示对客体数量化的词，称之
为 量词 。
? 定义了两种量词：
(1).存在量词,记作 ?，表示, 有些,,, 一
些,,
,某些,,, 至少一个, 等。
(2).全称量词,记作 ?，表示, 每个,,, 任
何
一个,,, 一切,,, 所有的,,“凡是”、
“任意
? 定义,量词后边要有一个客体变元，指明对哪
个客体变元量化，称此客体变元是 量词后的指
导变元 。
例如 ?x(读作, 任意 x”),?x(读作, 存在 x”)，
其中的 x就是量词后的指导变元。
例题１,所有的自然数都是整数。
设 N(x),x是自然数。 I(x),x是整数。此命
题可以写成 ?x(N(x)→I(x))
例题２,有些自然数是偶数。
设 E(x),x是偶数。
此命题可以写成 ?x(N(x)∧E(x))
? 例题 3,每个人都有一个生母。
设 P(x):x是个人。 M(x,y):y是 x的生母。
此命题可以写成
?x(P(x)→ ?y(P(y)∧M(x,y)))
2-2 谓词公式及命题符号化
命题逻辑中有命题公式，类似地，在谓词逻辑
中，要研究谓词公式。
2-2.1 客体函数
有些命题中，可能有若干个客体，其中有些客体
之间有函数关系，例如
例题 1,如果 x是奇数，则 2x是偶数。
其中客体 x与客体 2x之间就有函数关系，可以设
客体函数 g(x)=2x，
谓词 O(x),x是奇数,E(x),x是偶数，
则此命题可以表示为,?x(O(x)→E(g(x)))
? 例题 2 小王的父亲是个医生。
设函数 f(x)=x的父亲，谓词 D(x):x是个医
生,a:小王，此命题可以表示为 D(f(a)).
? 例题 3 如果 x和 y都是奇数，则 x+y是偶数。
设 h(x,y)=x+y,此命题可以表示为,
?x?y((O(x)∧O(y))→E(h(x,y))
? 像上述的 g(x),f(x),h(x,y)就是客体函
数，一般地用小写的英文字母 f,g,h…,表
示客体函数。
? 注意,客体函数与谓词是不同的，不可混
淆,
要注意区分客体函数与谓词间的区别：
? 设例题 1的论域是自然数集合 N。
? 客体函数中的客体变元用客体带入后的结果依
然 是个客体 (3∈N,g(3)=6,所以 g(3)∈N) 。
? 谓词中的客体变元用确定的客体带入后就 变成
了命题,其真值为Ｔ或者为Ｆ (3∈N,O( ３ )是
个命题,真值为 T)。
? 把它们都看成, 映射, 的话，则
客体函数是论域到论域的映射, g:N→N,如果
指定的客体 a∈N,则 g(a)∈N 。
而谓词是从论域到 {T,F}的映射,即谓词 E(x)可
以看成映射 E:N→{T,F},如果指定客体 a∈N,则
E(a)的真值 ∈ {T,F}。
2-2.2 原子谓词公式
? 定义,称 n元谓词 P(x1,x2,...,xn)为原子
谓词公式。
? 例如 P,Q(x), A(x,f(x)),B(x,y,a)
都是原子谓词公式。
2-2.3 谓词合式公式 (WFF)
(Well Formed formulas)
? 定义,谓词合式公式递归定义如下：
1.原子谓词公式是合式公式。
2.如果 A是合式公式，则 ?A也是合式公式。
3.如果 A,B是合式公式，则 (A∧B), (A∨B),
(A→B), (A?B)都是合式公式。
4.如果 A是合式公式,x是Ａ中的任何客体变元，
则 ?xＡ和 ?xＡ也是合式公式。
5.只有有限次地按规则 (1)至 (4)求得的公式才
是合式公式。
? 谓词合式公式 也叫 谓词公式,简称 公式 。
? 下面都是合式公式：
P,(P→Q), (Q(x)∧P),
?x(A(x)→B(x)), ?xC(x)
? 而下面都不是合式公式：
x?y?P(x), P(?x)∧Q(x) ??x
? 为了方便，最外层括号可以省略，但是
若量词后边有括号，则此括号不能省。
? 注意,公式 ?x(A(x)→B(x) )中 ?x后边的
括号不是最外层括号，所以不可以省略。
2-2.4 量词的作用域 (辖域 )
? 定义,在谓词公式中，量词的作用范围称之为
量词的 作用域,也叫量词的 辖域 。
? 例如 ?xA(x)中 ?x的辖域为 A(x).
? ?x((P(x)∧Q(x))→ ?yR(x,y))中
?x的辖域是 ((P(x)∧Q(x))→ ?yR(x,y))
?y的辖域为 R(x,y)。
? ?x?y?z(A(x,y)→B(x,y,z))∧C(t)
?x的辖域
?z的辖域
?y的辖域
一般地，
? 如果量词后边只是一个原子谓词公式时，
该量词的辖域就是此原子谓词公式。
? 如果量词后边是括号，则此括号所表示
的区域就是该量词的辖域。
? 如果多个量词紧挨着出现，则后边的量
词及其辖域就是前边量词的辖域。
2-2.5 自由变元与约束变元
? 在谓词公式中的客体变元可以分成两种，
一种是受到量词约束的，一种是不受量词
约束的。请看下面公式：
? ?x(F(x,y)→ ?yP(y))∧Q(z)
Ｆ (x,y)中的 x在 ?x的辖域内，受到 ?x的
约束，而其中的 y不受 ?x的约束。
P(y)中的 y在 ?y的辖域内，受 ?y的约束。
Q(z)中的 z不受量词约束。
? 定义,如果客体变元 x在 ?x或者 ?x的辖域
内，则称 x在此辖域内约束出现，并称 x
在此辖域内是 约束变元 。否则 x是自由出
现，并称 x是 自由变元 。
? 上例中
?x(F(x,y)→ ?yP(y))∧Q(z)
F(x,y)中的 x和 P(y)中的 y是约束变元。
而 F(x,y)中的 y和 Q(z)中的 z是自由变元。
? 对约束变元和自由变元有如下几点 说明,
(1).对约束变元用什么符号表示无关紧要。
就是说 ?xA(x)与 ?yA(y)是一样的。这类
似于计算积分与积分变元无关，即积分
∫ f(x)dx 与 ∫ f(y)dy 相同。
(2).一个谓词公式如果无自由变元，它就
表示一个命题 。
例如 A(x)表示 x是个大学生。 ?xA(x)或
者 ?xA(x)就是个命题了，因为它们分别
表示命题, 有些人是大学生, 和, 所有
人都是大学生, 。
(3).一个 n元谓词 P(x1,x2,…,xn)，若在前边添加
k个量词，使其中的 k个客体变元变成约束变
元，则此 n元谓词就变成了 n-k元谓词。
? 例如 P(x,y,z)表示 x+y=z，假设论域是整数集。
?x?yP(x,y,z)表示, 任意给定的整数 x，都可
以找到整数 y，使得 x+y=z” 。
? 如果令 z=1，则 ?x?yP(x,y,1)就变成了命题
,任意给定的整数 x，都可以找到整数 y，使得
x+y=1”,… 。
? 可见每当给 z指定个整数 a后,?x?yP(x,y,a)就
变成了一个命题。所以谓词公式 ?x?yP(x,y,z)
就相当于只含有客体变元 z的一元谓词了。
? 在一个谓词公式中，如果某个客体变元
既以约束变元形式出现，又以自由变元
形式出现，就容易产生混淆。为了避免
此现象发生，可以对客体变元更改名称。
如 ?x(F(x,y)→ ?yP(y))∧Q(z)
? 约束变元的改名规则,
(1).对约束变元可以更改名称，改名的范
围是：量词后的指导变元以及该量词的
辖域内此客体变元出现的各处同时换名。
(2).改名后用的客体变元名称，不能与该
量词的辖域内的其它变元名称相同。
例如 ?x(P(x)→Q(x,y))∨(R(x)∧A(x))
此式中的 x 就是以两种形式出现。可以对 x改名 成
?z(P(z)→Q(z,y))∨(R(x)∧A(x))
对自由变元也可以换名字，此换名叫代入。
对 自由变元的代入规则,
(1).对谓词公式中的自由变元可以作代入。代入
时需要对公式中出现该变元的每一处，同时作
代入。
(2).代入后的变元名称要与公式中的其它变元名
称不同
上例也可以对自由变元 x作代入，改成
?x(P(x)→Q(x,y))∨(R(z)∧A(z))
2-2.6 命题的符号化
在谓词演算中，命题的符号化比较复杂,命题的
符号表达式与论域有关系 。例如
1.每个自然数都是整数。
(1).如果论域是自然数集合 N，令 I(x),x是整
数，则命题的表达式为 ?xI(x)
(2).如果论域扩大为 全总个体域 时，上述表达式
?xI(x)表示, 所有客体都是整数,,显然这是
假的命题，此表达式已经不能表达原命题了。
因此需要添加谓词 N(x),x是自然数,用于表
明 x的特性,于是命题的符号表达式为
?x(N(x)→I(x))
2.有些大学生吸烟。
(1).如果论域是大学生集合 S，令 A(x),x
吸烟，则命题的表达式为 ?xA(x)
(2).如果论域扩大为 全总个体域 时，上述
表达式 ?xA(x)表示, 有些客体吸烟,,
就不是表示此命题了，故需要添加谓词
S(x),x是大学生,用于表明 x的特性,
于是命题的表达式为 ?x(S(x)∧A(x))
? 从上述两个例子可以看出，命题的符号表达式
与论域有关。 当论域扩大时，需要添加用来表
示客体特性的谓词，称此谓词为 特性谓词 。 特
性谓词 往往就是给定命题中量词后边的那个名
词 。如上面两个例子中的, 所有 自然数,,
,有些 大学生, 。
? 如何添加特性谓词，这是个十分重要的问题,
这与前边的量词有关 。
? 特性谓词的添加方法如下：
? 如果 前边是全称量词, 特性谓词后边是蕴含联
结词, →, ； 如果 前边是存在量词, 特性谓词
后边是合取联结词, ∧, 。
? 为什么必须这样添加特性谓词？
分析一下特性谓词和原谓词所表示的概念之间
的关系，得出下面的图，从此图可以得出如此
添加特性谓词的正确性。
? 令 N:自然数集合,I:整数集合，
S:大学生集合,A:烟民的集合。
IN S A
吸烟大学生
I包含 N
?x(N(x)→I(x))
吸烟大学生是 S与 A的交集
?x(S(x)∧A(x))
3.所有大学生都喜欢一些歌星。
令 S(x),x是大学生,X(x),x是歌星，
L(x,y),x喜欢 y。 则命题的表达式为
?x(S(x)→ ?y(X(y)∧L(x,y)))
4.没有不犯错误的人。
此话就是, 没有人不犯错误,,, 没有, 就是, 不存
在, 之意。令 P(x),x是人,F(x),x犯错误，
此命题的表达式为
??x(P(x)∧ ?F(x))或者 ?x(P(x)→F(x))
5.不是所有的自然数都是偶数。
令 N(x),x是自然数,E(x),x是偶数，
命题的表达式为,
??x(N(x)→E(x)) 或者 ?x(N(x)∧ ?E(x))
?6.如果一个人只是说谎话，那么他所说的每句话没有
一句是可以相信的。
令 A(x),x是人,B(x,y),y是 x说的话，
C(x):x是谎话,D(x),x是可以相信的
命题的表达式为,
?x(A(x)→( ?y(B(x,y)→C(y))→ ??z(B(x,z)∧D(z)))
或者 ?x(A(x)→ ?y((B(x,y)∧C(y))→ ?D(y)))
? 7.每个自然数都有唯一的后继数。
令 N(x),x是自然数,A(x,y),y是 x的后继数，
E(x,y),x=y 则命题的表达式为
?x(N(x)→ ?y(N(y)∧A(x,y)∧ ?z((N(z)∧A(x,z))→E(y,z))))
有一个后继数 后继数的唯一性
下面请同学们自己做练习第 60页 (2)
练习 P60(2)
? a) ?x(J(x)→ L(x))
? b) ?x(L(x)∧ S(x))
? c) ?x(J(x)∧ O(x)∧ V(x))
? d) J(j)∧ ?O(j)∧ ?V(j)
? e) ??x(L(x)→ J(x)) 或者 ?x(L(x)∧ ?J(x))
? f) ?x(S(x)∧ L(x)∧ C(x))
? g) ??x(C(x)∧ ?V(x)) 或者 ?x(C(x)→ V(x))
? h) ?x((C(x)∧ O(x))→ L(x))
? i) ??x(W(x)∧ C(x)∧ H(x))
? j) ?x(W(x)∧ J(x)∧ C(x))
? k) ?x(L(x)→ ?y(J(y)∧ A(x,y)))
? l) ?x(S(x)∧ ?y(L(y)→ ?A(x,y)))
小结
1.命题的符号表达式形式与论域有关系。
论域扩大需要用特性谓词对客体进行说明,注意如何添
加特性谓词 (即要注意特性谓词后边是什么联结词 )。
2.如果量词前有否定符号，如“没有,..”,不是所有
的,..”等，可以按照字面直译。如, ??x…”,??x...”
3.命题的符号表达式中所有客体变元必须都是约束变元，
才表示命题。有时给定命题中有些量词没有明确给出，
要仔细分析并写出这隐含的量词。 例如
a) 金子闪光，但闪光的不一定都是金子。 G(x),F(x)
?x(G(x)→ F(x))∧ ??x(F(x) → G(x))
b) 没有大学生不懂外语。 S(x),K(x,y),F(x)
??x(S(x)∧ ?y(F(y)→ ?K(x,y)))
? 作业
? 60页 (2)
? 62页 (2),
? (3) b),c),
? (5) b)
? (6)
? 65页 (4) b)
? (5) a)
2-3谓词演算的等价式与蕴涵式
? 在命题逻辑中，我们是通过对公式的命题变元
赋值来讨论永真式、永真蕴含式及等价公式的。
? 在谓词演算中，也要讨论一些重要的谓词公式。
但是由于谓词公式中可能有命题变元、客体变
元。对命题变元赋值比较容易，因为只有两个
值可赋。而对客体变元作指派却不那么简单，
因为论域中的客体可能有无限个。另外谓词公
式的真值还与论域有关。
2-3.1 对谓词公式赋值
? 定义,若将给定的谓词公式中的命题变元，
用确定的命题代替，对公式中的客体变元
用论域中的客体代替，这个过程就称之为
对谓词公式作指派,或者称之 为 对谓词
公式赋值 。
? 例如公式 P→N(x), N(x),x是自然数，
论域为实数集合 R，
令 P,2>1,x=4 时，此公式变成 P→N(4),
它的真值就是, 真, 。
2-3.2 谓词公式的永真式 定义
? 定义,给定谓词公式 A,E是其论域，如
果不论对公式 A作任何赋值，都使得 A的
真值为真，则称公式 A在论域 E上是永真
式 。如果不论对什么论域 E，都使得公式
A为永真式，则称 A为永真式 。
例如,I(x),x是整数，论域 E为自然数
集合，公式 I(x)在 E上就是永真式。
而公式 I(x)∨ ?I(x)就是与论域无关
的永真式。
2-3.3 谓词公式的等价公式 定义
? 定义,给定谓词公式 A,B,E是它们的论域，
如果不论对公式 A,B作任何赋值，都使得 A与 B
的真值相同 (或者说 A?B是永真式 )，则称公式
A与 B在论域 E上是等价的。如果不论对什么论
域 E，都使得公式 A与 B等价，则称 A与 B等价，
记作 A?B。
? 例如,I(x)：表示 x是整数,N(x)：表示 x是自
然数，假设论域 E是自然数集合，公式 I(x)与
N(x)在 E上是等价的。
而公式 N(x)→I(x) 与 ?N(x)∨I(x) 就是与论域
无关的等价的公式，即
N(x)→I(x) ??N(x)∨I(x) 。
2-3.4 谓词公式的永真蕴含式 定义
? 定义,给定谓词公式 A,B,E是它们的论域，
如果不论对公式 A,B作任何赋值，都使得 A→B
为永真式，则称在论域 E上公式 A永真蕴含 B。
如果不论对什么论域 E，都使得公式 A→B 为永
真式，则称 A永真蕴含 B，记作 A?B。
? 例如,G(x)：表示 x大于 5,N(x)：表示 x是自
然数，论域 E={-1,-2,6,7,8,9,....}，
? 在 E上公式 G(x)→N(x) 是永真式。
? 而公式 (G(x)∧N(x))→N(x) 就是与论域无关的
永真式，所以 (G(x)∧N(x)) ?N(x)。
2-3.5,重要公式
下面讨论重要的谓词等价公式和永真蕴含式。
一,由命题公式推广出的公式
因一个不含自由变元的谓词公式本身如 ?xA(x),?xB(x)
就是命题 。一个含有 n个自由变元的谓词公式，赋予论域
中的 n个指定客体后就变成命题 (例如 S(a),G(3,1)等 )。
因此可以把此公式 看成一个命题变元 。所以在命题演算
的永真式中，将其中的同一个命题变元，用同一个谓词
公式代替，所得到的公式也是永真式。这样就可以将命
题演算中的等价公式和永真蕴含式推广到谓词演算中使
用。例如
A(x)?A(x)∨B(x) P?P∨Q
?x(A(x)→B(x)) ??x(?A(x)∨B(x)) P→Q ??P∨ Q
?(?xA(x)∧ ?xB(x))???xA(x)∨ ??xB(x) 摩根定律
二,带量词的公式在论域内的展开式
? 先看一个例子，令 A(x)：表示 x是整数,B(x)：
表示 x是奇数，设论域是 {1,2,3,4,5}，谓词公
式 ?xA(x)表示论域内所有的客体都是整数，显
然公式 ?xA(x)的真值为真，因为 A(1),A(2)、
A(3),A(4),A(5)都为真，于是有
?xA(x)?A(1)∧A(2)∧A(3)∧A(4)∧A(5)
类似地，谓词公式 ?xB(x)表示论域内有些客体
是奇数，显然公式 ?xB(x)的真值也为真，因为
B(1),B(3),B(5)的真值为真，于是有
?xB(x)?B(1)∨B(2)∨B(3)∨B(4)∨B(5)
一般地，设论域为 {a1,a2,....,an}，则
1,?xA(x)?A(a1)∧A(a 2)∧......∧A(a n)
2,?xB(x)?B(a1)∨B(a 2)∨......∨B(a n)
三,量词否定公式
? 我们还是先用一个例子说明这个问题。令
Ａ (x)表示 x是优等生，论域是某班级的学生集合。
? ??xA(x)表示：不是所有人都是优等生。
?x?A(x)表示：有些人不是优等生。
? ??xA(x)表示：没有人是优等生。
?x?A(x)表示：所有人都不是优等生。
? 从这个例子可以看出
,不是所有人都是优等生。, 与, 有些人不是
优等生。, 是等价的。
,没有人是优等生。, 与, 所有人都不是优等
生。, 是等价的。于是有：
1,??xA(x)??x?A(x)
2,??xA(x)??x?A(x)
对这两个公式可以证明如下：
证明,设论域为 {a1,a2,....,an}，则
??xA(x)??(A(a1)∧A(a 2)∧...∧A(a n))
??A(a1)∨ ?A(a2)∨...∨ ?A(an)??x?A(x)
类似可以证明另一个公式。
从这两个公式，可以总结出如下 规律,将量词前
的, ?” 移到量词的后边，或者将量词后的
,?” 移到量词的前边时，量词也随着改变，
如果原来是全称量词改成存在量词，如果原来
是存在量词改成全称量词。所以我们也把这两
个公式称为量词转换公式。
四,量词辖域的扩充公式
如果 Ｂ是个不含客体变元 x的谓词公式,且不在
?x和 ?x的辖域内，可以将Ｂ放入 ?x和 ?x的辖
域内。即得如下公式：
1,?xA(x)∨B ??x(A(x)∨B)
2,?xA(x)∧B ??x(A(x)∧B)
3,?xA(x)∨B ??x(A(x)∨B)
4,?xA(x)∧B ??x(Ａ (x)∧B)
5,B→ ?xA(x)??x(B→A(x))
6,B→ ?xA(x)??x(B→A(x))
7,?xA(x)→B ??x(A(x)→B)
8,?xA(x)→B ??x(A(x)→B)
上述公式我们只证明三个。
? 证明,设论域为 {a1,a2,....,an}，
?xA(x)∨B ?(A(a1)∧A(a 2)∧...∧A(a n))∨B
?(A(a1)∨B)∧(A(a 2)∨B)∧...∧(A(a n)∨B)
??x(Ａ (x)∨ Ｂ )
B→ ?xA(x)??B∨ ?xA(x)??x(?B∨A(x))
??x(B→A(x))
?xA(x)→B ???xA(x)∨B ??x?A(x)∨B
??x(?A(x)∨B) ??x(A(x)→B)
在使用公式 7.,8.时，要特别注意，量词的辖
域扩充后，量词发生了变化 。
五,量词分配公式
1,?x(A(x)∨B(x)) ??xA(x)∨ ?xB(x)
2,?x(A(x)∧B(x)) ??xA(x)∧ ?xB(x)
3,?x(A(x)∧B(x)) ??xA(x)∧ ?xB(x)
4,?xA(x)∨ ?xB(x)??x(A(x)∨B(x))
证明,设论域为 {a1,a2,....,an}，
?x(A(x)∨B(x))
?(A(a1)∨B(a 1))∨(A(a 2)∨B(a 2))∨ …
∨(A(a n)∨B(a n))
?(A(a1)∨A(a 2)∨...∨A(a n))∨
(B(a1)∨B(a 2)∨...∨B(a n))
??xA(x)∨ ?xB(x)
? 注意 公式 3.和 4.不是等价公式，而是永
真蕴含式。
例如公式 3.由 ?xA(x)∧ ?xB(x)不能推出
?x(A(x)∧B(x)),
? 我们可以举一个反例，设 A(x)和 B(x)分别
表示, x是奇数, 和, x是偶数,,显然命
题 ?xA(x)∧ ?xB(x)为真。而
?x(A(x)∧B(x)) 是表示命题, 存在一些数
既是奇数，也是偶数,,显然不为真。
所以说由 ?xA(x)∧ ?xB(x)不能推出
?x(A(x)∧B(x)).
? 证明公式 3.
?x(A(x)∧B(x)) ??xA(x)∧ ?xB(x)
? 证明,假设前件 ?x(A(x)∧B(x)) 为真，
则论域中至少有一个客体 a，使得
A(a)∧B(a) 为真，于是 A(a)和 B(a)都为
真，所以有 ?xA(x)以及 ?xB(x)为真，进
而得 ?xA(x)∧ ?xB(x)为真。于是有
?x(A(x)∧B(x)) ??xA(x)∧ ?xB(x)
下面利用公式 3.证明公式 4.。
证明,因为公式 3.中的 A(x)和 B(x)是任意
的谓词公式，不妨用 ?A(x)和 ?B(x)分别
代替公式 3.中的 A(x)和 B(x)得
?x(?A(x)∧ ?B(x))??x?A(x)∧ ?x?B(x)
?x?(A(x)∨B(x)) ???xA(x)∧ ??xB(x)
??x(A(x)∨B(x)) ??(?xA(x)∨ ?xB(x))
应用公式 P→ Q??Q→ ?P 得
?xA(x)∨ ?xB(x)??x(A(x)∨B(x))
公式 4.得证。
在使用公式 4.的时候,特别要注意蕴含式
的方向，不要搞错。
六．其它公式
1,?x(A(x)→B(x)) ??xA(x)→ ?xB(x)
2,?xA(x)→ ?xB(x)??x(A(x)→ B(x))
证明 1,?xA(x)→ ?xB(x)
???xA(x)∨ ?xB(x)
??x?A(x)∨ ?xB(x)
??x(?A(x)∨ B(x))
??x(A(x)→ B(x))
证明 2,?xA(x)→ ?xB(x)
???xA(x)∨ ?xB(x)
??x?A(x)∨ ?xB(x) ??x(?A(x)∨ B(x))
??x(A(x)→ B(x))
七．两个量词的公式
? 在 A(x,y)前有两个量词，如果两个量词
是相同的，它们的次序是无关紧要，但
是如果是不同的，它们的次序就不可以
随便交换。例如设
? A(x,y)表示, x+y=0”,论域为：实数集合，
? ?x?yA(x,y)表示, 对于任意给定的一个
实数 x,可以找到一个 y,使得 x+y=0”,这是
一个为, 真, 的命题。而交换量词后
? ?y?xA(x,y) 表示, 存在一个实数 y,与任
意给定的一个实数 x之和都等于 0”,这是
一个为, 假, 的命题。
有如下一些公式：
1,?x?yA(x,y)??y?xA(x,y)
2,?x?yA(x,y)??y?xA(x,y)
3,?y?xA(x,y)??x?yA(x,y)
4,?x?yA(x,y)??x?yA(x,y)
5,?y?xA(x,y)??x?yA(x,y)
6,?x?yA(x,y)??y?xA(x,y)
7,?y?xA(x,y)??x?yA(x,y)
8,?x?yA(x,y)??y?xA(x,y)
注意：下面式子不成立
?x?yA(x,y)??y?xA(x,y)
? 为了便于记忆，用下面图形表示上面八个公式。
?x?yA(x,y) ?y?xA(x,y)
?x?yA(x,y)
?y?xA(x,y) ?x?yA(x,y)
?y?xA(x,y)
?y?xA(x,y) ?x?yA(x,y)
? 实际上，根据 ?具有传递性，还可以派生出一些公式。
下面我们只证明一个等价公式。用谓词逻辑推理方法很
容易证明上面那些永真蕴涵式，在此就不证明了。下面
证明公式 1.。
? 证明,设论域为 {a1,a2,....,an}，则
?x?yA(x,y)??yA(a1,y)∧ ?yA(a2,y)∧ … ∧ ?yA(an,y)
?(A(a1,a1)∧A(a 1,a2)∧ … ∧A(a 1,an))∧
(A(a2,a1)∧A(a 2,a2)∧ … ∧A(a 2,an))∧ … ∧
(A(an,a1)∧A(a n,a2)∧ … ∧A(a n,an))
?(A(a1,a1)∧A(a 2,a1)∧ … ∧A(a n,a1))∧
(A(a1,a2)∧A(a 2,a2)∧ … ∧A(a n,a2))∧ … ∧
(A(a1,an)∧(A(a 2,an)∧ … ∧A(a n,an))
??xA(x,a1)∧ ?xA(x,a2)∧ … ∧ ?xA(x,an)
??y?xA(x,y)
? 本节小结：
? 熟练掌握谓词等价公式和永真蕴涵式的
证明方法及应用。
? 作业题：
? P66 (3) b)
? P71 (2) d),(6)
? 面作做个 练习 P71(1) c)
练习 P71(1) c),论域 D={1,2} a=1 b=2 f(1)=2 f(2)=1
P(1,1)=T P(1,2)=T P(2,1)=F P(2,2)=F
求 ?x?y(P(x,y)?P(f(x),f(y)))
??y(P(1,y) ?P(f(1),f(y)) ) ??y(P(2,y) ?P(f(2),f(y)) )
?((P(1,1) ?P(f(1),f(1))) ? (P(1,2) ?P(f(1),f(2))))?
((P(2,1) ?P(f(2),f(1))) ?(P(2,2) ?P(f(2),f(2))))
?((P(1,1) ?P(2,2)) ? (P(1,2) ?P(2,1)))?
((P(2,1) ?P(1,2)) ?(P(2,2) ?P(1,1)))
?((T ?F ) ? (T ?F))?((F ?T) ? (F ?T))
?(F ? F)?(T ? T)
?F?T ?F
2-4前束范式
与命题公式的范式类似，谓词公式也有规范形式。这
里主要介绍前束范式 --所有量词都在公式前边约束变元 。
1.前束范式定义：
如果一个谓词公式符合下面条件，它就是 前束范式,
所有量词前面都没有联接词；
所有量词都在公式的左面；
所有量词的辖域都延伸到公式的末尾。
例如 ?y?x?z(A(x)→(B(x,y)∨C(x,y,z)) )
?x(Ａ (x)→B(x) )
就是前束范式，而 ?xA(x)∧ ?yB(y)
?x?y(A(x)→(B(x,y)∧ ?zC(z)))
?xA(x)→B(x) 这三个就不是前束范式。
? 2.前束范式的写 法
给定一个带有量词的谓词公式，
1)消去公式中的联接词 → 和 ?(为了便于量
词辖域的扩充 )；
2)如果量词前有, ?”,则用量词否定公式
将, ?” 后移。再用摩根定律或求公式的
否定公式，将,?”后移到原子谓词公式
之前。
3)用约束变元的改名规则或自由变元的代入
规则对变元换名 (为量词辖域扩充作准备 )
4)用量词辖域扩充公式提取量词，使之成为
前束范式形式。
? 例 1,?xA(x)→ ?xB(x)
???xA(x)∨ ?xB(x)
??x?A(x)∨ ?xB(x)
??x?A(x)∨ ?yB(y) (换元 )
??x(?A(x)∨ ?yB(y)) (量词辖域扩充 )
??x?y(?A(x)∨B(y))
? 另一个方法,?xA(x)→ ?xB(x)
???xA(x)∨ ?xB(x)
??x?A(x)∨ ?xB(x)
??x(?A(x)∨B(x)) ( 量词分配公式 )
? 例 2.?x(P(x)∧R(x))→( ??xP(x)∧Q(x))
???x(P(x)∧R(x))∨( ??xP(x)∧Q(x)) (去 → )
??x?(P(x)∧R(x))∨( ?x?P(x)∧Q(x )) (量词转换 )
??x(?P(x)∨ ?R(x))∨( ?x?P(x)∧Q(x )) (后移 ?)
??x(?P(x)∨ ?R(x))∨( ?y?P(y)∧Q(z )) (换变元 )
??x(?P(x)∨ ?R(x))∨ ?y(?P(y)∧Q(z )) (扩量词辖域 )
??x?y((?P(x)∨ ?R(x))∨( ?P(y)∧Q(z )))(扩量词辖域 )
3.前束析取范式与前束合取范式：
前束析取范式,前束范式中量词后的括号内是析取范式形式。
前束合取范式,前束范式中量词后的括号内是合取范式形式。
上例的前束析取范式为,
?x?y(?P(x)∨ ?R(x)∨( ?P(y)∧Q(z )))
上例的前束合取范式为,
?x?y((?P(x)∨ ?R(x)∨ ?P(y))∧( ?P(x)∨ ?R(x)∨Q(z )))
? 本节掌握 前束范式的写法。
? 作业
? P75 (1)b)
? (2)c)
2-5 谓词演算的推理理论
推理方法：
直接推理、条件论证、反证法
所用公式,43页和 70页的 I1~I19,E1~E33
推理规则,P,T,CP,US,ES,EG,UG
? 后四个规则，是处理量词的，因为推理时
要使用不含量词的命题公式，所以要去掉
量词，如果结论有量词，还要添加量词。
? 下面介绍四个新规则：
一,全称特指规则 US
(Universal Specialization)
形式,?xA(x)?A(c)
(其中 c是论域内 指定客体 )
含义：如果 ?xA(x)为真，则在论域内 任
何指定 客体 c,都使得 A(c)为真。
作用：去掉全称量词。
要求,c不是 A(x)中的符号。
二,存在特指规则 ES(Existential Specialization)
形式,?xA(x)?A(c)
(其中 c是论域内 指定客体 )
含义：如果 ?xA(x)为真，则在论域内 指定 客体 c，
都使得 A(c)为真。
作用：去掉存在量词。
要求：⑴ c不是 A(x)中的符号。
⑵ 用 ES指定的客体 c不应该是 在此之前 用
US规则或者用 ES规则所指定的客体 c(即本次用
ES特指客体 c,不应该是以前特指的客体 )。
请看下面两个例子：
例 1,令 A(x)表示 x是自然数,B(x)表示 x是
整数。
⑴ ?x(A(x)→B(x)) P
⑵ A(c)→B(c) US 如 c=0.1
⑶ ?xA(x) P
⑷ A(c) × ES A(0.1)为 F
⑴ ?xB(x) P
⑵ B(c) ES 如 c=-1
⑶ ?xA(x) P
⑷ A(c) × ES A(-1)为 F
三,存在推广规则 EG
(Existential Generalization)
形式,A(c)??xA(x)
(其中 c是论域内 指定客体 )
含义：如果 在论域内 指定 客体 c使得
A(c)为真，则 ?xA(x)为真。
作用：添加存在量词。
要求,x不是 A(c)中的符号 。
四,全称推广规则 UG
(Universal Generalization)
形式,A(c)??xA(x)
(其中 c是论域内 任何 指定客体 )
含义：如果 在论域内 任何指定 客体 c都 使
得 A(c)为真，则 ?xA(x)为真。
作用：添加 全称 量词。
要求,x不是 A(c)中的符号。
c一定是任意 的客体，否则不可 全
称推广 。
例 1 所有金属都导电。铜是金属。
故铜导电。
令 M(x):x是金属。 C(x):x导电。 a:铜。
符号化为：
?x(M(x)→C(x)),M(a) ?C(a)
⑴ ?x(M(x)→C(x)) P
⑵ M(a)→C(a) US ⑴
⑶ M(a) P
⑷ C(a) T ⑵⑶ I11
例 2,所有自然数都是整数。有些数是自然
数。因此有些数是整数。
令 A(x)表示 x是自然数,B(x)表示 x是整数。
?x(A(x)→B(x)), ?xA(x) ? ?xB(x)
⑴ ?xA(x) P
⑵ A(c) ES ⑴
⑶ ?x(A(x)→B(x)) P
⑷ A(c)→B(c) US ⑶
⑸ B(C) T ⑵⑷ I11
⑹ ?xB(x) EG ⑸
例 2中，如果按下面方法推理，是否正确？
?x(A(x)→B(x)), ?xA(x) ? ?xB(x)
⑴ ?x(A(x)→B(x)) P
⑵ A(c)→B(c) US ⑴
⑶ ?xA(x) P
⑷ A(c) ES ⑶
⑸ B(C) T ⑵⑷ I11
⑹ ?xB(x) EG ⑸
问题在哪里？
例 3 不认识错误的人，也不能改正错误。
有些诚实的人改正了错误。所以有些诚
实的人是认识了错误的人。
设 A(x):x是 认识错误的人。
B(x):x改正了错误。 C(x):x是诚实的人。
符号化为：
?x(?A(x)→ ?B(x)),?x(C(x)∧B(x)),
? ?x(C(x)∧A(x))
?x(?A(x)→ ?B(x)),?x(C(x)∧B(x)),
? ?x(C(x)∧A(x))
⑴ ?x(C(x)∧B(x)) P
⑵ C(c)∧B(c) ES ⑴
⑶ C(c) T ⑵ I1
⑷ B(c) T ⑵ I2
⑸ ?x(?A(x)→ ?B(x))P
⑹ ?A(c)→ ?B(c) US ⑸
⑺ ??A(c) T ⑷⑹ I12
⑻ A(c) T ⑺ E1
⑼ C(c)∧A(c) T ⑶⑻ I9
⑽ ?x(C(x)∧A(x)) EG ⑼
例 4 一些病人喜欢所有医生。任何病人都不喜欢庸
医。所以没有医生是庸医。
设, P(x):x是 病人,D(x):x是 医生,
Q(x):x是 庸医,L(x,y),x喜欢 y.
符号化为,?x(P(x)∧ ?y(D(y)→ L(x,y)))，
?x(P(x)→ ?y(Q(y)→ ?L(x,y)))
???y(D(y)∧Q(y))
?x(P(x)∧ ?y(D(y)→ L(x,y))),?x(P(x)→ ?y(Q(y)→ ?L(x,y)))
???y(D(y)∧Q(y))
⑴ ?x(P(x)∧ ?y(D(y)→ L(x,y))) P
⑵ P(a)∧ ?y(D(y)→ L(a,y)) ES ⑴
⑶ P(a) T ⑵ I1
⑷ ?y(D(y)→ L(a,y)) T ⑵ I2
⑸ ?x(P(x)→ ?y(Q(y)→ ?L(x,y))) P
⑹ P(a)→ ?y(Q(y)→ ?L(a,y)) US ⑸
⑺ ?y(Q(y)→ ?L(a,y)) T ⑶ ⑹ I11
⑻ D(b)→ L(a,b) US⑷
⑼ Q(b)→ ?L(a,b) US ⑺
⑽ L(a,b) → ?Q(b) T ⑼ E18
⑾ D(b)→ ?Q(b) T ⑻⑽ I13
⑿ ?D(b)∨ ?Q(b) T ⑾ E16
⒀ ?(D(b)∧Q(b)) T ⑿ E8
⒁ ?y?(D(y)∧Q(y)) UG ⒀
⒂ ??y(D(y)∧Q(y)) T ⒁ E25
课堂练习 P79(1)d)改成：
?x(A(x)∨B(x) ),?x(B(x)→ ?C(x)),?xC(x)??x(A(x)
(1) ?x(A(x)∨B(x) ) P
(2) A(a)∨B(a) ES (1)
(3) ?x(B(x)→ ?C(x)) P
(4) B(a)→ ?C(a)) US (3)
(5) ?xC(x) P
(6) C(a) US (5)
(7 ) ?B(a) T (4)(6) I12
(8) A(a) T (2)(7) I10
(9) ?x(A(x) EG (8)
例 5 ?x(P(x)→Q(x)) ? ?xP(x)→ ?xQ(x)
用条件论证证明：
⑴ ?xP(x) P(附加前提 )
⑵ ?x(P(x)→Q(x)) P
⑶ P(a)→Q(a) ES ⑵
⑷ P(a) US ⑴
⑸ Q(a) T ⑶ ⑷ I11
⑹ ?xQ(x) EG ⑸
⑺ ?xP(x)→ ?xQ(x) CP
用反证法证明例 5：
?x(P(x)→Q(x)) ? ?xP(x)→ ?xQ(x)
⑴ ?(?xP(x)→ ?xQ(x)) P(假设前提 )
⑵ ?(??xP(x)∨ ?xQ(x)) T ⑴ E16
⑶ ?xP(x)∧ ??xQ(x) T⑵ E9
⑷ ?xP(x) T⑶ I1
⑸ ??xQ(x) T⑶ I2
⑹ ?x(P(x)→Q(x)) P
⑺ P(a)→Q(a) ES ⑹
⑻ P(a) US ⑷
⑼ Q(a) T ⑺⑻ I11
⑽ ?xQ(x) EG ⑼
⑾ ??xQ(x)∧ ?xQ(x) T⑸⑽ I9
用推理证明公式：
?y?xA(x,y)??x?yA(x,y)
⑴ ?y?xA(x,y) P
⑵ ?xA(x,b) ES ⑴
⑶ A(a,b) US ⑵
⑷ ?yA(a,y) EG ⑶
⑸ ?x?yA(x,y) UG ⑷
作业,79页 ⑴ c)d) ⑵,⑶
推理时的注意事项：
推理时注意事项：
1.注意使用 ES,US,EG,UG的限制条件。
2.对于同一个客体变元，既有带 ?也有带 ?的前提，去量词
时，应先去 ?后去 ?，这样 才可以特指同一个客体 c.
3.去量词时，该量词必须是公式的最左边的量词，且此量
词的前边 无任何符号,它的辖域作用到公式末尾。
下面的作法是错误的,正确作法是,
⑴ ?xP(x)→ ?yQ(y) P ⑴ ?xP(x)→ ?yQ(y) P
⑵ ?xP(x)→ Q(b) × ES⑴ (2)??xP(x)∨ ?yQ(y) T(1) E
(3)P(a)→ Q(b) × US(2) (3) ?x?P(x)∨ ?yQ(y) T(2) E
(4) ?x?y(?P(x)∨ Q(y)) T(3) E
(5) ?y(?P(a)∨ Q(y)) ES(4)
实际上 ?x的辖域扩 (6) ?P(a)∨ Q(b)) ES(4)
充后量词改成为 ?x (7) P(a)→ Q(b) T(5)E
下面的作法是错误的,正确作法是,
⑴ ??xP(x) P ⑴ ??xP(x) P
⑵ ?P(c) US⑴ (2) ?x?P(x) T(1)E
实际上⑴ 中不是 ?x而是 ?x (3) ?P(c) ES (2)
⑴ ?x?yP(x,y) P ⑴ ?x?yP(x,y) P
⑵ ?xP(x,c) ES⑴ (2) ?yP(a,y) US(1)
令 P(x,y):y是 x的 生母，显然 ⑵是个假命题,
另外 X是公式 A的子公式，且 X?Y,如果用 Y替换 A中 X而得
到 B，那么不一定有 A?B。例如 P∧ Q?P,而 ?(P∧ Q)??P
是不成立的。 US和 ES规则都是蕴涵式，所以不可对一个
子公式用这些规则。
4.添加量词时，也要加在公式的最左边,(即新加的量词
前也无任何符号 ！！ )且其辖域作用到公式的末尾。
第二章 小结
本章重点掌握内容：
1.各基本概念清楚。
2.会命题符号化。
3.熟练掌握等价公式和永真蕴涵式。
4.会写前束范式。
5.熟练掌握谓词逻辑的三种推理方法。
第二章 习题课
一, 命题符号化 60页 (2)
a) ?x(J(x)→ L(x)) b) ?x(L(x)∧ S(x))
c) ?x(J(x)∧ O(x)∧ V(x)) d) J(j)∧ ?O(j)∧ ?V(j)
e) ??x(L(x)→ J(x)) 或者 ?x(L(x)∧ ?J(x))
f) ?x(S(x)∧ L(x)∧ C(x))
g) ??x(C(x)∧ ?V(x)) 或者 ?x(C(x)→ V(x))
h) ?x((C(x)∧ O(x))→ L(x))
i) ??x(W(x)∧ C(x)∧ H(x))
j) ?x(W(x)∧ J(x)∧ C(x))
k) ?x(L(x)→ ?y(J(y)∧ A(x,y)))
l) ?x(S(x)∧ ?y(L(y)→ ?A(x,y)))
62页 (2)
?x?y((P(x)∧ P(y)∧ ?E(x,y))
→ ?z(L(z)∧R(x,y,z)∧ ?t((L(t)∧R(x,y,t))→E(t,z))))
(3)b)设 R(x):x是实数,G(x,y):x＞ y
?x(R(x)→ ?y(R(y)∧ G(y,x)))
c)设 R(x):x是实数,G(x,y):x＞ y
f(x,y)=x+y g(x,y)=xy
?x?y?z(R(x)∧ R(y)∧ R(z)∧ G(f(x,y),g(x,z)))
或者 ?x?y?z(R(x)∧ R(y)∧ R(z)∧ G(x+y,xz))
(5)b)设 N(x):x是数,A(x,y):y是 x的后继数
??x(N(x)∧ A(x,1))
(6)设 A(x):x是戴眼镜的,B(x):x是用功的,C(x):x是大学
生,D(x):x是大的,E(x):x是厚的,F(x):x是巨著,
A(x,y):x在看 y,a:那位,b:这本
A(a)∧ B(a)∧ C(a)∧ D(b)∧ E(b)∧ F(b)∧ A(a,b)
*补充题,
1.每个人的叔叔都是他父亲的弟弟。
设,P(x):x是人,U(x,y):y是 x的叔叔，
B(x,y):x是 y的弟弟,f(x)=x的父亲
?x(P(x)→ ?y(U(x,y)→B (y,f(x)))
2.下面是判定一个年号是否为闰年的命题,
“年号能被 4整除并且不能被 100整除的为闰年, 或者年号
能被 400整除的也是闰年,”
设 Y(x):x是年号 ; D(x,y):x可整除 y; R(x):x是闰年
?x(Y(x)→( ((D(4,x)∧ ?D(100,x))→R(x) )∨ (D(400,x) →R(x) )))
66页 (3)b)P:2>1,Q(x):x≤3,R(x):x>5,a:5,{-2,3,6}
?x(P→ Q(x))∨ R(a)?(P→ ?xQ(x))∨ R(a)
?(P→ (Q(-2)∧ Q(3)∧ Q(6)))∨ R(5)
?(T→ (T ∧ T ∧ F ))∨ F
?(T→ F)∨ F?F∨ F ?F
(4)b)对约束变元换名
?x(P(x)→(R(x)∨Q(x))) ∧ ?xR(x)→ ?zS(x,z)
??y(P(y)→(R( y)∨Q( y)))∧ ?tR(t)→ ?uS(x,u)
(5)a)对自由变元代入
(?yA(x,y)→ ?xB(x,z))∧ ?x?zC(x,y,z)
?(?yA(u,y)→ ?xB(x,v))∧ ?x?zC(x,w,z)
72页 (2)d)论域为 {1,2}
P(1) P(2) Q(1,1) Q(1,2) Q(2,1) Q(2,2)
F T T T F F
?x?y(P(x)∧ Q(x,y))
??y(P(1)∧ Q(1,y))∧ ?y(P(2)∧ Q(2,y))
?((P(1)∧ Q(1,1))∨ (P(1)∧ Q(1,2)))∧
((P(2)∧ Q(2,1))∨ (P(2)∧ Q(2,2)))
?((F∧ T)∨ (F∧ T))∧ ((T∧ F)∨ (T∧ F))
?(F∨ F)∧ (F∨ F)?F
(6)判断下面推证是否正确。
?x(A(x)→B(x))
⑴ ??x(?A(x)∨B(x))
⑵ ??x?(A(x)∧ ?B(x)
⑶ ???x(A(x)∧ ?B(x))
⑷ ??(?xA(x)∧ ?x?B(x))
⑸ ???xA(x)∨ ??x?B(x)
⑹ ???xA(x)∨ ?xB(x)
⑺ ??xA(x)→ ?xB(x)
第⑷步错，由⑶到⑷用的是公式：
?x(A(x)∧ ?B(x))?(?xA(x)∧ ?x?B(x))
无此公式，而是 ?x(A(x)∧ ?B(x))?
?xA(x)∧ ?x?B(x)，应将⑷中的 ?换成 ? 即：
?x(A(x)→B(x))
⑴ ??x(?A(x)∨B(x))
⑵ ??x?(A(x)∧ ?B(x)
⑶ ???x(A(x)∧ ?B(x))
⑷ ??(?xA(x)∧ ?x?B(x))
⑸ ???xA(x)∨ ??x?B(x)
⑹ ???xA(x)∨ ?xB(x)
⑺ ??xA(x)→ ?xB(x)
因为由公式 E18 P→ Q??Q→ ?P
?x(A(x)∧ B(x))? ?xA(x)∧ ?xB(x),
P Q
得 ?(?xA(x)∧ ?xB(x))???x(A(x)∧ B(x))
75页 (1)b)?x(??yP(x,y)→( ?zQ(z)→R(x)) )
??x(?yP(x,y)∨ (??zQ(z)∨ R(x)))
??x(?yP(x,y)∨ (?z?Q(z)∨ R(x)))
??x(?yP(x,y)∨ ?z(?Q(z)∨ R(x)))
??x?y?z(P(x,y)∨ (?Q(z)∨ R(x)))
(2)c)?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)∨ ?zR(x,y,z))
??x?P(x)∨ ?u(?zQ(u,z)∨ ?tR(u,y,t))
??x?u?z?t(?P(x)∨ (Q(u,z)∨ R(u,y,t)))
??x?u?z?t(?P(x)∨ Q(u,z)∨ R(u,y,t))
此式既是前束析取范式，也是前束合取范式。
79页 (2)a)用 CP规则证明
?x(P(x)∨ Q(x)? ?xP(x)∨ ?xQ(x)
因为 ?xP(x)∨ ?xQ(x)? ??xP(x)→ ?xQ(x)
⑴ ??xP(x) P(附加前提 )
⑵ ?x ?P(x) T ⑴ E
⑶ ?P(a) ES ⑵
⑷ ?x(P(x)∨ Q(x) P
⑸ P(a)∨ Q(a) US ⑷
⑹ Q(a) T ⑶⑸ I
⑺ ?xQ(x) EG ⑹
⑻ ??xP(x)→ ?xQ(x) CP
(3)a)所有有理数是实数，某些有理数是整数，
因此某些实数是整数。
设 Q(x):x是有理数 R(x):x是实数 I(x):x是整数
?x(Q(x)→R(x) ),?x(Q(x)∧ I(x))?
?x(R(x)∧ I(x))
⑴ ?x(Q(x)∧ I(x)) P
⑵ Q(a)∧ I(a) ES⑴
⑶ Q(a) T ⑵ I
⑷ I(a) T ⑵ I
⑸ ?x(Q(x)→R(x) ) P
⑹ Q(a)→R(a) US ⑸
⑺ R(a) T ⑶⑹ I
⑻ R(a)∧ I(a) T ⑷⑺ I
⑼ ?x(R(x)∧ I(x)) EG⑻
b)任何人如果他喜欢步行，他就不喜欢乘汽车；
每个人或者喜欢乘汽车或者喜欢骑自行车。有
的人不爱骑自行车，因此有的人不爱步行。
设 A(x):x是人,B(x):x是 喜欢步行,
C(x):x喜欢乘汽车,D(x):x喜欢骑自行车
?x(A(x)→(B(x)→ ?C(x))),
?x(A(x)→(C(x) ∨ D(x))),?x(A(x)∧ ?D(x))
? ?x(A(x)∧ ?B(x))
⑴ ?x(A(x)∧ ?D(x)) P
⑵ A(a)∧ ?D(a)) ES ⑴
⑶ A(a) T ⑵ I
⑷ ?D(a)) T ⑵ I
⑸ ?x(A(x)→(B(x)→ ?C(x))) P
⑹ A(a)→(B(a)→ ?C(a)) US ⑸
⑺ B(a)→ ?C(a)) T ⑶⑹ I
⑻ ?x(A(x)→(C(x) ∨ D(x))) P
⑼ A(a)→(C(a) ∨ D(a))) US⑻
⑽ C(a)∨ D(a) T ⑶⑼ I
⑾ C(a) T ⑷⑽ I
⑿ ?B(a) T ⑺⑾ I
⒀ A(a)∧ ?B(a)) T ⑶⑿ I
⒁ ?x(A(x)∧ ?B(x)) EG ⒀
c)每个大学生不是文科生就是理工科生，
有的大学生是优等生，小张不是理工科
生，但他是优等生，因此如果小张是大
学生，他就是文科生。
设 A(x):x是大学生,B(x):x是 文科生,
C(x):x是理工科生, D(x):x是优等生,
a:小张
?x(A(x)→( ?B(x)→C(x) )),
?x(A(x)∧ D(x))
?C(a)∧ D(a) ? A(a)→B(a)
?x(A(x)→( ?B(x)→C(x) )),?x(A(x)∧ D(x))
?C(a)∧ D(a) ? A(a)→B(A)
⑴ A(a) P(附加前提 )
⑵ ?x(A(x)→( ?B(x)→C(x) )) P
⑶ A(a)→( ?B(a)→C(a) ) US ⑵
⑷ ?B(a)→C(a) ) T ⑴⑶ I
⑸ ?C(a)∧ D(a) P
⑹ ?C(a) T ⑸ I
⑺ ??B(a) T ⑷⑹ I
⑻ B(a) T ⑺ E
⑼ A(a)→B(a) CP
补充题,小杨、小刘和小林为高山俱乐部成员，该俱乐
部的每个成员是个滑雪者或登山者。没有一个登山者喜
欢雨。而所有滑雪者都喜欢雪。凡是小杨喜欢的，小刘
就不喜欢。小杨喜欢雨和雪。试证明该俱乐部是否有个
是登山者而不是滑雪者的成员。如果有，他是谁？
设,M(x):x是高山俱乐部成员。 H(x):x是滑雪者。
D(x):x是登山者。 L(x,y):x喜欢 y。
a:小杨； b:小刘； c:小林； d:雨； e:雪。
命题符号化为：
M(a),M(b),M(c),?x(M(x)→( H(x)∨ D(x))),
??x(D(x)∧ L(x,d)),?x(H(x)→L (x,e))
?x(L(a,x)→ ?L(b,x)),L(a,d)∧ L(a,e)
⑴ L(a,d)∧ L(a,e) P
⑵ L(a,e) T ⑴
⑶ ?x(L(a,x)→ ?L(b,x)) P
⑷ L(a,e)→ ?L(b,e)) US ⑶
⑸ ?L(b,e)) T ⑵ ⑷ I11
⑹ ?x(H(x)→L (x,e)) P
⑺ H(b)→L (b,e)) US ⑹
⑻ ?H(b) T ⑸ ⑺ I12
⑼ ?x(M(x)→( H(x)∨ D(x))) P
⑽ M(b)→( H(b)∨ D(b)) US ⑼
⑾ M(b) P
⑿ H(b)∨ D(b) T ⑽ ⑾ I11
⒀ D(b) T ⑻ ⑿ I10
⒁ D(b)∧ ?H(b) T ⑻ ⒀
第二章 谓词逻辑
到此结束
