01-命題邏輯-14~15.ppt

第一章命題邏輯 2020年3月14日星期六 第四節(jié)對偶式與蘊涵式 第四節(jié)對偶式與蘊涵式一 對偶式定義 在給定的僅使用聯(lián)結(jié)詞 的命題公式A中 若把 和 互換 F和T互換 得到一個公式A 稱A 是A的對偶式 稱A和A 互為對偶式 2020年3月14日星期六 對偶式 例1 24求下列公式的對偶式 P Q R P TP Q P Q R P F P Q P Q P Q P Q 2020年3月14日星期六 對偶式 對偶定理 設(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 2020年3月14日星期六 A P1 P2 Pn A P1 P2 Pn 證明 設(shè)公式A中含有聯(lián)結(jié)詞 的數(shù)目為L當L 0時 A P1 A A P1 P1 P1 A P1 當L 1時 A P1 P2 或 P1 P2 或 P1 當A P1 P2 時 A P1 P2 A P1 P2 P1 P2 P1 P2 A P1 P2 當A P1 P2 時 A P1 P2 A P1 P2 P1 P2 P1 P2 A P1 P2 當A P1時 A P1 A P1 P1 A P1 2020年3月14日星期六 A P1 P2 Pn A P1 P2 Pn 設(shè)當L k 1時 k 1 2 時 A P1 P2 Pn A P1 P2 Pn 成立當L k時若A P1 P2 Pn A1 P1 P2 Pn A2 P1 P2 Pn 則LA1 LA2 k 1 由上面結(jié)論得 A1 P1 P2 Pn A1 P1 P2 Pn A2 P1 P2 Pn A2 P1 P2 Pn 2020年3月14日星期六 A P1 P2 Pn A P1 P2 Pn A P1 P2 Pn A1 P1 P2 Pn A2 P1 P2 Pn A1 P1 P2 Pn A2 P1 P2 Pn A1 P1 P2 Pn A2 P1 P2 Pn A P1 P2 Pn 2020年3月14日星期六 A P1 P2 Pn A P1 P2 Pn 同理 若A P1 P2 Pn A1 P1 P2 Pn A2 P1 P2 Pn 可證 A P1 P2 Pn A P1 P2 Pn 若A P1 P2 Pn A1 P1 P2 Pn 可證 A P1 P2 Pn A1 P1 P2 Pn A P1 P2 Pn 由上證明 可得當L K時 A P1 P2 Pn A P1 P2 Pn 證畢 2020年3月14日星期六 對偶式 例1 25設(shè)A P Q R P Q R 求證 A P Q R P Q R 證明 A P Q R P Q R P Q R 又因為 A P Q R A P Q R 所以 A P Q R P Q R 證畢 A P1 P2 Pn A P1 P2 Pn 2020年3月14日星期六 對偶式 對偶定理 設(shè)A和B是兩個命題公式 若A B 則A B 證明 A B意味著A P1 P2 Pn B P1 P2 Pn 永真 所以 A P1 P2 Pn B P1 P2 Pn 永真 因為 A P1 P2 Pn A P1 P2 Pn B P1 P2 Pn B P1 P2 Pn 因此A P1 P2 Pn B P1 P2 Pn 永真 用 Pi代入Pi得到A P1 Pn B P1 Pn 永真因此A B 證畢 2020年3月14日星期六 對偶式 例1 26求證 P Q P Q P Q證明 P Q P Q P Q P Q E1E11 P P Q Q P Q E2E4 T P Q E6E10 P QE7 2020年3月14日星期六 對偶式 例1 27求證 P Q P Q P Q證明 由前面證明得知 P Q P Q P Q P Q P Q P Q P Q P Q P Q證畢 設(shè)A和B是兩個命題公式 若A B 則A B 2020年3月14日星期六 蘊涵式 二 蘊涵式定義 設(shè)A和B是兩個命題公式 若A B是永真式 則稱A蘊涵B 記做A B 稱A B為蘊涵式或條件永真式 與 的區(qū)別 是邏輯聯(lián)結(jié)詞 出現(xiàn)在命題公式中 是一個符號 表示兩個命題公式之間的蘊涵關(guān)系 2020年3月14日星期六 蘊涵式 蘊涵式有以下性質(zhì) 自反性對任意公式A 有A A傳遞性對任意公式A B C 若有A B B C 則有A C對任意公式A B C 若有A B A C則A B C 對任意公式A B C 若有A C B C則 A B C 2020年3月14日星期六 蘊涵式 等價式和蘊涵式的關(guān)系 定理 設(shè)A和B是兩個命題公式 A B的充要條件是 A B且B A證明 1 若A B 則A B是永真式 因為 A B A B B A 所以 A B B A 是永真式所以 A B 和 B A 都是永真式所以A B且B A 必要條件得證 P QP是Q的充分條件 Q是P的必要條件 2020年3月14日星期六 蘊涵式 證明 2 若A B且B A 則 A B 和 B A 都是永真式 因為 A B A B B A 所以A B是永真式所以A B 充分條件得證 因此 A B的充要條件是 A B且B A 證畢 2020年3月14日星期六 蘊涵式的證明 蘊涵式的證明方法 真值表法若前件為真 能推得后件為真 則此蘊涵式為真若后件為假 能推得前件為假 則此蘊涵式為真 指明兩種證明思路 2020年3月14日星期六 蘊涵式的證明 例1 28求證 Q P Q P證明 1 真值表法 2020年3月14日星期六 蘊涵式的證明 2 前件真則后件真 Q P Q P 設(shè) Q P Q 為T 則 Q為T P Q也為T可得到 Q為F 故P為F 因此 P為T 得證3 后件假則前件假設(shè) P為F 則P為T若Q為T 則 Q為F 則 Q P Q 為F若Q為F 則P Q為F 則 Q P Q 為F 證畢 2020年3月14日星期六 基本蘊涵公式 基本蘊涵公式A B C D代表任意命題I1化簡式A B AI2A B BI3附加式A A B A B AI4附加式變形 A A BI5B A BI6化簡式變形 A B AI7 A B B 2020年3月14日星期六 基本蘊涵公式 I8假言推論A A B BI9拒取式 B A B AI10析取三段論 A A B BI11條件三段論 A B B C A CI12雙條件三段論 A B B C A CI13合取構(gòu)造二難 A B C D A C B D A B C D代表任意命題 如果A則B A 所以B 如果A則B B 所以 A 要么A 要么B A 所以B 2020年3月14日星期六 基本蘊涵公式 I14析取構(gòu)造二難 A B C D A C B D特別的 當B D時 有 A B C B A C B A B C B A C BI15前后件附加A B A C B C A B A C B C A B C D代表任意命題 如果A則B 并且如果C則D 但是要幺A要幺C 所以 要幺B要幺D 2020年3月14日星期六 基本蘊涵公式 補充 I16A B B C A C I17 A B C D A C B D I18A B A BA B B AI19A B A B A B C D代表任意命題 A和B分別為真 所以A B為真 2020年3月14日星期六 蘊涵式 例1 29求證 P Q P Q證明 1 P Q P Q P Q P Q P Q P Q P Q Q T2 P Q QI2 P QI5 指明兩種證明思路按定義套公式 定義 若A B是永真式 則稱A蘊涵B 2020年3月14日星期六 第五節(jié)聯(lián)結(jié)詞的擴充與功能完全組 第五節(jié)聯(lián)結(jié)詞的擴充與功能完全組一 聯(lián)結(jié)詞的擴充合取非 設(shè)P Q是任意兩個原子命題 定義 P Q P Q 當且僅當P和Q的值均為T時 P Q的值為FP Q讀作 P合取非Q 合取非 又稱 與非 2020年3月14日星期六 聯(lián)結(jié)詞的擴充 析取非 設(shè)P Q是任意兩個原子命題 定義 P Q P Q 當且僅當P和Q的值均為F時 P Q的值為TP Q讀作 P析取非Q 析取非 又稱 或非 2020年3月14日星期六 聯(lián)結(jié)詞的擴充 條件非 設(shè)P Q是任意兩個原子命題 定義 P Q P Q 當且僅當P為T而Q為F時 P Q的值為TP Q讀作 P條件非Q 2020年3月14日星期六 聯(lián)結(jié)詞的擴充 雙條件非 設(shè)P Q是任意兩個原子命題 定義 P Q P Q 當且僅當P和Q的真值不同時 P Q的值為TP Q讀作 P雙條件非Q 雙條件非 又稱 異或 2020年3月14日星期六 擴充聯(lián)結(jié)詞的性質(zhì) 與非的性質(zhì)交換律P Q Q P冪律P P P P Q P Q P Q P P Q Q P Q 2020年3月14日星期六 擴充聯(lián)結(jié)詞的性質(zhì) 與非的性質(zhì) 補充 P T PP F T德 摩根律 P Q P Q 自己證明 2020年3月14日星期六 擴充聯(lián)結(jié)詞的性質(zhì) 或非的性質(zhì)交換律P Q Q P冪律P P P P Q P Q P Q P P Q Q P Q 2020年3月14日星期六 擴充聯(lián)結(jié)詞的性質(zhì) 或非的性質(zhì) 補充 P F PP T F德 摩根律 P Q P Q 自己證明 2020年3月14日星期六 擴充聯(lián)結(jié)詞的性質(zhì) 例1 30求證 P Q的對偶式是P Q證明 P Q P Q P Q P Q P Q P Q 2020年3月14日星期六 擴充聯(lián)結(jié)詞的性質(zhì) 例1 31求證 P Q P Q P Q證明 P Q P Q P Q E12 P Q同理 可證 P Q P Q 2020年3月14日星期六 擴充聯(lián)結(jié)詞的性質(zhì) 異或的性質(zhì)交換律P Q Q P結(jié)合律P Q R P Q R分配律P Q R P Q P R 冪律P P F P P T同一律P F P P T P若P Q R 則Q R P R P Q且P Q R F 2020年3月14日星期六 擴充聯(lián)結(jié)詞的性質(zhì) 我們一共學習了9個聯(lián)結(jié)詞 優(yōu)先級由高到低為 由教材P16的真值表可知 這9個命題聯(lián)結(jié)詞可以表示所有的命題間的聯(lián)結(jié)關(guān)系 是不是必須用這9個表示命題間的聯(lián)結(jié)關(guān)系呢 能不能再少一些 2020年3月14日星期六 聯(lián)結(jié)詞功能完全組 二 聯(lián)結(jié)詞功能完全組由定義知 P Q P Q P Q P Q P Q P Q P Q P Q 因此 僅使用 就足夠了 2020年3月14日星期六 聯(lián)結(jié)詞功能完全組 又因為 P Q P Q P Q E12P Q P QE11P Q P Q E5P Q P Q E5僅使用 或 就足夠了 2020年3月14日星期六 聯(lián)結(jié)詞功能完全組 定義 設(shè)D為聯(lián)結(jié)詞集合 若D中一個聯(lián)結(jié)詞可以由D中其他的聯(lián)結(jié)詞表示 則該聯(lián)結(jié)詞成為冗余聯(lián)結(jié)詞 設(shè)D為聯(lián)結(jié)詞集合 若任何命題公式總可以用含有D中的聯(lián)結(jié)詞的等值式表示 且D中不含有冗余聯(lián)結(jié)詞 則稱D為全功能聯(lián)結(jié)詞集合 或聯(lián)結(jié)