【正文】 61/73 ：范式 ?定理 ： 任一命題公式都存在著與之等值的析取范式和合取范式。Q) ?(P→R)的析取范式和合取范式。如公式(P∨ Q)∧ (P∨ R)與之等價(jià)的公式有： P∨ (Q∧ R)，(P∧ P)∨ (Q∧ R) ， P∨ (Q∧ 172。 ?定義 ： (1)包含 A中所有命題變?cè)蚱浞穸ㄒ淮蝺H一次的簡單合取式，稱為極小項(xiàng)； (2)包含 A中所有命題變?cè)蚱浞穸ㄒ淮蝺H一次的簡單析取式，稱為極大項(xiàng)； (3)由有限個(gè)極小項(xiàng)組成的析取范式稱為主析取范式； (4)由有限個(gè)極大項(xiàng)組成的合取范式稱為主合取范式。P ∧ Q， P∧ 172。P ∧ 172。P ∨ Q, P∨ 172。P ∨ 172。其真值表如下： 一般來說，對(duì)于 n個(gè)命題變?cè)?，則應(yīng)有 個(gè)不同的極小項(xiàng)和 個(gè)不同的極大項(xiàng)。P∧ Q P∧ 172。P∧ 172。P∨ 172。P∨ Q P∨ 172。P ∧ 172。R 只有在 P， Q， R分別取真值 0， 0， 0時(shí)才為真，所以有時(shí)又可用 ( )來表示，又如 172。R 也可用 ( )來表示。因此可給極大項(xiàng)編碼，使極大項(xiàng)為“ F”的那組真值指派為對(duì)應(yīng)的極大項(xiàng)的編碼，如極大項(xiàng) 172。Q ∨ 172。 000m 0m 010m2m)M(M 711165/73 ：范式 三個(gè)命題變?cè)恼嬷等≈蹬c極小項(xiàng)和極大項(xiàng)的對(duì)應(yīng)對(duì)位關(guān)系表： P Q R 極小項(xiàng) 極大項(xiàng) 0 0 0 m0= 172。Q∧ 172。P∧ 172。R 0 1 0 m2= 172。R M2= P∨ 172。P∧ Q∧ R M3= P∨ 172。R 1 0 0 m4= P∧ 172。R M4= 172。Q∧ R M5= 172。R 1 1 0 m6= P∧ Q∧ 172。P∨ 172。P∨ 172。R 66/73 ：范式 (3)：任意兩極小項(xiàng)的合取必假，任意兩個(gè)極大項(xiàng)的析取必為真。 [真值表技術(shù) ] ?例 ： 求命題公式 ((P∧ Q)→R)∧ (P?Q)的主析取范式。 68/73 ：范式 ?利用真值表技術(shù)求主析取范式和主合取范式的方法： ① ：選出公式的真值結(jié)果為真的所有行，在這樣的行中，找到其每一個(gè)解釋所對(duì)應(yīng)的極小項(xiàng)，將這些極小項(xiàng)析取即可得到相應(yīng)的主析取范式； ②：選出公式的真值結(jié)果為假的所有行，在這樣的行中，找到其每一個(gè)解釋所對(duì)應(yīng)的極大項(xiàng)，將這些極大項(xiàng)合取即可得到相應(yīng)的主合取范式。 ?例 ： 利用公式的等價(jià)求 G=(P→Q)∧ R的主析取范式和主合取范式 70/73 ：范式 ? 3：主合取范式和主析取范式之間的轉(zhuǎn)換 真值表技術(shù)和公式轉(zhuǎn)換方式在求主析取范式和主合取范式各有其優(yōu)點(diǎn)，在公式中的命題變?cè)^少時(shí)時(shí)，利用真值表技術(shù)更為簡單。但兩者之間必然有相應(yīng)的關(guān)系。 71/73 ：范式 ? (1)：已知公式 G的主析取范式求公式 G的主合取范式的步驟如下： a：求 172。(172。G 的主析取范式，其中 后剩下的極小項(xiàng)。 ilki m1G ???injki mG?????21),1()12,1,0()2,2,1( kimimkim ii jninj ??? ????? 中去掉是inininjkijkijki MmmGG?????? ???????????212121 )(72/73 ：范式 ? (2)：已知公式 G的主合取范式，求 G的主析取范式的步驟如下： a：求 172。(172。G 的主合取范式。 則 為 G的主析取范式 ijki MG ??injki MG?????21),2,1()12,1,0()2,2,1( kiMiMkiM ii jninj ??? ????? 中去掉是inininjkijkijki mMMGG?????? ???????????212121 )(73/73 ：范式 ?例 ： 設(shè) G=(P∧ Q)∨ (172。Q∧ 172。 (真值表和主范式是描述命題公式標(biāo)準(zhǔn)形式的兩種不同的等價(jià)形式 )。 ?定義 ： 設(shè) G1， G2， … ， Gn， H是命題公式，若對(duì)于 G1， G2， … ， Gn， H中出現(xiàn)的命題變?cè)娜我庖唤M賦值，或者 G1∧ G2∧ …Gn 為假，或者當(dāng)G1∧ G2∧ …Gn 為真， H也為真，則稱 H是 G1，G2， … ， Gn的有效結(jié)論 (Efficacious Conclusion)或邏輯結(jié)果 (Logic Conclusion)。記 {G2， … ， Gn}推理H為 {G2， … ， Gn}├H，若正確推理，則記為{G2， … ， Gn}╞H。 =：邏輯蘊(yùn)含關(guān)系， G=H不是命題公式，計(jì)算機(jī)判斷 G=H辦不到； →：蘊(yùn)含聯(lián)結(jié)詞， G →H是命題公式，計(jì)算機(jī)可判斷 G →H為永真公式。 我們將由 {G1， G2， … ， Gn}推理 H，用蘊(yùn)含式表示為： (G1∧ G2∧ …Gn) →H 將由 {G1， G2， … ， Gn}正確推理出 H，用蘊(yùn)含式表示為： G1∧ G2∧ …Gn =H 76/73 ：命題邏輯的推理理論 推理的形式結(jié)構(gòu)為： G1∧ G2∧ …Gn →H ，書寫為： 前提： G1， G2， … ， Gn 結(jié)論： H 推理的有效性判斷，即判斷推理是否正確，也就是判斷 G1∧ G2∧ …Gn→H 是否為重言式。則 H是G1， G2， … ， Gn的邏輯結(jié)果。 (1). H： Q。P。Q ； (3). H： Q。P ， G2： P→Q； 直接用等值演算來判斷推理的形式結(jié)構(gòu)是否是重言式。她沒去看電影。 79/73 ：命題邏輯的推理理論 將推理的形式結(jié)構(gòu)轉(zhuǎn)化為主析取范式，但仍判斷其是否為重言式。若她去游泳，她就不去看電影了。 以上方法，當(dāng)形式結(jié)構(gòu)比較復(fù)雜，特別是所含的命題變?cè)^多時(shí)，一般很不方便，下面介紹構(gòu)造證明法。 (1)推理規(guī)則： ⑴ 前提引入規(guī)則：在推理的任何步驟上都可以引入前提； ⑵ 結(jié)論引入規(guī)則：在推理的任何步驟上所得到的結(jié)論都可以做為后續(xù)證明的前提； ⑶ 置換規(guī)則：在推理的任何步驟上，命題公式的子公式都可以用與之等價(jià)的公式置換，得到公式序列中又一個(gè)公式。B =172。B =A 析取三段論 6 .(A→B) ∧ (B→C) =A→C 假言三段論 7 .(A?B) ∧ (B?C) =A?C 等價(jià)三段論 8 .(A→B)∧ (C→D)∧ (A∨ C) =(B∨ D) 構(gòu)造性二難 (A→B)∧ (172。A) =B構(gòu)造性二難 (特殊形式 ) 9 .(A→B)∧ (C→D)∧ (172。D) =(172。C)破壞性二難 82/73 ：命題邏輯的推理理論 由著 9個(gè)定律中的 8個(gè)可以得到 8個(gè)推理規(guī)則： ⑷附加規(guī)則： A|=(A∨ B) ⑸ 化簡規(guī)則： (A∧ B)|=A ⑹ 假言推理規(guī)則： (A→B) ， A |=B ⑺ 拒取式規(guī)則： (A→B)， 172。A ⑻ 假言三段論規(guī)則： (A→B)， (B→C)|=(A→C) ⑼ 析取三段論規(guī)則： (A ? B)， 172。B∨ 172。A∨ 172。r， s →t， 172。t 結(jié)論： q ?例 ： 分析下列事實(shí)：“早飯我吃面包或蛋糕；如果我吃面包，那么我還要喝牛奶；如果我吃蛋糕，那么我還要喝咖啡；但我沒有喝咖啡，所以早飯我吃的是牛奶和面包。 ?例 ： 用構(gòu)造法證明，找出下列推理的有效結(jié)論。 84/73 ：命題邏輯的推理理論 (3)P1∧ P2∧ … ∧ Pn →(P → Q)形式命題的證明。 ?例 ： 如果 A參加球賽，則 B或 C也將參加球賽。如果 D參加球賽，則 C不參加球賽。 85/73 ：命題邏輯的推理理論 ?例 ： 設(shè)前提條件 T={P→(Q→S)， 172。 (4)反證法 (歸謬法 ) ?定義 ： 設(shè) G1， G2， … ， Gn是一組命題公式 P1，P2， … ， Pn是出現(xiàn)在 G1， G2， … ， Gn中的一切命題變?cè)?I是它的任意解釋，若有解釋 I使G1∧ G2∧ … ∧ Gn取值為“真”，則稱公式 G1，G2， … ， Gn是一致的 (Consistency)。 86/73 ：命題邏輯的推理理論 ?定理 ： 設(shè)命題公式集合 {G1， G2， … ， Gn}是一致的，于是從前提集合 {G1， G2， … ， Gn}出發(fā)可以邏輯地推出公式 H的充要條件是從前提集合{G1， G2， … ， Gn， 172。 由定理知： 歸謬法：將結(jié)論的否定作為附加前提引入，公式序列的最后得到一矛盾式，則原結(jié)論成立。所以拉齊奧隊(duì)不能獲得亞軍 88/73 ：命題演算的自然推理形式系統(tǒng) ? 永真式是命題邏輯推理中一個(gè)非?；镜闹匾拍睿瑸榱讼到y(tǒng)研究它們，就需要把所有的永真式包括在一個(gè)系統(tǒng)內(nèi)，作為一個(gè)整體來研究，這樣的系統(tǒng)應(yīng)當(dāng)是一個(gè)形式系統(tǒng)，也只有形式系統(tǒng)，才能進(jìn)行充分的研究，從而掌握全部規(guī)律。 89/73 ：命題演算的自然推理形式系統(tǒng) ?形式系統(tǒng)一般有以下幾個(gè)部分組成 (1).字母表：由不加定義而采用的符號(hào)組成，字母表指此形式系統(tǒng)可以使用的符號(hào)； (2).字母表上符號(hào)串的一個(gè)子集 Form： Form中的元素稱為公式， Form指此形式系統(tǒng)可以使用的符號(hào)串； (3).Form的一個(gè)子集是 Axiom： Axiom中的元素稱為公理， Axiom指此形式系統(tǒng)一開始便接受而不加證明的定理； (4).推理規(guī)則系 Rule： Rule中的元素稱為推理規(guī)則，Rule規(guī)定了公式間的轉(zhuǎn)換關(guān)系。 ?對(duì)于一個(gè)具體的實(shí)際系統(tǒng)，用形式系統(tǒng)來描述，有兩個(gè)具體的問題必須解決： (1).可靠性問題：形式系統(tǒng)中正確推理出來的公式，定理在所討論的具體實(shí)際系統(tǒng)中是否為永真； (2).完備性問題：具體實(shí)際系統(tǒng)中的永真的語句是否均為形式系統(tǒng)內(nèi)的定理。 ∧ ， ∨ ， →， ?； (3)括號(hào)與逗號(hào) (， ) 2)公式 (同前面命題公式的定義 ) 3)推理規(guī)則 (用 12條規(guī)則 ) ? （定理 ） (1)可靠性：如果 G1， G2， …Gn |=H ，則G1∧ G2∧ …Gn →H 永真 (2)完備性：反之