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

離散數(shù)學(xué)命題邏輯推理理論1第一頁，共二十三頁，2022年，8月28日有效推理定義2.20若對于每組賦值,A1ùA2ù…ù

Ak

為假,或者當(dāng)A1ùA2ù…ùAk為真時,B也為真,則稱由前提A1,A2,…,Ak推B的推理有效或推理正確,并稱B是有效的結(jié)論定理2.8由前提A1,A2,…,Ak

推出B的推理正確當(dāng)且僅當(dāng)

A1ùA2ù…ùAk?B為重言式.2第二頁，共二十三頁，2022年，8月28日推理的形式結(jié)構(gòu)形式(1)

A1ùA2ù…ùAk?B形式(2)前提:A1,A2,…,Ak

結(jié)論:B

推理正確記作A1ùA2ù…ùAkTB判斷推理是否正確的方法:真值表法等值演算法主析取范式法構(gòu)造證明法3第三頁，共二十三頁，2022年，8月28日實例例1判斷下面推理是否正確:(1)若今天是1號,則明天是5號.今天是1號.所以,明天是5號.解設(shè)p:今天是1號,q:明天是5號推理的形式結(jié)構(gòu)為(p?q)ùp?q證明用等值演算法(p?q)ùp?q

?

?((?púq)ùp)úq?((pù?q)ú?p)úq

?

?pú?qúq

?1得證推理正確4第四頁，共二十三頁，2022年，8月28日實例(續(xù))(2)若今天是1號,則明天是5號.明天是5號.所以,今天是1號.解設(shè)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úm301是成假賦值,所以推理不正確.5第五頁，共二十三頁，2022年，8月28日推理定律——重言蘊涵式

A

T(AúB)附加律(AùB)T

A

化簡律(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)等價三段論(A?B)ù(C?D)ù(AúC)T(BúD)構(gòu)造性二難(A?B)ù(?A?B)T

B

構(gòu)造性二難(特殊形式)(A?B)ù(C?D)ù(?Bú?D)T(?Aú?C)破壞性二難6第六頁，共二十三頁，2022年，8月28日自然推理系統(tǒng)P自然推理系統(tǒng)P由下述3部分組成:1.字母表(1)命題變項符號:p,q,r,…,pi,qi,ri,…(2)聯(lián)結(jié)詞:

,

,,,(3)括號與逗號:(),,2.合式公式3.推理規(guī)則(1)前提引入規(guī)則(2)結(jié)論引入規(guī)則(3)置換規(guī)則7第七頁，共二十三頁，2022年，8月28日自然推理系統(tǒng)P(續(xù))(7)拒取式規(guī)則

A?B

?B

\?A(8)假言三段論規(guī)則

A?B

B?C

\A?C

(4)假言推理規(guī)則

A?BA

\B(5)附加規(guī)則

A

\AúB(6)化簡規(guī)則

AùB

\A

8第八頁，共二十三頁，2022年，8月28日自然推理系統(tǒng)P(續(xù))(11)破壞性二難推理規(guī)則

A?B

C?D

?Bú?D

\?Aú?C(12)合取引入規(guī)則

A

B

\AùB

(9)析取三段論規(guī)則

AúB

?B

\A(10)構(gòu)造性二難推理規(guī)則

A?B

C?D

AúC

\BúD9第九頁，共二十三頁，2022年，8月28日直接證明法例2在自然推理系統(tǒng)P中構(gòu)造下面推理的證明:前提:

púq,q?r,p?s,?s結(jié)論:rù(púq)證明①

p?s前提引入②?s

前提引入③

?p

①②拒取式④

púq

前提引入⑤q

③④析取三段論

⑥q?r

前提引入⑦r

⑤⑥假言推理⑧rù(púq)

⑦④合取推理正確,rù(púq)是有效結(jié)論10第十頁，共二十三頁，2022年，8月28日實例例3構(gòu)造推理的證明:若明天是星期一或星期三,我就有課.若有課,今天必需備課.我今天下午沒備課.所以,明天不是星期一和星期三.解設(shè)p:明天是星期一,q:明天是星期三，

r:我有課，s:我備課前提:(púq)?r,r?s,?s結(jié)論:?pù?q

11第十一頁，共二十三頁，2022年，8月28日實例(續(xù))前提:(púq)?r,r?s,?s結(jié)論:?pù?q

證明①r?s

前提引入②?s

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

前提引入⑤?(púq)③④拒取式⑥?pù?q⑤置換結(jié)論有效,即明天不是星期一和星期三12第十二頁，共二十三頁，2022年，8月28日附加前提證明法欲證明等價地證明前提:A1,A2,…,Ak前提:A1,A2,…,Ak,C結(jié)論:C?B結(jié)論:B理由:(A1ùA2ù…ùAk)?(C?B)

?

?(A1ùA2ù…ùAk)ú(?CúB)

?

?(A1ùA2ù…ùAkùC)úB

?(A1ùA2ù…ùAkùC)?B13第十三頁，共二十三頁，2022年，8月28日實例例4構(gòu)造下面推理的證明:前提:?púq,?qúr,r?s結(jié)論:p?s證明①

p附加前提引入②?púq

前提引入③

q

①②析取三段論④

?qúr

前提引入⑤r

③④析取三段論

⑥r(nóng)?s

前提引入⑦s

⑤⑥假言推理推理正確,p?s是有效結(jié)論14第十四頁，共二十三頁，2022年，8月28日歸謬法(反證法)欲證明前提：A1,A2,…,Ak

結(jié)論：B將?B加入前提,若推出矛盾,則得證推理正確.理由:A1ùA2ù…ùAk?B

?

?(A1ùA2ù…ùAk)úB

?

?(A1ùA2ù…ùAkù?B)括號內(nèi)部為矛盾式當(dāng)且僅當(dāng)(A1ùA2ù…ùAk?B)為重言式15第十五頁，共二十三頁，2022年，8月28日實例例5構(gòu)造下面推理的證明前提:?(pùq)úr,r?s,?s,p結(jié)論:?q證明用歸繆法①q

結(jié)論否定引入②r?s

前提引入③?s

前提引入④?r②③拒取式16第十六頁，共二十三頁，2022年，8月28日實例(續(xù))⑤?(pùq)úr

前提引入⑥?(pùq)④⑤析取三段論⑦?pú?q⑥置換⑧?p①⑦析取三段論⑨p

前提引入⑩?pùp⑧⑨合取推理正確,?q是有效結(jié)論17第十七頁，共二十三頁，2022年，8月28日歸結(jié)證明法理由(púq)ù(?púr)?(qúr)??((púq)ù(?púr))ú(qúr)?(?pù?q)ú(pù?r)úqúr?((?pù?q)úq)ú((pù?r)úr)?(?púq)ú(púr)?1歸結(jié)規(guī)則

AúB

?AúC

\BúC18第十八頁，共二十三頁，2022年，8月28日歸結(jié)證明法(續(xù))在自然推理系統(tǒng)P中只需下述推理規(guī)則:(1)前提引入規(guī)則(2)結(jié)論引入規(guī)則(3)置換規(guī)則(4)化簡規(guī)則(5)合取引入規(guī)則(6)歸結(jié)規(guī)則19第十九頁，共二十三頁，2022年，8月28日歸結(jié)證明法的基本步驟1.將每一個前提化成等值的合取范式,設(shè)所有合取范式的全部簡單析取式為A1,A2,…,At2.將結(jié)論化成等值的合取范式B1ùB2ù…ùBs,其中每個Bj是簡單析取式3.以A1,A2,…,At為前提,使用歸結(jié)規(guī)則推出每一個Bj,1js4.由合取引入規(guī)則得到結(jié)論B1ùB2ù…ùBs20第二十頁，共二十三頁，2022年，8月28日實例例6用歸結(jié)證明法構(gòu)造下面推理的證明:前提:(p?q)?r,r?s,?s結(jié)論:(p?q)?(pùs)解(p?q)?r??(?púq)úr?(pù?q)úr?(púr)ù(?qúr)

r?s??rús(p?q)?(pùs)??(?púq)ú(pùs)?(pù?q)ú(pùs)?pù(?qús)推理可表成前提:púr,?qúr,?rús,?s結(jié)論:pù(?qús)21第二十一頁，共二十三頁，2022年，8月28