河北工业大学计算机科学技术与软件学院离散数学
Discrete Mathematics
郭永芳
guoyongfang.2006@yahoo.com.cn
Guoyongfang.2006@yahoo.com.cn
在命题逻辑中,把命题分解到原子命题为止,认为原子命题是不能再分解的,仅仅研究以原子命题为基本单位的复合命题之间的逻辑关系和推理 。 这样,有些推理用命题逻辑就难以确切地表示出来 。 例如,著名的亚里士多德三段论苏格拉底推理：
谓词逻辑
Guoyongfang.2006@yahoo.com.cn
所有的人都是要死的，
苏格拉底是人，
所以苏格拉底是要死的。
根据常识，认为这个推理是正确的。但是，若用
Ls来表示，设 P,Q和 R分别表示这三个原子命题，则有
P,Q?R
Guoyongfang.2006@yahoo.com.cn
然而,(P∧ Q)→ R并不是永真式,故上述推理形式又是错误的 。 一个推理,得出矛盾的结论,
问题在哪里呢? 问题就在于这类推理中,各命题之间的逻辑关系不是体现在原子命题之间,
而是体现在构成原子命题的内部成分之间,即体现在命题结构的更深层次上 。 对此,Ls是无能为力的 。 所以,在研究某些推理时,有必要对原子命题作进一步分析,分析出其中的个体词,谓词和量词,研究它们的形式结构的逻辑关系,正确的推理形式和规则,这些正是谓词逻辑 （ 简称为 Lp） 的基本内容 。
Guoyongfang.2006@yahoo.com.cn
如有句子：
张红 是一个大学生 ；
王南 是一个大学生 ；
李华 是一个大学生 。
则在命题中必须要用三个命题 P,Q,R
来表示。
谓词逻辑
Guoyongfang.2006@yahoo.com.cn
在 Lp中,命题是具有真假意义的陈述句 。 从语法上分析,一个陈述句由主语和谓语两部分组成 。
在 Lp中,为揭示命题内部结构及其不同命题的内部结构关系,就按照这两部分对命题进行分析,并且把主语称为个体或客体,把谓语称为谓词 。
Guoyongfang.2006@yahoo.com.cn
一、谓词定义 在句子中，可以独立存在的客体称为个体词，而用以刻划客体的属性或客体之间的关系即是谓词。
谓词逻辑
Guoyongfang.2006@yahoo.com.cn
1.张三是大学生。
2.李四是大学生。
3.7是素数。
4.锻炼身体是个好习惯。
5.7小于 10。
6.张三和李四是好朋友。
7.哥白尼指出地球围绕太阳转。
谓词逻辑
Guoyongfang.2006@yahoo.com.cn
2－ 1 谓词的概念与表示个体词用 a,b,c,...x,y,z,a1,a2,a3等表示，谓词用 A,B,C,...P,Q，
R,…,A1,A2,A3,…,等表示。
Guoyongfang.2006@yahoo.com.cn
1.张三是大学生。 P（ c）
2.李四是大学生。 P（ a）
3.7是素数。 Q（ a）
4.锻炼身体是个好习惯。 R（ a）
5.7小于 10。 X（ a,b）
6.张三和李四是好朋友。 F（ a,b）
7.哥白尼指出地球围绕太阳转。 S（ a,b,c）
谓词逻辑
Guoyongfang.2006@yahoo.com.cn
谓词的概念与表示设,H(X):X是人
D(x),x是要死的。
上述三段论可翻译为：
则有,H(x)→ D(x),H(S)? D(S)
Guoyongfang.2006@yahoo.com.cn
谓词填式,把谓词字母后填以客体所得式子称为谓词填式，谓词和谓词填式是两个不同的概念，谓词不是命题，而谓词填式是命题。
谓词的概念与表示
Guoyongfang.2006@yahoo.com.cn
表示具体或特定的个体词称为 个体常量,一般个体词常量用带或不带下标的小写英文字母 a,b,C,……,a1,a2,a3.,…… 表示。
表示抽象的或泛指的个体词称为 个体变量,一般用带或不带下标的小写英文字
x,y,z,.…,x1,x2,x3,…… 表示。
个体词的取值范围称为 个体域 或 论域,常用 D
表示。而宇宙间的所有个体域聚集在一起所构成的个体域称为 全总个体域 。
谓词的概念与表示
Guoyongfang.2006@yahoo.com.cn
设有如下命题：
P,5是一个实数。 Q,3大于 2。
R,点 A位于点 B和点 C之间。 S,王同高于李浩。
解,设有如下 谓词,
R(x),x是一个实数。 G(x,y),x大于 y。
B(x,y,z),点 x位于点 y和点 z之间。
H(x,y),x高于 y。
并设 a1表示 A,a2表示 B,a3表示 C； a表示王同,b表示李浩 。
则上述四个命题可表示如下：
P,R(5)； Q:G(3,2)；
R:B(a1,a2,a3)； S:H(a,b)。
谓词的概念与表示
Guoyongfang.2006@yahoo.com.cn
几个结论：
1) 谓词中个体词的顺序是十分重要的，不能随意变更。
2) 一元谓词用以描述某一个个体的某种特性或性质，而 n元谓词则用以描述 n个个体之间的关系。
3) 0元谓词 (不含个体词的 )实际上就是一般的命题。
谓词的概念与表示
Guoyongfang.2006@yahoo.com.cn
一、命题函数定义 由一个谓词，一些客体变元组成的表达式称为 简单命题函数可见,n元谓词就是有 n个客体变元的命题函数，当 n=0时，称为 o元谓词，其本身就是一个命题,n=1时，称为一元谓词。
2－ 2 命题函数与量词
Guoyongfang.2006@yahoo.com.cn
定义 由一个或 n个简单命题函数以及逻辑联结词组合而成的表达式称为复合命题函数。
简单命题函数和复合命题函数，统称为命题函数。
Guoyongfang.2006@yahoo.com.cn
逻辑联结词 ┐,∧,∨,→,?与 命题演算中的解释完全相同。
例如,S（ x）,x学习好
W（ x）,x工作好
2－ 2 命题函数与量词
Guoyongfang.2006@yahoo.com.cn
n元谓词不是命题，只有其中的个体变元用特定个体或个体常元替代时，才能成为一个命题。
但个体变元在哪些论域取特定的值，对命题的真值极有影响。 例如，令 S(x),x是大学生。
若 x的论域为某大学的计算机系中的全体同学，
则 S(x)是真的；若 x的论域是某中学的全体学生，则 S(x)是假的；若 x的论域是某剧场中的观众，且观众中有大学生也有非大学生的其它观众，则 S(x)是真值是不确定的。
Guoyongfang.2006@yahoo.com.cn
例如
( P（ x,y） ∧ P（ y,z） ) → P（ x,z）
Guoyongfang.2006@yahoo.com.cn
命题函数确定为命题，与客体变元的论述范围有关。在命题函数中，客体变元的论述范围称作个体域。个体域可以是有限的，也可以是无限的，把各种个体域综合在一起作为论述范围的域称全总个体域。
Guoyongfang.2006@yahoo.com.cn
量词在上述三段论的例子中，如要对句子：
H(x)→ D(x)求否定，则有：
┐ (H(x)→ D(x))＝ ┐┐ H(ｘ )∧┐ Ｄ (ｘ )＝ H(ｘ )∧┐
Ｄ (ｘ )
上述式子说明：,命题 P”的否定是：,所有的人都不死,。
但这与人们在日常生活中对命题：,所有人都是要死的,。
的否定为：,并非一切的人都是要死的,。
显然相差甚远。
其原因在于：命题 P的确切含义是：
,对任意的 x，如果 x是人，则 x是要死的,。
但 H(x)→ D(x)并没有确切地表示出,对任意 x”这个意思，
Guoyongfang.2006@yahoo.com.cn
量词的引入
P（ x）：所有人都聪明
┐ P（ x）：所有人都不聪明
Q（ x）：有些人聪明
┐ Q（ x）：有些人不聪明
Guoyongfang.2006@yahoo.com.cn
命题函数与量词符号化下述命题：
1） 每一个苹果 都是红的。
2） 任意一个整数 都是正整数或负整数。
3） 有一些实数是 有理数。
4） 有一些人 是很聪明的。
5） 对每一个实数,都有 x2+2x+1=(x+1)2。
6） 有一些实数,使得 x+6=5。
上述每一个描述量词的语句下划有,下划线,。
Guoyongfang.2006@yahoo.com.cn
解：设 R(x),x是红的；
P(x),x是正整数； N(x),x是负整数；
Q(x),x是有理数； C(x),x是聪明的；
L(x),x2+2x+1=(x+1)2；
M(x),x+6=5。
1) R(x) (对任意的苹果 )
2) P(x)∨N(x) (对任意的整数 )
3) Q(x) ((对有一些实数 )
4) C(x) (对有一些人 )
5) L(x) (对任意实数 )
6) M(x) (对有一些实数 )
则有：
命题函数与量词
Guoyongfang.2006@yahoo.com.cn
利用 n元谓词和它的论域概念，有时还是不能用符号来很准确地表达某些命题，例如 S(x)表示
x是大学生，而 x的个体域为某单位的职工，那么 S(x)可表示某单位职工都是大学生，也可表示某单位有一些职工是大学生，为了避免理解上的歧义，在 Lp中，需要引入用以刻划,所有的,,,存在一些,等表示不同数量的词，即量词。
Guoyongfang.2006@yahoo.com.cn
上述一系列例子，都仅仅只符号化了一部分内容，而对句子中的,对每一个,,,对任意的,,,有一些,等等无法用谓词来表示，这些都是与个体词的数量有关的语句。为了把它们符号化，引进如下两个符号：
(?x):所有的 x； (?x)：有些 x；
任意的 x； 至少有一个 x；
一切的 x； 存在 x；
每一个 x； 等等。 等等。
Guoyongfang.2006@yahoo.com.cn
定义 (?x)称为全称量词 。 (?x)为存在量词,其中的 x称为作用变量 。 一般将其量词加在其谓词之前，记为
(?x)F(x),(?x)F(x),此时,F(x)称为全称量词和存在量词的辖域 。
Guoyongfang.2006@yahoo.com.cn
1) (?x)R(x) (x?{苹果 })
2) (?x)(P(x)∨ N(x)) (x?{整数 })
3) (?x)Q(x) (x?{实数 })
4) (?x)C(x) (x?{人 })
5) (?x)L(x) (x?{实数 })
6) (?x)M(x) (x?{实数 })
三段论中的 P也可表示为,(?x)(H(x)→ D(x))。
在前面的例中,利用量词则有：
命题函数与量词
Guoyongfang.2006@yahoo.com.cn
从书写上十分不便，总要特别注明个体域。
在同一个比较复杂的句子中，对于不同命题函数中的个体可能属于不同的个体域，此时无法清晰表达。
如讨论求上述例中 (1)和 (3)的合取而得的新命题有：
(x)R(x)∧ (?x)Q(x)。
其中，全称量词中的 x?｛苹果｝，存在量词中的 x?｛实数｝。
命题函数与量词
Guoyongfang.2006@yahoo.com.cn
有时，由于个体域的注明不清楚，造成无法确定其真值。对于同一个公式，不同的个体域有可能带来不同的真值。如 (?x)(x＋ 6＝ 5)，
(1)、在实数范围内时，确有 x＝ -1
使得 x＋ 6＝ 5，因此,(?x)(x＋ 6＝ 5)为
,真,。
(2)、在正整数范围内时，则找不到任何 x，使得 x＋ 6＝ 5为,真,,所以，
(?x)(x＋ 6＝ 5)为,假,。
命题函数与量词
Guoyongfang.2006@yahoo.com.cn
对于全称量词，刻划其对应个体域的特性谓词作为蕴涵的前件加入。
对于存在量词，刻划其对应个体域的特性谓词作为合取式之合取项加入。
基于上述情况，必要对个体域进行统一，全部使用全总个体域，此时，对每一个句子中个体变量的变化范围用一 特性谓词 刻划。而统一成 全总个体域 后，此全总个体域在谓词公式中就不必特别说明，常常省略不记。同时，这种特性谓词在加入到命题函数中时必定遵循如下原则：
命题函数与量词
Guoyongfang.2006@yahoo.com.cn
解,A(x),x是苹果； (?x)(A(x)→ R(x))
I(x),x是整数 (?x)(I(x)→ (P(x)∨ N(x)))
R(x),x是实数； (?x)(R(x)∧ Q(x))
H(x),x是人； (?x)(H(x)∧ C(x))
R(x),x是实数； (?x)(R(x)→ L(x))
R(x),x是实数； (?x)(R(x)∧ M(x))
对于前面例中的例子运用用特性谓词描述。
上述三段论可完整翻译为：
(?x)(H(x)→ D(x)),H(S),D(S)
┐ (?x)(H(x)→ D(x))＝ (?x)(H(ｘ )∧┐ Ｄ (ｘ ))
命题函数与量词
Guoyongfang.2006@yahoo.com.cn
一,谓词公式定义 谓词公式定义为
（ 1） 原子谓词公式是合式公式；
（ 2） 若 A是谓词公式,则 （?A） 也是合式公式；
（ 3） 若 A,B是谓词公式,则 （ A∨ B）,
（ A∧ B）,（ A→ B）,（ A?B） 也是合式公式；
（ 4） 若 A是合式公式,x是 A中出现的任何变元,
则 (Vx) A和 (?x) A也是合式公式 。
（ 5） 有限次地使用 （ 1） ~（ 4） 所得到的也是合式公式 。
Guoyongfang.2006@yahoo.com.cn
谓词公式与翻译二、翻译翻译：将自然语言表示的命题符号化方法：首先找出谓词，选择合适的联结词，再确定使用的量词。
Guoyongfang.2006@yahoo.com.cn
谓词公式与翻译符号化下述语句：
1） 有会说话的机器人。
2） 每个实数都存在比它大的另外的实数。
3） 每个人都有某些专长。
4） 尽管有人很聪明，但未必一切人都聪明
。
Guoyongfang.2006@yahoo.com.cn
1） M(x),x是机器人。 F(x),x会说话。则 有：
(?x)(M(x)∧ F(x))。
2） R(x),x是实数。 L(x,y),x小于 y。 则有：
(?x)(R(x)→ (?y)(R(y)∧ L(x,y)))
3） M(x),x是人。 N(x),是专长。
P(x,y),x都有 y。 则有,
(?x)(M(x)→ (?y)(N(y)∧ P(x,y)))。
4） M(x),x是人。 C(x),x很聪明。 则有,
(?x)(M(x)∧ C(x))∧┐ (?x)(M(x)→ C(x))
谓词公式与翻译
Guoyongfang.2006@yahoo.com.cn
设 P(x):x是素数
I(x):x是整数
Q(x,y):x+y=0
用语句描述下述句子，并判断其真假值。
1) (?x)(I(x)→ P(x))
2) (?x)(I(x)∧ P(x))
3) (?x)(?y)(I(x)∧ I(y)→ Q(x,y))
4) (?x)(I(x)→ (?y)(I(y)∧ Q(x,y)))
5) (?x)(?y)(I(x)∧ (I(y)→ Q(x,y)))
谓词公式与翻译
Guoyongfang.2006@yahoo.com.cn
解：
1)可描述为：,对任意的整数 x,x一定是素数,,真值为,假,。
2)可描述为：,存在一些整数 x,x是素数,,
真值为,真,。
3)可描述为：,对任意的整数 x,y,都有
x+y=0”,真值为,假,。
4)可描述为：,对任意的整数 x,都存在着整数
y,使得 x+y=0”,真值为,真,。
5)可描述为：,存在着整数 x,使得对任意的整数 y,都有 x+y=0”,真值为,假,。
谓词公式与翻译
Guoyongfang.2006@yahoo.com.cn
从上面的例子可知，如有多个量词，则读的顺序按从左到右的顺序，即：
(?x)(?y)G(x,y)＝ (?x)((?y)(G(x,y))
另外，量词对变元的约束，往往与量词的次序有关，不同的量词次序，可以产生不同的真值，此时对多个量词同时出现时，
不能随意颠倒它们的顺序，颠倒后会改变原体的含义。如上例中 4)和 5)。
谓词公式与翻译
Guoyongfang.2006@yahoo.com.cn
2-4 变元的约束一、自由变元与约束变元量词后所跟的 x叫做量词的指导变元或作用变元,P(x)叫做相应量词的作用域或辖域。在作用域中 变元 x的 出现 称 为约束出现,此时的变元 x称为约束变元 (量 )。
若 x的出现不是约束出现，则称它为自由出现,此时的变元 x称为自由变元 (量 )。
Guoyongfang.2006@yahoo.com.cn
例：
(?y)(P(y,z)→Q(x,y) )∨R(y).
(?x)(P(x)→Q(x)),
(?x)(P(x))→ (?y)(R(x,y))
(?x)(P(x)→R(x)) ∧ (?y)Q(x,y)
Guoyongfang.2006@yahoo.com.cn
解：在 1)中,P(y,z)与 Q(x,y)中的 y为约束变元,x,z为自由变元,R(y)中的 y为自由变元。
在 2)中,P(x)和 Q(x)中的 x都为约束变元。
在 3)中,P(x)中的 x和 R(x,y)中的 y都为约束变元,R(x,y)中的 x为自由变元。
在 4)中,P(x),R(x)中的 x和 Q(x,y)中的
y都是约束变元,Q(x,y)中的 x为自由变元。
Guoyongfang.2006@yahoo.com.cn
从约束变元的概念看,P（ x1，
x2,… xn）是 n元谓词，它有 n个互相独立的自由变元，若对其中 k个变元进行约束则成了 n-k元谓词，因此，谓词公式中如果没有自由变元出现，则该式成为一个命题。
Guoyongfang.2006@yahoo.com.cn
二、约束变元的改名规则 1(约束变元的改名规则 )：
1)、将量词中出现的变元以及该量词辖域中此变量之所有约束出现都用新的变元替换。
2)、新的变元一定要有别于改名辖域中的所有其它变量。
Guoyongfang.2006@yahoo.com.cn
变元的约束在公式 (?x)(P(x)→ R(x,y))∧ Q(y)中，变元 x是约束变元,y是自由变元。
利用规则 1对 x进行改名，则,
(?z)(P(z)→ R(z,y))∧ Q(y)
不合法的改名有,
(?z)(P(z)→ R(x,y))∧ Q(y)
(?y)(P(y)→ R(y,y))∧ Q(y)
Guoyongfang.2006@yahoo.com.cn
三,自由变元的代入规则 2(自由变元的代入规则 )：
1)、将公式中出现该自由变元的每一处都用新的变元替换。
2)、新变元不允许在原公式中以任何约束形式出现。
Guoyongfang.2006@yahoo.com.cn
变元的约束利用规则 2对 (?x)(P(x)→ R(x,y))∧ Q(y) 中的 y进行代入，则,
(?x)(P(x)→ R(x,z))∧ Q(z)
不合法的代入有,(?x)(P(x)→ R(x,y))∧ Q(z)
(?x)(P(x)→ R(x,x))∧ Q(x)
Guoyongfang.2006@yahoo.com.cn
量词作用域中的约束变元，当论域的元素是有限时，客体变元的所有可能取代是可以枚举的。
设论域元素为 a1,a2,…,an
则 (?x)P(x)=P(a1) ∧ P(a2) … ∧ P(an)
(? x)P(x)=P(a1) ∨ P(a2) … ∨ P(an)
Guoyongfang.2006@yahoo.com.cn
变元的约束
1,其中,①,个体域为 D＝ {2,3}；
.a指定为,2；
.P(2)=1,P(3)=0
则有,P(a)∧ (?x)P(x)
＝ P(2)∧(P(2)∧P(3)) ＝ 1∧(1∧0) ＝ 0
(?x)P(x)→P(a)
＝ (P(2)∧P(3))→P(2) ＝ (1∧0)→1 ＝ 1。
求公式,P(a)∧ (?x)P(x)和 (?x)P(x)→P(a) 的真值。
Guoyongfang.2006@yahoo.com.cn
2,其中,①,个体域为 D＝ {1,2,3,4,5,6,7,8,9}；
②,a指定为,5；
③,P(x)指定为 1,x>0。
则 有,P(a)∧ (?x)P(x)
＝ P(5)∧(P(1)∧P(2)∧....∧P(9))
＝ 1∧(1∧1∧....∧1) ＝ 1；
(?x)P(x)→P(a)
＝ (P(1)∧P(2)∧....∧P(9))→P(5)
＝ (1∧1∧....∧1)→1 ＝ 1。
变元的约束
Guoyongfang.2006@yahoo.com.cn
2-5 谓词演算的等价式与蕴含式在谓词公式中常包含命题变元和客体变元，当客体变元有确定的客体所取代，
命题变元用确定的命题所取代时，就称作为谓词公式赋值。一个谓词公式经过赋值以后，就成为具有确定真值 T或 F的命题。
Guoyongfang.2006@yahoo.com.cn
定义,给定任何两个谓词公式 wffA和
wffB，设它们有共同的个体域 E，若对 A
和 B的任一组变元进行赋值，所得命题的真值相同，则称谓词公式 A和 B在 E上是等价的，并记做 A?B。
Guoyongfang.2006@yahoo.com.cn
定义,给定任意谓词公式 wffA，其个体域为 E，
对于 A的所有赋值,wffA都为真，则称 wffA
在 E上是有效的（或永真的）。
定义,给定任意谓词公式 wffA，其个体域为 E，
对于 A的所有赋值,wffA都为假，则称 wffA
在 E上是不可满足的（或永假的）。
定义,给定任意谓词公式 wffA，其个体域为 E，
对于 A的所有赋值中至少有一种赋值为真，则称 wffA在 E上是可满足的。
Guoyongfang.2006@yahoo.com.cn
谓词演算的等价式与蕴含式
1.命题公式的推广将命题演算中的等价公式表和蕴含式表推广到谓词演算中使用。
例,(?x)(P(x)→ Q(x))
(?x)(┐ P(x)∨ Q(x))
(?x)P(x)∨ (?y)R(x,y)
┐ (┐ (?x)P(x)∧ ┐ (?y)R(x,y))
(?x)H(x,y)∧ ┐ (?x)H(x,y)?F
Guoyongfang.2006@yahoo.com.cn
谓词演算的等价式与蕴含式
2.量词与联结词 ┐ 之间的关系例 1)不是所有人今天来上课。
┐ (?x)P(x)
2)存在一些人今天没有来上课。
(?x)┐ P(x)
3)不是存在一些人今天来上课。
┐ (?x)P(x)
4)所有的人今天都没有来上课。
(?x)┐ P(x)
Guoyongfang.2006@yahoo.com.cn
谓词演算的等价式与蕴含式得到了公式：
┐ (?x)P(x)? (?x) ┐ P(x)
(?x)┐ P(x)?┐ (?x)P(x)
约定：出现在量词之前的否定，不是否定该量词，而是否定被量化了的整个命题。
Guoyongfang.2006@yahoo.com.cn
规则,将量词前面的 ┐ 移到量词的后面去时，存在量词改为全称量词，全称量词改为存在量词，反之，若将量词后面的否定 ┐ 移到量词的前面去时，也要作相应的改变，这种量词与 ┐ 的关系是普遍成立的 。
Guoyongfang.2006@yahoo.com.cn
在有限个体域 D = {a1,a2,…,an}中消除量词：
(1),(?x)A(x)? A(a1)?A(a2)?…?A(an)
(2),(?x)A(x)? A(a1)?A(a2)?…?A(an)
谓词演算的等价式与蕴含式
Guoyongfang.2006@yahoo.com.cn
谓词演算的等价式与蕴含式
3.量词作用域的扩张与收缩
(?x)(A(x)∨ B)?((?x)A(x)∨ B)
(?x)(A(x)∧ B)?((?x)A(x)∧ B)
(?x)(A(x)∨ B)?((?x)A(x)∨ B)
(?x)(A(x)∧ B)?((?x)A(x)∧ B)
Guoyongfang.2006@yahoo.com.cn
((?x)A(x) → B)? (?x)(A(x) → B)
((?x)A(x) → B)? (?x)(A(x) → B)
(B → (?x)A(x))? (?x)(B → A(x))
(B → (?x)A(x))? (?x)(B → A(x))
Guoyongfang.2006@yahoo.com.cn
谓词演算的等价式与蕴含式
4.量词与命题联结词之间的一些等价式
(?x)(A(x)∧ B(x))
(?x)A(x)∧(?x)B(x)
(?x)(┐ A(x)∧ ┐ B(x))
(?x)(┐ A(x))∧(?x)(┐ B(x))
(?x)(A(x)∨ B(x))
(?x)A(x)∨ (?x)B(x)
(?x)(┐ A(x)∨ ┐ B(x))
(?x)(┐ A(x))∨ (?x)(┐ B(x))
Guoyongfang.2006@yahoo.com.cn
谓词演算的等价式与蕴含式
5.量词与命题联结词之间的一些蕴含式
(?x)A(x)∨ (?x)B(x)
(?x)(A(x)∨ B(x))
(?x)(┐ A(x))∨ (?x)(┐ B(x))
(?x)(┐ A(x)∨ ┐ B(x))
(?x)(A(x)∧ B(x))
(?x)A(x)∧(?x)B(x)
┐ ((?x)A(x)∧(?x)B(x))
┐ (?x)(A(x)∧ B(x))
Guoyongfang.2006@yahoo.com.cn
谓词演算的等价式与蕴含式类似的有：
(?x)(A(x)→ B(x))
(?x)A(x)→ (?x)B(x)
(?x)(A(x)? B(x))
(?x)A(x)?(?x)B(x)
Guoyongfang.2006@yahoo.com.cn
谓词演算的等价式与蕴含式
6.多个量词的使用全称量词与存在量词在公式中出现的次序，不能随意更换。
(?x)(?y)A(x,y) (?y)(?x)A(x,y)
(?x)(?y)A(x,y) (?y)(?x)A(x,y)
(?x)(?y)A(x,y) (?y)(?x)A(x,y)
(?x)(?y)A(x,y) (?y)(?x)A(x,y)
Guoyongfang.2006@yahoo.com.cn
E23 (?x)(A(x)∨ B(x))?(?x)A(x)∨ (?x)B(x))
E24 (?x)(A(x)∧ B(x))?(?x)A(x)∧(?x)B(x)
E25 ┐ (?x)A(x)?(?x)┐ A(x)
E26 ┐ (?x)A(x)?(?x)┐ A(x)
E27 (?x)(A∧ B(x))?A∧(?x)B(x))
E28 (?x)(A∨ B(x))?A∨ (?x)B(x))
E29 (?x)(A∨ B(x))?A∨ (?x)B(x))
E30 (?x)(A∧ B(x))?A∧(?x)B(x))
E31 (?x)(A(x)→ B(x))?(?x)A(x)→ (?x)B(x)
E32 (?x)A(x)→ B?(?x)(A(x)→ B)
谓词演算的等价式与蕴含式
Guoyongfang.2006@yahoo.com.cn
E33 (?x)A(x)→ B?(?x)(A(x)→ B)
E34 A→ (?x)B(x)?(?x)(A→ B(x))
E35 A→ (?x)B(x)?(?x)(A→ B(x))
I17 (?x)A(x)∨ (?x)B(x)=> (?x)(A(x)∨ B(x))
I18 (?x)(A(x)∧ B(x))=> (?x)A(x)∧(?x)B(x)
I19 (?x)A(x)→ (?x)B(x)=> (?x)(A(x)→ B(x))
谓词演算的等价式与蕴含式
Guoyongfang.2006@yahoo.com.cn
作业
P71：
2-5习题 1(c),2（ d）
Guoyongfang.2006@yahoo.com.cn
2－ 6 前束范式定义,一个公式，如果量词均在全式的开头，它们的作用域，延伸到整个公式的末尾，则该公式叫做前束范式。
例,(?x)(?y)(?z)(A(x,y)→ B(z))
(?y)(?z)(A(y)∨ B(z))
Guoyongfang.2006@yahoo.com.cn
前束范式定理,任意一个谓词公式，均和一个前束范式等价。
方法：
否定深入变元换名，量词提前
Guoyongfang.2006@yahoo.com.cn
例 1 把公式 (?x)P(x)→ (?x)Q(x)转化为前束范式解,(?x)P(x)→ (?x)Q(x)
┐ (?x)P(x)∨ (?x)Q(x)
(?x)┐ P(x)∨ (?x)Q(x)
(?x)(┐ P(x)∨ Q(x))
前束范式
Guoyongfang.2006@yahoo.com.cn
例 2 把公式
(?x)(?y)((?z)(P(x,z)∧ P(y,z))→ (?u)Q(x,y,u))转化为前束范式解,(?x)(?y)((?z)(P(x,z)∧ P(y,z))→ (?u)Q(x,y,u))
(?x)(?y)(┐ (?z)(P(x,z)∧ P(y,z))∨ (?u)Q(x,y,u))
(?x)(?y)((?z)┐ (P(x,z)∧ P(y,z))∨ (?u)Q(x,y,u))
(?x)(?y)((?z)(┐ P(x,z)∨ ┐ P(y,z))∨ (?u)Q(x,y,
u))
(?x)(?y)(?z)(?u)(┐ P(x,z)∨ ┐ P(y,z)∨ Q(x,y,u))
前束范式
Guoyongfang.2006@yahoo.com.cn
前束范式定义,一个 wffA如果具有如下形式称为前束合取式。
(? v1) (? v2) … (? vn)[(A11∨ A12∨ … ∨ A1l1)
∧ (A21∨ A22∨ … ∨ A2l2) ∧ … ∧
(Am1∨ Am2∨ … ∨ Amlm)]
可能为?或?,Aij是原子公式或其否定。
定理,每一个 wffA都可转化为与其等价的前束合取范式。
Guoyongfang.2006@yahoo.com.cn
前束范式方法：
取消多余量词换名消去条件联结词否定深入量词提前
Guoyongfang.2006@yahoo.com.cn
例 3 把公式
(?x)[(?y)P(x)∨ (?z)Q(z,y)→ ┐ (?y)R(x,y)]转化为前束合取范式解,(?x)[(?y)P(x)∨ (?z)Q(z,y)→ ┐ (?y)R(x,y)]
(?x)[P(x)∨ (?z)Q(z,y)→ ┐ (?y)R(x,y)]/取消多余量词
(?x)[P(x)∨ (?z)Q(z,y)→ ┐ (?w)R(x,w)]/换名
(?x)[┐ (P(x)∨ (?z)Q(z,y))∨ ┐ (?w)R(x,w)]/消去条件联结词
(?x)[(┐ P(x)∧ ┐ (?z)Q(z,y) )∨ ┐ (?w)R(x,w)]/否定深入
(?x)[(┐ P(x)∧ (?z)┐ Q(z,y) )∨ (?w) ┐ R(x,w)]
(?x)(?z)(?w)[(┐ P(x)∧ ┐ Q(z,y) )∨ ┐ R(x,w)]/量词提前
(?x)(?z)(?w)[(┐ P(x)∨ ┐ R(x,w))∧ (┐ Q(z,y) )∨
┐ R(x,w)]
前束范式
Guoyongfang.2006@yahoo.com.cn
前束范式定义,一个 wffA如果具有如下形式称为前束析取式。
(? v1) (? v2) … (? vn)[(A11∧ A12∧ … ∧ A1l1)
∨ (A21∧ A22∧ … ∧ A2l2)∨ … ∨
(Am1∧ Am2∧ … ∧ Amlm)]
可能为?或?,Aij是原子公式或其否定。
定理,每一个 wffA都可转化为与其等价的前束析取范式。
Guoyongfang.2006@yahoo.com.cn
作业
P75,2-6习题
1（ b）,2（ d）
Guoyongfang.2006@yahoo.com.cn
2-7谓词演算的推理理论消去和添加量词规则：
US(全称指定规则 ),(?x)G(x)?G(c)
ES(存在指 定 规则 ),(?x)G(x)?G(c)
UG(全称推广规则 ),G(y)?(?x)G(x)
EG(存在推广规则 ),G(c)?(?x)G(x)
Guoyongfang.2006@yahoo.com.cn
有关规则 US，实际可书写形式：
(?x)G(x)?G(c)
成立的条件是：
x是 G(x)中自由出现的个体变量 。
c为任意的个体常量 。
谓词演算的推理理论
Guoyongfang.2006@yahoo.com.cn
谓词演算的推理理论
(?x)G(x)?G(c)
成立的条件是：
x是 G(x)中自由出现的个体变量。
在 G(x)中，变元 x的每一次自由出现都用相同的个体常量 c代入。
c是使 G(x)为真的特定的个体常量。
此 c是在该推导之前从未使用过的。
Guoyongfang.2006@yahoo.com.cn
谓词演算的推理理论
G(y)?(?x)G(x)
成立的条件和限制是：
y是 G(y)中自由出现的个体变量。且 y取遍整个个体域时，
都有 G(y)为真。
对 G(y)中不满足假设前提 (使 G(y)为真 )的自由变元 y不能使用规则 UG。
添加的量词 (?x)中的 x和取代 y的 x不能在 G(y)中以约束身份出现。
对于曾经由使用规则 ES所得之公式中原来的约束变元不能使用规则 UG。
Guoyongfang.2006@yahoo.com.cn
谓词演算的推理理论该规则有形式：
G(c)?(?x)G(x)
成立的条件和限制是：
c是使 G(c)为真的特定的个体常量。
取代 c的 x和添加的量词 (?x)中的 x不能在 G(c))中以任何约束出现。
Guoyongfang.2006@yahoo.com.cn
谓词演算的推理理论在推导的过程中，可以引用命题演算中的规则 P、规则 T、
规则 CP 。
为了在推导过程中消去量词，可以引用规则 US和规则 ES来消去量词。
当所要求的结论可能被定量时，此时可引用规则 UG和规则
EG将其量词加入。
证明时可采用如命题演算中的直接证明方法和间接证明方法。
在推导过程中，对消去量词的公式或公式中没含量词的子公式，完全可以引用命题演算中的基本等价公式和基本蕴涵公式。
Guoyongfang.2006@yahoo.com.cn
谓词演算的推理理论在推导过程中，对含有量词的公式可以引用谓词中的基本等价公式和基本蕴涵公式。
在推导过程中，如既要使用规则 US又要使用规则 ES消去公式中的量词 (只要有可能，我们总是先使用规则
ES，再使用规则 US)。然后再使用命题演算中的推理规则，最后使用规则 UG或规则 EG引入量词，得到所要的结论。
如一个变量是用规则 ES消去量词,对该变量在添加量词时,则只能使用规则 EG,而不能使用规则 UG;如使用规则 US消去量词,对该变量在添加量词时,则可使用规则 EG和规则 UG。
Guoyongfang.2006@yahoo.com.cn
谓词演算的推理理论如有两个含有存在量词的公式，当用规则 ES消去量词时，不能选用同样的一个常量符号来取代两个公式中的变元，而应用不同的常量符号来取代它们。
在用规则 US和规则 ES消去量词时，此量词必须位于整个公式的最前端。
在 添加的量词 (?x),(?x)时，所选用的 x不能在 公式 G(c)中以任何约束出现。
Discrete Mathematics
郭永芳
guoyongfang.2006@yahoo.com.cn
Guoyongfang.2006@yahoo.com.cn
在命题逻辑中,把命题分解到原子命题为止,认为原子命题是不能再分解的,仅仅研究以原子命题为基本单位的复合命题之间的逻辑关系和推理 。 这样,有些推理用命题逻辑就难以确切地表示出来 。 例如,著名的亚里士多德三段论苏格拉底推理：
谓词逻辑
Guoyongfang.2006@yahoo.com.cn
所有的人都是要死的，
苏格拉底是人，
所以苏格拉底是要死的。
根据常识，认为这个推理是正确的。但是，若用
Ls来表示，设 P,Q和 R分别表示这三个原子命题，则有
P,Q?R
Guoyongfang.2006@yahoo.com.cn
然而,(P∧ Q)→ R并不是永真式,故上述推理形式又是错误的 。 一个推理,得出矛盾的结论,
问题在哪里呢? 问题就在于这类推理中,各命题之间的逻辑关系不是体现在原子命题之间,
而是体现在构成原子命题的内部成分之间,即体现在命题结构的更深层次上 。 对此,Ls是无能为力的 。 所以,在研究某些推理时,有必要对原子命题作进一步分析,分析出其中的个体词,谓词和量词,研究它们的形式结构的逻辑关系,正确的推理形式和规则,这些正是谓词逻辑 （ 简称为 Lp） 的基本内容 。
Guoyongfang.2006@yahoo.com.cn
如有句子：
张红 是一个大学生 ；
王南 是一个大学生 ；
李华 是一个大学生 。
则在命题中必须要用三个命题 P,Q,R
来表示。
谓词逻辑
Guoyongfang.2006@yahoo.com.cn
在 Lp中,命题是具有真假意义的陈述句 。 从语法上分析,一个陈述句由主语和谓语两部分组成 。
在 Lp中,为揭示命题内部结构及其不同命题的内部结构关系,就按照这两部分对命题进行分析,并且把主语称为个体或客体,把谓语称为谓词 。
Guoyongfang.2006@yahoo.com.cn
一、谓词定义 在句子中，可以独立存在的客体称为个体词，而用以刻划客体的属性或客体之间的关系即是谓词。
谓词逻辑
Guoyongfang.2006@yahoo.com.cn
1.张三是大学生。
2.李四是大学生。
3.7是素数。
4.锻炼身体是个好习惯。
5.7小于 10。
6.张三和李四是好朋友。
7.哥白尼指出地球围绕太阳转。
谓词逻辑
Guoyongfang.2006@yahoo.com.cn
2－ 1 谓词的概念与表示个体词用 a,b,c,...x,y,z,a1,a2,a3等表示，谓词用 A,B,C,...P,Q，
R,…,A1,A2,A3,…,等表示。
Guoyongfang.2006@yahoo.com.cn
1.张三是大学生。 P（ c）
2.李四是大学生。 P（ a）
3.7是素数。 Q（ a）
4.锻炼身体是个好习惯。 R（ a）
5.7小于 10。 X（ a,b）
6.张三和李四是好朋友。 F（ a,b）
7.哥白尼指出地球围绕太阳转。 S（ a,b,c）
谓词逻辑
Guoyongfang.2006@yahoo.com.cn
谓词的概念与表示设,H(X):X是人
D(x),x是要死的。
上述三段论可翻译为：
则有,H(x)→ D(x),H(S)? D(S)
Guoyongfang.2006@yahoo.com.cn
谓词填式,把谓词字母后填以客体所得式子称为谓词填式，谓词和谓词填式是两个不同的概念，谓词不是命题，而谓词填式是命题。
谓词的概念与表示
Guoyongfang.2006@yahoo.com.cn
表示具体或特定的个体词称为 个体常量,一般个体词常量用带或不带下标的小写英文字母 a,b,C,……,a1,a2,a3.,…… 表示。
表示抽象的或泛指的个体词称为 个体变量,一般用带或不带下标的小写英文字
x,y,z,.…,x1,x2,x3,…… 表示。
个体词的取值范围称为 个体域 或 论域,常用 D
表示。而宇宙间的所有个体域聚集在一起所构成的个体域称为 全总个体域 。
谓词的概念与表示
Guoyongfang.2006@yahoo.com.cn
设有如下命题：
P,5是一个实数。 Q,3大于 2。
R,点 A位于点 B和点 C之间。 S,王同高于李浩。
解,设有如下 谓词,
R(x),x是一个实数。 G(x,y),x大于 y。
B(x,y,z),点 x位于点 y和点 z之间。
H(x,y),x高于 y。
并设 a1表示 A,a2表示 B,a3表示 C； a表示王同,b表示李浩 。
则上述四个命题可表示如下：
P,R(5)； Q:G(3,2)；
R:B(a1,a2,a3)； S:H(a,b)。
谓词的概念与表示
Guoyongfang.2006@yahoo.com.cn
几个结论：
1) 谓词中个体词的顺序是十分重要的，不能随意变更。
2) 一元谓词用以描述某一个个体的某种特性或性质，而 n元谓词则用以描述 n个个体之间的关系。
3) 0元谓词 (不含个体词的 )实际上就是一般的命题。
谓词的概念与表示
Guoyongfang.2006@yahoo.com.cn
一、命题函数定义 由一个谓词，一些客体变元组成的表达式称为 简单命题函数可见,n元谓词就是有 n个客体变元的命题函数，当 n=0时，称为 o元谓词，其本身就是一个命题,n=1时，称为一元谓词。
2－ 2 命题函数与量词
Guoyongfang.2006@yahoo.com.cn
定义 由一个或 n个简单命题函数以及逻辑联结词组合而成的表达式称为复合命题函数。
简单命题函数和复合命题函数，统称为命题函数。
Guoyongfang.2006@yahoo.com.cn
逻辑联结词 ┐,∧,∨,→,?与 命题演算中的解释完全相同。
例如,S（ x）,x学习好
W（ x）,x工作好
2－ 2 命题函数与量词
Guoyongfang.2006@yahoo.com.cn
n元谓词不是命题，只有其中的个体变元用特定个体或个体常元替代时，才能成为一个命题。
但个体变元在哪些论域取特定的值，对命题的真值极有影响。 例如，令 S(x),x是大学生。
若 x的论域为某大学的计算机系中的全体同学，
则 S(x)是真的；若 x的论域是某中学的全体学生，则 S(x)是假的；若 x的论域是某剧场中的观众，且观众中有大学生也有非大学生的其它观众，则 S(x)是真值是不确定的。
Guoyongfang.2006@yahoo.com.cn
例如
( P（ x,y） ∧ P（ y,z） ) → P（ x,z）
Guoyongfang.2006@yahoo.com.cn
命题函数确定为命题，与客体变元的论述范围有关。在命题函数中，客体变元的论述范围称作个体域。个体域可以是有限的，也可以是无限的，把各种个体域综合在一起作为论述范围的域称全总个体域。
Guoyongfang.2006@yahoo.com.cn
量词在上述三段论的例子中，如要对句子：
H(x)→ D(x)求否定，则有：
┐ (H(x)→ D(x))＝ ┐┐ H(ｘ )∧┐ Ｄ (ｘ )＝ H(ｘ )∧┐
Ｄ (ｘ )
上述式子说明：,命题 P”的否定是：,所有的人都不死,。
但这与人们在日常生活中对命题：,所有人都是要死的,。
的否定为：,并非一切的人都是要死的,。
显然相差甚远。
其原因在于：命题 P的确切含义是：
,对任意的 x，如果 x是人，则 x是要死的,。
但 H(x)→ D(x)并没有确切地表示出,对任意 x”这个意思，
Guoyongfang.2006@yahoo.com.cn
量词的引入
P（ x）：所有人都聪明
┐ P（ x）：所有人都不聪明
Q（ x）：有些人聪明
┐ Q（ x）：有些人不聪明
Guoyongfang.2006@yahoo.com.cn
命题函数与量词符号化下述命题：
1） 每一个苹果 都是红的。
2） 任意一个整数 都是正整数或负整数。
3） 有一些实数是 有理数。
4） 有一些人 是很聪明的。
5） 对每一个实数,都有 x2+2x+1=(x+1)2。
6） 有一些实数,使得 x+6=5。
上述每一个描述量词的语句下划有,下划线,。
Guoyongfang.2006@yahoo.com.cn
解：设 R(x),x是红的；
P(x),x是正整数； N(x),x是负整数；
Q(x),x是有理数； C(x),x是聪明的；
L(x),x2+2x+1=(x+1)2；
M(x),x+6=5。
1) R(x) (对任意的苹果 )
2) P(x)∨N(x) (对任意的整数 )
3) Q(x) ((对有一些实数 )
4) C(x) (对有一些人 )
5) L(x) (对任意实数 )
6) M(x) (对有一些实数 )
则有：
命题函数与量词
Guoyongfang.2006@yahoo.com.cn
利用 n元谓词和它的论域概念，有时还是不能用符号来很准确地表达某些命题，例如 S(x)表示
x是大学生，而 x的个体域为某单位的职工，那么 S(x)可表示某单位职工都是大学生，也可表示某单位有一些职工是大学生，为了避免理解上的歧义，在 Lp中，需要引入用以刻划,所有的,,,存在一些,等表示不同数量的词，即量词。
Guoyongfang.2006@yahoo.com.cn
上述一系列例子，都仅仅只符号化了一部分内容，而对句子中的,对每一个,,,对任意的,,,有一些,等等无法用谓词来表示，这些都是与个体词的数量有关的语句。为了把它们符号化，引进如下两个符号：
(?x):所有的 x； (?x)：有些 x；
任意的 x； 至少有一个 x；
一切的 x； 存在 x；
每一个 x； 等等。 等等。
Guoyongfang.2006@yahoo.com.cn
定义 (?x)称为全称量词 。 (?x)为存在量词,其中的 x称为作用变量 。 一般将其量词加在其谓词之前，记为
(?x)F(x),(?x)F(x),此时,F(x)称为全称量词和存在量词的辖域 。
Guoyongfang.2006@yahoo.com.cn
1) (?x)R(x) (x?{苹果 })
2) (?x)(P(x)∨ N(x)) (x?{整数 })
3) (?x)Q(x) (x?{实数 })
4) (?x)C(x) (x?{人 })
5) (?x)L(x) (x?{实数 })
6) (?x)M(x) (x?{实数 })
三段论中的 P也可表示为,(?x)(H(x)→ D(x))。
在前面的例中,利用量词则有：
命题函数与量词
Guoyongfang.2006@yahoo.com.cn
从书写上十分不便，总要特别注明个体域。
在同一个比较复杂的句子中，对于不同命题函数中的个体可能属于不同的个体域，此时无法清晰表达。
如讨论求上述例中 (1)和 (3)的合取而得的新命题有：
(x)R(x)∧ (?x)Q(x)。
其中，全称量词中的 x?｛苹果｝，存在量词中的 x?｛实数｝。
命题函数与量词
Guoyongfang.2006@yahoo.com.cn
有时，由于个体域的注明不清楚，造成无法确定其真值。对于同一个公式，不同的个体域有可能带来不同的真值。如 (?x)(x＋ 6＝ 5)，
(1)、在实数范围内时，确有 x＝ -1
使得 x＋ 6＝ 5，因此,(?x)(x＋ 6＝ 5)为
,真,。
(2)、在正整数范围内时，则找不到任何 x，使得 x＋ 6＝ 5为,真,,所以，
(?x)(x＋ 6＝ 5)为,假,。
命题函数与量词
Guoyongfang.2006@yahoo.com.cn
对于全称量词，刻划其对应个体域的特性谓词作为蕴涵的前件加入。
对于存在量词，刻划其对应个体域的特性谓词作为合取式之合取项加入。
基于上述情况，必要对个体域进行统一，全部使用全总个体域，此时，对每一个句子中个体变量的变化范围用一 特性谓词 刻划。而统一成 全总个体域 后，此全总个体域在谓词公式中就不必特别说明，常常省略不记。同时，这种特性谓词在加入到命题函数中时必定遵循如下原则：
命题函数与量词
Guoyongfang.2006@yahoo.com.cn
解,A(x),x是苹果； (?x)(A(x)→ R(x))
I(x),x是整数 (?x)(I(x)→ (P(x)∨ N(x)))
R(x),x是实数； (?x)(R(x)∧ Q(x))
H(x),x是人； (?x)(H(x)∧ C(x))
R(x),x是实数； (?x)(R(x)→ L(x))
R(x),x是实数； (?x)(R(x)∧ M(x))
对于前面例中的例子运用用特性谓词描述。
上述三段论可完整翻译为：
(?x)(H(x)→ D(x)),H(S),D(S)
┐ (?x)(H(x)→ D(x))＝ (?x)(H(ｘ )∧┐ Ｄ (ｘ ))
命题函数与量词
Guoyongfang.2006@yahoo.com.cn
一,谓词公式定义 谓词公式定义为
（ 1） 原子谓词公式是合式公式；
（ 2） 若 A是谓词公式,则 （?A） 也是合式公式；
（ 3） 若 A,B是谓词公式,则 （ A∨ B）,
（ A∧ B）,（ A→ B）,（ A?B） 也是合式公式；
（ 4） 若 A是合式公式,x是 A中出现的任何变元,
则 (Vx) A和 (?x) A也是合式公式 。
（ 5） 有限次地使用 （ 1） ~（ 4） 所得到的也是合式公式 。
Guoyongfang.2006@yahoo.com.cn
谓词公式与翻译二、翻译翻译：将自然语言表示的命题符号化方法：首先找出谓词，选择合适的联结词，再确定使用的量词。
Guoyongfang.2006@yahoo.com.cn
谓词公式与翻译符号化下述语句：
1） 有会说话的机器人。
2） 每个实数都存在比它大的另外的实数。
3） 每个人都有某些专长。
4） 尽管有人很聪明，但未必一切人都聪明
。
Guoyongfang.2006@yahoo.com.cn
1） M(x),x是机器人。 F(x),x会说话。则 有：
(?x)(M(x)∧ F(x))。
2） R(x),x是实数。 L(x,y),x小于 y。 则有：
(?x)(R(x)→ (?y)(R(y)∧ L(x,y)))
3） M(x),x是人。 N(x),是专长。
P(x,y),x都有 y。 则有,
(?x)(M(x)→ (?y)(N(y)∧ P(x,y)))。
4） M(x),x是人。 C(x),x很聪明。 则有,
(?x)(M(x)∧ C(x))∧┐ (?x)(M(x)→ C(x))
谓词公式与翻译
Guoyongfang.2006@yahoo.com.cn
设 P(x):x是素数
I(x):x是整数
Q(x,y):x+y=0
用语句描述下述句子，并判断其真假值。
1) (?x)(I(x)→ P(x))
2) (?x)(I(x)∧ P(x))
3) (?x)(?y)(I(x)∧ I(y)→ Q(x,y))
4) (?x)(I(x)→ (?y)(I(y)∧ Q(x,y)))
5) (?x)(?y)(I(x)∧ (I(y)→ Q(x,y)))
谓词公式与翻译
Guoyongfang.2006@yahoo.com.cn
解：
1)可描述为：,对任意的整数 x,x一定是素数,,真值为,假,。
2)可描述为：,存在一些整数 x,x是素数,,
真值为,真,。
3)可描述为：,对任意的整数 x,y,都有
x+y=0”,真值为,假,。
4)可描述为：,对任意的整数 x,都存在着整数
y,使得 x+y=0”,真值为,真,。
5)可描述为：,存在着整数 x,使得对任意的整数 y,都有 x+y=0”,真值为,假,。
谓词公式与翻译
Guoyongfang.2006@yahoo.com.cn
从上面的例子可知，如有多个量词，则读的顺序按从左到右的顺序，即：
(?x)(?y)G(x,y)＝ (?x)((?y)(G(x,y))
另外，量词对变元的约束，往往与量词的次序有关，不同的量词次序，可以产生不同的真值，此时对多个量词同时出现时，
不能随意颠倒它们的顺序，颠倒后会改变原体的含义。如上例中 4)和 5)。
谓词公式与翻译
Guoyongfang.2006@yahoo.com.cn
2-4 变元的约束一、自由变元与约束变元量词后所跟的 x叫做量词的指导变元或作用变元,P(x)叫做相应量词的作用域或辖域。在作用域中 变元 x的 出现 称 为约束出现,此时的变元 x称为约束变元 (量 )。
若 x的出现不是约束出现，则称它为自由出现,此时的变元 x称为自由变元 (量 )。
Guoyongfang.2006@yahoo.com.cn
例：
(?y)(P(y,z)→Q(x,y) )∨R(y).
(?x)(P(x)→Q(x)),
(?x)(P(x))→ (?y)(R(x,y))
(?x)(P(x)→R(x)) ∧ (?y)Q(x,y)
Guoyongfang.2006@yahoo.com.cn
解：在 1)中,P(y,z)与 Q(x,y)中的 y为约束变元,x,z为自由变元,R(y)中的 y为自由变元。
在 2)中,P(x)和 Q(x)中的 x都为约束变元。
在 3)中,P(x)中的 x和 R(x,y)中的 y都为约束变元,R(x,y)中的 x为自由变元。
在 4)中,P(x),R(x)中的 x和 Q(x,y)中的
y都是约束变元,Q(x,y)中的 x为自由变元。
Guoyongfang.2006@yahoo.com.cn
从约束变元的概念看,P（ x1，
x2,… xn）是 n元谓词，它有 n个互相独立的自由变元，若对其中 k个变元进行约束则成了 n-k元谓词，因此，谓词公式中如果没有自由变元出现，则该式成为一个命题。
Guoyongfang.2006@yahoo.com.cn
二、约束变元的改名规则 1(约束变元的改名规则 )：
1)、将量词中出现的变元以及该量词辖域中此变量之所有约束出现都用新的变元替换。
2)、新的变元一定要有别于改名辖域中的所有其它变量。
Guoyongfang.2006@yahoo.com.cn
变元的约束在公式 (?x)(P(x)→ R(x,y))∧ Q(y)中，变元 x是约束变元,y是自由变元。
利用规则 1对 x进行改名，则,
(?z)(P(z)→ R(z,y))∧ Q(y)
不合法的改名有,
(?z)(P(z)→ R(x,y))∧ Q(y)
(?y)(P(y)→ R(y,y))∧ Q(y)
Guoyongfang.2006@yahoo.com.cn
三,自由变元的代入规则 2(自由变元的代入规则 )：
1)、将公式中出现该自由变元的每一处都用新的变元替换。
2)、新变元不允许在原公式中以任何约束形式出现。
Guoyongfang.2006@yahoo.com.cn
变元的约束利用规则 2对 (?x)(P(x)→ R(x,y))∧ Q(y) 中的 y进行代入，则,
(?x)(P(x)→ R(x,z))∧ Q(z)
不合法的代入有,(?x)(P(x)→ R(x,y))∧ Q(z)
(?x)(P(x)→ R(x,x))∧ Q(x)
Guoyongfang.2006@yahoo.com.cn
量词作用域中的约束变元，当论域的元素是有限时，客体变元的所有可能取代是可以枚举的。
设论域元素为 a1,a2,…,an
则 (?x)P(x)=P(a1) ∧ P(a2) … ∧ P(an)
(? x)P(x)=P(a1) ∨ P(a2) … ∨ P(an)
Guoyongfang.2006@yahoo.com.cn
变元的约束
1,其中,①,个体域为 D＝ {2,3}；
.a指定为,2；
.P(2)=1,P(3)=0
则有,P(a)∧ (?x)P(x)
＝ P(2)∧(P(2)∧P(3)) ＝ 1∧(1∧0) ＝ 0
(?x)P(x)→P(a)
＝ (P(2)∧P(3))→P(2) ＝ (1∧0)→1 ＝ 1。
求公式,P(a)∧ (?x)P(x)和 (?x)P(x)→P(a) 的真值。
Guoyongfang.2006@yahoo.com.cn
2,其中,①,个体域为 D＝ {1,2,3,4,5,6,7,8,9}；
②,a指定为,5；
③,P(x)指定为 1,x>0。
则 有,P(a)∧ (?x)P(x)
＝ P(5)∧(P(1)∧P(2)∧....∧P(9))
＝ 1∧(1∧1∧....∧1) ＝ 1；
(?x)P(x)→P(a)
＝ (P(1)∧P(2)∧....∧P(9))→P(5)
＝ (1∧1∧....∧1)→1 ＝ 1。
变元的约束
Guoyongfang.2006@yahoo.com.cn
2-5 谓词演算的等价式与蕴含式在谓词公式中常包含命题变元和客体变元，当客体变元有确定的客体所取代，
命题变元用确定的命题所取代时，就称作为谓词公式赋值。一个谓词公式经过赋值以后，就成为具有确定真值 T或 F的命题。
Guoyongfang.2006@yahoo.com.cn
定义,给定任何两个谓词公式 wffA和
wffB，设它们有共同的个体域 E，若对 A
和 B的任一组变元进行赋值，所得命题的真值相同，则称谓词公式 A和 B在 E上是等价的，并记做 A?B。
Guoyongfang.2006@yahoo.com.cn
定义,给定任意谓词公式 wffA，其个体域为 E，
对于 A的所有赋值,wffA都为真，则称 wffA
在 E上是有效的（或永真的）。
定义,给定任意谓词公式 wffA，其个体域为 E，
对于 A的所有赋值,wffA都为假，则称 wffA
在 E上是不可满足的（或永假的）。
定义,给定任意谓词公式 wffA，其个体域为 E，
对于 A的所有赋值中至少有一种赋值为真，则称 wffA在 E上是可满足的。
Guoyongfang.2006@yahoo.com.cn
谓词演算的等价式与蕴含式
1.命题公式的推广将命题演算中的等价公式表和蕴含式表推广到谓词演算中使用。
例,(?x)(P(x)→ Q(x))
(?x)(┐ P(x)∨ Q(x))
(?x)P(x)∨ (?y)R(x,y)
┐ (┐ (?x)P(x)∧ ┐ (?y)R(x,y))
(?x)H(x,y)∧ ┐ (?x)H(x,y)?F
Guoyongfang.2006@yahoo.com.cn
谓词演算的等价式与蕴含式
2.量词与联结词 ┐ 之间的关系例 1)不是所有人今天来上课。
┐ (?x)P(x)
2)存在一些人今天没有来上课。
(?x)┐ P(x)
3)不是存在一些人今天来上课。
┐ (?x)P(x)
4)所有的人今天都没有来上课。
(?x)┐ P(x)
Guoyongfang.2006@yahoo.com.cn
谓词演算的等价式与蕴含式得到了公式：
┐ (?x)P(x)? (?x) ┐ P(x)
(?x)┐ P(x)?┐ (?x)P(x)
约定：出现在量词之前的否定，不是否定该量词，而是否定被量化了的整个命题。
Guoyongfang.2006@yahoo.com.cn
规则,将量词前面的 ┐ 移到量词的后面去时，存在量词改为全称量词，全称量词改为存在量词，反之，若将量词后面的否定 ┐ 移到量词的前面去时，也要作相应的改变，这种量词与 ┐ 的关系是普遍成立的 。
Guoyongfang.2006@yahoo.com.cn
在有限个体域 D = {a1,a2,…,an}中消除量词：
(1),(?x)A(x)? A(a1)?A(a2)?…?A(an)
(2),(?x)A(x)? A(a1)?A(a2)?…?A(an)
谓词演算的等价式与蕴含式
Guoyongfang.2006@yahoo.com.cn
谓词演算的等价式与蕴含式
3.量词作用域的扩张与收缩
(?x)(A(x)∨ B)?((?x)A(x)∨ B)
(?x)(A(x)∧ B)?((?x)A(x)∧ B)
(?x)(A(x)∨ B)?((?x)A(x)∨ B)
(?x)(A(x)∧ B)?((?x)A(x)∧ B)
Guoyongfang.2006@yahoo.com.cn
((?x)A(x) → B)? (?x)(A(x) → B)
((?x)A(x) → B)? (?x)(A(x) → B)
(B → (?x)A(x))? (?x)(B → A(x))
(B → (?x)A(x))? (?x)(B → A(x))
Guoyongfang.2006@yahoo.com.cn
谓词演算的等价式与蕴含式
4.量词与命题联结词之间的一些等价式
(?x)(A(x)∧ B(x))
(?x)A(x)∧(?x)B(x)
(?x)(┐ A(x)∧ ┐ B(x))
(?x)(┐ A(x))∧(?x)(┐ B(x))
(?x)(A(x)∨ B(x))
(?x)A(x)∨ (?x)B(x)
(?x)(┐ A(x)∨ ┐ B(x))
(?x)(┐ A(x))∨ (?x)(┐ B(x))
Guoyongfang.2006@yahoo.com.cn
谓词演算的等价式与蕴含式
5.量词与命题联结词之间的一些蕴含式
(?x)A(x)∨ (?x)B(x)
(?x)(A(x)∨ B(x))
(?x)(┐ A(x))∨ (?x)(┐ B(x))
(?x)(┐ A(x)∨ ┐ B(x))
(?x)(A(x)∧ B(x))
(?x)A(x)∧(?x)B(x)
┐ ((?x)A(x)∧(?x)B(x))
┐ (?x)(A(x)∧ B(x))
Guoyongfang.2006@yahoo.com.cn
谓词演算的等价式与蕴含式类似的有：
(?x)(A(x)→ B(x))
(?x)A(x)→ (?x)B(x)
(?x)(A(x)? B(x))
(?x)A(x)?(?x)B(x)
Guoyongfang.2006@yahoo.com.cn
谓词演算的等价式与蕴含式
6.多个量词的使用全称量词与存在量词在公式中出现的次序，不能随意更换。
(?x)(?y)A(x,y) (?y)(?x)A(x,y)
(?x)(?y)A(x,y) (?y)(?x)A(x,y)
(?x)(?y)A(x,y) (?y)(?x)A(x,y)
(?x)(?y)A(x,y) (?y)(?x)A(x,y)
Guoyongfang.2006@yahoo.com.cn
E23 (?x)(A(x)∨ B(x))?(?x)A(x)∨ (?x)B(x))
E24 (?x)(A(x)∧ B(x))?(?x)A(x)∧(?x)B(x)
E25 ┐ (?x)A(x)?(?x)┐ A(x)
E26 ┐ (?x)A(x)?(?x)┐ A(x)
E27 (?x)(A∧ B(x))?A∧(?x)B(x))
E28 (?x)(A∨ B(x))?A∨ (?x)B(x))
E29 (?x)(A∨ B(x))?A∨ (?x)B(x))
E30 (?x)(A∧ B(x))?A∧(?x)B(x))
E31 (?x)(A(x)→ B(x))?(?x)A(x)→ (?x)B(x)
E32 (?x)A(x)→ B?(?x)(A(x)→ B)
谓词演算的等价式与蕴含式
Guoyongfang.2006@yahoo.com.cn
E33 (?x)A(x)→ B?(?x)(A(x)→ B)
E34 A→ (?x)B(x)?(?x)(A→ B(x))
E35 A→ (?x)B(x)?(?x)(A→ B(x))
I17 (?x)A(x)∨ (?x)B(x)=> (?x)(A(x)∨ B(x))
I18 (?x)(A(x)∧ B(x))=> (?x)A(x)∧(?x)B(x)
I19 (?x)A(x)→ (?x)B(x)=> (?x)(A(x)→ B(x))
谓词演算的等价式与蕴含式
Guoyongfang.2006@yahoo.com.cn
作业
P71：
2-5习题 1(c),2（ d）
Guoyongfang.2006@yahoo.com.cn
2－ 6 前束范式定义,一个公式，如果量词均在全式的开头，它们的作用域，延伸到整个公式的末尾，则该公式叫做前束范式。
例,(?x)(?y)(?z)(A(x,y)→ B(z))
(?y)(?z)(A(y)∨ B(z))
Guoyongfang.2006@yahoo.com.cn
前束范式定理,任意一个谓词公式，均和一个前束范式等价。
方法：
否定深入变元换名，量词提前
Guoyongfang.2006@yahoo.com.cn
例 1 把公式 (?x)P(x)→ (?x)Q(x)转化为前束范式解,(?x)P(x)→ (?x)Q(x)
┐ (?x)P(x)∨ (?x)Q(x)
(?x)┐ P(x)∨ (?x)Q(x)
(?x)(┐ P(x)∨ Q(x))
前束范式
Guoyongfang.2006@yahoo.com.cn
例 2 把公式
(?x)(?y)((?z)(P(x,z)∧ P(y,z))→ (?u)Q(x,y,u))转化为前束范式解,(?x)(?y)((?z)(P(x,z)∧ P(y,z))→ (?u)Q(x,y,u))
(?x)(?y)(┐ (?z)(P(x,z)∧ P(y,z))∨ (?u)Q(x,y,u))
(?x)(?y)((?z)┐ (P(x,z)∧ P(y,z))∨ (?u)Q(x,y,u))
(?x)(?y)((?z)(┐ P(x,z)∨ ┐ P(y,z))∨ (?u)Q(x,y,
u))
(?x)(?y)(?z)(?u)(┐ P(x,z)∨ ┐ P(y,z)∨ Q(x,y,u))
前束范式
Guoyongfang.2006@yahoo.com.cn
前束范式定义,一个 wffA如果具有如下形式称为前束合取式。
(? v1) (? v2) … (? vn)[(A11∨ A12∨ … ∨ A1l1)
∧ (A21∨ A22∨ … ∨ A2l2) ∧ … ∧
(Am1∨ Am2∨ … ∨ Amlm)]
可能为?或?,Aij是原子公式或其否定。
定理,每一个 wffA都可转化为与其等价的前束合取范式。
Guoyongfang.2006@yahoo.com.cn
前束范式方法：
取消多余量词换名消去条件联结词否定深入量词提前
Guoyongfang.2006@yahoo.com.cn
例 3 把公式
(?x)[(?y)P(x)∨ (?z)Q(z,y)→ ┐ (?y)R(x,y)]转化为前束合取范式解,(?x)[(?y)P(x)∨ (?z)Q(z,y)→ ┐ (?y)R(x,y)]
(?x)[P(x)∨ (?z)Q(z,y)→ ┐ (?y)R(x,y)]/取消多余量词
(?x)[P(x)∨ (?z)Q(z,y)→ ┐ (?w)R(x,w)]/换名
(?x)[┐ (P(x)∨ (?z)Q(z,y))∨ ┐ (?w)R(x,w)]/消去条件联结词
(?x)[(┐ P(x)∧ ┐ (?z)Q(z,y) )∨ ┐ (?w)R(x,w)]/否定深入
(?x)[(┐ P(x)∧ (?z)┐ Q(z,y) )∨ (?w) ┐ R(x,w)]
(?x)(?z)(?w)[(┐ P(x)∧ ┐ Q(z,y) )∨ ┐ R(x,w)]/量词提前
(?x)(?z)(?w)[(┐ P(x)∨ ┐ R(x,w))∧ (┐ Q(z,y) )∨
┐ R(x,w)]
前束范式
Guoyongfang.2006@yahoo.com.cn
前束范式定义,一个 wffA如果具有如下形式称为前束析取式。
(? v1) (? v2) … (? vn)[(A11∧ A12∧ … ∧ A1l1)
∨ (A21∧ A22∧ … ∧ A2l2)∨ … ∨
(Am1∧ Am2∧ … ∧ Amlm)]
可能为?或?,Aij是原子公式或其否定。
定理,每一个 wffA都可转化为与其等价的前束析取范式。
Guoyongfang.2006@yahoo.com.cn
作业
P75,2-6习题
1（ b）,2（ d）
Guoyongfang.2006@yahoo.com.cn
2-7谓词演算的推理理论消去和添加量词规则：
US(全称指定规则 ),(?x)G(x)?G(c)
ES(存在指 定 规则 ),(?x)G(x)?G(c)
UG(全称推广规则 ),G(y)?(?x)G(x)
EG(存在推广规则 ),G(c)?(?x)G(x)
Guoyongfang.2006@yahoo.com.cn
有关规则 US，实际可书写形式：
(?x)G(x)?G(c)
成立的条件是：
x是 G(x)中自由出现的个体变量 。
c为任意的个体常量 。
谓词演算的推理理论
Guoyongfang.2006@yahoo.com.cn
谓词演算的推理理论
(?x)G(x)?G(c)
成立的条件是：
x是 G(x)中自由出现的个体变量。
在 G(x)中，变元 x的每一次自由出现都用相同的个体常量 c代入。
c是使 G(x)为真的特定的个体常量。
此 c是在该推导之前从未使用过的。
Guoyongfang.2006@yahoo.com.cn
谓词演算的推理理论
G(y)?(?x)G(x)
成立的条件和限制是：
y是 G(y)中自由出现的个体变量。且 y取遍整个个体域时，
都有 G(y)为真。
对 G(y)中不满足假设前提 (使 G(y)为真 )的自由变元 y不能使用规则 UG。
添加的量词 (?x)中的 x和取代 y的 x不能在 G(y)中以约束身份出现。
对于曾经由使用规则 ES所得之公式中原来的约束变元不能使用规则 UG。
Guoyongfang.2006@yahoo.com.cn
谓词演算的推理理论该规则有形式：
G(c)?(?x)G(x)
成立的条件和限制是：
c是使 G(c)为真的特定的个体常量。
取代 c的 x和添加的量词 (?x)中的 x不能在 G(c))中以任何约束出现。
Guoyongfang.2006@yahoo.com.cn
谓词演算的推理理论在推导的过程中，可以引用命题演算中的规则 P、规则 T、
规则 CP 。
为了在推导过程中消去量词，可以引用规则 US和规则 ES来消去量词。
当所要求的结论可能被定量时，此时可引用规则 UG和规则
EG将其量词加入。
证明时可采用如命题演算中的直接证明方法和间接证明方法。
在推导过程中，对消去量词的公式或公式中没含量词的子公式，完全可以引用命题演算中的基本等价公式和基本蕴涵公式。
Guoyongfang.2006@yahoo.com.cn
谓词演算的推理理论在推导过程中，对含有量词的公式可以引用谓词中的基本等价公式和基本蕴涵公式。
在推导过程中，如既要使用规则 US又要使用规则 ES消去公式中的量词 (只要有可能，我们总是先使用规则
ES，再使用规则 US)。然后再使用命题演算中的推理规则，最后使用规则 UG或规则 EG引入量词，得到所要的结论。
如一个变量是用规则 ES消去量词,对该变量在添加量词时,则只能使用规则 EG,而不能使用规则 UG;如使用规则 US消去量词,对该变量在添加量词时,则可使用规则 EG和规则 UG。
Guoyongfang.2006@yahoo.com.cn
谓词演算的推理理论如有两个含有存在量词的公式，当用规则 ES消去量词时，不能选用同样的一个常量符号来取代两个公式中的变元，而应用不同的常量符号来取代它们。
在用规则 US和规则 ES消去量词时，此量词必须位于整个公式的最前端。
在 添加的量词 (?x),(?x)时，所选用的 x不能在 公式 G(c)中以任何约束出现。
