第二章命題推理(離散數(shù)學)

1/66上堂課的內(nèi)容、重點與難點合(析)取式與成真(假)解釋求解范式、主范式等價公式的熟練運用等價變換法、解釋法、真值表法的靈活運用聯(lián)結(jié)詞的完備集合合取式、析取式合取范式、析取范式極小項、極大項主合取范式、主析取范式2/66邏輯推理

演繹推理（數(shù)學家使用）歸納推理（科學家使用）溯因推理（偵探使用）從真的前提出發(fā)，得到的結(jié)論只能夠要求它與前提是協(xié)調(diào)的，但不一定是真的。從前提出發(fā)，通過推導即“演繹”，得出結(jié)論的過程。前提和結(jié)論之間有可推導性關(guān)系：前提的真蘊涵結(jié)論的真。生成假設(shè)來解釋觀察或結(jié)論。3/66例判斷下面兩個推理是否正確:(1)

如果今天是星期二,今天有數(shù)學課。

今天是星期二，

所以今天有數(shù)學課。

(2)如果今天是星期二,今天有數(shù)學課。今天不是星期二，

所以今天沒有數(shù)學課。第二章命題演算的推理理論4/66推理是否正確？記：P表示今天是星期二，

Q表示今天有數(shù)學課。(1)

如果今天是星期二,今天有數(shù)學課。今天是星期二，所以今天有數(shù)學課。((PQ)P)Q(2)如果今天是星期二,今天有數(shù)學課。今天不是星期二，所以今天沒有數(shù)學課。

((PQ)P)Q5/66從真值表看推理是否正確：PQ((PQ)P)Q

((PQ)P)QTT

TTTF

TTFT

TFFF

TT永真公式三段論非永真6/66有效推理若有重言式則稱由前提A1，…，

An

推出結(jié)論B的

推理有效，并稱B是A1，A2，

…，

An

的邏輯結(jié)論，記為：A1，A2，

…，

An┣B或

A1，A2，

…，

An

B重言式——推理規(guī)則(A1A2…An)B7/66三段論

PQ大前提

P小前提

Q結(jié)論三段論推理的有效性由永真公式：((PQ)P)Q所保證。已知的一般原理對特殊情況作出判斷所研究的特殊情況

8/66前提和結(jié)論間具有可推導性的形式關(guān)系大前提：如果1+1=3，則雪是黑的。小前提：1+1=3。結(jié)論：雪是黑的。該推理過程正確,但不意味著前提與結(jié)論正確9/669/70莫紹揆教授（1917.8-2011.4）1939年畢業(yè)于中央大學教學系1948年，瑞士蘇黎世高級工業(yè)大學留學，師從希爾伯特的繼承人貝爾奈斯1950年4月回國，任職南京大學，創(chuàng)建數(shù)理邏輯專業(yè)數(shù)理邏輯教育和研究的開拓者之一。編著有：《數(shù)理邏輯導論》《遞歸數(shù)論》《遞歸論》《算法論》10/6610/70公理化演繹推理歸結(jié)推理離散數(shù)學北京大學耿素云前提引入規(guī)則結(jié)論引入規(guī)則置換規(guī)則8條推理定律離散數(shù)學及其應(yīng)用北京大學屈婉玲前提引入規(guī)則結(jié)論引入規(guī)則置換規(guī)則

9條推理定律,24個等值式離散數(shù)學解放軍通信工程學院方世昌9條推理規(guī)則離散數(shù)學朱懷宏，南京大學出版社前提引入規(guī)則（P規(guī)則）結(jié)論引入規(guī)則（T規(guī)則）置換規(guī)則,11個重言式,22個等價公式關(guān)于推理理論的學習11/6611/70公理化演繹推理歸結(jié)推理離散數(shù)學導論南京大學徐潔磐?應(yīng)用公理系統(tǒng)?自動定理證明?離散數(shù)學基礎(chǔ)教程南京大學徐潔磐等式推理蘊涵推理離散數(shù)學及其在計算機中的應(yīng)用南京大學徐潔磐?推理定理?離散數(shù)學導論解放軍理工大學王元元3條公理模式分離規(guī)則自然推理系統(tǒng)?消解原理?離散數(shù)學南京理工大學朱保平15條公理代入規(guī)則,分離規(guī)則??關(guān)于推理理論的學習12/662.1命題演算的公理系統(tǒng)給出若干條永真公式(稱為公理)，再給出若干條由永真公式推出永真公式的推理規(guī)則，由它們出發(fā)推出一切永真公式。要求：了解公理系統(tǒng)的構(gòu)成規(guī)則和推理形式。13/66

公理系統(tǒng)的組成部分一、語法部分

㈠基本符號

公理系統(tǒng)所允許出現(xiàn)的全體符號的集合

㈡

公理

㈢

規(guī)則

二、語義部分14/66㈠基本符號

命題變元P，Q，R，……

聯(lián)結(jié)詞,,,,

括號(，)

合式公式

推出符┣

15/66㈡公理公理1PP公理2(P(QR))(Q(PR))公理3(PQ)((QR)(PR))公理4(P(PQ))(PQ)公理5(PQ)(PQ)公理6(PQ)(QP)公理7(PQ)((QP)(PQ))調(diào)頭傳遞凝縮與有關(guān)16/66㈡公理公理8(PQ)P公理9(PQ)Q公理10P(Q(PQ))公理11P(PQ)公理12Q(PQ)公理13(PR)((QR)((PQ)R))公理14(PQ)(QP)公理15PP與∧有關(guān)與∨有關(guān)與有關(guān)17/66㈢規(guī)則(1)代入規(guī)則：將公式中出現(xiàn)的某一符號B每處均代以某一公式C，所到的公式D稱為C對的代入。(2)分離規(guī)則：如果AB，且A，則B。MP規(guī)則18/66二、語義部分(1)公理是永真公式。規(guī)則規(guī)定如何從永真公式推出永真公式。分離規(guī)則指明:如果AB永真且A永真，則B也為永真公式。(3)代入規(guī)則指明如果為永真公式，則某一個公式正確代入公式后所得的公式也為永真公式。(4)定理為永真公式。19/66公理系統(tǒng)的推理過程定義如果能夠作出一系列合式公式序列

A1，A2,A3,…，An，它們滿足下列性質(zhì)：諸Ai或為公理/定理之一(可以使用代入規(guī)則)；或由前面的Ag、Ah利用分離規(guī)則而得；(3)An=B。稱序列A1，A2,…，An為B的永真證明過程。├B20/66公理推理證明的方法構(gòu)造合式公式序列

A1，A2,A3,…，An=B，把待證明的公式結(jié)論變成永真蘊涵式的后件，再證明前件永真，最后利用分離規(guī)則得到結(jié)論。├B21/66定理1(p20)

├

PP證明：(1)(PQ)(QP)公理14(2)(PP)(PP)P用P，Q用P代入(3)PP

公理1(4)PP

P用P代入(5)PP

(2)(4)分離P=P?22/66定理1的推論├

PP證明：(1)PP公理15(2)PP定理1(3)(PQ)((QP)(PQ))公理7

(4)(PP)((PP)(PP))

代入(3)

(5)(PP)(PP)(2)(4)分離(6)PP(1)(5)分離23/66定理2(p18)

├

(PQ)((RP)(RQ))

分析：由傳遞公理3知道(RP)((PQ)(RQ))與要求證的公式的聯(lián)系是兩個前件次序換一換，就可以用調(diào)頭公理2：(P(QR))(Q(PR))

加頭公式24/66定理3(p18,拒取式)

├(PQ)(QP)

分析：由公理14，(PQ)(QP)，可以得到(PQ)(QP)

如果(PQ)(PQ)，則由傳遞性知道結(jié)論成立。

25/66例：

├(PQ)(PQ)證明：

(PQ)((RP)(RQ))加頭定理2(2)(QQ)((PQ)(PQ))

P用Q代入，Q用Q代入，R用P代入(3)PP

定理1(4)QQ

P用Q代入(5)(PQ)(PQ)

(6)(2)分離26/66

定理4

├

P((PQ)Q)

證明：(1)(P(QR))(Q(PR))公理2(2)((PQ)(PQ))(P((PQ)Q))

Q用P代入，R用Q代入，P用PQ代入

(3)PP公理1(4)

(PQ)(PQ)代入(5)P((PQ)Q)分離(2)(4)27/66例1已知公理：A:(Q

R)((PQ)(PR))B:(PP)PC:Q(PQ)及分離規(guī)則和代入規(guī)則試證明PP

為定理28/66例1的證明(1)(Q

R)((PQ)(PR))公理A(2)(P∨P)P公理B(3)Q(PQ)公理C(4)(QP)((PQ)(PP))R用P代入(5)((P∨P)P)((P(P∨P))(PP))

(4)式中Q用P∨P(6)(P(P∨P))(PP)(2)(5)分離(7)P(P∨P)(3)式中Q用P代入(8)PP(6)(7)分離29/66例2已知公理A:(P(QR))((PQ)(PR))B:P(QP)C:(PQ)(QP)及分離規(guī)則和代入規(guī)則，試證明PP

為定理。30/66(1)(P(QR))((PQ)(PR))(2)P(QP)(3)(PQ)(QP)(4)(P(QP))((PQ)(PP))代入(1)(5)(PQ)(PP)(2)(4)分離(6)(P(QP))(PP)代入(5)(7)PP(2)(5)分離(8)PP代入(8)(9)(PP)(PP)代入(3)(10)

PP

(8)(9)分離例2的證明:31/662.2若干重要的導出規(guī)則2.2.1關(guān)于分離規(guī)則的討論從分離規(guī)則出發(fā)，由永真公式(a)，導出分(a)規(guī)則。永真公式(a)分(a)分分(a)分分分(a)├()├,├

(())├

(),├

,,├32/66

2.2.2關(guān)于公理和定理的導出規(guī)則每一個永真公式(公理與定理)都可以導出一條推理規(guī)則。公理2P(QR)├

Q(PR)調(diào)頭規(guī)則公理3PQ，QR├

PR傳遞規(guī)則公理7PQ，QP├PQ充要規(guī)則公理8PQ├P化簡規(guī)則公理10P，Q├PQ合取規(guī)則33/66重要的導出規(guī)則公理13PR，QR├(PQ)R析取規(guī)則定理2PQ

├

(RP)(RQ)加頭規(guī)則公理14PQ├QP逆否規(guī)則拒取規(guī)則PQ，Q├

P定理3PQ├

QPPQ，Q├P34/66假言三段論（傳遞三段論）

P

Q

前提

Q

R

前提

PR

結(jié)論推理的有效性由公理3所保證。35/66化簡

P∧Q

前提

P

結(jié)論推理的有效性由公理8所保證。36/66合取

P

前提

Q前提

P∧Q

結(jié)論推理的有效性由公理10所保證。37/66拒取

P

Q

大前提

Q

小前提

P

結(jié)論推理的有效性由定理3所保證。38/66定理3├(PQ)(QP)

運用導出規(guī)則的新證明：

(PQ)(QP)公理14(2)(PQ)(QP)Q用Q代入(3)P

P定理1(4)Q

Q代入(3)(5)

(PQ)(PQ)

(4)加頭(6)

(PQ)(QP)

(5)(2)傳遞39/66替換定理40/66定理3├(PQ)(QP)

運用替換規(guī)則的新證明：(PQ)(QP)公理14(2)(PQ)(QP)

Q用Q代入(3)P

P定理1的推論(4)Q

Q代入(3)(5)(PQ)(QP)

(4)替換(2)41/66例(p22)├(PQ)(QP)利用替換規(guī)則的新證明：(1)(PQ)(QP)公理14

(2)(PQ)(QP)代入(1)(3)P

P

定理1的推論(4)QQ

代入(3)(5)(PQ)(QP)(3)替換(2)(6)(PQ)(QP)(4)替換(5)42/662.3

假設(shè)推理系統(tǒng)

——自然推理系統(tǒng)一、擴充的推理規(guī)則二、假設(shè)推理過程三、推理定理四、假設(shè)推理證明定理的方法2.3.1假設(shè)推理系統(tǒng)的組成43/66一、擴充的推理規(guī)則記R：A1，A2，…，An

├B稱B是由A1，A2，…，An實施規(guī)則R而得。設(shè)有重言式：(A1

A2

…

An)B

A1

前提

A2

前提……

An

前提

B

結(jié)論規(guī)則R：在假設(shè)推理系統(tǒng)中的重言式既可以是公理系統(tǒng)中的公理及定理，也可以是利用真值表法驗證的等值公式。44/66肯定前提律（化簡）

P∧Q

前提

P

結(jié)論推理的有效性由公理(8)所保證。一般地，

A1，A2，…，An├Ai

(i=1，2，…，n)即前提中的任何命題均可作為結(jié)論。45/66置換(替換)任何命題公式都可以用與之等值的命題公式置換。如果A=B，則A┣B例P┣

PP┣PPQ┣

P∨QP∨Q┣

PQ

在公理系統(tǒng)中，導出規(guī)則(包括：替換)在初學時一般不允許使用。46/66析取三段論

P∨Q

大前提

P

小前提

Q

結(jié)論推理的有效性由永真公式：((P∨Q)P)Q所保證。47/66拒取

P

Q

大前提

Q

小前提

P

結(jié)論推理的有效性由定理3所保證。48/66二、假設(shè)推理過程定義:

如果能夠作出一系列合式公式序列A1，A2,A3,…，An，它們滿足下列性質(zhì)：(1)諸Ai或為公理/定理之一(可以使用代入規(guī)則)；(2)或為公式1,

2,

…,k之一(對假設(shè)i不能代入)；(3)或由前面的Ag、Ah利用分離規(guī)則而得；(4)An=B。稱這個公式序列A1，A2,…，An為由公式1，2，…，k證明B的證明過程。1，2，…，k├B49/66三、推理定理附加前提推理定理(CP規(guī)則)

如果Γ，A├B，則Γ├AB

Γ

(AB)與(?！腁)

B同真假50/66附加前提推理定理如果A1，A2，…，An-1

，An，A├B，則

A1，A2，…，An-1

，An├AB進而，有下面定理：

A1，A2…，An-1├An

(AB)A1，A2，…，An-2├An-1

(An

(AB))依次類推可得定理：

├A1(A2(…(An(AB))…))51/66四、反證律如果Γ，A├B

且Γ，A├B這里B是一個公式。則有:

Γ├A。52/66五、假設(shè)推理證明定理的方法

把待證公式的前件一一列出，注明為假設(shè)或前提。按推理規(guī)則進行推理，但此時不能對假設(shè)以及演繹公式實施代入規(guī)則。(3)當推導出待證公式的后件時，就完成了該定理的證明。附加前提推理證明方法53/66反證法(1)把待證公式的前件一一列出，把待證公式的后件的否定列出，注明為假設(shè)或前提。(2)按推理規(guī)則進行推理，但此時不能對假設(shè)以及演繹公式實施代入規(guī)則。(3)當推導出兩個矛盾的結(jié)論時，就完成了該定理的證明。54/66例1：求證├

(P(QR))((PQ)R)證明(1)P(QR)假設(shè)

(2)PQ假設(shè)

(3)(PQ)P公理8(4)(PQ)Q公理9(5)P(3)(2)分離

(6)Q(4)(2)分離

(7)QR(1)(5)分離

(8)R(6)(7)分離55/66例1：求證├

(P(QR))((PQ)R)證明:(1)P(QR)假設(shè)

(2)PQ假設(shè)

(3)P(2)化簡

(4)Q(2)化簡

(5)QR(1)(3)分離

(6)R(4)(5)分離(4)R

在(3)中用R代入P有錯嗎?不能對(3)實施代入規(guī)則!!!56/66例3(p25)求證：├

(PP)P證明：(1)

PP

假設(shè)

(2)

P

假設(shè)，結(jié)論的否定

(3)

P

(1)(2)分離顯然，(2)與(3)矛盾。

由反證法，

結(jié)論得證。57/66定理(PR)((QR)(PQ))證明:(1)PR假設(shè)(2)QR假設(shè)(3)P假設(shè)(4)R(1)(3)分離(5)

Q(2)(4)拒取規(guī)則

即證得:PR,QR,P├Q由推理定理,原公式得證58/66例├((SQ)(PQ)S)P證明:（直接證明，不采用反證律）

(1)

(SQ)(PQ)S

假設(shè)

(2)S→Q

(1)化簡

(3)P→Q(1)化簡

(4)S(1)化簡

(5)

Q(2)(4)分離

(6)

P

(3)(5)拒取

59/66例├((SQ)(PQ)S)P解:(1)

(SQ)(PQ)S假設(shè)(2)S→Q

(1)化簡

(3)P→Q(1)化簡

(4)S(1)化簡

(5)

P

假設(shè),結(jié)論的否定(置換)

(6)

Q(2)(4)分離

(7)Q(3)(5)分離顯然，(6)與(7)矛盾。由反證法，公式得證。60/66例構(gòu)造下面的假設(shè)推理證明前提：p∨q,r∨q,r→s結(jié)論：p→s證明：p∨q

假設(shè)

r∨q

假設(shè)(3)r→s

假設(shè)p附加假設(shè)q(1)(4)析取三段論r(2)(5)析取三段論s(3)(6)分離61/66半反證法、窮舉法若A1，A2，…，An,β├B,A1，A2，…，An,├B,則A1，A2，…，An,β∨├B若A1，A2，…，An,β├

,則A1，A2，…，An

├

β∨62/66例

寫出對應(yīng)下面的假設(shè)推理證明解：記p：今天是星期天

q：去中山陵r：去玄武湖

s：中山陵游玩的人多

前提：p→(q∨r),s→q,p,s

結(jié)論：r如果今天是星期天,則小組就到中山陵或玄武湖去游玩。如果中山陵游玩的人多，小組就不去中山陵游玩。今天是星期天，中山陵游玩的人多，所以小組去玄武湖。

例4的證明：p→(q∨r)

假設(shè)s→q假設(shè)p假設(shè)s假設(shè)(5)

q∨r

(1)(3)分離q(2)(4)分離r(5)(6)析取三段論(7’)q→r等值(5)(8’)r

6)(7’)分離例

構(gòu)造下面推理的證明：

若明天是星期一或星期三，我就有課.若有課，今天必備課.我今天下午沒備課.所以，明天不是星期一和星期三.解

設(shè)p：明天是星期一，q：明天是星期三，

r：我有課，s：我備課形式結(jié)構(gòu)為前提：(púq)?r,r?s,?s

結(jié)論：?pù?q

64直接證明法(續(xù))證明①r?s

前提引入②?s

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

前提引入⑤?(púq)③④拒取式

⑥?pù?q⑤置換65前提：(púq)?r,r?s,?s結(jié)論：?pù?q

66例

找出下列推理的有效結(jié)論。如果我考試通過了，那么我很快樂。如果我快樂，那么陽光燦爛。現(xiàn)在陽光不燦爛且天很暖。因此我考試沒通過。解設(shè)p：我考試通過了，q：我很快樂，r：陽光燦爛，s：天很暖。前提：p→q，q→r，?rù

s

結(jié)論：p67前提：p→q，q→r，?rù

s結(jié)論：p（1）p→q前提引入（2）q→r前提引入（3）p→r（1）（2）假言三段論（4）

r∧s前提引入（5）

r（4）化簡（6）p（5）（3）拒取式所以有效結(jié)論是：我考試沒通過。68例3證明Ｒ∨Ｓ是前題Ｃ∨Ｄ，Ｃ→Ｒ，Ｄ→Ｓ的有效結(jié)論，即證明：

(C∨D)∧(C→R)∧(D→S)(R∨S)。

證明：①C∨D前提引入②C→D置換③D→S前提引入④C→S②③⑤C→R前提⑥R→C⑤⑦R→S④⑥

⑧R∨S置換69例構(gòu)造下面推理的證明:2是素數(shù)或合數(shù).若2是素數(shù)，則是無理數(shù).

若是無理數(shù)，則4不是素數(shù).

所以，如果4是素數(shù)，則2是合數(shù).

用附加前提證明法構(gòu)造證明解設(shè)p：2是素數(shù)，q：2是合數(shù)，

r：是無理數(shù)，s：4是素數(shù)形式結(jié)構(gòu)前提：púq,p?r,r??s

結(jié)論：s?q70證明①s

附加前提引入②p?r

前提引入③r??s

前提引入④p??s②③假言三段論⑤?p①④拒取式⑥púq

前提引入⑦q⑤⑥析取三段論前提：púq,p?r,r??s結(jié)論：s?q71例構(gòu)造下面推理的證明前提：?(pùq)úr,r?s,?s,p

結(jié)論：?q證明（用歸繆法）①q

結(jié)論否定引入⑩?pùp

⑧⑨合取②r?s

前提引入③?s

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

前提引入

⑥?(pùq)④⑤析取三段論

⑦?pú?q

⑥置換

⑧?p

①⑦析取三段論

⑨p

前提引入證：①A→B前提

②A

否定結(jié)論

③B①②

④

(B∨C)前提

⑤B∧C③置換

⑥B④

⑦B∧B（矛盾）

72練習1

證明

(B∨C)∧(A→B)A

6、課內(nèi)練習證：⑴(A→C)否定結(jié)論

⑵A∧C1置換⑶A2化簡⑷C2化簡⑸A∨B前提⑹B3、5⑺C→B前提⑻B4、7

⑼B∧B(矛盾)6、873練習2證明

A∨B，C→BA→C

74練習2證明

A∨B，C→BA→C

證:(1)

A附加前提引入(2)

A∨B前提(3)B1、2(4)C→B前提(5)C3、4

75/66已知公理

A:(PQ)P

B:(PQ)Q

C:P(Q(PQ))

及分離規(guī)則和代入規(guī)則，試用假設(shè)推理證明下面公式為本系統(tǒng)的定理:

(PR)(((QS)(PQ))(SR))

例(10級期末試題,6分)證：（1）PR

假設(shè)

（2）(QS)(PQ)假設(shè)

（3）((QS)(PQ))(QS)

公理（A）代入

（4）((QS)(PQ))(PQ)公理（B）代入