【正文】 ?(P∧ ?P) ∨ (P∧ ?Q)∨ (?P∧ Q)∨ (Q∧ ?Q)（析取范式） E3 50 定理 95 （ 1）公式 A為永真式的充分必要條件是， A的合取范式中每一質(zhì)析取式至少包含一對互為否定的析取項。 按下列步驟進(jìn)行： （ 1）利用 E11， E12和 E14消去公式中的運算符“ ?” 和 “ ?” ； (2) 利用德 ?摩根定律將否定符號 “ ?” 向內(nèi)深入，使之只作用于命題變元； （ 3）利用雙重否定律 E6將 ? (?P)置換成 P； （ 4）利用分配律、結(jié)合律將公式歸約為合取范式或析取范式。 F3=(?P∨R∨Q)∧(P∨Q)∧R∧(P∨ ?R)也是一合取范式。 即具有 A1∧A 2∧ … ∧A n (n≥1) 的形式的公式，其中 Ai是質(zhì)析取式。 例如 ， F1=P∨(P∧Q)∨R∨( ?P∧ ?Q∧R) 是一析取范式。 46 定義 914 質(zhì)合取式的析取稱為析取范式。P i，而 Pi∨ 172。 例如 A=P1∨ 172。P i時，指派 Pi取 1。 證明 （ 2） 必要性 ：假設(shè) A= P1*∨ P2*∨ … ∨ Pn*為一質(zhì)析取式，且 A為一永真式。 （ 2） 一質(zhì)析取式為永真式的充分必要條件是，它同時包含某個命題變元 P及其否定 172。 45 定理 94 （ 1） 一質(zhì)合取式為永假式的充分必要條件是，它同時包含某個命題變元 P及其否定 172。 Q∨P∨ 172。Pi ，則稱其為 質(zhì)析取式 。P∧Q∧R∧S 是由命題變元 P、 Q、 R、 S組成的一質(zhì)合取式。Pi ，則稱其為 質(zhì)合取式 。 因此蘊含式成立。 于是 P為真， Q?R為假。 由 P?R為假 ,得 P為真， R為假。 由此可知 P?Q與 R?S中至少一個為假 , 因此 (P?Q)?(R?S)為假 . 故上述蘊含式成立 。 故蘊含式 I12 成立。 于是 Q為假，因而 P也為假。 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是否也為真。 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”是否成立的問題可轉(zhuǎn)化為判定 A ? B是否為重言式，有下述判定方法： （ 1）真值表； （ 2）等值演算； （ 3）假定前件 A為真； （ 4）假定后件 B為假。 傳遞性 ：若 A?B， B?C，則 A?C。 33 A?B是偏序關(guān)系 即 自反性 ： A?A。 “?”是聯(lián)系詞， A?B是一個公式。 注意： 符號 “ ?” 和 “ ?” 的區(qū)別和聯(lián)系與符號 “ ?” 與 “ ? ” 的區(qū)別和聯(lián)系類似。 32 三、命題公式的蘊含關(guān)系 定義 911 設(shè) A， B是兩個公式，若公式 A?B是重言式，即 A?B?1，則稱公式 A蘊含公式 B，記作 A?B。 （ 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ノ ?Q∧ ?P∧ ?Q E10 ?（ Q∧ ?Q） ∧ ?P E1ノ ,E2 ?0 E5ノ ,E8ノ 所以 Q∧ ? (?P? (?P∧ Q))是矛盾式。 29 (3) 等值演算 等值演算是指利用已知的一些等值式，根據(jù)置換規(guī)則、代入規(guī)則以及等值關(guān)系的可傳遞性推導(dǎo)出另外一些等值式的過程。 則 ?P∨ Q， P?Q，（ P?Q） ∨ （ R∧ ?S）等均是 A的子公式， 但 ?P∨ ， P?和 ?Q等均不是 A的子公式， 置換規(guī)則 設(shè) C是公式 A的子公式， C?D。 28 (2) 置 換規(guī)則 定義 910 設(shè) C是命題公式 A的一部分（即 C是公式 A中連續(xù)的幾個符號），且 C本身也是一個命題公式，則稱 C為公式 A的 子公式。 注意：因為 A ? B當(dāng)且僅當(dāng) A ? B 是重言式。 1 0 1 1 0 0 1 1 1 27 (1) 代入規(guī)則 代入規(guī)則 對于重言式中的任一命題變元出現(xiàn)的每一處均用同一命題公式代入，得到的仍是重言式。 22 二 、 基本的等值式 設(shè) 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) 結(jié)合律 (P∧ Q)∧ R ?P∧ (Q∧ R) 結(jié)合律 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， 構(gòu)造 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所標(biāo)記的列全為 1，因此 A?B。 可傳遞性 ：對任意公式 A、 B、 C，若 A?B，B?C，則 A?C。 即 自反性 ：對任意公式 A，有 A?A。 A?B當(dāng)且僅當(dāng) A?B 是永真公式。 “?”不是聯(lián)結(jié)詞， A?B不表示一個公式，它表示兩個公式間的一種關(guān)系，即等值關(guān)系。 20 命題公式的等值關(guān)系和蘊含關(guān)系 一、命題公式的等值關(guān)系 定義 99 設(shè) A和 B是兩個命題公式 , P1, P2, …, P n 是所有出現(xiàn)于 A和 B中的命題變元，如果對于 P1, P2, …, P n 的任一組真值指派， A和 B的真值都相同 ,則稱公式 A和 B等值 ，記為 A ? B,稱 A?B為等值式 。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是 矛盾式。P?Q P ?Q 172。 P∧Q ） F1和 F2的真值表如下： P Q 172。P? Q） ? 172。R）。（ P?Q ）； （ 2）（ Q→P ） ∧ （ 172。 例 3 構(gòu)造下列命題公式的真值表，并判斷它們是何種類型的公式 （ 1）（ 172。相反地，若對于 F所包含的命題變元的任何一組真值指派， F的真值恒為假，則稱公式 F為 矛盾式 （或 永假公式 ），常用“ 0”表示。R P∨ Q Q∧ R (P∨ Q)→(Q∧ R) P∧ 172。R）的真值表。 公式與其命題變元之間的真值關(guān)系，可以用真值表的方法表示出來。 16 二、真值指派 命題