離散數學第一章命題演算基礎-真假性.ppt

《離散數學第一章命題演算基礎-真假性.ppt》由會員分享，可在線閱讀，更多相關《離散數學第一章命題演算基礎-真假性.ppt（43頁珍藏版）》請在裝配圖網上搜索。

第一章命題演算基礎 1 1命題和聯結詞1 2真假性1 2 1解釋1 2 2等價公式1 2 3聯結詞的完備集1 2 4對偶式和內否式1 3范式及其應用 完全解釋 部分解釋 定義 設n元公式 中所有的不同的命題變元為P1 Pn如果對每個命題變元均給予一個確定的值 則稱對公式 給了一個完全解釋 如果僅對部分變元給予確定的值 則稱對公式 給了一個部分解釋 n元公式 有2n個完全解釋 例考察公式 P Q R 成真解釋與成假解釋 定義 對于任何公式 凡使得 取真值的解釋 不管是完全解釋還是部分解釋 均稱為 的成真解釋 定義 對于任何公式 凡使得 取假值的解釋 不管是完全解釋還是部分解釋 均稱為 的成假解釋 例考察公式 P Q R 永真公式與永假公式 定義 如果一個公式的所有完全解釋均為成真解釋 則稱該公式為永真公式或稱為重言式 定義 如果一個公式的所有完全解釋均為成假解釋 則稱該公式為永假公式或稱為予盾式 例由定義可知 P P為永假公式 P P為永真公式 可滿足公式與非永真公式 定義 如果一個公式存在成真解釋 則稱該公式為可滿足公式 如果一個公式存在成假解釋 則稱該公式為非永真公式 例由定義可知 P P永假公式P P永真公式P Q可滿足公式 非永真公式P Q可滿足公式 非永真公式 第一章命題演算基礎 1 1命題和聯結詞1 2真假性1 2 1解釋1 2 2等價公式1 2 3聯結詞的完備集1 2 4對偶式和內否式1 3范式及其應用 邏輯等價 定義 給定兩個公式 和 設P1 P2 Pn為 和 的所有命題變元 那么 和 有2n個解釋 如果對每個解釋 和 永取相同的真假值 則稱 和 是邏輯等價的 記為 八組重要的等價公式 雙重否定律 P 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 Q Q PP Q Q P 八組重要的等價公式 等冪律P P PP P PP P TP P T等值公式P Q P QP Q P Q Q P P Q P Q P Q P Q P Q P Q P Q P Q 八組重要的等價公式 部份解釋P T PP F FP T TP F PT P PF P TP T TP F PT P PF P P吸收律P P Q PP P Q P 例判斷下列公式的類型 q p q p 永真 解 q p q p q p q p q p p q T所以 它是永真的 例判斷下列公式的類型 p p q q r 永假 解 p p q q r T q q r q q r F r F所以 它是永假的 例判斷下列公式的類型 p q p 可滿足 解 p q p p q p p所以 它是可滿足的 成真解釋和成假解釋的求解方法 1 否定深入 即把否定詞一直深入至命題變元上 2 部分解釋 選定某個出現次數最多的變元對它作真或假的兩種解釋從而得公式 3 化簡 4 依次類推 直至產生公式的所有解釋 例 p7 試判定公式 P Q Q P R 的永真性和可滿足性 解1 否定深入原式 P Q Q P R 對P T進行解釋并化簡 結果見教材 例 p7 P Q Q P R 解2 在否定深入的基礎上對P F進行解釋并化簡 原式 F Q Q F R Q F R Q RQ T時 原式 T R R 于是R T時 原式 FR F時 原式 T因此 公式存在成真解釋 P Q R F T F 公式存在成假解釋 P Q R F T T 故公式可滿足但非永真 例 p7 P Q Q P R 解3 所以 公式存在成真解釋 T T T F F F T F F F T 公式存在成假解釋 T F T F T T F F F 故公式可滿足但非永真 例試求下列公式的成真解釋和成假解釋 P Q Q R P 解 當P T時 原式 T Q Q R T Q Q R Q R當P F時 原式 F Q Q R F T Q F Q由上可知 公式不是永真公式 是可滿足的 成真解釋為 P Q R T F F F T 成假解釋為 P Q R T T T T F T T T F F F 第一章命題演算基礎 1 1命題和聯結詞1 2真假性1 2 1解釋1 2 2等價公式1 2 3聯結詞的完備集1 2 4對偶式和內否式1 3范式及其應用 聯結詞的完備集 定義設S是聯結詞的集合 如果對任何命題演算公式均可以由S中的聯結詞表示出來的公式與之等價 則說S是聯結詞的完備集 由聯結詞的定義知 聯結詞集合 是完備的 定理1聯結詞的集合 是完備的 證明 因為P Q P QP 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 PQP QTTFTFTFTTFFT 定理2 p8 聯結詞的集合 是完備的 證明 顯然 有 P P PP Q P Q 所以 可以表示集合 又因為 是完備的 即任何公式 均可以由集合 中的聯結詞表達出來的公式與之等價 所以任何公式 均可以由集合 中的聯結詞表達出來的公式與之等價 故集合 是完備的 或非P Q P Q 定理 聯結詞的集合 是完備的 例 p8 試證明聯結詞集合 不完備 證明 假設 是完備的根據完備性的定義知 P Q1 Q2 Q3 Qn當P Q1 Q2 Q3 Qn全取為真時 公式左邊 F 公式右邊 T 顯然矛盾 故聯結詞集合 不完備 第一章命題演算基礎 1 1命題和聯結詞1 2真假性1 2 1解釋1 2 2等價公式1 2 3聯結詞的完備集1 2 4對偶式和內否式1 3范式及其應用 對偶式的定義 定義 將任何一個不含蘊含詞和等價詞的命題演算公式 中的 換為 換為 后所得的公式稱為 的對偶式 記為 例已知公式 P Q R S 則 P Q R S P Q R S 例求如下公式 的對偶式 P R P Q R 解 P Q P QP Q P Q P Q P R P Q R P Q R P R P Q R P Q R 注意 求合式公式的對偶式時 應先消去公式中的蘊含詞和等價詞 內否式的定義 定義 將任何命題演算公式 中的所有肯定形式換為否定形式 否定形式換為肯定形式后所得的公式稱為 的內否式 記為 例如公式 P Q R S 則 P Q R S P Q R S 例 P R P Q R 求公式 的對偶式與內否式 解 P Q P QP Q P Q P Q P R P Q R P Q R P R P Q R P Q R P R P Q R P Q R 例 P Q Q R P 試寫出公式 的對偶式和內否式解 因為P Q P Q 所以 P Q Q R P 于是 P Q Q R P P Q Q R P 雙重對偶式和內否式 性質1 例 P Q Q R P P Q Q R P P Q Q R P P Q Q R P P Q Q R P 合取與析取的對偶式和內否式 性質2 A B A B A B A B A B A B A B A B 對偶式和內否式的否定 定理1 p9 A A A A 證明可以模仿定理2的證明進行 省略 約定在討論對偶式和內否式的定理時 命題公式中僅含有 和 三個聯結詞 即應先消去公式中的蘊含詞和等價詞 定理2 p9 A A 證明 對公式A中出現的聯結詞的個數n進行歸納證明奠基 當n 0時A中無聯結詞 便有A P 從而有 A P 且A P 所以A P A 即定理成立 歸納 設n k時定理成立 考察n k 1 1 A中至少有一個聯結詞 可分為下面三種情形 A A1 A A1 A2 A A1 A2其中A1 A2中的聯結詞個數 k 定理2的證明 續(xù) 依歸納假設 A1 A1 A2 A2 當A A1時 A A1 A1 歸納假設 A1 定理1 A 當A A1 A2時 A A1 A2 A1 A2等值公式 A1 A2 歸納假設 A1 A2 內否的定義 A1 A2 對偶的定義 A 同理可證當當A A1 A2時結論成立 數學歸納法知 定理得證 勘誤 定理3 定理4 定理3A和A 既同永真又同可滿足 定理4A B和B A 既同永真又同可滿足 A B和A B 既同永真又同可滿足 不難證明 證明省略 第一章命題演算基礎 1 1命題和聯結詞1 2真假性1 2 1解釋1 2 2等價公式1 2 3聯結詞的完備集1 2 4對偶式和內否式1 3范式及其應用