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

《離散數(shù)學第二章-命題演算的推理理論-命題演算的公理系統(tǒng)》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、目錄（數(shù)理邏輯）第一章命題演算基礎(chǔ)（6學時）第二章命題演算的推理理論（4學時）第三章謂詞演算基礎(chǔ)（5學時）第四章謂詞演算的推理理論（5學時）第五章遞歸函數(shù)論（4學時）第二章命題演算的推理理論例判斷下面各推理是否正確:(1)如果天氣涼快,小王就不去游泳。天氣涼快,所以小王沒去游泳。(2)如果天氣涼快,小王就不去游泳。天氣不涼快,所以小王去游泳了。推理是否正確：形式化引入符號：P表示天氣涼快，Q表示小王去游泳(1)如果天氣涼快,小王就不去游泳。天氣涼快,所以小王沒去游泳。((P??Q)?P)??Q(2)如果天氣涼快,小王就不去游泳。

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

3、)?(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é)論例如果今天下雨，則運動會將推遲舉行；今天下雨；運動會將推遲舉行。邏輯推理由前提推出結(jié)論（前提與結(jié)論都是命題，可真可假）演繹推理歸納推理歸納推理從真的前提出發(fā)，得到的

4、結(jié)論只能夠要求它與前提是協(xié)調(diào)的，但不一定是真的。它基于對特殊的代表的有限觀察，或基于對反復(fù)再現(xiàn)的現(xiàn)象的模式的有限觀察，用公式表達規(guī)律。所有觀察到的烏鴉都是黑的。所以所有烏鴉都是黑的。演繹推理可推導(dǎo)性——當前提的真蘊涵結(jié)論的真時，稱前提和結(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公理

5、系統(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)進行推理的能力。2．1．1公理系統(tǒng)的組成部分一、語法部分㈠基本符號公理系統(tǒng)所允許出現(xiàn)的全體符號的集合㈡公理㈢規(guī)則二、語義部分㈠基本符號命題變元P，Q，R，……等字母表示命題變元聯(lián)結(jié)詞?、?、?、?、?是聯(lián)結(jié)詞括號(，)是括號合式公式

6、(1)任何命題變元均是公式；(2)如果P為公式，則?P為公式；(3)如果為P，Q為公式，則P?Q，P?Q，P?Q，P?Q為公式；(4)當且僅當經(jīng)過有限次使用(1),(2),(3)所組成的符號串才是公式。推出符┣表示其后的公式為永真公式(教材中遺漏)㈡公理公理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)頭傳遞凝縮與?有關(guān)㈡公理公理8(P?Q)?

7、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與∧有關(guān)與∨有關(guān)與?有關(guān)常用推理定律(詳見耿素云《離散數(shù)學》)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)等價三段論(A?B)∧(C?D)∧(A∨C)?(B∨

8、D)構(gòu)造性二難常用推理定律(詳見方世昌的《離散數(shù)學》)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