【文章內容簡介】 （ ┐ A?┐C ） ?B ? ┐ （ A?C） ?B ? A?C→B 返回性質 返回第三節(jié)目錄 第三節(jié) 重言式與蘊含式 四． 對 偶 原 理 定義：設命題公式 A， 其中僅有聯(lián)結詞 ┐ ， ?， ?， 在 A中將 ?， ?， F， T分別換以 ?， ?， T， F得出公 式 A*， 則 A*稱為 A的對偶公式 。 第三節(jié) 重言式與蘊含式 四． 對 偶 原 理 注意 :(A*)*=A 例 1. (┐P ?(Q?R)) * = ┐P ?(Q?R) 返回對偶原理 1. 對 偶 公 式 如 A， A*是對偶式， P1， P2， P3…… .Pn出現(xiàn)于 A和 A*所有命題變元。 第三節(jié) 重言式與蘊含式 四． 對 偶 原 理 則 ┐ A(P1， P2， P3…… .Pn） ? A*（ ┐ P1， ┐ P2， ┐ P3…… .┐Pn ） 說明：因為 ┐ (P?Q)?(┐P ?┐Q) ┐(P ?Q)?┐P ?┐Q 所以 ┐ A（ P1， P2， P3…… Pn） ? A*（ ┐ P1， ┐ P2， ┐ P3…… .┐Pn ） 例題 返回對偶原理 2. 定 理 1 2. 定 理 1 例 題 例： A （ P1， P2， P3 ） = ┐P1 ?（ P2 ? P3） 因為 ┐ A （ P1， P2， P3 ） 第三節(jié) 重言式與蘊含式 四． 對 偶 原 理 ? ┐ （ ┐ P1 ?（ P2 ? P3） ） ? ┐ ┐ P1 ? ┐ （ P2 ? P3） ? ┐ （ ┐ P1） ? （ ┐ P2 ? ┐P3 ） 所以 A* ( ┐P1 ， ┐ P2， ┐ P3 ) ? ┐( ┐P1 ) ? ( ┐P2 ? ┐P3 ) 即： ┐ A（ P1， P2， P3） ? A*（ ┐ P1， ┐ P2， ┐ P3） 返回定理 1 定理 2：對偶原理，若 A?B，則 A*?B*， A， B僅由 ┐ ， ?， ?構成。 第三節(jié) 重言式與蘊含式 四． 對 偶 原 理 證： 因為 A (P1， P2， P3…… .Pn) ? B (P1， P2， P3…… .Pn) 則 A (P1， P2， P3…… .Pn) ? B (P1， P2， P3…… .Pn)永真 所以： ┐ A (P1， P2， P3…… .Pn) ? ┐ B (P1， P2， P3…… .Pn)永真 由定理 1 A* (┐P1 ， ┐ P2， ┐ P3… .┐Pn) ? B* (┐P1 ， ┐ P2， ┐ P3… .┐Pn) 永真 以 ┐ Pi代 Pi， i=1， 2……… n則 A* (P1， P2， P3…… .Pn) ? B* (P1， P2， P3…… .Pn)永真 故 A* ? B* 返回對偶原理 定理 3 例題 3. 對 偶 原 理 3. 定 理 2 例 題 例如： 因為： P?(P?Q)?P 第三節(jié) 重言式與蘊含式 四． 對 偶 原 理 由對偶原理 : P?(P?Q) ?P 返回定理 2 3. 定 理 3 定理 3：若 A?B，則 B*?A*。 A， B僅由 ┐ ， ?， ?構成。 證： 因為 A?B， 所以 A(P1， P2， P3…… .Pn) → B(P1 ， P2， P3…… .Pn)永真 由逆反律： ┐ B(P1， P2， P3…… .Pn) → ┐A(P1 ， P2， P3…… .Pn)永真 由對偶原理： B*(P1， P2， P3…… .Pn) → A *(P1， P2， P3…… .Pn)永真 以 Pi代 ┐ Pi， i=1， 2……… n B*(P1， P2， P3…… .Pn) → A *(P1， P2， P3…… .Pn)永真 所以 B* ? A* 注： 存在大量互不相同的命題公式，實際上互為等價 有必要引入標準形式。 返回對偶原理 第三節(jié) 重言式與蘊含式 四． 對 偶 原 理 一 .析取范式和合取范式 二 .主析取范式和主合取范式 第三節(jié)目錄 三 .主析取范式的個數(shù) 第五節(jié)目錄 第一章第四節(jié)目錄 第 4節(jié) 范 式 合取式稱為積 ,析取式稱為和 2. 析 取 范 式 定義：命題公式 A的析取范式記為 A?A1 ? A2 ? …... ? An， 其中， n大于等于 1， Ai是合取式（ ┐ ， ? ） 第 4節(jié) 范 式 一 .析取范式和合取范式 定理 1：任何命題公式都可化為析取范式 證： → ， ? 用 ?， ┐和 ?表達，括號可通過德 .摩根定律消去 其中（ P→Q ?┐P ?Q P?Q?（ P?Q） ?(┐P ?┐Q ） 再利用 ? 在 ?上的分配律： （ P ? （ Q ? R） ?（ P ? Q） ? （ P ? R））可得合 取范式 注：運算符最少的稱為最簡析取范式 方法見 數(shù)字邏輯 例題 返回第四節(jié)目錄 例 1. 求 P?（ P→ Q） 的析取范式 解 例 2. 求 ┐（ P?Q） ?（ P?Q）的最簡析取范式 解 注意： 1. 析取范式不是唯一的。 第 4節(jié) 范 式 一 .析取范式和合取范式 2. 若給定公式的析取范式中，其中的每個合取式 都是永假式，則該式必是永假式 。 返回析取范式 求 P?（ P→ Q） 的析取范式 解： P?（ P→Q ） ? P?（ ┐ P?Q） ?（ P?┐P ） ?（ P?Q） ?（ P?Q） 第 4節(jié) 范 式 一 .析取范式和合取范式 返回析取范式例題 析取范式例題 1解答 析取范式例題 2解答 求 ┐（ P?Q） ?（ P?Q）的最簡析取范式 解： ┐ （ P?Q） ?（ P?Q） ?(┐(P ?Q)?(P?Q))?((P?Q)?┐(P ?Q)) ?((P?Q) ? ┐P ?┐Q)) ?((P?Q)?(┐P ?┐Q)) ?（ P?┐Q ） ?（ Q?┐P ） 第 4節(jié) 范 式 一 .析取范式和合取范式 返回析取范式例題 3． 合 取 范 式 定義：命題公式 A的合取范式： 第 4節(jié) 范 式 一 .析取范式和合取范式 注：若析取式都為永真式，合取范式才是永真式。 記為 A1?A2?…….. ?An ，其中 n=1， Ai是析取式 證明合取范式 例題 返回第四節(jié)目錄 例：求 ┐ （ P?Q） ? （ P?Q）的合取范式 解： ┐ （ P?Q） ? （ P?Q） ? ┐ (P ? Q)?(P ? Q)?(P ? Q)?┐( P ? Q) ? ┐P ?┐Q ?P?Q ?((P ? Q)?(┐P ? ┐Q)) ? (P ? Q)?(┐P ? ┐Q) 第 4節(jié) 范 式 一 .析取范式和合取范式 返回合取范式 合取范式例題 1. 主 析 取 范 式 定義 1：在 n個變元的合取式中，若每一個變元與 其否定不同時存在，且二者之中出現(xiàn)一 次且僅出現(xiàn)一次，則這種 合取式 稱為 極小項 。 第 4節(jié) 范 式 二 .主析取范式和主合取范式 n個變元可構成 2n個不同的極小項。 例題 返回第四節(jié)目錄 例 :極小項 真值指派 編碼 極小項真值 ┐ P?┐Q ?┐R 000 m0 1 ┐P ?┐Q ?R 001 m1 1 ┐P ?Q?┐R 010 m2 1 ┐P ?Q?R 011 m3 1 P?┐Q ?┐R 100 m4 1 P?┐Q ?R 101 m5 1 P?Q?┐R 110 m6 1 P?Q?R 111 m7 1 第 4節(jié) 范 式 二 .主析取范式和主合取范式 返回主析取范式 標記法 標記法 : 編碼原則 :編碼指派當且僅當使該極小項真值為真。 n個變元的極小項 m0 ?┐P1 ?┐P2 ?………… . ?┐Pn m1 ?┐P1 ?┐P2 ?………… . ?P ………………………………… m2n 1?P1?P2?………… . ?Pn 第 4節(jié) 范 式 二 .主析取范式和主合取范式 定義 2：一個由極小項之和組成的公式，若與 wff A等價， 則稱為 A的 主析取范式 。 返回主析取范式 2． WffA化為主析取范式方法 1 ① wffA?析取范式 ?主析取范式 例： A?P?Q?R ?P?Q?（ R?┐R ） ?（ P?┐P ） ?（ Q?┐Q ） ? R ? m7 ?m6 ? m7 ? m5 ?m3 ? m1 ?∑(1 ， 3， 5， 6， 7) ② 第 4節(jié) 范 式 二 .主析取范式和主合取范式 返回第四節(jié)目錄 2． WffA如何化為主析取范式方法 2 ② 定理：已知命題公式 A(P1， P2， …… Pn), 第 4節(jié) 范 式 二 .主析取范式和主合取范式 P1， P2， …… Pn是其中 n個命題變元，則能夠 直接構成與其等價的主析取范式。 證明：在 A的真值表中，對于 A的每一個真值 T, 都選取一個相應的極小項，這些極小項之和，構 成一個主析取范式，此范式與 A有相同的真值表， 故該主析取范式與命題公式 A等價。 因命題公式 A的真值表是唯一的，故命題公式 A的