【正文】 稱為合取范式 (Conjunctive Normal From)。 60/73 ：范式 ?例如， ①： P， 172。P ；②： P∨ Q∨ 172。R ； ③： 172。P ∧ Q∧ R；④： (P∧ Q)∨ (172。P∧ Q)； ⑤： (P∨ Q)∧ (172。P∨ Q)； ?性質： (1)：一個文字既是一個析取范式又是一個合取范式； (2)：一個析取范式為矛盾式，當且僅當它的每個簡單合取式是矛盾式； (3)一個合取范式為重言式，當且僅當它的每個簡單析取式是重言式。 61/73 ：范式 ?定理 ： 任一命題公式都存在著與之等值的析取范式和合取范式。 ?例 ： 求公式 (P∧ 172。Q) ?(P→R)的析取范式和合取范式。 62/73 ：范式 ?：主析取范式和主合取范式 范式雖然為命題公式提供了一種統(tǒng)一的表達形式，但這種表達形式卻并不是唯一的。如公式(P∨ Q)∧ (P∨ R)與之等價的公式有： P∨ (Q∧ R)，(P∧ P)∨ (Q∧ R) ， P∨ (Q∧ 172。Q)∨ (Q∧ R)，P∨ (P∧ R)∨ (Q∧ R),等，這種不唯一的表達形式給研究問題帶來了不便，因此有必要引進更為標準的范式。 ?定義 ： (1)包含 A中所有命題變元或其否定一次僅一次的簡單合取式，稱為極小項； (2)包含 A中所有命題變元或其否定一次僅一次的簡單析取式，稱為極大項； (3)由有限個極小項組成的析取范式稱為主析取范式； (4)由有限個極大項組成的合取范式稱為主合取范式。 63/73 ：范式 ? 對于兩個命題變元 P， Q來說，由于每個 P， Q可以取命題變元自身和其否定，所以其對應的極小項和極大項分別有四項： P∧ Q， 172。P ∧ Q， P∧ 172。Q ，172。P ∧ 172。Q ； P∨ Q， 172。P ∨ Q, P∨ 172。Q ， 172。P ∨ 172。Q 。其真值表如下： 一般來說，對于 n個命題變元，則應有 個不同的極小項和 個不同的極大項。 P Q P∧ Q 172。P∧ Q P∧ 172。Q 172。P∧ 172。Q 172。P∨ 172。Q 172。P∨ Q P∨ 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 ：范式 ?性質： (1)：沒有兩個不同的極小項是等價的，且每個極小項只有一組真值指派使該極小項的真值為真，因此可給極小項編碼，使極小項為“ T”和那組真值指派為對應的極小項編碼；如極小項 172。P ∧ 172。Q ∧ 172。R 只有在 P， Q， R分別取真值 0， 0， 0時才為真，所以有時又可用 ( )來表示，又如 172。P ∧ Q∧ 172。R 也可用 ( )來表示。 (2)：沒有兩個不同的極大項是等價的，且每個極大項只有一組真值指派，使該極大項的真值為假。因此可給極大項編碼，使極大項為“ F”的那組真值指派為對應的極大項的編碼，如極大項 172。P ∨ 172。Q ∨ 172。R只有在 P， Q， R分別取真值 1， 1， 1時才為假，所以有時又可用 來表示。 000m 0m 010m2m)M(M 711165/73 ：范式 三個命題變元的真值取值與極小項和極大項的對應對位關系表： P Q R 極小項 極大項 0 0 0 m0= 172。P∧ 172。Q∧ 172。R M0= P∨ Q∨ R 0 0 1 m1= 172。P∧ 172。Q∧ R M1= P∨ Q∨ 172。R 0 1 0 m2= 172。P∧ Q∧ 172。R M2= P∨ 172。Q∨ R 0 1 1 m3= 172。P∧ Q∧ R M3= P∨ 172。Q∨ 172。R 1 0 0 m4= P∧ 172。Q∧ 172。R M4= 172。P∨ Q∨ R 1 0 1 m5= P∧ 172。Q∧ R M5= 172。P∨ Q∨ 172。R 1 1 0 m6= P∧ Q∧ 172。R M6= 172。P∨ 172。Q∨ R 1 1 1 m7= P∧ Q∧ R M7= 172。P∨ 172。Q∨ 172。R 66/73 ：范式 (3)：任意兩極小項的合取必假，任意兩個極大項的析取必為真。極大項的否定是極小項，極小項的否定是極大項，即 (4)：所有極小項的析取為永真公式，所有極大項的合取是永假公式，即 iiiinjijimMMmjijiFmmTMM???????????，；， ])12,0[,.(0 1 12 012 0 ???? ???? iiii Mm nn ，67/73 ：范式 ? ?定理 ： 任何命題公式的主析取范式和主合取范式存在且唯一，即任何命題公式都有且僅有一個與之等價的主合取范式和主析取范式。 [真值表技術 ] ?例 ： 求命題公式 ((P∧ Q)→R)∧ (P?Q)的主析取范式。 ?例 ： 求命題公式 (P→Q)?R的主合取范式。 68/73 ：范式 ?利用真值表技術求主析取范式和主合取范式的方法： ① ：選出公式的真值結果為真的所有行，在這樣的行中，找到其每一個解釋所對應的極小項，將這些極小項析取即可得到相應的主析取范式； ②：選出公式的真值結果為假的所有行，在這樣的行中，找到其每一個解釋所對應的極大項，將這些極大項合取即可得到相應的主合取范式。 69/73 ：范式 [公式轉換法 ] 唯一性： 設任一命題公式 A有兩個主析取范式 B和 C，則因為 A=B， A=C，所以 B=C，若 B， C是 A的(在不計極小項的順序的情況下 )不同的主析取范式，則必有在存在極小項 mi， mi只存在于 B， C之一中，不妨設 mi在 B中 ,而不在 C中，因此 i之二進制表示 B的一個真值解釋，而對于 C則為真值為假的解釋，這與 B=C矛盾，所以 B和 C相同，同理主合取范式也是唯一的。 ?例 ： 利用公式的等價求 G=(P→Q)∧ R的主析取范式和主合取范式 70/73 ：范式 ? 3：主合取范式和主析取范式之間的轉換 真值表技術和公式轉換方式在求主析取范式和主合取范式各有其優(yōu)點，在公式中的命題變元較少時時，利用真值表技術更為簡單。當命題變元較多時，一般采用公式轉換法，而在公式轉換中，有時求主析取范式更為方便，而有時求主合取范式更為方便。但兩者之間必然有相應的關系。下面介紹一種兩者之間的轉換方法。 71/73 ：范式 ? (1)：已知公式 G的主析取范式求公式 G的主合取范式的步驟如下： a：求 172。G 的主析取范式，即 G的主析取范式中沒有出現(xiàn)過的極小項的析取 b： G=172。(172。G)即是 G的主合取范式 即：若 為 G的主析取范式，則 為 172。G 的主析取范式，其中 后剩下的極小項。則 為 G的主合取范式。 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。G 的主合取范式，即 G的主合取范式中沒有出現(xiàn)過的極大項的合取 b： G=172。(172。G)即是 G的主析取范式， 即，若 為 G的主合取范式，則 為 172。G 的主合取范式。其中 后剩下的極大項。 則 為 G的主析取范式 ijki MG ??injki MG?????21),2,1()12,1,0()2,2,1( kiMiMkiM ii jninj ??? ????? 中去掉是inininjkijkijki mMMGG?????? ???????????212121 )(73/73 ：范式 ?例 ： 設 G=(P∧ Q)∨ (172。P∧ R)∨ (172。Q∧ 172。R),求其對應的主析取范式和主合取范式 ?性質： (1)：如果命題公式是永真公式 =它的主析取范式包含所有極小項，此時主合取范式不含有任何極大項，為空，記 1或 T (2)：如果命題公式是永假公式 =它的主合取范式包含所有極大項，此時主析取范式不含有任何極小項，為空，記 0或 F (3)：兩個命題公式 A， B， A=B當且僅當 A與 B有相同的真值表，又當且僅當 A與 B有相同的主析取范式 (主合取范式 )。 (真值表和主范式是描述命題公式標準形式的兩種不同的等價形式 )。 74/73 ：命題邏輯的推理理論 ?：推理的基本概念和推理形式 推理也稱論證，它是指從前提出發(fā)推出結論的思維過程，而前提是已知命題公式集合，結論是從前提出發(fā)應用推理規(guī)則推出的命題形式。 ?定義 ： 設 G1， G2， … ， Gn， H是命題公式，若對于 G1， G2， … ， Gn， H中出現(xiàn)的命題變元的任意一組賦值，或者 G1∧ G2∧ …Gn 為假，或者當G1∧ G2∧ …Gn 為真， H也為真，則稱 H是 G1，G2， … ， Gn的有效結論 (Efficacious Conclusion)或邏輯結果 (Logic Conclusion)。 G1， G2， … ，Gn仍為一組前提 (Premise)。記 {G2， … ， Gn}推理H為 {G2， … ， Gn}├H，若正確推理，則記為{G2， … ， Gn}╞H。 75/73 ：命題邏輯的推理理論 ?定理 ： 命題公式 G1， G2， … ， Gn推出結論 H的推理正確或公式 H是前提條件 {G1， G2， … ， Gn}的邏輯結果，當且僅當 (G1∧ G2∧ …Gn) →H 為重言式。 =：邏輯蘊含關系， G=H不是命題公式，計算機判