命題邏輯推理理論離散數(shù)學1第一頁，共二十六頁，編輯于2023年，星期日2.4.1推理的形式結(jié)構(gòu)一、什么是推理定義2.19設A1，A2，

…，Ak，B都是命題公式，若對于每組賦值,A1A2

…Ak為假,或者當A1

A2

…

Ak為真時，B也為真,則稱由前提A1，A2，…,Ak推B的推理有效或推理正確,并稱B是有效的結(jié)論。2第二頁，共二十六頁，編輯于2023年，星期日定理2.8

由前提A1,A2,…,Ak

推出B的推理正確當且僅當

A1

A2

…

Ak

B為重言式.如果把（A1

A2

…

Ak）

B為永真式記為：上式的含義？？？3第三頁，共二十六頁，編輯于2023年，星期日二、推理的形式結(jié)構(gòu)定義2.20稱（A1

A2

…

Ak）

B為由前提A1,A2,…,Ak推結(jié)論B的推理的形式結(jié)構(gòu)。推理的形式結(jié)構(gòu)一般有以下三種：形式(1)

A1

A2

…

Ak

B

形式(2)

前提:A1,A2,…,Ak

結(jié)論:B

形式(3)A1，

A2，

…，

Ak

B4第四頁，共二十六頁，編輯于2023年，星期日真值表法等值演算法主析取范式法構(gòu)造證明法判斷推理是否正確的方法:真值表的方法參見P.67例2.23。5第五頁，共二十六頁，編輯于2023年，星期日例1

判斷下面推理是否正確:(1)若今天是1號,則明天是5號.今天是1號.所以,明天是5號.解設p:今天是1號,q:明天是5號推理的形式結(jié)構(gòu)為證明用等值演算法所以，原推理正確。6第六頁，共二十六頁，編輯于2023年，星期日例1(2)若今天是1號,則明天是5號.明天是5號.所以,今天是1號。解設p:今天是1號,q:明天是5號推理的形式結(jié)構(gòu)為證明用主析取范式法這不是一個永真式，01是該公式成假的賦值，所以推理不正確。7第七頁，共二十六頁，編輯于2023年，星期日三、推理定律——重言蘊涵式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)破壞性二難8第八頁，共二十六頁，編輯于2023年，星期日注意：（1）推理規(guī)則中出現(xiàn)的A、B、C等是元語言符號；（2）直接引用而不需證明，只要說明所引用規(guī)則的名稱；（3）24個永真公式每個都可以等效為2個推理規(guī)則。9第九頁，共二十六頁，編輯于2023年，星期日2.4.2自然推理系統(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ī)則10第十頁，共二十六頁，編輯于2023年，星期日自然推理系統(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

11第十一頁，共二十六頁，編輯于2023年，星期日自然推理系統(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úD12第十二頁，共二十六頁，編輯于2023年，星期日直接證明法例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é)論13第十三頁，共二十六頁，編輯于2023年，星期日實例例3

構(gòu)造推理的證明:若明天是星期一或星期三,我就有課.若有課,今天必需備課.我今天下午沒備課.所以,明天不是星期一和星期三.解設p:明天是星期一,q:明天是星期三，

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

14第十四頁，共二十六頁，編輯于2023年，星期日實例(續(xù))前提:(púq)?r,r?s,?s結(jié)論:?pù?q

證明①r?s

前提引入②?s

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

前提引入⑤?(púq)③④拒取式⑥?pù?q⑤置換結(jié)論有效,即明天不是星期一和星期三15第十五頁，共二十六頁，編輯于2023年，星期日附加前提證明法欲證明等價地證明前提: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)?B16第十六頁，共二十六頁，編輯于2023年，星期日實例例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é)論17第十七頁，共二十六頁，編輯于2023年，星期日歸謬法(反證法)欲證明前提：A1,A2,…,Ak

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

?

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

?

?(A1ùA2ù…ùAkù?B)括號內(nèi)部為矛盾式當且僅當(A1ùA2ù…ùAk?B)為重言式18第十八頁，共二十六頁，編輯于2023年，星期日實例例5

構(gòu)造下面推理的證明前提:?(pùq)úr,r?s,?s,p結(jié)論:?q證明用歸繆法①q

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

前提引入③?s

前提引入④?r②③拒取式19第十九頁，共二十六頁，編輯于2023年，星期日實例(續(xù))⑤?(pùq)úr

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

前提引入⑩?pùp⑧⑨合取推理正確,?q是有效結(jié)論20第二十頁，共二十六頁，編輯于2023