數(shù)理邏輯1.5-(2)

1、1.5 命題演算的形式推理,1.5.1　形式推理的一般概念 1.5.2　命題演算的自然推理系統(tǒng) 1.5.3　形式推理證明舉例,1.5.1　形式推理的一般概念,通過前幾節(jié)的介紹，不難發(fā)現(xiàn)大多數(shù)邏輯演算問題都與邏輯蘊(yùn)涵的判斷有關(guān)?？梢杂孟旅娴氖聦?shí)說明這一點(diǎn)。 1) ? ? ? 永真 當(dāng)且僅當(dāng) ? ? ? 2) ? ? ?永真 當(dāng)且僅當(dāng) ? ?

2、 ? 3) ? ? ? 當(dāng)且僅當(dāng) ? ? ? 且 ? ? ? 因此，研究 ? ? ? 便成為邏輯演算的核心問題之一。 目前，在數(shù)理邏輯中，研究形式推理主要有兩種方式， 一種是以規(guī)則為主的自然推理方法。這種方法主要以應(yīng)用為背景。因此，自然推理比較接近人們的直觀，一般人容易接受。 一種是公理系統(tǒng)的方法。公理系統(tǒng)方法理論性較強(qiáng)，適用于從事數(shù)理邏輯專門研究的理論工作者。 下面我們討論自

3、然推理的方法。因此，以下提到的形式推理均指自然推理。,自然推理系統(tǒng)的主要特點(diǎn)是：允許直接引入前提或假設(shè)，然后應(yīng)用一些給定的推理規(guī)則，逐步引出一系列命題公式，直到所要證的命題公式(結(jié)論)被引出。 設(shè) ?1,?2,…,?n, ? 是命題公式。如果在?1,?2,…,?n的假設(shè)下，根據(jù)一些給定的推理規(guī)則(直接的或間接的)，可以構(gòu)造出一個(gè)命題公式序列?1, ?2,…,?m直到?引出，則稱此命題公式序列為在前提?1,?2,…,?n下關(guān)

4、于結(jié)論?的一個(gè)證明?1,?2,…,?n |= ? (*) 有時(shí)為了方便將前提集用?表示，即 ? = {?1, ?2, …, ?n}。 關(guān)于(*)的邏輯關(guān)系，可以用下式解釋：?1??2?…??n ? ?,在自然推理系統(tǒng)中，推理規(guī)則主要包括兩大類，一類為直接推理規(guī)則，另一類為間接推理規(guī)則或稱為假設(shè)消去規(guī)則。 一般來說，直接推理規(guī)則具有下述形式?1,?2,…,?n┝ ? 意指：若

5、在推理過程中 ?1,?2,…,?n 已經(jīng)引出，則根據(jù)此規(guī)則可引出? 。 如果用命題公式之間的邏輯關(guān)系來說明，那么此規(guī)則的含義可理解為?1 ? ?2 ? … ? ?n ? ? 例如“ ? , ???┝ ? ”意為在推理過程中，若?及???已經(jīng)引出，那么便可直接引出? 。此規(guī)則所表示的邏輯關(guān)系是： ??(???) ? ? 。 當(dāng)然，在以后的形式推理過程中，不進(jìn)行后者的解釋。,一般來說，間接推理規(guī)則上有下

6、述形式“若 ?，? |= ? ，則 ?┝ ? ” 意指：若在前提集?下，利用新的假設(shè)(額外假設(shè))?能夠證明?，則可消去假設(shè)?而直接引出? 。然而在增加了假設(shè)?之下引出的諸命題公式直到?在以后的證明過程中不允許再引用。 例如，“若?，? |= ? ，則 ?┝ ??? ?！?意為：若在增加了假設(shè)?之下能夠證明?，則可消去假設(shè)?而直接引入 ??? 。 由于間接規(guī)則的應(yīng)用，若將諸前提?i

7、也看成是額外假設(shè)，可能導(dǎo)致具有下述形式的證明：|= ?這時(shí)稱?為可證命題公式。 如果用真假性來解釋，可證命題公式即為永真命題公式。這條性質(zhì)通常稱為可靠性。,1.5.2　命題演算的自然推理系統(tǒng),自然推理系統(tǒng)的證明是按行進(jìn)行的，而且每行只能寫一個(gè)命題公式。其一般格式如下　　　　　　　 1) 標(biāo)號(hào)部分給出證明的步驟，而且是從第一步開始，逐步增加。如第i步寫成 (i) 等。 2) 命題公式為在本章中所定義的命題公式

8、。其中不能帶有命題公式定義以外的字符，如逗號(hào)等是不允許的。 3) 說明部分是指出引入該命題公式的根據(jù)。一般來說，總是給出規(guī)則名及某些輔助說明，以便驗(yàn)證。關(guān)于這一點(diǎn)，在下面給出規(guī)則時(shí)再作具體的說明。 對(duì)于一行中各部分的位置做如下約定：標(biāo)號(hào)部分及說明部分各行之間應(yīng)對(duì)齊，即下一行的相應(yīng)部分的第一個(gè)字符與上一行應(yīng)對(duì)齊。命題公式部分除規(guī)則中有其它約定外，也應(yīng)對(duì)齊。同時(shí)一行各部分之間也應(yīng)留有適當(dāng)?shù)目瘴?，尤其是在命題公式與說

9、明部分之間。,一、直接引入規(guī)則 1) 前提引入規(guī)則，記為P。 可根據(jù)需要隨時(shí)引入一個(gè)前提。 2) 假設(shè)引入規(guī)則，記為H。 可根據(jù)需要隨時(shí)引入一個(gè)假設(shè)。 盡管前提與假設(shè)均可隨時(shí)引入，但前提的引入是無后果的，而假設(shè)的引入最終必須用間接規(guī)則消去。事實(shí)上，假設(shè)的引入往往是由某個(gè)間接規(guī)則所啟發(fā)的。因此，為了明確假設(shè)最終由哪個(gè)間接規(guī)則消去，并使證明過程清晰自然，容易判斷，我們約定：在每次引入一個(gè)假設(shè)時(shí)，應(yīng)將

10、所引入的命題公式比上一行的命題公式后移幾格，并在說明部分的規(guī)則H之后注明啟發(fā)該假設(shè)的規(guī)則名稱。 例如，說明部分為“H(?+)”表示該假設(shè)是由間接規(guī)則?+所啟發(fā)的。 當(dāng)消去一個(gè)假設(shè)時(shí)，則將所引入的命題公式與該假設(shè)引入前的命題公式對(duì)齊。前提的引入不需要考慮消去問題，因此只需與上一行的命題公式對(duì)齊，并在說明部分寫上P即可。,二、直接推理規(guī)則 1) 合取引入規(guī)則，記為?+,, 其形式為

11、 (i) ? , (j) ? ┝ (k) ? ? ? ?+(i)(j) 2) 合取消去規(guī)則，記為?_ , 其形式為 (i) ? ? ? ┝ (j) ? ?_ (i) (i) ? ? ? ┝ (k) ?

12、 ?_ (i) 3) 析取引入規(guī)則，記為?+ , 其形式為 (i) ? ┝ (k) ? ? ? ?+ (i) (j) ? ┝ (k) ? ? ? ?+ (j)

13、 4) 蘊(yùn)涵消去規(guī)則，記為?_ , 其形式為 (i) ? , (j) ? ? ? ┝ (k) ? ?_(i)(j) 5) 等價(jià)引入規(guī)則，記為?+ , 其形式為 (i) ??? , (j) ???┝ (k) ??? ?+ (i) (j) 6) 等價(jià)消去規(guī)則，記為?_

14、, 其形式為 (i) ???┝ (j) ??? ?_ (i) (i) ???┝ (k) ??? ?_ (i),三、間接推理規(guī)則 1) 否定引入規(guī)則，記為?+ , 其形式為 若? , (i) ? |= (j) ? ， (k)

15、 ? ? ， 則 ?┝ (l) ?? ?+ (j)(k) | (i) 注意：在引入假設(shè)?時(shí)，說明部分應(yīng)寫成H(?+ )。 2) 否定消去規(guī)則，記為?_ , 其形式為 若? , (i)?? |= (j) ? ， (k) ? ? ， 則 ?┝ (l) ?

16、 ?_ (j)(k) | (i) 注意：在引入假設(shè)??時(shí)，說明部分應(yīng)寫成H(?_)。 3) 析取消去規(guī)則，記為?_ , 其形式為 若 ? |= (i) ? ? ? , 且 (j) ? |= (l) ? , 且 (k) ? |= (m) ? , 則 ? ┝ (n) ? ?_(i)(l)(m)

17、 | (j)(k) 注意：第j行與第k行的說明部分均應(yīng)寫成H(?_)。4) 蘊(yùn)涵引入規(guī)則，記為?+ , 其形式為 若 ? , (i)? |= (j)?， 則 ?┝ (k) ??? ?+ (j) | (i) 注意：第i行的說明部分應(yīng)寫成H(?+)。,關(guān)于規(guī)則的使用說明 1. 關(guān)于假設(shè)消去的順序問題，為了保證各間接推

18、理規(guī)則的正常使用，規(guī)定：當(dāng)有多個(gè)假設(shè)時(shí)，消去的順序必須從最后一個(gè)假設(shè)開始消去。 2. 關(guān)于證明的終止問題。一個(gè)證明已終止；當(dāng)且僅當(dāng)所有的假設(shè)被消去，且結(jié)論命題公式已經(jīng)引出。如果用證明的格式判斷：當(dāng)?shù)谝恍惺乔疤釙r(shí)，終止的結(jié)論命題公式應(yīng)與第一行命題公式對(duì)齊；當(dāng)?shù)谝恍惺羌僭O(shè)時(shí)，終止的結(jié)論命題公式應(yīng)比第一行命題公式前移幾格。 3. 關(guān)于推理規(guī)則的可靠性問題。前面曾給出可靠性的一種說法。與之等價(jià)的另一種說法是：若前提均為永真命

19、題公式，則應(yīng)用諸推理規(guī)則所得到的命題公式均為永真命題公式。 利用這種說法，很容易判斷前提引入規(guī)則及各條直接推理規(guī)則的可靠性。由于假設(shè)引入規(guī)則本身不是獨(dú)立的，因此它的可靠性應(yīng)與間接推理規(guī)則放在一起來說明。,下面僅以蘊(yùn)涵引入規(guī)則為例加以說明，其它兩條間接推理規(guī)則的說明由留作課后習(xí)題。 設(shè) ? = ?1??2?…??n，于是按照前面關(guān)于推理規(guī)則所表示邏輯關(guān)系，蘊(yùn)涵引入規(guī)則是指若 ? ? ? ? ? ，則 ? ? ???

20、 事實(shí)上 (? ? ?)?? ? ? (? ? ?) ? ? ? (?? ? ??) ? ? ? ??(???)　于是有 (? ? ?)?? 永真當(dāng)且

21、僅當(dāng) ??(???) 永真。 因此，如果已證明出 ? ? ? ? ? ，即 (? ? ?)?? 永真，則有??(???) 永真，即 ? ? ??? 。 故當(dāng)?為永真命題公式時(shí)，則???必為永真命題公式。這就說明蘊(yùn)涵引入規(guī)則是可靠的。,1.5.3　形式推理證明舉例,例1 |= ??? ? ?例2 ??? |= ???????例3 ??(???) |= ??(???)例4 ?(???) |= ?????例5

22、 ????? |= ?(???)例6 ??? |= ????例7 ??? |= ????例8 ?(???) |= ????,例1　如果天氣晴朗，并且沒有考試，則他們就外出郊游；結(jié)果他們并沒有外出郊游，而且也沒有考試。所以，天氣不好。 解　命題符號(hào)化后的形式為(P??Q) ? R , ?R??Q |= ?P其中 P: 天氣晴朗。Q: 他們考試。R: 他們外出郊游。　例2　如果下雨，則交通困難；如果他們準(zhǔn)點(diǎn)到達(dá)

23、，則交通不困難。所以，如果他們準(zhǔn)點(diǎn)到達(dá)，則沒有下雨。 解　命題符號(hào)化的形式為P ? Q , R ? ?Q |= R ? ?P其中 P: 天下雨。Q: 交通困難。R: 他們準(zhǔn)點(diǎn)到達(dá)。,例3　如果小張缺席，那么不是小李就是小王缺席；如果小李缺席，則小張就不會(huì)缺席；如果小趙缺席，則小王不會(huì)缺席。所以，如果小張缺席，則小趙不會(huì)缺席。 解　命題符號(hào)化的形式為A ? (B?C) , B ? ?A , D ? ?C |= A ?

24、 ?D其中 A: 小張缺席，B: 小李缺席，C: 小王缺席，D: 小趙缺席。 例4　若他競(jìng)技狀態(tài)不好，他就不會(huì)取得好成績；若他競(jìng)技狀態(tài)良好，他就會(huì)獲得金牌；他要么取得好成績，要么不參加這次比賽。所以，他如果參加比賽，就會(huì)獲得金牌。 解　命題符號(hào)化的形式為 ?P ? ?Q , P ? R , Q ? ?S |= S ? R 其中 P: 他競(jìng)技狀態(tài)良好。 Q: 他取得好

25、成績。 R: 他獲得金牌。 S: 他參加比賽。,作為本節(jié)的結(jié)束，下面對(duì)如何評(píng)價(jià)一個(gè)形式推理系統(tǒng)做一點(diǎn)說明，以便對(duì)一般的形式推理系統(tǒng)有一個(gè)比較全面的了解。 對(duì)于給定的一個(gè)形式推理系統(tǒng)，一般說可以從三個(gè)方面來進(jìn)行評(píng)價(jià)，即可靠性、完備性、獨(dú)立性。 關(guān)于可靠性，在前面已做了說明，這里不再重復(fù)。 其次是完備性。就自然推理系統(tǒng)而言，完備性是指命題演算中的所有永真命題公式均為