離散數(shù)學(xué)第一章命題演算基礎(chǔ)-真假性.ppt

《離散數(shù)學(xué)第一章命題演算基礎(chǔ)-真假性.ppt》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《離散數(shù)學(xué)第一章命題演算基礎(chǔ)-真假性.ppt（43頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

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