資源描述：
《第二章 命題邏輯等值演算》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、主要內(nèi)容等值式與基本的等值式等值演算與置換規(guī)則析取范式與合取范式，主析取范式與主合取范式聯(lián)結(jié)詞完備集可滿足性問題與消解法第二章命題邏輯等值演算12.1等值式定義2.1若等價(jià)式A?B是重言式，則稱A與B等值，記作A?B，并稱A?B是等值式幾點(diǎn)說明：定義中，A,B,?均為元語言符號(hào)A或B中可能有啞元出現(xiàn).例如(p?q)?((?p?q)?(?r?r))r為左邊公式的啞元.用真值表可檢查兩個(gè)公式是否等值請(qǐng)驗(yàn)證：p?(q?r)?(p?q)?rp?(q?r)不與(p?q)?r等值2等值式例題例1判斷下列各組公式是否等值:(1)p?(q?r)與(p
2、?q)?r111111011111110111011101000001010011100101110111(p?q)?rp?(q?r)q?rpqrp?q00000011結(jié)論:p?(q?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
3、?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?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特別提示：必須牢記
4、這16組等值式，這是繼續(xù)學(xué)習(xí)的基礎(chǔ)6等值演算與置換規(guī)則1.等值演算——由已知的等值式推演出新的等值式的過程2.等值演算的基礎(chǔ)：(1)等值關(guān)系的性質(zhì)：自反性、對(duì)稱性、傳遞性(2)基本的等值式(3)置換規(guī)則（見3）3.置換規(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（德摩根
5、律，置換規(guī)則）?(p?q)?r（蘊(yùn)涵等值式，置換規(guī)則）今后在注明中省去置換規(guī)則注意：用等值演算不能直接證明兩個(gè)公式不等值8證明兩個(gè)公式不等值例3證明p?(q?r)與(p?q)?r不等值證方法一真值表法,見例1(2)方法二觀察法.觀察到000,010是左邊的成真賦值，是右邊的成假賦值方法三先用等值演算化簡(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
6、?1例4用等值演算法判斷下列公式的類型(1)q??(p?q)(2)(p?q)?(?q??p)(3)((p?q)?(p??q))?r)等值演算的應(yīng)用舉例解(1)q??(p?q)?q??(?p?q)（蘊(yùn)涵等值式）?q?(p??q)（德摩根律）?p?(q??q)（交換律，結(jié)合律）?p?0（矛盾律）?0（零律）矛盾式10判斷公式類型(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（排
7、中律）?p?r（同一律）可滿足式，101和111是成真賦值，000和010等是成假賦值.11下面舉一個(gè)如何利用等值演算解決實(shí)際問題的例子：例：在某次研討會(huì)的中間休息時(shí)間，3名與會(huì)者根據(jù)王教授的口音對(duì)他是哪個(gè)省市的人判斷如下：甲：王教授不是蘇州人，是上海人.乙：王教授不是上海人，是蘇州人.丙：王教授既不是上海人，也不是杭州人.聽完這3人的判斷后,王教授笑說,你們3人中有一人說得全對(duì),有一人說對(duì)了一半,另一個(gè)說的全不對(duì).試用邏輯演算分析王教授到底是哪里人.12解設(shè)命題p：王教授是蘇州人.q：王教授是上海人.r：王教授是杭州人.p,q,r中
8、必有一個(gè)真命題，兩個(gè)假命題.甲的判斷為：?p?q乙的判斷為：p??q丙的判斷為：?q??r于是有13甲的判斷全對(duì)為：B1=?p?q甲的判斷對(duì)一半為：B2=(?p??q)?(p?q)甲的判斷全錯(cuò)為：B3=p??q乙的判斷全
