離散數(shù)學(xué)第二章-命題演算的推理理論-命題演算的公理系統(tǒng).ppt

《離散數(shù)學(xué)第二章-命題演算的推理理論-命題演算的公理系統(tǒng).ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)第二章-命題演算的推理理論-命題演算的公理系統(tǒng).ppt（46頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

目錄（數(shù)理邏輯）,第一章命題演算基礎(chǔ)（6學(xué)時(shí)）第二章命題演算的推理理論（4學(xué)時(shí)）第三章謂詞演算基礎(chǔ)（5學(xué)時(shí)）第四章謂詞演算的推理理論（5學(xué)時(shí)）第五章遞歸函數(shù)論（4學(xué)時(shí)）,第二章命題演算的推理理論,例判斷下面各推理是否正確:(1)如果天氣涼快,小王就不去游泳。天氣涼快,所以小王沒去游泳。(2)如果天氣涼快,小王就不去游泳。天氣不涼快,所以小王去游泳了。,推理是否正確：形式化,引入符號(hào)：P表示天氣涼快，Q表示小王去游泳(1)如果天氣涼快,小王就不去游泳。天氣涼快,所以小王沒去游泳。((P??Q)?P)??Q(2)如果天氣涼快,小王就不去游泳。天氣不涼快,所以小王去游泳了。((P??Q)??P)?Q,推理是否正確?考察主析取范式,((P??Q)?P)??Q=?((P??Q)?P)??Q=?(P??Q)??P??Q=?(?P??Q)??P??Q=(P?Q)??P??Q=(P?Q)?(?P?(Q??Q))?(?Q?(P??P))=(P?Q)?(?P?Q)?(?P??Q)?(?Q?P)=m0∨m2∨m3∨m1永真公式,推理是否正確?考察主析取范式,((P??Q)??P)?Q=?((P??Q)??P)?Q=?(P??Q)?P?Q=?(?P??Q)?P?Q=(P?Q)?P?Q=(P?Q)?(P?(Q??Q))?(Q?(P??P))=(P?Q)?(P??Q)?(Q??P)=m0∨m1∨m2非永真公式,推理是否正確：真值表,PQ((P?Q)?P)?Q((P?Q)??P)??QTTTTTFTTFTTFFFTT,,,,((P?Q)?P)?Q為永真公式而((P?Q)??P)??Q不是永真的。,三段論,三段論,可用三段論表示((P?Q)?P)?Q如下：P?Q大前提P小前提Q結(jié)論,例如果今天下雨，則運(yùn)動(dòng)會(huì)將推遲舉行；今天下雨；運(yùn)動(dòng)會(huì)將推遲舉行。,,邏輯推理,由前提推出結(jié)論（前提與結(jié)論都是命題，可真可假）,演繹推理歸納推理,歸納推理,從真的前提出發(fā)，得到的結(jié)論只能夠要求它與前提是協(xié)調(diào)的，但不一定是真的。它基于對(duì)特殊的代表的有限觀察，或基于對(duì)反復(fù)再現(xiàn)的現(xiàn)象的模式的有限觀察，用公式表達(dá)規(guī)律。,所有觀察到的烏鴉都是黑的。所以所有烏鴉都是黑的。,演繹推理,可推導(dǎo)性——當(dāng)前提的真蘊(yùn)涵結(jié)論的真時(shí)，稱前提和結(jié)論之間有可推導(dǎo)性關(guān)系，即前提和結(jié)論之間的推理是正確的。,演繹推理——前提和結(jié)論之間有可推導(dǎo)性關(guān)系的這種推理。,前提和結(jié)論間的形式關(guān)系(而不考慮內(nèi)容),如果1+1=3，則雪是黑的。1+1=3。雪是黑的。,該推理過程正確,但不意味著前提與結(jié)論正確,第二章命題演算的推理理論,2.1命題演算的公理系統(tǒng)2.1.1公理系統(tǒng)的組成部分2.1.2公理系統(tǒng)的推理過程2.2命題演算的假設(shè)推理系統(tǒng)2.3命題演算的歸結(jié)推理法,,2．1命題演算的公理系統(tǒng),給出若干條永真公式(稱為公理)，再給出若干條由永真公式推出永真公式的推理規(guī)則，由它們出發(fā)推出一切永真公式的系統(tǒng)。,了解公理系統(tǒng)的構(gòu)成規(guī)則和推理形式，培養(yǎng)讀者構(gòu)造公理系統(tǒng)及利用該公理系統(tǒng)進(jìn)行推理的能力。,2．1．1公理系統(tǒng)的組成部分,一、語法部分㈠基本符號(hào)公理系統(tǒng)所允許出現(xiàn)的全體符號(hào)的集合㈡公理㈢規(guī)則二、語義部分,㈠基本符號(hào),命題變元P，Q，R，……等字母表示命題變元聯(lián)結(jié)詞?、?、?、?、?是聯(lián)結(jié)詞括號(hào)(，)是括號(hào)合式公式(1)任何命題變元均是公式；(2)如果P為公式，則?P為公式；(3)如果為P，Q為公式，則P?Q，P?Q，P?Q，P?Q為公式；(4)當(dāng)且僅當(dāng)經(jīng)過有限次使用(1),(2),(3)所組成的符號(hào)串才是公式。,推出符┣表示其后的公式為永真公式(教材中遺漏),㈡公理,公理1P?P公理2(P?(Q?R))?(Q?(P?R))公理3(P?Q)?((Q?R)?(P?R))公理4(P?(P?Q))?(P?Q)公理5(P?Q)?(P?Q)公理6(P?Q)?(Q?P)公理7(P?Q)?((Q?P)?(P?Q)),調(diào)頭,傳遞,凝縮,㈡公理,公理8(P?Q)?P公理9(P?Q)?Q公理10P?(Q?(P?Q))公理11P?(P?Q)公理12Q?(P?Q)公理13(P?R)?((Q?R)?((P?Q)?R))公理14(P??Q)?(Q??P)公理15??P?P,常用推理定律(詳見耿素云《離散數(shù)學(xué)》),P?(P∨Q)附加(P∧Q)?P化簡((P?Q)∧P)?Q假言推理((P?Q)∧?Q)??P拒取式((A∨B)∧?A)?B析取三段論((A?B)∧(B?C))?(A?C)假言三段論((A?B)∧(B?C))?(A?C)等價(jià)三段論(A?B)∧(C?D)∧(A∨C)?(B∨D)構(gòu)造性二難,常用推理定律(詳見方世昌的《離散數(shù)學(xué)》),P?(P∨Q)加法式(P∧Q)?P簡化式((P?Q)∧P)?Q假言推理((P?Q)∧?Q)??P拒取式((A∨B)∧?A)?B析取三段論((A?B)∧(B?C))?(A?C)(假言)前提三段論(A?B)∧(C?D)∧(A∨C)?(B∨D)構(gòu)造性二難(A?B)∧(C?D)∧(?B∨?D)?(?A∨?C)破壞性二難,㈢規(guī)則,(1)代入規(guī)則：將公式?中出現(xiàn)的某一符號(hào)B每處均代以某一公式C，所到的公式D稱為C對(duì)?的代入。(2)分離規(guī)則：如果A?B且A，則B。,二、語義部分,(1)公理是永真公式。(2)規(guī)則規(guī)定如何從永真公式推出永真公式。分離規(guī)則指明，如果A?B永真且A永真，則B也為永真公式。(3)代入規(guī)則指明如果?為永真公式，則某一個(gè)公式正確代入公式?后所得的公式也為永真公式。(4)定理為永真公式，它們是從公理出發(fā)利用分離規(guī)則和代入規(guī)則推出來的公式。,第二章命題演算的推理理論,2.1命題演算的公理系統(tǒng)2.1.1公理系統(tǒng)的組成部分2.1.2公理系統(tǒng)的推理過程2.2命題演算的假設(shè)推理系統(tǒng)2.3命題演算的歸結(jié)推理法,,定理1(p18)P???P,證明：(1)(P??Q)?(Q??P)公理14(2)(?P??P)?(P???P)P用?P，Q用P代入(3)P?P公理1(4)?P??PP用?P代入(5)P???P(2)(4)分離,??P=P,?,例(P∨P)→P,證明：(1)(P→R)→((Q→R)→((P∨Q)→R)))公理13(2)(P→P)→((P→P)→((P∨P)→P)))(1)式中Q用P、R用P代入P→P公理1(P→P)→((P∨P)→P)(2)(3)分離(P∨P)→P(3)(4)分離,例P?(P?P),證明(1)(P→R)→((Q→R)→((P∨Q)→R)))公理13(2)(P→P)→((P→P)→((P∨P)→P)))(1)式中Q用P、R用P代入(3)P→P公理1(4)(P→P)→((P∨P)→P)(2)(3)分離(5)(P∨P)→P(3)(4)分離(6)P→(P∨Q)公理11(7)P→(P∨P)(6)式中Q用P代入(8)(P?Q)?((Q?P)?(P?Q))公理7(9)(P?(P∨P))?(((P∨P)?P)?(P?(P∨P)))(8)式中Q用P∨P代入(10)((P∨P)?P)?(P?(P∨P))(7)(9)分離(11)P?(P∨P)(5)(10)分離,定理2(p18)(P?Q)?((R?P)?(R?Q)),分析：由傳遞公理3知道(R?P)?((P?Q)?(R?Q))與要求證的公式的聯(lián)系是兩個(gè)前件次序換一換，就可以用調(diào)頭公理2：(P?(Q?R))?(Q?(P?R)),加頭公式,定理2(p18)(P?Q)?((R?P)?(R?Q)),證明：(1)(P?Q)?((Q?R)?(P?R))公理3(2)(R?P)?((P?Q)?(R?Q))P用R，Q用P，R用Q代入(3)(P?(Q?R))?(Q?(P?R))公理2(4)((R?P)?((P?Q)?(R?Q)))?((P?Q)?(R?P)?(R?Q)))P用R?P，Q用P?Q，R用R?Q代入(5)(P?Q)?((R?P)?(R?Q))(4)(2)分離,定理3(p18,拒取式)(P?Q)?(?Q??P),分析：由公理14，(P??Q)?(Q??P)，可以得到(P???Q)?(?Q??P)下面就是要建立(P?Q)與(P???Q)之間的聯(lián)系。如果(P?Q)?(P???Q)，則由傳遞性知道結(jié)論成立。下面先證明(P?Q)?(P???Q)。,證明：先證(P?Q)?(P???Q),(1)P???P定理1(2)Q???QP用Q代入(3)(P??Q)?(Q??P)公理14(4)(P???Q)?(?Q??P)Q用?Q代入(5)(P?Q)?((R?P)?(R?Q))加頭定理2(6)(Q???Q)?((P?Q)?(P???Q))(5)式中P用Q代入，Q用??Q代入，R用P代入(7)(P?Q)?(P???Q)(6)(2)分離,定理3(p18,拒取式)(P?Q)?(?Q??P),證明：(1)P???P定理1(2)Q???QP用Q代入(3)(P??Q)?(Q??P)公理14(4)(P???Q)?(?Q??P)Q用?Q代入(5)(P?Q)?((R?P)?(R?Q))定理2(6)(Q???Q)?((P?Q)?(P???Q))(5)式中P用Q代入，Q用??Q代入，R用P代入(7)(P?Q)?(P???Q)(6)(2)分離(8)(P?Q)?((Q?R)?(P?R))公理3(9)((P?Q)?(P???Q))?(((P???Q)?(?Q??P))?((P?Q)?(?Q??P)))(8)式中P用P?Q，Q用P???Q，R用?Q??P代入(10)((P???Q)?(?Q??P))?((P?Q)?(?Q??P))(9)(7)分離(11)(P?Q)?(?Q??P)(10)(4)分離,例（同定理3）,已知公理A:P???PB:(P??Q)?(Q??P)C:(P?Q)?((R?P)?(R?Q))D:(P?Q)?((Q?R)?(P?R))要證(P?Q)?(?Q??P)為本系統(tǒng)中的定理。,公理推理證明定理的方法,對(duì)于簡單題，可以把待證明的公式變成永真蘊(yùn)涵式的后件，再證明前件永真。,引理P?((P?Q)?Q),證明：(1)(P?(Q?R))?(Q?(P?R))公理2(2)((P?Q)?(P?Q))?(P?((P?Q)?Q))Q用P代入，R用Q代入，P用P?Q代入(3)P?P公理1(4)(P?Q)?(P?Q)代入(5)P?((P?Q)?Q)分離(2)(4),例1(p18)已知引理，試證明(P??P)??P,(1)P?((P?Q)?Q)定理(2)P?((P??P)??P)Q用?P代入(3)(P??Q)?(Q??P)公理14(4)((P??P)??P)?(P??(P??P))P用P??P代入，Q用P代入(5)(P?Q)?((R?P)?(R?Q))定理2(6)(((P??P)??P)?(P??(P??P)))?((P?((P??P)??P))?(P?(P??(P??P))))P用(P??P)??P，Q用P??(P??P)，R用P代入(7)(P?((P??P)??P))?(P?(P??(P??P)))(6)(4)分離(8)P?(P??(P??P))(7)(2)分離(9)(P?(P?Q))?(P?Q)公理4(10)(P?(P??(P??P)))?(P??(P??P))Q用?(P??P)代入(11)(P??(P??P))(10)(8)分離(12)(P??(P??P))?((P??P)??P)(3)式中Q用P??P代入(13)(P??P)??P(12)(11)分離,例2(p19),已知公理：AP?(Q?P)B(P?(Q?R))?((P?Q)?(P?R))C(P?(Q?R))?(Q?(P?R))DP?(P?Q)E(P?Q)?(Q?P)及分離規(guī)則和代入規(guī)則證明公式(R??R)?(P?P)為定理。,P?P？,例2的分析,先要證明P?P如果用公理A：P?（Q?P），得到P?（P?P），難以繼續(xù)。,證明:先證P?P,P?(Q?P)公理A(2)(P?(Q?R))?((P?Q)?(P?R))公理B(3)(P?(Q?P))?((P?Q)?(P?P))R用P代入(2)(4)(P?Q)?(P?P)(3)(1)分離(5)(P?(Q?P))?(P?P)Q用Q?P代入(4)(6)P?P(5)(1)分離,例2的證明(p19),(1)P?(Q?P)公理A(2)(P?(Q?R))?((P?Q)?(P?R))公理B(3)(P?(Q?P))?((P?Q)?(P?P))R用P代入(2)(4)(P?Q)?(P?P)(3)(1)分離(5)(P?(Q?P))?(P?P)Q用Q?P代入(4)(6)P?P(5)(1)分離(7)P?(P?Q)公理D(8)(P?P)?((P?P)?(R??R))P用P?P，Q用R??R代入(7)(9)(P?P)?(R??R)(8)(6)分離(10)(P?Q)?(Q?P)公理E(11)((P?P)?(R??R))?((R??R)?(P?P))P用P?P，Q用R??R代入(10)(12)(R??R)?(P?P)(11)(9)分離,已知公理A:(p?q)?((q?p)?(p?q))B:p?p∨qC:p?pD:(p?r)?((q?r)?((p∨q)?r))E:p∧q?p證明定理:p?(p∨p),同前例!,例3,(1)p?p∨q公理B(2)p?p∨p代入(3)(p?r)?((q?r)?((p∨q)?r))公理D(4)(p?p)?((p?p)?((p∨p)?p))代入(5)p?p公理C(6)(p?p)?((p∨p)?p)(4)(5)分離(7)(p∨p)?p(5)(6)分離,證明：先證(p∨p)?p,(1)p?p∨q公理B(2)p?p∨p代入(3)(p?r)?((q?r)?((p∨q)?r))公理D(4)(p?p)?((p?p)?((p∨p)?p))代入(5)p?p公理C(6)(p?p)?((p∨p)?p)(4)(5)分離(7)(p∨p)?p(5)(6)分離(8)(p?q)?((q?p)?(p?q))公理A(9)(p?(p∨p))?(((p∨p)?p)?(p?(p∨p)))代入(10)((p∨p)?p)?(p?(p∨p))(2)(9)分離(11)(p?(p∨p))(7)(10)分離,例3的證明,例4,已知公理A：(Q?R)?((P?Q)?(P?R))B：(P?(Q?R))?(Q?(P?R))C：(P?Q)?((Q?R)?(P?R))D：??P?P及分離規(guī)則和代入規(guī)則,試證明下式為定理((P?Q)??R)?((P???Q)??R),例4的證明,(1)??P?P公理4(2)??Q?QP用Q代入(3)(Q?R)?((P?Q)?(P?R))公理1(4)(??Q?Q)?((P???Q)?(P?Q))Q用??Q代入,R用Q代入(5)(P???Q)?(P?Q)(4)、(2)分離(6)(P?Q)?((Q?R)?(P?R))公理3(7)((P???Q)?(P?Q))?(((P?Q)??R)?((P???Q)??R))P用P???Q代入，Q用P?Q代入，R用?R代入(8)((P?Q)??R)?((P???Q)??R)(7)、(5)分離,例5,已知公理：A:P?(Q?P)B:(Q?R)?((P?Q)?(P?R))C:(P?P)?PD:Q?(P?Q)E:(P?Q)?(Q?P)及分離規(guī)則和代入規(guī)則試證明P?P為定理,例5的證明,(1)P?(Q?P)公理A(2)(Q?R)?((P?Q)?(P?R))公理B(3)(P∨P)?P公理C(4)Q?(P?Q)公理D(5)(P∨Q)?(Q∨P)公理E(6)((P∨P)?P)?((P?(P∨P))?(P?P))(2)式中Q用P∨P、R用P代入(7)(P?(P∨P))?(P?P)(3)(6)分離(8)P?(P∨P)(4)式中Q用P代入(9)P?P(7)(8)分離,第二章命題演算的推理理論,2.1命題演算的公理系統(tǒng)2.1.1公理系統(tǒng)的組成部分2.1.2公理系統(tǒng)的推理過程2.2命題演算的假設(shè)推理系統(tǒng)2.3命題演算的歸結(jié)推理法,,