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

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

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