離散數(shù)學(xué)：第一章1-6 推理理論

1第一章命題邏輯

1.1命題符號(hào)化及聯(lián)結(jié)詞1.2命題公式及分類1.3等值演算1.4聯(lián)結(jié)詞全功能集1.5對(duì)偶與范式1.6推理理論21.6

命題邏輯的推理理論

推理的形式結(jié)構(gòu)判斷推理是否正確的方法推理定律與推理規(guī)則構(gòu)造證明法3一、推理的形式結(jié)構(gòu)前提是指已知的命題公式；結(jié)論是從前提出發(fā)應(yīng)用推理規(guī)則推出的命題公式；推理是從前提推出結(jié)論的思維過(guò)程。若A1ùA2ù…ùAk?B為重言式，稱A1ùA2ù…ù

Ak推出結(jié)論B的推理正確。B是A1ùA2ù…ù

Ak的邏輯結(jié)論或有效結(jié)論。若推理正確，則記作：A1ùA2ù…ùAkTB.稱A1ùA2ù…ùAk?B為由前提A1ùA2ù…ù

Ak推出結(jié)論B的推理的形式結(jié)構(gòu)。4一、推理的形式結(jié)構(gòu)注意：推理正確，不能保證結(jié)論一定正確！因?yàn)榍疤峥赡苁清e(cuò)誤的。當(dāng)A1,A2,…,Ak中有為假時(shí)，A1ùA2ù…ùAk?B恒為真！只有在推理正確，且前提也正確時(shí)，才能保證結(jié)論正確！5二、判斷推理是否正確的方法真值表法等值演算法判斷推理是否正確主析取范式法構(gòu)造證明法證明推理正確

說(shuō)明：當(dāng)命題變項(xiàng)比較少時(shí)，用前3個(gè)方法比較方便,此時(shí)采用形式結(jié)構(gòu)“A1ùA2ù…ùAk?B”.而在構(gòu)造證明時(shí)，采用“前提:A1,A2,…,Ak,結(jié)論:B”.

例判斷下面推理是否正確。如果天氣涼快，小王就不去游泳。天氣涼快。所以小王沒(méi)去游泳。如果我上街，我一定去新華書(shū)店。我沒(méi)上街。所以我沒(méi)去新華書(shū)店。提示：先將命題符號(hào)化；再寫(xiě)出前提、結(jié)論、推理的形式結(jié)構(gòu)；最后進(jìn)行判斷。67推理定律——重言蘊(yùn)涵式

重要的推理定律

A

T(AúB)附加律

(AùB)T

A

化簡(jiǎn)律

(A?B)ùA

T

B

假言推理

(A?B)ù?B

T

?A

拒取式

(AúB)ù?B

T

A

析取三段論

(A?B)ù(B?C)T(A?C)假言三段論

(A?B)ù(B?C)T(A?C)等價(jià)三段論

(A?B)ù(C?D)ù(AúC)T(BúD)構(gòu)造性二難8構(gòu)造證明——直接證明法構(gòu)造下列推理的證明。前提：p?r,q?s,púq.

結(jié)論：rús.前提：púq,p??r,s?t,?s?r,?t.

結(jié)論：q.提示——常用推理規(guī)則還有：前提引入規(guī)則：任何步驟都可以引入前提；結(jié)論引入規(guī)則：已證明的結(jié)論均可作為后續(xù)證明的前提；置換規(guī)則：命題公式中的任何子命題均可用與之等值的命題公式置換；合取引入規(guī)則：A,BTAùB9直接證明法(續(xù))例構(gòu)造下面推理的證明：若明天是星期一或星期三，我就有課.若有課，今天必備課.我今天沒(méi)備課.所以，明天不是星期一和星期三.解

設(shè)p：明天是星期一，q：明天是星期三，

r：我有課，s：我備課推理的形式結(jié)構(gòu)為

前提：(púq)?r,r?s,?s

結(jié)論：?pù?q

10直接證明法(續(xù))前提：(púq)?r,r?s,?s

結(jié)論：?pù?q

證明①r?s

前提引入②?s

前提引入③?r①②拒取式④(púq)?r

前提引入⑤?(púq)③④拒取式⑥?pù?q⑤置換11構(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)?B12附加前提證明法(例)證明：①s

附加前提引入②?súp

前提引入③p①②析取三段論④p?(q?r)前提引入⑤q?r③④假言推理⑥q

前提引入⑦r⑤⑥假言推理前提：p?(q?r),?súp,q.

結(jié)論：s?r.13附加前提證明法(練習(xí))證明：①s

附加前提引入②r??s

前提引入③p?r

前提引入④p??s②③假言三段論⑤?p①④拒取式

⑥púq

前提引入⑦q⑤⑥析取三段論前提：púq,p?r,

r??s

結(jié)論：s?q14構(gòu)造證明——?dú)w謬法（反證法）

欲證明前提：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)為重言式。15歸謬法(例)證明：①q

否定結(jié)論引入

②p

前提引入

③p?(?(rùs)??q)

前提引入

④

?(rùs)??q

②③假言推理

⑤rùs①④拒取式

⑥?s

前提引入

⑦s

⑤化簡(jiǎn)

⑧?sùs

⑥⑦合取由⑧得出了矛盾，根據(jù)歸謬法說(shuō)明推理正確。

前提：p?(?(rùs)??q),

?s,p結(jié)論：?q.16歸謬法(練習(xí))證明：①q

否定結(jié)論引入

②r?s

前提引入

③?s

前提引入

④

?r

②③拒取式

⑤?(pùq)úr

前提引入

⑥?(pùq)④⑤析取三段論

⑦?pú?q⑥置換

⑧?p①⑦析取三段論

⑨p

前提引入

⑩?pùp⑧⑨合取由⑩得出了矛盾，根據(jù)歸謬法說(shuō)明推理正確。

前提：?(pùq)úr,r?s,?s,p結(jié)論：?q1717誰(shuí)養(yǎng)魚(yú)?此題源自1981年柏林的德國(guó)邏輯思考學(xué)院.....98%的測(cè)驗(yàn)者無(wú)法解題,以下是題目的中譯版.前提有五間房屋排成一列所有房屋的外表顏色都不一樣所有的屋主來(lái)自不同的國(guó)家所有的屋主都養(yǎng)不同的寵物;喝不同的飲料;抽不同牌的香煙1818誰(shuí)養(yǎng)魚(yú)?題示:英國(guó)人住在紅色房屋瑞典人養(yǎng)狗丹麥人喝茶綠色的房子在白色房子的左邊綠色房屋的屋主喝咖啡抽PallMall香煙的屋主養(yǎng)鳥(niǎo)黃色屋主抽Dunhill位於最中間的屋主喝牛奶挪威人住在第一間房屋抽Blend的人住在養(yǎng)貓人家的隔壁養(yǎng)馬的屋主隔壁住抽Dunhill的人家抽BlueMaster的屋主他喝啤酒德國(guó)人他抽Prince挪威人住在藍(lán)色房子隔壁只喝開(kāi)水的人家住在抽Blend的隔壁1919

答： 挪威-黃色房屋-貓-水-Dunhill

丹麥-藍(lán)色房屋-馬-茶-Blend

英國(guó)-紅色房屋-鳥(niǎo)-牛奶-Pall

德國(guó)-綠色房屋-魚(yú)-咖啡-Prince

瑞典-白色房屋-狗-啤酒-Blue問(wèn)題:請(qǐng)問(wèn)誰(shuí)養(yǎng)魚(yú)?房屋——紅色、綠色、白色、黃色、藍(lán)色主人——英國(guó)、瑞典、丹麥、挪威、德國(guó)飲料——茶、咖啡、牛奶、啤酒、水寵物——狗、鳥(niǎo)、貓、馬、魚(yú)香煙——Pall、Dunhill、Blend、Blue、Prince誰(shuí)養(yǎng)魚(yú)?20艾麗斯與謀殺案艾麗斯、艾麗斯的丈夫、他們的兒子、他們的女兒，還有艾麗斯的哥哥，卷入一樁謀殺案。這五人中的一人殺了其余四人中的一人。這五人的有關(guān)情況是：（1）在謀殺發(fā)生時(shí)，有一男一女兩人正在一家酒吧里。（2）在謀殺發(fā)生時(shí)，兇手和被害者兩人正在一個(gè)海灘上。（3）在謀殺發(fā)生時(shí)，兩個(gè)子女中的一個(gè)正一人獨(dú)處。（4）在謀殺發(fā)生時(shí)，艾麗斯和她的丈夫