離散數(shù)學(xué)(1.8推理理論)

1離散數(shù)學(xué)(DiscreteMathematics)2第一章命題邏輯（PropositionalLogic）

1.8推理理論(InferenceTheory)1.8.1常用的證明方法1.8.2真值表法

(TruthTable)1.8.3直接證法

(DirectProof)1.8.4間接證法

(IndirectProof)3第一章命題邏輯（PropositionalLogic）

1.8推理理論(InferenceTheory)

1.8.1常用的證明方法定義1.8.1

：設(shè)Ａ和Ｃ是兩個命題公式,當(dāng)且僅當(dāng)ＡＣ為一重言式，即ＡＣ,稱Ｃ是Ａ的有效結(jié)論;或稱Ｃ可由Ａ邏輯推出.一般地,如果有n個前提H1,H2,H3,.…,Hn

,

若H1H2H3....HnC,則稱C是一組前提H1,H2,…,Hn的有效結(jié)論。注意:在形式邏輯中,我們并不關(guān)心結(jié)論是否真實(shí),而主要關(guān)心結(jié)論是否可以由給定的前提推出來,我們只注意推理的形式是否正確.因此,有效結(jié)論并不一定是正確的,只有正確的前提經(jīng)過正確的推理得到的邏輯結(jié)論才是正確的.4第一章命題邏輯（PropositionalLogic）

1.8推理理論(InferenceTheory)證明C是A的有效結(jié)論的方法就是判別重言蘊(yùn)含的方法.前面我們介紹的論證方法有真值表法、等值演算法、主析（合）取范式法。論證方法千變?nèi)f化，但最基本、最常用的方法有三種：推理證明的方法5第一章命題邏輯（PropositionalLogic）

1.8推理理論(InferenceTheory)1.8.2真值表法

(TruthTable)構(gòu)造命題公式H1∧

H2∧……∧

Hn→C的真值表，若為永真，H1∧

H2∧……∧

HnC推理正確。例：證明((P∨Q)∧┐Q)PPQP∨Q┐Q(P∨Q)∧┐Q((P∨Q)∧┐Q)P0001010110011011111110016第一章命題邏輯（PropositionalLogic）

1.8推理理論(InferenceTheory)由上面真值表可知((P∨Q)∧┐Q)P。1.8.3直接證法

(DirectProof)直接證法：由一組前提，利用一些公認(rèn)的推理規(guī)則，根據(jù)已知的等價或蘊(yùn)含公式推演得到有效結(jié)論。常用的推理規(guī)則P規(guī)則:（也稱前提引入規(guī)則）前提在推導(dǎo)過程中的任何時候都可以引用。T規(guī)則:在推導(dǎo)過程中，所證明的結(jié)論、已知的等價或蘊(yùn)含公式都可以作為后續(xù)證明的前提，命題公式中的任何子公式都可以用與之等價的命題公式置換。7第一章命題邏輯（PropositionalLogic）

1.8推理理論(InferenceTheory)常用的蘊(yùn)含式和等價式見課本P43表1-8.3、1-8.4例1.如果考試及格，那我高興。若我高興，那么我飯量增加。我的飯量沒增加，所以我考試沒有及格。試對上述論證構(gòu)造證明。解：設(shè)P：我考試及格.Q：我高興。R：我飯量增加。則此論證可表為(P→Q)(Q→R)┐R┐P

證:8第一章命題邏輯（PropositionalLogic）

1.8推理理論(InferenceTheory)常用的蘊(yùn)含式和等價式見課本P43表1-8.3、1-8.4例1.如果考試及格，那我高興。若我高興，那么我飯量增加。我的飯量沒增加，所以我考試沒有及格。試對上述論證構(gòu)造證明。解：設(shè)P：我考試及格.Q：我高興。R：我飯量增加。則此論證可表為(P→Q)(Q→R)┐R┐P

證:1P→Q P2Q→R P3┐R P4┐Q T，2，3I125┐P T，1，4I129第一章命題邏輯（PropositionalLogic）

1.8推理理論(InferenceTheory)例2.證明RS是前提CD，C→R,D→S的有效結(jié)論。

證：10第一章命題邏輯（PropositionalLogic）

1.8推理理論(InferenceTheory)例2.證明RS是前提CD，C→R,D→S的有效結(jié)論。

證：1.CDP2.C→RP 3.D→SP4.┐C→DT，1E5.┐R→┐CT，2E6.┐R→ST，5，4，3I13

7.RST，6E11第一章命題邏輯（PropositionalLogic）

1.8推理理論(InferenceTheory)例3：證明:P∨Q,QR,PS,┐SR∧(Q∨P)

證：12第一章命題邏輯（PropositionalLogic）

1.8推理理論(InferenceTheory)例3：P∨Q,QR,PS,┐SR∧(Q∨P)

證明：1.PSP(前提引入)2.┐SP(前提引入)3.┐PT1,2I114.P∨QP(前提引入)5.QT3,4I116.QRP(前提引入)7.RT5,6I118.R∧(Q∨P)T4,7I913第一章命題邏輯（PropositionalLogic）

1.8推理理論(InferenceTheory)例4：證明(P（Q∨R))∧(┐S

┐Q)∧(P∧┐S)R.證：14第一章命題邏輯（PropositionalLogic）

1.8推理理論(InferenceTheory)例4：證明(P（Q∨R))∧(┐S

┐Q)∧(P∧┐S)R.證：（1）P∧┐SP（2）PT（1）I1（3）┐ST（1）I1（4）P（Q∨R)

P（5）Q∨RT(2)，(4)I11（6）┐S

┐Q

P（7）┐Q

T(3)，(6)I11（8）RT(5)，(7)I1115第一章命題邏輯（PropositionalLogic）

1.8推理理論(InferenceTheory)1.8.4間接證法

(IndirectProof)附加前提證明法適用于如下類型蘊(yùn)含式的證明:

(A1∧A2∧…∧Ak)(AB)(*)

欲證明(*)式，只需證明

(A1∧A2∧…∧Ak∧A)B即可，因?yàn)?6第一章命題邏輯（PropositionalLogic）

1.8推理理論(InferenceTheory)(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(A1∧A2∧…∧Ak∧A)

B這樣一來,原來結(jié)論中的前件A就變成了前提,稱A為附加前提.

17第一章命題邏輯（PropositionalLogic）

1.8推理理論(InferenceTheory)由證(A1∧A2∧…∧Ak∧A)B永真而證得(A1∧A2∧…∧Ak)(AB)永真的證明方法,稱為附加前提證明法或CP規(guī)則.18第一章命題邏輯（PropositionalLogic）

1.8推理理論(InferenceTheory)例1:證明:(A→BC)(B→┐A)(D→┐C)(A→┐D)證： 19第一章命題邏輯（PropositionalLogic）

1.8推理理論(InferenceTheory)例1:證明:(A→BC)(B→┐A)(D→┐C)(A→┐D)證：1.A→BCP2.B→┐AP3.D→┐CP4.AP(附加前提) 5.BCT1，4I11 6.A→┐BT2,E 7.C→┐DT3，E8.┐BT4，6I119.CT5，8I11 10.┐DT7，9I11 11.A→┐DＴ４，10CP 20第一章命題邏輯（PropositionalLogic）

1.8推理理論(InferenceTheory)

例2：前提：P(QR),SP,Q結(jié)論：SR.證明：21第一章命題邏輯（PropositionalLogic）

1.8推理理論(InferenceTheory)

例2：前提：P(QR),SP,Q結(jié)論：SR.證明：1.SPP2.SP（附加前提引入）3.PT（1,2）I114.P(QR)P5.QRT（3,4）I116.QP7.RT（5,6）I118.SRT（2,7）CP22第一章命題邏輯（PropositionalLogic）

1.8推理理論(InferenceTheory)2.歸謬法定義1.8.2：設(shè)命題公式集合為{H1,H2,H3,.…,Hn}，若H1H2H3....Hn為永假式，則稱{H1,H2,H3,.…,Hn}是不相容的，否則稱為相容的。由于(A1∧A2∧…∧Ak)B┐(A1∧A2∧…∧Ak)∨B┐(A1∧A2∧…Ak∧┐B)故要證(A1∧A2∧…∧Ak)B永真,只需證A1∧A2∧…Ak∧┐B永假.這種將┐B作為附加前提推出矛盾的證明方法稱為歸謬法.23第一章命題邏輯（PropositionalLogic）

1.8推理理論(InferenceTheory)例1:證明(P┐Q)∧(┐R∨Q)∧(R∧┐S)┐P證：24第一章命題邏輯（PropositionalLogic）

1.8推理理論(InferenceTheory)例1:證明(P┐Q)∧(┐R∨Q)∧(R∧┐S)┐P證：1.

PP(附加前提)2.P┐Q

P3.┐Q

T(1,2)I114.┐R∨Q

P5.┐RT(3,4)I116.R∧┐SP7.RT(6)I18.R∧┐R(矛盾）T(5,7)由8得出了矛盾,根據(jù)歸謬法說明原推理正確.25第一章命題邏輯（PropositionalLogic）

1.8推理理論(InferenceTheory)例2:從PQ→RS,(T→Q)(S→U),┐R,(W→P)(T→U)推出W→┐T證：26第一章命題邏輯（PropositionalLogic）

1.8推理理論(InferenceTheory)例2:從PQ→RS,(T→Q)(S→U),┐R,(W→P)(T→U)推出W→┐T證：1.PQ→RSP2.(T→Q)(S→U)P3.(W→P)(T→U)P4.┐RP5.WP(附加前提) 6.┐R∨┐S T4I

7.┐(RS)T6E8.┐(PQ)T1，7I11 9.(W→P)T3,I

10.PT5，9I11.┐P∨┐QT8,E12.┐QT10，11I11 13.T→QT2I1114.┐TT12，13I1115.W→┐TＴ５,15CP27第一章命題邏輯（PropositionalLogic）

1.8推理理論(Infe