第5章謂詞邏輯的等值和推理演算

1、第5章 謂詞邏輯的等值和推理演算l謂詞邏輯研究的對象是重要的邏輯規(guī)律，謂詞邏輯研究的對象是重要的邏輯規(guī)律，普遍有效式是最重要的邏輯規(guī)律，普遍有效式是最重要的邏輯規(guī)律，而等值而等值式、推理式都是普遍有效的謂詞公式，式、推理式都是普遍有效的謂詞公式，因因此等值和推理演算就成了謂詞邏輯的基本此等值和推理演算就成了謂詞邏輯的基本內(nèi)容內(nèi)容l這章的討論，主要是以這章的討論，主要是以語義的觀點語義的觀點進(jìn)行的進(jìn)行的非形式的描述，而嚴(yán)格的形式化的討論見非形式的描述，而嚴(yán)格的形式化的討論見第第6章所建立的公理系統(tǒng)章所建立的公理系統(tǒng)51 否定型等值式l等值：等值：若給定了兩個謂詞公式A，B，說A和B是等值的，如果

2、在公式A，B的任一解釋(注意在謂詞邏輯中，解釋的范圍還包含注意在謂詞邏輯中，解釋的范圍還包含論域以外的其他要素，見論域以外的其他要素，見P65)下，A和B都有相同的真值l其他說法：其他說法：A，B等值當(dāng)且僅當(dāng)AB是普遍有效的公式(注意這里不再說重言式了)記作AB或AB。511 由命題公式移植來的等值式l 若將命題公式的等值式，直接以謂詞公式代入命題若將命題公式的等值式，直接以謂詞公式代入命題變項便可得謂詞等值式由變項便可得謂詞等值式由pp,pq=pq, (pq)r=(pr)(qr)可得可得(以下每兩個為一對：無量詞、有量詞以下每兩個為一對：無量詞、有量詞)P(x)P(x)(x)P(x)(x)P

3、(x)P(x)Q(x)P(x)Q(x)(x)P(x)(x)Q(x) (x)P(x)(x)Q(x)(P(x)Q(x)R(x)=(P(x)R(x)(Q(x)R(x)(x)P(x)Q(y)(z)R(z)=(x)P(x)(z)R(z)(Q(y)(z)R(z)512 否定型等值式（摩根律的推廣） (x)P(x)=(x)P(x)(x)P(x)=(x)P(x)l 形式上看這對公式，是說否定詞”可越過量詞深入到量詞的轄域內(nèi)，但要把所越過的量詞轉(zhuǎn)換為，轉(zhuǎn)換為. (1)(1)從語義上說明從語義上說明(2)(2)例：在例：在ll，22域上分析域上分析(x)P(x)=(P(1)P(2)=P(1)vP(2) =(x)

4、P(x)(x)P(x)=(P(1)vP(2)=P(1) P(2) =(x)P(x)(3)(3)語義上的證明語義上的證明l 證明方法：依等值式定義，A=B如果在任一解釋I下A真B就真，而且B真A就真若證明(x)P(x)=(x)P(x)1. 設(shè)某一解釋I下若(x)P(x)=T從而(x)P(x)=F，即有一個xoD,使P(Xo)=F于是P(xo)=T 故在I下(x)P(x)=T2. 反過來，設(shè)某一解釋I下若 (x) P(x)=T即有一個xoD,使P(Xo)=T 從而P(Xo)=F 于是(x) P(x)=F即 (x)P(x)=T(4)(4)舉例舉例例1 “并非所有的動物都是貓”的表示設(shè) A(x)：x是

5、動物B(x)：x是描原語句可表示成(x)(A(x)B(x)依否定型公式得例2 “天下烏鴉般黑”的表示設(shè) F(x)：x是烏鴉G(x，y)：x與y是一般黑原語句可表示成(x)(y)(F(x)F(y) G(x,y)不難知道與之等值的公式是(x)(y)(F(x)F(y)G(x,y)即不存在x,y是烏鴉但不一般黑這兩句話含義是相同的經(jīng)計算有 5 52 2 量詞分配等值式量詞分配等值式一、含單獨的命題變項，與x無關(guān)521 量詞對、的分配律l 這是一組量詞對這是一組量詞對 、 的分配律，其中的分配律，其中q q是命題變項，是命題變項，與個體變元與個體變元x x無關(guān)，這是很重要的條件無關(guān)，這是很重要的條件l

6、我們僅對第一個等式給出證明，其余三個同樣可我們僅對第一個等式給出證明，其余三個同樣可證證l設(shè)在一解釋I下，(x)(P(x)q)=T，從而對任一x D ，有P(x)q=T 若qT，則(x)P(x)q=T若qF，從而對任一x D ，有P(x) =T ，即有(x)P(x)=T，故仍有，(x)P(x)q=Tl反過來，設(shè)在一解釋I下，(x)P(x)q=T，若q=T，則(x)(P(x)q)=T若q=F，必有(x)P(x)=T，從而對任一xD有P(x)=T，于是對任一x D有P(x)q=T故(x)(P(x)q)=T5 52 22 2 量詞對量詞對的分配律的分配律l 這是一組量詞對的分配律，其中p，q是命題變

7、項，與個體變元x無關(guān)，這是很重要的條件l 5.2節(jié)介紹的等值公式中僅有這里的第一、二個公節(jié)介紹的等值公式中僅有這里的第一、二個公式有量詞的改變！式有量詞的改變！l 先證明其中的第一個等式先證明其中的第一個等式 依依5 52 21 1的等值式的等值式 依依5 5l l2 2的等值式的等值式l 再證明其中的第三個等式再證明其中的第三個等式 依依5 52 2l l的等值式的等值式l 其余兩個等值式同樣可證其余兩個等值式同樣可證二、轄域中無單獨的命題變項二、轄域中無單獨的命題變項5 52 23 3 量詞量詞 對對 、量詞、量詞 對對V V的分配律的分配律l 這是當(dāng)這是當(dāng)P(x)P(x)，Q(x)Q(x

8、)都含有個體變元都含有個體變元x x時，量詞時，量詞 對對 ，量詞，量詞 對對V V所遵從的分配律然而所遵從的分配律然而 對對V V， 對對 的分配律一般并不成立證明中使用了的分配律一般并不成立證明中使用了5.2.15.2.1中的解釋方法。中的解釋方法。(x)P(x)v(x)Q(x)=(x)(P(x)vQ(x)(x)(P(x)Q(x)=(x)P(x)(x)Q(x)一些例子一些例子5 52 24 4 變元易名后的分配律變元易名后的分配律( (在求前束范式時有很大作用在求前束范式時有很大作用) )l 這兩個等值式，說明了通過變元的易名，仍可實現(xiàn)這兩個等值式，說明了通過變元的易名，仍可實現(xiàn) 對對V

9、V， 對對 的分配律的分配律l 證明是容易的首先有變元易名等值式證明是容易的首先有變元易名等值式( ( x)P(x)= (x)P(x)= ( y y)P(y)P(y)( ( x)P(x)= (x)P(x)= ( y y)P(y)P(y)于是于是( ( x)P(x)v(x)P(x)v( x)Q(x)=x)Q(x)=( ( x)P(x)v(x)P(x)v( y)Q(y)y)Q(y)對對x x而言而言( ( y)Q(y)y)Q(y)相當(dāng)于命題變項，與相當(dāng)于命題變項，與x x無關(guān)，可推得無關(guān)，可推得(x)P(x)v(y)Q(y)=(x)(P(x)v(y)Q(y)對對y y而言，而言，P(x)P(x)相

10、當(dāng)于命題變項與相當(dāng)于命題變項與y y無關(guān)，又可推得無關(guān)，又可推得(x)(P(x)v(y)Q(y)=(x)(y)(P(x)vQ(y)同理(x)(y)(P(x)Q(y)=(x)P(x)(x)Q(x)然而(x)(y)(P(x)vQ(y)與(x)(P(x)vQ(x)是不等值的(x)(y)(P(x)Q(y)與(x)(P(x)Q(x)也是不等值的5 53 3 范范 式式l在命題邏輯里每一公式都有與之等值的范在命題邏輯里每一公式都有與之等值的范式，范式是一種統(tǒng)一的表達(dá)形式式，范式是一種統(tǒng)一的表達(dá)形式 對謂詞邏輯的公式來說也有范式，其中對謂詞邏輯的公式來說也有范式，其中前束前束范式與原公式是等值的范式與原公式

11、是等值的，而其他范式與原公，而其他范式與原公式只有較弱的關(guān)系。式只有較弱的關(guān)系。5 53 31 1 前束范式前束范式l 定義定義5 53 31 1 說公式A是一個前束范式，如果A中的一切量詞都位于該公式的最左邊(不含否定詞)且這些量詞的轄域都延伸到公式的末端，前束范式A的一般形式為 (Q1x1)(Qnxn)M(xl，xn)其中其中Q Qi i為量詞為量詞 或或 (il，n)，M稱作公式A的母式母式( (基基式式) )，M中不再有量詞不再有量詞定理定理5 53 31 1 謂詞邏輯的任一公式都可化為與之謂詞邏輯的任一公式都可化為與之等值的等值的前束范式但其前束范式前束范式但其前束范式并不唯一并不唯

12、一l 經(jīng)過這幾步，便可求得任一公式的前束范式由于每一步變換都保持著等值性，所以，所得到的前束形與原公式是等值的l 這里的S(a，b，x，y，z)便是原公式的母式其中a,b為自由個體變項。l 由于前束中量詞的次序排列，以及對母式都沒有明確的限制，自然前束范式不是唯一的，如例1的前束范式也可以是 (x)(z)(y)(S(a,b,x,y,z)P)其中P可以是任一不含量詞的普遍有效的公式。532 Skolem標(biāo)準(zhǔn)形l前束范式對前束量詞沒有次序要求，也沒有其他要求如果對前束范式進(jìn)而要求所有存在量詞都在全稱量詞之左得到存在前束范式(略)，或是只保留全稱量詞而消去存在量詞得到Skolem標(biāo)準(zhǔn)形。不難想像，仍

13、保持與原公式的等值性就不可能了，只能保持在某種意義下的等值關(guān)系(1) (1) 前束范式前束范式( (略略) )l 一個公式的前束范式為 (x1)(xi)(xi+1)(xn )M(x1，xn)即存在量詞都在全稱量詞的左邊，且可保持至少至少有一個存在量詞(i1)，其中M(x1，xn)中不再含有量詞也無自由個體變項 定理定理5.3.25.3.2 謂詞邏輯的任一公式A，都可化成相應(yīng)的前束范式，并且A是普遍有效的當(dāng)且僅當(dāng)其前束范式是普遍有效的。 這定理是說對普遍有效的公式，它與其前束范式是等值的，而一般的公式與其前束范式并不是等值的自然僅當(dāng)自然僅當(dāng)A A是普遍有效的，方使用是普遍有效的，方使用 前束范式

14、前束范式例2 求( x)( y)( u)P(x，y，u)的前束范式(P中無量詞)l將一公式化成前束形，首先要求出前束形，再做前束，這個例子已是前束形了，便可直接求前束形l 首先將全稱量詞( y)改寫成存在量詞( y)，其次是引入謂詞S和一個變元z，得S(x，z)，建立公式( x)(y)(u)(P(x，y，u)S(x，y)V(z)S(x，z)其中S(x，y)的變元，是(y)的變元y和(y)左邊存在量詞( x)的變元x, 附加的(z)S(x，z)中的變元z是新引入的未在原公式中出現(xiàn)過的個體，S也是不曾在M中出現(xiàn)過的謂詞l 進(jìn)而將(z)左移(等值演算)，便得前束范式( x)(y)(u)(z)(P(x

15、，y，u)S(x，y)VS(x，z)當(dāng)原公式中，有多個全稱量詞在存在量詞的左邊，可按這辦法將全稱量詞逐一地右移l 前束范式僅在普遍有效的意義下與原公式等值 前束形對謂詞邏輯完備性的證明是重要的改寫前=改寫后：簡單改寫后=改寫前：反證若A=( x)( y)( u)P(x，y，u)不是普遍有效，則存在解釋I使A為F,于是( x)( y)( u)P(x，y，u)為F. 因此在解釋I下，改寫后B= ( x)(z)S(x，z)可為F,因為S是謂詞變元。(2) (2) SkolemSkolem標(biāo)準(zhǔn)形標(biāo)準(zhǔn)形 另一種Skolem標(biāo)準(zhǔn)形是僅保留全稱量詞的前束形 定理定理5.35.3. .3 3 謂詞邏輯的任一公

16、式A，都可化成相應(yīng)的Skolem標(biāo)準(zhǔn)形(只保留全稱量詞的前束形)，并且A是不可滿足的當(dāng)且僅當(dāng)其Skolem標(biāo)準(zhǔn)形是不可滿足的l 這定理是說對不可滿足的公式，它與其Skolem標(biāo)準(zhǔn)形是等值的，而一般的公式與其Skolem標(biāo)準(zhǔn)形并不是等值的自然僅當(dāng)A是不可滿足的方使用Skolem標(biāo)準(zhǔn)形.例3 求公式(x)(y)(z)(u)(v)(w)P(x,y,z,u,v,w)的Skolem標(biāo)準(zhǔn)形將一公式化成Skolem標(biāo)準(zhǔn)形，首先也要求出前束形這個例子已是前束形了，便可直接求Skolem標(biāo)準(zhǔn)形了首先將最左邊的(x)消去，而將謂詞P中出現(xiàn)的所有變元x均以論域中的某個常項a(a未在P中出現(xiàn)過,且不知道a具體是哪個常

17、量）代入。進(jìn)而消去從左邊數(shù)第二個存在量詞(u)，因(u)的左邊有全稱量詞(y)(z)，需將謂詞P中出現(xiàn)的所有變元u均以y，z的某個二元函數(shù)f(y，z) (f未在P中出現(xiàn)過，且不知道f具體是哪個函數(shù))代入最后按同樣的方法消去存在量詞(w)，因(w)的左邊有全稱量詞(y)(z)和(v)，需將謂詞P中出現(xiàn)的所有變元w均以y，z，v的某個三元函數(shù)g(y，z，v)(g未在P中出現(xiàn)過也不同于f)代入這樣便得消去全部存在量詞的Skolem標(biāo)準(zhǔn)形 (y)(z)(v)P(a,y,z,f(y,z),v,g(y,z,v)54 基本的推理公式l命題邏輯中有關(guān)推理形式、重言蘊(yùn)涵以及基本的推理公式的討論和所用的術(shù)語，都可

18、引入到謂詞邏輯中并可把命題邏輯的推理作為謂詞邏輯推理的一個部分來看待l這里所介紹的是謂詞邏輯所特有的，在命題邏輯里不能討論的推理形式和基本的推理公式。 54 .1 推理形式舉例l例例1 所有的整數(shù)都是有理數(shù)，所有的有理所有的整數(shù)都是有理數(shù)，所有的有理數(shù)都是實數(shù)，所以所有的整數(shù)都是實數(shù)數(shù)都是實數(shù)，所以所有的整數(shù)都是實數(shù)引入謂詞將這三句話形式化，可得如下推引入謂詞將這三句話形式化，可得如下推理形式理形式: (x)(P(x)Q(x)(x)(Q(x)R(x)(x)(P(x)R(x)l例2 所有的人都是要死的，孔子是人，所以孔子是要死的，引入謂詞將這三句話形式化，可得如下推理形式：(x)(A(x)B(x

19、)A(孔子)B(孔子)l例3 有一個又高又胖的人，必有一個高個子而且有個胖子。引入謂詞將這兩句話形式化，可得如下推理形式：(x)(C(x)D(x)(x)C(x)(x)D(x)l例4 若某一個體a具有性質(zhì)E，那么所有的個體x都具有性質(zhì)E這兩句話形式化，可得如下推理形式：E(a)(x)E(x)l不難看出，由例1，2，3所建立的推理形式是正確的，而例4的推理形式是不正確的5.4.2 5.4.2 基本的量詞推理公式基本的量詞推理公式(1)(1) ( ( x)P(x)V(x)P(x)V( x)Q(x)=(x)Q(x)=( x)(P(x)VQ(x)x)(P(x)VQ(x)量詞分配律量詞分配律p73p73(

20、2) (x)(P(x)Q(x)=(x)P(x) (x)Q(x) 注意(1)(1)的逆否的逆否,例3(3) (x)(P(x)Q(x)=(x)P(x)(x)Q(x) 5.2.25.2.2的推廣的推廣(4) (x)(P(x)Q(x)=(x)P(x)(x)Q(x) 5.2.25.2.2的推廣的推廣(5) (x)(P(x)Q(x) )=(x)P(x) (x)Q(x) (3)(3)的推廣的推廣(6) (x)(P(x) Q(x)=(x)P(x) (x)Q(x) (4)(4)的推廣的推廣(7) (x)(P(x)Q(x) (x)(Q(x)R(x)=(x)(P(x)R(x) 例例1 1(8) (x)(P(x)Q(

21、x) P(a)=Q(a) 例例2 2(9)(x)(y)P(x,y)=(x)(y)P(x,y)易理解易理解(10)(x)(y)P(x,y)=(y)(x)P(x,y)易理解，注意右邊易理解，注意右邊x x是是y y的函數(shù)的函數(shù)這些推理公式或稱推理定理的逆一般是不成立的，這些推理公式或稱推理定理的逆一般是不成立的，所以正確地理解這些定理的前提與結(jié)論的不同是重所以正確地理解這些定理的前提與結(jié)論的不同是重要的。要的。5.5 5.5 推理演算推理演算l命題邏輯中引入推理規(guī)則的推理演算，可命題邏輯中引入推理規(guī)則的推理演算，可推廣到謂詞邏輯，有關(guān)的推理規(guī)則都可推廣到謂詞邏輯，有關(guān)的推理規(guī)則都可直直接移入接移入

22、到謂詞邏輯，除此之外還需介紹到謂詞邏輯，除此之外還需介紹4 4條條有關(guān)量詞的消去和引入規(guī)則有關(guān)量詞的消去和引入規(guī)則l( (代入規(guī)則需補(bǔ)充說明：保持合式公式和普代入規(guī)則需補(bǔ)充說明：保持合式公式和普遍有效性不被破壞，見遍有效性不被破壞，見p58)p58)5 55 51 1 推理規(guī)則推理規(guī)則(1)(1)全稱量詞消去規(guī)則全稱量詞消去規(guī)則(x)P(x)=P(y)注：1其中y是論域中任意一個體2需限制y不在P(x)中約束出現(xiàn)(右側(cè)量不在左側(cè)約束出現(xiàn)) 如(x)P(x)(x)(y)(xP(y)因P(y)會有問題(2)全稱量詞引入規(guī)則P(y) =(P(y) =( x)P(x)x)P(x)注：注：1 1任一個體

23、任一個體y(y(自由變項自由變項) )都具有性質(zhì)都具有性質(zhì)P P2 2仍需限制仍需限制x x不在不在P(y)P(y)中約束出現(xiàn)中約束出現(xiàn)(右側(cè)量不在左側(cè)約束出現(xiàn)) 如如P(y)P(y)( ( x)(xy)x)(xy)時，時，P(x)P(x)會會有問題有問題(3)(3)存在量詞消去規(guī)則存在量詞消去規(guī)則(x)P(x)=P(c)注1. c是論域中使P為真的某個個體常項2. 需限制(x)P(x)中沒有自由個體出現(xiàn)3. 還需限制P(x)中不含有c (右側(cè)量不在左側(cè)出現(xiàn)) 如在實數(shù)域上(x)P(x)=(x)(cP(c)的正確性(4)存在量詞引入規(guī)則P(c)=(x)P(x)注：1. c是論域中使P為真的一個

24、特定個體常項2. 需限制x不出現(xiàn)在P(c)中(右側(cè)量不在左側(cè)出現(xiàn)) 如實數(shù)域上，P(c)( x)(xc)時，P(x)會出問題l這4條推理規(guī)則是基本的，對多個量詞下的量詞消去與引入規(guī)則的使用也已談到再明確說明一下(x)(y)P(x，y)=(y)P(x，y)的右端，不允許寫成(y)P(y，y)，(x)P(x，c)=(y)(x)P(x，y)的右端不允許寫成(x)(x)P(x，x)。(x)(y)P(x，y)=(y)P(x，y)=P(x，a)但不允許再推演出(x)P(x，a)和(y)(x)P(x，y)原因是(x)(y)P(x，y)成立時，所找到的y是依賴于x的，從而P(x，y)的成立是有條件的，不是對所

25、有的x對同一個a都有P(x，a)成立，于是不能再推演出(y)(x)P(x,y)552 使用推理規(guī)則的推理演算舉例l 和命題邏輯相比，在謂詞邏輯里使用推理規(guī)則進(jìn)行推理演算同樣是方便的，然而在謂詞邏輯里，真值表法不能使用真值表法不能使用，又不存在判明不存在判明AB是普遍有是普遍有效的一般方法效的一般方法，從而使用推理規(guī)則的推理方法已使用推理規(guī)則的推理方法已是謂詞邏輯的基本推理演算方法是謂詞邏輯的基本推理演算方法l 推理演算過程首先首先是將以自然語句表示的推理問題引入謂詞形式化，若若不能直接使用基本的推理公式便消去量詞，在無量詞下使用規(guī)則和公式推理，最后再引入量詞以求得結(jié)論例1 前提 (x)(P(x

26、)Q(x)，(x)(Q(x)R(x) 結(jié)論 (x)(P(x)R(x)證明 (1)(x)(P(x)Q(x) 前提 (2)P(x)Q(x) 全稱量詞消去全稱量詞消去 (3)(x)(Q(x)R(x) 前提 (4)Q(x)R(x) 全稱量詞消去 (5)P(x)R(x) (2)，(4)三段論 (6)(x)(P(x)R(x) 全稱量詞引入全稱量詞引入例2 所有的人都是要死的，蘇格拉底是人，所以蘇格拉底是要死的首先引入謂詞形式化，令P(x)表x是人，Q(x)表x是要死的，于是問題可描述為 (x)(P(x)Q(x)P(蘇格拉底)Q(蘇格拉底)證明 (1)(x)(P(x)Q(x) 前提 (2)P(蘇格拉底)Q(

27、蘇格拉底) 全稱量詞消去 (3)P(蘇格拉底) 前提 (4)Q(蘇格拉底) (2)(3)分離規(guī)則分離規(guī)則例3 前提(x)P(x)(x)(P(x)VQ(x)R(x)，(x)P(x) 結(jié)論(x)(y)(R(x)R(y)證明 (1)(x)P(x)(x)(P(x)VQ(x)R(x) 前提 (2)(x)P(x) 前提 (3)(x)(P(x)VQ(x)R(x) (1)，(2)分離 (4)P(c) (2)存在量詞消去存在量詞消去 (5)P(c)VQ(c)R(c) (3)全稱量詞消去 (6)P(c)VQ(c) (4) (7)R(c) (5)，(6)分離 (8)(x)R(x) (7)存在量詞引入存在量詞引入 (

28、9)(y)R(y) (7)存在量詞引入 (10)(x)R(x)(y)R(y) (8)，(9) (11)(x)(y)(R(x)R(y) (10)置換例4(不正確) 分析下述推理的正確性 (1)(x)(y)(xy) 前提 (2)(y)(zy) 全稱量詞消去,y y與與z z有關(guān)有關(guān) (3)zb 存在量詞消去,b b依賴依賴z z (4)(z)(zb) 全稱量詞引入,b b不依賴不依賴z z (5)bb 全稱量詞消去 (6)(x)(xx) 全稱量詞引入 推理(1)到(2)，應(yīng)明確指出y是依賴于x的，即(2)中y和z有關(guān)(2)到(3)，其中的b是依賴于z的從而(3)到(4)是不成立的又由于b是常項，(5)到(6)也是不允許的，因個體常項不能用全稱量詞量化56 謂詞邏輯的歸結(jié)推理法l歸結(jié)方法可推廣到謂詞邏輯，困難在于出現(xiàn)了量詞，變元證明過程同命題邏輯，只不過每一步驟都要考慮到有變元，從而帶來復(fù)雜性l使用推理規(guī)則的推理演算過于靈活，技巧性強(qiáng)，而歸結(jié)法較為機(jī)械，容易使用計算機(jī)來實現(xiàn)。5.6.1 謂詞邏輯歸結(jié)證明過程四步驟(從例子來理解步驟)(1)為證明AB是定理(A，B為謂詞公式)，即AB, 等價的是證明G=AB是矛盾式，這是歸結(jié)法的出發(fā)點(反證法)(2)通過G的合取形式建立子句集S，在建立子句集S的時利用前束范式及Skolem標(biāo)準(zhǔn)形(不嚴(yán)格)，消去存在量