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

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