【正文】 8） （ 9） （ 10） （ 11） 172。R∨ S 172。I11 （ 4） P→ Q 前提 （ 5） 172。 Q 前 提 （ 2） 172。R （ 9），（ 10）； I11 （ 12） 172。 R→ （ P∨ Q）。 編 號 公 式 依 據 （ 1） R→ 172。Q是前提（ P∧ Q） → R， 172。 Q、 P→Q ? 172。B C D→ 172。R∨ （ 172。這樣的證明稱作是合理的。 CHHH n ???? )( 21 ?P Q 0 0 0 1 1 0 1 1 解 構造其真值表如下： 172。 59 六 、 利用主范式判定公式類型 1. 利用主析取范式判定 (1) 若公式 F(P1, P2， … ， Pn)的主析取范式包含所有 2n個最小項，則 F是永真公式。 又 P?(P?Q) ? (P?Q)??P 53 四、主析取范式和主合取范式 定義 916 設有命題變元 P1， P2， … ,Pn ， 形如 的命題公式稱為是由命題變元 P 1， P2， … ， Pn所產生的最小項。 48 例 1 求 F1=(P∧ (Q?R))?S的合取范式和析取范式 解 F1? ? (P∧ (?Q∨ R))∨ S E11 ? ?P∨ ?(? Q∨ R)∨ S E10ノ ? ?P∨ (Q∧ ?R)∨ S (析取范式 ) E10 ,E6 又 F1? ?P∨ (Q∧ ?R)∨ S ? (?P∨ S)∨ (Q∧ ?R) E1 ,E2 ? (?P∨ S∨ Q)∧ (?P∨ S∨ ?R) （合取范式） E3ノ 另外由 F1? (?P∨ S∨ Q)∧ (?P∨ S∨ ?R) ?(?P∧ (?P∨ S∨ ?R))∨ (S∧ (?P∨ S∨ ?R))∨ (Q∧ (?P∨ S∨ ?R)) E3 ??P∨ S∨ (Q∧ ?P)∨ (Q∧ S)∨ (Q∧ ?R) （析取范式） E9 ,E13 49 例 2 求 F2= ?(P∨Q) ? (P∧Q) 的析取范式、合取范式。 (反證法 ) 假設 A式中不同時包含任一命題變元及其否定 ， 則在 A中，當 Pi*為 Pi時指派 Pi取 0，當 Pi*為 172。 從而 P?（ Q?R）為假。 反對稱 ：若 A?B， B?A，則 A?B。所以，若對于等值式中的任一命題變元出現的每一處均用同一命題公式代入，則得到的仍是等值式。 (3)的真值表如第 4頁所示，它是可滿足公式。R F 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 0 1 0 1 0 1 0 0 0 1 1 1 1 1 1 0 0 0 1 0 0 0 1 1 1 0 1 0 0 0 1 0 0 0 0 1 0 1 0 0 0 1 0 1 1 1 0 18 三、公式類型 定義 98 如果對于命題公式 F所包含的命題變元的任何一組真值指派， F的真值恒為真，則稱公式 F為 重言式（或 永真公式 ），常用“ 1”表示。 一個命題變元當沒有對其賦予內容時，它的真值不能確定，一旦用一個具體的命題代入，它的真值就確定了。（ P ∧ Q） （ 5） 令 P：上午下雨； Q：我去看電影； R：我在家讀書。 （ 2）（ 172。 于是上述命題可表示為 P→Q 。”符號化。P取值為假；命題 P取值為假時，命題 172。 （ 4）你吃飯了嗎？ （ 5） x=3。首先引入命題、命題公式等概念。 C：如果明天天氣晴朗，那么我們舉行運動會。 當且僅當命題 P和 Q均取值為真時， P ∧ Q才取值為真。 由于 “ ∨ ”可用“ ∨ ”，“ ∧ ”和“ 172。 11 三、命題符號化 利用聯結詞可以把許多日常語句符號化。 （ 2） 令 P：我們劃船； Q：我們跑步。 則該命題可表示為 172。 16 二、真值指派 命題公式代表一個命題，但只有當公式中的每一個命題變元都用一個確定的命題代入時，命題公式才有確定的真值，成為命題。P? Q） ? 172。 可傳遞性 ：對任意公式 A、 B、 C，若 A?B，B?C，則 A?C。 32 三、命題公式的蘊含關系 定義 911 設 A， B是兩個公式，若公式 A?B是重言式，即 A?B?1，則稱公式 A蘊含公式 B，記作 A?B。 故蘊含式 I12 成立。 Q∨P∨ 172。 例如 ， F1=P∨(P∧Q)∨R∨( ?P∧ ?Q∧R) 是一析取范式。 51 例 3 判別公式 A=P? (P∧(Q ?P))是否為重言式或矛盾式。 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所產生的主析取范式等值。 (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是可滿足公式 。P) → 172。 所以 P∨ Q， Q→ R， P→ S， 172。 推理過程符號化為 A→ （ B∨ C）， B→ 172。 因此， H1， H2， … ,Hn是不相容的。Q 172。P∨ 172。 令 P：張三說真話； Q：李四說真話； R：王五說真話， 由題意知推理的前提為： P→ 172。 Q） （ 3），（ 4）； I13 （ 6） 172。P∧ 172。P→ Q， Q→ 172。 R∨ S， 172。Q 附加前提 （ 1）； E6 前提 （ 1），（ 2）； I11 前提 （ 4），（ 5）； E6， I12 前提 （ 6），（ 7）； I10 前提 （ 8），（ 9）； I11 （ 4），（ 10）； I9 因此（ R→ 172。R）是重言式， 75 為了證明 H H … 、 H n?C， 利用定理 98，將 ? C 添 加 到 這 一 組 前 提 中 ， 轉 化 為 證 明 H1?H2?… ?Hn??C ? R??R 于是得出 H H … 、 Hn、 ?C是不相容的 。C， A ? 172。S 172。 67 等值演算方法 例 證明 ? ? PRRP ???????? 、 分析 根據題意，需證明 PRRP ?????????? )()(.))()(( 是永真公式即需證明 PRRP ??????????PRRRP ??????????? )))()(()(( PRP ???????? ))()(( PRRQP ???????????? ))()(( PRQP ???????? )( PRQP ????????? )(1?????? PRQP ))()(( PRRP ??????????證明 PRRP ?????????? )))(()(( 68 “ 形式證明 ” 方法 （ 1）基本述語 形式證明 ：一個描述推理過程的命題序列，其中每個 命題或者是已知的命題，或者是由某些前提所推得的結論， 序列中最后一個命題就是所要求的結論，這樣的命題序列稱 為形式證明。 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不是重言式和矛盾式，只是可滿足式。 永假公式 的主析取范式是一個空公式 。 又 A??P∨(P∧( ?Q∨P)) ?（ ?P∨P ） ∧ （ ?P∨ ?Q∨P) （合取范式） E3ノ 由定理 95知， A是重言式。 即具有 A1∧A 2∧ … ∧A n (n≥1) 的形式的公式，其中 Ai是質析取式。 45 定理 94 （ 1） 一質合取式為永假式的充分必要條件是，它同時包含某個命題變元 P及其否定 172。 由此可知 P?Q與 R?S中至少一個為假 , 因此 (P?Q)?(R?S)為假 . 故上述蘊含式成立 。 注意： 符號 “ ?” 和 “ ?” 的區(qū)別和聯系與符號 “ ?” 與 “ ? ” 的區(qū)別和聯系類似。 22 二 、 基本的等值式 設 P、 Q、 R是命題變元 ， 下表中列出了 24個最基本的等值式 : 編號 公 式 E1 E1ノ E2 E2ノ E3 E3ノ E4 E4ノ E5 E5ノ E6E6ノ E7 E7ノ P∨ Q?Q∨ P 交換律 P∧ Q?Q∧ P 交換律 (P∨ Q)∨ R ? P∨ (Q∨ R) 結合律 (P∧ Q)∧ R ?P∧ (Q∧ R) 結合律 P∧ (Q∨ R) ? (P∧ Q)∨ (P∧ R) 分配律 P∨ (Q∧ R) ? (P∨ Q)∧ (P∨ R) 分配律 P∨ 0?P 同一律 P∧ 1?P 同