【正文】 P∧ Q∧ 172。R 前 提 （ 11） 172。P （ 6）； E9 （ 8） 172。P∧ 172。 Q） （ 3），（ 4）； I13 （ 6） 172。Q） 前 提 （ 5） P→ （ 172。 Q→ R 前 提 （ 3） P→ R （ 1），（ 2）； I13 （ 4） R→ （ 172。 編 號 公 式 依 據(jù) （ 1） P → 172。 下面根據(jù)已知前提進(jìn)行形式推理。 Q）， 172。 Q→ R， R→ （ 172。P→ Q， Q→ 172。 令 P：張三說真話； Q：李四說真話； R：王五說真話， 由題意知推理的前提為： P→ 172。 P 79 2. 張三說李四在說謊，李四說王五在說謊，王五說張三、 李四都在說謊。P （ 3），（ 4）； I12 則上述推理過程符號化為 P → Q， R → 172。Q （ 1），（ 2） 。Q 前提 因此上述推理正確。 解 先將已知條件符號化 , 令 P：這里有球賽； Q：通行是困難的； R：他們按指定的時間到達(dá)了。P∨ 172。 R∨ S， 172。P∨ 172。（ P∧ Q） ∨ R 172。S 172。 編 號 公 式 依 據(jù) （ 1） （ 2） （ 3） （ 4） （ 5） （ 6） （ 7） 172。R∨ S， 172。P∨ 172。 Q） ∧ （ P→ Q)? 172。Q 附加前提 （ 1）； E6 前提 （ 1），（ 2）； I11 前提 （ 4），（ 5）； E6， I12 前提 （ 6），（ 7）； I10 前提 （ 8），（ 9）； I11 （ 4），（ 10）； I9 因此（ R→ 172。Q 172。Q 172。（ 172。P）作為附加前提，添加到前提集合中，然后推出矛盾。P 用反證法，將 172。 Q、 R∨S 、 S→ 172。 這意味著當(dāng) H1?H2?… ?Hn為真時， ?C必為假，因而 C必為真。R）是重言式， 75 為了證明 H H … 、 H n?C， 利用定理 98，將 ? C 添 加 到 這 一 組 前 提 中 ， 轉(zhuǎn) 化 為 證 明 H1?H2?… ?Hn??C ? R??R 于是得出 H H … 、 Hn、 ?C是不相容的 。 因此， H1， H2， … ,Hn是不相容的。 R ， 而 R∧ 172。 R 則公式 H1， H2， … ,Hn是不相容的。否則稱公式 H1， H2… ,Hn是相容的。 C 172。A 172。(172。C， A ? 172。 推理過程符號化為 A→ （ B∨ C）， B→ 172?！叭绻资枪谲姡瑒t乙或丙將得亞軍；如果乙得亞軍，則甲不能得冠軍；如果丁得亞軍，丙不能得亞軍；事實(shí)是甲已得冠軍，可知丁不能得亞軍”。 ,)()( RQPRQP ?????RQPRSQP 、 ???? )( 編 號 公 式 依 據(jù) （ 1） （ 2） （ 3） （ 4） （ 5） （ 6） （ 7） （ 8） R 172。R∨ S） Q 172。Q∨ S） 172。R∨ P R→ P P→ （ Q→ S） R→ （ Q→ S） 172。 R∨P 和 Q的有效結(jié)論。S 172。 所以 P∨ Q， Q→ R， P→ S， 172。 70 例 2 證明 R∧ （ P∨Q ）是前提 P∨Q ， Q→ R，P→ S ， 172。 置換規(guī)則 ： 在證明的任何步驟上，命題公式的子公式都可以用與它等值的其它命題公式置換。 69 ( 2) 推理規(guī)則 前提引用規(guī)則 ： 在證明的任何步驟上都可以引用前提。 合理的結(jié)論 ：一個結(jié)論是否有效與它自身的真假沒有關(guān) 系。 如果所有的前提都是真的，那么通過有效的證明所得到的結(jié)論 也是真的。 有效的結(jié)論 ：通過有效的證明而得到結(jié)論，稱作是有效的結(jié)論。 67 等值演算方法 例 證明 ? ? PRRP ???????? 、 分析 根據(jù)題意，需證明 PRRP ?????????? )()(.))()(( 是永真公式即需證明 PRRP ??????????PRRRP ??????????? )))()(()(( PRP ???????? ))()(( PRRQP ???????????? ))()(( PRQP ???????? )( PRQP ????????? )(1?????? PRQP ))()(( PRRP ??????????證明 PRRP ?????????? )))(()(( 68 “ 形式證明 ” 方法 （ 1）基本述語 形式證明 ：一個描述推理過程的命題序列，其中每個 命題或者是已知的命題，或者是由某些前提所推得的結(jié)論， 序列中最后一個命題就是所要求的結(jié)論，這樣的命題序列稱 為形式證明。P) → 172。Q P→ Q （ P→ Q） ∧ 172。 Q 解 構(gòu)造其真值表如下： 172。 （ 1） H1： P→ Q， H2： P， C： Q 二、如何判斷由一個前提集合能否推出某個結(jié)論 66 （ 2） H1： P→Q ， H2： 172。P 172。有時也記作H1， H2， … ,Hn ? C 65 真值表法 對于命題公式 中所有命題變元的每一組真值指派作出該公式的真值表，看是否為永真 。 定義 919 設(shè) A和 B是兩個命題公式，如果 A?B，即如果命題公式 A?B為重言式，則稱 B是前提 A的結(jié)論或從 A推出結(jié)論 B。 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個項(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是可滿足公式 。 (2) 若 F的主合取范式是一空公式且為 1， 則 F是永真公式 。 60 2 利用主合取范式判定 (1) 若公式 F（ P1, P2, … , Pn） 的主合取范式包含所有 2n個最大項(xiàng) ， 則 F是永假公式 。例如，例 4中的 F2。例如，例 4中的 F1。 永真公式 的主合取范式是一空公式，用 1表示。 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 每一個不為永真的公式 F(P1, P2, … , Pn）必與一個由 P1, P2, … , Pn所產(chǎn)生的主合取范式等值。 永假公式 的主析取范式是一個空公式 。 56 F2?(P?Q)?(P??Q) ? (?P?Q)? (P??Q) E11 ? (?P?P??Q)?(Q?P??Q) E3 ? 0?0 E?1, E?5 ? 0 定理 96 每一個不為永假的命題公式 F（ P1, P2, … , Pn）必與一個由 P1， P2， … ， Pn所產(chǎn)生的主析取范式等值。 (P1??P2?P3)?(P1?P2?P3)?(?P1??P2??P3)?(?P1?P2??P3)是一個主合取范式 。 定義 918 由不同最大項(xiàng)所組成的合取式，稱為 主合取范式 。 P1∨ ?P2∨P 3是由 P1， P2， P3產(chǎn)生的一個最大項(xiàng)。而形如 的命題公式稱為是由命題變元 P1， P2， … ， Pn所產(chǎn)生的最大項(xiàng) 。 由上可知 ， 該公式是一可滿足公式 。 解 P?(P?Q) ?(P?(P?Q))?(?P??(P?Q)) E12 ?(P?Q)?(?P?(?P??Q)) E?10 ?(P?Q)??P (析取范式 ) E?9 由定理 95，該公式不是永假公式。 又 A??P∨(P∧( ?Q∨P)) ?（ ?P∨P ） ∧ （ ?P∨ ?Q∨P) （合取范式） E3ノ 由定理 95知， A是重言式。 51 例 3 判別公式 A=P? (P∧(Q ?P))是否為重言式或矛盾式。于是由定理 94知，每一 Ai(1≤i≤n)都為矛盾式，因此 A1∨ A2∨ … ∨ An必為矛盾式，即 A為矛盾式。 對同一組真值指派， A的取值也必為真，這與 A是矛盾式不符，假設(shè)不成立。 則由定理 94知， Ai不是矛盾式。 解 F2 ? (?(P∨ Q) ?(P∧ Q))∧ ((P∧ Q) ?? (P∨ Q)) E14 ? ((P∨ Q)∨ (P∧ Q))∧ (?(P∧ Q)∨ ? (P∨ Q)) E11,E6 ?(P∨ (Q∨ (P∧ Q)))∧ (?P∨ ?Q∨ (?P∧ ?Q)) E2,E10ノ ,E10 ? (P∨ Q)∧ (?P∨ ?Q) （合取范式） E2,E9 ?(P∧ (?P∨ ?Q))∨ (Q∧ (?P∨ ?Q)) E3