【文章內容簡介】 ?Q∧ ?P∧ ?Q E10 ?（ Q∧ ?Q） ∧ ?P E1ノ ,E2 ?0 E5ノ ,E8ノ 所以 Q∧ ? (?P? (?P∧ Q))是矛盾式。 （ 2） （ P?Q） ∧ ?P ?（ ?P∨ Q） ∧ ?P E11 ? ?P E9ノ 于是該公式是可滿足式。 32 三、命題公式的蘊含關系 定義 911 設 A， B是兩個公式，若公式 A?B是重言式，即 A?B?1，則稱公式 A蘊含公式 B，記作 A?B。稱 “ A?B”為 蘊含式 。 注意： 符號 “ ?” 和 “ ?” 的區(qū)別和聯(lián)系與符號 “ ?” 與 “ ? ” 的區(qū)別和聯(lián)系類似。 “?”不是聯(lián)結詞， “ A?B”不是公式，它表示公式 A與 B之間存在蘊含關系。 “?”是聯(lián)系詞， A?B是一個公式。 A?B當且僅當 A?B是永真公式 。 33 A?B是偏序關系 即 自反性 ： A?A。 反對稱 ：若 A?B， B?A，則 A?B。 傳遞性 ：若 A?B， B?C，則 A?C。 反對稱性的證明： 設 A?B且 B?A， 由定義 711 A?B?1且 B?A?1 于是 A?B?(A?B)?(B?A) E14 ? 1?1 ? 1 因此 A?B 34 傳遞性的證明： 設 A?B， B?C， 則 A?B?1， B?C?1 ? (?A?B?C)?(?A??B?C) ? ((A?B) ?C)?(?A?(B?C)) ? (1?C)?(?A?1) ? 1?1 ? 1 因此 A?C. 于是 A?C ?? A?C ? (?A?C)?(B??B) 35 四 、 基本的蘊含式 編號 蘊 含 式 I1 P?Q?P I2 P?Q?Q I3 P ?P?Q I4 Q?P?Q I5 ?P ?P?Q I6 Q?P?Q I7 ?(P?Q)?P I8 ?(P?Q)? ?Q 設 P、 Q、 R是命題變元 ， 下表中列出了 16個最基本的蘊含式 。 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為假。 1. 真值表方法 例 4 證明 I14 ： (（ P∨ Q） ∧ （ P ? R） ∧ （ Q ? R） ) ? R 證明 令公式 F =（ （ P∨ Q） ∧ （ P?R） ∧ （ Q?R） ） ?R， 其真值表如下： 38 公式 F對任意的一組真值指派取值均為 1，故 F是重言式。 P Q R P∨Q P→R Q →R (P∨Q)∧ (P→R ）∧ （ Q →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 0 0 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 1 0 1 1 1 0 1 0 0 0 1 0 1 0 1 1 1 1 1 1 1 1 1 39 2. 等值演算方法 例 5 證明 I11： P∧ （ P?Q） ? Q 證明 （ P∧ （ P?Q） ） ? Q ? ?（ P∧ （ ?P∨Q ） ） ∨ Q E11 ? （ ?P∨ ?（ ?P∨Q ） ） ∨ E10ノ ?（ ?P∨Q ） ∨ ?（ ?P∨Q ） E2 ? 1 代入規(guī)則 ,E5 因此 P∧ （ P?Q） ? Q 40 3. 假定前件 A真 假定前件 A為真，檢查在此情況下，其后件 B是否也為真。 A B A?B 0 0 1 0 1 1 1 0 0 1 1 1 例 6 證明 I12 : ?Q ∧ （ P?Q） ? ?P 證明 令前件 ?Q∧ （ P?Q）為真， 則 ?Q為真 , 且 P?Q為真。 于是 Q為假，因而 P也為假。由此 ?P為真。 故蘊含式 I12 成立。 41 假定后件 B假 假定后件 B為假，檢查在此情況下，其前件 A是否也為假 . 例 7 證明蘊含式 (P?Q) ? (R?S) ? (P?R) ? (Q?S) 證明 令后件 (P?R)?(Q?S)為假 ， 則 P?R為真 ， Q?S為假 , 于是 P、 R均為真 ， 而 Q和 S至少一個為假 。 由此可知 P?Q與 R?S中至少一個為假 , 因此 (P?Q)?(R?S)為假 . 故上述蘊含式成立 。 42 練習 73 1．判斷下列等值式是否成立 （ 1）（ P?Q） ∧ （ R ? Q） ?（ P∨ R） ? Q （ 2） ?（ P?Q） ?（ P∧ ? Q） ∨ （ ?P∧ Q） 解 （ 1）（ P?Q） ∧ （ R?Q） ?（ ?P∨ Q） ∧ （ ?R∨ Q） E11 ?（ ?P∧ ?R） ∨ Q E3ノ ??（ P∨ R） ∨ Q E10 （ 2）（ P∧ ?Q） ∨ （ ?P∧ Q） ? ? (（ ?P∨ Q） ∧ （ ?Q∨ P） ) E6， E10ノ ? ? (（ P?Q） ∧ （ Q?P） ) E11 ? ?（ P?Q） E14 ?（ P∨ R） ?Q E11 43 2．判定蘊含式 P?（ Q?R） ?（ P?Q） ?（ P?R）是否成立 解 假定后件（ P?Q） ?（ P?R）為假， 則 P?Q為真， P?R為假。 由 P?R為假 ,得 P為真， R為假。 又 P?Q為真，故得 Q為真。 于是 P為真， Q?R為假。 從而 P?（ Q?R）為假。 因此蘊含式成立。 44 范式 一、 析取范式和合取范式 定義 912 一個命題公式若它具有P1*∧P 2*∧ … ∧P n*的形式（ n≥1 ），其中 Pi*是命題變元 Pi或其否定 172。Pi ，則稱其為 質合取式 。 例如 ,172。P∧Q∧R∧S 是由命題變元 P、 Q、 R、 S組成的一質合取式。 定義 913 一個命題公式若具有P1*∨P 2*∨ … ∨P n*（ n≥1 ）的形式，其中 P*i是命題變元 Pi或是其否定 172。Pi ，則稱其為 質析取式 。 例如 , 172。 Q∨P∨ 172。R是由命題變元 P、 Q、 R組成的一質析取式。 45 定理 94 （ 1） 一質合取式為永假式的充分必要條件是，它同時包含某個命題變元 P及其否定 172。P 。 （ 2） 一質析取式為永真式的充分必要條件是，它同時包含某個命題變元 P及其否定 172。P 。 證明 （ 2） 必要性 ：假設 A= P1*∨ P2*∨ … ∨ Pn*為一質析取式，且 A為一永真式。 (反證法 ) 假設 A式中不同時包含任一命題變元及其否定 ， 則在 A中，當 Pi*為 Pi時指派 Pi取 0，當 Pi*為 172。P i時，指派 Pi取 1。(i =1,2,… n).這樣的一組真值指派使 A的真值取 0，這與 A為永真式矛盾。 例如 A=P1∨ 172。P 2∨ (P1,P2,P3)=(0,1,0)的指派，使 A的真值為 0. 充分性 ：設 A含命題變元 Pi和 172。P i，而 Pi∨ 172。P i是永真式， 由結合律和零一律， A的真值必為 1，故 A也是永真式。 46 定義 914 質合取式的析取稱為析取范式。即具有 A1∨A 2∨ … ∨A n(n≥1) 的形式的公式，其中 Ai是質合取式。 例如 ， F1=P∨(P∧Q)∨R∨( ?P∧ ?Q∧R) 是一析取范式。 定義 915 質析取式的合取稱為合取范式。 即具有 A1∧A 2∧ … ∧A n (n≥1) 的形式的公式，其中 Ai是質析取式。 例如 ， F2=?P∧(P∨Q)∧R∧(P∨ ?Q∨R) 是一合取范式。 F3=(?P∨R∨Q)∧(P∨Q)∧R∧(P∨ ?R)也是一合取范式。 47 二、求公式的析取范式和合取范式 任何一個命題公式都可以變換為與它等值的析取范式或合取范式。 按下列步驟進行： （ 1）利用 E11， E12和 E14消去公式中的運算符“ ?” 和 “ ?” ； (2) 利用德 ?摩根定律將否定符號 “ ?” 向內深入，使之只作用于命題變元； （ 3）利用雙重否定律 E6將 ? (?P)置換成 P； （ 4）利用分配律、結合律將公式歸約為合取范式或析取范式。 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))∨ (