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

1、121.8.1常用的證明方法常用的證明方法1.8.2真值表法真值表法 (Truth Table)1.8.3直接證法直接證法 (Direct Proof1.8.4 間接證法間接證法 (Indirect Proof3 1.8.1常用的證明方法常用的證明方法 定義定義1.8.1 ：設(shè)和是兩個(gè)命題公式：設(shè)和是兩個(gè)命題公式,當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)為一重言式，即為一重言式，即,稱是的有效結(jié)論稱是的有效結(jié)論;或稱可或稱可由邏輯推出由邏輯推出.一般地一般地,如果有如果有n個(gè)前提個(gè)前提H1,H2,H3,.,Hn , 若H1H2H3.HnC,則稱C是一組前提H1,H2,Hn的有效結(jié)論。 注意注意:在形式邏輯中在形式邏輯

2、中,我們并不關(guān)心結(jié)論是否真實(shí)我們并不關(guān)心結(jié)論是否真實(shí),而主要而主要關(guān)心結(jié)論是否可以由給定的前提推出來關(guān)心結(jié)論是否可以由給定的前提推出來,我們只注意推我們只注意推理的形式是否正確理的形式是否正確.因此因此,有效結(jié)論并不一定是正確的有效結(jié)論并不一定是正確的,只只有正確的前提經(jīng)過正確的推理得到的邏輯結(jié)論才是正確有正確的前提經(jīng)過正確的推理得到的邏輯結(jié)論才是正確的的.4 證明證明C是是A的有效結(jié)論的方法就是判別重言蘊(yùn)含的方的有效結(jié)論的方法就是判別重言蘊(yùn)含的方法法.前面我們介紹的論證方法有真值表法、等值演算前面我們介紹的論證方法有真值表法、等值演算法、主析（合）取范式法。論證方法千變?nèi)f化，但法、主析（合）

3、取范式法。論證方法千變?nèi)f化，但最基本、最常用的方法有三最基本、最常用的方法有三種：種： 推理證明的方法推理證明的方法間接證法直接證法真值表法附加前提證明法歸謬法51.8.2真值表法真值表法 (Truth Table)構(gòu)造命題公式構(gòu)造命題公式H1 H2 Hn C的真值表，若為永的真值表，若為永真，真，H1 H2 Hn C 推理正確。推理正確。例：例：證明證明( (PQ)Q) PPQ PQ Q( (PQ)Q( (PQ)Q)P0001010110011011111110016由上面真值表可知由上面真值表可知( (PQ)Q) P。 1.8.3直接證法直接證法 (Direct Proof 直接證法：直接

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

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

6、.如果考試及格，那我高興。若我高興，那么我如果考試及格，那我高興。若我高興，那么我飯量增加。我的飯量沒增加，所以我考試沒有及飯量增加。我的飯量沒增加，所以我考試沒有及格。格。試對(duì)上述論證構(gòu)造證明。試對(duì)上述論證構(gòu)造證明。解：設(shè)解：設(shè)P P：我考試及格：我考試及格. Q. Q：我高興。：我高興。R R：我飯量增加。：我飯量增加。則此論證可表為則此論證可表為 (PQ)(PQ) (QR)(QR) RRPP 證證: 1: 1PQ PQ P P 2 2QRQRP P 3 3 RRP P 4 4 QQT T，2 2，3 I3 I1212 5 5 PPT T，1 1，4 I4 I12129例例2.2.證明證明

7、 R R S S是是前提前提C C D D，CR,DSCR,DS的的有有效結(jié)論效結(jié)論。 證：證：10例例2.2.證明證明 R R S S是是前提前提C C D D，CR,DSCR,DS的的有效結(jié)論有效結(jié)論。 證：證：1.C1.C D PD P 2.CR P 2.CR P 3.DS P 3.DS P 4.CD T 4.CD T，1 E1 E 5.RC T 5.RC T，2 E2 E 6.RS T 6.RS T，5 5，4 4，3 3 I I1313 7.R 7.R S TS T，6 E6 E11例例3：證明證明: PQ , QR, PS , S R(QP) 證：證：12例例3：PQ , QR,

8、PS , S R(QP) 證明：證明： 1. P S P (前提引入前提引入) 2. S P (前提引入前提引入) 3. P T1, 2 I I1111 4. PQ P (前提引入前提引入) 5. Q T3,4 I I1111 6. QR P (前提引入前提引入) 7. R T5,6 I I1111 8. R(QP) T4,7 I I9 913例例4：證明：證明 (P（QR)(S Q)(PS)R.證證：14例例4：證明：證明 (P（QR)(S Q)(PS)R.證證：（：（1） PS P （2） P T（1） I I1 1 （3） S T（1） I I1 1 （4） P（QR) P （5） QR

9、 T (2)，(4) I I1111 （6） S Q P （7） Q T(3)，(6) I I1111 （8） R T(5)，(7) I I1111151.8.4 間接證法間接證法 (Indirect Proof 適用于如下類型蘊(yùn)含式的證明適用于如下類型蘊(yùn)含式的證明: (A1A2Ak) (AB) (*) 欲證明欲證明(*)式，只需證明式，只需證明 (A1A2AkA) B 即可，因?yàn)榧纯?，因?yàn)?6 (A1A2Ak)(AB)(A1A2Ak) (A B ) (A1A2 Ak) ( A B ) (A1A2 Ak) (AB) A1A2AkAB (A1A2AkA)B (A1A2AkA)B (A1A2AkA

10、) B這樣一來這樣一來,原來結(jié)論中的前件原來結(jié)論中的前件A就變成了前提就變成了前提,稱稱A為為附加附加前提前提. 17由證由證(A1A2AkA)B永真而證得永真而證得(A1A2Ak)(AB)永真的證明方法永真的證明方法, 稱為稱為18例例1:證明證明:(AB C) (BA) (DC) (AD)證：證： 19例例1:證明證明:(AB C) (BA) (DC) (AD)證：證：1. AB C P 2. BA P 3. DC P 4. A P(附加前提附加前提) 5. B C T1，4 I I1111 6. AB T2, E 7. CD T3 ，E 8. B T4，6 I I1111 9. C T5

11、，8 I I1111 10. D T7，9 I I1111 11. AD ，10 CP 20 例例2：前提：前提：P(QR) , SP , Q 結(jié)論：結(jié)論：SR.證明：證明：21 例例2：前提：前提：P(QR) , SP , Q 結(jié)論：結(jié)論：SR.證明：證明： 1. SP P 2. S P（附加（附加前提引入）前提引入） 3. P T（1, 2） I I1111 4. P(QR) P 5. QR T（3,4） I I1111 6. Q P 7. R T（5,6） I I11 11 8. SR T（2,7） CPCP222. 歸謬法歸謬法定義定義1.8.21.8.2：設(shè)命題公式集合為設(shè)命題公式集

12、合為HH1 1, ,H H2 2, ,H H3 3, ,. ., ,H Hn n ，若，若H H1 1 H H2 2 H H3 3 . H Hn n為永假式，則稱為永假式，則稱HH1 1, ,H H2 2, ,H H3 3, ,. ., ,H Hn n 是不是不相容的，否則稱為相容的。相容的，否則稱為相容的。由于由于 (A1A2Ak)B (A1A2Ak)B (A1A2 AkB)故要證故要證(A1A2Ak)B永真永真,只需證只需證A1A2 AkB永假永假.這種將這種將B作為附加前提作為附加前提推出矛盾的證明方法稱為推出矛盾的證明方法稱為歸謬法歸謬法.23 例例1:證明證明 (PQ)Q)(RQ)(

13、RS)S) PP證證：24 例例1:證明證明 (PQ)Q)(RQ)(RS)S) PP證證：1. P P(附加前提附加前提) 2. PQQ P 3. QQ T(1, 2) I I1111 4. RQ P 5. R T(3,4) I I1111 6. RSS P 7. R T(6) I I1 1 8. RR(矛盾）矛盾）T(5,7) 由由8得出了矛盾得出了矛盾,根據(jù)歸謬法說明原推理正確根據(jù)歸謬法說明原推理正確.25 例例2:從從P P QRQR S,(TQ)S,(TQ) (SU),R,(WP)(SU),R,(WP) (T(TU) U) 推出推出 WTWT證：證：26例例2:從從P P QRQR S

14、,(TQ)S,(TQ) (SU),R,(WP)(SU),R,(WP) (TU) (TU) 推出推出 WTWT證：證： 1. P1. P QRQR S P S P 2.(TQ) 2.(TQ) (SU) P(SU) P 3.(WP) 3.(WP) (TU) P(TU) P 4. R P 4. R P 5. W P( 5. W P(附加前提附加前提) ) 6. R 6. RS S T 4 I T 4 I 7. (R7. (R S) T 6 ES) T 6 E 8. (P 8. (P Q) T 1Q) T 1，7 I7 I1111 9 .(WP) T3,I.(WP) T3,I 10. P T510.

15、P T5，9 I9 I 11. PPQ T8,EQ T8,E 12. Q T 10 12. Q T 10，11 I11 I1111 13. TQ T 2 ITQ T 2 I1111 14. T T 12 14. T T 12，13 I13 I1111 15. WT 15. WT ,15 CP,15 CP27小結(jié)小結(jié):本節(jié)將推理證明命題公式序列化本節(jié)將推理證明命題公式序列化.主要主要介紹了推理證明重言蘊(yùn)含式的直接證法和介紹了推理證明重言蘊(yùn)含式的直接證法和間接證法。間接證法。 作業(yè)作業(yè): 1. P46-47 (1)a, (2) e (3) a,b 2. 預(yù)習(xí)第二章預(yù)習(xí)第二章2.1,2.228補(bǔ)充補(bǔ)充:分分 情情 況況 證證 明明 欲證：欲證： (P(P1 1 P P2 2 P Pn n) )Q Q只需證明只需證明 1=i=n 1=i=n 有有 P Pi iQ Q因?yàn)椋阂驗(yàn)椋?(P(P1 1 P P2 2 P Pn n)Q)Q (P(P1 1 P P2 2 P Pn n) ) Q Q （PP1 1 PP2 2 PPn n) ) Q Q (P(P1 1