命題演算(推理理論)

《命題演算(推理理論)》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。

1、1第四講命題邏輯的推理理論命題邏輯的推理理論也稱為命題演算主要內容一、推理的形式結構二、推理定律和推理規(guī)則三、邏輯證明方法2數理邏輯的推理理論主要研究推理的“思維過程”，為推理提供一定的推理規(guī)則。它只關心從前提得到結論這種推理的正確有效性。無論前提是否真得正確，它總是假設其是成立的。所以推理的正確性和結論的正確性可能是不一致的。推理理論在應用上常常是將一些定理，定律，公理和條件作為前提，通過推理得到新的定理。引言3一、推理的形式結構定義1設A1,A2,…,Ak,B為命題公式.若對于每組賦值，A1?A2?…?Ak為假，或當A1?A2?…?Ak為真時，B也為真，則

2、稱由前提A1,A2,…,Ak推出結論B的推理是有效的或正確的,并稱B是有效結論或稱B可由A1,A2,…,Ak邏輯推出.定理1由命題公式A1,A2,…,Ak推B的推理正確當且僅當A1?A2?…?Ak?B為重言式4推理的形式結構2.A1?A2?…?Ak?B若推理正確,記為A1?A2?…?Ak?B3.前提：A1,A2,…,Ak結論：B推理的形式結構1.{A1,A2,…,Ak}B若推理正確,記為{A1,A2,?,An}B5二、推理定律——重言蘊涵式1.A?(A?B)附加律2.(A?B)?A化簡律3.(A?B)?A?B假言推理4.(A?B)??B??A拒取式5.(A?B

3、)??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?A6推理規(guī)則(1)前提引入規(guī)則(P)在推理過程中，可以隨時引入已知的前提。(2)結論引入規(guī)則(T)在推理過程中，前面已推出的有效結論都可作為后續(xù)推理的前提引用。(3)置換規(guī)則(R)在推理過程中，命題公

4、式中的子公式都可以用與之等值的命題公式置換，得到證明的公式序列的另一公式。(4)代入規(guī)則(S)在推理過程中，重言式中的任一命題變元都可以用一命題公式代入，得到的仍是重言式。7推理規(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∴A8推理規(guī)則(10)構造性二難推理規(guī)則(12)合取引入規(guī)則A?BC?DA?C∴B?DA?BC?D?B??D∴?A??CAB∴A?B(11)破壞性二難推理規(guī)則9三、邏輯證明方法判斷有效結論的過程就是論證過

5、程。基本方法：（1）真值表法（2）直接證明法（3）間接證明法（反證法）具體：等值演算、主析取范式、構造證明法等10例：判斷下列推理是否正確。今天楊尚樹或去網吧或去教室。他沒去教室，所以他去網吧了。設p：楊尚樹去網吧。q：楊尚樹去教室。則，前提：p∨q,?q結論：p推理的形式結構：((p∨q)∧?q)?p真值表法11pqp∨q?q(p∨q)∧?q((p∨q)∧?q)?p000101011001101111111001真值表法該命題公式為重言式，說明推理正確，所以楊尚樹去網吧((p∨q)∧?q)?p12推理實例例1判斷下面推理是否正確(1)若今天是1號，則明天是5

6、號.今天是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由定理1可知推理正確13推理實例(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是成假賦值，所以推理不正確14例2構造下面推理的證明：若

7、明天是星期一或星期三，我明天就有課.若我明天有課，今天必備課.我今天沒備課.所以，明天不是星期一、也不是星期三.解(1)設命題并符號化設p：明天是星期一，q：明天是星期三，r：我明天有課，s：我今天備課(2)寫出證明的形式結構前提：(p?q)?r,r?s,?s結論：?p??q15直接證明法(2)寫出證明的形式結構前提：(p?q)?r,r?s,?s結論：?p??q(3)證明（證明過程三列式）序號當前得到的結論當前得到結論的理由①r?sP(前提引入)②?sP③?rT①②I(拒取式)④(p?q)?rP⑤?(p?q)T③④E(拒取式)⑥?p??qT⑤E德摩根率16附加

8、前提證明法附加前提證明法適用于結論為蘊