【正文】 假的命題公式 F（ P1, P2, … , Pn）必與一個(gè)由 P1， P2， … ， Pn所產(chǎn)生的主析取范式等值。 57 例 5 求公式 F1= (P?Q)?(P??Q)和 公式 F2=P?(P?(Q?P))的主合取范式 F1? (?P?Q)?(P??Q) E11 ? (?P?Q)?(P?(Q??Q))?(?Q?(P??P)) E?5, E4 ? (?P?Q)?(P?Q)?(P??Q)?(P??Q)?(?P??Q) E?3 ? (P?Q)?(P??Q)?(?P?Q)?(?P??Q) E?7 58 解 F2 ??P∨ (P∧ (?Q∨ P)) E11 ? (?P∨ P)∧ (?P∨ ?Q∨ P) E3ノ ?1∧ 1 E5,E1 ? 1 定理 97 每一個(gè)不為永真的公式 F(P1, P2, … , Pn）必與一個(gè)由 P1, P2, … , Pn所產(chǎn)生的主合取范式等值。例如，例 4中的 F1。 60 2 利用主合取范式判定 (1) 若公式 F（ P1, P2, … , Pn） 的主合取范式包含所有 2n個(gè)最大項(xiàng) ， 則 F是永假公式 。 (3) 否則 ， F為可滿足公式 61 例 6 求公式 F=(Q?(P?Q))?P的主范式并判定公式的類型 . 解 (1) 求 F的主析取范式 F? ? (Q?(?P?Q))?P ? ?Q ? (P??Q)?P ? (?Q?(P??P)) ?(P??Q)?(P?(Q??Q)) ? （ P??Q)?(?P??Q)?(P??Q)?(P?Q)?(P??Q) ? (P?Q)?(P??Q)?(?P??Q) 由此可知 F是可滿足公式 。 定義 919 設(shè) A和 B是兩個(gè)命題公式，如果 A?B，即如果命題公式 A?B為重言式，則稱 B是前提 A的結(jié)論或從 A推出結(jié)論 B。P 172。 Q 解 構(gòu)造其真值表如下： 172。P) → 172。 有效的結(jié)論 ：通過(guò)有效的證明而得到結(jié)論，稱作是有效的結(jié)論。 合理的結(jié)論 ：一個(gè)結(jié)論是否有效與它自身的真假?zèng)]有關(guān) 系。 置換規(guī)則 ： 在證明的任何步驟上，命題公式的子公式都可以用與它等值的其它命題公式置換。 所以 P∨ Q， Q→ R， P→ S， 172。 R∨P 和 Q的有效結(jié)論。Q∨ S） 172。 ,)()( RQPRQP ?????RQPRSQP 、 ???? )( 編 號(hào) 公 式 依 據(jù) （ 1） （ 2） （ 3） （ 4） （ 5） （ 6） （ 7） （ 8） R 172。 推理過(guò)程符號(hào)化為 A→ （ B∨ C）， B→ 172。(172。 C 172。 R 則公式 H1， H2， … ,Hn是不相容的。 因此， H1， H2， … ,Hn是不相容的。 這意味著當(dāng) H1?H2?… ?Hn為真時(shí)， ?C必為假，因而 C必為真。P 用反證法，將 172。（ 172。Q 172。 Q） ∧ （ P→ Q)? 172。R∨ S， 172。S 172。P∨ 172。P∨ 172。Q 前提 因此上述推理正確。P （ 3），（ 4）； I12 則上述推理過(guò)程符號(hào)化為 P → Q， R → 172。 令 P：張三說(shuō)真話； Q：李四說(shuō)真話； R：王五說(shuō)真話， 由題意知推理的前提為： P→ 172。 Q→ R， R→ （ 172。 下面根據(jù)已知前提進(jìn)行形式推理。 Q→ R 前 提 （ 3） P→ R （ 1），（ 2）； I13 （ 4） R→ （ 172。 Q） （ 3），（ 4）； I13 （ 6） 172。P （ 6）； E9 （ 8） 172。P∧ Q∧ 172。R 前 提 （ 11） 172。P∧ 172。Q） 前 提 （ 5） P→ （ 172。 編 號(hào) 公 式 依 據(jù) （ 1） P → 172。 Q）， 172。P→ Q， Q→ 172。 P 79 2. 張三說(shuō)李四在說(shuō)謊，李四說(shuō)王五在說(shuō)謊，王五說(shuō)張三、 李四都在說(shuō)謊。Q （ 1），（ 2） 。 解 先將已知條件符號(hào)化 , 令 P：這里有球賽； Q：通行是困難的； R：他們按指定的時(shí)間到達(dá)了。 R∨ S， 172。（ P∧ Q） ∨ R 172。 編 號(hào) 公 式 依 據(jù) （ 1） （ 2） （ 3） （ 4） （ 5） （ 6） （ 7） 172。P∨ 172。Q 附加前提 （ 1）； E6 前提 （ 1），（ 2）； I11 前提 （ 4），（ 5）； E6， I12 前提 （ 6），（ 7）； I10 前提 （ 8），（ 9）； I11 （ 4），（ 10）； I9 因此（ R→ 172。Q 172。P）作為附加前提，添加到前提集合中，然后推出矛盾。 Q、 R∨S 、 S→ 172。R）是重言式， 75 為了證明 H H … 、 H n?C， 利用定理 98，將 ? C 添 加 到 這 一 組 前 提 中 ， 轉(zhuǎn) 化 為 證 明 H1?H2?… ?Hn??C ? R??R 于是得出 H H … 、 Hn、 ?C是不相容的 。 R ， 而 R∧ 172。否則稱公式 H1， H2… ,Hn是相容的。A 172。C， A ? 172?！叭绻资枪谲?，則乙或丙將得亞軍；如果乙得亞軍，則甲不能得冠軍；如果丁得亞軍，丙不能得亞軍；事實(shí)是甲已得冠軍，可知丁不能得亞軍”。R∨ S） Q 172。R∨ P R→ P P→ （ Q→ S） R→ （ Q→ S） 172。S 172。 70 例 2 證明 R∧ （ P∨Q ）是前提 P∨Q ， Q→ R，P→ S ， 172。 69 ( 2) 推理規(guī)則 前提引用規(guī)則 ： 在證明的任何步驟上都可以引用前提。 如果所有的前提都是真的，那么通過(guò)有效的證明所得到的結(jié)論 也是真的。 67 等值演算方法 例 證明 ? ? PRRP ???????? 、 分析 根據(jù)題意，需證明 PRRP ?????????? )()(.))()(( 是永真公式即需證明 PRRP ??????????PRRRP ??????????? )))()(()(( PRP ???????? ))()(( PRRQP ???????????? ))()(( PRQP ???????? )( PRQP ????????? )(1?????? PRQP ))()(( PRRP ??????????證明 PRRP ?????????? )))(()(( 68 “ 形式證明 ” 方法 （ 1）基本述語(yǔ) 形式證明 ：一個(gè)描述推理過(guò)程的命題序列，其中每個(gè) 命題或者是已知的命題，或者是由某些前提所推得的結(jié)論， 序列中最后一個(gè)命題就是所要求的結(jié)論，這樣的命題序列稱 為形式證明。Q P→ Q （ P→ Q） ∧ 172。 （ 1） H1： P→ Q， H2： P， C： Q 二、如何判斷由一個(gè)前提集合能否推出某個(gè)結(jié)論 66 （ 2） H1： P→Q ， H2： 172。有時(shí)也記作H1， H2， … ,Hn ? C 65 真值表法 對(duì)于命題公式 中所有命題變?cè)拿恳唤M真值指派作出該公式的真值表，看是否為永真 。 63 練習(xí) 74 1．判斷公式 F=(?P∨ ?Q)→(P ? ?Q)是否為重言式或矛盾式？ 解 F?? (?P∨ ?Q)∨ ((P→ ?Q)∧ (?Q→P)) E 11 ? (P∧Q)∨(( ?P∨ ?Q)∧(Q∨P)) E 10,E6,E11 ? (P∧ Q)∨ ((?P∧ (Q∨ P))∨ (?Q∧ (Q∨ P))) E3 ? (P∧ Q)∨ (?P∧ Q)∨ (?P∧ P)∨ (?Q∧ Q)∨ (?Q∧ P) E3 ? (P∧ Q)∨ (?P∧ Q)∨ (?Q∧ P) E5ノ ,E8 F的主析取范式既非空公式，又未包含 22=4個(gè)項(xiàng)，故 F不是重言式和矛盾式，只是可滿足式。 (2) 若 F的主合取范式是一空公式且為 1， 則 F是永真公式 。例如，例 4中的 F2。 永真公式 的主合取范式是一空公式，用 1表示。 永假公式 的主析取范式是一個(gè)空公式 。 (P1??P2?P3)?(P1?P2?P3)?(?P1??P2??P3)?(?P1?P2??P3)是一個(gè)主合取范式 。 P1∨ ?P2∨P 3是由 P1， P2， P3產(chǎn)生的一個(gè)最大項(xiàng)。 由上可知 ， 該公式是一可滿足公式 。 又 A??P∨(P∧( ?Q∨P)) ?（ ?P∨P ） ∧ （ ?P∨ ?Q∨P) （合取范式） E3ノ 由定理 95知， A是重言式。于是由定理 94知，每一 Ai(1≤i≤n)都為矛盾式，因此 A1∨ A2∨ … ∨ An必為矛盾式，即 A為矛盾式。 則由定理 94知， Ai不是矛盾式。 按下列步驟進(jìn)行： （ 1）利用 E11， E12和 E14消去公式中的運(yùn)算符“ ?” 和 “ ?” ； (2) 利用德 ?摩根定律將否定符號(hào) “ ?” 向內(nèi)深入，使之只作用于命題變?cè)? （ 3）利用雙重否定律 E6將 ? (?P)置換成 P； （ 4）利用分配律、結(jié)合律將公式歸約為合取范式或析取范式。 即具有 A1∧A 2∧ … ∧A n (n≥1) 的形式的公式，其中 Ai是質(zhì)析取式。 46 定義 914 質(zhì)合取式的析取稱為析取范式。 例如 A=P1∨ 172。 證明 （ 2） 必要性 ：假設(shè) A= P1*∨ P2*∨ … ∨ Pn*為一質(zhì)析取式，且 A為一永真式。 45 定理 94 （ 1） 一質(zhì)合取式為永假式的充分必要條件是，它同時(shí)包含某個(gè)命題變?cè)?P及其否定 172。Pi ，則稱其為 質(zhì)析取式 。Pi ，則稱其為 質(zhì)合取式 。 于是 P為真， Q?R為假。 由此可知 P?Q與 R?S中至少一個(gè)為假 , 因此 (P?Q)?(R?S)為假 . 故上述蘊(yùn)含式成立 。 于是 Q為假，因而 P也為假。 36 編號(hào) 蘊(yùn) 含 式 I9 P?Q?P?Q 或表示為 ： P、 Q?P?Q I10 ?P?(P?Q) ?Q ?P、 (P?Q)?Q I11 P?(P?Q)?Q P、 P?Q?Q I12 ?Q?(P?Q)??P ?Q、 P?Q??P I13 (P?Q)?(Q?R)?P?R P?Q、 Q?R?P?R I14 (P?Q)?(P?R) ? (Q?R) ?R P?Q、 P?R、 Q?R?R I15 P?Q?(P?R)?(Q?R) I16 P?Q?(P?R)?(Q?R) 37 五、蘊(yùn)含式的判別 判定“ A