離散數(shù)學(xué) 命題邏輯等值演算.ppt

《離散數(shù)學(xué) 命題邏輯等值演算.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、主要內(nèi)容:等值式與基本的等值式等值演算與置換規(guī)則析(合)取范式，主析(合)取范式聯(lián)結(jié)詞完備集可滿足性問題與消解法*第二章命題邏輯等值演算12.1等值式定義2.1若等價式A?B是重言式，則稱A與B等值，記作A?B，并稱A?B是等值式。幾點說明：定義中，A,B,?均為元語言符號用真值表可檢查兩個公式是否等值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蘊涵等值式A?B??A?B等價等值式A?B?(A?B)?(B?A)假言易位A?B??B??A等價否定等值式A?B??A??B歸謬論(A?B)?(A??B)??A特別提示：必須牢記這16組等值式(24式)，這是繼續(xù)學(xué)習的基礎(chǔ)。6等值演算與置換規(guī)則1.等值演算——由已知的等值式推演出新的等值式的過程2.等值演算的基礎(chǔ)：(1)等值關(guān)系的性質(zhì)：自反性、對稱性、傳遞性(2)基本的等值式(3)置換規(guī)則3

4、.置換規(guī)則設(shè)?(A)是含公式A的命題公式，?(B)是用公式B置換?(A)中所有的A后得到的命題公式。若B?A，則?(B)??(A)。7等值演算的應(yīng)用舉例證明兩個公式等值例2證明p?(q?r)?(p?q)?r證p?(q?r)??p?(?q?r)（蘊涵等值式，置換規(guī)則）?(?p??q)?r（結(jié)合律，置換規(guī)則）??(p?q)?r（德摩根律，置換規(guī)則）?(p?q)?r（蘊涵等值式，置換規(guī)則）注意：用等值演算不能直接證明兩個公式不等值8證明兩個公式不等值例3證明p?(q?r)與(p?q)?r不等值證方法一真值表法,見例1(2)方法二觀察法。觀察到000,010

5、是左邊的成真賦值，是右邊的成假賦值方法三先用等值演算化簡公式，然后再觀察p?(q?r)??p??q?r(p?q)?r??(?p?q)?r?(p??q)?r更容易看出前面的兩個賦值分別是左邊的成真賦值和右邊的成假賦值等值演算的應(yīng)用舉例9判斷公式類型:A為矛盾式當且僅當A?0A為重言式當且僅當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)（蘊涵等值式）?q?(p??q)（德摩根律）?p

6、?(q??q)（交換律，結(jié)合律）?p?0（矛盾律）?0（零律）矛盾式11判斷公式類型(2)(p?q)?(?q??p)?(?p?q)?(q??p)（蘊涵等值式）?(?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)文字——命題變項及其否定的總稱(2)簡單析取式——僅由有限個文字構(gòu)成的析取式p,?q,p??q,p?q?r,…(3)簡單合取式—

7、—僅由有限個文字構(gòu)成的合取式p,?q,p??q,p?q?r,…(4)析取范式——由有限個簡單合取式組成的析取式p,?p?q,p??q,(p??q)?(?p?q??r)?(q?r)(5)合取范式——由有限個簡單析取式組成的合取式p,p??q,?p?q,(p?q??p?(p??q??r)(6)范式——析取范式與合取范式的總稱13說明：單個文字既是簡單析取式，又是簡單合取式形如p??q?r,?p?q??r的公式既是析取范式，又是合取范式定理2.1(1)一個簡單析取式是重言式當且僅當它同時含有某個命題變項和它的否定式。(2)一個簡單合取式是矛盾式當且僅當它同

8、時含有某個命題變項和它的否定式。14范式的性質(zhì)定理2.2(1)一個析取范式是矛盾式當且僅當它每個簡單合取式都