【正文】 值式的判別 有兩種方法：真值表方法 ， 命題演算方法 真值表方法 例 1 用真值表方法證明 E10： ? (P?Q) ?? P??Q 解 令： A= ?(P?Q)， B= ? P??Q， 構造 A， B 以及 A ?B的真值表如下： P Q P?Q ?(P?Q) ?P ?Q ?P??Q A?B 0 0 0 1 1 1 1 1 0 1 1 0 1 0 0 1 1 1 1 0 0 1 0 1 由于公式 A?B所標記的列全為 1，因此 A?B。 則 ?P∨ Q， P?Q，（ P?Q） ∨ （ R∧ ?S）等均是 A的子公式， 但 ?P∨ ， P?和 ?Q等均不是 A的子公式， 置換規(guī)則 設 C是公式 A的子公式， C?D。 注意： 符號 “ ?” 和 “ ?” 的區(qū)別和聯(lián)系與符號 “ ?” 與 “ ? ” 的區(qū)別和聯(lián)系類似。 36 編號 蘊 含 式 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 五、蘊含式的判別 判定“ A ? B”是否成立的問題可轉化為判定 A ? B是否為重言式，有下述判定方法： （ 1）真值表； （ 2）等值演算； （ 3）假定前件 A為真； （ 4）假定后件 B為假。 由此可知 P?Q與 R?S中至少一個為假 , 因此 (P?Q)?(R?S)為假 . 故上述蘊含式成立 。Pi ，則稱其為 質(zhì)合取式 。 45 定理 94 （ 1） 一質(zhì)合取式為永假式的充分必要條件是，它同時包含某個命題變元 P及其否定 172。 例如 A=P1∨ 172。 即具有 A1∧A 2∧ … ∧A n (n≥1) 的形式的公式，其中 Ai是質(zhì)析取式。 則由定理 94知， Ai不是矛盾式。 又 A??P∨(P∧( ?Q∨P)) ?（ ?P∨P ） ∧ （ ?P∨ ?Q∨P) （合取范式） E3ノ 由定理 95知， A是重言式。 P1∨ ?P2∨P 3是由 P1， P2， P3產(chǎn)生的一個最大項。 永假公式 的主析取范式是一個空公式 。例如，例 4中的 F2。 63 練習 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個項，故 F不是重言式和矛盾式，只是可滿足式。 （ 1） H1： P→ Q， H2： P， C： Q 二、如何判斷由一個前提集合能否推出某個結論 66 （ 2） H1： P→Q ， H2： 172。 67 等值演算方法 例 證明 ? ? PRRP ???????? 、 分析 根據(jù)題意，需證明 PRRP ?????????? )()(.))()(( 是永真公式即需證明 PRRP ??????????PRRRP ??????????? )))()(()(( PRP ???????? ))()(( PRRQP ???????????? ))()(( PRQP ???????? )( PRQP ????????? )(1?????? PRQP ))()(( PRRP ??????????證明 PRRP ?????????? )))(()(( 68 “ 形式證明 ” 方法 （ 1）基本述語 形式證明 ：一個描述推理過程的命題序列，其中每個 命題或者是已知的命題，或者是由某些前提所推得的結論， 序列中最后一個命題就是所要求的結論，這樣的命題序列稱 為形式證明。 69 ( 2) 推理規(guī)則 前提引用規(guī)則 ： 在證明的任何步驟上都可以引用前提。S 172。R∨ S） Q 172。C， A ? 172。否則稱公式 H1， H2… ,Hn是相容的。R）是重言式， 75 為了證明 H H … 、 H n?C， 利用定理 98，將 ? C 添 加 到 這 一 組 前 提 中 ， 轉 化 為 證 明 H1?H2?… ?Hn??C ? R??R 于是得出 H H … 、 Hn、 ?C是不相容的 。P）作為附加前提，添加到前提集合中，然后推出矛盾。Q 附加前提 （ 1）； E6 前提 （ 1），（ 2）； I11 前提 （ 4），（ 5）； E6， I12 前提 （ 6），（ 7）； I10 前提 （ 8），（ 9）； I11 （ 4），（ 10）； I9 因此（ R→ 172。 編 號 公 式 依 據(jù) （ 1） （ 2） （ 3） （ 4） （ 5） （ 6） （ 7） 172。 R∨ S， 172。Q （ 1），（ 2） 。P→ Q， Q→ 172。 編 號 公 式 依 據(jù) （ 1） P → 172。P∧ 172。P∧ Q∧ 172。 Q） （ 3），（ 4）； I13 （ 6） 172。 下面根據(jù)已知前提進行形式推理。 令 P：張三說真話； Q：李四說真話； R：王五說真話， 由題意知推理的前提為： P→ 172。Q 前提 因此上述推理正確。P∨ 172。R∨ S， 172。Q 172。P 用反證法，將 172。 因此， H1， H2， … ,Hn是不相容的。 C 172。 推理過程符號化為 A→ （ B∨ C）， B→ 172。Q∨ S） 172。 所以 P∨ Q， Q→ R， P→ S， 172。 合理的結論 ：一個結論是否有效與它自身的真假沒有關 系。P) → 172。P 172。 (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是可滿足公式 。例如，例 4中的 F1。 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， … ， Pn所產(chǎn)生的最大項 。 51 例 3 判別公式 A=P? (P∧(Q ?P))是否為重言式或矛盾式。 解 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 ?(P∧ ?P) ∨ (P∧ ?Q)∨ (?P∧ Q)∨ (Q∧ ?Q)（析取范式） E3 50 定理 95 （ 1）公式 A為永真式的充分必要條件是， A的合取范式中每一質(zhì)析取式至少包含一對互為否定的析取項。 例如 ， F1=P∨(P∧Q)∨R∨( ?P∧ ?Q∧R) 是一析取范式。P i時，指派 Pi取 1。 Q∨P∨ 172。 因此蘊含式成立。 故蘊含式 I12 成立。 傳遞性 ：若 A?B， B?C，則 A?C。 32 三、命題公式的蘊含關系 定義 911 設 A， B是兩個公式，若公式 A?B是重言式，即 A?B?1，則稱公式 A蘊含公式 B，記作 A?B。 28 (2) 置 換規(guī)則 定義 910 設 C是命題公式 A的一部分（即 C是公式 A中連續(xù)的幾個符號），且 C本身也是一個命題公式，則稱 C為公式 A的 子公式。 可傳遞性 ：對任意公式 A、 B、 C，若 A?B，B?C，則 A?C。 20 命題公式的等值關系和蘊含關系 一、命題公式的等值關系 定義 99 設 A和 B是兩個命題公式 , P1, P2, …, P n 是所有出現(xiàn)于 A和 B中的命題變元，如果對于 P1, P2, …, P n 的任一組真值指派， A和 B的真值都相同 ,則稱公式 A和 B等值 ，記為 A ? B,稱 A?B為等值式 。P? Q） ? 172。相反地，若對于 F所包含的命題變元的任何一組真值指派， F的真值恒為假，則稱公式 F為 矛盾式 （或 永假公式 ），常用“ 0”表示。 16 二、真值指派 命題公式代表一個命題，但只有當公式中的每一個命題變元都用一個確定的命題代入時，命題公式才有確定的真值，成為命題。 15 3. 命題公式 命題公式（或簡稱公式）是由 0、 1和命題變元以及命題聯(lián)結詞按一定的規(guī)則產(chǎn)生的符號串。 則該命題可表示為 172。 則命題可表示為 （ 172。 （ 2） 令 P：我們劃船； Q：我們跑步。P ∧ 172。 11 三、命題符號化 利用聯(lián)結詞可以把許多日常語句符號化。 例 9 若 P：雪是黑色的； Q：太陽從西邊升起； R：太陽從東邊升起。 由于 “ ∨ ”可用“ ∨ ”，“ ∧ ”和“ 172。 解 令 P：他可能是 100米賽跑冠軍；