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

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

1,1.6命題邏輯的推理理論,推理的形式結構判斷推理是否正確的方法推理定律與推理規(guī)則構造證明法,2,推理的形式結構—問題的引入,推理:從前提出發(fā)推出結論的思維過程前提是指已知的命題公式，結論是推出的命題公式例如果天氣涼快，小王就不去游泳.天氣涼快.所以小王沒有去游泳.p:天氣涼快，q:小王去游泳前提：(pq)p結論：q問題：如何判斷推理的是否正確？,3,推理的形式結構,定義“A1,A2,…,Ak推B”的推理正確當且僅當A1A2…AkB為重言式.若對于每組賦值，A1A2…Ak為假，或當A1A2…Ak為真時,B也為真,則稱由A1,A2,…,Ak推B的推理正確,否則推理不正確（錯誤）.推理的形式結構:A1A2…AkB或前提：A1,A2,…,Ak結論：B若推理正確，則記作：A1A2…AkB.,4,判斷推理是否正確的方法,真值表法等值演算法主析取范式法構造證明法說明：當命題變項比較少時，用前3個方法比較方便,此時采用形式結構“A1A2…AkB”.當命題變項比較多時，用構造證明法，采用“前提:A1,A2,…,Ak,結論:B”.,5,實例,例判斷下面推理是否正確(1)若今天是1號，則明天是5號.今天是1號.所以明天是5號.解設p：今天是1號，q：明天是5號.證明的形式結構為:(pq)pq證明（用等值演算法）(pq)pq((pq)p)qpqq1得證推理正確,6,實例(續(xù)),(2)若今天是1號，則明天是5號.明天是5號.所以今天是1號.解設p：今天是1號，q：明天是5號.證明的形式結構為:(pq)qp證明（用主析取范式法）(pq)qp(pq)qp((pq)q)pqp(pq)(pq)(pq)(pq)m0m2m3結果不含m1,故01是成假賦值，所以推理不正確.,7,推理定律——重言蘊涵式,重要的推理定律A(AB)附加律(AB)A化簡律(AB)AB假言推理(AB)BA拒取式(AB)BA析取三段論(AB)(BC)(AC)假言三段論(AB)(BC)(AC)等價三段論(AB)(CD)(AC)(BD)構造性二難,8,推理定律(續(xù)),(AB)(AB)(AA)B構造性二難（特殊形式）(AB)(CD)(BD)(AC)破壞性二難,說明：若某推理符合某條推理定律，則它自然是正確的AB產生兩條推理定律:AB,BA,9,推理規(guī)則,,10,推理規(guī)則(續(xù)),,11,構造證明——直接證明法,例構造下面推理的證明：若明天是星期一或星期三，我就有課.若有課，今天必備課.我今天下午沒備課.所以，明天不是星期一和星期三.解設p：明天是星期一，q：明天是星期三，r：我有課，s：我備課形式結構為前提：(pq)r,rs,s結論：pq,12,直接證明法(續(xù)),證明①rs前提引入②s前提引入③r①②拒取式④(pq)r前提引入⑤(pq)③④拒取式⑥pq⑤置換,13,構造證明——附加前提證明法,欲證明前提：A1,A2,…,Ak結論：CB等價地證明前提：A1,A2,…,Ak,C結論：B理由：(A1A2…Ak)(CB)(A1A2…Ak)(CB)(A1A2…AkC)B(A1A2…AkC)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ù)形式結構前提：pq,pr,rs結論：sq,15,附加前提證明法(續(xù)),證明①s附加前提引入②pr前提引入③rs前提引入④ps②③假言三段論⑤p①④拒取式⑥pq前提引入⑦q⑤⑥析取三段論請用直接證明法證明之,16,構造證明——歸謬法（反證法）,欲證明前提：A1,A2,…,Ak結論：B將B加入前提，若推出矛盾，則得證推理正確.理由:A1A2…AkB(A1A2…Ak)B(A1A2…AkB)括號內部為矛盾式當且僅當(A1A2…AkB)為重言式,17,歸謬法(續(xù)),例構造下面推理的證明前提：(pq)r,rs,s,p結論：q證明（用歸繆法）①q結論否定引入②rs前提引入③s前提引入④r②③拒取式,18,歸謬法(續(xù)),⑤(pq)r前提引入⑥(pq)④⑤析取三段論⑦pq⑥置換⑧p①⑦析取三段論⑨p前提引入⑩pp⑧⑨合取請用直接證明法證明之,