【正文】 T F T F T T T T T 000 001 010 011 100 101 110 111 P?(Q?R) Q?R R Q P 河南工業(yè)大學(xué)離散數(shù)學(xué)課程組 57 二、 等價公式 例子 看下面三個公式的真值表 從真值表可以看出，不論對 P、 Q作何 指派 ，都使得 P?Q、 ?P∨ Q和 ?Q??P的真值相同，即它們的真值表完全相同，表明它們之間彼此 等價或邏輯相同 。 P Q P?Q T T T T F F F T T F F T P Q ?P∨ Q T T T T F F F T T F F T P Q ?Q??P T T T T F F F T T F F T 河南工業(yè)大學(xué)離散數(shù)學(xué)課程組 58 定義 ? A、 B是含有命題變元 P1,P2,…, Pn的命題公式，如不論對 P1, P2 , …, Pn作任何指派，都使得 A和B的 真值相同 ，則稱之為 A與 B等價 ，記作 A?B。 P Q P?Q ?P∨ Q ?Q??P T T T T T T F F F F F T T T T F F T T T ?顯然 P?Q??P∨ Q??Q??P 河南工業(yè)大學(xué)離散數(shù)學(xué)課程組 59 首先， ? G?H的結(jié)果仍是一個命題公式 。 G ? H 的結(jié)果 不是命題公式。 ? 雙條件詞 “ ?”是一種 命題 聯(lián)結(jié)詞 ，公式G?H是命題公式，其中 “ ?” 是一種邏輯運算， G?H的結(jié)果仍是一個命題公式 。 ? 邏輯等價 “ ?” 則是描述了兩個公式 G與 H之間的一種邏輯等價關(guān)系， G ? H表示 “ 命題公式 G等 價 于命題公式 H” ， G ? H 的結(jié)果不是命題公式。 其次， ? 如果要求用計算機來判斷命題公式 G、 H是否邏輯 等價，即 G ? H那是辦不到的 ， 然而計算機卻可 “ 計算 ” 公式 G?H是否是永真公式。 “ ?” 與“ ?” 的區(qū)別 河南工業(yè)大學(xué)離散數(shù)學(xué)課程組 60 重要的等價公式 ⑴ 對合律 ??P?P (雙否律 ) ⑵ 冪等律 P∨ P?P P∧ P?P ⑶ 結(jié)合律 (P∨ Q)∨ R ? P∨ (Q∨ R) (P∧ Q)∧ R ? P∧ (Q∧ R) ⑷ 交換律 P∨ Q?Q∨ P P∧ Q?Q∧ P ?下面給出一些常用的等值式，其中很多是通常所說的布爾代數(shù)或邏輯代數(shù)的主要組成部分。 河南工業(yè)大學(xué)離散數(shù)學(xué)課程組 61 二、 等價公式 ⑸ 分配律 P∨ (Q∧ R)?(P∨ Q)∧ (P∨ R) P∧ (Q∨ R)?(P∧ Q)∨ (P∧ R) ⑹ 吸收律 P∨ (P∧ Q)?P P∧ (P∨ Q)?P ⑺ 德 摩根定律 ?(P∨ Q)??P∧ ?Q ?(P∧ Q)??P∨ ?Q ⑻ 同一律 P∨ F?P P∧ T?P ⑼ 零律 P∨ T?T P∧ F?F ⑽ 互補律 P∨ ?P?T P∧ ?P?F P：今天下雨， Q：今天刮風(fēng)， ?(P∨ Q)：今天下雨或刮風(fēng)的否定， ?P ∧ ? Q：今天不下雨且今天不刮風(fēng)， ?(P ∧ Q)：今天下雨且刮風(fēng)的否定， ?P ∨ ? Q：今天不下雨或今天不刮風(fēng)， 河南工業(yè)大學(xué)離散數(shù)學(xué)課程組 62 二、 等價公式 P43 ⑾ P?Q??P∨ Q ⑿ P?Q??Q??P ⒀ P?Q ?(P?Q)∧ (Q?P) ⒁ P?Q ?(?P∨ Q)∧ (P∨ ?Q) ⒂ P?Q ?(P∧ Q)∨ (?P∧ ?Q ) ⒃ (P∧ Q)?R ?(P?Q)?R ?(P?Q)?(P?R) 河南工業(yè)大學(xué)離散數(shù)學(xué)課程組 63 等價公式的證明方法 怎樣證明公式是等價的 ? 方法 1：用真值表。 ? 方法 2：用重言式證明 （見下一節(jié)） ? 方法 3：用公式的等價變換。 ? 定義 如果 X是合式公式 A的一部分，且 X本身也是一合式公式，則稱 X為公式 A的 子公式 。 ? 如： A： (P ∧ Q) ∨ R中 P、 Q、 R、 P ∧ Q 河南工業(yè)大學(xué)離散數(shù)學(xué)課程組 64 定理 置換定律（等價代換定理）： ? 設(shè) X是合式公式 A的子公式， Y是一命題公式，若 X?Y，如果將 A中的 X用 Y來置換，則所得到公式 B與公式 A等價，即 A?B。 ? 從定理可見，一個命題公式 A，經(jīng)過多次的置換，所得到的新公式與原公式等價。 ? 等價代換定理的用途。 ? 驗證兩個命題公式等價。 ? 化簡命題公式。 ? 判斷命題公式的類型。 （見第五節(jié)） 河南工業(yè)大學(xué)離散數(shù)學(xué)課程組 65 等價代換定理用于證明公式的等價 ? 例題 1. 求證吸收律 P∧ (P∨ Q)?P ? 證明 ? P∧ (P∨ Q) ? ? (P∨ F)∧ (P∨ Q) (同一律 ) ? ?P∨ (F∧ Q) (分配律 ) ? ?P∨ F (零律 ) ? ?P (同一律 ) 河南工業(yè)大學(xué)離散數(shù)學(xué)課程組 66 等價代換定理用于證明公式的等價 ? 例題 2. 求證 (?P∨ Q)→(P ∧ Q) ?P ? 證明 ? (?P∨ Q)→(P ∧ Q) ? ??(?P∨ Q)∨ (P∧ Q) (公式 E16) ? ? (??P∧ ?Q)∨ (P∧ Q) (摩根定律 ) ? ? (P∧ ?Q)∨ (P∧ Q) (對合律 ) ? ?P∧ (?Q∨ Q) (分配律 ) ? ?P∧ T (互補律 ) ? ?P (同一律 ) ?公式E16 ： P?Q??P∨ Q 河南工業(yè)大學(xué)離散數(shù)學(xué)課程組 67 補充：等價代換定理用于化簡公式 ? 化簡語句：“不會休息的人也不會工作，沒有豐富知識的人也不會工作”。 ? 解：設(shè) P：某人會工作， Q：某人會休息， R：某人有豐富的知識 語句符號化為： (?Q→ ?P) ∧ (?R→ ?P) (?Q→ ?P) ∧ (?R→ ?P) ? ?(Q ∨ ?P) ∧ (R∨ ?P) ? ? ? P ∨ (Q∧ R) ? ? P →(Q ∧ R) ? 與語句“工作得好的人一定會休息并且有豐富的知識”，具有相同的邏輯含義。 公式 E16 ： P?Q??P∨ Q 河南工業(yè)大學(xué)離散數(shù)學(xué)課程組 68 練習(xí) ? 作業(yè)題： ? 第 12頁：（ 5）、（ 7） ? 第 17頁：（ 1） a)、 d) ? 第 18頁 ： （ 7） b)、 d)，（ 8）