【正文】 式。 16 二、真值指派 命題公式代表一個命題，但只有當公式中的每一個命題變元都用一個確定的命題代入時，命題公式才有確定的真值，成為命題。 定義 9—7 設 F為含有命題變元 P1， P2， … ,Pn的命題公式，對 P1， P2， … ,Pn分別指定一個真值 ,稱為對公式 F的一組 真值指派 。 公式與其命題變元之間的真值關系，可以用真值表的方法表示出來。 17 例 2 給 出公式 F=(（ P∨Q ） ?（ Q∧R ） )? (P∧ 172。R）的真值表。 解 公式 F的真值表如下： P QR 172。R P∨ Q Q∧ R (P∨ Q)→(Q∧ R) P∧ 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的真值恒為假，則稱公式 F為 矛盾式 （或 永假公式 ），常用“ 0”表示。如果至少有一組真值指派使公式 F的真值為真，則稱 F為 可滿足公式 。 例 3 構造下列命題公式的真值表，并判斷它們是何種類型的公式 （ 1）（ 172。P?Q ） ? 172。（ P?Q ）； （ 2）（ Q→P ） ∧ （ 172。P ∧ Q）； （ 3）（（ P∨Q ） → （ Q∧R ）） → （ P∧ 172。R）。 19 解 令 F1=（ 172。P? Q） ? 172。（ P ? Q）， F2=（ Q→ P） ∧ （ 172。 P∧Q ） F1和 F2的真值表如下： P Q 172。P 172。P?Q P ?Q 172。(P→Q) F1 Q→P 172。P∧ Q F2 0 0 1 0 1 0 1 1 0 0 0 1 1 1 0 1 1 0 1 0 1 0 0 1 0 1 1 1 0 0 1 1 0 0 1 0 1 1 0 0 由上可知： F1是 重言式 , F2是 矛盾式。 (3)的真值表如第 4頁所示，它是可滿足公式。 20 命題公式的等值關系和蘊含關系 一、命題公式的等值關系 定義 99 設 A和 B是兩個命題公式 , P1, P2, …, P n 是所有出現(xiàn)于 A和 B中的命題變元，如果對于 P1, P2, …, P n 的任一組真值指派， A和 B的真值都相同 ,則稱公式 A和 B等值 ，記為 A ? B,稱 A?B為等值式 。 注意 ： （ 1）符號 “ ?” 與 “ ? ” 的區(qū)別與聯(lián)系。 “?”不是聯(lián)結詞， A?B不表示一個公式，它表示兩個公式間的一種關系，即等值關系。 “? ”是聯(lián)結詞， A? B是一個公式。 A?B當且僅當 A?B 是永真公式。 21 （ 2） 可以驗證等值關系是等價關系。 即 自反性 ：對任意公式 A，有 A?A。 對稱性 ：對任意公式 A， B，若 A?B，則B?A。 可傳遞性 ：對任意公式 A、 B、 C，若 A?B，B?C，則 A?C。 （ 3）當 A是重言式時， A?1；當 A是矛盾式時，則 A?0。 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 同一律 P∨ ?P?1 互否律 P∧ ?P?0 互否律 ?（ ?P） ?P 雙重否定律 P∨ P?P 等冪律 P∧ P ?P 等冪律 23 編號 公 式 E8 E8ノ E9 E9ノ E10 E10ノE11 E12 E13 E14 E15 P∨ 1?1 零一律 P∧ 0?0 零一律 P∨ （ P∧ Q） ?P 吸收律 P∧ （ P∨ Q） ?P 吸收律 ?（ P∨ Q） ??P∧ ?Q 德 .摩根定律 ?（ P∧ Q） ??P∨ ?Q 德 .摩根定律 P?Q??P∨ Q P?Q ? (P∧ Q)∨ (?P∧ ?Q) P? (Q?R) ? (P∧ Q) ? R P?Q ? (P?Q)∧ (Q?P) P?Q??Q??P 24 三 、 等值式的判別 有兩種方法：真值表方法 ， 命題演算方法 真值表方法 例 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。 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不成立 。 1 0 1 1 0 0 1 1 1 27 (1) 代入規(guī)則 代入規(guī)則 對于重言式中的任一命題變元出現(xiàn)的每一處均用同一命題公式代入，得到的仍是重言式。 2．等值演算方法 例如 F=（ P?Q） ? （ ?Q??P）是重言式，若 用公式 A∧ B代換命題變元 P得公式 F1=（（ A∧ B） ?Q） ? （ ?Q??（ A∧ B））， F1仍是重言式。 注意：因為 A ? B當且僅當 A ? B 是重言式。所以，若對于等值式中的任一命題變元出現(xiàn)的每一處均用同一命題公式代入，則得到的仍是等值式。 28 (2) 置 換規(guī)則 定義 910 設 C是命題公式 A的一部分（即 C是公式 A中連續(xù)的幾個符號），且 C本身也是一個命題公式，則稱 C為公式 A的 子公式。 例如 設公式 A=（ ?P∨Q ） ?（（ P?Q） ∨ （ R∧ ?S））。 則 ?P∨ Q， P?Q，（ P?Q） ∨ （ R∧ ?S）等均是 A的子公式， 但 ?P∨ ， P?和 ?Q等均不是 A的子公式， 置換規(guī)則 設 C是公式 A的子公式， C?D。如果將公式 A中的子公式 C置換成公式 D之后，得到的公式是 B，則 A?B。 29 (3) 等值演算 等值演算是指利用已知的一些等值式，根據(jù)置換規(guī)則、代入規(guī)則以及等值關系的可傳遞性推導出另外一些等值式的過程。 由代入規(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 判別下列公式的類型。 （ 1） Q∧ ? (?P?（ ?P∧ Q） ) （ 2）（ P?Q） ∧ ?P 解 （ 1） Q∧ ?（ ?P?（ ?P∧ Q） ） ?Q∧ ?（ P∨ （ ?P∧ Q） ） E11,E6 ?Q∧ ?（ （ P∨ ?P） ∧ （ P∨ Q） ） E3ノ ?Q∧ ?（ 1∧ （ P∨ Q） ） E5 ?Q∧ ?（ P∨ Q） E4ノ