離散數(shù)學方世昌第5節(jié)

1.5推理規(guī)則(guīzé)和證明方法講授重點：推理規(guī)則(guīzé)，直接證明方法與CP規(guī)則(guīzé)講授難點：直接證明方法，CP規(guī)則與反證法1共三十九頁什么(shénme)是推理？1.推理(tuīlǐ)和推理(tuīlǐ)規(guī)則推理:從前提推出結論的思維過程。前提:指已知的命題公式。結論:從前提出發(fā)，應用推理規(guī)則推出的命題公式。本節(jié)內容：從邏輯推理的角度來理解命題演算前提結論推理規(guī)則推理2共三十九頁推理的例子(lìzi)：設x屬于實數(shù),P:x是偶數(shù),Q:x2是偶數(shù)。例1.如果(rúguǒ)x是偶數(shù),則x2是偶數(shù)。x是偶數(shù)。x2是偶數(shù)。例3.如果x是偶數(shù),則x2是偶數(shù)。x不是偶數(shù)。x2不是偶數(shù)。例2.如果x是偶數(shù),則x2是偶數(shù)。x2是偶數(shù)。x是偶數(shù)。例4.如果x是偶數(shù),則x2是偶數(shù)。x2不是偶數(shù)。x不是偶數(shù)?！獭獭痢燎疤?------------結論四個例子的推理是否正確？所用依據(jù)是什么？3共三十九頁1、推理(tuīlǐ)和推理規(guī)則推理規(guī)則：正確推理的依據(jù)。任何一條永真蘊含式都可以作為一條推理規(guī)則。例：析取三段論：如果(rúguǒ)，P：他在釣魚，Q：他在下棋前提：他在釣魚或下棋；他不在釣魚結論：所以他在下棋

4共三十九頁定義1：若H1∧H2∧…∧Hn

C,則稱C是H1,H2,…,Hn的有效結論(jiélùn)。特別若A

B,則稱B是A的有效結論，或從A推出B。1、推理(tuīlǐ)和推理規(guī)則注意：不考慮前提的真假，推理正確≠結論為真。結論的真假取決于前提H1∧H2∧…∧Hn的真假。前提為真，則結論為真；前提為假，則結論可真可假。因此，定義中只說C是H1,H2,…,Hn

的有效結論而不說是正確結論?！坝行А笔侵附Y論的推出合乎推理規(guī)則。

5共三十九頁有效(yǒuxiào)結論如Q是P→Q，P的一個有效(yǒuxiào)結論。即證P∧(P→Q)永真蘊含Q也就是要證：P∧(P→Q)→Q是重言式.設P∧(P→Q)取值為真，則P為真，且P→Q為真，故Q為真故P∧(P→Q)→Q是重言式.假言推理P?QP

\Q6共三十九頁如：Q是?P，(PúQ)的有效結論(jiélùn)。即?Pù(PúQ)→Q是一個永真式。析取三段論規(guī)則

PúQ

?P

\Ｑ7共三十九頁推理(tuīlǐ)的形式結構形式(1)

H1ùH2ù…ùHn?C形式(2)前提:H1,H2,…,Hn結論(jiélùn):C

推理正確記作H1ùH2ù…ùHnTC注1.T與?的區(qū)別8共三十九頁推理(tuīlǐ)的形式結構形式(1)

H1ùH2ù…ùHn?C形式(2)前提:H1,H2,…,Hn結論(jiélùn):C

推理正確記作H1ùH2ù…ùHnTC對于實際中給出的推理:將推理中的（簡單）命題符號化寫出前提和結論判斷該推理是否正確正確：給出一個證明序列不正確：給出反例9共三十九頁常用的推理規(guī)則1)恒等式(E1~E24)2)永真蘊含式(I1~I8,表1.5-1)3)替換規(guī)則，代入規(guī)則4)P規(guī)則和T規(guī)則P規(guī)則：(前提引入)在推導的任何步驟上，都可以引入前提。T規(guī)則：(結論引用(yǐnyòng))在推導任何步驟上所得結論都可以作為后繼證明的前提。

1、推理(tuīlǐ)和推理規(guī)則10共三十九頁永真蘊含(yùnhán)式11共三十九頁(4)拒取式規(guī)則P?Q

?Q

\?P(3)假言推理規(guī)則P?QP

\Q(1)加法規(guī)則

P

\PúQ(2)簡化規(guī)則PùQ

\P(5)析取三段論規(guī)則

PúQ

?Q

\P12共三十九頁推理(tuīlǐ)規(guī)則(9)破壞性二難推理規(guī)則

P?Q

R?S

?Qú?S

\?Pú?R(8)構造性二難推理規(guī)則

P?Q

R?S

PúR

\QúS(7)合取引入規(guī)則

P

Q

\PùQ

(6)前提三段論規(guī)則

P?Q

Q?R

\P?R13共三十九頁例1：考慮下述論證:1.如果這里有球賽,則通行是困難的。2.如果他們按時到達,則通行是不困難的。3.他們按時到達了。4.所以這里沒有球賽。前3個斷言是前提,最后(zuìhòu)1個斷言是結論,要求我們從前提推出結論。設P:這里有球賽,Q:通行是困難(kùnnɑn)的,R:他們按時到達。

即證P→Q，R→?Q，R

?P運用推理規(guī)則形式化證明14共三十九頁證：步驟(bùzhòu)斷言(真)根據(jù)（1）RP（2）R→?QP（3）?QT,(1),(2),I3（4）P→QP（5）?PT,(3),(4),I4即證P→Q，R→?Q，R

?P15共三十九頁1.5.2證明方法

定理常見的形式是“P當且僅當Q”，“如果P，那么Q”。而前者又相當于P→Q并且Q→P，所以歸根結底，定理的主要形式是P→Q。至于其它形式，諸如：P形式，只需證明P是假;P∧Q形式，只需證明P、Q俱真;P∨Q形式，可轉化為P→Q形式。

我們主要從策略意義上說明如何證明P→Q形式的命題，具體的技巧，仍需通過(tōngguò)例題來學習。16共三十九頁1).無義證明法證明P

Q為真，只需證明P為假。2).平凡證明法證明P

Q為真，只需證明Q為真。

無義證明法和平凡證明法應用的次數(shù)較少,但對有限的或特殊(tèshū)的情況,它們常常是重要的。3.證明(zhèngmíng)方法（P→Q）17共三十九頁3.證明(zhèngmíng)方法3).直接證明法

假設P是真，如果(rúguǒ)能推得Q是真，則P→Q是真

H1∧H2∧…∧Hn

C，由前提利用推理規(guī)則直接推出C。例2：證明CD,C→R,D→S

R

S18共三十九頁

證：

(1)CDP(2)?(

?

C)DT,(1),E1(3)?C→DT,(2),E14(4)D→SP

(5)?C→ST,(3),(4),I6(6)C→RP(7)?R→?CT,(6),E24(8)?R→ST,(5),(7),I6(9)?(

?R)ST,(8),E14(10)R

ST,(9),E1

例2：證明(zhèngmíng)CD,C→R,D→S

R

S19共三十九頁實例(shílì)例構造推理的證明:若明天是星期一或星期三,我就有課.若有課,今天必須備課.我今天下午沒備課.所以(suǒyǐ),明天不是星期一和星期三.解設P:明天是星期一,Q:明天是星期三，

R:我有課，S:我備課前提:(PúQ)?R,R?S,?S結論:?Pù?Q

20共三十九頁實例(shílì)(續(xù))前提(qiántí):(PúQ)?R,R?S,?S結論:?Pù?Q

證明①R?S前提引入②?S前提引入③?R①②拒取式④(PúQ)?R前提引入⑤?(PúQ)③④拒取式⑥?Pù?Q⑤置換結論有效,即明天不是星期一和星期三21共三十九頁4).間接證明法-（對原命題的逆否命題進行(jìnxíng)證明）證P

Q只需證?Q

?P因為P

Q也即P→Q永真，?Q→?P永真所以?Q

?P3.證明(zhèngmíng)方法22共三十九頁

(2)一個完全數(shù)是一個整數(shù)，它等于它的所有因子(除本身外)的和。如6是一個完全數(shù)，因為6=1+2+3，同樣28也是。

定理:一個完全數(shù)不是一個質數(shù)。

證其逆反如下:一個質數(shù)不是一個完全數(shù)。假設P是一質數(shù)，那么P≥2并且P恰有兩個因子1和P，所以小于P的所有因子的總和(zǒnghé)是1。這得出P不是一個完全數(shù)。

這是間接證明法。23共三十九頁5).(H1∧H2∧…∧Hn)

Q形式命題的證明

H1∧H2∧…∧Hn

QiffH1∧H2∧…∧Hn

→Q是重言式iff?(H1∧H2∧…∧Hn

)Q是重言式iff?

H1

?H2

…

?Hn

Q是重言式iff(Q

?

H1)(Q

?H2)

…(Q

?Hn)是重言式iff(?Q→?

H1)(?Q→

?H2)

…(?

Q

→

?Hn)是重言式若至少有一個(yīɡè)i，使得使?Q

?Hi,則原恒等式成立。24共三十九頁6.CP規(guī)則（演繹定理(dìnglǐ)）P1∧P2∧…∧Pn

→(P→Q)形式命題的證明證：P1∧P2∧…∧Pn

P→Q因為P1∧P2∧…∧Pn

P→QiffP1∧P2∧…∧Pn

→(

P→Q)永真iff?(P1∧P2∧…∧Pn

)

(?

P

Q)永真iff?P1

?P2

…

?Pn

?

P

Q永真iff(?P1

?P2

…

?Pn

?

P)

Q永真iff?(P1∧P2∧…∧Pn

∧

P)

Q永真

iffP1∧P2∧…∧Pn

∧

P→Q永真

6.證明(zhèngmíng)方法25共三十九頁CP規(guī)則(guīzé)（演繹定理）前提(qiántí):P1,P2,…,Pn

結論:P?Q欲證明等價地證明前提:P1,P2,…,Pn,P(附加前提)結論:Q26共三十九頁例1.5-7如果A參加球賽(qiúsài)，則B或C也將參加球賽。如果B參加球賽，則A不參加球賽。如果D參加球賽，則C不參加球賽。所以，A若參加球賽，則D不參加球賽。

解設A:A參加球賽，B:B參加球賽，C:C參加球賽，D:D參加球賽。要證明的是A→D可從A→B∨C，B→A，D→C推出。27共三十九頁28共三十九頁利用CP規(guī)則證明以下例題(lìtí)練習：證A→(B→C)，?D

A，B

D→C證：(1)DP（附加前提）(2)?D

AP(3)AT,(1),(2),I5(4)A→(B→C)P(5)B→CT,(3),(4),I3(6)BP(7)CT,(5),(6),I3(8)D→CCP規(guī)則

29共三十九頁7.分情況證明(zhèngmíng)

證明P1

P2…Pn

Q，只需證明對每一i，Pi

→Q成立。3.證明(zhèngmíng)方法因為P1

P2…Pn

QiffP1

P2…Pn→Q永真iff?(P1

P2…Pn)Q永真iff(?P1

?P2…?Pn)Q永真iff(?P1

Q)(?P2

Q)…(?Pn

Q)永真iff(P1→Q)(P2→Q)(Pn→Q)永真30共三十九頁

例1.5-8試證記作“└┘”的二元運算“max”是可結合(jiéhé)的，即對任何整數(shù)a、b和c，(a└┘b)└┘c=a└┘(b└┘c)。

證對任意3整數(shù)a、b、c，下列6種情況之一必須成立:

a≥b≥c，a≥c≥b，b≥a≥c，b≥c≥a，c≥a≥b或c≥b≥a。

情況1:a≥b≥c，那么

(a└┘b)└┘c=a└┘c=a

a└┘(b└┘c)=a└┘b=a

所以 (a└┘b)└┘c=a└┘(b└┘c)

其它情況類似可證。31共三十九頁8.反證法（又稱歸謬法、矛盾法）

定義：設公式H1,H2,…,Hm中的原子命題變元是P1,P2,…,Pn,如果給P1,P2,…,Pn以某一指派,能使H1∧H2…∧Hm的真值為真,則稱命題公式集合{H1,H2,…,Hm}是一致的,否則稱為(chēnɡwéi)非一致的。

這個定義也可這樣敘述:若H1∧H2∧…∧Hm

R∧?R,則{H1,H2,…,Hm}是非一致的,否則是一致的。3.證明(zhèngmíng)方法32共三十九頁證明：H1∧H2∧…∧Hn

∧

?C

R∧?RiffH1∧H2∧…∧Hn

∧

?C永假(1)而{H1,H2,…,Hn}是一致的，所以存在一種指派使得H1∧H2∧…∧Hn

為真(2)由(1),(2)知存在一種指派使得?C為假，即C為真。由肯定(kěndìng)前件法可得H1∧H2∧…∧Hn

C。定理(dìnglǐ)：設{H1,H2,…,Hn}是一致的,C是一命題公式,如果{H1,H2,…,Hn,?C}非一致,則能從H1,

H2,…,Hn推出C，即H1∧H2∧…∧Hn

C。33共三十九頁歸謬法(反證法)欲證明前提：A1,A2,…,An結論：B將?B加入前提,若推出矛盾,則得證推理(tuīlǐ)正確.34共三十九頁例4:P

Q→R,?R

S,?S

?P

?Q證：(1)?(?P

?Q)P,假設(jiǎshè)前提(2)??P

?

?QT,(1),E10(3)P

QT,(1),E1(4)P

Q→RP(5)RT,(3),(4),I3(6)?R

SP(7)S