【正文】 （ 1） P→( Q∧ PR）； （ 2）（ P∨ Q） → （ 172。 （ 2） 是命題公式。 定義 9—7 設 F為含有命題變元 P1， P2， … ,Pn的命題公式，對 P1， P2， … ,Pn分別指定一個真值 ,稱為對公式 F的一組 真值指派 。 17 例 2 給 出公式 F=(（ P∨Q ） ?（ Q∧R ） )? (P∧ 172。 解 公式 F的真值表如下： P QR 172。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”表示。如果至少有一組真值指派使公式 F的真值為真，則稱 F為 可滿足公式 。P?Q ） ? 172。P ∧ Q）； （ 3）（（ P∨Q ） → （ Q∧R ）） → （ P∧ 172。 19 解 令 F1=（ 172。（ P ? Q）， F2=（ Q→ P） ∧ （ 172。P 172。(P→Q) F1 Q→P 172。 (3)的真值表如第 4頁所示，它是可滿足公式。 注意 ： （ 1）符號 “ ?” 與 “ ? ” 的區(qū)別與聯(lián)系。 “? ”是聯(lián)結詞， A? B是一個公式。 21 （ 2） 可以驗證等值關系是等價關系。 對稱性 ：對任意公式 A， B，若 A?B，則B?A。 （ 3）當 A是重言式時， A?1；當 A是矛盾式時，則 A?0。 1 0 1 0 0 0 0 1 25 例 2 用真值表方法證明 E11： P?Q??P?Q 解 令 A=P?Q， B=?P?Q 構造 A， B以及 A?B的真值表如下： P Q ?P ?P?Q P?Q A?B 0 0 1 1 1 1 0 1 1 1 1 1 1 0 0 0 0 1 由于公式 A?B所標記的列全為 1， 因此 A?B. 1 1 0 1 1 1 26 例 3 用真值表方法判斷 P?Q??P??Q是否成立 . 解 令 A=P?Q， B=?P??Q 構造 A， B以及 A?B的真值表 P Q ?P ?Q ?P??Q P?Q A?B 0 0 1 1 1 1 1 0 1 1 0 0 1 0 0 1 1 0 0 由于公式 A?B所標記的列不全為 1， A?B不是永真公式 ， 因此 A?B不成立 。 2．等值演算方法 例如 F=（ P?Q） ? （ ?Q??P）是重言式，若 用公式 A∧ B代換命題變元 P得公式 F1=（（ A∧ B） ?Q） ? （ ?Q??（ A∧ B））， F1仍是重言式。所以，若對于等值式中的任一命題變元出現(xiàn)的每一處均用同一命題公式代入，則得到的仍是等值式。 例如 設公式 A=（ ?P∨Q ） ?（（ P?Q） ∨ （ R∧ ?S））。如果將公式 A中的子公式 C置換成公式 D之后，得到的公式是 B，則 A?B。 由代入規(guī)則知前述的基本等值式，不僅對任意的命題變元 P， Q， R是成立的，而且當 P， Q， R分別為命題公式時，這些等值式也成立 例 2 證明命題公式的等值關系： （ P?Q） ∧ （ R?Q） ?（ P∨ R） ?Q； 證明 （ P?Q） ∧ （ R?Q） ?（ ? P∨ Q） ∧ (? R∨ Q) E11 ?（ ? P∧ ? R） ∨ Q E3ˊ( 分配律 ) ? ? (P∨ R)∨ Q E10(德 .摩根定律 ) ? (P∨ R) ? Q E11 所以（ P?Q） ∧ （ R?Q） ?（ P∨ R） ?Q 30 例 3 證明下列命題公式的等值關系 (P ? Q ) ? (? P ? ( ? P ? Q ) ) ? ?P ? Q 證明 (P?Q)?( ?P?(?P?Q)) ? (P?Q)?( (?P? ? P ) ? Q ) E2(結合律 ) ? (P?Q)?( ?P?Q) E7(等冪律 ) ? (?P ? Q )? ( P?Q ) E1 (交換律 ) ? ? P?(Q?(P?Q)) E2(結合律 ) ? ?P?Q E?1， E9(交換律，吸收律 ) 31 例 4 判別下列公式的類型。 （ 2） （ P?Q） ∧ ?P ?（ ?P∨ Q） ∧ ?P E11 ? ?P E9ノ 于是該公式是可滿足式。稱 “ A?B”為 蘊含式 。 “?”不是聯(lián)結詞， “ A?B”不是公式，它表示公式 A與 B之間存在蘊含關系。 A?B當且僅當 A?B是永真公式 。 反對稱 ：若 A?B， B?A，則 A?B。 反對稱性的證明： 設 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個最基本的蘊含式 。 1. 真值表方法 例 4 證明 I14 ： (（ P∨ Q） ∧ （ P ? R） ∧ （ Q ? R） ) ? R 證明 令公式 F =（ （ P∨ Q） ∧ （ P?R） ∧ （ Q?R） ） ?R， 其真值表如下： 38 公式 F對任意的一組真值指派取值均為 1，故 F是重言式。 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為真。由此 ?P為真。 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至少一個為假 。 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?Q為真，故得 Q為真。 從而 P?（ Q?R）為假。 44 范式 一、 析取范式和合取范式 定義 912 一個命題公式若它具有P1*∧P 2*∧ … ∧P n*的形式（ n≥1 ），其中 Pi*是命題變元 Pi或其否定 172。 例如 ,172。 定義 913 一個命題公式若具有P1*∨P 2*∨ … ∨P n*（ n≥1 ）的形式，其中 P*i是命題變元 Pi或是其否定 172。 例如 , 172。R是由命題變元 P、 Q、 R組成的一質析取式。P 。P 。 (反證法 ) 假設 A式中不同時包含任一命題變元及其否定 ， 則在 A中，當 Pi*為 Pi時指派 Pi取 0，當 Pi*為 172。(i =1,2,… n).這樣的一組真值指派使 A的真值取 0，這與 A為永真式矛盾。P 2∨ (P1,P2,P3)=(0,1,0)的指派，使 A的真值為 0. 充分性 ：設 A含命題變元 Pi和 172。P i是永真式， 由結合律和零一律， A的真值必為 1，故 A也是永真式。即具有 A1∨A 2∨ … ∨A n(n≥1) 的形式的公式，其中 Ai是質合取式。 定義 915 質析取式的合取稱為合取范式。 例如 ， F2=?P∧(P∨Q)∧R∧(P∨ ?Q∨R) 是一合取范式。 47 二、求公式的析取范式和合取范式 任何一個命題公式都可以變換為與它等值的析取范式或合取范式。 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