離散數(shù)學(xué)課件 第一章 命題邏輯-4th.pdf

1 38 離散數(shù)學(xué) 大連理工大學(xué)軟件學(xué)院 陳志奎 教授 辦公室 綜合樓411 Tel 87571525 實驗室 教學(xué)樓A318 A323 Tel 87571620 24 MobileEmail zkchen zkchen00 2 38 回顧 勘誤 P14 兩處 P16 5 2 對偶原理 定義 三條原理 非運算與對偶 等價 永真蘊含 析取范式和合取范式 基本積 基本和 基本和的積 基本積的和 主析取范式和主合取范式 極小項 積 極大項 和 基 二進制數(shù) 十進 制數(shù) 描述符 極小項的和 極大項的積 兩者的關(guān)系 3 38 求范式步驟 求范式步驟 2 否定消去或內(nèi)移 3 利用分配律 1 消去聯(lián)結(jié)詞 回顧 4 38 1 7命題演算的推理理論 數(shù)理邏輯的一個主要任務(wù)就是提供一套推理規(guī) 則 給定一些前提 利用所提供的推理規(guī)則 推 導(dǎo)出一些結(jié)論來 這個過程稱為演繹或證明 生活中 倘若認定前提是真的 從前提推導(dǎo)出結(jié)論的論證是遵 守了邏輯推理規(guī)則 則認為此結(jié)論是真的 并且認為 這個論證過程是合法的 數(shù)理邏輯中 不關(guān)心前提的真實真值 把注意力集中于推理規(guī)則的 研究 依據(jù)這些推理規(guī)則推導(dǎo)出的任何結(jié)論 稱為有 效結(jié)論 而這種論證則被稱為有效論證 5 38 有效結(jié)論 定義 設(shè)A和B是兩個命題公式 當且僅當 A B是個永真式 即A B 則說B是A的有 效結(jié)論 或B由A可邏輯的推出 可把該定義推廣到有n個前提的情況 6 38 有效結(jié)論 定義 例 H1 今天周一或者今天下雨 H2 今天不是周一 C 今天下雨 12 12 12 m m m H HHC HHHC CH HH 設(shè)是一些命題公式 當且僅當 則稱 是前提集合的有效結(jié)論 7 38 證明有效結(jié)論的方法 1 真值表法 思路 證明使前提集合取值為真的那些組真值 指派 也一定使結(jié)論取值為真 證明使前提集合取值為真的那些組真值 指派 也一定使結(jié)論取值為真 例 考察結(jié)論C是否是下列前提H1 H2 H3 的結(jié)論 1 H1 P Q H2 P C Q PQH1H2CH1 H2 C 001001 011011 100101 111111 8 38 真值表法 2 真值表構(gòu)造如下 1 HPQ 2 HQR 3 HR CP P Q RPQ QR R P 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 0 1 1 0 1 0 1 0 1 0 1 1 1 1 0 0 0 0 9 38 真值表法 3 1 HP 2 HPQ C PQ P QP PQ PQ 0 0 0 1 1 0 1 1 1 1 0 0 0 1 1 1 0 0 0 1 10 38 例 一份統(tǒng)計表格的錯誤或者是由于材料不可靠 或者是由于計算有錯誤 這份統(tǒng)計表格的錯誤不 是由于材料不可靠 所以這份統(tǒng)計表格是由于計 算有錯誤 解 設(shè)P 一份統(tǒng)計表格的錯誤是由于材料不可靠 Q 一份統(tǒng)計表格的錯誤是由于計算有錯誤 于是問題可符號化為 P Q P Q 其真值表如下頁所示 使前提集合取值為真的真值 指派只有一組 這組真值指派使結(jié)論Q也取值為 真 真值表法 11 38 真值表法真值表法 P Q P Q P Q 0 0 0 0 0 1 1 1 1 0 0 0 1 1 0 1 12 38 證明有效結(jié)論的方法 2 直接證法 在命題變元較多的情況下 真值表法顯得不方便 我 們采用直接證明法 為此先給出如下的定義 定義 設(shè)S是一個命題公式的集合 從S推出命題公式C 的推理過程是命題公式的一個有限序列 C1 C2 Cn 其中 Ci 或者屬于S 或者是某些Cj j i 的有效結(jié) 論 并且Cn 就是C 如何構(gòu)造這個推理序列以得出結(jié) 論C呢 只要遵循下面的推理規(guī)則 使用列出的等價 式或永真蘊涵式 就能構(gòu)造出滿足要求的公式序列 為了幫助大家記憶 我們把常用的等價式和永真蘊 涵式再次列出來 13 38 常用永真蘊含式 I1 P Q P I2 P P Q I3 P P Q I4 Q P Q I5 P Q P I6 P Q Q I7 P Q P Q I8 P P Q Q I9 P P Q Q I10 Q P Q P I11 P Q Q R P R I12 P Q P R Q R R 公式中 代表 公式不必死記硬背 其證明均可 從 的定義出發(fā) 例如對I11 前件為真時保證 P Q和Q R都必為真 P Q為真 則保證P為真 時Q一定為真 而Q為真和Q R為真則保證了R必 為真 P為真 R為真自然保證了P R為真 問題得證 14 38 常用等價式 E E1 1 P P E P P E2 2 P Q Q P E P Q Q P E3 3 P Q Q P E P Q Q P E4 4 P Q R P Q R E P Q R P Q R E5 5 P Q R P Q R E P Q R P Q R E6 6 P Q R P R Q R E P Q R P R Q R E7 7 P Q R P R Q R E P Q R P R Q R E8 8 P Q P Q E P Q P Q E9 9 P Q P Q E P Q P Q E10 10 P P P E P P P E11 11 P P P P P P 15 38 常用等價式 E E12 12 R P P R E R P P R E13 13 R P P R E R P P R E14 14 R P P T E R P P T E15 15 R P P F E R P P F E16 16 P Q P Q E P Q P Q E17 17 P Q P Q E P Q P Q E18 18 P Q Q P E P Q Q P E19 19 P Q R P Q R E P Q R P Q R E20 20 P P Q PQ P Q E Q E21 21 P P Q P Q Q P E Q P Q Q P E22 22 P P Q P Q P Q Q P Q P Q 16 38 常用等價公式 24 25 26 27 28 29 30 EPTP EPFP EPQPQQPPQPQ EPQPQ EPQRPQR EPPQP EPPQP 輸出律 吸收律 17 38 直接證法 直接證明法 使用推理規(guī)則和給定的等價式 及永真蘊涵式進行推導(dǎo)證明 推理規(guī)則 規(guī)則P 在推導(dǎo)過程中 任何時候都可以引入 前提 引入一個前提稱為使用一次P規(guī)則 規(guī)則T 在推導(dǎo)中 如果前面有一個或多個公 式永真蘊含公式S 則可以把公式S引進推導(dǎo) 過程中 換句話說 引進前面推導(dǎo)過程中的 推理結(jié)果稱為使用T規(guī)則 18 38 直接證法 PPQQRR 例 證明是 的有效結(jié)論 解 1 1 P Q P規(guī)則 1 2 P Q T規(guī)則 1 和E11 1 3 P Q T規(guī)則 2 和E27 4 4 Q R P規(guī)則 4 5 Q R T規(guī)則 4 和E27 1 4 6 P R T 3 5 和I12 7 7 R P規(guī)則 1 4 7 8 P T 6 7 和I12 19 38 直接證法 例 證明公式S 例 證明公式S R可由公式P Q P Q P R Q S推出 解 問題即證 S推出 解 問題即證P Q P Q P R Q S S S S R 1 P Q P規(guī)則 2 P Q T規(guī)則和1 3 Q P規(guī)則 2 P Q T規(guī)則和1 3 Q S P規(guī)則 4 S P規(guī)則 4 Q S T規(guī)則和3 5 P S T規(guī)則及2和4 6 S P T規(guī)則和5 7 P S T規(guī)則和3 5 P S T規(guī)則及2和4 6 S P T規(guī)則和5 7 P R P規(guī)則 8 P R R P T規(guī)則和7 9 P R T規(guī)則和8 10 S R T規(guī)則及6和9 11 S P規(guī)則 8 P R R P T規(guī)則和7 9 P R T規(guī)則和8 10 S R T規(guī)則及6和9 11 S R T規(guī)則和9 得證 T規(guī)則和9 得證 20 38 直接證法 例 P例 P Q R S Q R S Q P R R P Q 1 R P規(guī)則 2 Q R R P Q 1 R P規(guī)則 2 Q P R P規(guī)則 3 Q R P規(guī)則 3 Q P T規(guī)則及1和2 4 R S T規(guī)則及1 5 P T規(guī)則及1和2 4 R S T規(guī)則及1 5 P Q R S P規(guī)則 6 P R S P規(guī)則 6 P Q T規(guī)則及4和5 7 P T規(guī)則及4和5 7 P Q Q Q P T規(guī)則及3和6 8 P Q T規(guī)則和7 T規(guī)則及3和6 8 P Q T規(guī)則和7 21 38 直接證法 推理規(guī)則 CP規(guī)則 如果能從R和前提集合中推導(dǎo)出S 來 則就能夠從前提集合中推導(dǎo)出R S 換句話說 當結(jié)論是R S的形式的時候 可 以把結(jié)論的前件當作一個附加前提使用 并 且它和前提一起若能推出結(jié)論的后件 則問 題得證 實際上恒等式E28就可以推出CP規(guī)則 P Q R P Q R P Q R P Q R P Q R 22 38 直接證法 解 1 1 R P規(guī)則 附加前提 2 2 R P P規(guī)則 1 2 3 P T規(guī)則 1 2 和I9 4 4 P Q S P規(guī)則 1 2 4 5 Q S T規(guī)則 3 4 和I10 6 6 Q P規(guī)則 1 2 4 6 7 S T規(guī)則 5 6 和I10 1 2 4 6 8 R S CP規(guī)則 1 7 RSPQSQRP 例 證明是 的有效結(jié)論 23 38 例 證明R S是前提P Q S R P Q 的有效結(jié)論 解 原證明即證 P Q S R P Q R S 1 R P規(guī)則 附加前提 2 R P Q P規(guī)則 3 P Q T規(guī)則及1和2 4 P T規(guī)則和3 5 P Q S P規(guī)則 6 Q S T規(guī)則及4和5 7 Q T規(guī)則和3 8 S T規(guī)則及6和7 9 R S CP規(guī)則及1和8 例 證明R S是前提P Q S R P Q 的有效結(jié)論 解 原證明即證 P Q S R P Q R S 1 R P規(guī)則 附加前提 2 R P Q P規(guī)則 3 P Q T規(guī)則及1和2 4 P T規(guī)則和3 5 P Q S P規(guī)則 6 Q S T規(guī)則及4和5 7 Q T規(guī)則和3 8 S T規(guī)則及6和7 9 R S CP規(guī)則及1和8 直接證法 24 38 例 證明P Q R Q P S S R 解 1 S P規(guī)則 附加前提 2 P S P規(guī)則 3 P T規(guī)則及1和2 4 P Q R P規(guī)則 5 Q R T規(guī)則及3和4 6 Q P規(guī)則 7 R T規(guī)則及5和6 8 S R CP規(guī)則及1和7 例 證明P Q R Q P S S R 解 1 S P規(guī)則 附加前提 2 P S P規(guī)則 3 P T規(guī)則及1和2 4 P Q R P規(guī)則 5 Q R T規(guī)則及3和4 6 Q P規(guī)則 7 R T規(guī)則及5和6 8 S R CP規(guī)則及1和7 直接證法 25 38 證明有效結(jié)論的方法 3 間接證明法 反證法 定義 設(shè)公式H1 H2 Hm中的原子變元是P1 P2 Pn 如果給各原子變元P1 P2 Pn指派 某一個真值集合 能使H1 H2 Hm具 有真值T 則命題公式集合 H1 H2 Hm 稱為 一致的 或相容的 對于各原子變元的每一個 真值指派 如果命題公式H1 H2 Hm中至少有 一個是假 從而使得H1 H2 Hm是 假 則稱命題公式集合是不一致的 或不相容 的 例如 令H1 P H2 P 則H1 H2 P P 是矛盾式 所以P P是不相容的 26 38 反證法 定理 若存在一個公式R 使得 H1 H2 Hm R R 則公式H1 H2 Hm 是不相容的 證明 設(shè) H1 H2 Hm R R 則意味著 H1 H2 Hm R R 是重言式 而R R是矛盾式 所以前件 H1 H2 Hm必永假 因此 H1 H2 Hm是不相容的 27 38 反證法 定理 設(shè)命題公式集合 H1 H2 Hm 是一致的 于是從前提集合出發(fā)可以邏輯 的推出公式C的充要條件是從前提集合 H1 H2 Hm C 出發(fā) 可以邏輯地 推出一個矛盾 永假 式 證明 必要性 由于H1 H2 Hm C 即H1 H2 Hm C為永真式 因而使H1 H2 Hm 為真的真值指派一定使C為真 C為假 從而 使H1 H2 Hm C為假 必要性證完 28 38 反證法 證充分性 由于 H證充分性 由于 H1 1 H H2 2 H Hm m C 可以邏輯 地推出一個矛盾 即H C 可以邏輯 地推出一個矛盾 即H1 1 H H2 2 H Hm m C F 即 H C F 即 H1 1 H H2 2 H Hm m C F為永真式 即 H C F為永真式 即 H1 1 H H2 2 H Hm m C為假 由假設(shè)知 H C為假 由假設(shè)知 H1 1 H H2 2 H Hm m 是一致的 所以任何使H 是一致的 所以任何使H1 1 H H2 2 H Hm m 為真的命題變元的真值指派必然使 C 為 假 從而使C為真 故有 H 為真的命題變元的真值指派必然使 C 為 假 從而使C為真 故有 H1 1 H H2 2 H Hm m C 該定理說明用直接證明法可以證明的結(jié)論 用間 接證明法都可以證明 反之亦然 因此 為了證明B是A的結(jié)論 可以把A和 B作為前 提 然后推出一個矛盾 從而使問題得證 下 面用例子說明 C 該定理說明用直接證明法可以證明的結(jié)論 用間 接證明法都可以證明 反之亦然 因此 為了證明B是A的結(jié)論 可以把A和 B作為前 提 然后推出一個矛盾 從而使問題得證 下 面用例子說明 29 38 反證法 F規(guī)則 如果前體集合和 規(guī)則 如果前體集合和 S不相容 那么可以從 前提集合中推出 不相容 那么可以從 前提集合中推出S 例 證明 P Q 是 P Q的有效結(jié)論 解 把 P Q 作為假設(shè)前提 并證明該假設(shè) 前提導(dǎo)致一個永假式 1 1 P Q P規(guī)則 假設(shè)前提 1 2 P Q T規(guī)則 1 和E10 1 3 P T規(guī)則 2 和I1 4 4 P Q P規(guī)則 4 5 P T規(guī)則 4 和I1 1 4 6 P P T規(guī)則 3 5 和I16 1 4 7 P Q F規(guī)則 1 6 30 38 反證法 例 證明P Q P R Q R R 解 1 R P規(guī)則 假設(shè)前提 2 P R P規(guī)則 3 P T規(guī)則及1和2 4 P Q P規(guī)則 5 Q T規(guī)則及3和4 6 Q R P規(guī)則 7 R T規(guī)則及5和6 8 R R T規(guī)則及1和7 9 R F規(guī)則及1和8 例 證明P Q P R Q R R 解 1 R P規(guī)則 假設(shè)前提 2 P R P規(guī)則 3 P T規(guī)則及1和2 4 P Q P規(guī)則 5 Q T規(guī)則及3和4 6 Q R P規(guī)則 7 R T規(guī)則及5和6 8 R R T規(guī)則及1和7 9 R F規(guī)則及1和8 31 38 反證法反證法 例 足壇4支甲級隊進行比賽 已知情況如下 前提 1 若大連萬達獲冠軍 則北京國安和上海 申花獲亞軍 2 若上海申花獲亞軍 則大連萬達不能獲 冠軍 3 若陜西國力獲亞軍 則北京國安不能獲 亞軍 4 最后大連萬達獲冠軍 結(jié)論 5 陜西國力未獲亞軍 例 足壇4支甲級隊進行比賽 已知情況如下 前提 1 若大連萬達獲冠軍 則北京國安和上海 申花獲亞軍 2 若上海申花獲亞軍 則大連萬達不能獲 冠軍 3 若陜西國力獲亞軍 則北京國安不能獲 亞軍 4 最后大連萬達獲冠軍 結(jié)論 5 陜西國力未獲亞軍 32 38 反證法反證法 用推理的方法證明由 1 2 3 4 能否推出 5 解 首先將命題符號化 令P 大連萬達獲冠軍 Q 北京國安獲亞軍 R 上海申花獲亞軍 S 陜西國力獲亞軍 用推理的方法證明由 1 2 3 4 能否推出 5 解 首先將命題符號化 令P 大連萬達獲冠軍 Q 北京國安獲亞軍 R 上海申花獲亞軍 S 陜西國力獲亞軍 33 38 反證法反證法 于是問題可符號化為 P Q R R P S Q P S 注意這里自然語言 中的和表示的是排斥或 所以用 來表示 解 1 S P規(guī)則 假設(shè)前提 2 S T規(guī)則和1 3 S Q P規(guī)則 4 Q T規(guī)則2和3 5 P P規(guī)則 6 P Q R P規(guī)則 7 Q R T規(guī)則5和6 8 R T規(guī)