命題邏輯的推理理論.ppt

《命題邏輯的推理理論.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《命題邏輯的推理理論.ppt（13頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

漳州師范學(xué)院計(jì)算機(jī)科學(xué)與工程系 第三章命題邏輯的推理理論 2020年3月21日2時(shí)53分 第二章命題邏輯等值演算 推理的形式結(jié)構(gòu)自然推理系統(tǒng)P知識(shí)點(diǎn) 推理的形式結(jié)構(gòu) 推理理論 自然系統(tǒng)P 推理規(guī)則教學(xué)要求 深刻理解和掌握命題邏輯中的基本推理方法教學(xué)重點(diǎn) 推理理論 推理規(guī)則學(xué)時(shí) 2 2020年3月21日2時(shí)53分 3 1推理的形式結(jié)構(gòu) 論證是指由一些前提出發(fā)得到某個(gè)結(jié)論 在數(shù)理邏輯中需要討論論證的有效性提出正確的推理規(guī)則和可行的推理方法A1 A2 An為前提 B為結(jié)論稱 A1 A2 An B為推理的形式結(jié)構(gòu)定理3 1命題公式A1 A2 An推B是正確的當(dāng)且僅當(dāng)A1 A2 An B為重言式 即A1 A2 An B并稱B為前提A1 A2 An的有效結(jié)論或稱B為前提A1 A2 An的邏輯結(jié)果當(dāng)前提為真時(shí)結(jié)論也為真 但推理正確并不能保證有效結(jié)論B一定為真例如 設(shè)p為 太陽從西邊升起 q為 太陽從東邊落下 p q為 如果太陽從西邊升起則太陽從東邊落下 推理 p p q q是正確的 即q是前提的有效結(jié)論 但q是個(gè)假命題 2020年3月21日2時(shí)53分 3 1推理的形式結(jié)構(gòu) 推理的形式結(jié)構(gòu) 前提 A1 A2 An結(jié)論 B重要的推理定律A B A A B B 化簡律 A A B B A B 附加律 A B A B 假言推論 A B B A 拒取式 A B B A 析取三段論 A B B C A C 假言三段論 A B B C A C 等價(jià)三段論 A B C D A C B D 構(gòu)造性二難 A B A B B構(gòu)造性二難 特殊形式 A B C D B D A C 破壞性二難 2020年3月21日2時(shí)53分 3 1推理的形式結(jié)構(gòu) 論證的方法真值表法等值演算法將推理過程形式化 證明公式A1 A2 An B是重言式即證明 A1 A2 An B 1 形式系統(tǒng)一般分為兩類一類是自然推理系統(tǒng) 它的特點(diǎn)是從任意給定的前提出發(fā) 應(yīng)用系統(tǒng)中的推理規(guī)則進(jìn)行推理演算 得到的最后命題公式是推理的結(jié)論 有時(shí)稱為有效的結(jié)論 它可能是重言式 也可能不是 一類是公理推理系統(tǒng) 它只能從若干給定的公理出發(fā) 應(yīng)用系統(tǒng)中推理規(guī)則進(jìn)行推理演算 得到的結(jié)論是系統(tǒng)中的重言式 稱為系統(tǒng)中的定理 2020年3月21日2時(shí)53分 3 2自然推理系統(tǒng)P 定義3 2一個(gè)形式系統(tǒng)I由下面四個(gè)部分組成 1 非空的字符表集 記作A I 2 A I 中符號(hào)構(gòu)造的合式公式集 記作E I 3 E I 中一些特殊的公式組成的公理集 記作AX I 4 推理規(guī)則集 記作R I 可以將I記為其中是I的形式語言系統(tǒng)為I的形式演算系統(tǒng) 定義3 3自然推理系統(tǒng)P定義如下 1 字母表 1 命題變項(xiàng)符號(hào) p q r pi qi ri 2 聯(lián)結(jié)詞符號(hào) 3 括號(hào)和逗號(hào) 2 合式公式同定義1 63 推理規(guī)則 2020年3月21日2時(shí)53分 3 2自然推理系統(tǒng)P 定理3 1 A1 A2 An Ai i 1 2 n證明因?yàn)锳1 A2 An A1 A2 Ai 1 Ai 1 An Ai Ai所以 A1 A2 An Ai定理3 2若 A1 A2 An Bi i 1 2 m且 B1 B2 Bm C 則 A1 A2 An C證明由重言蘊(yùn)涵的性質(zhì)和題設(shè)可知A1 A2 An B1 B2 Bm再由重言蘊(yùn)涵的傳遞性可知A1 A2 An C 即 A1 A2 An C定理3 3若 A1 A2 An B C 則 A1 A2 An B C 證明因?yàn)?A1 A2 An B C 所以1 A1 A2 An B C A1 A2 An B C A1 A2 An B C A1 A2 An B C A1 A2 An B C 即 A1 A2 An B C 2020年3月21日2時(shí)53分 3 2自然推理系統(tǒng)P P規(guī)則在推演過程中可以隨時(shí)引用前提T規(guī)則在推演過程中可以隨時(shí)引用前面已經(jīng)得到的結(jié)論CP規(guī)則若 A1 A2 An B C則 A1 A2 An B C B稱為附加前提在推理過程中可以隨時(shí)使用重言等價(jià)式 E 在推理過程中可以隨時(shí)使用重言蘊(yùn)涵式 I 在推理過程中可以隨時(shí)引用置換規(guī)則和代入替則 2020年3月21日2時(shí)53分 3 2自然推理系統(tǒng)P 直接證明法 由一組前提遵循P規(guī)則和T規(guī)則 根據(jù)已知的重言等價(jià)式和重言蘊(yùn)涵式推演出有效結(jié)論的論證方法例1前提 p q q r p s s結(jié)論 r p q 證明 p s前提引入 s前提引入 p 拒取式 p q前提引入 q 析取三段論 q r前提引入 r 假言推理 r p q 合取此證明的序列長為8 最后一步為推理的結(jié)論 所以推理正確 r p q 是有效結(jié)論 2020年3月21日2時(shí)53分 3 2自然推理系統(tǒng)P 例2 在自然推理系統(tǒng)P中構(gòu)造下面推理的證明 若數(shù)a是實(shí)數(shù) 則它不是有理數(shù)就是無理數(shù) 若a不能表示成分?jǐn)?shù) 則它不是有理數(shù) a是實(shí)數(shù)且它不能表示成分?jǐn)?shù) 所以a是無理數(shù) 解首先將簡單命題符號(hào)化 證明 p s前提引入 p 化簡律 s 化簡律 p q r 前提引入 q r 假言推理 s q前提引入 q 假言推理 r 假言推理 設(shè)p a是實(shí)數(shù) q a是有理數(shù) r a是無理數(shù) s a能表示成分?jǐn)?shù)推理的形式結(jié)構(gòu)為 p q r s q p s r 2020年3月21日2時(shí)53分 3 2自然推理系統(tǒng)P 間接證明法 由一組前提遵循P規(guī)則 T規(guī)則和CP規(guī)則推演出有效結(jié)論 或者將否定結(jié)論作為附加前提 利用P規(guī)則和T規(guī)則得出矛盾式的論證方法 后一種情形又稱為反證法在構(gòu)造形式結(jié)構(gòu)為 A1 A2 Ak B的推理證明中 如果將 B作為前提能推出矛盾來 比如說得出 A A 則說明推理正確 其原因如下 A1 A2 Ak B A1 A2 Ak B A1 A2 Ak B 若 A1 A2 Ak B 為矛盾式 正說明 A1 A2 Ak B為重言式 即 A1 A2 Ak B原故推理是正確 2020年3月21日2時(shí)53分 3 2自然推理系統(tǒng)P 例3在自然推理系統(tǒng)P中構(gòu)造下面推理的證明 如果小張和小王去看電影 則小李也去看電影 小趙不去看電影或小張去看電影 小王去看電影 所以 當(dāng)小趙去看電影時(shí) 小李也去看電影 解將簡單命題符號(hào)化 前提 p q r s p q結(jié)論 s r證明 用附加前提證明法 s附加前提引入 s p前提引入 p 析取三段論 p q r前提引入 q前提引入 p q 合取 r 假言推理 設(shè)p 小張去看電影 q 小王去看電影 r 小李去看電影 s 小趙去看電影 2020年3月21日2時(shí)53分 3 2自然推理系統(tǒng)P 例4 在自然推理系統(tǒng)A中構(gòu)造下面推理的證明 如果小張守第一壘并且小李向B隊(duì)投球 則A隊(duì)將取勝 或者A隊(duì)未取勝 或者A隊(duì)獲得聯(lián)賽第一名 A隊(duì)沒有獲得聯(lián)賽的第一名 小張守第一壘 因此 小李沒有向B隊(duì)投球 證明 q結(jié)論的否定引入 r s前提引入 s前提引入 r 析取三段論 p q r前提引入 p q 假言推理 p q 置換 p前提引入 q 析取三段論 q q 合取由于最后一步q q 0 即原推理正確 先將簡單命題符號(hào)化設(shè)p 小張守第一壘q 小李向B隊(duì)投球r A隊(duì)取勝s A隊(duì)獲得聯(lián)賽第一名推理的形式結(jié)構(gòu) p q r r s s p q