離散第12講證明的方法

計(jì)算機(jī)專業(yè)基礎(chǔ)課程授課人：張桂蕓

dyxy1999@126.comPowerPointTemplate_Sub1命題與邏輯聯(lián)結(jié)詞2邏輯等價(jià)式和邏輯蘊(yùn)涵式3范式4證明的方法（補(bǔ)充）第四章邏輯代數(shù)（上）：命題演算2第12講證明的方法證明的方法《離散數(shù)學(xué)》第12講

補(bǔ)充內(nèi)容應(yīng)用：推理所謂推理是指從前提出發(fā)推出結(jié)論的思維過程，前提是已知的命題公式集合，結(jié)論是從前提出發(fā)應(yīng)用推理規(guī)則推出的命題公式定義：設(shè)A1,A2,…,Ak和B都是命題公式，若對(duì)于A1,A2,…,Ak和B中出現(xiàn)的命題變?cè)娜我庖唤M指派，當(dāng)A1∧A2∧…∧Ak為真時(shí)B也為真，則稱由前提A1,A2,…,Ak推出結(jié)論B的推理是有效的或正確的，并稱B是有效的結(jié)論4第12講證明的方法推理與重言式定理：命題公式A1,A2,…,Ak推出B的推理正確當(dāng)且僅當(dāng)A1∧A2∧…∧AkB邏輯蘊(yùn)涵式的三種證明方法真值表法對(duì)指派進(jìn)行討論利用代入、替換進(jìn)行推演5第12講證明的方法推理與重言式定理：命題公式A1,A2,…,Ak推出B的推理正確當(dāng)且僅當(dāng)A1∧A2∧…∧AkB判斷下面的推理是否正確：下午馬芳或去看電影或去游泳。她沒去看電影。所以，她去游泳了。

令p:馬芳下午去看電影;q:馬芳下午去游泳

前提：p∨q，┐p

結(jié)論：q根據(jù)I5，(p∨q)∧

┐pq。所以，推理正確6第12講證明的方法推理與重言式定理：命題公式A1,A2,…,Ak推B的推理正確當(dāng)且僅當(dāng)A1∧A2∧…∧AkB判斷下面的推理是否正確：若下午氣溫超過30C，則馬芳必去游泳。若她去游泳，她就不去看電影了。所以，若馬芳沒去看電影，下午氣溫必超過30C。

令p:下午氣溫超過30C；q:馬芳去游泳;r:馬芳去看電影

前提：p→q，q

→

┐r

結(jié)論：┐r

→

p當(dāng)指派為(0,0,0)時(shí)，(p→q)∧(q

→

┐r)→(┐r

→

p)=0所以，推理錯(cuò)誤pqrp→qq

→

┐r┐r

→

p(p→q)∧(q

→

┐r)→(┐r

→

p)000110000111110101100011101110001111010111110111111110117第12講證明的方法應(yīng)用：證明在實(shí)際應(yīng)用中常見的情況是:

已知一個(gè)前提的集合，例如{A,B,C,D}，要求證一個(gè)結(jié)論，例如K，或求解“K是否可以由前提集合推出”。我們可以怎么做？（1）求證：ABCD

K；或證明ABCD

K不能成立

（2）想想我們?cè)凇白C明”中是怎樣做的：建立一個(gè)由A,B,C,D以及由它們用邏輯規(guī)則推理出的結(jié)果的序列，而這個(gè)序列的末段是K。如何完成這樣的證明？可用哪些邏輯規(guī)則？這正是“證明技術(shù)”要告訴大家的。8第12講證明的方法證明技術(shù)常用規(guī)則前提引入規(guī)則：在證明的任何步驟都可引入前提結(jié)論引入規(guī)則：在證明的任何步驟得到的結(jié)論都可作為后繼證明的前提置換規(guī)則：在證明的任何步驟，命題公式中的子公式都可以用與之等價(jià)的公式置換化簡(jiǎn)規(guī)則附加規(guī)則A∴A∨B由重要邏輯蘊(yùn)含式和結(jié)論引入規(guī)則可導(dǎo)出以下各條推理規(guī)則使用已知的邏輯等價(jià)公式I1AA∨BAB∴AI2A∧BA9第12講證明的方法證明技術(shù)常用規(guī)則假言推理規(guī)則拒取式規(guī)則假言三段論規(guī)則析取三段論規(guī)則AB┐B∴┐AABBC∴ACI6(A→B)∧(B→C)A→CI4(A→B)∧┐B┐AA∨B

┐B∴AI5┐A∧(A∨B)B，┐B∧(A∨B)AABA∴BI3A∧(A→B)B10第12講證明的方法證明技術(shù)常用規(guī)則合取引入規(guī)則構(gòu)造性二難推理規(guī)則破壞性二難推理規(guī)則AB∴ABABCDA∨C∴B∨DABCD┐B∨┐D∴┐A∨┐C11第12講證明的方法實(shí)例1：形式化前提：1、只要你認(rèn)真聽課、認(rèn)真做作業(yè)，你考試就能及格；2、你認(rèn)真聽課；3、你考試不及格；結(jié)論：你沒有認(rèn)真做作業(yè)p:你認(rèn)真聽課；q：你認(rèn)真做作業(yè)；r：你考試及格；1、p∧q→r2、p：你認(rèn)真聽課；3、┐r：你考試不及格；要證明：p∧q→r,p,┐r┐q12第12講證明的方法實(shí)例1：證明要證明：p∧q→r,p,┐r┐q（1）┐r

引入前提（2）p∧q→r

引入前提（3）┐r→┐(p∧q)

由（2）置換據(jù)A→B┐B→┐A（5）┐p∨┐q

由（4）置換據(jù)┐(A∧B)┐A∨┐B（6）p

引入前提（4）┐(p∧q)

由（1）（3）假言推理（7）┐q

由（6）（5）析取三段論13第12講證明的方法實(shí)例2要證明：p∨q,pr,qss∨rp∨q

引入前提┐pq

由(1)置換qs

引入前提┐ps

由(2)(3)假言三段論┐s

p 由(4)置換pr 引入前提┐s

r 由(5)(6)假言三段論s∨r

由(7)置換14第12講證明的方法兩種構(gòu)造證明方法（1）歸謬法設(shè)推理的形式結(jié)構(gòu)具有如下形式

A1∧A2∧…∧AkB此時(shí)若將┐B作為推理的前提推出矛盾，則說明推理正確若證A1∧A2∧…∧AkB，即證(A1∧A2∧…∧Ak)B為永真式

(A1∧A2∧…∧Ak)B┐(A1∧A2∧…∧Ak)∨B┐(A1∧A2∧…∧Ak∧┐B)所以，若A1∧A2∧…∧Ak∧┐B

為矛盾式，則說明(A1∧A2∧…∧Ak)B為重言式，即A1∧A2∧…∧AkB推理正確15第12講證明的方法實(shí)例3已知事實(shí)：（a）如果委員會(huì)拒絕通過新條令，那么罷工不結(jié)束，或者罷工持續(xù)一年并且商行董事長辭職。（b）罷工剛剛開始。得出結(jié)論：如果委員會(huì)拒絕通過新條令,那么罷工不結(jié)束。證明上述推理是正確的(有效的)。解.首先將事實(shí)和結(jié)論形式化。

p：委員會(huì)拒絕通過新條令。

q：罷工結(jié)束。

r：商行董事長辭職。s：罷工持續(xù)一年。于是,問題的已知事實(shí)是{p→(┐q∨(r∧s)),┐s},結(jié)論是p→┐q

欲證(p→(┐q∨(r∧s)))∧┐s

p→┐q

16第12講證明的方法方法一使用歸謬法（1）┐(p→┐q)

引入結(jié)論的否定（2）┐(┐p∨┐q) 由(1)置換（3）p∧q 由(2)置換（4）p 由(3)化簡(jiǎn)（5）p→(┐q∨(r∧s)) 引入前提（6）┐q∨(r∧s)) 由(4)(5)假言推理（7）q 由(3)化簡(jiǎn)（8）r∧s 由(6)(7)析取三段論（9）s 由(8)化簡(jiǎn)（10）┐s 引入前提（11）┐s∧s（矛盾） 由(9)(10)合取引入欲證p→(┐q∨(r∧s))∧┐sp→┐q

17第12講證明的方法兩種構(gòu)造證明方法（2）附加前提證明法設(shè)推理的形式結(jié)構(gòu)具有如下形式

A1∧A2∧…∧AkAB此時(shí)可將結(jié)論中的前件A作為推理的前提，使結(jié)論為B推理的形式結(jié)構(gòu)改寫為 A1∧A2∧…∧Ak∧

A

B若證A1∧A2∧…∧AkAB，即證(A1∧A2∧…∧Ak)(AB)為永真式(A1∧A2∧…∧Ak)(AB)┐(A1∧A2∧…∧Ak)∨(┐A∨B)(┐A1∨┐A2∨…∨┐Ak)∨(┐A∨B)(┐A1∨┐A2∨…∨┐Ak∨┐A)

∨B┐(A1∧A2∧…∧Ak

∧A)∨B(A1∧A2∧…∧Ak

∧A)B所以，若將A作為附加前提，如有A1∧A2∧…∧Ak

∧

A

B，即證A1∧A2∧…∧AkAB18第12講證明的方法方法二使用附加前提證明法（1）p→(┐q∨(r∧s))引入前提（2）p附加前提引入（3）┐q∨(r∧s)由(1)(2)假言推理（4）(┐q∨r)∧(┐q∨s)由(3)置換（5）┐q∨s 由(4)化簡(jiǎn)（6）┐s 引入前提（7）┐q由(5)(6)析取三段論欲證（p→(┐q∨(r∧s))）∧┐sp→┐q

19第12講證明的方法實(shí)例4已知事實(shí)：（a）如果委員會(huì)拒絕通過新條令，那么罷工不結(jié)束，或者罷工持續(xù)一年并且商行董事長辭職。（b）罷工剛剛開始。得出結(jié)論：如果委員會(huì)拒絕通過新條令,那么罷工結(jié)束。證明上述推理是不正確的(無效的)。解.首先將事實(shí)和結(jié)論形式化。

p：委員會(huì)拒絕通過新條令。

q：罷工結(jié)束。

r：商行董事長辭職。s：罷工持續(xù)一年。于是,問題的已知事實(shí)是p→(┐q∨(r∧s)),┐s,結(jié)論是p→q

欲證（p→(┐q∨(r∧s))）∧┐s

p→q不成立。20第12講證明的方法實(shí)例4為了證明p→(┐q∨(r∧s))∧┐s

p→q不成立，只要給出一種指派，使得p→(┐q∨(r∧s))，┐s均為真，但使p→q為假。不難看出，這一指派應(yīng)使得p為真，使得q為假，從而計(jì)算得這一指派應(yīng)使s為假(而對(duì)r可隨意指派真假)。21第12講證明的方法本講小結(jié)主要內(nèi)容推理、前提、結(jié)論、正確的推理推理規(guī)則證明的技術(shù)作業(yè)(補(bǔ)P601,2(1),4）┐(P∧┐Q),┐Q∨R,┐R┐PJ(M∨N)，(H∨G)J,H∨GM∨NA(BC),(C∧D)E,┐F(D∧┐E)A(BF)構(gòu)造下面推理的證明：只要A曾到過受害者房間并且11點(diǎn)以前沒離開，A就是謀殺嫌犯；A曾到過受害者房間；如果A在11點(diǎn)以前離開房間，看門人會(huì)看見他；看門人沒有看見他。所以，A是謀殺嫌犯。22第12講證明的方法-23-一些重要的邏輯等價(jià)式E1┐┐A

A

雙重否定律E2A∨A

A，A∧A

A 冪等律E3A∨B

B∨A，A∧B

B∧A交換律E4(A∨B)∨C

A∨(B∨C) 結(jié)合律

(A∧B)∧C

A∧(B∧C)E5A∧(B∨C)(A∧B)∨(A∧C) 分配律

A∨(B∧C)(A∨B)∧(A∨C)23第12講證明的方法-24-一些重要的邏輯等價(jià)式E6┐(A∨B)

┐A∧┐B DeMorgan律┐(A∧B)

┐A∨┐BE7A∨(A∧B)

A 吸收律

A∧(A∨B)

AE8A→B

┐A∨B蘊(yùn)涵表達(dá)式E9A