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

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

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

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

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

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

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

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

PúQ

?P

\Ｑ7共三十九頁(yè)推理(tuīlǐ)的形式結(jié)構(gòu)形式(1)

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

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

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

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

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

?Q

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

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

P

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

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

PúQ

?Q

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

P?Q

R?S

?Qú?S

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

P?Q

R?S

PúR

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

P

Q

\PùQ

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

P?Q

Q?R

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

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

?P運(yùn)用推理規(guī)則形式化證明14共三十九頁(yè)證：步驟(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共三十九頁(yè)1.5.2證明方法

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

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

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

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

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

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

H1∧H2∧…∧Hn

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

R

S18共三十九頁(yè)

證：

(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共三十九頁(yè)實(shí)例(shílì)例構(gòu)造推理的證明:若明天是星期一或星期三,我就有課.若有課,今天必須備課.我今天下午沒(méi)備課.所以(suǒyǐ),明天不是星期一和星期三.解設(shè)P:明天是星期一,Q:明天是星期三，

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

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

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

Q只需證?Q

?P因?yàn)镻

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

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

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

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

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

這是間接證明法。23共三十九頁(yè)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)是重言式若至少有一個(gè)(yīɡè)i，使得使?Q

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

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

P→Q因?yàn)镻1∧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共三十九頁(yè)CP規(guī)則(guīzé)（演繹定理）前提(qiántí):P1,P2,…,Pn

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

解設(shè)A:A參加球賽，B:B參加球賽，C:C參加球賽，D:D參加球賽。要證明的是A→D可從A→B∨C，B→A，D→C推出。27共三十九頁(yè)28共三十九頁(yè)利用CP規(guī)則證明以下例題(lìtí)練習(xí)：證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共三十九頁(yè)7.分情況證明(zhèngmíng)

證明P1

P2…Pn

Q，只需證明對(duì)每一i，Pi

→Q成立。3.證明(zhèngmíng)方法因?yàn)镻1

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共三十九頁(yè)

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

證對(duì)任意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)

其它情況類(lèi)似可證。31共三十九頁(yè)8.反證法（又稱(chēng)歸謬法、矛盾法）

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

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

R∧?R,則{H1,H2,…,Hm}是非一致的,否則是一致的。3.證明(zhèngmíng)方法32共三十九頁(yè)證明：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ǐ)：設(shè){H1,H2,…,Hn}是一致的,C是一命題公式,如果{H1,H2,…,Hn,?C}非一致,則能從H1,

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

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

Q→R,?R

S,?S

?P

?Q證：(1)?(?P

?Q)P,假設(shè)(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