在命题逻辑中,命题是命题演算的基本单位,不关心每个简单命题反映的具体内容,
没有进一步研究命题的内部结构,因而在实际应用中存在很多缺陷 。
著名的苏格拉底三段论,
,所有的人都是要死的,苏格拉底是人,所以是苏格拉底是要死的,”
P,所有的人是要死的 ;
Q,苏格拉底是人 ;
R,苏格拉底是要死的,
由上述文字构造的命题逻辑推理结构为,(P? Q)?R
可知,(P? Q)?R不是一个重言式,因此,按命题逻辑的方法,无法证明上述问题,
为了在命题演算中,反映命题的内在联系,常常要将简单命题分解成 个体词,谓词,量词 等,并对它们的形式结构及逻辑关系加以研究,总结出正确的推理形式和规则,这就是本章一阶逻辑要研究的内容 。
个体词：可以独立存在的客体，既可以是抽象的概念，
也可以是具体的事物。
谓 词：用来刻划个体词的 性质 或个体词之间 关系 的。
。2如：李明、自然数、
2如,(1) 是无理数 (性质 )
(2) 小李 比 小赵 高 2厘米 (关系 )
简单命题总可以被分解成 个体词 和 谓词 两部分。
§ 2.1一阶逻辑命题符号化的有关概念与方法个体常项：指 具体 或 特定 的个体的词，用小写字母 a,b,c,……,表示。
个体变项：表示 抽象 的或 泛指 的个体的词，用 x,
y,z,……,表示。
个体域：个体变项的取值范围，又称 论域 。
全总个体域：当无特殊声明时,表示宇宙间的一切事物组成的个体域。
谓词常项,表示具体 性质 或 关系 的谓词，用大写英文字母 F,G,……,表示。
谓词变项,表示 抽象 的或 泛指 的性质或关系的谓词，也用大写字母表示。
一般根据上、下文区分常项与变项。
个体变项 x具有性质 F,记作 F(x)
个体变项 x,y具有关系 L,记作 L(x,y)
将 (1),(2)两命题符号化：
2(1) 是无理数 (性质 )
(2) 小李 比 小赵 高 2厘米 (关系 )
F(x),x 是无理数,2:a ).()1( aF可表示为
H(x,y),x 比 y 高 2厘米
a,小李,b,小赵
(2)可表示为,H(a,b)(但不是 H(b,a))
元 数：在谓词中所包含的 个体词数 。
n元谓词,含 n(n?1)个个体词的谓词，可用 D(x1,x2,……,xn)表示。
一元谓词表性质；
二元或更多元谓词表关系。
0元谓词,不含 个体变项 的谓词 。
例 2.1,将下列命题用 0元谓词符号化
(1) 2是素数且是偶数 ；
(2) 如果 2大于 3，则 2大于 4 ；
(3) 如果张明比李民高，李民比赵亮高，
则张明比赵亮高 ；
如,a为 2,b为 3,L(a,b)是 0元谓词。
解,引入一元谓词,F(x) ––– x是素数
G(x) ––– x是偶数命题符号化,a为 2
(1) 符号化为 F(a) G(a)? (0元谓词 )
(1) 2是素数且是偶数 ；
解,引入二元谓词,L(x,y)––– x比 y大命题符号化,a为 2,b为 3,c为 4
(2) 符号化为 L(a,b)? L(a,c)
(2) 如果 2大于 3，则 2大于 4 ；
类似于 (2),自己做！
(3) 如果张明比李民高，李民比赵亮高，
则张明比赵亮高 ；
(1) 所有的人都是要死的 ;
(2) 有些人活百岁以上 ;
考虑以下形式命题的符号化,
量 词表示数量的词，分 全称量词 与 存在量词 。
,一切、所有的、任意 的 ；
,存在着、有一个、至少有一个 ；
x,个体域中所有个体 ；
x,存在个体域中某个个体 ；
xF(x),个体域中所有个体具有性质 F ；
xF(x),存在着个体域中某个个体具有性质 F 。
将命题,所有的人都是要死的,符号化
(考虑个体域为人类集合 ）
符号化为,?xF(x) 其中 F(x)表示,x是要死的。
将命题,有的人活百岁以上,符号化
(考虑个体域为人类集合 ）
符号化为,?xF(x) 其中 F(x)表示,x活百岁以上。
特性谓词：在全总个体域的情况下，为了 指定 某个个体变元的范围，引入特性谓词。
将命题 (公式 ),所有的人都是要死的,符号化
M(x),x是人 (特性谓词 )
F (x),x是要死的命题 (公式 )符号化为,?x(M(x)?F(x))
分析一下,它与?xF(x)有什么区别？
解：
有了个体词，谓词，量词等概念，我们就可以更细致地刻划命题公式。
将命题 (公式 ),有些人活百岁以上,符号化
M(x),x是人 (特性谓词 )
F(x),x活百岁以上命题 (公式 )符号化为,?x(M(x)?F(x))
分析一下,它与?xF(x)有什么区别？
解：
使用量词时,应该注意以下几点,
1,在不同的个体域中,命题符号化的形式可能不一样 ;
2,如没有事先给出个体域,都应以全总个体域为个体域
3,在引入特性谓词后,引入全称量词与存在量词符号化的形式是不同的 ;
4.当个体域为有限集时,如 D={a1,a2,a3,…an},对于任意的谓词 A(x),都有
(1)?xA(x)?A(a1)?A(a2)?…..,? A(an)
(2)?xA(x)?A(a1)?A(a2)?……?A(an)
5,多个量词同时出现时,不能随意颠倒顺序 ;
x?y H(x,y),其中 H(x,y),x+y=5
量词颠倒顺序成立吗?
例,对于任意的 x,存在 y,使得 x+y=5,
取个体域为实数集合,该如何符号化?
例 2.3 在谓词逻辑中将下列命题符号化
(1) 对所有的 x,均有 x2 –1=(x+1)(x–1) (个体域为自然数集 )
(2) 存在 x,使得 x +5=2 (个体域为自然数集 )
(4) 存在着偶素数
(5) 没有不犯错误的人
(3) 凡偶数均能被 2整除
(6) 在北京工作的人未必都是北京人
(7) 一切人都不一样高
(8) 每个自然数都有后继数
(9) 有的自然数无先驱数
(10) 有的有理数是整数 (个体域为实数集 )
F(x),x满足 x2–1=(x+1)(x – 1)
(1)符号化,?xF(x)
解,对所有的 x,均有 x2 –1=(x+1)(x–1)
(1) 对所有的 x,均有 x2 –1=(x+1)(x–1)
(个体域为自然数集 )
G(x),x是满足 x +5＝ 2
(2)符号化,?xG(x)
解,存在 x,使得 x +5=2
(2) 存在 x,使得 x +5=2 (个体域为自然数集 )
解,要引入特性谓词,F(x),x是偶数
G(x),x能被 2整除解,F(x),x是偶数 G(x),x是素数符号化,?x(F(x)?G(x))
符号化,?x(F(x)?G(x))
(4) 存在着偶素数
(3) 凡偶数均能被 2整除解,特性谓词 M(x),x是人解,F(x),x是在北京工作的人,G(x),x是北京人
F(x),x犯错误符号化,x(M(x) F(x))
或?x(M(x)? F(x))
符号化,x(F(x)? G(x))
(5) 没有不犯错误的人
(6) 在北京工作的人未必都是北京人解,M(x),x是人,L(x,y),x与 y一样高
H(x,y),x与 y是同一个人符号化,?x?y(M(x)? M(y) H(x,y) L(x,y))
(7) 一切人都不一样高
(8) 每个自然数都有后继数解,F(x),x自然数 H(x,y),y是 x的后继数符号化,?x(F(x)y (F(y)? H(x,y))
解,F(x),x是自然数,H(x,y),y是 x的先驱数符号化,?x(F(x)y(F(y) H(x,y))
解,F(x),x是有理数,G(x),x是整数符号化,?x(F(x)? G(x))
(9) 有的自然数无先驱数
(10) 有的有理数是整数 (个体域为实数集 )
§ 2.2 一阶逻辑公式及解释谓词演算中的合式公式：
原子公式：不出现 命题联结词 和 量词 的命题函数 P(x1,x2,…,xn),其中 x1,x2,…,
xn为个体变项或常项。
(1) 原子谓词公式是合式公式 ；
(2) 若 A是合式公式，则? A也是 ；
一、一阶逻辑合式 (谓词 )公式的概念
(3)若 A和 B是合式公式，则 (A?B),(A?B),(A?B)
和 (A? B)也是 ；
(4)如果 A是合式公式,x是 A中出现的个体变项，
则 (?x)A和 (?x)A是合式公式 ；
(5)只有有限次地应用规则 (1),(2),(3),(4)所得到的公式才是合式公式 。
谓词合式公式即按规则 (1),(2),(3),(4)、
(5)由原子公式、联结词、量词及圆括号组成的字符串，但最外层括号可以省略。
例 2.4 用谓词 (一阶逻辑合式 )公式表示下列命题：
(1) 并非每个实数都是有理数 ；
(2) 没有不犯错误的人 ；
(3) 每个人都有一些缺点 。
解,(1) 设 R(x),x是实数,Q(x),x是有理数对应谓词公式,?(?x)(R(x)?Q(x))
二、应用或,(?x)(R(x) Q(x))
(2) 设 F(x),x犯错误,M(x),x是人对应谓词公式,?(?x)(M(x) F(x))
或,(?x)(M(x)? F(x))
解,F(x,y),x都有 y,M(x),x是人,G(y),y是缺点对应的谓词公式,(?x)(?y)(M(x)?(G(y)?F(x,y)))
(3) 每个人都有一些缺点 。
或,(?x) (M(x)?(?y) (G(y)?F(x,y)))
符号化方法
1,找到所有的个体词 ;
2,是否要引入特性谓词 ;
3,描述个体词性质－性质谓词 (一元 );
描述个体词关系－关系谓词 (二元 );
4,按原命题的实际意义进行刻划。
指导变元及作用域在谓词公式中,形如 (?x)P(x)或 (?x)P(x)
的部分,叫做 公式的约束部分 。
量词?,?后面的 x叫做量词的 作用变元,或指导变元,P(x)叫做 量词的作用域 （ 辖域 ） 。
在作用域中,x的一切出现为 约束出现,非约束出现的其它变元叫 自由出现变元 。
在谓词公式中，我们还用到以下概念。
例 2.5,指出下列合式公式中的指导变元，
量词的作用域及变元约束的情况：
(1) (?x)(P(x)?(?y)R (x,y)) ；
(2) (?x)(?y)(P(x,y)?Q(y,z))?(?x)P(x,y) ；
(3) (?x)(P(x)?(?x)Q(x,z)?(?y)R(x,y))?Q(x,y) ；
解,(?y)R(x,y)中,指导变元是 y,?的作用域为 R(x,
y),其中 y是约束出现,x是自由出现的 。
(1) (?x)(P(x)?(?y)R (x,y)) ；
在整个合式公式中,x是作用变元 (指导变元 ),?的作用域 (P(x)?(?y)R(x,y)),x,y
都是约束出现的,x约束出现 2次,y约束出现 1
次。
(2) (?x) (?y) (P(x,y)? Q(y,z))? (?x) P(x,y)
在 (?x)P(x,y)中,
x是指导变元,?的作用域为 P(x,y),其中 x
约束出现 1次,y自由出现 1次 。 在整个合式公式中,x约束出现 2次,y约束出现 2次,自由出现 1次,z自由出现 1次 。
解,(?x)(?y)(P(x,y)?Q(y,z)),x,y是作用变元，两个量词?的作用域都是 (P(x,y)?Q(y,z)),其中
x,y均为约束出现,x约束出现 1次,y约束出现
2次,z为自由出现 1次。
解,(?x)Q(x,z)中 x 是作用变元,?的辖域为 Q(x,z)，
其中 x 约束出现,z自由出现；
(3) (?x)(P(x)? (?x)Q(x,z)?(?y)R(x,y))?Q(x,y) ；
(?y)R(x,y)
中,y是作用变元,?的辖域为 R(x,y),其中 y约束出现,x自由出现； 在 (?x)(P(x)?(?x) Q(x,z)?(?y)R(x,
y)) 中，作用变元为 x,?的作用域为 (P(x)?(?x)Q(x,
z)?(?y)R(x,y)),但 Q(x,z)中的 x不是?的作用变元,x,y均为约束出现,z自由出现；
在整个公式中,x约束出现 3次，自由出现
1次,y约束出现 1次，自由出现 1次,z自由出现 1次。
Q(x,y)中,x,y为自由变元。
三、谓词公式的改写考虑到谓词公式中,有的个体变项既可以约束出现,又可以自由出现,为避免这种双重性,以引起混淆,我们要将谓词公式进一步改写,改写规则如下,
(?x)(P(x)? (?x)Q(x,z)?(?y)R(x,y))?Q(x,y)
1,换名规则,
将量词作用域中出现的某个约束出现的个体变项及对应的指导变项改成另一个作用域中没有出现过的个体变项符号，公式的其余部分不变。
2,代替规则：
对某自由出现的个体变项用与原公式中所有个体变项符号不同的变项符号去代替，且处处代替。
(1) (?x)(P(x)?(?y)R (x,y)) ；
(2) (?x)(?y)(P(x,y)?Q(y,z))?(?x)P(x,y) ；
(3) (?x)(P(x)?(?x)Q(x,z)?(?y)R(x,y))?Q(x,y) ；
换名规则与代替规则可避免有的个体变项既可以约束出现，又可以自由出现。试对下列公式换名或代替 (？ )
解,(1) 不用改写
(2) 第一步换名,
(?x)(?y)(P(x,y)?Q(y,z))?(?u)P(u,y) ；
第二步代替,
(?x)(?y)(P(x,y)?Q(y,z))?(?u)P(u,v) ；
(3) 第一步换名,
(?x)(P(x)?(?u)Q(u,z)?(?y)R(x,y))?Q(x,y)
第二步代替,
(?x)(P(x)?(?u)Q(u,z)?(?y)R(x,y))?Q(s,t)
谓词合式公式的解释 (或指派 )
一个一阶逻辑合式公式中往往含有个体变项、
谓词变项等，一组使合式公式成为具有确定真值的常项（ 个体 常项,谓词 常项等）就构成了一个公式的 解释 。
主要包含以下四部分：
非空个体域、个体域上特定元素、特定函数、
特定谓词。
例 2.6 求下列谓词公式的真值：
(?x)(P(x)?Q(x)),其中 P(x),x = 1，
Q(x),x = 2,且个体域 E = {1,2}；
当个体域是有限集时，如 D ={a1,a2,……a n}
(?x)A(x)?A(a1)?A(a2)?……?A(an)
则,(?x)A(x)?A(a1)?A(a2)?……?A(an)
从而谓词公式的真值等价于命题公式的真值。
解题思想解：
(?x)(P(x)?Q(x))?(P(1)?Q(1)?(P(2)?Q(2))
(1?0)?(0?1)
0?1
0
2009-7-29 离散数学 48
例 8：给定解释 N如下,(a)DN 为自然数集合； (b)DN中特定元素 a=0；
(c)DN 上特定函数 f(x,y)= x + y,g(x,y)= x *y ； (d)DN 上特定谓词 F(x,y)为 x =y.
在解释 N下，下列公式那些为真？那些为假？
(1)? xF (g (x,a),x)；
三、谓词公式的解释（续）
(2)? x?y (F (f (x,a),y)? F (f (y,a),x))；
(3)? x?y? z F (f (x,y),z)
(4) F (f (x,y),f (y,z))
因此 (1)为假命题
x(0 = x)
解：在解释 N 下，
(1) xF (x ·0,x)
2009-7-29 离散数学 49
解：在解释 N 下,(2) x?y (F (x,y)? F (y,x))
例 8：给定解释 N 如下,(a) DN 为自然数集合； (b) DN
中特定元素 a = 0； (c) DN 上特定函数 f(x,y) = x + y,
g (x,y) = x ·y ； (d) DN 上特定谓词 F(x,y)为 x = y 。
在解释 N 下，下列公式那些为真？那些为假？
(2)? x?y (F (f (x,a),y)? F (f (y,a),x)) ；
三、谓词公式的解释（续）
因此 (2)为真命题
x?y (x = y? y = x)
2009-7-29 离散数学 50
解：在解释 N 下,(3) x?y? z F (x + y,z)
例 8：给定解释 N 如下,(a) DN 为自然数集合； (b) DN
中特定元素 a = 0； (c) DN 上特定函数 f (x,y) = x + y,
g (x,y) = x · y ； (d) DN 上特定谓词 F(x,y)为 x = y 。
在解释 N 下，下列公式那些为真？那些为假？
(3)? x?y? z F (f (x,y),z) ；
三、谓词公式的解释（续）
因此 (3)为真命题
x?y? z (x + y = z)
2009-7-29 离散数学 51
解：在解释 N 下,(4)? F (x + y,y + z)
例 8：给定解释 N 如下,(a) DN 为自然数集合； (b) DN
中特定元素 a = 0； (c) DN 上特定函数 f (x,y) = x + y,
g (x,y) = x ·y ； (d) DN 上特定谓词 F(x,y)为 x = y 。
在解释 N 下，下列公式那些为真？那些为假？
(4) F (f (x,y),f (y,z)) ；
三、谓词公式的解释（续）
真值不确定，因此 (4)不是命题
x + y = y + z
例：给定解释 I如下：
DI={2,3}；
DI中 特定的元素 a=2;
函数 f(x)为 f(2)=3,f(3)=2；
谓词 F(x)为 F(2)=0,F(3)=1;
G(x,y)为 G(i,j)=1,i,j=2,3;
L(x,y)为 L(2,2)= L(3,3)=1;
L(2,3)= L(3,2)=0.
x(F(x) ∧ G (x,a))
(F(2) ∧ G (2,2)) ∧ (F(3) ∧ G (3,2))
(0 ∧ 1) ∧ (1 ∧ 1)? 0
x(F(f(x)) ∧ G (x,f(x)))
(F(f(2)) ∧ G (2,f(2))) ∨ (F(f(3)) ∧ G (3,f(3)))
(F(3) ∧ G (2,3)) ∨ (F(2) ∧ G (3,2))
(1 ∧ 1) ∨ (0 ∧ 1)? 1
x?y L(x,y)
x(L(x,2)∨ L(x,3))
(L(2,2)∨ L(2,3)) ∧ (L(3,2)∨ L(3,3))
(1∨ 0) ∧ (0∨ 1)? 1
永真式 (逻辑有效式）,任一组解释皆使公式真值为 1
永假式,(?)
可满足式,(?)
没有一个可行的算法来判断一阶逻辑公式的类型，只能对某些 特殊的 公式进行判断 。
x(F (x)? F (x))；
代换实例,设 A0是含命题变项 p1,p2,…,p n的命题公式,A1,A2,…,An是 n 个谓词公式，
用 Ai 处处代换 pi，所得谓词公式 A称为 A0的代换实例。
例如,F(x)?G(x),?xF(x)xG(x)等是 P?Q 的代换实例。
命题公式中重言式的代换实例是逻辑有效式，
矛盾式的代换实例是矛盾式。
2009-7-29 离散数学 56
(1) 解：若?xF (x)为真，则任意的 x?D都有 F (x)为真，则?xF (x)为真，于是? xF (x) xF (x)为真。
因此公式是逻辑有效式。
2 解,p? (q? p)是重言式，所以 (2)为逻辑有效式。
(3) 解,?( p? q )? q是矛盾式，所以 (3)是矛盾式。
(2)? xF (x)? (?x? y G (x,y) xF (x))；
(3)? (F (x,y)? R (x,y))? R (x,y)；
(4)?x? y F (x,y) x? y F (x,y)。
四、谓词公式的类型（续）
例 5：判断下列公式的类型。
(1)? xF (x) xF (x)； p? q
p? (q? p)
( p? q )? q
2009-7-29 离散数学 57
(4) 解：设 DI为实数集,F (x,y)为 x + y = 0，则前件化为?x?y (x + y = 0)为真；后件为?x? y (x + y = 0)
为假，蕴涵式为假。
(2)? xF (x)? (?x? y G (x,y) xF (x))；
(3)? (F (x,y)? R (x,y))? R (x,y)；
(4)?x? y F (x,y) x? y F (x,y)。
四、谓词公式的类型（续）
例 5：判断下列公式的类型。
(1)? xF (x) xF (x)； p? q
p? (q? p)
( p? q )? q
p? q
§ 2.3 一阶逻辑等值式及前束范式一、谓词演算中常见等值式：
(I) 命题公式的推广
24个常用的命题演算等值式及其代换可推广到谓词演算中使用,如
2,(?x)P(x)?(?y)R(x,y)
(? (?x)P(x) (?y)R(x,y))
3,(?x)H(x,y) (?x)H(x,y)?F
1,(?x)(P(x)?Q(x))?(?x)(? P(x)?Q(x))
(Ⅱ ) 量词否定等值式 (量词转换律 )
(?x)P(x)? (?x)? P(x)
(?x)P(x)? (?x)? P(x)
实例：,不是所有人今天都来校上课,
,存在一些人今天没来校上课,
,没有一个人今天来校上课,
,所有的人今天都没来上课,。
(Ⅲ ) 量词作用域的扩张与收缩等值式
(?x)(A(x)?B)?((?x)A(x))?B)
(?x)(A(x)?B)?((?x)A(x))?B)
* ((?x)A(x)?B)?(?x)(A(x)?B)
(B?(?x) A(x))? (?x)(B?A(x))
(?x)(A(x)?B)?(?x)A(x)?B
(?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可含其他非指导变元。
xA (x)? B
xA (x)? B
x(? A (x))? B
x(? A (x)? B)
(Ⅳ ) 量词分配等价式
(?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) 举例？
(Ⅴ ) 多个量词的使用
(?x)(?y)A(x,y)?(?y)(?x)A(x,y)
(?x)(?y)A(x,y)? (?y)(?x)A(x,y)
注意,其他情况下量词换序后一般不等价。
前束范式：一个合式谓词公式，它的所有量词均 非否定 地出现在公式的最前面，且它们的 作用域一直延伸到公式的末尾。
如,(?x)(?y)(?z)(P(x)?F(y,z)?Q(y,z))
二、常见等值式的应用借助于常见等价式，我们仿照命题公式可以化成标准形式，也想把谓词公式化成标准形式。 谓词逻辑中，
任何谓词公式的前束范式都存在，但一般不唯一。
例 2.8 将合式公式 ((?x)P(x)?(?y)R(y))?(?x)F(x)
化为前束范式：
任一合式公式表示成前束范式可按如下步骤进行：
(1) 消去公式中出现的多余量词；
解题思想
(2) 利用双重否定定律,德? 摩根律及量词转换律将公式中的否定字符深入到谓词字母前 (否定符紧贴 )；
(3) 利用换名和代换规则使所有约束变元均不相同,
并且使自由变元也与约束变元不同 (更名 )；
(4) 利用量词作用域的扩张和收缩律,扩大量词的作用域至整个公式 (扩域 )。
解,；
(?xP(x)yR(y))xF(x)
(?xP(x)yR(y))zF(z)
(1) 更换变元符号
x?y?z((P(x)? R(y))? F(z))
(2) 扩大作用域例 2.9 求下列合式公式的前束范式
(1) (?x)P(x) (?x)Q(x)
解,(?x)P(x) (?x)Q(x)
(?x)P(x)?(?x)? Q(x)
(?x)P(x)?(?y)? Q(y)
(?x)(?y)(P(x) Q(y))
(2) (?x)P(x)?(?x)Q(x)
(?x)P(x)?(?y)Q(y)
(?x)(?y)(P(x)? Q(y))
前束合取范式：
前束范式 (?x)P(x)的命题公式部分即 P(x)为合取范式。
前束析取范式：
前束范式 (?x)P(x)的命题公式部分即 P(x)为析取范式。
§ 2.4,谓词逻辑推理理论一、常见推理定律在谓词逻辑中，如果 A1?A2?……?An?B是有效式，
即 A1?A2?……?An?B，则称该式为推理定律。
常用的推理定律主要有以下几种,
1 命题逻辑中的重言蕴涵式，在一阶逻辑中的代换实例，都是一阶逻辑中的推理定律。
例,F(x) ∧ G(x)? F(x) (化简）
(?x F(x)? G(x) ) ∧?x F(x)?G(x) (假言推理）
等等,
2 每个等值式可产生两条推理定律。
例如,?x (F(x) ∧ G(x) )x F(x) ∧?x G(x)
x (x) ∧?x G(x)x (F(x) ∧ G(x) )
等等。（即臵换定律 ）
3 量词分配推理定律
(1) (?x)A(x)?(?x)B(x)?(?x)(A(x)?B(x))
(2) (?x)(A(x)?B(x))?(?x)A(x)?(?x)B(x)
(3) (?x)(A(x)?B(x))?(?x)A(x)?(?x)B(x)
(4) (?x)(A(x)?B(x))?(?x)A(x)?(?x)B(x))
推理规则：
命题演算的所有推理规则 ;
全称量词消去规则 ;
全称量词引入规则 ;
存在量词消去规则。
二,谓词逻辑推理中遵循的推理规则存在量词引入规则 ;
(1) 全称量词消去规则 (UI规则 )：
(?x)A(x)?A(y)
(y为任意的不在 A(x)中约束出现的个体变项 )
(?x)A(x)?A(c)
(c为任意的个体域中的个体常项 )
注意,x在 A(x)中一定要是自由出现的。
(2) 全称量词引入规则 (UG规则 )：
A(y)? (?x)A(x)
要求：
(i) y在 A(y)中自由出现，且 y取任何值时
A均为真 ；
(ii) 取代 y的 x不能在 A(y)中约束出现 。
(3) 存在量词引入规则 (EG规则 )：
A(c)? (?x)A(x)
要求：
(i) c是特定的个体常项
(ii) 取代 c的 x不能已在 A(c)中出现过,
(iii) A(x)中除 x外还有其它自由出现的个体变元时，不能用此规则。
(i) c 是使 A为真的特定的个体常项 ；
(ii) c不曾在 A(x)中出现过 ；
(4) 存在量词消去规则 (EI)
xA(x)? A(c)
要求,
例 2.10 证明苏格拉底三段论,凡人都是要死的，
苏格拉底是人，所以苏格拉底是要死的,。
解题步骤
(1) 命题符号化
(2) 写出前提、结论
(3) 用推理规则进行推理 (构造证明 )
解,命题符号化,F(x),x是人
G(x),x是要死的
a,苏格拉底前提,(?x)(F(x)?G(x)),F(a)
结论,G(a)
证明,1,(?x)(F(x)?G(x)) 前提引 入
4,G(a) 2,3假言推理
2,F(a)?G(a) (1) UI规则
3,F(a) 前提引入例 2.11 证明：,每个学术会的成员都是工人并且是专家，有些成员是青年人，所以有的成员是青年专家,。
解,命题符号化,F(x),x是学术会会员
G(x),x是专家
H(x),x是工人
R(x),x是青年人前提,(?x)(F(x)?G(x)?H(x)),(?x)(F(x)?R(x))
结论,(?x)(F(x)?R(x)?G(x))
证明,1,(?x)(F(x)?R(x)) 前提引 入
4,F(c)?G(c)?H(c) (3).UI
2.F(c)?R(c) (1)EI
3,(?x)(F(x)?G(x)?H(x)) 前提引入
7,R(c) 2.化简
10,(?x)(F(x)?R(x)?G(x)) 9.EG
8,G(c) 6.化简
9,F(c)?R(c)?G(c) 5,7,8 合取
5,F(c) 2.化简
6,G(c)?H(c) 4,5 假言推理注意,如果将证明步骤改为：
1,(?x)(F(x)?G(x)?H(x))
4.F(c)?R(c)
2,F(c)?G(c)?H(c)
3,(?x)(F(x)?R(x))
…
最后也可推出 (?x)(F(x)?R(x)?G(x)),但 (4)
是有错误的，因为 (2)中 c不一定刚好满足 (3)。记住,如果前提中既有存在量词，又有全称量词，应先引入存在量词以避免上述错误。
例 2.12 构造下列推理的证明：
前提,?(?x)(F(x)?H(x))，
(?x)(G(x)?H(x))
结论,(?x)(G(x) F(x))
7) G(y) F(y) 4,6 假言三段论
8) (?x)(G(x) F(x)) 7) UG
5) (?x)(G(x)? H(x)) 前提引入
6) G(y)?H(y) 5) UI
4) H(y) F(y) 3) UI
3) (?x)(H(x) F(x)) 2)置换证明,1)? (?x)(F(x)?H(x)) 前提引人
2) (?x)(? F(x) H(x)) 1)置换前提,? (?x)(F(x)?H(x)),(?x)(G(x)?H(x))
小结与学习要求掌握谓词公式与命题公式间的关系,应特别注意变元的特性,量词,谓词公式的蕴涵与等价等内容,
以便正确,迅速地将谓词公式化为前束范式 。 还应真正了解谓词公式的推理规则,善于将语句符号化,并正确推理 。
x?y
y?x
y?x
x?y
y?x?x?y
x?y
y?x
