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

第一章命題邏輯 2020年3月14日星期六 第四節(jié)對(duì)偶式與蘊(yùn)涵式 第四節(jié)對(duì)偶式與蘊(yùn)涵式一 對(duì)偶式定義 在給定的僅使用聯(lián)結(jié)詞 的命題公式A中 若把 和 互換 F和T互換 得到一個(gè)公式A 稱(chēng)A 是A的對(duì)偶式 稱(chēng)A和A 互為對(duì)偶式 2020年3月14日星期六 對(duì)偶式 例1 24求下列公式的對(duì)偶式 P Q R P TP Q P Q R P F P Q P Q P Q P Q 2020年3月14日星期六 對(duì)偶式 對(duì)偶定理 設(shè)A和A 互為對(duì)偶式 P1 P2 Pn是出現(xiàn)在A和A 的原子命題變?cè)?則 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(zhǎng)當(dāng)L 0時(shí) A P1 A A P1 P1 P1 A P1 當(dāng)L 1時(shí) A P1 P2 或 P1 P2 或 P1 當(dāng)A P1 P2 時(shí) A P1 P2 A P1 P2 P1 P2 P1 P2 A P1 P2 當(dāng)A P1 P2 時(shí) A P1 P2 A P1 P2 P1 P2 P1 P2 A P1 P2 當(dāng)A P1時(shí) A P1 A P1 P1 A P1 2020年3月14日星期六 A P1 P2 Pn A P1 P2 Pn 設(shè)當(dāng)L k 1時(shí) k 1 2 時(shí) A P1 P2 Pn A P1 P2 Pn 成立當(dāng)L k時(shí)若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 由上證明 可得當(dāng)L K時(shí) A P1 P2 Pn A P1 P2 Pn 證畢 2020年3月14日星期六 對(duì)偶式 例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 又因?yàn)?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日星期六 對(duì)偶式 對(duì)偶定理 設(shè)A和B是兩個(gè)命題公式 若A B 則A B 證明 A B意味著A P1 P2 Pn B P1 P2 Pn 永真 所以 A P1 P2 Pn B P1 P2 Pn 永真 因?yàn)?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日星期六 對(duì)偶式 例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日星期六 對(duì)偶式 例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是兩個(gè)命題公式 若A B 則A B 2020年3月14日星期六 蘊(yùn)涵式 二 蘊(yùn)涵式定義 設(shè)A和B是兩個(gè)命題公式 若A B是永真式 則稱(chēng)A蘊(yùn)涵B 記做A B 稱(chēng)A B為蘊(yùn)涵式或條件永真式 與 的區(qū)別 是邏輯聯(lián)結(jié)詞 出現(xiàn)在命題公式中 是一個(gè)符號(hào) 表示兩個(gè)命題公式之間的蘊(yùn)涵關(guān)系 2020年3月14日星期六 蘊(yùn)涵式 蘊(yùn)涵式有以下性質(zhì) 自反性對(duì)任意公式A 有A A傳遞性對(duì)任意公式A B C 若有A B B C 則有A C對(duì)任意公式A B C 若有A B A C則A B C 對(duì)任意公式A B C 若有A C B C則 A B C 2020年3月14日星期六 蘊(yùn)涵式 等價(jià)式和蘊(yùn)涵式的關(guān)系 定理 設(shè)A和B是兩個(gè)命題公式 A B的充要條件是 A B且B A證明 1 若A B 則A B是永真式 因?yàn)?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日星期六 蘊(yùn)涵式 證明 2 若A B且B A 則 A B 和 B A 都是永真式 因?yàn)?A B A B B A 所以A B是永真式所以A B 充分條件得證 因此 A B的充要條件是 A B且B A 證畢 2020年3月14日星期六 蘊(yùn)涵式的證明 蘊(yùn)涵式的證明方法 真值表法若前件為真 能推得后件為真 則此蘊(yùn)涵式為真若后件為假 能推得前件為假 則此蘊(yùn)涵式為真 指明兩種證明思路 2020年3月14日星期六 蘊(yùn)涵式的證明 例1 28求證 Q P Q P證明 1 真值表法 2020年3月14日星期六 蘊(yùn)涵式的證明 2 前件真則后件真 Q P Q P 設(shè) Q P Q 為T(mén) 則 Q為T(mén) P Q也為T(mén)可得到 Q為F 故P為F 因此 P為T(mén) 得證3 后件假則前件假設(shè) P為F 則P為T(mén)若Q為T(mén) 則 Q為F 則 Q P Q 為F若Q為F 則P Q為F 則 Q P Q 為F 證畢 2020年3月14日星期六 基本蘊(yùn)涵公式 基本蘊(yùn)涵公式A B C D代表任意命題I1化簡(jiǎn)式A B AI2A B BI3附加式A A B A B AI4附加式變形 A A BI5B A BI6化簡(jiǎn)式變形 A B AI7 A B B 2020年3月14日星期六 基本蘊(yùn)涵公式 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日星期六 基本蘊(yùn)涵公式 I14析取構(gòu)造二難 A B C D A C B D特別的 當(dāng)B D時(shí) 有 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日星期六 基本蘊(yùn)涵公式 補(bǔ)充 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日星期六 蘊(yùn)涵式 例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是永真式 則稱(chēng)A蘊(yùn)涵B 2020年3月14日星期六 第五節(jié)聯(lián)結(jié)詞的擴(kuò)充與功能完全組 第五節(jié)聯(lián)結(jié)詞的擴(kuò)充與功能完全組一 聯(lián)結(jié)詞的擴(kuò)充合取非 設(shè)P Q是任意兩個(gè)原子命題 定義 P Q P Q 當(dāng)且僅當(dāng)P和Q的值均為T(mén)時(shí) P Q的值為FP Q讀作 P合取非Q 合取非 又稱(chēng) 與非 2020年3月14日星期六 聯(lián)結(jié)詞的擴(kuò)充 析取非 設(shè)P Q是任意兩個(gè)原子命題 定義 P Q P Q 當(dāng)且僅當(dāng)P和Q的值均為F時(shí) P Q的值為T(mén)P Q讀作 P析取非Q 析取非 又稱(chēng) 或非 2020年3月14日星期六 聯(lián)結(jié)詞的擴(kuò)充 條件非 設(shè)P Q是任意兩個(gè)原子命題 定義 P Q P Q 當(dāng)且僅當(dāng)P為T(mén)而Q為F時(shí) P Q的值為T(mén)P Q讀作 P條件非Q 2020年3月14日星期六 聯(lián)結(jié)詞的擴(kuò)充 雙條件非 設(shè)P Q是任意兩個(gè)原子命題 定義 P Q P Q 當(dāng)且僅當(dāng)P和Q的真值不同時(shí) P Q的值為T(mén)P Q讀作 P雙條件非Q 雙條件非 又稱(chēng) 異或 2020年3月14日星期六 擴(kuò)充聯(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日星期六 擴(kuò)充聯(lián)結(jié)詞的性質(zhì) 與非的性質(zhì) 補(bǔ)充 P T PP F T德 摩根律 P Q P Q 自己證明 2020年3月14日星期六 擴(kuò)充聯(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日星期六 擴(kuò)充聯(lián)結(jié)詞的性質(zhì) 或非的性質(zhì) 補(bǔ)充 P F PP T F德 摩根律 P Q P Q 自己證明 2020年3月14日星期六 擴(kuò)充聯(lián)結(jié)詞的性質(zhì) 例1 30求證 P Q的對(duì)偶式是P Q證明 P Q P Q P Q P Q P Q P Q 2020年3月14日星期六 擴(kuò)充聯(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日星期六 擴(kuò)充聯(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日星期六 擴(kuò)充聯(lián)結(jié)詞的性質(zhì) 我們一共學(xué)習(xí)了9個(gè)聯(lián)結(jié)詞 優(yōu)先級(jí)由高到低為 由教材P16的真值表可知 這9個(gè)命題聯(lián)結(jié)詞可以表示所有的命題間的聯(lián)結(jié)關(guān)系 是不是必須用這9個(gè)表示命題間的聯(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é)詞功能完全組 又因?yàn)?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中一個(gè)聯(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é)詞 則稱(chēng)D為全功能聯(lián)結(jié)詞集合 或聯(lián)結(jié)