資源描述：
《離散數(shù)學(xué) 命題邏輯等值演算.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、主要內(nèi)容:等值式與基本的等值式等值演算與置換規(guī)則析(合)取范式，主析(合)取范式聯(lián)結(jié)詞完備集可滿足性問(wèn)題與消解法*第二章命題邏輯等值演算12.1等值式定義2.1若等價(jià)式A?B是重言式，則稱A與B等值，記作A?B，并稱A?B是等值式。幾點(diǎn)說(shuō)明：定義中，A,B,?均為元語(yǔ)言符號(hào)用真值表可檢查兩個(gè)公式是否等值2等值式例題例1判斷下列各組公式是否等值。(1)p?(q?r)與(p?q)?r111111011111110111011101000001010011100101110111(p?q)?rp?(q?r)q?rpqrp?q00000011結(jié)論:p?(q?
2、r)?(p?q)?r3等值式例題(2)p?(q?r)與(p?q)?r010111011111110111011101000001010011100101110111(p?q)?rp?(q?r)q?rpqrp?q11110011結(jié)論:p?(q?r)與(p?q)?r不等值4基本等值式雙重否定律??A?A冪等律A?A?A,A?A?A交換律A?B?B?A,A?B?B?A結(jié)合律(A?B)?C?A?(B?C),(A?B)?C?A?(B?C)分配律A?(B?C)?(A?B)?(A?C),A?(B?C)?(A?B)?(A?C)德摩根律?(A?B)??A??B?(A?
3、B)??A??B吸收律A?(A?B)?A,A?(A?B)?A5基本等值式零律A?1?1,A?0?0同一律A?0?A.A?1?A排中律A??A?1矛盾律A??A?0蘊(yùn)涵等值式A?B??A?B等價(jià)等值式A?B?(A?B)?(B?A)假言易位A?B??B??A等價(jià)否定等值式A?B??A??B歸謬論(A?B)?(A??B)??A特別提示：必須牢記這16組等值式(24式)，這是繼續(xù)學(xué)習(xí)的基礎(chǔ)。6等值演算與置換規(guī)則1.等值演算——由已知的等值式推演出新的等值式的過(guò)程2.等值演算的基礎(chǔ)：(1)等值關(guān)系的性質(zhì)：自反性、對(duì)稱性、傳遞性(2)基本的等值式(3)置換規(guī)則3
4、.置換規(guī)則設(shè)?(A)是含公式A的命題公式，?(B)是用公式B置換?(A)中所有的A后得到的命題公式。若B?A，則?(B)??(A)。7等值演算的應(yīng)用舉例證明兩個(gè)公式等值例2證明p?(q?r)?(p?q)?r證p?(q?r)??p?(?q?r)（蘊(yùn)涵等值式，置換規(guī)則）?(?p??q)?r（結(jié)合律，置換規(guī)則）??(p?q)?r（德摩根律，置換規(guī)則）?(p?q)?r（蘊(yùn)涵等值式，置換規(guī)則）注意：用等值演算不能直接證明兩個(gè)公式不等值8證明兩個(gè)公式不等值例3證明p?(q?r)與(p?q)?r不等值證方法一真值表法,見(jiàn)例1(2)方法二觀察法。觀察到000,010
5、是左邊的成真賦值，是右邊的成假賦值方法三先用等值演算化簡(jiǎn)公式，然后再觀察p?(q?r)??p??q?r(p?q)?r??(?p?q)?r?(p??q)?r更容易看出前面的兩個(gè)賦值分別是左邊的成真賦值和右邊的成假賦值等值演算的應(yīng)用舉例9判斷公式類型:A為矛盾式當(dāng)且僅當(dāng)A?0A為重言式當(dāng)且僅當(dāng)A?1例4用等值演算法判斷下列公式的類型(1)q??(p?q)(2)(p?q)?(?q??p)(3)((p?q)?(p??q))?r)等值演算的應(yīng)用舉例10等值演算的應(yīng)用舉例解(1)q??(p?q)?q??(?p?q)（蘊(yùn)涵等值式）?q?(p??q)（德摩根律）?p
6、?(q??q)（交換律，結(jié)合律）?p?0（矛盾律）?0（零律）矛盾式11判斷公式類型(2)(p?q)?(?q??p)?(?p?q)?(q??p)（蘊(yùn)涵等值式）?(?p?q)?(?p?q)（交換律）?1重言式(3)((p?q)?(p??q))?r)?(p?(q??q))?r（分配律）?p?1?r（排中律）?p?r（同一律）可滿足式，101和111是成真賦值，000和010等是成假賦值.122.2析取范式與合取范式基本概念(1)文字——命題變項(xiàng)及其否定的總稱(2)簡(jiǎn)單析取式——僅由有限個(gè)文字構(gòu)成的析取式p,?q,p??q,p?q?r,…(3)簡(jiǎn)單合取式—
7、—僅由有限個(gè)文字構(gòu)成的合取式p,?q,p??q,p?q?r,…(4)析取范式——由有限個(gè)簡(jiǎn)單合取式組成的析取式p,?p?q,p??q,(p??q)?(?p?q??r)?(q?r)(5)合取范式——由有限個(gè)簡(jiǎn)單析取式組成的合取式p,p??q,?p?q,(p?q??p?(p??q??r)(6)范式——析取范式與合取范式的總稱13說(shuō)明：?jiǎn)蝹€(gè)文字既是簡(jiǎn)單析取式，又是簡(jiǎn)單合取式形如p??q?r,?p?q??r的公式既是析取范式，又是合取范式定理2.1(1)一個(gè)簡(jiǎn)單析取式是重言式當(dāng)且僅當(dāng)它同時(shí)含有某個(gè)命題變項(xiàng)和它的否定式。(2)一個(gè)簡(jiǎn)單合取式是矛盾式當(dāng)且僅當(dāng)它同
8、時(shí)含有某個(gè)命題變項(xiàng)和它的否定式。14范式的性質(zhì)定理2.2(1)一個(gè)析取范式是矛盾式當(dāng)且僅當(dāng)它每個(gè)簡(jiǎn)單合取式都
