離散數(shù)學高教版第3章

1主要內容推理的形式結構推理的正確與錯誤推理的形式結構判斷推理正確的方法推理定律自然推理系統(tǒng)P形式系統(tǒng)的定義與分類自然推理系統(tǒng)P在P中構造證明:直接證明法、附加前提證明法、歸謬法第三章命題邏輯的推理理論23.1推理的形式結構定義3.1設A1,A2,…,Ak,B為命題公式.若對于每組賦值，A1

A2

…

Ak為假，或當A1

A2

…

Ak為真時，B也為真，則稱由前提A1,A2,…,Ak推出結論B的推理是有效的或正確的,并稱B是有效結論.定理3.1由命題公式A1,A2,…,Ak推B的推理正確當且僅當A1

A2

…

Ak

B為重言式注意:推理正確不能保證結論一定正確3推理的形式結構2.A1

A2

…

Ak

B若推理正確,記為A1

A2

…

Ak

B3.前提：A1,A2,…,Ak結論：B判斷推理是否正確的方法:真值表法等值演算法主析取范式法推理的形式結構1.{A1,A2,…,Ak}B若推理正確,記為{A1,A2,,An}B4推理實例例1判斷下面推理是否正確(1)若今天是1號，則明天是5號.今天是1號.所以,明天是5號.(2)若今天是1號，則明天是5號.明天是5號.所以,今天是1號.解設p：今天是1號，q：明天是5號.(1)推理的形式結構:(p

q)

p

q用等值演算法(p

q)

p

q

((

p

q)

p)

q

p

q

q

1由定理3.1可知推理正確5推理實例(2)推理的形式結構:(p

q)

q

p用主析取范式法(p

q)

q

p

(

p

q)

q

p

((

p

q)

q)

p

q

p

(

p

q)

(p

q)

(p

q)

(p

q)

m0

m2

m3

結果不含m1,故01是成假賦值，所以推理不正確6推理定律——重言蘊涵式1.A

(A

B)附加律2.(A

B)

A化簡律3.(A

B)

A

B假言推理4.(A

B)

B

A拒取式5.(A

B)

B

A析取三段論6.(A

B)

(B

C)

(A

C)假言三段論7.(A

B)

(B

C)

(A

C)等價三段論8.(A

B)

(C

D)

(A

C)

(B

D)構造性二難(A

B)

(

A

B)

B構造性二難(特殊形式)9.(A

B)

(C

D)

(

B

D)

(

A

C)破壞性二難每個等值式可產生兩個推理定律如,由A

A可產生A

A和A

A73.2自然推理系統(tǒng)P定義3.2一個形式系統(tǒng)I由下面四個部分組成：(1)非空的字母表，記作A(I).(2)A(I)中符號構造的合式公式集，記作E(I).(3)E(I)中一些特殊的公式組成的公理集，記作AX(I).(4)推理規(guī)則集，記作R(I).

記I=<A(I),E(I),AX(I),R(I)>,其中<A(I),E(I),AX(I),R(I)>是I的形式語言系統(tǒng),<A(I),E(I),AX(I),R(I)>是I的形式演算系統(tǒng).自然推理系統(tǒng):無公理,即AX(I)=

公理推理系統(tǒng)推出的結論是系統(tǒng)中的重言式,稱作定理8自然推理系統(tǒng)P定義3.3自然推理系統(tǒng)P定義如下:1.字母表(1)命題變項符號：p,q,r,…,pi,qi,ri,…(2)聯(lián)結詞符號：

,

,

,

,

(3)括號與逗號：(,),，2.合式公式（同定義1.6）3.推理規(guī)則

(1)前提引入規(guī)則(2)結論引入規(guī)則(3)置換規(guī)則9推理規(guī)則(4)假言推理規(guī)則

(6)化簡規(guī)則

(8)假言三段論規(guī)則

A

BA∴BA∴A

BA

B∴A(5)附加規(guī)則

(7)拒取式規(guī)則

(9)析取三段論規(guī)則

A

B

B∴AA

BB

C∴A

CA

B

B∴A10推理規(guī)則(10)構造性二難推理規(guī)則(11)破壞性二難推理規(guī)則

(12)合取引入規(guī)則

A

BC

DA

C∴B

DA

BC

D

B

D∴

A

CAB∴A

C11在自然推理系統(tǒng)P中構造證明設前提A1,A2,,Ak,結論B及公式序列C1,C2,,Cl.如果每一個Ci(1

i

l)是某個Aj,或者可由序列中前面的公式應用推理規(guī)則得到,并且Cl=B,則稱這個公式序列是由A1,A2,,Ak推出B的證明例2構造下面推理的證明：若明天是星期一或星期三，我明天就有課.若我明天有課，今天必備課.我今天沒備課.所以，明天不是星期一、也不是星期三.解(1)設命題并符號化設p：明天是星期一，q：明天是星期三，

r：我明天有課，s：我今天備課12直接證明法(2)寫出證明的形式結構前提：(p

q)

r,r

s,

s結論：

p

q證明

①r

s前提引入②

s前提引入③

r①②拒取式④(p

q)

r前提引入⑤

(p

q)③④拒取式⑥

p

q⑤置換13附加前提證明法附加前提證明法適用于結論為蘊涵式欲證前提：A1,A2,…,Ak結論：C

B等價地證明前提：A1,A2,…,Ak,C結論：B理由：

(A1

A2

…

Ak)

(C

B)

(A1

A2

…

Ak)

(

C

B)

(A1

A2

…

Ak

C)

B

(A1

A2

…

Ak

C)

B14附加前提證明法實例例3構造下面推理的證明2是素數(shù)或合數(shù).若2是素數(shù)，則是無理數(shù).若是無理數(shù)，則4不是素數(shù).所以，如果4是素數(shù)，則2是合數(shù).解用附加前提證明法構造證明(1)設p：2是素數(shù)，q：2是合數(shù)，

r：是無理數(shù)，s：4是素數(shù)(2)推理的形式結構前提：p

q,p

r,r

s結論：s

q

15附加前提證明法實例(3)證明①s附加前提引入②p

r前提引入③r

s前提引入④p

s②③假言三段論⑤

p①④拒取式⑥p

q前提引入⑦q⑤⑥析取三段論16歸謬法（反證法）歸謬法(反證法)欲證前提：A1,A2,…,Ak

結論：B做法在前提中加入

B，推出矛盾.理由

A1

A2

…

Ak

B

(A1

A2

…

Ak)

B

(A1

A2

…

Ak

B)

(A1

A2

…

Ak

B)0

A1

A2

…

Ak

B017歸謬法實例例4前提：

(p

q)

r,r

s,

s,p結論：

q證明用歸繆法①q結論否定引入②r

s前提引入③

s前提引入④

r②③拒取式⑤

(p

q)

r前提引入⑥

(p

q)④⑤析取三段論⑦

p

q⑥置換⑧

p①⑦析取三段論⑨p前提引入

p

p⑧⑨合取18第三章習題課主要內容推理的形式結構判斷推理是否正確的方法真值表法等值演算法主析取范式法推理定律自然推理系統(tǒng)P構造推理證明的方法直接證明法附加前提證明法歸謬法(反證法)19基本要求理解并記住推理形式結構的兩種形式：1.(A1

A2

…

Ak)

B2.前提：A1,A2,…,Ak

結論：B熟練掌握判斷推理是否正確的不同方法（如真值表法、等值演算法、主析取范式法等）牢記P系統(tǒng)中各條推理規(guī)則熟練掌握構造證明的直接證明法、附加前提證明法和歸謬法會解決實際中的簡單推理問題20練習1：判斷推理是否正確1.判斷下面推理是否正確:

(1)前提：

p

q,

q結論：

p解推理的形式結構:(

p

q)

q

p方法一：等值演算法(

p

q)

q

p

((p

q)

q)

p

(

p

q)

q

p

((

p

q)

(

q

q))

p

p

q易知10是成假賦值，不是重言式，所以推理不正確.21練習1解答方法二：主析取范式法，(

p

q)

q

p((p

q)q)p

p

q

M2

m0

m1

m3未含m2,不是重言式,推理不正確.22練習1解答方法三真值表法

不是重言式,推理不正確111001110100(

p

q)

q

pqp

p

q0111(p

q)

q0010方法四直接觀察出10是成假賦值23練習1解答用等值演算法(q

r)

(p

r)(q

p)(q

r)(p

r)(q

p)

((q

r)(p

r))(q

p)

((q

p)(q

r)(r

p))(q

p)((q

p)(q

r)(r

p))(q

p)1推理正確