第5章 一階邏輯等值演算與推理

1主要內(nèi)容一階邏輯等值式與基本的等值式置換規(guī)則、換名規(guī)則、代替規(guī)則前束范式自然推理系統(tǒng)NL及其推理規(guī)則第五章一階邏輯等值演算與推理25.1一階邏輯等值式與置換規(guī)則在一階邏輯中，有些命題可以有不同的形式例如命題：沒(méi)有不犯錯(cuò)誤的人。

設(shè)F(x):x是人，G(x):x犯錯(cuò)誤(1)x(F(x)G(x))或(2)x(F(x)G(x))定義5.1

設(shè)A,B是兩個(gè)謂詞公式,如果AB是永真式,則稱A與B等值,記作AB,并稱AB是等值式顯然，AB當(dāng)且僅當(dāng)在任何解釋I和I中的任意賦值υ下，A與B有相同的真值。即在I和υ下,A為真當(dāng)且僅當(dāng)B為真，或者，A為假當(dāng)且僅當(dāng)B為假。同時(shí)，要證明兩個(gè)公式不等值，只需找到一個(gè)解釋I和I中的一個(gè)賦值υ，使得兩個(gè)公式在I和υ下，一個(gè)為真，另一個(gè)為假。35.1一階邏輯等值式與置換規(guī)則由定義5.1

可知，判斷公式A與B是否等值，等價(jià)于判斷公式AB是否為永真式,同命題邏輯中一樣，證明了一些常用的重要等值式，并用這些等值式推演出更多的等值式基本等值式第一組命題邏輯中16組基本等值式的代換實(shí)例

例如，AA(2.1)

xF(x)xF(x),

AB

AB

(2.12)xF(x)yG(y)

xF(x)yG(y)等第二組(1)消去量詞等值式

設(shè)個(gè)體為有限集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)表示“在個(gè)體域D中，并非所有的x都具有性質(zhì)A”，

而xA(x)

表示“在個(gè)體域D中，至少有一個(gè)x不具有性質(zhì)A”，

兩個(gè)命題的含義是一樣的，因此它們同真或同假，它們是等值的。(2)在個(gè)體域D中，”不存在有性質(zhì)A的x”與“所有的x都沒(méi)有性質(zhì)A”是同一回事。5基本等值式(3)量詞轄域收縮與擴(kuò)張等值式.

設(shè)A(x)是含x自由出現(xiàn)的公式，B中不含x的自由出現(xiàn)。則：

關(guān)于全稱量詞的：①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（∨表示取大）當(dāng)且僅當(dāng)xA(x)=0且B=0（只能每項(xiàng)都取0）

當(dāng)且僅當(dāng)B=0且對(duì)于DI中的每一個(gè)元素c，有A(c)=0當(dāng)且僅當(dāng)對(duì)于DI中的每一個(gè)元素c，有A(c)∨B=0當(dāng)且僅當(dāng)x(A(x)∨B)=0

(2)x(A(x)B)

xA(x)B

在任何解釋I和I中的任意賦值υ下，

xA(x)∧B=1（∧表示取?。?/p>

當(dāng)且僅當(dāng)xA(x)=1且B=1（只能每項(xiàng)都取1）當(dāng)且僅當(dāng)B=1且對(duì)于DI中的每一個(gè)元素c，A(c)=1當(dāng)且僅當(dāng)對(duì)于DI中的每一個(gè)元素c，A(c)∧B=1當(dāng)且僅當(dāng)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基本等值式

關(guān)于存在量詞的：①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（∨表示取大）當(dāng)且僅當(dāng)xA(x)=0且B=0（只能每項(xiàng)都取0）

當(dāng)且僅當(dāng)B=0且存在DI中的元素c，使得A(c)=0當(dāng)且僅當(dāng)存在DI中的元素c，使得A(c)∨B=0當(dāng)且僅當(dāng)x(A(x)B)=0

(2)

x(A(x)B)

xA(x)B

在任何解釋I和I中的任意賦值υ下，

xA(x)B=1（∧表示取?。?/p>

當(dāng)且僅當(dāng)xA(x)=1且B=1（只能每項(xiàng)都取1）當(dāng)且僅當(dāng)B=1且存在DI中的元素c，A(c)=1當(dāng)且僅當(dāng)存在DI中的元素c，A(c)∧B=1當(dāng)且僅當(dāng)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當(dāng)且僅當(dāng)對(duì)于DI中的每一個(gè)元素c，A(c)∧B(c)=1當(dāng)且僅當(dāng)對(duì)于DI中的每一個(gè)元素c，A(c)=1且B(c)=1當(dāng)且僅當(dāng)xA(x)=1且xB(x)=1當(dāng)且僅當(dāng)xA(x)∧xB(x)=1注意：對(duì)，對(duì)無(wú)分配律，見(jiàn)例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為自然數(shù)集，A(x)為x是奇數(shù)，B(x)為x是偶數(shù)。在DI下，x(A(x)∨B(x))意為“所有的自然數(shù)，或是奇數(shù)，或是偶數(shù)”，是真命題，而xA(x)∨xB(x)意為“所有的自然數(shù)是奇數(shù)，或者所有的自然數(shù)是偶數(shù)”，是假命題。

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

(2)x(A(x)∧B(x))意為“存在著自然數(shù)x，x既是奇數(shù)又是偶數(shù)”，顯然這是一個(gè)假命題，

而xA(x)∧xB(x)意為“有自然數(shù)是奇數(shù)并且也有自然數(shù)是偶數(shù)”，是真命題，

因此，xA(x)∧xB(x)與x(A(x)∧B(x))不等值。12置換規(guī)則、換名規(guī)則、代替規(guī)則1.置換規(guī)則設(shè)(A)是含A的公式,那么,若AB,則(A)(B).2.換名規(guī)則

設(shè)A為一公式，將A中某量詞轄域中個(gè)體變項(xiàng)的所有約束出現(xiàn)及相應(yīng)的指導(dǎo)變?cè)獡Q成該量詞轄域中未曾出現(xiàn)過(guò)的個(gè)體變項(xiàng)符號(hào)，其余部分不變，設(shè)所得公式為A，則AA.3.代替規(guī)則

設(shè)A為一公式，將A中某個(gè)個(gè)體變項(xiàng)的所有自由出現(xiàn)用A中

未曾出現(xiàn)過(guò)的個(gè)體變項(xiàng)符號(hào)代替，其余部分不變，設(shè)所得

公式為A，則AA.13實(shí)例例5.1

將公式化成等值的不含既有約束出現(xiàn)、又有自由出現(xiàn)的個(gè)體變項(xiàng):(1)xF(x,y,z)yG(x,y,z)解:公式中x,y都是既有約束出現(xiàn)、又有自由出現(xiàn)的個(gè)體變項(xiàng)xF(x,y,z)yG(x,y,z)tF(t,y,z)yG(x,y,z)

換名規(guī)則tF(t,y,z)wG(x,w,z)

換名規(guī)則或者xF(x,y,z)yG(x,y,z)xF(x,t,z)yG(x,y,z)

代替規(guī)則xF(x,t,z)yG(w,y,z)

代替規(guī)則14實(shí)例例5.1

將公式化成等值的不含既有約束出現(xiàn)、又有自由出現(xiàn)的個(gè)體變項(xiàng):(2)x(F(x,y)yG(x,y,z))解公式中y都是既有約束出現(xiàn)yG(x,y,z)、又有自由出現(xiàn)F(x,y)的個(gè)體變項(xiàng)，需要處理。x只有約束出現(xiàn)，z只有自由出現(xiàn)，保持不變。x(F(x,y)yG(x,y,z))x(F(x,t)yG(x,y,z))

代替規(guī)則

或者x(F(x,y)yG(x,y,z))x(F(x,y)tG(x,t,z))

換名規(guī)則

15實(shí)例例5.1

將公式化成等值的不含既有約束出現(xiàn)、又有自由出現(xiàn)的個(gè)體變項(xiàng):(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))

換名規(guī)則xt(F(x,y,z)G(x,t,z))

轄域擴(kuò)張等值式或者x(F(x,y,z)yG(x,y,z))x(F(x,u,z)yG(x,y,z))

代替規(guī)則xy(F(x,u,z)G(x,y,z))

轄域擴(kuò)張等值式16實(shí)例例3

設(shè)個(gè)體域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實(shí)例解法二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實(shí)例(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實(shí)例例5.4給定解釋I如下（1）個(gè)體域D={2、3}（2）D中特定元素a=2（3）D中特定函數(shù)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實(shí)例(類似例5.4)設(shè)解釋I為：DI={2，3}，f(2)=3，f(3)=2，

F(2，2)=F(2，3)=0，F(xiàn)(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)設(shè)解釋I為：DI={2，3}，f(2)=3，f(3)=2，

F(2，2)=F(2，3)=0，F(xiàn)(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)設(shè)解釋I為：DI={2，3}，f(2)=3，f(3)=2，

F(2，2)=F(2，3)=0，F(xiàn)(3，2)=F(3，3)=1。23實(shí)例例1(例5.5)將下面命題用兩種形式符號(hào)化,并證明兩者等值:(1)沒(méi)有不犯錯(cuò)誤的人解令F(x)：x是人，G(x)：x犯錯(cuò)誤.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實(shí)例(2)不是所有的人都愛(ài)看電影解令F(x)：x是人，G(x)：愛(ài)看電影.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實(shí)例例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

設(shè)A為一個(gè)一階邏輯公式，若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)))不是前束范式，在命題邏輯中，我們介紹過(guò)析取范式和合取范式，利用它們可將命題公式表示為統(tǒng)一的形式，為我們討論問(wèn)題提供了方便。下面我們介紹一階邏輯中的范式概念——前束范式。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))后兩步結(jié)果都是前束范式，說(shuō)明公式的前束范式不惟一.28求前束范式的實(shí)例(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)換名規(guī)則

xy(F(x)G(y))轄域收縮擴(kuò)張規(guī)則29求前束范式的實(shí)例(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))代替規(guī)則

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

zF(z)y(G(x,y)H(y))換名規(guī)則

zy(F(z)(G(x,y)H(y)))轄域收縮擴(kuò)張規(guī)則30化為前束范式的過(guò)程

在一階邏輯推理中，需要將公式化成前束范式形式，這總是可以辦到的。即任何一個(gè)一階公式均可等值演算成前束范式，化歸過(guò)程如下：

(1)消去除、∧、∨之外的聯(lián)結(jié)詞；

(2)將否定符移到量詞符后；

(3)換名使各變?cè)煌?/p>

(4)擴(kuò)大轄域使所有量詞處在最前面。

說(shuō)明1

化歸過(guò)程需遵守置換規(guī)則和換名規(guī)則(也可用代替規(guī)則)。說(shuō)明2過(guò)程(1)是為了方便地使用量詞轄域擴(kuò)縮律(5.3)～(5.4)。由此可知，公式的前束范式形式并不唯一。31實(shí)例書(shū)本例5.6求下面公式的前束泛式（1）xF(x)xG(x)（2）xF(x)xG(x)例5.7求下面公式的前束泛式,填出每一步的依據(jù)（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實(shí)例書(shū)本例5.7求下面公式的前束泛式,填出每一步的依據(jù)（1）xF(x)xG(x)

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

yF(y)xG(x)換名規(guī)則

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

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

yF(y)xG(x)

換名規(guī)則

y(F(y)xG(x))

yx(F(y)G(x))33實(shí)例書(shū)本例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)換名規(guī)則tw(F(t,y)G(x,w))((5.3),(5.4))或xF(x,y)yG(x,y)

xF(x,t)yG(w,y)代替規(guī)則xy(F(x,t)G(w,y))((5.3),(5.4))34實(shí)例書(shū)本例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)

換名規(guī)則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一階邏輯的推論理論由于謂詞演算是在命題演算的基礎(chǔ)上，進(jìn)一步擴(kuò)大了謂詞與量詞的功能，因此容易想到，命題演算中有關(guān)推理演繹的規(guī)則基本上適用于謂詞演算，即在命題邏輯中的各項(xiàng)推理規(guī)則在一階邏輯推理中仍然適用，當(dāng)然也會(huì)有不少只適用于謂詞演算的概念與規(guī)則。在一階邏輯中，由前提A1,A2,,Ak

出發(fā)推出結(jié)論B的形式結(jié)構(gòu)仍然是A1A2AkB。如果此式是永真式，則稱由前提A1,A2,,Ak

推出結(jié)論B的推理正確，記作A1A2Ak

B

或者A1,A2,,Ak

B，否則稱推理不正確。365.3一階邏輯的推論理論推理的形式結(jié)構(gòu)1.A1A2AkB

若此式是永真式,則稱推理正確,記作A1A2AkB2.前提:A1,A2,,Ak

結(jié)論:B推理定理:永真式的蘊(yùn)涵式37推理定理第一組命題邏輯推理定理的代換實(shí)例

如,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量詞消去引入規(guī)則1.全稱量詞消去規(guī)則(-，UI)

或其中(1)x,y是個(gè)體變項(xiàng)符號(hào),c是個(gè)體常項(xiàng)符號(hào),且在A中x不在y和y的轄域內(nèi)自由出現(xiàn).(2)A(y)(或A(c))中約束變?cè)獋€(gè)數(shù)與A(x)中約束變?cè)獋€(gè)數(shù)相同。2.全稱量詞引入規(guī)則(+，UG)

其中x是個(gè)體變項(xiàng)符號(hào),且不在前提的任何公式中自由出現(xiàn)xA(x)A(y)xA(x)A(c)A(x)xA(x)40量詞消去引入規(guī)則3.存在量詞消去規(guī)則(-，EI)

其中x是個(gè)體變項(xiàng)符號(hào),且不在前提的任何公式和B中自由出現(xiàn),其中（1）c是特定的個(gè)體常項(xiàng)符號(hào),（2）xA(x)是閉式且c不A(x)中出現(xiàn).A(x)BxA(x)B

xA(x)A(c)41量詞消去引入規(guī)則4.存在量詞引入消去規(guī)則(+，EG)

或或其中x,y是個(gè)體變項(xiàng)符號(hào),c是個(gè)體常項(xiàng)符號(hào),且在A中y和c不在x和x的轄域內(nèi)自由出現(xiàn).BA(y)BxA(x)BA(c)BxA(x)A(y)xA(x)A(c)xA(x)42【例A】設(shè)前提為?x?yF(x,y)，下面推理是否正確？

(1)?x?yF(x,y)前提引入

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

解：

?x?yF(x,y)?yF(y,y)的推理并不正確。如果給定解釋I：

個(gè)體域?yàn)閷?shí)數(shù)集，F(xiàn)(x，y)：x＞y，則?x?yF(x,y)意為“對(duì)于每個(gè)實(shí)數(shù)x，均存在著比之更小的實(shí)數(shù)y”，這是一個(gè)真命題。而?yF(y,y)意為“存在著比自己小的實(shí)數(shù)”，是假命題。之所以出現(xiàn)這樣的錯(cuò)誤，是違反了UI規(guī)則成立的條件(2)。43實(shí)例解析例B設(shè)個(gè)體域?yàn)閷?shí)數(shù)集合，F(xiàn)(x,y)為xy,

指出在推理系統(tǒng)F中，以?x?yF(x,y)(真命題）為前提，推出?xF(x,c)（假命題）,或?y?xF(x,y)的原因.(1)?x?yF(x,y)前提引入(2)?yF(z,y)UI規(guī)則

(3)F(z,c)EI規(guī)則

(4)?xF(x,c)UG規(guī)則(5)?y?xF(x,y)EG規(guī)則解：?x?yF(x,y)?y?xF(x,y)的推理并不正確。取與例A相同的解釋，則由?x?yF(x,y)為真，而?y?xF(x,y)意為“存在著最小實(shí)數(shù)”，是假命題，知推理不正確。之所以出現(xiàn)這樣的錯(cuò)誤，是第(3)步違反了EI規(guī)則成立的條件(2)。44自然推理系統(tǒng)NL定義5.3

自然推理系統(tǒng)NL定義如下:1.字母表.同一階語(yǔ)言L的字母表2.合式公式.同L的合式公式3.推理規(guī)則:(1)前提引入規(guī)則(2)結(jié)論引入規(guī)則(3)置換規(guī)則(4)假言推理規(guī)則(5)附加規(guī)則(6)化簡(jiǎn)規(guī)則(7)拒取式規(guī)則45自然推理系統(tǒng)NL(8)假言三段論規(guī)則(9)析取三段論規(guī)則(10)構(gòu)造性二難推理規(guī)則(11)合取引入規(guī)則(12)-規(guī)則(13)+規(guī)則(14)-規(guī)則(15)+規(guī)則

設(shè)前提A1,A2,,Ak,結(jié)論B及公式序列C1,C2,,Cl.如果每一個(gè)Ci(1il)是某個(gè)Aj,或者可由序列中前面的公式應(yīng)用推理規(guī)則得到,并且Cl=B,則稱這個(gè)公式序列C1,C2,,Cl是由A1,A2,,Ak推出B的證明46重要提示要特別注意使用-、+、-、+規(guī)則的條件.反例1.對(duì)A=xyF(x,y)使用-規(guī)則,推得B=yF(y,y).取解釋I:個(gè)體域?yàn)镽,在I下A被解釋為xy(x>y),真;而B(niǎo)被解釋為y(y>y),假原因:在A中x自由出現(xiàn)在y的轄域F(x,y)內(nèi)反例2.前提:P(x)Q(x),P(x)結(jié)論:xQ(x)取解釋I:個(gè)體域?yàn)閆,在I下前提為真,結(jié)論為假,從而推理不正確47反例2(續(xù))“證明”:①P(x)Q(x)前提引入②P(x)前提引入③Q(x)①②假言推理④xQ(x)③+錯(cuò)誤原因:在④使用+規(guī)則,而x在前提的公式中自由出現(xiàn).48構(gòu)造推理證明的實(shí)例例5.9在自然推理系統(tǒng)NL中構(gòu)造下面推理的證明,取個(gè)體域R:

任何自然數(shù)都是整數(shù).存在自然數(shù).所以,存在整數(shù).解設(shè)F(x):x是自然數(shù),G(x):x是整數(shù).前提:x(F(x)G(x)),xF(x)結(jié)論:xG(x)證明:①x(F(x)G(x))前提引入②F(x)G(x)①-③F(x)xG(x)②+④xF(x)xG(x)③-⑤xF(x)前提引入⑥xG(x)④⑤假言推理

49構(gòu)造推理證明的實(shí)例例5

.10

在自然推理系統(tǒng)NL中構(gòu)造下面推理的證明.前提:x(F(x)G(x)),x(F(x)H(x))，結(jié)論:xG(x)①x(F(x)G(x))前提引入②F(x)G(x)①-③

F(x)H(x)F(x)化簡(jiǎn)規(guī)則④F(x)H(x)G(x)③

②假言推理

⑤F(x)H(x)H(x)化簡(jiǎn)規(guī)則⑥(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構(gòu)造推理證明的實(shí)例例5.11

在自然推理系統(tǒng)NL中構(gòu)造下面推理的證明,取個(gè)體域R:

不存在能表示成分?jǐn)?shù)的無(wú)理數(shù).有理數(shù)都能表示成分?jǐn)?shù).

所以,有理數(shù)都不是無(wú)理數(shù).解設(shè)F(x):x是無(wú)理數(shù),G(x):x是有理數(shù),H(x):x能表示成分?jǐn)?shù).前提:x(F(x)H(x)),

x(G(x)H(x))結(jié)論: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構(gòu)造推理證明的實(shí)例⑤x(G(x)H(x))

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

⑦H(x)F(x)④置換⑧G(x)F(x)⑥⑦假言三段論⑨x(G(x)F(x))⑧+52附加前提證明法例構(gòu)造下面推理的證明：

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

結(jié)論：xF(x)→xG(x)

分析本題直接證明很困難，注意到結(jié)論部分是蘊(yùn)含式，應(yīng)考慮用附加前提證明法。證明

(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歸繆法例構(gòu)造下面推理的證明：

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

結(jié)論：x(y(F(y)∧H(x,y))→z(G(z)∧H(x,z)))

分析本題直接證明會(huì)感到無(wú)從下手，而由于結(jié)論并非蘊(yùn)含式(x的轄域是其后整個(gè)公式)，附加前提證明法也不適用，此時(shí)我們應(yīng)考慮歸繆法。證明(1)x(y(F(y)∧H(x,y))→z(G(z)∧H(x,z)))

否定結(jié)論引入(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)化簡(jiǎn)(6)F(b)∧H(a,b) (5)EI(7)F(b) (6)化簡(jiǎn)(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)化簡(jiǎn)(12)z(G(z)∨H(a,

z)) (11)置換(13)G(b)∨H(a,b) (12)UI(14)H(a,b) (6)化簡(jiǎn)(15)

H(a,b) (14)置換(16)G(b) (13)(15)析取三段論(17)G(b)∧G(b) (10)(16)合取引入55補(bǔ)充總結(jié)要正確使用UI，UG，EG，EI4條推理規(guī)則，使用時(shí)要注意以下幾點(diǎn)：（1）一定要對(duì)前束范式才能使用UI，UG，EG，EI規(guī)則，對(duì)不是前束范式的公式要使用它們，一定先求出公式的前束范式。（2）記住UI，UG，EG，EI各自使用的條件。（3）在同一推理的證明中，如果既要使用UI規(guī)則，又在使用EI規(guī)則，一定要先使用EI規(guī)則，后使用UI規(guī)則，而且UI規(guī)則使用的個(gè)體項(xiàng)一定是EI規(guī)則中使用過(guò)的；（4）對(duì)A(c)不能使用UG規(guī)則，其中c為特定的個(gè)體常項(xiàng)。56第五章習(xí)題課主要內(nèi)容一階邏輯等值式

基本等值式，置換規(guī)則、換名規(guī)則、代替規(guī)則前束范式推理的形式結(jié)構(gòu)自然推理系統(tǒng)NL

推理定律、推理規(guī)則57基本要求深刻理解并牢記一階邏輯中的重要等值式,并能準(zhǔn)確而熟練地應(yīng)用它們．熟練正確地使用置換規(guī)則、換名規(guī)則、代替規(guī)則．熟練地求出給定公式的前束范式．深刻理解自然推理系統(tǒng)NL

的定義，牢記NL

中的各條推理規(guī)則，特別是注意使用、+、+、

4條推理規(guī)則的條件．能正確地給出有效推理的證明．58練習(xí)11.給定解釋I如下:(1)個(gè)體域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練習(xí)22.求下述公式的前束范式:

xF(x)y(G(x,y)H(x,y))解使用換名規(guī)則,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)))使用代替規(guī)則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練習(xí)33.構(gòu)造下面推理的證明:(1)前提：x(F(x)G(x)),xF(x)結(jié)論：xG(x)證明：①x(F(x)G(x))前提引入②F(y)G(y)①③xF(x)前提引入④F(y)③⑤G(y)②④假言推理⑥