非形式的謂詞演算

非形式的謂詞演算5非形式的謂詞演算我們首先來看下面一個(gè)論證：所有的人都是會(huì)死的，蘇格拉底是人，蘇格拉底是會(huì)死的。這個(gè)是一個(gè)直覺上有效的推理。但是，按照前面所講的方法來分析，它的形式是：p,q所以r。顯然，從命題演算的角度來看這不是一個(gè)有效的推理。原因在哪里呢？這種情況下，推理的有效性不是依賴于作為簡(jiǎn)單命題的前提和結(jié)論之間的關(guān)系，而依賴于命題各個(gè)組成部分之間的關(guān)系、依賴于這些命題本身的形式。第2頁,共53頁，2024年2月25日，星期天5非形式的謂詞演算一般來說，我們可以把它分析成以下形式：所有的A是B,a是A,所以,a是A。在這個(gè)推理形式中，有幾個(gè)值得我們注意的地方：謂詞變?cè)狝、B，個(gè)體變?cè)猘和量詞“所有的”。一般的簡(jiǎn)單命題都具有“主詞”和“謂詞”，主詞是命題要加以斷定的事物，而謂詞是指該事物具有的“屬性”。我們來分析下列命題：第3頁,共53頁，2024年2月25日，星期天5非形式的謂詞演算在下列各命題中，主詞是用紅字標(biāo)記的，余下的部分是謂詞：（a）蘇格拉底是人。（b）我寫書。（c）平方為－1的數(shù)不是實(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í)數(shù)”，j代表平方為－1的數(shù)。命題(d)可以表示為L(zhǎng)(w):L表示“給人以生存”，i代表世界。第4頁,共53頁，2024年2月25日，星期天5非形式的謂詞演算只要我們知道了簡(jiǎn)單命題如何按照這種形式翻譯成符號(hào)語言，加上前面的知識(shí)，我們自然也就知道了復(fù)合命題如何翻譯成這種符號(hào)語言。現(xiàn)在的問題是：對(duì)于“所有人都是會(huì)死的”，這樣的命題我們?cè)趺崔k？這類命題的主詞不是指稱單個(gè)的對(duì)象，而是用量詞“所有”賦予多個(gè)對(duì)象以某個(gè)性質(zhì)。我們參考數(shù)學(xué)符號(hào)體系中的常用方法。例如，說“每個(gè)整數(shù)都有素因子”就被翻譯成“對(duì)于所有的x來說，如果x是整數(shù)，那么x就有素因子?！鳖愃频兀八腥硕际菚?huì)死的”也被翻譯成“對(duì)于所有的x來說，如果x是人，那么x是會(huì)死的。”第5頁,共53頁，2024年2月25日，星期天5非形式的謂詞演算以后，為了記法上的方便，我們把這個(gè)命題記為“

x(MxDx)”。其中：（1）謂詞M、D分別表示“是人”和“是會(huì)死的”。（2）“

”是全稱量詞符號(hào)，表示所有的意思。（3）x是個(gè)體變?cè)?dāng)它沒有被量詞約束時(shí)，它表示不確定的主體，這個(gè)時(shí)候我們一般也稱之為自由變?cè)?。自由變?cè)恼撚蚴遣淮_定的。（4）單個(gè)的全稱量詞符號(hào)是不完整的，當(dāng)它和自由變?cè)Y(jié)合成“

x”這樣的形式，我們就表示自由變?cè)獂被全稱量詞“

”約束了。在這里x就成為了約束變?cè)s束變?cè)恼撚蚴谴_定的。我們可以指定一個(gè)特定的論域，例如“全體自然數(shù)”。當(dāng)沒有指定特定論域時(shí)，我們就把論域看成是全域，即萬事萬物。第6頁,共53頁，2024年2月25日，星期天5非形式的謂詞演算（5）但是，僅僅是“

x”仍然不是完整的公式，它僅僅表示“所有的事物”或“所有的數(shù)”。顯然這樣還不能完整地構(gòu)成一個(gè)公式，從而表達(dá)一個(gè)全稱命題。只有當(dāng)它和謂詞變?cè)Y(jié)合在一起才構(gòu)成合式公式。例如：“

xMx”表示“所有的事物是人”。或者限定x的論域是全體整數(shù)，我們用“

xAx”表示“所有的整數(shù)都有素因子”，其中“A”表示“有素因子”。請(qǐng)大家注意：如果x是全域中的不確定個(gè)體的話，那么這句話“所有的整數(shù)都有素因子”就翻譯成“

x(IxAx)”,其中“I”和“A”分別表示“是整數(shù)和”“有素因子”。第7頁,共53頁，2024年2月25日，星期天5非形式的謂詞演算一般來說，還有一個(gè)量詞在我們把自然語言翻譯成謂詞符號(hào)語言時(shí)也是需要的：例如：“有些豬是有翅膀的”。我們一般可以把它看成：“至少存在有一個(gè)x使得x是一頭豬并且x有翅膀”。同樣地，我們可以將這個(gè)命題翻譯成：“

x(PxWx)”，其中“P”和“W”分別表示“是一頭豬”和“有翅膀”。一般來說，“全稱量詞＋普通名詞＋屬性”翻譯時(shí)我們使用蘊(yùn)含聯(lián)結(jié)詞把前后兩個(gè)謂詞符號(hào)聯(lián)結(jié)起來?！按嬖诹吭~＋普通名詞＋屬性”翻譯時(shí)我們使用合取聯(lián)結(jié)詞把前后兩個(gè)謂詞符號(hào)聯(lián)結(jié)起來。第8頁,共53頁，2024年2月25日，星期天5非形式的謂詞演算請(qǐng)大家把以下自然語言翻譯成謂詞符號(hào)語言：(1)所有的鳥都會(huì)飛。(2)并非所有的鳥都會(huì)飛。(3)所有的鳥都不會(huì)飛。(4)并非所有的鳥都不會(huì)飛。(5)至少有一只鳥會(huì)飛。(6)并非至少有一只鳥會(huì)飛。(7)至少有一只鳥不會(huì)飛。(8)并非至少有一只鳥不會(huì)飛。(9)有一個(gè)整數(shù)大于其他所有整數(shù)。(10)所有的馬都是動(dòng)物，所以所有的馬頭都是動(dòng)物頭。(1)-(8)論域是全域，B——鳥，F(xiàn)——會(huì)飛。(1)x(BxFx)；(2)x(BxFx)；(3)x(BxFx)；(4)x(BxFx)；第9頁,共53頁，2024年2月25日，星期天5非形式的謂詞演算(5)x(BxFx)；(6)x(BxFx)；(7)x(BxFx)；(8)x(BxFx)；(9)論域?yàn)槿颍琁——整數(shù)，LI(x,y)——xy。

x(Ixy(IyLI(x,y))(10)首先，我們把后面那句話等價(jià)地翻譯為“對(duì)于所有的x而言，如果存在有一個(gè)y，y是馬并且x是y(馬)的頭，那么也存在有一個(gè)z,z是動(dòng)物并且x是z(動(dòng)物)的頭。”論域?yàn)槿?，H——馬，A——?jiǎng)游?，T(x,y)——x是y的頭。

x(HxAx)x(y(HyT(x,y))z(AzT(x,z))。第10頁,共53頁，2024年2月25日，星期天5非形式的謂詞演算課后作業(yè)：請(qǐng)把“沒有一個(gè)人尊重不自重的人，并且沒有一個(gè)人信任他不尊重的人。所以，一個(gè)不受尊重的人是不受任何人信任的?！狈g成謂詞符號(hào)語言。其中，論域?yàn)槿颍琈——是人，R(x,y)——x尊重y，（注：R(x,x)——表示x自重），H(x,y)——x信任y。第11頁,共53頁，2024年2月25日，星期天5非形式的謂詞演算現(xiàn)在我們來進(jìn)一步考察(1)－(8)：直覺上，我們是用(7)“至少有一只鳥不會(huì)飛”來證實(shí)(2)“并非所有的鳥會(huì)飛?！奔?/p>

x(BxFx)x(BxFx)

根據(jù)前面的知識(shí)，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ù)明白一個(gè)道理：“

x”可以替換“

x”；另一方面，“

x”也可以替換“

x”。第12頁,共53頁，2024年2月25日，星期天5非形式的謂詞演算因?yàn)橹庇^上：(1)“并非所有的x都不具有屬性P”(xPx)等價(jià)于“存在有某個(gè)x具有屬性P”(xPx)。(2)“并非存在有某個(gè)x不具有屬性P”(xPx)等價(jià)于“所有的x都具有屬性P”(xPx)。于是，存在量詞和全稱量詞只需要有一個(gè)，另一個(gè)可以借助否定聯(lián)結(jié)詞相應(yīng)地定義出來。同樣的道理:(1)x(BxFx)(8)x(BxFx)(3)x(BxFx)(6)x(BxFx)

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

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

A，AB，xiA(其中xi是任意個(gè)體變?cè)?也是合式公式。（3）L中的所有合式公式都是按照(1)和(2)生成的。注1：

xiA并不要求A中一定有個(gè)體變?cè)獂i的出現(xiàn)。第19頁,共53頁，2024年2月25日，星期天5.2L中合式公式的定義注2：我們規(guī)定：

xiA是xiA的縮寫。

AB是(AB)的縮寫。

AB是AB的縮寫。注3：我們要注意xi(AB)和xiAB之間的區(qū)別。為此，我們需要再引入一些相關(guān)的定義。定義：在公式xiA中，我們稱A是量詞的轄域。更一般地，當(dāng)xiA作為子公式出現(xiàn)在B中時(shí)，我們稱這個(gè)量詞在B中的轄域是A。定義：變?cè)獂i在一個(gè)公式中的出現(xiàn)稱為約束的，如果它出現(xiàn)在公式中的xi的轄域之內(nèi)，或者xi在xi中。如果一個(gè)變?cè)某霈F(xiàn)不是約束的，那么我們就稱它是自由的。第20頁,共53頁，2024年2月25日，星期天5.2轄域、約束變?cè)妥杂勺冊(cè)赫?qǐng)說明下列公式中量詞的轄域，以及個(gè)體變?cè)拿恳淮纬霈F(xiàn)是約束的還是自由的。第21頁,共53頁，2024年2月25日，星期天5.2轄域、約束變?cè)妥杂勺冊(cè)?dāng)我們僅僅對(duì)公式中的變?cè)信d趣時(shí)，我們常常有這種寫法：A(x1)或B(x1,…,xn)。在這種情況中，我們一般指其中的變?cè)亲杂沙霈F(xiàn)的。如果xi在A中確實(shí)是自由出現(xiàn)，那么對(duì)于任何項(xiàng)t，A(t)將指對(duì)xi的每次自由出現(xiàn)都代入t后所得到的結(jié)果。下面我們解釋一個(gè)比較重要的概念：令A(yù)是L中的任意公式，我們稱項(xiàng)t對(duì)A中的個(gè)體變?cè)獂i是自由的，如果xi并不自由地出現(xiàn)在A的一個(gè)

xj的轄域中，這里的xj是指出現(xiàn)在t中的任何變?cè)?。粗略地說，所謂項(xiàng)對(duì)個(gè)體變?cè)淖杂芍傅氖恰?xiàng)可以代入A中的xi每個(gè)自由出現(xiàn)，而不引起和A中的量詞相互作用。第22頁,共53頁，2024年2月25日，星期天項(xiàng)對(duì)個(gè)體變?cè)拇肱e例來說，（1）x3對(duì)公式中的x2是自由的，而x1對(duì)公式中的x2則是不自由的。因?yàn)閤2自由地出現(xiàn)在

x1的轄域中，而x2并沒有自由地出現(xiàn)在x3的轄域中（在這里有兩個(gè)意思：或者x2沒有出現(xiàn)在x3的轄域中，或者x2出現(xiàn)在x3的轄域中，但是x2的出現(xiàn)是不自由的）。對(duì)于（1）中所舉的例子來說，是因?yàn)閤2沒有出現(xiàn)在x3的轄域中。（2）也有可能出現(xiàn)x2約束地出現(xiàn)在x3的轄域中的情況，例如x3對(duì)公式中的x2是自由的。因?yàn)樵谶@個(gè)公式中沒有x2的自由出現(xiàn)。第23頁,共53頁，2024年2月25日，星期天項(xiàng)對(duì)個(gè)體變?cè)拇胗缮喜浑y看出，項(xiàng)t對(duì)公式A中的變?cè)獂是自由的，主要是看t對(duì)x在A中的自由出現(xiàn)進(jìn)行代入是不是自由的。而對(duì)x的約束出現(xiàn)進(jìn)行代入則沒有太多的意義。就好像（2）中例子所看到的那樣。第24頁,共53頁，2024年2月25日，星期天課后作業(yè)：第25頁,共53頁，2024年2月25日，星期天項(xiàng)對(duì)公式的替換定義第26頁,共53頁，2024年2月25日，星期天項(xiàng)對(duì)公式的替換定義——舉例第27頁,共53頁，2024年2月25日，星期天課后作業(yè)：第28頁,共53頁，2024年2月25日，星期天5.3解釋定義5.3.1：L的一個(gè)解釋I是由以下幾部分內(nèi)容構(gòu)成的：（1）一個(gè)非空集DI（I的論域）；（2）一個(gè)特別的元素集{(a1)’,(a2)’,…,}；（3）一個(gè)在DI上的函數(shù)集（4）一個(gè)在DI上的關(guān)系集我們的意圖是：L中的變?cè)獙?huì)被解釋為“對(duì)象”，而集合DI將被解釋為變?cè)谄渖先≈档恼撚?。特別的元素集將對(duì)應(yīng)L中個(gè)體常元的取值。DI上的函數(shù)和關(guān)系將分別對(duì)應(yīng)L中函數(shù)和關(guān)系的解釋。注：以后為了方便，在不會(huì)引起混淆的情況下，我們不區(qū)分a1與(a1)’第29頁,共53頁，2024年2月25日，星期天5.3解釋一階語言：如果一個(gè)語言的解釋中，量詞僅僅作用于將被解釋為“對(duì)象”的個(gè)體變?cè)?。二階語言：如果一個(gè)語言的解釋中，量詞不僅可以作用于將被解釋為“對(duì)象”的個(gè)體變?cè)?，還可以作用于將被解釋為對(duì)象關(guān)系的謂詞變?cè)稀階語言：如果一個(gè)語言的解釋中，量詞可以作用于將被解釋為N－1階關(guān)系之間的關(guān)系之上。一階符號(hào)語言系統(tǒng)又可稱為一階邏輯，二階以上的符號(hào)語言系統(tǒng)統(tǒng)稱為高階邏輯。在本課程中，我們只討論一階邏輯。第30頁,共53頁，2024年2月25日，星期天5.3解釋舉例：（1）用一階語言表示有關(guān)自然數(shù)的算術(shù)命題。解釋I：論域DI

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

B”這樣的形式，那么v(A)=1當(dāng)且僅當(dāng)v(B)1（這也就是說，v不滿足B，當(dāng)且僅當(dāng)v就滿足B）(3)如果A是“BC”這樣的形式，那么v(BC)=1，當(dāng)且僅當(dāng)，或者v(B)1或者v(C)=1

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

。當(dāng)然我們也可以選擇a,b,e,…替換xi

，這正是其他與vi-等值的賦值所干的事情。）假如所有的與vi-等值的賦值都有使得（d*表示某個(gè)個(gè)體常元），則我們前面所說的意思已經(jīng)充分地表達(dá)出來了。第39頁,共53頁，2024年2月25日，星期天5.4滿足和真例：（1）算術(shù)解釋N：論域DI

＝{0,1,2,…}；個(gè)體常元a1被解釋為0；在解釋N的一個(gè)賦值v下:v(x1)=2,v(x1)=6,v(x1)=3,v(x1)=4。顯然，賦值下v滿足公式（1）因?yàn)?×6＝3×4.第40頁,共53頁，2024年2月25日，星期天5.4滿足和真例2：在解釋N中被解釋為：對(duì)任意的自然數(shù)n，nm=mn。這顯然是一個(gè)真命題?，F(xiàn)在我們面對(duì)的一個(gè)問題是：公式（2）是可以從公式（1）中可推導(dǎo)出來的，或者說，公式（1）是否邏輯蘊(yùn)涵公式（2）呢？分析步驟1：令v是N中的任意一個(gè)賦值，顯然v(x1)和v(x2)是自然數(shù)，因此公式（1）被解釋為v(x1)×v(x2)＝v(x2)×v(x1)，而這顯然是真的。分析步驟2：對(duì)任意與v1-等值的賦值v’來說，v’無非是要改變v對(duì)于x1的賦值。但是，無論如何第41頁,共53頁，2024年2月25日，星期天5.4滿足和真v’(x1)仍然是一個(gè)自然數(shù)，因此v’(x1)×v(x2)＝v(x2)×v’(x1)仍然是真的。這意味著對(duì)任意與v1-等值的賦值v’，都有成立，所以根據(jù)定義5.4.2.(4)我們有結(jié)論：賦值v在解釋N下滿足公式（2），再由于賦值v的任意性，解釋N下所有的賦值都滿足公式（2）。同理可證，在解釋N下的所有賦值都滿足這個(gè)公式。第42頁,共53頁，2024年2月25日，星期天5.4滿足和真例3：在解釋N下是什么意思，請(qǐng)大家思考解釋N下是否有賦值v是否滿足公式。不難發(fā)現(xiàn)，以后用另外的項(xiàng)或者變?cè)ヌ娲粋€(gè)變?cè)墙?jīng)常用到的技巧，因此，以下定理是必須的。第43頁,共53頁，2024年2月25日，星期天5.4有窮指派引理1命題邏輯中的有窮指派引理：令{p1,…,pn}是命題公式A中出現(xiàn)的所有命題變?cè)鶚?gòu)成的集合，假如v和u分別是對(duì)A的任意兩組真值指派(賦值函數(shù))，并且有v(p1)=u(p1),…,v(pn)=u(pn)，那么v(A)=u(A)。證明思路：施歸納于公式A的結(jié)構(gòu)易證。其中我們會(huì)用到賦值函數(shù)的定義。這個(gè)證明比較簡(jiǎn)單，請(qǐng)同學(xué)們作為課后作業(yè)完成。有窮指派引理旨在說明：一個(gè)賦值函數(shù)對(duì)于命題公式A的真值的影響僅僅在于它給A中出現(xiàn)的命題變?cè)概稍鯓拥恼嬷?，而與A中不出現(xiàn)的命題變?cè)恢概墒裁凑嬷禑o關(guān)。第44頁,共53頁，2024年2月25日，星期天5.4有窮指派引理循著這樣的思路，我們?cè)噲D考察對(duì)一階公式是不是也存在有類似的有窮指派引理呢？謂詞邏輯中的有窮指派引理旨在表明：在一個(gè)確定的解釋下，一個(gè)賦值函數(shù)v是否滿足一階公式A，僅僅取決于v給A中出現(xiàn)的自由變?cè)馁x值是什么，而與A中不出現(xiàn)的自由變?cè)駻中約束出現(xiàn)的自由變?cè)獰o關(guān)。第45頁,共53頁，2024年2月25日，星期天5.4有窮指派引理定理5.4.3：令I(lǐng)是L的一個(gè)解釋，A是L的一個(gè)公式。如果v和w都是賦值，并且對(duì)A中的每個(gè)自由變?cè)獂i，有v(xi)=w(xi)，那么v滿足A，當(dāng)且僅當(dāng)，w滿足A.證明：對(duì)A中的聯(lián)結(jié)詞和量詞的數(shù)目施歸納?；A(chǔ)步驟：A是一個(gè)原子公式，例如A(t1,…,tn)。賦值v和w對(duì)出現(xiàn)在A中的所有自由變?cè)蛡€(gè)體常元賦值都是一樣的，所以對(duì)任意項(xiàng)ti(n

i1)，有v(ti)=w(ti)(為什么？請(qǐng)同學(xué)們?cè)谡n后作業(yè)中證明)。又因?yàn)関和w對(duì)謂詞A的賦值是一樣的，所以v滿足A，當(dāng)且僅當(dāng)，w滿足A.第46頁,共53頁，2024年2月25日，星期天5.4有窮指派引理歸納步驟：情形1：A是

B情形2：A是BC

情形1，2易證，請(qǐng)同學(xué)們?cè)谡n后作業(yè)中完成。情形3：A是xiB

假設(shè)v滿足A，那么對(duì)于所有的與vi-等值的v’都滿足B。現(xiàn)在，我們對(duì)賦值w，我們?nèi)我膺x擇一個(gè)與wi-等值的賦值函數(shù)w’。由于xi在

xiB中不自由出現(xiàn)，所以只要個(gè)體變?cè)獃在xiB是自由的，就有w’(y)=v(y)。現(xiàn)在，我們對(duì)任意的w’，相應(yīng)地構(gòu)造v’如下：第47頁,共53頁，2024年2月25日，星期天5.4有窮指派引理

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

(2)v’(xj)=w’(xj)(ji)在xi這一點(diǎn)之外顯然，對(duì)于B中出現(xiàn)的任意自由變?cè)獃，我們有w’(y)=v’(y)。（因?yàn)閷?duì)

xiB

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

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

xiB

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

xiB

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

xiB

v滿足

xiB。

第48頁,共53頁，2024年2月25日，星期天5.4有窮指派引理定理5.4.4：令A(yù)(xi