第5章 一阶逻辑等值演算与推理

1主要内容一阶逻辑等值式与基本的等值式置换规则、换名规则、代替规则前束范式自然推理系统NL及其推理规则第五章一阶逻辑等值演算与推理25.1一阶逻辑等值式与置换规则在一阶逻辑中，有些命题可以有不同的形式例如命题：没有不犯错误的人。

设F(x):x是人，G(x):x犯错误(1)x(F(x)G(x))或(2)x(F(x)G(x))定义5.1

设A,B是两个谓词公式,如果AB是永真式,则称A与B等值,记作AB,并称AB是等值式显然，AB当且仅当在任何解释I和I中的任意赋值υ下，A与B有相同的真值。即在I和υ下,A为真当且仅当B为真，或者，A为假当且仅当B为假。同时，要证明两个公式不等值，只需找到一个解释I和I中的一个赋值υ，使得两个公式在I和υ下，一个为真，另一个为假。35.1一阶逻辑等值式与置换规则由定义5.1

可知，判断公式A与B是否等值，等价于判断公式AB是否为永真式,同命题逻辑中一样，证明了一些常用的重要等值式，并用这些等值式推演出更多的等值式基本等值式第一组命题逻辑中16组基本等值式的代换实例

例如，AA(2.1)

xF(x)xF(x),

AB

AB

(2.12)xF(x)yG(y)

xF(x)yG(y)等第二组(1)消去量词等值式

设个体为有限集D={a1,a2,…,an}①xA(x)A(a1)A(a2)…A(an)②xA(x)A(a1)A(a2)…A(an)4基本等值式(2)量词否定等值式①xA(x)xA(x)②xA(x)xA(x)证明

(1)在任何解释I下，xA(x)表示“在个体域D中，并非所有的x都具有性质A”，

而xA(x)

表示“在个体域D中，至少有一个x不具有性质A”，

两个命题的含义是一样的，因此它们同真或同假，它们是等值的。(2)在个体域D中，”不存在有性质A的x”与“所有的x都没有性质A”是同一回事。5基本等值式(3)量词辖域收缩与扩张等值式.

设A(x)是含x自由出现的公式，B中不含x的自由出现。则：

关于全称量词的：①x(A(x)B)

xA(x)B②x(A(x)B)

xA(x)B③x(A(x)B)

xA(x)B④x(BA(x))

BxA(x)6证明证明(1)

x(A(x)B)

xA(x)B

在任何解释I和I中的任意赋值υ下，

xA(x)B=0（∨表示取大）当且仅当xA(x)=0且B=0（只能每项都取0）

当且仅当B=0且对于DI中的每一个元素c，有A(c)=0当且仅当对于DI中的每一个元素c，有A(c)∨B=0当且仅当x(A(x)∨B)=0

(2)x(A(x)B)

xA(x)B

在任何解释I和I中的任意赋值υ下，

xA(x)∧B=1（∧表示取小）

当且仅当xA(x)=1且B=1（只能每项都取1）当且仅当B=1且对于DI中的每一个元素c，A(c)=1当且仅当对于DI中的每一个元素c，A(c)∧B=1当且仅当x(A(x)B)=17证明证明

第(3)式:x(A(x)B)

xA(x)B

x(A(x)B)

x(A(x)∨B)

xA(x)∨B(5.3)①

xA(x)∨B(5.2)

xA(x)B

第(4)式:x(BA(x))

BxA(x)

x(BA(x))

x(BA(x))

BxA(x)(5.3)①

BxA(x)8基本等值式

关于存在量词的：①x(A(x)B)

xA(x)B②x(A(x)B)

xA(x)B③x(A(x)B)

xA(x)B④x(BA(x))

BxA(x)证明：方法一：(2)x(A(x)B)

xA(x)BxA(x)B

((xA(x)B))

(xA(x)B))

(xA(x)B)

(x(A(x)B))

(x(A(x)B))

x(A(x)B)

9证明证明方法二：(1)

x(A(x)B)

xA(x)B

在任何解释I和I中的任意赋值υ下，

xA(x)B=0（∨表示取大）当且仅当xA(x)=0且B=0（只能每项都取0）

当且仅当B=0且存在DI中的元素c，使得A(c)=0当且仅当存在DI中的元素c，使得A(c)∨B=0当且仅当x(A(x)B)=0

(2)

x(A(x)B)

xA(x)B

在任何解释I和I中的任意赋值υ下，

xA(x)B=1（∧表示取小）

当且仅当xA(x)=1且B=1（只能每项都取1）当且仅当B=1且存在DI中的元素c，A(c)=1当且仅当存在DI中的元素c，A(c)∧B=1当且仅当x(A(x)B)=110基本等值式(4)量词分配等值式①x(A(x)B(x))

xA(x)xB(x)②x(A(x)B(x))

xA(x)xB(x)证明

(1)在任何解释I和I中的任意赋值υ下，

x(A(x)∧B(x))=1当且仅当对于DI中的每一个元素c，A(c)∧B(c)=1当且仅当对于DI中的每一个元素c，A(c)=1且B(c)=1当且仅当xA(x)=1且xB(x)=1当且仅当xA(x)∧xB(x)=1注意：对，对无分配律，见例5.211证明例5.2证明（1）x(A(x)B(x))不等值于xA(x)xB(x)（2）x(A(x)B(x))不等值于xA(x)xB(x)证明给定解释I：DI为自然数集，A(x)为x是奇数，B(x)为x是偶数。在DI下，x(A(x)∨B(x))意为“所有的自然数，或是奇数，或是偶数”，是真命题，而xA(x)∨xB(x)意为“所有的自然数是奇数，或者所有的自然数是偶数”，是假命题。

因此，x(A(x)∨B(x))与xA(x)∨xB(x)不等值。

(2)x(A(x)∧B(x))意为“存在着自然数x，x既是奇数又是偶数”，显然这是一个假命题，

而xA(x)∧xB(x)意为“有自然数是奇数并且也有自然数是偶数”，是真命题，

因此，xA(x)∧xB(x)与x(A(x)∧B(x))不等值。12置换规则、换名规则、代替规则1.置换规则设(A)是含A的公式,那么,若AB,则(A)(B).2.换名规则

设A为一公式，将A中某量词辖域中个体变项的所有约束出现及相应的指导变元换成该量词辖域中未曾出现过的个体变项符号，其余部分不变，设所得公式为A，则AA.3.代替规则

设A为一公式，将A中某个个体变项的所有自由出现用A中

未曾出现过的个体变项符号代替，其余部分不变，设所得

公式为A，则AA.13实例例5.1

将公式化成等值的不含既有约束出现、又有自由出现的个体变项:(1)xF(x,y,z)yG(x,y,z)解:公式中x,y都是既有约束出现、又有自由出现的个体变项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)

代替规则14实例例5.1

将公式化成等值的不含既有约束出现、又有自由出现的个体变项:(2)x(F(x,y)yG(x,y,z))解公式中y都是既有约束出现yG(x,y,z)、又有自由出现F(x,y)的个体变项，需要处理。x只有约束出现，z只有自由出现，保持不变。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))

换名规则

15实例例5.1

将公式化成等值的不含既有约束出现、又有自由出现的个体变项:(3)x(F(x,y,z)yG(x,y,z))解x(F(x,y,z)yG(x,y,z))x(F(x,y,z)tG(x,t,z))

换名规则xt(F(x,y,z)G(x,t,z))

辖域扩张等值式或者x(F(x,y,z)yG(x,y,z))x(F(x,u,z)yG(x,y,z))

代替规则xy(F(x,u,z)G(x,y,z))

辖域扩张等值式16实例例3

设个体域D={a,b,c},消去下述公式中的量词:(1)xy(F(x)G(y))(2)xyF(x,y)解法一xy(F(x)G(y))(y(F(a)G(y)))(y(F(b)G(y)))(y(F(c)G(y)))((F(a)G(a))(F(a)G(b))(F(a)G(c)))((F(b)G(a))(F(b)G(b))(F(b)G(c)))

((F(c)G(a))(F(c)G(b))(F(c)G(c)))

17实例解法二xy(F(x)G(y))x(F(x)yG(y))辖域缩小等值式x(F(x)G(a)G(b)G(c))(F(a)G(a)G(b)G(c))

(F(b)G(a)G(b)G(c))(F(c)G(a)G(b)G(c))18实例(2)xyF(x,y)xyF(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))19实例例5.4给定解释I如下（1）个体域D={2、3}（2）D中特定元素a=2（3）D中特定函数f(x):f(2)=3、f(3)=2（4）D上的特定谓词G（x、y)为：G（2、2）=G（2、3）=G（3、2）=1，G（3、3）=0L（2、2）=L（3、3）=1、L（2、3）=L（3、2）=0F（x）为:F（2）=0、F（3）=1在I下求下列各式的真值(1)x(F(x)G(x、a))(2)x(F(f(x))G(x、f(x)))(3)xyL(x、y)(4)xyL(x、y)20实例(类似例5.4)设解释I为：DI={2，3}，f(2)=3，f(3)=2，

F(2，2)=F(2，3)=0，F(3，2)=F(3，3)=1。

在I下消去下列公式的量词并求真值。

(1)F(2，f(2))∧F(3，f(3))

(2)xyF(y，x)

(3)x(F(x,f(x))→yF(f(x),f(y)))解

(1)式中不含量词，所以直接求真值。

F(2，f(2))∧F(3，f(3))

F(2，3)∧F(3，2)

0∧1

0

21(2)xyF(y,x)

x((F(2，x)∨F(3，x)))

(F(2，2)∨F(3，2))∧(F(2，3)∨F(3，3))

(0∨1)∧(0∨1)

1∧1

1(类似例5.4)设解释I为：DI={2，3}，f(2)=3，f(3)=2，

F(2，2)=F(2，3)=0，F(3，2)=F(3，3)=1。22(3)x(F(x，f(x))→yF(f(x)，f(y)))(F(2,f(2))→yF(f(2),f(y)))∧(F(3,f(3))→yF(f(3),f(y))(F(2,f(2))→(F(f(2),f(2))∧F(f(2),f(3))))

∧(F(3,f(3))→(F(f(3),f(2))∧F(f(3),f(3))))

(F(2,3)→(F(3,3)∧F(3,2)))∧(F(3,2)→(F(2,3)∧F(2,2))

(0→(1∧1))∧(1→(0∧0))

(0→1)∧(1→0)

1∧00(类似例5.4)设解释I为：DI={2，3}，f(2)=3，f(3)=2，

F(2，2)=F(2，3)=0，F(3，2)=F(3，3)=1。23实例例1(例5.5)将下面命题用两种形式符号化,并证明两者等值:(1)没有不犯错误的人解令F(x)：x是人，G(x)：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))置换

x(F(x)G(x))置换24实例(2)不是所有的人都爱看电影解令F(x)：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))置换

x(F(x)G(x))置换25实例例5.5证明下列各等值式。（1）x(M(x)F(x))x(Mx)F(x))（2）x(F(x)G(x))x(F(x)G(x))（3）xy(F(x)G(y)H(x,y))xy(F(x)G(y)H(x,y)（4）xy(F(x)G(y)L(x,y))xy(F(x)G(y)L(x,y))证明（3）xy(F(x)G(y)H(x,y))xy((F(x)G(y))H(x,y))x(y((F(x)G(y))H(x,y)))xy((F(x)G(y))H(x,y))xy(F(x)G(y)H(x,y))（4）xy(F(x)G(y)L(x,y))x(y(F(x)G(y)L(x,y)))xy(F(x)G(y)L(x,y))

xy((F(x)G(y))L(x,y))xy(F(x)G(y)L(x,y))265.2一阶逻辑前束范式定义5.2

设A为一个一阶逻辑公式，若A具有如下形式

Q1x1Q2x2…QkxkB则称A为前束范式，其中Qi(1

i

k)为或，B为不含量词的公式.例如，x(F(x)G(x))

xy(F(x)(G(y)H(x,y)))是前束范式而x(F(x)G(x))

x(F(x)y(G(y)H(x,y)))不是前束范式，在命题逻辑中，我们介绍过析取范式和合取范式，利用它们可将命题公式表示为统一的形式，为我们讨论问题提供了方便。下面我们介绍一阶逻辑中的范式概念——前束范式。27前束范式存在定理定理5.1（前束范式存在定理）

一阶逻辑中的任何公式都存在与之等值的前束范式例4求下列公式的前束范式(1)x(M(x)F(x))解x(M(x)F(x))

x(M(x)F(x))（量词否定等值式）

x(M(x)F(x))后两步结果都是前束范式，说明公式的前束范式不惟一.28求前束范式的实例(2)xF(x)xG(x)解xF(x)xG(x)

xF(x)xG(x)（量词否定等值式）

x(F(x)G(x))（量词分配等值式）或

xF(x)xG(x)

xF(x)xG(x)量词否定等值式

xF(x)yG(y)换名规则

xy(F(x)G(y))辖域收缩扩张规则29求前束范式的实例(3)xF(x)y(G(x,y)H(y))或xF(x)y(G(x,y)H(y))

xF(x)y(G(z,y)H(y))代替规则

xy(F(x)(G(z,y)H(y)))解xF(x)y(G(x,y)H(y))

zF(z)y(G(x,y)H(y))换名规则

zy(F(z)(G(x,y)H(y)))辖域收缩扩张规则30化为前束范式的过程

在一阶逻辑推理中，需要将公式化成前束范式形式，这总是可以办到的。即任何一个一阶公式均可等值演算成前束范式，化归过程如下：

(1)消去除、∧、∨之外的联结词；

(2)将否定符移到量词符后；

(3)换名使各变元不同名；

(4)扩大辖域使所有量词处在最前面。

说明1

化归过程需遵守置换规则和换名规则(也可用代替规则)。说明2过程(1)是为了方便地使用量词辖域扩缩律(5.3)～(5.4)。由此可知，公式的前束范式形式并不唯一。31实例书本例5.6求下面公式的前束泛式（1）xF(x)xG(x)（2）xF(x)xG(x)例5.7求下面公式的前束泛式,填出每一步的依据（1）xF(x)xG(x)

（3）xF(x)xG(x)例5.8求下面公式的前束泛式(1)xF(x,y)yG(x,y)(2)(x1F(x1,x2)x2G(x2))x1H(x1,x2,x3)32实例书本例5.7求下面公式的前束泛式,填出每一步的依据（1）xF(x)xG(x)

（2）xF(x)xG(x)（3）xF(x)xG(x)解:(1)xF(x)xG(x)

yF(y)xG(x)换名规则

y(F(y)xG(x))(5.4式二)

yx(F(y)G(x))(5.4式二)（3）xF(x)xG(x)

yF(y)xG(x)

换名规则

y(F(y)xG(x))

yx(F(y)G(x))33实例书本例5.8求下面公式的前束泛式(1)xF(x,y)yG(x,y)(2)(x1F(x1,x2)x2G(x2))x1H(x1,x2,x3)解：（1）xF(x,y)yG(x,y)tF(t,y)wG(x,w)换名规则tw(F(t,y)G(x,w))((5.3),(5.4))或xF(x,y)yG(x,y)

xF(x,t)yG(w,y)代替规则xy(F(x,t)G(w,y))((5.3),(5.4))34实例书本例5.8求下面公式的前束泛式(1)xF(x,y)yG(x,y)(2)(x1F(x1,x2)x2G(x2))x1H(x1,x2,x3)解：（2）(x1F(x1,x2)x2G(x2))x1H(x1,x2,x3)

(x4F(x4,x2)x5G(x5))x1H(x1,x2,x3)

换名规则x4x5(F(x4,x2)G(x5))x1H(x1,x2,x3)((5.3),(5.4))

x4x5x1(F(x4,x2)G(x5)H(x1,x2,x3)((5.3),(5.4))

355.3一阶逻辑的推论理论由于谓词演算是在命题演算的基础上，进一步扩大了谓词与量词的功能，因此容易想到，命题演算中有关推理演绎的规则基本上适用于谓词演算，即在命题逻辑中的各项推理规则在一阶逻辑推理中仍然适用，当然也会有不少只适用于谓词演算的概念与规则。在一阶逻辑中，由前提A1,A2,,Ak

出发推出结论B的形式结构仍然是A1A2AkB。如果此式是永真式，则称由前提A1,A2,,Ak

推出结论B的推理正确，记作A1A2Ak

B

或者A1,A2,,Ak

B，否则称推理不正确。365.3一阶逻辑的推论理论推理的形式结构1.A1A2AkB

若此式是永真式,则称推理正确,记作A1A2AkB2.前提:A1,A2,,Ak

结论:B推理定理:永真式的蕴涵式37推理定理第一组命题逻辑推理定理的代换实例

如,xF(x)yG(y)xF(x)xF(x)yG(y)xF(x)xF(x)xF(x)yG(y)第二组基本等值式生成的推理定理

如,xF(x)xF(x),xF(x)xF(x)xF(x)xF(x),xF(x)xF(x)38推理定理第三组其他常用推理定律(1)xA(x)xB(x)x(A(x)B(x))(2)x(A(x)B(x))xA(x)xB(x)(3)x(A(x)B(x))xA(x)xB(x)(4)x(A(x)B(x))xA(x)xB(x)39量词消去引入规则1.全称量词消去规则(-，UI)

或其中(1)x,y是个体变项符号,c是个体常项符号,且在A中x不在y和y的辖域内自由出现.(2)A(y)(或A(c))中约束变元个数与A(x)中约束变元个数相同。2.全称量词引入规则(+，UG)

其中x是个体变项符号,且不在前提的任何公式中自由出现xA(x)A(y)xA(x)A(c)A(x)xA(x)40量词消去引入规则3.存在量词消去规则(-，EI)

其中x是个体变项符号,且不在前提的任何公式和B中自由出现,其中（1）c是特定的个体常项符号,（2）xA(x)是闭式且c不A(x)中出现.A(x)BxA(x)B

xA(x)A(c)41量词消去引入规则4.存在量词引入消去规则(+，EG)

或或其中x,y是个体变项符号,c是个体常项符号,且在A中y和c不在x和x的辖域内自由出现.BA(y)BxA(x)BA(c)BxA(x)A(y)xA(x)A(c)xA(x)42【例A】设前提为∀x∃yF(x,y)，下面推理是否正确？

(1)∀x∃yF(x,y)前提引入

(2)∃yF(y,y)(1)UI

解：

∀x∃yF(x,y)∃yF(y,y)的推理并不正确。如果给定解释I：

个体域为实数集，F(x，y)：x＞y，则∀x∃yF(x,y)意为“对于每个实数x，均存在着比之更小的实数y”，这是一个真命题。而∃yF(y,y)意为“存在着比自己小的实数”，是假命题。之所以出现这样的错误，是违反了UI规则成立的条件(2)。43实例解析例B设个体域为实数集合，F(x,y)为xy,

指出在推理系统F中，以∀x∃yF(x,y)(真命题）为前提，推出∀xF(x,c)（假命题）,或∃y∀xF(x,y)的原因.(1)∀x∃yF(x,y)前提引入(2)∃yF(z,y)UI规则

(3)F(z,c)EI规则

(4)∀xF(x,c)UG规则(5)∃y∀xF(x,y)EG规则解：∀x∃yF(x,y)∃y∀xF(x,y)的推理并不正确。取与例A相同的解释，则由∀x∃yF(x,y)为真，而∃y∀xF(x,y)意为“存在着最小实数”，是假命题，知推理不正确。之所以出现这样的错误，是第(3)步违反了EI规则成立的条件(2)。44自然推理系统NL定义5.3

自然推理系统NL定义如下:1.字母表.同一阶语言L的字母表2.合式公式.同L的合式公式3.推理规则:(1)前提引入规则(2)结论引入规则(3)置换规则(4)假言推理规则(5)附加规则(6)化简规则(7)拒取式规则45自然推理系统NL(8)假言三段论规则(9)析取三段论规则(10)构造性二难推理规则(11)合取引入规则(12)-规则(13)+规则(14)-规则(15)+规则

设前提A1,A2,,Ak,结论B及公式序列C1,C2,,Cl.如果每一个Ci(1il)是某个Aj,或者可由序列中前面的公式应用推理规则得到,并且Cl=B,则称这个公式序列C1,C2,,Cl是由A1,A2,,Ak推出B的证明46重要提示要特别注意使用-、+、-、+规则的条件.反例1.对A=xyF(x,y)使用-规则,推得B=yF(y,y).取解释I:个体域为R,在I下A被解释为xy(x>y),真;而B被解释为y(y>y),假原因:在A中x自由出现在y的辖域F(x,y)内反例2.前提:P(x)Q(x),P(x)结论:xQ(x)取解释I:个体域为Z,在I下前提为真,结论为假,从而推理不正确47反例2(续)“证明”:①P(x)Q(x)前提引入②P(x)前提引入③Q(x)①②假言推理④xQ(x)③+错误原因:在④使用+规则,而x在前提的公式中自由出现.48构造推理证明的实例例5.9在自然推理系统NL中构造下面推理的证明,取个体域R:

任何自然数都是整数.存在自然数.所以,存在整数.解设F(x):x是自然数,G(x):x是整数.前提:x(F(x)G(x)),xF(x)结论:xG(x)证明:①x(F(x)G(x))前提引入②F(x)G(x)①-③F(x)xG(x)②+④xF(x)xG(x)③-⑤xF(x)前提引入⑥xG(x)④⑤假言推理

49构造推理证明的实例例5

.10

在自然推理系统NL中构造下面推理的证明.前提:x(F(x)G(x)),x(F(x)H(x))，结论:xG(x)①x(F(x)G(x))前提引入②F(x)G(x)①-③

F(x)H(x)F(x)化简规则④F(x)H(x)G(x)③

②假言推理

⑤F(x)H(x)H(x)化简规则⑥(F(x)H(x))G(x)④置换⑦(F(x)H(x))H(x)⑤置换⑧((F(x)H(x))G(x))((F(x)H(x))H(x))⑥⑦合取引入⑨(F(x)H(x))(G(x)H(x))⑧置换⑩F(x)H(x)G(x)H(x)⑨置换(11)F(x)H(x)x(G(x)H(x))⑩+(12)x(F(x)H(x))x(G(x)H(x))(11)-

(13)x(F(x)H(x))前提引入

(14)x(G(x)H(x))(12)(13)假言推理

50构造推理证明的实例例5.11

在自然推理系统NL中构造下面推理的证明,取个体域R:

不存在能表示成分数的无理数.有理数都能表示成分数.

所以,有理数都不是无理数.解设F(x):x是无理数,G(x):x是有理数,H(x):x能表示成分数.前提:x(F(x)H(x)),

x(G(x)H(x))结论:x(G(x)F(x))证明:①x(F(x)H(x))前提引入②x(F(x)H(x))①置换③x(F(x)H(x))②置换④F(x)H(x)③-51构造推理证明的实例⑤x(G(x)H(x))

前提引入⑥G(x)H(x)⑤-

⑦H(x)F(x)④置换⑧G(x)F(x)⑥⑦假言三段论⑨x(G(x)F(x))⑧+52附加前提证明法例构造下面推理的证明：

前提：x(F(x)→G(x))

结论：xF(x)→xG(x)

分析本题直接证明很困难，注意到结论部分是蕴含式，应考虑用附加前提证明法。证明

(1)x(F(x)→G(x)) 前提引入

(2)xF(x) 附加前提引入

(3)F(t) (2)UI

(4)F(t)→G(t) (1)UI

(5)G(t) (3)(4)假言推理

(6)xG(x) (5)UG

(7)xF(x)→xG(x) CP

53归缪法例构造下面推理的证明：

前提：x(F(x)→G(x))

结论：x(y(F(y)∧H(x,y))→z(G(z)∧H(x,z)))

分析本题直接证明会感到无从下手，而由于结论并非蕴含式(x的辖域是其后整个公式)，附加前提证明法也不适用，此时我们应考虑归缪法。证明(1)x(y(F(y)∧H(x,y))→z(G(z)∧H(x,z)))

否定结论引入(2)x(y(F(y)∧H(x,y))→z(G(z)∧H(x,z)))(1)置换(3)

(

y(F(y)∧H(a,y))→z(G(z)∧H(a,z)))(2)EI,x改a(4)(

y(F(y)∧H(a,y))z(G(z)∧H(a,z)))

即

y(F(y)∧H(a,y))∧z(G(z)∧H(a,z))

(3)置换→54(4)

y(F(y)∧H(a，y))

∧

z(G(z)∧H(a，z))

(5)y(F(y)∧H(a,y)) (4)化简(6)F(b)∧H(a,b) (5)EI(7)F(b) (6)化简(8)x(F(x)→G(x)) 前提引入(9)F(b)→G(b) (8)UI(10)G(b) (7)(9)假言推理(11)

z(G(z)∧H(a,z)) (4)化简(12)z(G(z)∨H(a,

z)) (11)置换(13)G(b)∨H(a,b) (12)UI(14)H(a,b) (6)化简(15)

H(a,b) (14)置换(16)G(b) (13)(15)析取三段论(17)G(b)∧G(b) (10)(16)合取引入55补充总结要正确使用UI，UG，EG，EI4条推理规则，使用时要注意以下几点：（1）一定要对前束范式才能使用UI，UG，EG，EI规则，对不是前束范式的公式要使用它们，一定先求出公式的前束范式。（2）记住UI，UG，EG，EI各自使用的条件。（3）在同一推理的证明中，如果既要使用UI规则，又在使用EI规则，一定要先使用EI规则，后使用UI规则，而且UI规则使用的个体项一定是EI规则中使用过的；（4）对A(c)不能使用UG规则，其中c为特定的个体常项。56第五章习题课主要内容一阶逻辑等值式

基本等值式，置换规则、换名规则、代替规则前束范式推理的形式结构自然推理系统NL

推理定律、推理规则57基本要求深刻理解并牢记一阶逻辑中的重要等值式,并能准确而熟练地应用它们．熟练正确地使用置换规则、换名规则、代替规则．熟练地求出给定公式的前束范式．深刻理解自然推理系统NL

的定义，牢记NL

中的各条推理规则，特别是注意使用、+、+、

4条推理规则的条件．能正确地给出有效推理的证明．58练习11.给定解释I如下:(1)个体域D={2,3}(2)(3)(4)求下述在I下的解释及其真值:

xy(F(f(x))G(y,f(a)))解xF(f(x))yG(y,f(a))F(f(2))F(f(3))(G(2,f(2))G(3,f(2)))10(10)059练习22.求下述公式的前束范式:

xF(x)y(G(x,y)H(x,y))解使用换名规则,xF(x)y(G(x,y)H(x,y))

zF(z)y(G(x,y)H(x,y))

z(F(z)y(G(x,y)H(x,y))

zy(F(z)(G(x,y)H(x,y)))使用代替规则xF(x)y(G(x,y)H(x,y))

xF(x)y(G(z,y)H(z,y))

x(F(x)y(G(z,y)H(z,y))

xy(F(x)(G(z,y)H(z,y)))60练习33.构造下面推理的证明:(1)前提：x(F(x)G(x)),xF(x)结论：xG(x)证明：①x(F(x)G(x))前提引入②F(y)G(y)①③xF(x)前提引入④F(y)③⑤G(y)②④假言推理⑥