離散數(shù)學 命題邏輯的推理理論.ppt

《離散數(shù)學 命題邏輯的推理理論.ppt》由會員分享，可在線閱讀，更多相關《離散數(shù)學 命題邏輯的推理理論.ppt（18頁珍藏版）》請在裝配圖網上搜索。

1 1 6命題邏輯的推理理論 推理的形式結構判斷推理是否正確的方法推理定律與推理規(guī)則構造證明法 2 推理的形式結構 問題的引入 推理 從前提出發(fā)推出結論的思維過程前提是指已知的命題公式 結論是推出的命題公式例如果天氣涼快 小王就不去游泳 天氣涼快 所以小王沒有去游泳 p 天氣涼快 q 小王去游泳前提 p q p結論 q問題 如何判斷推理的是否正確 3 推理的形式結構 定義 A1 A2 Ak推B 的推理正確當且僅當A1 A2 Ak B為重言式 若對于每組賦值 A1 A2 Ak為假 或當A1 A2 Ak為真時 B也為真 則稱由A1 A2 Ak推B的推理正確 否則推理不正確 錯誤 推理的形式結構 A1 A2 Ak B或前提 A1 A2 Ak結論 B若推理正確 則記作 A1 A2 Ak B 4 判斷推理是否正確的方法 真值表法等值演算法主析取范式法構造證明法說明 當命題變項比較少時 用前3個方法比較方便 此時采用形式結構 A1 A2 Ak B 當命題變項比較多時 用構造證明法 采用 前提 A1 A2 Ak 結論 B 5 實例 例判斷下面推理是否正確 1 若今天是1號 則明天是5號 今天是1號 所以明天是5號 解設p 今天是1號 q 明天是5號 證明的形式結構為 p q p q證明 用等值演算法 p q p q p q p q p q q 1得證推理正確 6 實例 續(xù) 2 若今天是1號 則明天是5號 明天是5號 所以今天是1號 解設p 今天是1號 q 明天是5號 證明的形式結構為 p q q p證明 用主析取范式法 p q q p p q q p p q q p q p p q p q p q p q m0 m2 m3結果不含m1 故01是成假賦值 所以推理不正確 7 推理定律 重言蘊涵式 重要的推理定律A A B 附加律 A B A化簡律 A B A B假言推理 A B B A拒取式 A B B A析取三段論 A B B C A C 假言三段論 A B B C A C 等價三段論 A B C D A C B D 構造性二難 8 推理定律 續(xù) A B A B A A B構造性二難 特殊形式 A B C D B D A C 破壞性二難 說明 若某推理符合某條推理定律 則它自然是正確的A B產生兩條推理定律 A B B A 9 推理規(guī)則 10 推理規(guī)則 續(xù) 11 構造證明 直接證明法 例構造下面推理的證明 若明天是星期一或星期三 我就有課 若有課 今天必備課 我今天下午沒備課 所以 明天不是星期一和星期三 解設p 明天是星期一 q 明天是星期三 r 我有課 s 我備課形式結構為前提 p q r r s s結論 p q 12 直接證明法 續(xù) 證明 r s前提引入 s前提引入 r 拒取式 p q r前提引入 p q 拒取式 p q 置換 13 構造證明 附加前提證明法 欲證明前提 A1 A2 Ak結論 C B等價地證明前提 A1 A2 Ak C結論 B理由 A1 A2 Ak C B A1 A2 Ak C B A1 A2 Ak C B A1 A2 Ak C B 14 附加前提證明法 續(xù) 例構造下面推理的證明 2是素數(shù)或合數(shù) 若2是素數(shù) 則是無理數(shù) 若是無理數(shù) 則4不是素數(shù) 所以 如果4是素數(shù) 則2是合數(shù) 用附加前提證明法構造證明解設p 2是素數(shù) q 2是合數(shù) r 是無理數(shù) s 4是素數(shù)形式結構前提 p q p r r s結論 s q 15 附加前提證明法 續(xù) 證明 s附加前提引入 p r前提引入 r s前提引入 p s 假言三段論 p 拒取式 p q前提引入 q 析取三段論請用直接證明法證明之 16 構造證明 歸謬法 反證法 欲證明前提 A1 A2 Ak結論 B將 B加入前提 若推出矛盾 則得證推理正確 理由 A1 A2 Ak B A1 A2 Ak B A1 A2 Ak B 括號內部為矛盾式當且僅當 A1 A2 Ak B 為重言式 17 歸謬法 續(xù) 例構造下面推理的證明前提 p q r r s s p結論 q證明 用歸繆法 q結論否定引入 r s前提引入 s前提引入 r 拒取式 18 歸謬法 續(xù) p q r前提引入 p q 析取三段論 p q 置換 p 析取三段論 p前提引入 p p 合取請用直接證明法證明之