【文章內(nèi)容簡介】 顧表 10個命題定律： 58 16 對偶與范式（續(xù)） ? 定義： 在給定的命題中，將聯(lián)結(jié)詞 ?換成 ?，將 ?換成 ?，若有特殊變元 F和 T也相互替代，所得公式 A*稱為 A的對偶式。 ? 顯然， A*與 A互為對偶式。 ? 例題 1. ? 例題 2. 定理： 設(shè) A*為 A的對偶式 ， P1,P2,… ,Pn是出現(xiàn)在 A和 A*中的 原子變元，則 ?A(P1,P2,… , Pn) ? A*(?P1,?P2,… , ?Pn) A(?P1,?P2,… , ?Pn) ? ?A*(P1,P2,… , Pn) 59 16 對偶與范式（續(xù)） ? 例題 4： p ↑ q 的對偶式是 p ↓ q 。 p ↓ q 的對偶式是 p ↑ q ? 永真式的對偶式是永假式，反之亦然； 定理： 設(shè) A*為 A的對偶式 ， P1,P2,… ,Pn是出現(xiàn)在公式 A和 B中 的原子變元，如果 A ? B，則 A* ? B*。 60 16 對偶與范式（續(xù)） 定義： 一個命題稱為 合取范式 ，當(dāng)且僅當(dāng)它具有如下的形式： A1?A2 ? … ? An， (n≥1) 其中 A1,A2,… ,An都是由命題變元或其否定所組成的析取式。 定義： 一個命題稱為 析取范式 ，當(dāng)且僅當(dāng)它具有如下的形式： A1?A2 ? … ? An， (n≥1) 其中 A1,A2,… ,An都是由命題變元或其否定所組成的合取式。 注意：一個命題的合取范式或析取范式不是唯一的。 61 16 對偶與范式（續(xù)） 求一個命題的合取范式或析取范式的步驟： (1) 將公式中的聯(lián)結(jié)詞化歸成 ?， ?及 ?。 (2) 利用德 .摩根定律將否定聯(lián)結(jié)詞 ?直接移到各命題變元之前。 (3) 利用分配律、結(jié)合律將公式歸約為合取范式或析取范式。 62 16 對偶與范式（續(xù)） 定義： n個命題變元的合取式稱為 布爾合取 （或 小項 ），其中每個變元與它的否定不能同時存在，但兩者必須出現(xiàn)且僅出現(xiàn)一次。 例如：兩個變元 P和 Q，其小項為： P?Q， P??Q， ?P?Q，?P??Q。 三個變元 P， Q， R的小項為： P ? Q ? R， P ? Q ? ?R， P ? ?Q ? R， ?P ? Q ? R ， ?P ? Q ? ?R ，?P ? ?Q ? R ， ?P ? ?Q ? R ， ?P ? ?Q ? ?R 。 一般說來， n個命題變元共有 2n個小項。 63 16 對偶與范式（續(xù)） 兩個變元 P和 Q的小項的真值表： P Q P?Q P??Q ?P?Q ?P??Q 1 1 1 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 1 64 16 對偶與范式（續(xù)） 三個變元 P， Q， R的小項的真值表： P Q R ?P ? ?Q ? ?R ?P ? ?Q ? R ?P ? Q ? ?R ?P ? Q ? R 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 1 1 0 0 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 1 0 0 0 0 0 1 1 1 0 0 0 0 65 16 對偶與范式（續(xù)） 三個變元 P， Q， R的小項的真值表 : P Q R P ? ?Q ? ? R P ? Q ? R P ? Q ? ?R P ? Q ? R 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 1 0 0 0 1 0 1 0 1 0 0 1 1 0 0 0 1 0 1 1 1 0 0 0 1 66 16 對偶與范式（續(xù)） 三個變元 P， Q， R的小項的真值表 : P Q R ?P ? ?Q ? ?R ?P ? ?Q ? R ?P ? Q ? ?R ?P ? Q ? R P ? ?Q ? ? R P ? Q ? R P ? Q ? ?R P ? Q ? R 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0 0 0 0 0 1 67 16 對偶與范式（續(xù)） 三個變元 P， Q， R的小項的編碼表 : m000＝ ?P ? ?Q ? ?R m001＝ ?P ? ?Q ? R m010＝ ?P ? Q ? ?R m011＝ ?P ? Q ? R m100＝ P ? ?Q ? ?R m101＝ P ? ? Q ? R m110＝ P ? Q ? ?R m111＝ P ? Q ? R 68 16 對偶與范式（續(xù)） 小項的性質(zhì) : （ 1）每一個小項當(dāng)其真值指派與編碼相同時，其真值為 T，在其余 2n1中指派情況下均為 F。 （ 2）任意兩個不同小項的合取式為永假。 （ 3）全體小項的析取式為永真，記為： 2101 210...nniim m m m T???? ? ? ??69 16 對偶與范式（續(xù)） 定義： 對于給定的命題公式，如果有一個等價公式，它僅由小項的析取所組成，則該等式稱為原式的主析取范式。 定理： 在真值表中，一個公式的真值為 T的指派所對應(yīng)的小項的析取，即為此公式的主析取范式。 例題 6： 給定 P ? Q， P ? Q和 ? (P ? Q)，求這些公式的主析取范式。 例題 7： 例題 8： 例題 9： 70 16 對偶與范式（續(xù)） 對于給定命題公式的主析取范式，如果將其命題變元的個數(shù)和出現(xiàn)自許固定后，則此公式的主析取范式就是 唯一 的。 定義： n個命題變元的析取式稱為 布爾析取 或 大項 。其中每個變元與它的否定不能同時存在，但兩者必須且僅出現(xiàn)一次。 71 16 對偶與范式（續(xù)） 大項的二進(jìn)制編碼： n=2: M00＝ P ? Q M01＝ P ? ?Q M10＝ ?P ? Q M11＝ ?P ? ?Q 72 16 對偶與范式（續(xù)） 大項的二進(jìn)制編碼： n=3: M000＝ P ? Q ? R M001＝ P ? Q ? ? R M010＝ P ? ?Q ? R M011＝ P ? ?Q ? ?R M100＝ ?P ? Q ? R M101＝ ?P ? Q ? ?R M110＝ ?P ? ?Q ? R M111＝ ?P ? ?Q ? ?R 73 16 對偶與范式（續(xù)） 大項的性質(zhì) : （ 1）每一個大項當(dāng)其真值指派與編碼相同時，其真值為 F，在其余 2n1中指派情況下均為 T。 （ 2）任意兩個不同大項的析取式為永真。 （ 3）全體大項的合取式為永假，記為： 2101 210...nniim m m m F???? ? ? ??74 16 對偶與范式（續(xù)） 定義： 對于給定的命題公式，如果有一個等價公式，它僅由大項的合取所組成，則該等式稱為原式的主合取范式。 定理： 在真值表中，一個公式的真值為 F的指派所對應(yīng)的大項的合取，即為此公式的主合取范式。 75 16 對偶與范式（續(xù)） 例題 10：利用真值表技術(shù)求 (P?Q) ?(?P?R)的主析取范式和主合取范式。 解： 公式 (P?Q) ?(?P?R)的真值表如下： P Q R ?P P ? Q ?P ? R (P?Q) ? (?P?R) T T T F T F T T T F F T F T T F T F F F F T F F F F F F F T T T F T T F T F T F F F F F T T F T T F F F T F F F 主和取范式： 主析取范式： 76 16 對偶與范式（續(xù)） P Q R ?P ? ?Q ? ?R ?P ? ?Q ? R ?P ? Q ? ?R ?P ? Q ? R P ? ?Q ? ? R P ? ? Q ? R P ? Q ? ?R P ? Q ? R 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 1 0 1 1 1 0 0 0 0 0 0 0 1 77 16 對偶與范式（續(xù)） 例題 11：將 (P?Q) ?(?P?R)化為主合取范式。 78 17 重言式與蘊(yùn)涵式 ? 定義： 給定一個命題，若無論對分量作怎樣的指派，其對應(yīng)的真值永遠(yuǎn)為 T，則稱該命題公式為重言式或永真公式。 ? 定義： 給定一個命題，若無論對分量作怎樣的指派，其對應(yīng)的真值永遠(yuǎn)為 F，則稱該命題公式為矛盾式或永假公式。 ? 定理： 任何兩個重言式的合取或析取仍然是一個重言式。 ? 定理： 一個重言式，對同一分量都用任何公式置換，其結(jié)果仍然是一個重言式。 ? 定理： 設(shè) A， B為兩個命題公式， A ? B 當(dāng)且僅當(dāng) A ? B為一個重言式。 79 17 重言式與蘊(yùn)涵式 ? 定義： A、 B是命題公式，當(dāng) A ?B為一個重言式時，我們稱“ A蘊(yùn)涵 B”，并且記做 A = B 。 ? 注： P =Q 與 Q = P 是不等價的。 ? 對 P =Q 來說： ? Q = P稱為它的 逆換式 。 ? ? P = ? Q稱為它的 反換式 。 ? ? Q = ? P稱為它的 逆反式 。 ? P ? Q ? ? Q ? ? P ? Q ? P ? ? P ? ? Q 逆反命題 80 17 重言式與蘊(yùn)涵式 14個常用蘊(yùn)涵命題： 序號 表達(dá)式 1 P ? P ＝ P 2 P ? P = P 3 P = P ? Q *4 ?P = P ? Q *5 Q = P ? Q *6 ?(P ? Q) = P *7 ?(P ? Q) = ?Q 8 P ? (P ? Q) = Q 9 ?Q ? (P ? Q) = ?P 81 17 重言式與蘊(yùn)涵式 14個常用蘊(yùn)涵命題（續(xù)）： 序號 表達(dá)式 10 ?P ? (P ? Q) ＝ Q 11 (P ? Q) ? (Q ? R) = P ? R 12 (P ? Q) ? (P ? R) ? (Q ? R) = R 13 (P ? Q) ? (R ? S) = (P ? R) ?(Q ? S) 14 (P ? Q) ? (Q ? R) = (P ? R) 82 17 重言式與蘊(yùn)涵式 ? 定理： 設(shè) P， Q為任意兩個命題公式， P ? Q 的充分必要條件是 P =Q 且 Q = P 。 ? 性質(zhì) 1. 設(shè) A,B為合式公式，若 A=B且 A是重言式，則 B也是 重言式。 ? 性質(zhì) 2. 若 A=B， B=C，則 A=C。 ? 性質(zhì) 3. 若 A=B且 A=C，則 A=(B ? C)。 ? 性質(zhì) 4. 若 A=B且 C=B，則 (A ? C)=B。 83 18 推理理論 定義： 設(shè) A和 C是兩個命題公式，當(dāng)且僅當(dāng) AC為一個重言式，即 A=C，稱 C是 A的有效結(jié)論?；?C可以由 A邏輯地推出。 推廣： 定義： 設(shè) H1,H2,… ,Hn,C是命題公式，當(dāng)且僅當(dāng) H1 ? H2 ? … ? Hn=C 稱 C是一組前提 H1,H2,… ,Hn的有效結(jié)論?；蚍Q C可以由 H1,H2,… ,Hn邏輯地推出。 判斷有效結(jié)論的過程叫做 論證過程 。 84 18 推理理論 （續(xù)） 三種基本論證過程方法： 真值表法、直接證法、間接證法。 （ 1）真值表法 例題 1. 一個統(tǒng)計表格的錯誤或者是由材料不可靠，或者是由于計算有錯誤。這份統(tǒng)計表格的錯誤不是由于材料不可靠，所以這統(tǒng)計表格的錯誤是由于計算有錯誤。 解：設(shè) P：統(tǒng)計表格的錯誤是由于材料不可靠。 Q：統(tǒng)計表格的錯誤是由于計算有錯誤。 前提： ?P ? (P ? Q) 結(jié)論： Q ?P ? (P ? Q)=Q 85 18 推理理論 （續(xù)） 解： 公式 ?P ? (P ? Q)的真值表如下： P Q ?P P