數(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ù)邏輯演算問題都與邏輯蘊涵的判斷有關?？梢杂孟旅娴氖聦嵳f明這一點。 1) ? ? ? 永真 當且僅當 ? ? ? 2) ? ? ?永真 當且僅當 ? ?

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

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

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

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

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

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

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

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

10、所引入的命題公式比上一行的命題公式后移幾格，并在說明部分的規(guī)則H之后注明啟發(fā)該假設的規(guī)則名稱。 例如，說明部分為“H(?+)”表示該假設是由間接規(guī)則?+所啟發(fā)的。 當消去一個假設時，則將所引入的命題公式與該假設引入前的命題公式對齊。前提的引入不需要考慮消去問題，因此只需與上一行的命題公式對齊，并在說明部分寫上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) 蘊涵消去規(guī)則，記為?_ , 其形式為 (i) ? , (j) ? ? ? ┝ (k) ? ?_(i)(j) 5) 等價引入規(guī)則，記為?+ , 其形式為 (i) ??? , (j) ???┝ (k) ??? ?+ (i) (j) 6) 等價消去規(guī)則，記為?_

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

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

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

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

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

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

20、 事實上 (? ? ?)?? ? ? (? ? ?) ? ? ? (?? ? ??) ? ? ? ??(???)　于是有 (? ? ?)?? 永真當且

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

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

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

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

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