【正文】 1或 T (2)：如果命題公式是永假公式 =它的主合取范式包含所有極大項，此時主析取范式不含有任何極小項，為空，記 0或 F (3)：兩個命題公式 A， B， A=B當(dāng)且僅當(dāng) A與 B有相同的真值表，又當(dāng)且僅當(dāng) A與 B有相同的主析取范式 (主合取范式 )。 G1， G2， … ，Gn仍為一組前提 (Premise)。 因此我們可以用蘊含式來描述推理。 78/73 ：命題邏輯的推理理論 ?例 ： 判斷下列 H是否為前提 G1， G2的邏輯結(jié)果。 G1： P→Q ， G2： 172。 ?例 ： 下午馬芳或去看電影或去游泳。 ?例 ： 若下午氣溫超過 30℃ ，則王小燕必去游泳。 80/73 ：命題邏輯的推理理論 ? ：構(gòu)造證明法 構(gòu)造證明法是依據(jù)一些公認(rèn)的推理規(guī)則，從前提出發(fā)，推導(dǎo)結(jié)論，它可以看作公式的序列，其中每個公式都是按照事先規(guī)定的規(guī)則得到的，且可將所用的規(guī)則在公式后寫明，該系列最后一個公式是所要證明的結(jié)論。A 拒取式 5.(A?B) ∧ 172。B∨ 172。B|=172。D) |=(172。s →r， 172。 如果我考試通過了，那么我很快樂；如果我快樂，那么陽光燦爛；現(xiàn)在是晚上 11點，天很暗。如果 B參加球賽，則 A不參加球賽。R ∨ P， Q},公式 G=R →S，證明 T|=G。H}出發(fā)，可以邏輯推出一個矛盾式來。 在形式系統(tǒng)中，用符號語言來表達(dá)原始概念和用于推演的邏輯規(guī)則，決定一切的是符號串和符號串之間的關(guān)系，合法符號串的識別，系統(tǒng)內(nèi)的推演都可以根據(jù)合法符號串而形成規(guī)則和推理規(guī)則 (符號串之間的關(guān)系 )機(jī)械的完成；只有這樣的系統(tǒng)，才是本質(zhì)上能做符號變換的計算機(jī)可以接受的。 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)。 87/73 ：命題邏輯的推理理論 ?例 ： 證明： p →(q ∨ r)|=(p →q) ∨ (p →r) ?例 ： 證明下面論述的有效性：在意甲比賽中，假如有四只球隊，其比賽情況如下：如果國際米蘭奪冠，則 AC米蘭或尤文圖斯獲亞軍；若尤文圖斯獲亞軍，國際米蘭隊不能獲得冠軍，若拉齊奧隊獲得亞軍，則 AC米蘭隊不能獲得亞軍；最后，國際米蘭奪冠。如對任意的解釋 I，都有 G1∧ G2∧ … ∧ Gn取值為“假”，則稱公式 G1， G2， … ， Gn是不一致的(Inconsistency),或者說 G1∧ G2∧ … ∧ Gn是一個矛盾式。所以， A若參加球賽，則 D不參加球賽。 附加前提證明法 (CP規(guī)則 ) 若 P1， P2， … ， Pn ， P|= Q，則 P1， P2， … ， Pn |= P→Q 附加前提證明法的意義在于：當(dāng)推理的結(jié)論是蘊含式時，可以將其前件作為附加前提引用，只要能推理出其后件，則原推理成立?！睂懗銮疤岷陀行ЫY(jié)論并證明之。C) ⑿ 合取引入規(guī)則： A， B|=(A∧ B) 83/73 ：命題邏輯的推理理論 ?例 ： 構(gòu)造下列推理的證明： 前提： p ∨ q， p →172。B|=A ⑽ 構(gòu)造性二難規(guī)則： (A→B)， (C→D)， (A∨ C) |=(B∨ D) ⑾ 破壞性二難規(guī)則： (A→B)， (C→D)， (172。A∨ 172。A→B)∧ (A∨ 172。 81/73 ：命題邏輯的推理理論 (2)推理定理： (一些重要的永真蘊含式 ) =(A∨ B) 附加律 ∧ B=A 化簡律 3.(A→B) ∧ A =B 假言真理 4 .(A→B) ∧ 172。所以，若王小燕沒去看電影，下午氣溫超過了 30 ℃ 。所以，她去游泳了。 G1： 172。 G1： P， G2： P→Q； (2). H： 172。 ?：判斷結(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 為重言式。 74/73 ：命題邏輯的推理理論 ?：推理的基本概念和推理形式 推理也稱論證，它是指從前提出發(fā)推出結(jié)論的思維過程，而前提是已知命題公式集合，結(jié)論是從前提出發(fā)應(yīng)用推理規(guī)則推出的命題形式。P∧ R)∨ (172。G)即是 G的主析取范式， 即，若 為 G的主合取范式，則 為 172。則 為 G的主合取范式。G 的主析取范式，即 G的主析取范式中沒有出現(xiàn)過的極小項的析取 b： G=172。當(dāng)命題變元較多時，一般采用公式轉(zhuǎn)換法，而在公式轉(zhuǎn)換中，有時求主析取范式更為方便，而有時求主合取范式更為方便。 ?例 ： 求命題公式 (P→Q)?R的主合取范式。Q∨ 172。R M6= 172。P∨ Q∨ R 1 0 1 m5= P∧ 172。Q∨ 172。P∧ Q∧ 172。R M0= P∨ Q∨ R 0 0 1 m1= 172。R只有在 P， Q， R分別取真值 1， 1， 1時才為假，所以有時又可用 來表示。 (2)：沒有兩個不同的極大項是等價的，且每個極大項只有一組真值指派，使該極大項的真值為假。Q ∧ 172。Q 172。Q 172。Q 。Q ； P∨ Q， 172。 63/73 ：范式 ? 對于兩個命題變元 P， Q來說，由于每個 P， Q可以取命題變元自身和其否定，所以其對應(yīng)的極小項和極大項分別有四項： P∧ Q， 172。 62/73 ：范式 ?：主析取范式和主合取范式 范式雖然為命題公式提供了一種統(tǒng)一的表達(dá)形式，但這種表達(dá)形式卻并不是唯一的。P∨ Q)； ?性質(zhì)： (1)：一個文字既是一個析取范式又是一個合取范式； (2)：一個析取范式為矛盾式，當(dāng)且僅當(dāng)它的每個簡單合取式是矛盾式； (3)一個合取范式為重言式，當(dāng)且僅當(dāng)它的每個簡單析取式是重言式。P ；②： P∨ Q∨ 172。 58/73 ：范式 ：范式 對于給定公式的判定問題，可用真值表方法加以解釋，但當(dāng)公式中命題變元的數(shù)目較大時，計算量較大，每增加一個命題變元，真值表的行數(shù)要翻倍，計算量加倍，此外，對于同一問題，可以從不同的角度去考慮，產(chǎn)生不同的但又等價的命題公式，即同一個命題可以有不同的表達(dá)形式。 ?例 ： 試將公式 (P→(Q∨ 172。,∨ }， {172。,∧ }是一個極小聯(lián)結(jié)詞完備集。(172。 ?由前面 ， {172。 ?55/73 聯(lián)結(jié)詞的完備集 與非，或非，異或的性質(zhì) ： P↑Q?Q↑P， P↑P ? 172。(P?Q) ， P Q ? 172。Q， f8=(P?Q)， f9 = 172。(P∨ Q)， f3= 172。 P f1 f2 f3 f4 0 0 0 1 1 1 0 1 0 1 52/73 聯(lián)結(jié)詞的完備集 因此 ， 最多只能定義 4種運算 ， 但除了否定之外 ， 永假 ，永真 ， 恒等作為運算意義不大 ， 所以一般不再定義其它一元運算 。P∧ Q)= 172。P∨ (172。P1, 172。P ∨ (Q∧ R)和 172。 49/73 公式的解釋與真值表 ：對偶原理 ?定義 ： 設(shè)公式 A， 其中僅有聯(lián)結(jié)詞 ∧ ， ∨ ， 172。R)=P。((P∨ 172。 46/73 公式的解釋與真值表 例 ： 設(shè) G(P, Q) = 172。P∧ (P∨ Q) =Q I6 (P→Q) ∧ (Q→R) =(P→R) I7 (P→Q) =((Q→R) →(P→R)) I8 ((P→Q) ∧ (R→S)) =(P∧ R→Q∧ S) I9 ((P?Q) ∧ (R?S)) =(P?R) 43/73 公式的解釋與真值表 ： ? (1).若 A=B， B=C， 則 A=C；若 A=B， B=C， 則 A=C. (即邏輯恒等和永真蘊含都是可傳遞的 ) 證明： A=B， B=C， 即 A?B， B?C為重言式 ， 對任意的解釋 I， A和 B， B和 C的真值相同 ，則 A和 C的真值相同 。Q→172。P=T 排中律 E21 P∧ 172。(P∧ Q) =172。(P∨ Q) =172。 39/73 公式的解釋與真值表 ?注意 ?與 ?不同： (1). ? ：邏輯等價關(guān)系 ， G ? H不是命題公式； (2). ?：邏輯聯(lián)結(jié)詞 ， G ?H是命題公式； (3).計算機(jī)不能判斷 G， H是否邏輯等價 ， 而可計算 G ?H是否為重言式 。 (2). ((P→Q)∧ P) →Q； (3). P?(Q ∧ R)。 由于一個命題公式的解釋的數(shù)目是有窮的 ， 所以命題邏輯的判定問題是可解的 ， 即命題的永真 ， 永假性是可判定的 。 35/73 公式的解釋與真值表 ： ?定義 ： (1). 公式 G稱為永真公式 （ 重言式 ） ，