第 5章 一阶逻辑等值演算与推理离 散 数 学哈尔滨理工大学本科生课程计算机系本章说明
本章的主要内容
– 一阶逻辑等值式与基本等值式
– 置换规则,换名规则,代替规则
– 前束范式
– 一阶逻辑推理理论
本章与其他各章的关系
– 本章先行基础是前四章
– 本章是集合论各章的先行基础本章主要内容
5.1 一阶逻辑等值式与置换规则
5.2 一阶逻辑前束范式
5.3 一阶逻辑的推理理论
5.1 一阶逻辑等值式与置换规则
在一阶逻辑中,有些命题可以有不同的符号化形式 。
例如：没有不犯错误的人令 M(x):x是人。 F(x):x犯错误。
则将上述命题的符号化有以下两种正确形式：
(1) ┐?x(M(x)∧ ┐ F(x))
(2)?x(M(x)→F(x))
我们称 (1)和 (2)是等值的。说明等值式的定义定义 5.1 设 A,B是一阶逻辑中任意两个公式，若 A?B是永真式，则称 A与 B是 等值 的。
记做 A?B，称 A?B 是 等值式 。
G ( x ) )x ( F ( x ) G(x))x(F(x)例如：
判断公式 A与 B是否等值，等价于判断公式
A?B是否为永真式。
谓词逻辑中关于联结词的等值式与命题逻辑中相关等值式类似。
说明一阶逻辑中的一些基本而重要等值式
代换实例
消去量词等值式
量词否定等值式
量词辖域收缩与扩张等值式
量词分配等值式代换实例
由于命题逻辑中的重言式的代换实例都是一阶逻辑中的永真式，因而第二章的 16组等值式模式给出的代换实例都是一阶逻辑的等值式的模式。
例如：
(1)?xF(x)? ┐┐?xF(x) （ 双重否定律 ）
(2)F(x)→G(y)? ┐F(x)∨G(y) （ 蕴涵等值式 ）
(3)?x(F(x)→G(y))→?zH(z)
┐?x(F(x)→G(y))∨?zH(z) （ 蕴涵等值式 ）
消 去量词等值式设个体域为有限集 D={a1,a2,…,an},则有
（ 1）?xA(x)? A(a1)∧A(a 2)∧ … ∧A(a n)
（ 2）?xA(x)? A(a1)∨A(a 2)∨ … ∨A(a n)
（ 5.1）
量词否定等值式设 A(x)是任意的含自由出现个体变项 x的公式，则
（ 1） ┐?xA(x)x┐A(x)
（ 2） ┐?xA(x)x┐A(x)
说明?,并不是所有的 x都有性质 A”与,存在 x没有性质 A”是一回事。
,不存在有性质 A的 x”与,所有 X都没有性质
A”是一回事。
（ 5.2）
量词辖域收缩与扩张等值式设 A(x)是任意的含自由出现个体变项 x的公式,B中不含 x
的出现,则
（ 1）?x(A(x)∨B)xA(x)∨B
x(A(x)∧B)xA(x)∧B
x(A(x)→B)xA(x)→B
x(B→A(x))? B→?xA(x)
（ 2）?x(A(x)∨B)xA(x)∨B
x(A(x)∧B)xA(x)∧B
x(A(x)→B)xA(x)→B
x(B→A(x))? B→?xA(x)
（ 5.3）
（ 5.4）
证明,?xA(x)→Bx(A(x)→B)
xA(x)→B
┐?xA(x)∨B
x┐ A(x)∨B
x(┐ A(x)→B)
x(A(x)→B)
量词分配等值式设 A(x),B(x)是任意的含自由出现个体变项 x的公式，则
（ 1）?x(A(x)∧B(x))xA(x)∧?xB(x)
（ 2）?x(A(x)∨B(x))xA(x)∨?xB(x)
（ 5.5）
例如,,联欢会上所有人既唱歌又跳舞,和,联欢会上所有人唱歌且所有人跳舞,,这两个语句意义相同。故有
(1)式。
由 (1)式推导 (2)式
x(A(x)∧B(x))xA(x)∧?xB(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)
一阶逻辑等值演算的三条原则
置换规则,设 Φ(A) 是含公式 A的公式,Φ(B) 是用公式 B取代
Φ(A) 中所有的 A之后的公式，若 A?B，则 Φ(A)?Φ(B) 。
换名规则,设 A为一公式，将 A中某量词辖域中某约束变项的所有出现及相应的指导变元改成该量词辖域中未曾出现过的某个体变项符号，公式的其余部分不变，设所得公式为 A'，
则 A'?A。
代替规则,设 A为一公式，将 A中某个自由出现的个体变项的所有出现用 A中未曾出现过的个体变项符号代替,A中其余部分不变，设所得公式为 A'，则 A'?A。
说明? 一阶逻辑中的置换规则与命题逻辑中的置换规则形式上完全相同，只是在这里 A,B是一阶逻辑公式。
例 5.1
例 5.1 将下面公式化成与之等值的公式，使其 没有既是约束出现又是自由出现的个体变项 。
(1)?xF(x,y,z)→?yG(x,y,z)
(2)?x(F(x,y)→?yG(x,y,z))
(1)?xF(x,y,z)→?yG(x,y,z)
tF(t,y,z)→?yG(x,y,z) (换名规则 )
tF(t,y,z)→?wG(x,w,z) (换名规则 )
或?xF(x,y,z)→?yG(x,y,z)
xF(x,t,z)→?yG(x,y,z) (代替规则 )
xF(x,t,z)→?yG(w,y,z) (代替规则 )
解答例 5.1的解答
(2)?x(F(x,y)→?yG(x,y,z))
x(F(x,t)→?yG(x,y,z)) (代替规则 )
或?x(F(x,y)→?yG(x,y,z))
x(F(x,y)→?tG(x,t,z)) (换名规则 )
解答例 5.2
例 5.2 证明
（ 1）?x(A(x)∨B(x)) <≠>?xA(x)∨?xB(x)
（ 2）?x(A(x)∧B(x)) <≠>?xA(x)∧?xB(x)
其中 A(x),B(x)为含 x自由出现的公式 。
只要证明在某个解释下两边的式子不等值。
取解释 I：个体域为自然数集合 N；
(1)取 F(x),x是奇数，代替 A(x)；
取 G(x),x是偶数，代替 B(x)。
则?x(F(x)∨G(x)) 为真命题，
而?xF(x)∨? xG(x)为假命题。
两边不等值。
证明例 5.2
(2)?x(A(x)∧B(x)) <≠>?xA(x)∧?xB(x)
x(F(x)∧G(x)),有些 x既是奇数又是偶数为假命题；
而?xF(x)∧?xG(x)：有些 x是奇数并且有些 x是偶数为真命题。
两边不等值。
证明说明? 全称量词,?” 对,∨,无分配律。 存在量词,?” 对,∧,无分配律。
当 B(x)换成没有 x出现的 B时，则有
x(A(x)∨B)xA(x)∨B
x(A(x)∧B)xA(x)∧B
例 5.3—消 去量词例 5.3 设个体域为 D＝ {a,b,c},将下面各公式的量词消去：
(1)?x(F(x)→G(x))
(2)?x(F(x)∨?yG(y))
(3)?x?yF(x,y)
说明? 如果不用公式 (5.3)将量词的辖域缩小，演算过程较长。注意，此时?yG(y)是与 x无关的公式 B。
解答 (1)?x(F(x)→G(x))
(F(a)→G(a)) ∧ (F(b)→G(b)) ∧ (F(c)→G(c))
(2)?x(F(x)∨?yG(y))
xF(x)∨?yG(y) (公式 5.3)
(F(a)∧F(b)∧F(c))∨(G(a)∨G(b)∨G(c))
例 5.3—消 去量词
(3)?x?yF(x,y)
x(F(x,a)∧F(x,b)∧F(x,c))
(F(a,a)∧F(a,b)∧F(a,c))
∨(F(b,a)∧F(b,b)∧F(b,c))
∨(F(c,a)∧F(c,b)∧F(c,c))
在演算中先消去存在量词也可以，得到结果是等值的。
x?yF(x,y)
yF(a,y)∨?yF(b,y) ∨?yF(c,y)
(F(a,a)∧F(a,b)∧F(a,c))
∨(F(b,a)∧F(b,b)∧F(b,c))
∨(F(c,a)∧F(c,b)∧F(c,c))
例 5.4
例 5.4 给定解释 I如下：
（ a）个体域 D＝ {2,3}
（ b） D中特定元素
（ c） D上的特定函数 (x)为：
（ d） D的特定谓词
2a?
。,23 ( 3 )( 2 ) ff
。，为,0( 3,3 )1( 3,2 )( 2,3 )( 2,2 )y)( x, GGGGG
。，为,01 ( 3,2 )( 2,3 )( 3,3 )( 2,2 )y)( x,LLLLL
。，为,10 ( 3 )( 2 )( x ) FFF
在解释 I下求下列各式的值：
（ 1）?x(F(x)∧G(x,a))
（ 2）?x(F(f(x))∧G(x,f(x))
（ 3）?x?yL(x,y)
（ 4）?y?xL(x,y)
例 5.4的解答
（ 1）?x(F(x)∧G(x,a))
(F(2)∧G(2,2)) ∧ (F(3)∧G(3,2))
(0∧1) ∧ (1∧1)
0
（ 2）?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
例 5.4的解答
（ 3）?x?yL(x,y)
(L(2,2)∨L(2,3)) ∧ (L(3,2)∨L(3,3))
(1∨0) ∧ (0∨1)
1
（ 4）?y?xL(x,y)
y(L(2,y)∧L(3,y))
(L(2,2)∧L(3,2)) ∨ (L(2,3)∧L(3,3))
(1∧0) ∨ (0∧1)
0
说明? 由 (3),(4)的结果进一步可以说明量词的次序不能随意颠倒。
例 5.5
例 5.5 证明下列等值式。
（ 1） ┐?x(M(x)∧F(x))x(M(x)→┐F(x))
（ 2） ┐?x(F(x)→G(x))x(F(x)∧┐G(x))
（ 3） ┐?x?y(F(x)∧G(y)→H(x,y))
x?y(F(x)∧G(y)∧┐H(x,y))
（ 4） ┐?x?y(F(x)∧G(y)∧L(x,y))
x?y(F(x)∧G(y)→┐L(x,y))
例 5.5的证明
（ 1） ┐?x(M(x)∧F(x))x(M(x)→┐F(x))
┐?x(M(x)∧F(x))
x┐(M(x)∧F(x))
x(┐M(x)∨┐F(x))
x(M(x)→┐F(x))
（ 2） ┐?x(F(x)→G(x))x(F(x)∧┐G(x))
┐?x(F(x)→G(x))
x┐(F(x)→G(x))
x┐(┐F(x)∨G(x))
x(F(x)∧┐G(x))
例 5.5的证明
（ 3） ┐?x?y(F(x)∧G(y)→H(x,y))
x?y(F(x)∧G(y)∧┐H(x,y))
┐?x?y(F(x)∧G(y)→H(x,y))
x┐ (?y(F(x)∧G(y)→H(x,y)))
x?y┐ (┐(F(x)∧G(y))∨H(x,y))
x?y(F(x)∧G(y)∧┐H(x,y))
例 5.5的证明
（ 4） ┐?x?y(F(x)∧G(y)∧L(x,y))
x?y(F(x)∧G(y)→┐L(x,y))
┐?x?y(F(x)∧G(y)∧L(x,y))
x ┐(?y(F(x)∧G(y)∧L(x,y)))
x?y┐(F(x)∧G(y)∧L(x,y))
x?y(┐(F(x)∧G(y))∨┐L(x,y))
x?y(F(x)∧G(y)→┐L(x,y))
5.2 一阶逻辑前束范式定义 5.2 设 A为一个一阶逻辑公式，若 A具有如下形式
Q1x1Q2x2 … QkxkB
则称 A为 前束范式,其中 Qi(1≤i≤k) 为?或?,B为不含量词的公式。
前束范式的例子：
x?y(F(x)∧G(y)→H(x,y))
x?y?z(F(x)∧G(y)∧H(z)→L(x,y,z))
不是前束范式的例子：
x(F(x)→?y(G(y)∧H(x,y)))
x(F(x)∧?y(G(y)→H(x,y)))
前束范式存在定理定理 5.1 一阶逻辑中的任何公式都存在与之等值的前束范式。
说明? 求前束范式的过程，就是制造量词辖域可以扩大的条件，进行量词辖域扩大。
任何公式的前束范式都是存在的，但一般说来，并不唯一。
利用一阶逻辑等值式以及三条变换规则（置换规则
、换名规则、代替规则）就可以求出与公式等值的前束范式，或所谓公式的前束范式。
(1)利用量词转化公式，把否定深入到指导变元的后面。
┐?xA(x)x┐A(x)
┐?xA(x)x┐A(x)
(2)利用?x(A(x)∨B)xA(x)∨B 和?x(A(x)∧B)xA(x)∧B
把量词移到全式的最前面，这样便得到前束范式。
例 5.6 求公式的前束范式
（ 1）?xF(x)∧┐?xG(x)
xF(x)∧ ┐?yG(y) (换名规则 )
xF(x)∧?y┐G(y) ((5.2)第二式 )
x(F(x)∧?y┐G(y)) ((5.3)第二式 )
x?y(F(x)∧┐G(y)) ((5.3)第二式 )
（y?x(F(x)∧┐G(y)) ）
或者?xF(x)∧┐?xG(x)
xF(x)∧?x┐G(x) ((5.2)第二式 )
x(F(x)∧┐G(x)) ((5.5)第一式 )
例 5.6 求公式的前束范式
（ 2）?xF(x)∨ ┐?xG(x)
xF(x)∨?x┐G( x) ((5.2)第二式 )
xF(x)∨?y┐G(y) (换名规则 )
x(F(x)∨?y┐G(y)) ((5.3)第一式 )
x?y(F(x)∨┐G(y)) ((5.3)第一式 )
说明? 公式的前束范式是不唯一的。
例 5.7 求前束范式
(1)?xF(x) ∧?xG(x)
yF(y)∧?xG(x)
y?x(F(y)∧G(x))
(2)?xF(x) →?xG(x)
yF(y) →?xG(x)
y?x(F(y)→G(x))
(3)?xF(x) →?xG(x)
yF(y) →?xG(x)
y?x(F(y)→G(x))
(4)?xF(x) →?yG(y)
x?y(F(x)→G(x))
例 5.8 求公式的前束范式
(1)?xF(x,y)→?yG(x,y)
tF(t,y)→?wG(x,w) (换名规则 )
t?w(F(t,y)→G(x,w)) ((5.3),(5.4))
或者
xF(x,y)→?yG(x,y)
xF(x,t)→?yG(w,y) (代替规则 )
x?y(F(x,t)→G(w,y)) ((5.3),(5.4))
说明? 解本题时一定注意，哪些个体变项是约束出现
，哪些是自由出现，特别要注意那些既是约束出现又是自由出现的个体变项。不能混淆 。
例 5.8 求公式的前束范式
(2)(?x1F(x1,x2)→?x2G(x2)) →?x1H(x1,x2,x3)
(?x4F(x4,x2)→?x5G(x5)) →?x1H(x1,x2,x3)
x4?x5(F(x4,x2)→ G(x5)) →?x1H(x1,x2,x3)
x4?x5?x1((F(x4,x2)→ G(x5)) → H(x1,x2,x3))
5.3 一阶逻辑的推理理论
在一阶逻辑中，从前提 A1,A2,… Ak出发推结论 B的推理形式结构，依然采用如下的蕴涵式形式
A1,A2,…,Ak → B （ 5.6）
若式（ 5.6）为永真式，则称 推理正确,否则称推理不正确。
于是，在一阶逻辑中判断推理是否正确也归结为判断（ 5.6）
式是否为永真式了。
在一阶逻辑中称永真式的蕴涵式为 推理定律,若一个推理的形式结构正是某条推理定律，则这个推理显然是正确的。
在一阶逻辑的推理中，某些前提与结论可能是受量词限制，
为了使用命题逻辑中的等值式和推理定律,必须在推理过程中有消去和添加量词的规则,以便使谓词演算公式的推理过程可类似于命题演算中推理理论那样进行。
推理定律的来源
命题逻辑推理定律的代换实例
由基本等值式生成的推理定律
量词分配等值式
推理规则 —量 词消去和引入规则命题逻辑推理定律的代换实例
xF(x)∧?yG(y)xF(x) （化简律的代换实例）
xF(x)xF(x) ∨?yG(y) （附加律的代换实例）
…… ……
由基本等值式生成的推理定律
xF(x)? ┐┐?xF(x)
┐┐?xF(x)xF(x)
┐?xF(x)x┐F(x)
x┐F(x)? ┐?xF(x)
…… ……
其他推理定律
xA(x)∨?xB(x)x(A(x)∨B(x))
x(A(x)∧B(x))xA(x)∧?xB(x)
x(A(x)→B(x))xA(x)→?xB(x)
x(A(x)→B(x))xA(x)→?xB(x)
…… ……
对?x(A(x)∧B(x))xA(x)∧?xB(x)的讨论若?x(A(x)∧B(x)) 为真，则有一个客体 c，使得 A(c)∧B(c)
为真，即 A(c)和 B(c)都为真，所以?xA(x)∧?xB(x)也为真。
推理规则
为了构造推理系统，还要给出 4条重要的推理规则,
即消去量词和引入量词的规则：
1．全称量词消去规则 (简记为 UI规则或 UI)
2．全称量词引入规则 (简记为 UG规则或 UG)
3．存在量词引入规则 (简称 EG规则或 EG)
4．存在量词消去规则 (简记为 EI规则或 EI)
全称量词消去规则 (简记为 UI规则或 UI)
含义,如果个体域的所有元素都具有性质 A,则个体域中的任一元素具有性质 A。
两式成立的条件,
(1)在第一式中,取代 x的 y应为任意的不在 A(x)中约束出现的个体变项 。
(2)在第二式中,c为任意个体变项 。
(3)用 y或 c去取代 A(x)中自由出现的 x时,一定要在 x自由出现的一切地方进行取代 。
A(c)
xA(x)或
A(y)
xA(x)
全称量词消去规则 (简记为 UI规则或 UI)
举例 当 A(x)为原子公式时，比如 A(x)=F(x)，则当?xA(x)为真时，对于个体域中任意的个体变项 y，不会出现 F(y)为假的情况。
当 A(x)不是原子公式时，如 y已在 A(x)中约束出现了，
就不能用 y取代 x，否则会出现?xA(x)为真而 A(y)为假的情况。
考虑个体域为实数集合，公式 A(x)=?yF(x,y)为 x>y。
当对公式?xA(x)=?x?yF(x,y)使用 UI规则时，用 y取代 x
，就会得到 A(y)=?yF(y,y)，即?y(y>y)，这显然是假命题。原因是违背了条件 (1)。
若用 z取代 x，得 A(z)=?yF(z,y)=?y(z>y)就不会产生这种错误。
全称量词引入规则 (简记为 UG规则或 UG)
该式成立的条件是：
(1)无论 A(y)中自由出现的个体变项 y取何值,A(y)应该均为真 。
(2)取代自由出现的 y的 x也不能在 A(y)中约束出现 。
xA(x)
A(y)
举例 取个体域为实数集,F(x,y)为 x>y,A(y)=?xF(x,y)。
显然 A(y)满足条件 (1)。
对 A(y)应用 UG规则时，若取已约束出现的 x取代 y，会得到?xA(x)=?x?x(x>x)，这是假命题。
产生这种错误的原因是违背了条件 (2)。
若取 z取代 y，得?zA(z)=?z?x(x>z)为真命题。
存在量词引入规则 (简称 EG规则或 EG)
该式成立的条件是：
(1)c是特定的个体常项 。
(2)取代 c的 x不能在 A(c)中出现过 。xA(x)
A(c)
举例 取个体域为实数集,F(x,y)为 x>y，取 A(5)=?xF(x,5)。
显然 A(5)是真命题。
在应用 EG规则时，若用 A(5)中已出现的 x取代 5，得
x?xF(x,x)=?x(x>x)，这是假命题。
产生这种错误的原因是违背了条件 (2)。
若用 A(5)中未出现过的个体变项 y取代 5，得
yA(y)=?y?xF(x>y)，这为真命题。
存在量词消去规则 (简记为 EI规则或 EI)
该式成立的条件是：
(1)c是使 A为真的特定的个体常项 。
(2)c不在 A(x)中出现 。
(3)若 A(x)中除自由出现的 x外,还有其它自由出现的个体变项,此规则不能使用 。
A ( c )
x A ( x )
举例 取个体域为自然数集合,F(x)为 x是奇数,G(x)为 x是偶数
。xF(x)与?xG(x)都是真命题，则对于某些 c和 d，可以断定 P(c)∧Q(d) 必定为真，但不能断定 P(c)∧Q(c) 是真。
对?xF(x)使用 EI规则时，取代 x的 c一定是特定的个体常项
1,3,5等奇数。
对?xG(x)使用 EI规则时，取代 x的 c一定是特定的个体常项
2,4,6等偶数。
定义 5.3 自然推理系统定义
1.字母表 。 同一阶语言的字母表 。
2.合式公式 。 同合式公式的定义 。
3.推理规则：
(1)前提引入规则 。
(2)结论引入规则 。
(3)置换规则 。
(4)假言推理规则 。
(5)附加规则 。
(6)化简规则 。
(7)拒取式规则 。
(8)假言三段论规则 。
(9)析取三段论规则。
(10)构造性二难推理规则。
(11)合取引入规则。
(12)UI规则。
(13)UG规则。
(14)EG规则。
(15)EI规则。
例题例题 在自然推理系统中，构造下面推理的证明所有的人都是要死的，苏格拉底是人，所以苏格拉底是要死的。
解,先将原子命题符号化 。
设 F(x):x是一个人,G(x):x是要死的,s：苏格拉底 。
前提,?x(F(x)→G(x)),F(s)
结论,G(s)
证明,①?x(F(x)→G(x)) 前提引入
② F(s)→G(s) ① UI规则
③ F(s) 前提引入
④ G(s) ②③ 假言推理例 5.9
例 5.9 设个体域为实数集合,F(x,y)为 x>y。指出在推理系统 F
中，以?x?yF(x,y)(真命题 )为前提，推出?xF(x,c)(假命题 )的下述推理证明中的错误。
①?x?yF(x,y) 前提引入
②?yF(z,y) ① UI规则
③ F(z,c) ② EI规则
④?xF(x,c) ③ UG规则解 由于 c为特定的个体常项,所以?xF(x,c)(即为?x(x>c))为假命题 。 如果按 F中推理规则进行推理,不会从真命题推出假命题 。
在以上推理证明中,第三步错了,由于 F(z,y)中除有自由出现的 y,还有自由出现的 z,按 EI规则应该满足的条件 (3)，
此处不能用 EI规则 。 用了 EI规则,导致了从真命题推出假命题的错误 。
例 5.10
例 5.10 在自然推理系统中，构造下面推理的证明任何自然数都是整数；存在着自然数。所以存在着整数。
个体域为实数集合 R。
解,先将原子命题符号化 。
设 F(x):x为自然数,G(x):x为整数 。
前提,?x(F(x)→G(x)),?xF(x)
结论,?xG(x)
证明：
①?xF(x) 前提引入
② F(c) ① EI规则
③?x(F(x)→G(x)) 前提引入
④ F(c)→G(c) ③ UI规则
⑤ G(c) ②④ 假言推理
⑥?xG(x) ⑤ EG规则例 5.10说明
以上证明的每一步都是严格按推理规则及应满足的条件进行的 。 因此,前提的合取为真时,结论必为真 。
但如果改变命题序列的顺序会产生由真前提推出假结论的错误 。 如果证明如下进行：
①?x(F(x)→G(x)) 前提引入
② F(c)→G(c) ① UI规则
③?xF(x) 前提引入
④ F(c) ③ EI规则
在②中取 c=π,则 F(π)→G(π) 为真（前件假）,于是④中
F(π) 为假，这样从前件真推出了假的中间结果。
例 5.11
例 5.11 在自然推理系统 F中,构造下面推理的证明。
前提,?x(F(x)→G(x)),?x(F(x)∧H(x))
结论,?x(G(x） ∧ H(x))
提示 在证明序列中先引进带存在量词的前提。
例 5.11证明
①?x(F(x)∧H(x)) 前提引入
② F(c)∧H(c) ① EI规则
③?x(F(x)→G(x)) 前提引入
④ F(c)→G(c) ③ UI规则
⑤ F(c) ② 化简
⑥ G(c) ④⑤ 假言推理
⑦ H(c) ② 化简
⑧ G(c)∧H(c) ⑥⑦ 合取
⑨?(G(x） ∧ H(x)） ⑧ EG规则例 5.12
例 5.12 在自然推理系统 F中，构造下面推理的证明：
不存在能表示成分数的无理数，有理数都能表示成分数。
因此，有理数都不是无理数。
个体域为实数集合。
设 F(x):x为无理数，
G(x):x为有理数，
H(x):x能表示成分数。
前提,┐?x(F(x)∧H(x)),?x(G(x)→H(x))
结论,?x(G(x)→ ┐F(x))
解答例 5.12证明
① ┐?x(F(x)∧H(x)) 前提引入
②?x(┐F(x) ∨ ┐H(x)) ① 置换
③?x(H(x) → ┐F(x) ) ② 置换
④ H(y)→ ┐F(y) ③ UI规则
⑤?x(G(x)→H(x)) 前提引入
⑥ G(y)→H(y) ⑤ UI规则
⑦ G(y)→ ┐F(y) ⑥④ 假言三段论
⑧?x(G(x)→ ┐ F(x)) ⑦ UG规则
注意 ┐?x(F(x)∧H(x)) 不是前束范式，因而不能对它使用 EI规则。
因为结论中的量词是全称量词?，因而在使用 UI规则时用第一式，而不能用第二式。
说明本章主要内容
等值式与基本的等值式
①在有限个体域中消去量词等值式
②量词否定等值式
③量词辖域收缩与扩张等值式
④量词分配等值式
基本规则：置换规则、换名规则、代替规则
前束范式
推理理论：推理的形式结构、推理正确、构造证明
新的推理规则,UI,UG,EI,EG
学习要求
深刻理解重要的等值式,并能熟练地使用它们 。
熟练地使用置换规则,换名规则和代替规则 。
准确地求出给定公式的前束范式 （ 形式可以不唯一 ） 。
正确地使用 UI,UG,EI,EG规则,特别地要注意它们之间的关系 。
– 一定对前束范式才能使用 UI,UG,EI,EG规则,对不是前束范式的公式要使用它们,一定先求出公式的前束范式 。
– 记住 UI,UG,EI,EG规则的各自使用条件 。
– 在同一推理的证明中,如果既要使用 UI规则,又要使用 EI
规则,一定要先使用 EI规则,后使用 UI规则,而且 UI规则使用的个体常项一定是 EI规则中使用过的 。
对于给定的推理，正确地构造出它的证明。
在自然推理系统 F中构造推理的证明前提,?xF(x)→?xG(x)
结论,?x(F(x)→G(x))
证明
①?xF(x)→?xG(x) 前提引入
②?yF(y)→?xG(x) ① 置换（换名规则）
③?y?x(F(y)→G(x)) ② 置换
④?x(F(z)→G(x)) ③ UI规则
⑤ F(z)→G(z) ④ UI规则
⑥?x(F(x)→G(x)) ⑤ UG规则在自然推理系统 F中构造推理的证明前提,?x(F(x)→ G(x))
结论,?xF(x)→?xG(x)
证明
①?xF(x) 附加前提引入
② F(y) ① UI规则
③?x(F(x)→G(x)) 前提引入
④ F(y)→G(y) ③ UI规则
⑤ G(y) ②④ 假言推理
⑥?xG(x) ⑤ UG规则例题选讲例题 在自然推理系统 F中，构造下面推理的证明：
实数不是有理数就是无理数，无理数都不是分数，所以，
若有分数，则必有有理数（个体域为实数集合）
设 F(x):x是有理数，
G(x):x是无理数，
H(x):x是分数。
前提,?x(F(x)∨G(x)),?x(G(x)→ ┐H(x))
结论,?xH(x)→?xF(x)
解答例题的证明
①?xH(x) 附加前提引入
②?x(F(x)∨G(x)) 前提引入
③ H(c) ① EI规则
④ F(c)∨ G(c) ② UI规则
⑤?x(G(x)→ ┐H(x)) 前提引入
⑥ G(c)→ ┐H(c) ⑤ UI规则
⑦ ┐ G(c) ③⑥ 拒取式
⑧ F(c) ④⑦ 析取三段论
⑨?(x)F(x) ⑧ EG规则作业习题五
2,3,13,14,15,23
本章的主要内容
– 一阶逻辑等值式与基本等值式
– 置换规则,换名规则,代替规则
– 前束范式
– 一阶逻辑推理理论
本章与其他各章的关系
– 本章先行基础是前四章
– 本章是集合论各章的先行基础本章主要内容
5.1 一阶逻辑等值式与置换规则
5.2 一阶逻辑前束范式
5.3 一阶逻辑的推理理论
5.1 一阶逻辑等值式与置换规则
在一阶逻辑中,有些命题可以有不同的符号化形式 。
例如：没有不犯错误的人令 M(x):x是人。 F(x):x犯错误。
则将上述命题的符号化有以下两种正确形式：
(1) ┐?x(M(x)∧ ┐ F(x))
(2)?x(M(x)→F(x))
我们称 (1)和 (2)是等值的。说明等值式的定义定义 5.1 设 A,B是一阶逻辑中任意两个公式，若 A?B是永真式，则称 A与 B是 等值 的。
记做 A?B，称 A?B 是 等值式 。
G ( x ) )x ( F ( x ) G(x))x(F(x)例如：
判断公式 A与 B是否等值，等价于判断公式
A?B是否为永真式。
谓词逻辑中关于联结词的等值式与命题逻辑中相关等值式类似。
说明一阶逻辑中的一些基本而重要等值式
代换实例
消去量词等值式
量词否定等值式
量词辖域收缩与扩张等值式
量词分配等值式代换实例
由于命题逻辑中的重言式的代换实例都是一阶逻辑中的永真式，因而第二章的 16组等值式模式给出的代换实例都是一阶逻辑的等值式的模式。
例如：
(1)?xF(x)? ┐┐?xF(x) （ 双重否定律 ）
(2)F(x)→G(y)? ┐F(x)∨G(y) （ 蕴涵等值式 ）
(3)?x(F(x)→G(y))→?zH(z)
┐?x(F(x)→G(y))∨?zH(z) （ 蕴涵等值式 ）
消 去量词等值式设个体域为有限集 D={a1,a2,…,an},则有
（ 1）?xA(x)? A(a1)∧A(a 2)∧ … ∧A(a n)
（ 2）?xA(x)? A(a1)∨A(a 2)∨ … ∨A(a n)
（ 5.1）
量词否定等值式设 A(x)是任意的含自由出现个体变项 x的公式，则
（ 1） ┐?xA(x)x┐A(x)
（ 2） ┐?xA(x)x┐A(x)
说明?,并不是所有的 x都有性质 A”与,存在 x没有性质 A”是一回事。
,不存在有性质 A的 x”与,所有 X都没有性质
A”是一回事。
（ 5.2）
量词辖域收缩与扩张等值式设 A(x)是任意的含自由出现个体变项 x的公式,B中不含 x
的出现,则
（ 1）?x(A(x)∨B)xA(x)∨B
x(A(x)∧B)xA(x)∧B
x(A(x)→B)xA(x)→B
x(B→A(x))? B→?xA(x)
（ 2）?x(A(x)∨B)xA(x)∨B
x(A(x)∧B)xA(x)∧B
x(A(x)→B)xA(x)→B
x(B→A(x))? B→?xA(x)
（ 5.3）
（ 5.4）
证明,?xA(x)→Bx(A(x)→B)
xA(x)→B
┐?xA(x)∨B
x┐ A(x)∨B
x(┐ A(x)→B)
x(A(x)→B)
量词分配等值式设 A(x),B(x)是任意的含自由出现个体变项 x的公式，则
（ 1）?x(A(x)∧B(x))xA(x)∧?xB(x)
（ 2）?x(A(x)∨B(x))xA(x)∨?xB(x)
（ 5.5）
例如,,联欢会上所有人既唱歌又跳舞,和,联欢会上所有人唱歌且所有人跳舞,,这两个语句意义相同。故有
(1)式。
由 (1)式推导 (2)式
x(A(x)∧B(x))xA(x)∧?xB(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)
一阶逻辑等值演算的三条原则
置换规则,设 Φ(A) 是含公式 A的公式,Φ(B) 是用公式 B取代
Φ(A) 中所有的 A之后的公式，若 A?B，则 Φ(A)?Φ(B) 。
换名规则,设 A为一公式，将 A中某量词辖域中某约束变项的所有出现及相应的指导变元改成该量词辖域中未曾出现过的某个体变项符号，公式的其余部分不变，设所得公式为 A'，
则 A'?A。
代替规则,设 A为一公式，将 A中某个自由出现的个体变项的所有出现用 A中未曾出现过的个体变项符号代替,A中其余部分不变，设所得公式为 A'，则 A'?A。
说明? 一阶逻辑中的置换规则与命题逻辑中的置换规则形式上完全相同，只是在这里 A,B是一阶逻辑公式。
例 5.1
例 5.1 将下面公式化成与之等值的公式，使其 没有既是约束出现又是自由出现的个体变项 。
(1)?xF(x,y,z)→?yG(x,y,z)
(2)?x(F(x,y)→?yG(x,y,z))
(1)?xF(x,y,z)→?yG(x,y,z)
tF(t,y,z)→?yG(x,y,z) (换名规则 )
tF(t,y,z)→?wG(x,w,z) (换名规则 )
或?xF(x,y,z)→?yG(x,y,z)
xF(x,t,z)→?yG(x,y,z) (代替规则 )
xF(x,t,z)→?yG(w,y,z) (代替规则 )
解答例 5.1的解答
(2)?x(F(x,y)→?yG(x,y,z))
x(F(x,t)→?yG(x,y,z)) (代替规则 )
或?x(F(x,y)→?yG(x,y,z))
x(F(x,y)→?tG(x,t,z)) (换名规则 )
解答例 5.2
例 5.2 证明
（ 1）?x(A(x)∨B(x)) <≠>?xA(x)∨?xB(x)
（ 2）?x(A(x)∧B(x)) <≠>?xA(x)∧?xB(x)
其中 A(x),B(x)为含 x自由出现的公式 。
只要证明在某个解释下两边的式子不等值。
取解释 I：个体域为自然数集合 N；
(1)取 F(x),x是奇数，代替 A(x)；
取 G(x),x是偶数，代替 B(x)。
则?x(F(x)∨G(x)) 为真命题，
而?xF(x)∨? xG(x)为假命题。
两边不等值。
证明例 5.2
(2)?x(A(x)∧B(x)) <≠>?xA(x)∧?xB(x)
x(F(x)∧G(x)),有些 x既是奇数又是偶数为假命题；
而?xF(x)∧?xG(x)：有些 x是奇数并且有些 x是偶数为真命题。
两边不等值。
证明说明? 全称量词,?” 对,∨,无分配律。 存在量词,?” 对,∧,无分配律。
当 B(x)换成没有 x出现的 B时，则有
x(A(x)∨B)xA(x)∨B
x(A(x)∧B)xA(x)∧B
例 5.3—消 去量词例 5.3 设个体域为 D＝ {a,b,c},将下面各公式的量词消去：
(1)?x(F(x)→G(x))
(2)?x(F(x)∨?yG(y))
(3)?x?yF(x,y)
说明? 如果不用公式 (5.3)将量词的辖域缩小，演算过程较长。注意，此时?yG(y)是与 x无关的公式 B。
解答 (1)?x(F(x)→G(x))
(F(a)→G(a)) ∧ (F(b)→G(b)) ∧ (F(c)→G(c))
(2)?x(F(x)∨?yG(y))
xF(x)∨?yG(y) (公式 5.3)
(F(a)∧F(b)∧F(c))∨(G(a)∨G(b)∨G(c))
例 5.3—消 去量词
(3)?x?yF(x,y)
x(F(x,a)∧F(x,b)∧F(x,c))
(F(a,a)∧F(a,b)∧F(a,c))
∨(F(b,a)∧F(b,b)∧F(b,c))
∨(F(c,a)∧F(c,b)∧F(c,c))
在演算中先消去存在量词也可以，得到结果是等值的。
x?yF(x,y)
yF(a,y)∨?yF(b,y) ∨?yF(c,y)
(F(a,a)∧F(a,b)∧F(a,c))
∨(F(b,a)∧F(b,b)∧F(b,c))
∨(F(c,a)∧F(c,b)∧F(c,c))
例 5.4
例 5.4 给定解释 I如下：
（ a）个体域 D＝ {2,3}
（ b） D中特定元素
（ c） D上的特定函数 (x)为：
（ d） D的特定谓词
2a?
。,23 ( 3 )( 2 ) ff
。，为,0( 3,3 )1( 3,2 )( 2,3 )( 2,2 )y)( x, GGGGG
。，为,01 ( 3,2 )( 2,3 )( 3,3 )( 2,2 )y)( x,LLLLL
。，为,10 ( 3 )( 2 )( x ) FFF
在解释 I下求下列各式的值：
（ 1）?x(F(x)∧G(x,a))
（ 2）?x(F(f(x))∧G(x,f(x))
（ 3）?x?yL(x,y)
（ 4）?y?xL(x,y)
例 5.4的解答
（ 1）?x(F(x)∧G(x,a))
(F(2)∧G(2,2)) ∧ (F(3)∧G(3,2))
(0∧1) ∧ (1∧1)
0
（ 2）?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
例 5.4的解答
（ 3）?x?yL(x,y)
(L(2,2)∨L(2,3)) ∧ (L(3,2)∨L(3,3))
(1∨0) ∧ (0∨1)
1
（ 4）?y?xL(x,y)
y(L(2,y)∧L(3,y))
(L(2,2)∧L(3,2)) ∨ (L(2,3)∧L(3,3))
(1∧0) ∨ (0∧1)
0
说明? 由 (3),(4)的结果进一步可以说明量词的次序不能随意颠倒。
例 5.5
例 5.5 证明下列等值式。
（ 1） ┐?x(M(x)∧F(x))x(M(x)→┐F(x))
（ 2） ┐?x(F(x)→G(x))x(F(x)∧┐G(x))
（ 3） ┐?x?y(F(x)∧G(y)→H(x,y))
x?y(F(x)∧G(y)∧┐H(x,y))
（ 4） ┐?x?y(F(x)∧G(y)∧L(x,y))
x?y(F(x)∧G(y)→┐L(x,y))
例 5.5的证明
（ 1） ┐?x(M(x)∧F(x))x(M(x)→┐F(x))
┐?x(M(x)∧F(x))
x┐(M(x)∧F(x))
x(┐M(x)∨┐F(x))
x(M(x)→┐F(x))
（ 2） ┐?x(F(x)→G(x))x(F(x)∧┐G(x))
┐?x(F(x)→G(x))
x┐(F(x)→G(x))
x┐(┐F(x)∨G(x))
x(F(x)∧┐G(x))
例 5.5的证明
（ 3） ┐?x?y(F(x)∧G(y)→H(x,y))
x?y(F(x)∧G(y)∧┐H(x,y))
┐?x?y(F(x)∧G(y)→H(x,y))
x┐ (?y(F(x)∧G(y)→H(x,y)))
x?y┐ (┐(F(x)∧G(y))∨H(x,y))
x?y(F(x)∧G(y)∧┐H(x,y))
例 5.5的证明
（ 4） ┐?x?y(F(x)∧G(y)∧L(x,y))
x?y(F(x)∧G(y)→┐L(x,y))
┐?x?y(F(x)∧G(y)∧L(x,y))
x ┐(?y(F(x)∧G(y)∧L(x,y)))
x?y┐(F(x)∧G(y)∧L(x,y))
x?y(┐(F(x)∧G(y))∨┐L(x,y))
x?y(F(x)∧G(y)→┐L(x,y))
5.2 一阶逻辑前束范式定义 5.2 设 A为一个一阶逻辑公式，若 A具有如下形式
Q1x1Q2x2 … QkxkB
则称 A为 前束范式,其中 Qi(1≤i≤k) 为?或?,B为不含量词的公式。
前束范式的例子：
x?y(F(x)∧G(y)→H(x,y))
x?y?z(F(x)∧G(y)∧H(z)→L(x,y,z))
不是前束范式的例子：
x(F(x)→?y(G(y)∧H(x,y)))
x(F(x)∧?y(G(y)→H(x,y)))
前束范式存在定理定理 5.1 一阶逻辑中的任何公式都存在与之等值的前束范式。
说明? 求前束范式的过程，就是制造量词辖域可以扩大的条件，进行量词辖域扩大。
任何公式的前束范式都是存在的，但一般说来，并不唯一。
利用一阶逻辑等值式以及三条变换规则（置换规则
、换名规则、代替规则）就可以求出与公式等值的前束范式，或所谓公式的前束范式。
(1)利用量词转化公式，把否定深入到指导变元的后面。
┐?xA(x)x┐A(x)
┐?xA(x)x┐A(x)
(2)利用?x(A(x)∨B)xA(x)∨B 和?x(A(x)∧B)xA(x)∧B
把量词移到全式的最前面，这样便得到前束范式。
例 5.6 求公式的前束范式
（ 1）?xF(x)∧┐?xG(x)
xF(x)∧ ┐?yG(y) (换名规则 )
xF(x)∧?y┐G(y) ((5.2)第二式 )
x(F(x)∧?y┐G(y)) ((5.3)第二式 )
x?y(F(x)∧┐G(y)) ((5.3)第二式 )
（y?x(F(x)∧┐G(y)) ）
或者?xF(x)∧┐?xG(x)
xF(x)∧?x┐G(x) ((5.2)第二式 )
x(F(x)∧┐G(x)) ((5.5)第一式 )
例 5.6 求公式的前束范式
（ 2）?xF(x)∨ ┐?xG(x)
xF(x)∨?x┐G( x) ((5.2)第二式 )
xF(x)∨?y┐G(y) (换名规则 )
x(F(x)∨?y┐G(y)) ((5.3)第一式 )
x?y(F(x)∨┐G(y)) ((5.3)第一式 )
说明? 公式的前束范式是不唯一的。
例 5.7 求前束范式
(1)?xF(x) ∧?xG(x)
yF(y)∧?xG(x)
y?x(F(y)∧G(x))
(2)?xF(x) →?xG(x)
yF(y) →?xG(x)
y?x(F(y)→G(x))
(3)?xF(x) →?xG(x)
yF(y) →?xG(x)
y?x(F(y)→G(x))
(4)?xF(x) →?yG(y)
x?y(F(x)→G(x))
例 5.8 求公式的前束范式
(1)?xF(x,y)→?yG(x,y)
tF(t,y)→?wG(x,w) (换名规则 )
t?w(F(t,y)→G(x,w)) ((5.3),(5.4))
或者
xF(x,y)→?yG(x,y)
xF(x,t)→?yG(w,y) (代替规则 )
x?y(F(x,t)→G(w,y)) ((5.3),(5.4))
说明? 解本题时一定注意，哪些个体变项是约束出现
，哪些是自由出现，特别要注意那些既是约束出现又是自由出现的个体变项。不能混淆 。
例 5.8 求公式的前束范式
(2)(?x1F(x1,x2)→?x2G(x2)) →?x1H(x1,x2,x3)
(?x4F(x4,x2)→?x5G(x5)) →?x1H(x1,x2,x3)
x4?x5(F(x4,x2)→ G(x5)) →?x1H(x1,x2,x3)
x4?x5?x1((F(x4,x2)→ G(x5)) → H(x1,x2,x3))
5.3 一阶逻辑的推理理论
在一阶逻辑中，从前提 A1,A2,… Ak出发推结论 B的推理形式结构，依然采用如下的蕴涵式形式
A1,A2,…,Ak → B （ 5.6）
若式（ 5.6）为永真式，则称 推理正确,否则称推理不正确。
于是，在一阶逻辑中判断推理是否正确也归结为判断（ 5.6）
式是否为永真式了。
在一阶逻辑中称永真式的蕴涵式为 推理定律,若一个推理的形式结构正是某条推理定律，则这个推理显然是正确的。
在一阶逻辑的推理中，某些前提与结论可能是受量词限制，
为了使用命题逻辑中的等值式和推理定律,必须在推理过程中有消去和添加量词的规则,以便使谓词演算公式的推理过程可类似于命题演算中推理理论那样进行。
推理定律的来源
命题逻辑推理定律的代换实例
由基本等值式生成的推理定律
量词分配等值式
推理规则 —量 词消去和引入规则命题逻辑推理定律的代换实例
xF(x)∧?yG(y)xF(x) （化简律的代换实例）
xF(x)xF(x) ∨?yG(y) （附加律的代换实例）
…… ……
由基本等值式生成的推理定律
xF(x)? ┐┐?xF(x)
┐┐?xF(x)xF(x)
┐?xF(x)x┐F(x)
x┐F(x)? ┐?xF(x)
…… ……
其他推理定律
xA(x)∨?xB(x)x(A(x)∨B(x))
x(A(x)∧B(x))xA(x)∧?xB(x)
x(A(x)→B(x))xA(x)→?xB(x)
x(A(x)→B(x))xA(x)→?xB(x)
…… ……
对?x(A(x)∧B(x))xA(x)∧?xB(x)的讨论若?x(A(x)∧B(x)) 为真，则有一个客体 c，使得 A(c)∧B(c)
为真，即 A(c)和 B(c)都为真，所以?xA(x)∧?xB(x)也为真。
推理规则
为了构造推理系统，还要给出 4条重要的推理规则,
即消去量词和引入量词的规则：
1．全称量词消去规则 (简记为 UI规则或 UI)
2．全称量词引入规则 (简记为 UG规则或 UG)
3．存在量词引入规则 (简称 EG规则或 EG)
4．存在量词消去规则 (简记为 EI规则或 EI)
全称量词消去规则 (简记为 UI规则或 UI)
含义,如果个体域的所有元素都具有性质 A,则个体域中的任一元素具有性质 A。
两式成立的条件,
(1)在第一式中,取代 x的 y应为任意的不在 A(x)中约束出现的个体变项 。
(2)在第二式中,c为任意个体变项 。
(3)用 y或 c去取代 A(x)中自由出现的 x时,一定要在 x自由出现的一切地方进行取代 。
A(c)
xA(x)或
A(y)
xA(x)
全称量词消去规则 (简记为 UI规则或 UI)
举例 当 A(x)为原子公式时，比如 A(x)=F(x)，则当?xA(x)为真时，对于个体域中任意的个体变项 y，不会出现 F(y)为假的情况。
当 A(x)不是原子公式时，如 y已在 A(x)中约束出现了，
就不能用 y取代 x，否则会出现?xA(x)为真而 A(y)为假的情况。
考虑个体域为实数集合，公式 A(x)=?yF(x,y)为 x>y。
当对公式?xA(x)=?x?yF(x,y)使用 UI规则时，用 y取代 x
，就会得到 A(y)=?yF(y,y)，即?y(y>y)，这显然是假命题。原因是违背了条件 (1)。
若用 z取代 x，得 A(z)=?yF(z,y)=?y(z>y)就不会产生这种错误。
全称量词引入规则 (简记为 UG规则或 UG)
该式成立的条件是：
(1)无论 A(y)中自由出现的个体变项 y取何值,A(y)应该均为真 。
(2)取代自由出现的 y的 x也不能在 A(y)中约束出现 。
xA(x)
A(y)
举例 取个体域为实数集,F(x,y)为 x>y,A(y)=?xF(x,y)。
显然 A(y)满足条件 (1)。
对 A(y)应用 UG规则时，若取已约束出现的 x取代 y，会得到?xA(x)=?x?x(x>x)，这是假命题。
产生这种错误的原因是违背了条件 (2)。
若取 z取代 y，得?zA(z)=?z?x(x>z)为真命题。
存在量词引入规则 (简称 EG规则或 EG)
该式成立的条件是：
(1)c是特定的个体常项 。
(2)取代 c的 x不能在 A(c)中出现过 。xA(x)
A(c)
举例 取个体域为实数集,F(x,y)为 x>y，取 A(5)=?xF(x,5)。
显然 A(5)是真命题。
在应用 EG规则时，若用 A(5)中已出现的 x取代 5，得
x?xF(x,x)=?x(x>x)，这是假命题。
产生这种错误的原因是违背了条件 (2)。
若用 A(5)中未出现过的个体变项 y取代 5，得
yA(y)=?y?xF(x>y)，这为真命题。
存在量词消去规则 (简记为 EI规则或 EI)
该式成立的条件是：
(1)c是使 A为真的特定的个体常项 。
(2)c不在 A(x)中出现 。
(3)若 A(x)中除自由出现的 x外,还有其它自由出现的个体变项,此规则不能使用 。
A ( c )
x A ( x )
举例 取个体域为自然数集合,F(x)为 x是奇数,G(x)为 x是偶数
。xF(x)与?xG(x)都是真命题，则对于某些 c和 d，可以断定 P(c)∧Q(d) 必定为真，但不能断定 P(c)∧Q(c) 是真。
对?xF(x)使用 EI规则时，取代 x的 c一定是特定的个体常项
1,3,5等奇数。
对?xG(x)使用 EI规则时，取代 x的 c一定是特定的个体常项
2,4,6等偶数。
定义 5.3 自然推理系统定义
1.字母表 。 同一阶语言的字母表 。
2.合式公式 。 同合式公式的定义 。
3.推理规则：
(1)前提引入规则 。
(2)结论引入规则 。
(3)置换规则 。
(4)假言推理规则 。
(5)附加规则 。
(6)化简规则 。
(7)拒取式规则 。
(8)假言三段论规则 。
(9)析取三段论规则。
(10)构造性二难推理规则。
(11)合取引入规则。
(12)UI规则。
(13)UG规则。
(14)EG规则。
(15)EI规则。
例题例题 在自然推理系统中，构造下面推理的证明所有的人都是要死的，苏格拉底是人，所以苏格拉底是要死的。
解,先将原子命题符号化 。
设 F(x):x是一个人,G(x):x是要死的,s：苏格拉底 。
前提,?x(F(x)→G(x)),F(s)
结论,G(s)
证明,①?x(F(x)→G(x)) 前提引入
② F(s)→G(s) ① UI规则
③ F(s) 前提引入
④ G(s) ②③ 假言推理例 5.9
例 5.9 设个体域为实数集合,F(x,y)为 x>y。指出在推理系统 F
中，以?x?yF(x,y)(真命题 )为前提，推出?xF(x,c)(假命题 )的下述推理证明中的错误。
①?x?yF(x,y) 前提引入
②?yF(z,y) ① UI规则
③ F(z,c) ② EI规则
④?xF(x,c) ③ UG规则解 由于 c为特定的个体常项,所以?xF(x,c)(即为?x(x>c))为假命题 。 如果按 F中推理规则进行推理,不会从真命题推出假命题 。
在以上推理证明中,第三步错了,由于 F(z,y)中除有自由出现的 y,还有自由出现的 z,按 EI规则应该满足的条件 (3)，
此处不能用 EI规则 。 用了 EI规则,导致了从真命题推出假命题的错误 。
例 5.10
例 5.10 在自然推理系统中，构造下面推理的证明任何自然数都是整数；存在着自然数。所以存在着整数。
个体域为实数集合 R。
解,先将原子命题符号化 。
设 F(x):x为自然数,G(x):x为整数 。
前提,?x(F(x)→G(x)),?xF(x)
结论,?xG(x)
证明：
①?xF(x) 前提引入
② F(c) ① EI规则
③?x(F(x)→G(x)) 前提引入
④ F(c)→G(c) ③ UI规则
⑤ G(c) ②④ 假言推理
⑥?xG(x) ⑤ EG规则例 5.10说明
以上证明的每一步都是严格按推理规则及应满足的条件进行的 。 因此,前提的合取为真时,结论必为真 。
但如果改变命题序列的顺序会产生由真前提推出假结论的错误 。 如果证明如下进行：
①?x(F(x)→G(x)) 前提引入
② F(c)→G(c) ① UI规则
③?xF(x) 前提引入
④ F(c) ③ EI规则
在②中取 c=π,则 F(π)→G(π) 为真（前件假）,于是④中
F(π) 为假，这样从前件真推出了假的中间结果。
例 5.11
例 5.11 在自然推理系统 F中,构造下面推理的证明。
前提,?x(F(x)→G(x)),?x(F(x)∧H(x))
结论,?x(G(x） ∧ H(x))
提示 在证明序列中先引进带存在量词的前提。
例 5.11证明
①?x(F(x)∧H(x)) 前提引入
② F(c)∧H(c) ① EI规则
③?x(F(x)→G(x)) 前提引入
④ F(c)→G(c) ③ UI规则
⑤ F(c) ② 化简
⑥ G(c) ④⑤ 假言推理
⑦ H(c) ② 化简
⑧ G(c)∧H(c) ⑥⑦ 合取
⑨?(G(x） ∧ H(x)） ⑧ EG规则例 5.12
例 5.12 在自然推理系统 F中，构造下面推理的证明：
不存在能表示成分数的无理数，有理数都能表示成分数。
因此，有理数都不是无理数。
个体域为实数集合。
设 F(x):x为无理数，
G(x):x为有理数，
H(x):x能表示成分数。
前提,┐?x(F(x)∧H(x)),?x(G(x)→H(x))
结论,?x(G(x)→ ┐F(x))
解答例 5.12证明
① ┐?x(F(x)∧H(x)) 前提引入
②?x(┐F(x) ∨ ┐H(x)) ① 置换
③?x(H(x) → ┐F(x) ) ② 置换
④ H(y)→ ┐F(y) ③ UI规则
⑤?x(G(x)→H(x)) 前提引入
⑥ G(y)→H(y) ⑤ UI规则
⑦ G(y)→ ┐F(y) ⑥④ 假言三段论
⑧?x(G(x)→ ┐ F(x)) ⑦ UG规则
注意 ┐?x(F(x)∧H(x)) 不是前束范式，因而不能对它使用 EI规则。
因为结论中的量词是全称量词?，因而在使用 UI规则时用第一式，而不能用第二式。
说明本章主要内容
等值式与基本的等值式
①在有限个体域中消去量词等值式
②量词否定等值式
③量词辖域收缩与扩张等值式
④量词分配等值式
基本规则：置换规则、换名规则、代替规则
前束范式
推理理论：推理的形式结构、推理正确、构造证明
新的推理规则,UI,UG,EI,EG
学习要求
深刻理解重要的等值式,并能熟练地使用它们 。
熟练地使用置换规则,换名规则和代替规则 。
准确地求出给定公式的前束范式 （ 形式可以不唯一 ） 。
正确地使用 UI,UG,EI,EG规则,特别地要注意它们之间的关系 。
– 一定对前束范式才能使用 UI,UG,EI,EG规则,对不是前束范式的公式要使用它们,一定先求出公式的前束范式 。
– 记住 UI,UG,EI,EG规则的各自使用条件 。
– 在同一推理的证明中,如果既要使用 UI规则,又要使用 EI
规则,一定要先使用 EI规则,后使用 UI规则,而且 UI规则使用的个体常项一定是 EI规则中使用过的 。
对于给定的推理，正确地构造出它的证明。
在自然推理系统 F中构造推理的证明前提,?xF(x)→?xG(x)
结论,?x(F(x)→G(x))
证明
①?xF(x)→?xG(x) 前提引入
②?yF(y)→?xG(x) ① 置换（换名规则）
③?y?x(F(y)→G(x)) ② 置换
④?x(F(z)→G(x)) ③ UI规则
⑤ F(z)→G(z) ④ UI规则
⑥?x(F(x)→G(x)) ⑤ UG规则在自然推理系统 F中构造推理的证明前提,?x(F(x)→ G(x))
结论,?xF(x)→?xG(x)
证明
①?xF(x) 附加前提引入
② F(y) ① UI规则
③?x(F(x)→G(x)) 前提引入
④ F(y)→G(y) ③ UI规则
⑤ G(y) ②④ 假言推理
⑥?xG(x) ⑤ UG规则例题选讲例题 在自然推理系统 F中，构造下面推理的证明：
实数不是有理数就是无理数，无理数都不是分数，所以，
若有分数，则必有有理数（个体域为实数集合）
设 F(x):x是有理数，
G(x):x是无理数，
H(x):x是分数。
前提,?x(F(x)∨G(x)),?x(G(x)→ ┐H(x))
结论,?xH(x)→?xF(x)
解答例题的证明
①?xH(x) 附加前提引入
②?x(F(x)∨G(x)) 前提引入
③ H(c) ① EI规则
④ F(c)∨ G(c) ② UI规则
⑤?x(G(x)→ ┐H(x)) 前提引入
⑥ G(c)→ ┐H(c) ⑤ UI规则
⑦ ┐ G(c) ③⑥ 拒取式
⑧ F(c) ④⑦ 析取三段论
⑨?(x)F(x) ⑧ EG规则作业习题五
2,3,13,14,15,23
