資源描述：
《離散數(shù)學--命題邏輯1.6.ppt》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。
1、1.6命題邏輯的推理理論推理的形式結(jié)構(gòu)判斷推理是否正確的方法推理定律與推理規(guī)則構(gòu)造證明法1推理的形式結(jié)構(gòu)—問題的引入推理舉例:(1)正項級數(shù)收斂當且僅當部分和有上界.(2)若AèCíBèD，則AíB且CíD.推理:從前提出發(fā)推出結(jié)論的思維過程上面(1)是正確的推理，而(2)是錯誤的推理.證明:描述推理正確的過程.2推理的形式結(jié)構(gòu)定義若對于每組賦值，或者A1ùA2ù…ùAk均為假，或者當A1ùA2ù…ùAk為真時,B也為真,則稱由A1,A2,…,Ak推B的推理正確,否則推理不正確（錯誤）.“A1,A2,…,Ak推B”的推理正確當且僅當A1ùA2ù…ùAk?B為重言式.推理的形式結(jié)構(gòu):A1ùA
2、2ù…ùAk?B或前提：A1,A2,…,Ak結(jié)論：B若推理正確，則記作：A1ùA2ù…ùAkTB.3判斷推理是否正確的方法真值表法等值演算法判斷推理是否正確主析取范式法構(gòu)造證明法證明推理正確說明：當命題變項比較少時，用前3個方法比較方便,此時采用形式結(jié)構(gòu)“A1ùA2ù…ùAk?B”.而在構(gòu)造證明時，采用“前提:A1,A2,…,Ak,結(jié)論:B”.4實例例判斷下面推理是否正確(1)若今天是1號，則明天是5號.今天是1號.所以明天是5號.解設p：今天是1號，q：明天是5號.推理的形式結(jié)構(gòu)為:(p?q)ùp?q證明（用等值演算法）(p?q)ùp?q??((?púq)ùp)úq??pú?qúq?1得
3、證推理正確5實例(續(xù))(2)若今天是1號，則明天是5號.明天是5號.所以今天是1號.解設p：今天是1號，q：明天是5號.推理的形式結(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是成假賦值，所以推理不正確.6推理定律——重言蘊涵式重要的推理定律AT(AúB)附加律(AùB)TA化簡律(A?B)ùATB假言推理(A?B)ù?BT?A拒取式(AúB)ù?BTA析取三段論(A?B)ù(B?C)T(A?C)假言三段論(A?B)ù
4、(B?C)T(A?C)等價三段論(A?B)ù(C?D)ù(AúC)T(BúD)構(gòu)造性二難7推理定律(續(xù))(A?B)ù(?A?B)TB構(gòu)造性二難（特殊形式）(A?B)ù(C?D)ù(?Bú?D)T(?Aú?C)破壞性二難說明：A,B,C為元語言符號若某推理符合某條推理定律，則它自然是正確的A?B產(chǎn)生兩條推理定律:ATB,BTA8推理規(guī)則(1)前提引入規(guī)則(2)結(jié)論引入規(guī)則(3)置換規(guī)則(4)假言推理規(guī)則A?BAB(5)附加規(guī)則AAúB(6)化簡規(guī)則AùBA(7)拒取式規(guī)則A?B?B?A(8)假言三段論規(guī)則A?BB?CA?C9推理規(guī)則(續(xù))(11)破壞性二難推理規(guī)則A?BC?D?Bú
5、?D?Aú?C(12)合取引入規(guī)則ABAùB(9)析取三段論規(guī)則AúB?BA(10)構(gòu)造性二難推理規(guī)則A?BC?DAúCBúD10構(gòu)造證明——直接證明法例構(gòu)造下面推理的證明：若明天是星期一，我就有課.若有課，今天必備課.我今天沒備課.所以，明天不是星期一解?設p：明天是星期一，r：我有課，s：我備課推理的形式結(jié)構(gòu)為前提：p?r,r?s,?s結(jié)論：?p11直接證明法(續(xù))證明①r?s前提引入②?s前提引入③?r①②拒取式④p?r前提引入⑤?p③④拒取式12構(gòu)造證明——附加前提證明法欲證明前提：A1,A2,…,Ak結(jié)論：C?B等價地證明前提：A1,A2,…,Ak,C結(jié)論：B理由：(A1
6、ùA2ù…ùAk)?(C?B)??(A1ùA2ù…ùAk)ú(?CúB)??(A1ùA2ù…ùAkùC)úB?(A1ùA2ù…ùAkùC)?B13附加前提證明法(續(xù))例構(gòu)造下面推理的證明:2是素數(shù)或合數(shù).若2是素數(shù)，則是無理數(shù).若是無理數(shù)，則4不是素數(shù).所以，如果4是素數(shù)，則2是合數(shù).用附加前提證明法構(gòu)造證明解設p：2是素數(shù)，q：2是合數(shù)，r：是無理數(shù)，s：4是素數(shù)推理的形式結(jié)構(gòu)前提：púq,p?r,r??s結(jié)論：s?q14附加前提證明法(續(xù))證明①s附加前提引入②p?r前提引入③r??s前提引入④p??s②③假言三段論⑤?p①④拒取式⑥púq前提引入⑦q⑤⑥析取三段論請用直接證明法證明之
7、15構(gòu)造證明——歸謬法（反證法）欲證明前提：A1,A2,…,Ak結(jié)論：B將?B加入前提，若推出矛盾，則得證推理正確.理由:A1ùA2ù…ùAk?B??(A1ùA2ù…ùAk)úB??(A1ùA2ù…ùAkù?B)括號內(nèi)部為矛盾式當且僅當(A1ùA2ù…ùAk?B)為重言式16歸謬法(續(xù))例構(gòu)造下面推理的證明前提：?(pùq)úr,r?s,?s,p結(jié)論：?q證明（用歸繆法）①q結(jié)論否定引入②r?s前提引入③?s前提引入④?
