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

離散數(shù)學(xué)推理理論第一頁，共十八頁，編輯于2023年，星期日一、有效論證與推理規(guī)則定義：A1∧A2∧…∧An→A,其為永真式，則稱由前提A1,A2,…,An得到有效結(jié)論A；從前提公式得到有效結(jié)論的過程稱為正確推理。若AB是永真式，則記為AB；若A→B是永真式，則記為AB。前提一致和不一致：如果前提A1∧A2∧…∧An為可滿足式，則稱為前提A1,A2,…,An一致。第二頁，共十八頁，編輯于2023年，星期日實例分析

判斷推理是否正確：張紅不管有無空閑都不看電影。張紅看了電影。所以張紅有空閑時間又沒有空閑時間。解：P:張紅有空閑時間；Q：張紅看電影。

前提：A1=P∨P→QA2=Q

結(jié)論：A=P∧P

問題：該結(jié)論是否有效結(jié)論。(該推理是否正確)。01010000110111111101110110111100(P∨P→Q)∧Q→P∧PQP所以，結(jié)論A是有效結(jié)論；該推理是正確的。而前提是不一致的。第三頁，共十八頁，編輯于2023年，星期日基本蘊涵式名稱蘊涵關(guān)系式化簡式

A∧BAA∧BB

(A→B)A

(A→B)B

附加式

AA∨BBA∨B

AA→BBA→B假言推理

(A→B)∧AB拒取式

(A→B)∧B

A析取三段式

(A∨B)∧AB假言三段式

(A→B)∧(B→C)A→C等價三段式

(AB)∧(BC)AC二難推論

(A→B)∧(C→D)∧(A∨C)B∨D第四頁，共十八頁，編輯于2023年，星期日(A→B)∧B

A的證明AB(A→B)∧B→

A0011111011001110001101110010第五頁，共十八頁，編輯于2023年，星期日法一、真值表法：011011110101011010111000(A→B)→BBA法二、利用等值演算法證明：證：(A→B)→B

(A∨B)→B

(A∨B)∨B(A∨B)∨BA∨(B∨B)A∨TT

所以,(A→B)B(A→B)B的證明?第三種方法?第六頁，共十八頁，編輯于2023年，星期日自然推理系統(tǒng)P形式系統(tǒng)自然推理系統(tǒng)公理系統(tǒng)特點：只能從幾個給定的公理出發(fā)，應(yīng)用系統(tǒng)中的推理規(guī)則進行推演，得到的結(jié)論是系統(tǒng)中的定理。特點：可以從任意給定的前提出發(fā)，應(yīng)用系統(tǒng)中的推理進行推演，得到的結(jié)論在系統(tǒng)中被認(rèn)為是有效的。第七頁，共十八頁，編輯于2023年，星期日自然推理系統(tǒng)P

自然推理系統(tǒng)P定義如下：1.字母表

(1)命題常元，命題變元：P,Q,R,…,Pi,Qi,…,1,0(T,F)

(2)命題聯(lián)結(jié)詞：、∧、∨、→、

(3)括號：(,)2.合式公式：(略)3.推理規(guī)則：

(1).前提引入規(guī)則(P規(guī)則)：在證明的任何步上，都可引入前提；

(2).結(jié)論引用規(guī)則(T規(guī)則)：在證明的任何步上，所得的結(jié)論都可作為證明得前提；

(3).置換規(guī)則：在證明的任何步上，命題公式的任何子命題公式都可以用與之等價的命題公式置換。

(4).永真蘊涵規(guī)則：使用基本蘊涵式，常常將條件用‘，’分開。第八頁，共十八頁，編輯于2023年，星期日基本蘊涵式證明的另一種方法(A→B)B的證明證明：(A→B)(A∨B)

A∧B

A∧B

B(簡化式）(A→B)B的證明第九頁，共十八頁，編輯于2023年，星期日推理過程的證明形式規(guī)范化的形式：序號公式理由①B1E或I或P或…的合取或cp②B2..③B3..……注意：1)并非B1B2B32)Bi的獲取：前提、中間結(jié)論第十頁，共十八頁，編輯于2023年，星期日構(gòu)造下列的推理的證明：前提：P∨Q,P→R,S→M,S→R,M

結(jié)論：Q。證：①

MP②S→MP③

S①②I拒取式④

S→RP⑤R③④I假言推理⑥P→RP⑦

P⑤⑥I拒取式⑧

P∨QP⑨

Q⑦

⑧

I析取三段式第十一頁，共十八頁，編輯于2023年，星期日一公安人員審查一件案件。一致的事實如下：(1).張三或李四盜竊了錄像機；(2).如果張三盜竊了錄像機，則作案時間不能在午夜前；(3).如果李四證詞正確，則午夜時屋內(nèi)燈光未滅；(4).如果李四證詞不正確，則作案時間在午夜前；(5).午夜時屋內(nèi)燈滅了。①

MP②S→MP③

S①②I拒取式④

S→RP⑤R③④I假言推理⑥P→RP⑦

P⑤⑥I拒取式⑧

P∨QP⑨

Q⑦

⑧

I析取三段式解：將已知事實符號化：設(shè)P:張三盜竊錄像機；

Q:李四盜竊錄像機;R:作案時間發(fā)生在午夜前；

S:李四證詞正確；

M:午夜時燈光未滅。則前提為:(1)P∨Q,(2)P→R,(3)S→M,(4)S→R,(5)M。結(jié)論未定。所以，可以得出是李四盜了錄像機。第十二頁，共十八頁，編輯于2023年，星期日例如前提：p((r∧s)q)，p，s結(jié)論：q。證明：⑴pp規(guī)則⑵p((r∧s)q)p規(guī)則⑶(r∧s)q⑴⑵I⑷s

p規(guī)則⑸s∨r⑷I⑹(r∧s)⑸E⑺q⑶⑹I第十三頁，共十八頁，編輯于2023年，星期日推理證明的方法前提的合取→結(jié)論是永真式間接證明法推理證明演繹證明歸納證明直接證明法附加前提證法(CP)歸謬法(反證法)第十四頁，共十八頁，編輯于2023年，星期日附加前提證法

(CP)針對這種情況：前提：A1，A2，…，An結(jié)論：A→B前提：A1，A2，…，An，A結(jié)論：

B第十五頁，共十八頁，編輯于2023年，星期日例：前提：P,P→(Q→R∧S)

結(jié)論：Q→S證明：(1)Pcp規(guī)則

(2)P→(Q→R∧S)cp規(guī)則

(3)Q→R∧S(1)(2)I(4)Qcp規(guī)則

(5)R∧S(3)(4)I(6)S(5)I課堂作業(yè)：前提：P∧Q→R，S∨P，Q

結(jié)論：S→R第十六頁，共十八頁，編輯于2023年，星期日歸謬法(反證法)針對這種情況：前提：A1，A2，…，An結(jié)論：

A前提：A1，A2，…，An，A結(jié)論：0（F）A(A)第十七頁，共十八頁，編輯于2023年，星期日例：前提：R→Q，R∨S

，S→Q，P→Q

結(jié)論：P證明：①(

P)否定結(jié)論引入（CP規(guī)則）②P①E③P→QP④Q

②③I⑤R