非形式的謂詞演算

非形式的謂詞演算第一頁，共五十三頁，編輯于2023年，星期二5非形式的謂詞演算我們首先來看下面一個論證：所有的人都是會死的，蘇格拉底是人，蘇格拉底是會死的。這個是一個直覺上有效的推理。但是，按照前面所講的方法來分析，它的形式是：p,q所以r。顯然，從命題演算的角度來看這不是一個有效的推理。原因在哪里呢？這種情況下，推理的有效性不是依賴于作為簡單命題的前提和結(jié)論之間的關(guān)系，而依賴于命題各個組成部分之間的關(guān)系、依賴于這些命題本身的形式。第二頁，共五十三頁，編輯于2023年，星期二5非形式的謂詞演算一般來說，我們可以把它分析成以下形式：所有的A是B,a是A,所以,a是A。在這個推理形式中，有幾個值得我們注意的地方：謂詞變元A、B，個體變元a和量詞“所有的”。一般的簡單命題都具有“主詞”和“謂詞”，主詞是命題要加以斷定的事物，而謂詞是指該事物具有的“屬性”。我們來分析下列命題：第三頁，共五十三頁，編輯于2023年，星期二5非形式的謂詞演算在下列各命題中，主詞是用紅字標記的，余下的部分是謂詞：（a）蘇格拉底是人。（b）我寫書。（c）平方為－1的數(shù)不是實數(shù)。（d）世界給人以生存。以后，我們用大寫的英文字母A,B,C,…表示謂詞，用小寫的英文字母a,b,c,…表示主詞。相應(yīng)地，以上命題(a)可以表示為H(s):H表示“是人”，s代表蘇格拉底。命題(b)可以表示為B(i):B表示“寫書”，i代表我。命題(c)可以表示為R(j):R表示“是實數(shù)”，j代表平方為－1的數(shù)。命題(d)可以表示為L(w):L表示“給人以生存”，i代表世界。第四頁，共五十三頁，編輯于2023年，星期二5非形式的謂詞演算只要我們知道了簡單命題如何按照這種形式翻譯成符號語言，加上前面的知識，我們自然也就知道了復合命題如何翻譯成這種符號語言?，F(xiàn)在的問題是：對于“所有人都是會死的”，這樣的命題我們怎么辦？這類命題的主詞不是指稱單個的對象，而是用量詞“所有”賦予多個對象以某個性質(zhì)。我們參考數(shù)學符號體系中的常用方法。例如，說“每個整數(shù)都有素因子”就被翻譯成“對于所有的x來說，如果x是整數(shù)，那么x就有素因子?！鳖愃频?，“所有人都是會死的”也被翻譯成“對于所有的x來說，如果x是人，那么x是會死的?！钡谖屙?，共五十三頁，編輯于2023年，星期二5非形式的謂詞演算以后，為了記法上的方便，我們把這個命題記為“x(MxDx)”。其中：（1）謂詞M、D分別表示“是人”和“是會死的”。（2）“”是全稱量詞符號，表示所有的意思。（3）x是個體變元，當它沒有被量詞約束時，它表示不確定的主體，這個時候我們一般也稱之為自由變元。自由變元的論域是不確定的。（4）單個的全稱量詞符號是不完整的，當它和自由變元結(jié)合成“x”這樣的形式，我們就表示自由變元x被全稱量詞“”約束了。在這里x就成為了約束變元，約束變元的論域是確定的。我們可以指定一個特定的論域，例如“全體自然數(shù)”。當沒有指定特定論域時，我們就把論域看成是全域，即萬事萬物。第六頁，共五十三頁，編輯于2023年，星期二5非形式的謂詞演算（5）但是，僅僅是“x”仍然不是完整的公式，它僅僅表示“所有的事物”或“所有的數(shù)”。顯然這樣還不能完整地構(gòu)成一個公式，從而表達一個全稱命題。只有當它和謂詞變元結(jié)合在一起才構(gòu)成合式公式。例如：“xMx”表示“所有的事物是人”。或者限定x的論域是全體整數(shù)，我們用“xAx”表示“所有的整數(shù)都有素因子”，其中“A”表示“有素因子”。請大家注意：如果x是全域中的不確定個體的話，那么這句話“所有的整數(shù)都有素因子”就翻譯成“x(IxAx)”,其中“I”和“A”分別表示“是整數(shù)和”“有素因子”。第七頁，共五十三頁，編輯于2023年，星期二5非形式的謂詞演算一般來說，還有一個量詞在我們把自然語言翻譯成謂詞符號語言時也是需要的：例如：“有些豬是有翅膀的”。我們一般可以把它看成：“至少存在有一個x使得x是一頭豬并且x有翅膀”。同樣地，我們可以將這個命題翻譯成：“x(PxWx)”，其中“P”和“W”分別表示“是一頭豬”和“有翅膀”。一般來說，“全稱量詞＋普通名詞＋屬性”翻譯時我們使用蘊含聯(lián)結(jié)詞把前后兩個謂詞符號聯(lián)結(jié)起來。“存在量詞＋普通名詞＋屬性”翻譯時我們使用合取聯(lián)結(jié)詞把前后兩個謂詞符號聯(lián)結(jié)起來。第八頁，共五十三頁，編輯于2023年，星期二5非形式的謂詞演算請大家把以下自然語言翻譯成謂詞符號語言：(1)所有的鳥都會飛。(2)并非所有的鳥都會飛。(3)所有的鳥都不會飛。(4)并非所有的鳥都不會飛。(5)至少有一只鳥會飛。(6)并非至少有一只鳥會飛。(7)至少有一只鳥不會飛。(8)并非至少有一只鳥不會飛。(9)有一個整數(shù)大于其他所有整數(shù)。(10)所有的馬都是動物，所以所有的馬頭都是動物頭。(1)-(8)論域是全域，B——鳥，F(xiàn)——會飛。(1)x(BxFx)；(2)x(BxFx)；(3)x(BxFx)；(4)x(BxFx)；第九頁，共五十三頁，編輯于2023年，星期二5非形式的謂詞演算(5)x(BxFx)；(6)x(BxFx)；(7)x(BxFx)；(8)x(BxFx)；(9)論域為全域，I——整數(shù)，LI(x,y)——xy。

x(Ixy(IyLI(x,y))(10)首先，我們把后面那句話等價地翻譯為“對于所有的x而言，如果存在有一個y，y是馬并且x是y(馬)的頭，那么也存在有一個z,z是動物并且x是z(動物)的頭。”論域為全域，H——馬，A——動物，T(x,y)——x是y的頭。

x(HxAx)x(y(HyT(x,y))z(AzT(x,z))。第十頁，共五十三頁，編輯于2023年，星期二5非形式的謂詞演算課后作業(yè)：請把“沒有一個人尊重不自重的人，并且沒有一個人信任他不尊重的人。所以，一個不受尊重的人是不受任何人信任的?！狈g成謂詞符號語言。其中，論域為全域，M——是人，R(x,y)——x尊重y，（注：R(x,x)——表示x自重），H(x,y)——x信任y。第十一頁，共五十三頁，編輯于2023年，星期二5非形式的謂詞演算現(xiàn)在我們來進一步考察(1)－(8)：直覺上，我們是用(7)“至少有一只鳥不會飛”來證實(2)“并非所有的鳥會飛。”即x(BxFx)x(BxFx)

根據(jù)前面的知識，x(BxFx)x(BxFx)2.2.4.(12)＋等值置換x(BxFx)2.2.4.(1)＋等值置換x(BxFx)2.2.4.(6a)＋等值置換現(xiàn)在，我們比較“x(BxFx)”和“x(BxFx)”，我們發(fā)現(xiàn)：后者與前者的區(qū)別僅在于“x”代替了“x”。這樣我們據(jù)明白一個道理：“x”可以替換“x”；另一方面，“x”也可以替換“x”。第十二頁，共五十三頁，編輯于2023年，星期二5非形式的謂詞演算因為直觀上：(1)“并非所有的x都不具有屬性P”(xPx)等價于“存在有某個x具有屬性P”(xPx)。(2)“并非存在有某個x不具有屬性P”(xPx)等價于“所有的x都具有屬性P”(xPx)。于是，存在量詞和全稱量詞只需要有一個，另一個可以借助否定聯(lián)結(jié)詞相應(yīng)地定義出來。同樣的道理:(1)x(BxFx)(8)x(BxFx)(3)x(BxFx)(6)x(BxFx)

(4)x(BxFx)(5)x(BxFx)

上面的證明，大家任意選做一個，寫清楚理由！第十三頁，共五十三頁，編輯于2023年，星期二5非形式的謂詞演算課后作業(yè)：把下列各命題寫成符號形式。先不用存在量詞，然后不用全稱量詞。（任意選擇兩個做）（1）并非所有的汽車都是三只輪子。（2）有些人或者是懶惰的，或者是愚蠢的。（3）沒有一只耗子比任何一只象重。（4）每個數(shù)或者是負的或者有一平方根。要求：把論域和謂詞符號所代表的含義寫清楚。第十四頁，共五十三頁，編輯于2023年，星期二5.1一階語言一階符號語言由下列7類符號構(gòu)成：（1）個體變元符號：x1,x2,…,xn,…。（2）聯(lián)結(jié)詞符號：，。（3）量詞符號：。（4）技術(shù)符號：(，)。（5）個體常元：a1,a2,…,an(,…)。（6）函數(shù)符號：（7）謂詞符號：注1：以后我們用表示蘇格拉底是人。其中個體常元表示蘇格拉底，而一元謂詞表示性質(zhì)“是人”。第十五頁，共五十三頁，編輯于2023年，星期二5.1一階語言注2：謂詞符號的上標表明了謂詞是幾元謂詞。如果是1就表示一個性質(zhì)，如果是2就表示一個二元關(guān)系，如果是3就表示一個三元關(guān)系，如此類推。注：函數(shù)符號的上標和謂詞符號的上標解釋差不多，表示函數(shù)所帶參數(shù)的個數(shù)。不過請大家區(qū)別函數(shù)符號和謂詞符號。謂詞符號可以看成這樣一個函數(shù)：而函數(shù)符號則應(yīng)看成：第十六頁，共五十三頁，編輯于2023年，星期二5.1一階語言一般地，所有的個體變元的集合記為Var，所有的個體常元集記為Con。由(5)-(7)中的符號構(gòu)成的集合稱為L的特征符號集。一般情況下，我們固定(1)-(4)，而隨著情況不同改變(5)-(7)。給定了一個特征符號集也就給定了一個語言的初始符號集。我們在后面常常使用下列元語言符號：x,y,z表示個體變元；P,Q,R表示謂詞符號；F,G,H表示函數(shù)符號；c,d,e表示個體常元。第十七頁，共五十三頁，編輯于2023年，星期二5.2一階語言L中項和原子公式的定義為了定義一階語言L中的合式公式，我們首先必須定義L中的項：（1）變元和個體常元是項；（2）如果是L中的函數(shù)符號，且是L中的項，則也是L中的項。（3）所有的項都是按照（1）和（2）生成的。項在形式語言中將被解釋為對象，即函數(shù)作用于其上的事物，具有某種屬性的事物，對之作出某種斷定的事物。以后在元語言中，我們用t和u表示項。L中的原子公式定義為：如果是L中的一個謂詞符號，是L中的項，則是L中的原子公式。第十八頁，共五十三頁，編輯于2023年，星期二5.2L中合式公式的定義注：原子公式是語言中可斷定的最簡單的公式。例如，某些對象具有某種性質(zhì)。這里“原子”一詞當然是表示不能再分解了。L中的一個合式公式的定義如下：（1）L中的每個原子公式是L中的合式公式。（2）如果A和B是L中的合式公式，則A，AB，xiA(其中xi是任意個體變元)也是合式公式。（3）L中的所有合式公式都是按照(1)和(2)生成的。注1：xiA并不要求A中一定有個體變元xi的出現(xiàn)。第十九頁，共五十三頁，編輯于2023年，星期二5.2L中合式公式的定義注2：我們規(guī)定：xiA是xiA的縮寫。

AB是(AB)的縮寫。

AB是AB的縮寫。注3：我們要注意xi(AB)和xiAB之間的區(qū)別。為此，我們需要再引入一些相關(guān)的定義。定義：在公式xiA中，我們稱A是量詞的轄域。更一般地，當xiA作為子公式出現(xiàn)在B中時，我們稱這個量詞在B中的轄域是A。定義：變元xi在一個公式中的出現(xiàn)稱為約束的，如果它出現(xiàn)在公式中的xi的轄域之內(nèi)，或者xi在xi中。如果一個變元的出現(xiàn)不是約束的，那么我們就稱它是自由的。第二十頁，共五十三頁，編輯于2023年，星期二5.2轄域、約束變元和自由變元例：請說明下列公式中量詞的轄域，以及個體變元的每一次出現(xiàn)是約束的還是自由的。第二十一頁，共五十三頁，編輯于2023年，星期二5.2轄域、約束變元和自由變元當我們僅僅對公式中的變元感興趣時，我們常常有這種寫法：A(x1)或B(x1,…,xn)。在這種情況中，我們一般指其中的變元是自由出現(xiàn)的。如果xi在A中確實是自由出現(xiàn)，那么對于任何項t，A(t)將指對xi的每次自由出現(xiàn)都代入t后所得到的結(jié)果。下面我們解釋一個比較重要的概念：令A是L中的任意公式，我們稱項t對A中的個體變元xi是自由的，如果xi并不自由地出現(xiàn)在A的一個xj的轄域中，這里的xj是指出現(xiàn)在t中的任何變元。粗略地說，所謂項對個體變元的自由指的是——項可以代入A中的xi每個自由出現(xiàn)，而不引起和A中的量詞相互作用。第二十二頁，共五十三頁，編輯于2023年，星期二項對個體變元的代入舉例來說，（1）x3對公式中的x2是自由的，而x1對公式中的x2則是不自由的。因為x2自由地出現(xiàn)在x1的轄域中，而x2并沒有自由地出現(xiàn)在x3的轄域中（在這里有兩個意思：或者x2沒有出現(xiàn)在x3的轄域中，或者x2出現(xiàn)在x3的轄域中，但是x2的出現(xiàn)是不自由的）。對于（1）中所舉的例子來說，是因為x2沒有出現(xiàn)在x3的轄域中。（2）也有可能出現(xiàn)x2約束地出現(xiàn)在x3的轄域中的情況，例如x3對公式中的x2是自由的。因為在這個公式中沒有x2的自由出現(xiàn)。第二十三頁，共五十三頁，編輯于2023年，星期二項對個體變元的代入由上不難看出，項t對公式A中的變元x是自由的，主要是看t對x在A中的自由出現(xiàn)進行代入是不是自由的。而對x的約束出現(xiàn)進行代入則沒有太多的意義。就好像（2）中例子所看到的那樣。第二十四頁，共五十三頁，編輯于2023年，星期二課后作業(yè)：第二十五頁，共五十三頁，編輯于2023年，星期二項對公式的替換定義第二十六頁，共五十三頁，編輯于2023年，星期二項對公式的替換定義——舉例第二十七頁，共五十三頁，編輯于2023年，星期二課后作業(yè)：第二十八頁，共五十三頁，編輯于2023年，星期二5.3解釋定義5.3.1：L的一個解釋I是由以下幾部分內(nèi)容構(gòu)成的：（1）一個非空集DI（I的論域）；（2）一個特別的元素集{(a1)’,(a2)’,…,}；（3）一個在DI上的函數(shù)集（4）一個在DI上的關(guān)系集我們的意圖是：L中的變元將會被解釋為“對象”，而集合DI將被解釋為變元在其上取值的論域。特別的元素集將對應(yīng)L中個體常元的取值。DI上的函數(shù)和關(guān)系將分別對應(yīng)L中函數(shù)和關(guān)系的解釋。注：以后為了方便，在不會引起混淆的情況下，我們不區(qū)分a1與(a1)’第二十九頁，共五十三頁，編輯于2023年，星期二5.3解釋一階語言：如果一個語言的解釋中，量詞僅僅作用于將被解釋為“對象”的個體變元之上。二階語言：如果一個語言的解釋中，量詞不僅可以作用于將被解釋為“對象”的個體變元之上，還可以作用于將被解釋為對象關(guān)系的謂詞變元之上。N階語言：如果一個語言的解釋中，量詞可以作用于將被解釋為N－1階關(guān)系之間的關(guān)系之上。一階符號語言系統(tǒng)又可稱為一階邏輯，二階以上的符號語言系統(tǒng)統(tǒng)稱為高階邏輯。在本課程中，我們只討論一階邏輯。第三十頁，共五十三頁，編輯于2023年，星期二5.3解釋舉例：（1）用一階語言表示有關(guān)自然數(shù)的算術(shù)命題。解釋I：論域DI

＝{0,1,2,…}；特別元素只有一個0，它將被解釋為個體常元a1所對應(yīng)的對象；于是，在這樣一個解釋I下，公式（1）將被解釋為：對于所有的自然數(shù)x,y來說，并非對所有的自然數(shù)z，都有x+yz。第三十一頁，共五十三頁，編輯于2023年，星期二5.3解釋另一方面，我們知道上述公式邏輯等值于：這個公式將被解釋為：對于所有的自然數(shù)x,y來說，存在有一個自然數(shù)z，使得x+y=z。但是，我們要注意到一階語言不能表達這樣的算術(shù)命題“每個非空的自然數(shù)集都有一個最小數(shù)”，顯然在描述這個命題是，我們不得不將全稱量詞作用于自然數(shù)集，這樣的表述將成為二階語言中的一個公式。只有當一個語言被給定一個解釋之后，我們才能對有關(guān)公式的意義說些什么。也就是說，只有在第三十二頁，共五十三頁，編輯于2023年，星期二5.3解釋一個解釋下，才能考察這個公式的真假。上述公式（1）在解釋I下顯然是假的。但是，我們可以給這個公式另一種解釋I’使得它為真。在解釋I’下DI’是正有理數(shù)，這樣，公式（1）將會被解釋為：對任意的有理數(shù)x,y來說，存在有有理數(shù)z使得xy=z.顯然這個命題是真的。第三十三頁，共五十三頁，編輯于2023年，星期二5.3解釋課后作業(yè)：第三十四頁，共五十三頁，編輯于2023年，星期二5.4滿足和真正如命題邏輯系統(tǒng)PC中的討論一樣（只有對命題公式中的命題變元指派真值，命題公式才會有真假），在謂詞邏輯中，一階公式只有在一個具體的解釋下才有真假。在這里，解釋相當于命題邏輯系統(tǒng)中所介紹的賦值（指派）。令I(lǐng)是以DI為論域的語言L上的一個解釋。定義5.4.1：I上的一個賦值是一個從L的項集到集DI具有下列性質(zhì)的一個函數(shù)v：（1）v(ai)=(ai)’,對于L中的每個個體常元ai；（2）第三十五頁，共五十三頁，編輯于2023年，星期二5.4滿足和真賦值是這樣一個規(guī)則：它給語言L中的每一個項指派了DI中的一個對象作為它的解釋。注記：（1）在一個給定的解釋下，將有多種不同的賦值。因為對于個體變元總有不同賦值的可能。（2）一給定的賦值將對L中的每一個變元xi指派DI中的一個元素。因此，如果對L中個體變元的賦值被確定了，那么這個賦值也被確定下來了。這是因為個體常元和復雜項都在5.4.1.(1)和(2)中被指派了DI中的一個元素。其中(2)是對復雜項的指派的歸納定義。下面我們介紹一個后面經(jīng)常會用到的定義——i-等值：稱兩個賦值v和v’是i-等值，如果v(xj)=v’(xj)，對每個ij.即：兩個賦值只有在xi上可能不同（也可能相同，一般情況下是不同的）。第三十六頁，共五十三頁，編輯于2023年，星期二5.4滿足和真現(xiàn)在我們來考察在一個解釋和賦值之下，一階公式的滿足。定義5.4.2:令A是L的一個公式，I是L的一個解釋。I中的一個賦值v稱為滿足A，記為vI(A)=1(在不混淆的情況下記為v(A)=1)，如果(1)如果A是原子公式(2)如果A是“B”這樣的形式，那么v(A)=1當且僅當v(B)1（這也就是說，v不滿足B，當且僅當v就滿足B）(3)如果A是“BC”這樣的形式，那么v(BC)=1，當且僅當，或者v(B)1或者v(C)=1

（即或者v不滿足B或者v滿足C）。第三十七頁，共五十三頁，編輯于2023年，星期二5.4滿足和真(4)解釋I中的一個賦值v滿足當且僅當，每個i-等值于v的賦值v’滿足B,注：我們有必要對(4)做出一些解釋：首先，我們說I中的賦值v滿足一個公式是這個意思：對于任意DI中的對象d’，I中的賦值v都會滿足公式，其中對象d’是個體常元d在I下的解釋。但是，怎么表示DI中的任意對象d’，這就得要引入前面的與vi-等值的賦值v’了。由于v和v’的唯一區(qū)別是在xi的賦值上有不同，因此引入v’的意圖就在于可以給xi賦值不同的DI中的對象，而其他第三十八頁，共五十三頁，編輯于2023年，星期二5.4滿足和真的情況則保持不變。如果在任意的與vi-等值的賦值v’下，公式都有（其中個體常元c替換個體變元xi表示在賦值v’下xi將被解釋為論域中的對象c’

。當然我們也可以選擇a,b,e,…替換xi

，這正是其他與vi-等值的賦值所干的事情。）假如所有的與vi-等值的賦值都有使得（d*表示某個個體常元），則我們前面所說的意思已經(jīng)充分地表達出來了。第三十九頁，共五十三頁，編輯于2023年，星期二5.4滿足和真例：（1）算術(shù)解釋N：論域DI

＝{0,1,2,…}；個體常元a1被解釋為0；在解釋N的一個賦值v下:v(x1)=2,v(x1)=6,v(x1)=3,v(x1)=4。顯然，賦值下v滿足公式（1）因為2×6＝3×4.第四十頁，共五十三頁，編輯于2023年，星期二5.4滿足和真例2：在解釋N中被解釋為：對任意的自然數(shù)n，nm=mn。這顯然是一個真命題?，F(xiàn)在我們面對的一個問題是：公式（2）是可以從公式（1）中可推導出來的，或者說，公式（1）是否邏輯蘊涵公式（2）呢？分析步驟1：令v是N中的任意一個賦值，顯然v(x1)和v(x2)是自然數(shù)，因此公式（1）被解釋為v(x1)×v(x2)＝v(x2)×v(x1)，而這顯然是真的。分析步驟2：對任意與v1-等值的賦值v’來說，v’無非是要改變v對于x1的賦值。但是，無論如何第四十一頁，共五十三頁，編輯于2023年，星期二5.4滿足和真v’(x1)仍然是一個自然數(shù)，因此v’(x1)×v(x2)＝v(x2)×v’(x1)仍然是真的。這意味著對任意與v1-等值的賦值v’，都有成立，所以根據(jù)定義5.4.2.(4)我們有結(jié)論：賦值v在解釋N下滿足公式（2），再由于賦值v的任意性，解釋N下所有的賦值都滿足公式（2）。同理可證，在解釋N下的所有賦值都滿足這個公式。第四十二頁，共五十三頁，編輯于2023年，星期二5.4滿足和真例3：在解釋N下是什么意思，請大家思考解釋N下是否有賦值v是否滿足公式。不難發(fā)現(xiàn)，以后用另外的項或者變元去替代一個變元是經(jīng)常用到的技巧，因此，以下定理是必須的。第四十三頁，共五十三頁，編輯于2023年，星期二5.4有窮指派引理1命題邏輯中的有窮指派引理：令{p1,…,pn}是命題公式A中出現(xiàn)的所有命題變元所構(gòu)成的集合，假如v和u分別是對A的任意兩組真值指派(賦值函數(shù))，并且有v(p1)=u(p1),…,v(pn)=u(pn)，那么v(A)=u(A)。證明思路：施歸納于公式A的結(jié)構(gòu)易證。其中我們會用到賦值函數(shù)的定義。這個證明比較簡單，請同學們作為課后作業(yè)完成。有窮指派引理旨在說明：一個賦值函數(shù)對于命題公式A的真值的影響僅僅在于它給A中出現(xiàn)的命題變元指派怎樣的真值，而與A中不出現(xiàn)的命題變元被指派什么真值無關(guān)。第四十四頁，共五十三頁，編輯于2023年，星期二5.4有窮指派引理循著這樣的思路，我們試圖考察對一階公式是不是也存在有類似的有窮指派引理呢？謂詞邏輯中的有窮指派引理旨在表明：在一個確定的解釋下，一個賦值函數(shù)v是否滿足一階公式A，僅僅取決于v給A中出現(xiàn)的自由變元的賦值是什么，而與A中不出現(xiàn)的自由變元或A中約束出現(xiàn)的自由變元無關(guān)。第四十五頁，共五十三頁，編輯于2023年，星期二5.4有窮指派引理定理5.4.3：令I(lǐng)是L的一個解釋，A是L的一個公式。如果v和w都是賦值，并且對A中的每個自由變元xi，有v(xi)=w(xi)，那么v滿足A，當且僅當，w滿足A.證明：對A中的聯(lián)結(jié)詞和量詞的數(shù)目施歸納。基礎(chǔ)步驟：A是一個原子公式，例如A(t1,…,tn)。賦值v和w對出現(xiàn)在A中的所有自由變元和個體常元賦值都是一樣的，所以對任意項ti(ni1)，有v(ti)=w(ti)(為什么？請同學們在課后作業(yè)中證明)。又因為v和w對謂詞A的賦值是一樣的，所以v滿足A，當且僅當，w滿足A.第四十六頁，共五十三頁，編輯于2023年，星期二5.4有窮指派引理歸納步驟：情形1：A是B情形2：A是BC

情形1，2易證，請同學們在課后作業(yè)中完成。情形3：A是xiB

假設(shè)v滿足A，那么對于所有的與vi-等值的v’都滿足B?，F(xiàn)在，我們對賦值w，我們?nèi)我膺x擇一個與wi-等值的賦值函數(shù)w’。由于xi在xiB中不自由出現(xiàn)，所以只要個體變元y在xiB是自由的，就有w’(y)=v(y)?，F(xiàn)在，我們對任意的w’，相應(yīng)地構(gòu)造v’如下：第四十七頁，共五十三頁，編輯于2023年，星期二5.4有窮指派引理

(1)v’(xi)=w’(xi)在xi這一點上

(2)v’(xj)=w’(xj)(ji)在xi這一點之外顯然，對于B中出現(xiàn)的任意自由變元y，我們有w’(y)=v’(y)。（因為對xiB

中出現(xiàn)的自由變元，我們已經(jīng)有w’(y)=v(y)=v’(y)。所以。對于公式B來說，最多無非多增加一個自由變元xi

，但是根據(jù)v’的構(gòu)造（1），顯然我們就有了以上結(jié)論。）進一步，根據(jù)前面的結(jié)論——v’都是滿足B的，根據(jù)歸納假設(shè)(條件1B中出現(xiàn)的任意自由變元y，我們有w’(y)=v’(y);條件2B比xiB

結(jié)構(gòu)簡單)，有w’也，滿足B。再根據(jù)w’的任意性和滿足的定義，我們有w滿足xiB

。用類似方法可以證明：w滿足xiB

v滿足xiB。

第四十八頁，共五十三頁，編輯于2023年，星期二5.4有窮指派引理定理5.4.4：令