【正文】 91/73 ：命題演算的自然推理形式系統(tǒng) ? P 1)字母表： (1)命題符： p， q， r， … ， p1， q1， r1， … (2)聯(lián)結(jié)詞符： 172。 90/73 ：命題演算的自然推理形式系統(tǒng) ?對于一個形式系統(tǒng)， Axiom和 Rule均可以為空，當(dāng)兩者皆為空時，系統(tǒng)僅僅為一個語句生成系統(tǒng)，在數(shù)理邏輯中，如果 Axiom非空，則稱為公理系統(tǒng)，若 Axiom為空，則稱為自然推理系統(tǒng)。 在形式系統(tǒng)中，用符號語言來表達原始概念和用于推演的邏輯規(guī)則，決定一切的是符號串和符號串之間的關(guān)系，合法符號串的識別，系統(tǒng)內(nèi)的推演都可以根據(jù)合法符號串而形成規(guī)則和推理規(guī)則 (符號串之間的關(guān)系 )機械的完成；只有這樣的系統(tǒng)，才是本質(zhì)上能做符號變換的計算機可以接受的。 87/73 ：命題邏輯的推理理論 ?例 ： 證明： p →(q ∨ r)|=(p →q) ∨ (p →r) ?例 ： 證明下面論述的有效性：在意甲比賽中，假如有四只球隊，其比賽情況如下：如果國際米蘭奪冠，則 AC米蘭或尤文圖斯獲亞軍；若尤文圖斯獲亞軍，國際米蘭隊不能獲得冠軍，若拉齊奧隊獲得亞軍，則 AC米蘭隊不能獲得亞軍；最后，國際米蘭奪冠。H}出發(fā)，可以邏輯推出一個矛盾式來。如對任意的解釋 I，都有 G1∧ G2∧ … ∧ Gn取值為“假”，則稱公式 G1， G2， … ， Gn是不一致的(Inconsistency),或者說 G1∧ G2∧ … ∧ Gn是一個矛盾式。R ∨ P， Q},公式 G=R →S，證明 T|=G。所以， A若參加球賽，則 D不參加球賽。如果 B參加球賽，則 A不參加球賽。 附加前提證明法 (CP規(guī)則 ) 若 P1， P2， … ， Pn ， P|= Q，則 P1， P2， … ， Pn |= P→Q 附加前提證明法的意義在于：當(dāng)推理的結(jié)論是蘊含式時，可以將其前件作為附加前提引用，只要能推理出其后件，則原推理成立。 如果我考試通過了，那么我很快樂；如果我快樂，那么陽光燦爛；現(xiàn)在是晚上 11點，天很暗?！睂懗銮疤岷陀行ЫY(jié)論并證明之。s →r， 172。C) ⑿ 合取引入規(guī)則： A， B|=(A∧ B) 83/73 ：命題邏輯的推理理論 ?例 ： 構(gòu)造下列推理的證明： 前提： p ∨ q， p →172。D) |=(172。B|=A ⑽ 構(gòu)造性二難規(guī)則： (A→B)， (C→D)， (A∨ C) |=(B∨ D) ⑾ 破壞性二難規(guī)則： (A→B)， (C→D)， (172。B|=172。A∨ 172。B∨ 172。A→B)∧ (A∨ 172。A 拒取式 5.(A?B) ∧ 172。 81/73 ：命題邏輯的推理理論 (2)推理定理： (一些重要的永真蘊含式 ) =(A∨ B) 附加律 ∧ B=A 化簡律 3.(A→B) ∧ A =B 假言真理 4 .(A→B) ∧ 172。 80/73 ：命題邏輯的推理理論 ? ：構(gòu)造證明法 構(gòu)造證明法是依據(jù)一些公認的推理規(guī)則，從前提出發(fā)，推導(dǎo)結(jié)論，它可以看作公式的序列，其中每個公式都是按照事先規(guī)定的規(guī)則得到的，且可將所用的規(guī)則在公式后寫明，該系列最后一個公式是所要證明的結(jié)論。所以，若王小燕沒去看電影，下午氣溫超過了 30 ℃ 。 ?例 ： 若下午氣溫超過 30℃ ，則王小燕必去游泳。所以，她去游泳了。 ?例 ： 下午馬芳或去看電影或去游泳。 G1： 172。 G1： P→Q ， G2： 172。 G1： P， G2： P→Q； (2). H： 172。 78/73 ：命題邏輯的推理理論 ?例 ： 判斷下列 H是否為前提 G1， G2的邏輯結(jié)果。 ?：判斷結(jié)論有效的方法 ； ； 77/73 ：命題邏輯的推理理論 設(shè) P1， P2， … ， Pn是出現(xiàn)在前提 G1， G2， … ，Gn和結(jié)論 H中的一切命題變元，如果將 P1，P2， … ， Pn中所有可能的解釋及 G1， G2， … ，Gn， H的對應(yīng)真值結(jié)果都在一個表中，根據(jù)“ →”的定義，則有如下判斷方法： (1)對所有 G1， G2， … ， Gn都具有真值 T的行 (表示前提為真的行 )，如果在每個這樣的行中， H也具有真值 T，則 H是 G1， G2， … ， Gn的邏輯結(jié)果； (2)對所有 H具有真值為 F的行 (表示結(jié)論為假的行 )，如果在每一個這樣的行中， G1， G2， … ， Gn中至少有一個公式的真值為 F(前提也為假 )。 因此我們可以用蘊含式來描述推理。 75/73 ：命題邏輯的推理理論 ?定理 ： 命題公式 G1， G2， … ， Gn推出結(jié)論 H的推理正確或公式 H是前提條件 {G1， G2， … ， Gn}的邏輯結(jié)果，當(dāng)且僅當(dāng) (G1∧ G2∧ …Gn) →H 為重言式。 G1， G2， … ，Gn仍為一組前提 (Premise)。 74/73 ：命題邏輯的推理理論 ?：推理的基本概念和推理形式 推理也稱論證，它是指從前提出發(fā)推出結(jié)論的思維過程，而前提是已知命題公式集合，結(jié)論是從前提出發(fā)應(yīng)用推理規(guī)則推出的命題形式。R),求其對應(yīng)的主析取范式和主合取范式 ?性質(zhì)： (1)：如果命題公式是永真公式 =它的主析取范式包含所有極小項，此時主合取范式不含有任何極大項，為空，記 1或 T (2)：如果命題公式是永假公式 =它的主合取范式包含所有極大項，此時主析取范式不含有任何極小項，為空，記 0或 F (3)：兩個命題公式 A， B， A=B當(dāng)且僅當(dāng) A與 B有相同的真值表，又當(dāng)且僅當(dāng) A與 B有相同的主析取范式 (主合取范式 )。P∧ R)∨ (172。其中 后剩下的極大項。G)即是 G的主析取范式， 即，若 為 G的主合取范式，則 為 172。G 的主合取范式，即 G的主合取范式中沒有出現(xiàn)過的極大項的合取 b： G=172。則 為 G的主合取范式。G)即是 G的主合取范式 即：若 為 G的主析取范式，則 為 172。G 的主析取范式，即 G的主析取范式中沒有出現(xiàn)過的極小項的析取 b： G=172。下面介紹一種兩者之間的轉(zhuǎn)換方法。當(dāng)命題變元較多時，一般采用公式轉(zhuǎn)換法，而在公式轉(zhuǎn)換中，有時求主析取范式更為方便，而有時求主合取范式更為方便。 69/73 ：范式 [公式轉(zhuǎn)換法 ] 唯一性： 設(shè)任一命題公式 A有兩個主析取范式 B和 C，則因為 A=B， A=C，所以 B=C，若 B， C是 A的(在不計極小項的順序的情況下 )不同的主析取范式，則必有在存在極小項 mi， mi只存在于 B， C之一中，不妨設(shè) mi在 B中 ,而不在 C中，因此 i之二進制表示 B的一個真值解釋，而對于 C則為真值為假的解釋，這與 B=C矛盾，所以 B和 C相同，同理主合取范式也是唯一的。 ?例 ： 求命題公式 (P→Q)?R的主合取范式。極大項的否定是極小項，極小項的否定是極大項，即 (4)：所有極小項的析取為永真公式，所有極大項的合取是永假公式，即 iiiinjijimMMmjijiFmmTMM???????????，；， ])12,0[,.(0 1 12 012 0 ???? ???? iiii Mm nn ，67/73 ：范式 ? ?定理 ： 任何命題公式的主析取范式和主合取范式存在且唯一，即任何命題公式都有且僅有一個與之等價的主合取范式和主析取范式。Q∨ 172。Q∨ R 1 1 1 m7= P∧ Q∧ R M7= 172。R M6= 172。P∨ Q∨ 172。P∨ Q∨ R 1 0 1 m5= P∧ 172。Q∧ 172。Q∨ 172。Q∨ R 0 1 1 m3= 172。P∧ Q∧ 172。Q∧ R M1= P∨ Q∨ 172。R M0= P∨ Q∨ R 0 0 1 m1= 172。P∧ 172。R只有在 P， Q， R分別取真值 1， 1， 1時才為假，所以有時又可用 來表示。P ∨ 172。 (2)：沒有兩個不同的極大項是等價的，且每個極大項只有一組真值指派，使該極大項的真值為假。P ∧ Q∧ 172。Q ∧ 172。Q P∨ Q 0 0 0 0 0 1 1 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 0 0 1 0 1 0 1 1 1 1 1 0 0 0 0 1 1 1 n2n264/73 ：范式 ?性質(zhì)： (1)：沒有兩個不同的極小項是等價的，且每個極小項只有一組真值指派使該極小項的真值為真，因此可給極小項編碼，使極小項為“ T”和那組真值指派為對應(yīng)的極小項編碼；如極小項 172。Q 172。Q 172。Q 172。 P Q P∧ Q 172。Q 。Q ， 172。Q ； P∨ Q， 172。Q ，172。 63/73 ：范式 ? 對于兩個命題變元 P， Q來說，由于每個 P， Q可以取命題變元自身和其否定，所以其對應(yīng)的極小項和極大項分別有四項： P∧ Q， 172。Q)∨ (Q∧ R)，P∨ (P∧ R)∨ (Q∧ R),等，這種不唯一的表達形式給研究問題帶來了不便，因此有必要引進更為標(biāo)準(zhǔn)的范式。 62/73 ：范式 ?：主析取范式和主合取范式 范式雖然為命題公式提供了一種統(tǒng)一的表達形式，但這種表達形式卻并不是唯一的。 ?例 ： 求公式 (P∧ 172。P∨ Q)； ?性質(zhì)： (1)：一個文字既是一個析取范式又是一個合取范式； (2)：一個析取范式為矛盾式，當(dāng)且僅當(dāng)它的每個簡單合取式是矛盾式； (3)一個合取范式為重言式，當(dāng)且僅當(dāng)它的每個簡單析取式是重言式。P ∧ Q∧ R；④： (P∧ Q)∨ (172。P ；②： P∨ Q∨ 172。 59/73 ：范式 ?定義 ： (1)：命題變元或命題變元的否定稱為文字； (2)：有限個文字的析取式稱為簡單析取式 (基本和 )，有限個文字的合取式稱為簡單合取式 (基本積 )；