邏輯學(xué)導(dǎo)論第四章課件

1、邏輯學(xué)導(dǎo)論第四章命題邏輯和詞項(xiàng)邏輯的局限性（1）它們都不能處理關(guān)系命題及其推理。（2）它們都不能處理量詞內(nèi)部含聯(lián)結(jié)詞結(jié)構(gòu)的命題及其推理。所以，我們還需要另外的邏輯謂詞邏輯，它把一個(gè)命題拆分為個(gè)體詞、謂詞、量詞，很多時(shí)候還要加上聯(lián)結(jié)詞；它能夠在一個(gè)統(tǒng)一的框架內(nèi)同時(shí)處理性質(zhì)命題和關(guān)系命題及其推理。個(gè)體詞個(gè)體詞就是表示對(duì)象域中的個(gè)體的符號(hào)，包括個(gè)體變項(xiàng)和個(gè)體常項(xiàng)。其中，個(gè)體變項(xiàng)使用小寫字母x，y，z，等等，表示某個(gè)特定的范圍內(nèi)的某個(gè)不確定的對(duì)象。個(gè)體常項(xiàng)使用小寫字母a，b，c，等等，表示某個(gè)特定范圍內(nèi)的某個(gè)確定的對(duì)象。這里所說的“某個(gè)特定的范圍”，叫做“論域”，即由一定對(duì)象所組成的類或者集合。論域規(guī)

2、定了個(gè)體變項(xiàng)的取值范圍，因此也叫做“個(gè)體域”。論域一般是“全域”，即由世界上所有能夠被思考、被談?wù)摰氖挛锝M成的集合；有時(shí)也取特定個(gè)體域?yàn)檎撚颉?一、個(gè)體詞、性質(zhì)謂詞、量詞和公式一元謂詞和性質(zhì)謂詞符號(hào)，用大寫字母F，G，R，S等表示，若只把這些謂詞符號(hào)用于單個(gè)的個(gè)體詞，叫做“一元謂詞符號(hào)”，經(jīng)解釋后，它們表示論域中個(gè)體的某個(gè)具體性質(zhì)。4原子公式如果一個(gè)謂詞符號(hào)后面跟著寫在一對(duì)括號(hào)內(nèi)的一個(gè)個(gè)體詞（個(gè)體常項(xiàng)或個(gè)體變項(xiàng)），我們就得到“原子公式”，例如F(a)，G(x)，它們分別表示“a是F”，“x是G”。在派生的意義上，原子公式有兩個(gè)可能的真值：真或者假。5量詞和量化公式量詞包括全稱量詞和存在量詞：x

3、F(x)，讀做“對(duì)于所有x而言，x是F”。xF(x)，讀做“存在x使得x是F”。6原子公式和量化公式還可以用命題聯(lián)結(jié)詞連接起來，形成更復(fù)雜的公式：x(F(x)G(x)xF(x)y H(y)7量詞有其管轄的范圍，簡(jiǎn)稱“轄域”。如果一個(gè)量詞后面有括號(hào)，則處于括號(hào)內(nèi)的公式構(gòu)成該量詞的轄域；如果量詞后面無括號(hào)，則量詞后面最短的公式，構(gòu)成該量詞的轄域。一個(gè)變項(xiàng)的某一次出現(xiàn)，如果處于量詞x或x的轄域之內(nèi)的，或作為與該量詞一起出現(xiàn)的變項(xiàng)（指導(dǎo)變項(xiàng)），則稱該變項(xiàng)的這一次出現(xiàn)是“約束出現(xiàn)”，否則叫做“自由出現(xiàn)”。8一個(gè)變項(xiàng)，如果在一個(gè)公式中有約束出現(xiàn)，則稱它是“約束變項(xiàng)”；如果在一個(gè)公式中有自由出現(xiàn)，則稱它是“

4、自由變項(xiàng)”。因此，一個(gè)體變項(xiàng)在一個(gè)公式中可以既是約束變項(xiàng)又是自由變項(xiàng)。一個(gè)含有至少一個(gè)自由變項(xiàng)的公式，叫做“開公式”。開公式的意義不確定，沒有確定的真假。一個(gè)不含任何自由變項(xiàng)的公式，叫做“閉公式”。在給定論域及其解釋后，閉公式有確定的意義，也有確定的真假。9自然語言中性質(zhì)命題的符號(hào)化在論域?yàn)槿驎r(shí)，六種直言命題可以如下方式符號(hào)化：（1）全稱的直言命題應(yīng)符號(hào)化為一個(gè)全稱蘊(yùn)涵式。SAP：x(S(x)P(x)SEP：x(S(x)P(x)（2）特稱的直言命題應(yīng)符號(hào)化為存在合取式。SIP：x(S(x)P(x)SOP：x(S(x)P(x)（3）單稱的直言命題應(yīng)符號(hào)化為原子公式。 “春江花月夜是一支中國(guó)古代

5、名曲”可以符號(hào)化為：F(a) “周作人不是一位具有民族氣節(jié)的人”可以符號(hào)化為：F(b)10關(guān)系命題包括三個(gè)要素：個(gè)體詞、關(guān)系謂詞和量詞。從形式上看，關(guān)系謂詞與性質(zhì)謂詞沒有實(shí)質(zhì)性區(qū)別，只不過后者涉及一個(gè)個(gè)體，而前者涉及兩個(gè)以上的個(gè)體。發(fā)生在兩個(gè)對(duì)象之間的關(guān)系叫做“二元關(guān)系”，發(fā)生在三個(gè)對(duì)象之間的關(guān)系叫做“三元關(guān)系”，依此類推，發(fā)生在n個(gè)對(duì)象之間的關(guān)系叫做“n元關(guān)系”。11二、關(guān)系謂詞、重疊量化和二元關(guān)系的性質(zhì)一階語言（）初始符號(hào)（i）個(gè)體變項(xiàng)：x，y，z，（ii）個(gè)體常項(xiàng)：a，b，c，（iii）謂詞符號(hào)：F，G，R，S，（iv）量詞：全稱量詞，存在量詞（v）聯(lián)結(jié)詞：，（vi）輔足性符號(hào)：逗號(hào)，左

6、括號(hào)（，右括號(hào)）。12（）形成規(guī)則（i）一個(gè)謂詞符號(hào)F，后面跟有寫在一對(duì)括號(hào)內(nèi)、并用逗點(diǎn)適當(dāng)分開的n個(gè)個(gè)體詞（n1），是原子公式。（ii）如果A是公式，則A是公式。（iii）如果A和B都是公式，則AB，AB，AB，AB是公式。（iv）如果A是公式，則xA，xA是公式。（v）只有按以上方式形成的符號(hào)串是公式。13重疊的量詞和重疊的量化式“重疊量詞”指在一個(gè)量詞的轄域內(nèi)還有另外的量詞。包含重疊量詞的公式就叫做“重疊量化式”。一階語言中允許重復(fù)約束和空約束。14 自然語言中關(guān)系命題的符號(hào)化例如，下面的關(guān)系命題：（1）牛郎不愛有些愛織女的男人。（2）織女愛每一個(gè)愛牛郎的人。（3）有的投票人贊成所有的候

7、選人。分別可以符號(hào)化為：（1）x(M(x)L(x, a)L(b, x)（2）x(P(x)L(x, b)L(a, x)（3）x(T(x)y(H(y)Z(x, y)15一階語言的一個(gè)模型U（亦稱“解釋”）包括下列因素：（）一個(gè)個(gè)體域D，即由具有一定性質(zhì)的個(gè)體所構(gòu)成的集合。當(dāng)給定個(gè)體域之后，全稱量詞x表示個(gè)體域中的所有個(gè)體，存在量詞x表示個(gè)體域中的某些個(gè)體。全稱量詞、存在量詞和約束個(gè)體變項(xiàng)的意義都確定了。（）個(gè)體常項(xiàng)在個(gè)體域D中的值，即個(gè)體常項(xiàng)表示該個(gè)體域中的某個(gè)特定個(gè)體。（）謂詞符號(hào)在個(gè)體域D上的解釋，即表示該個(gè)體域中個(gè)體的性質(zhì)和個(gè)體間的關(guān)系。16三、模型和賦值 普遍有效式當(dāng)給定模型U后，謂詞邏輯

8、的閉公式的意義就確定了，其真假也確定了。但謂詞邏輯的開公式的意義尚不確定，為了確定該公式的真值，需要對(duì)其中的自由變項(xiàng)的值做指派（記為）。在模型U和指派之下，謂詞邏輯的所有公式都有了確定的意義，也有了確定的真假。謂詞邏輯的語言因此得到了確定的解釋。一個(gè)模型U和模型U上的一個(gè)指派合稱為一個(gè)賦值，記為U，。17如果一個(gè)謂詞邏輯的公式對(duì)于任一賦值都為真，則稱該公式為普遍有效式，亦稱常真式。普遍有效式是謂詞邏輯的規(guī)律。如果一個(gè)謂詞邏輯的公式對(duì)于任一賦值都為假，則稱該公式是一個(gè)不可滿足式，亦稱常假式。不可滿足式是謂詞邏輯中的邏輯矛盾。如果一個(gè)謂詞邏輯的公式，對(duì)于有些賦值為真，對(duì)于有些賦值為假，則稱該公式是

9、偶真式，但非普遍有效式。所有的偶真式都是可滿足式。18普遍有效式舉例（1）xF(x)F(y) （2）F(y) xF(x)（3）x(F(x)F(x)（4）x(F(x)F(x)19（5）xF(x) xF(x)（6）xF(x) xF(x)（7）x(F(x) G(x)(xF(x) xG(x)（8）x(F(x)G(x)(xF(x)xG(x)（9）x(F(x)G(x)( xF(x)xG(x)（10）xyR(x, y)yx R(x, y)20謂詞邏輯的樹形圖是命題邏輯樹形圖的擴(kuò)充，命題邏輯原有的關(guān)于聯(lián)結(jié)詞的九個(gè)畫圖規(guī)則仍然有效；但需要增加關(guān)于全稱量詞x和存在量詞x的四個(gè)畫圖規(guī)則：21四、普遍有效式的判定問題

10、222324謂詞邏輯是不可判定的即是說，不存在一種機(jī)械的、能行的辦法，它適合于任一的謂詞邏輯公式，將在有窮步內(nèi)結(jié)束，并且就該公式是不是普遍有效式給出唯一確定的結(jié)果。不過，某些特殊類型的謂詞邏輯公式，例如一元謂詞邏輯公式，其普遍有效性是可判定的。在這個(gè)意義上，謂詞邏輯是半可判定的。25證明非普遍有效性或可滿足性的方法要證明這樣的一個(gè)公式不普遍有效，或者是可滿足的，前者是要為該公式找一反模型，使得該公式在其中為假；后者是要為該公式找一模型，使得該公式在其中為真。這種方法叫做“解釋方法”或“模型方法”。26（一）QN推理規(guī)則謂詞邏輯自然推理QN是命題邏輯自然推理PN的擴(kuò)充，所有PN的規(guī)則都是QN的規(guī)

11、則；所有已經(jīng)證明的PN定理和導(dǎo)出規(guī)則，都是QN的定理和導(dǎo)出規(guī)則，故在證明或推演中可以直接使用它們，無需另外證明。在PN的基礎(chǔ)上，QN增加了四條與量詞有關(guān)的規(guī)則：27五、謂詞邏輯自然推理系統(tǒng)QN1全稱量詞消去規(guī)則，記為規(guī)則：從xA(x)推出A(x/t)，其中代換x的t不會(huì)被A中原有的量詞所約束。282全稱量詞引入規(guī)則，記為規(guī)則：從A(x)推出xA(x)，只要能夠確保前提中的自由變項(xiàng)x是任意的。29若不能確保前提中的自由變項(xiàng)x是任意的，就要給該x加標(biāo)記，其具體做法是：在一個(gè)證明或推演的某一步上，出現(xiàn)了含自由變項(xiàng)x的公式A，且不能保證其中的x是任意的，則在該公式的右邊注明該公式來歷的位置，寫上x，表

12、示該x可能不是任意的，不能對(duì)它使用規(guī)則。以下三種情形需要給相應(yīng)的自由變項(xiàng)加標(biāo)記：（i）給定前提中的自由變項(xiàng)；（ii）根據(jù)假設(shè)引入規(guī)則所引入的假設(shè)中的自由變項(xiàng)；（iii）一個(gè)在前提或假設(shè)中是自由的變項(xiàng)，在從該前提或假設(shè)出發(fā)，根據(jù)QN的推演規(guī)則所得到的任意一行中也出現(xiàn)，那么，它在后面這些行的出現(xiàn)也應(yīng)加標(biāo)記。303存在量詞消去規(guī)則，記為規(guī)則：從xA(x)可以推出A()，這里要求（i）是先前沒有出現(xiàn)過的特指常項(xiàng)；（ii）如果公式A含有x之外的自由變項(xiàng)y，應(yīng)該用該y給特指常項(xiàng)做下標(biāo)，寫成y。314存在量詞引入規(guī)則，記為規(guī)則：從A(x/t)可以推出xA(x)，只要代換x的t不會(huì)被A原有的量詞所約束，或者新

13、引入的存在量詞不會(huì)將A(x)中除x之外的其他自由變項(xiàng)一并加以約束。32量詞規(guī)則總結(jié)全稱量詞消去規(guī)則：從xA(x)推出A(x/t)，其中代換x的t不會(huì)被A中原有的量詞所約束，這包括以下情形：（1）t是一個(gè)個(gè)體常項(xiàng)；（2）A是一個(gè)原子公式，x是其中的自由變項(xiàng)，t是任一個(gè)體詞；（3）A含有量詞，但自由變項(xiàng)x不在這些量詞的轄域之內(nèi)，t是任一個(gè)體詞；（4）A含有量詞，且自由變項(xiàng)x在這些量詞的轄域之內(nèi)，則t必須是與已量化變項(xiàng)不同的變項(xiàng)。否則，稱為t對(duì)于公式A中的自由變項(xiàng)x代入不自由。33全稱量詞引入規(guī)則：從A(x)推出xA(x)，只要能夠確保前提中的自由變項(xiàng)x是任意的。以下情況下的自由變項(xiàng)不能確保是任意的

14、，被稱為“加標(biāo)記變項(xiàng)”：（i）給定前提中的自由變項(xiàng)；（ii）根據(jù)假設(shè)引入規(guī)則所引入的假設(shè)中的自由變項(xiàng)；（iii）從該前提或假設(shè)出發(fā)，根據(jù)QN的推演規(guī)則所得到的的那些行中、與前提或假設(shè)中的自由變項(xiàng)相同的自由變項(xiàng)；（iv）給特指常項(xiàng)做下標(biāo)的自由變項(xiàng)。對(duì)加標(biāo)記變項(xiàng)，規(guī)則不適用。34存在量詞消去規(guī)則：從xA(x)可以推出A()，這里要求（i）是先前沒有出現(xiàn)過的特指常項(xiàng)；（ii）如果公式A含有x之外的自由變項(xiàng)y，應(yīng)該用該y給特指常項(xiàng)做下標(biāo)，寫成y。存在量詞引入規(guī)則：從A(x/t)可以推出xA(x)，其中代換x的t不會(huì)被A中原有的量詞所約束，或者新引入的存在量詞不會(huì)將A中除x之外的其他自由變項(xiàng)一并加以約束。35（二）QN有前提推演3637 （三）QN定理及其證明1xA(x)xA(x)2xA(x)xA(x)3xA(x)xA(x) 4xA(x)xA(x)5AxA，若x不在A中自由出現(xiàn)6AxA，若x不在A中自由出現(xiàn)7A(x/t)x A(x)，若t對(duì)于x代入自由8xA(x)xA(x)3839第二組9x(A(x)B(x)xA(x)xB(x)10 x(A(x)B(x)xA(x)xB(x)11x(AB(x)AxB(x)，若x不在A中自由出現(xiàn)12x(AB(x)AxB(x)，若x不在A中自由出現(xiàn)13x(AB(x)AxB(x)，若x不在A中自由出現(xiàn)14x(AB(x