資源描述：
《離散數(shù)學(xué)之等值演算.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、11.3命題邏輯等值演算等值式基本等值式等值演算置換規(guī)則2等值式定義若等價(jià)式A?B是重言式，則稱A與B等值，記作A?B，并稱A?B是等值式說明：定義中，A,B,?均為元語(yǔ)言符號(hào),A或B中可能有啞元出現(xiàn).例如，在(p?q)?((?p?q)?(?r?r))中，r為左邊公式的啞元.用真值表可驗(yàn)證兩個(gè)公式是否等值請(qǐng)驗(yàn)證：p?(q?r)?(p?q)?rp?(q?r)(p?q)?r3基本等值式雙重否定律:??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
2、)?(A?B)?(A?C)4基本等值式(續(xù))德·摩根律:?(A?B)??A??B?(A?B)??A??B吸收律:A?(A?B)?A,A?(A?B)?A零律:A?1?1,A?0?0同一律:A?0?A,A?1?A排中律:A??A?1矛盾律:A??A?05基本等值式(續(xù))蘊(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注意:A,B,C代表任意的命題公式牢記這些等值式是繼續(xù)學(xué)習(xí)的基礎(chǔ)6等值演算與置換規(guī)則等值演算:由已知的等值式推演出新的等值式的過程置換規(guī)則：若A?B,則?(B)??
3、(A)等值演算的基礎(chǔ)：(1)等值關(guān)系的性質(zhì)：自反、對(duì)稱、傳遞(2)基本的等值式(3)置換規(guī)則7應(yīng)用舉例——證明兩個(gè)公式等值例1證明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ī)則）說明:也可以從右邊開始演算（請(qǐng)做一遍）因?yàn)槊恳徊蕉加弥脫Q規(guī)則，故可不寫出熟練后，基本等值式也可以不寫出8應(yīng)用舉例——證明兩個(gè)公式不等值例2證明:p?(q?r)(p?q)?r用等值演算不能直接證明兩個(gè)公式不等值,證明兩個(gè)公式不等值的基本思想是找到一個(gè)賦值使一個(gè)
4、成真,另一個(gè)成假.方法一真值表法（自己證）方法二觀察賦值法.容易看出000,010等是左邊的的成真賦值，是右邊的成假賦值.方法三用等值演算先化簡(jiǎn)兩個(gè)公式，再觀察.9應(yīng)用舉例——判斷公式類型例3用等值演算法判斷下列公式的類型(1)q??(p?q)解q??(p?q)?q??(?p?q)（蘊(yùn)涵等值式）?q?(p??q)（德?摩根律）?p?(q??q)（交換律，結(jié)合律）?p?0（矛盾律）?0（零律）由最后一步可知，該式為矛盾式.10例3(續(xù))(2)(p?q)?(?q??p)解(p?q)?(?q??p)?(?p?q)?(q??p)（蘊(yùn)涵等值式）?(?p?q)?(?p?q)（交換律）?1由最后一步可知，該
5、式為重言式.問：最后一步為什么等值于1？11例3(續(xù))(3)((p?q)?(p??q))?r)解((p?q)?(p??q))?r)?(p?(q??q))?r（分配律）?p?1?r（排中律）?p?r（同一律）這不是矛盾式，也不是重言式，而是非重言式的可滿足式.如101是它的成真賦值,000是它的成假賦值.總結(jié)：A為矛盾式當(dāng)且僅當(dāng)A?0A為重言式當(dāng)且僅當(dāng)A?1說明：演算步驟不惟一,應(yīng)盡量使演算短些121.4范式析取范式與合取范式主析取范式與主合取范式13析取范式與合取范式文字:命題變項(xiàng)及其否定的總稱簡(jiǎn)單析取式:有限個(gè)文字構(gòu)成的析取式如p,?q,p??q,p?q?r,…簡(jiǎn)單合取式:有限個(gè)文字構(gòu)成的合
6、取式如p,?q,p??q,p?q?r,…析取范式:由有限個(gè)簡(jiǎn)單合取式組成的析取式A1?A2???Ar,其中A1,A2,?,Ar是簡(jiǎn)單合取式合取范式:由有限個(gè)簡(jiǎn)單析取式組成的合取式A1?A2???Ar,其中A1,A2,?,Ar是簡(jiǎn)單析取式14析取范式與合取范式(續(xù))范式:析取范式與合取范式的總稱公式A的析取范式:與A等值的析取范式公式A的合取范式:與A等值的合取范式說明：?jiǎn)蝹€(gè)文字既是簡(jiǎn)單析取式，又是簡(jiǎn)單合取式p??q?r,?p?q??r既是析取范式，又是合取范式(為什么?)15命題公式的范式定理任何命題公式都存在著與之等值的析取范式與合取范式.求公式A的范式的步驟：(1)消去A中的?,?（若存在
7、）(2)否定聯(lián)結(jié)詞?的內(nèi)移或消去(3)使用分配律?對(duì)?分配（析取范式）?對(duì)?分配（合取范式）公式的范式存在，但不惟一16求公式的范式舉例例求下列公式的析取范式與合取范式(1)A=(p??q)??r解(p??q)??r?(?p??q)??r（消去?）??p??q??r（結(jié)合律）這既是A的析取范式（由3個(gè)簡(jiǎn)單合取式組成的析取式），又是A的合取范式（由一個(gè)簡(jiǎn)單析取式組成的合取式）17求公式的范式舉例(續(xù)
