資源描述：
《離散數(shù)學--命題邏輯1.5.ppt》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在PPT專區(qū)-天天文庫。
1、1.5對偶與范式對偶式與對偶原理析取范式與合取范式主析取范式與主合取范式1對偶式和對偶原理定義在僅含有聯(lián)結(jié)詞?,∧,∨的命題公式A中，將∨換成∧,∧換成∨，若A中含有0或1，就將0換成1，1換成0，所得命題公式稱為A的對偶式，記為A*.從定義不難看出，(A*)*還原成A定理設A和A*互為對偶式，p1,p2,…,pn是出現(xiàn)在A和A*中的全部命題變項，將A和A*寫成n元函數(shù)形式，則(1)?A(p1,p2,…,pn)?A*(?p1,?p2,…,?pn)(2)A(?p1,?p2,…,?pn)??A*(p1,p2,…,pn)定理（對偶原理）設A，B為兩個命題公式，若A?B，則A*?B*.2析取范式
2、與合取范式文字:命題變項及其否定的總稱簡單析取式:有限個文字構(gòu)成的析取式如p,?q,p??q,p?q?r,…簡單合取式:有限個文字構(gòu)成的合取式如p,?q,p??q,p?q?r,…析取范式:由有限個簡單合取式組成的析取式A1?A2???Ar,其中A1,A2,?,Ar是簡單合取式合取范式:由有限個簡單析取式組成的合取式A1?A2???Ar,其中A1,A2,?,Ar是簡單析取式3析取范式與合取范式(續(xù))范式:析取范式與合取范式的總稱公式A的析取范式:與A等值的析取范式公式A的合取范式:與A等值的合取范式說明：單個文字既是簡單析取式，又是簡單合取式p??q?r,?p?q??r既是析取范式，又是合
3、取范式(為什么?)4命題公式的范式定理任何命題公式都存在著與之等值的析取范式與合取范式.求公式A的范式的步驟：(1)消去A中的?,?（若存在）(2)否定聯(lián)結(jié)詞?的內(nèi)移或消去(3)使用分配律?對?分配（析取范式）?對?分配（合取范式）公式的范式存在，但不惟一5求公式的范式舉例例求下列公式的析取范式與合取范式(1)A=(p??q)??r解(p??q)??r?(?p??q)??r（消去?）??p??q??r（結(jié)合律）這既是A的析取范式（由3個簡單合取式組成的析取式），又是A的合取范式（由一個簡單析取式組成的合取式）6求公式的范式舉例(續(xù))(2)B=(p??q)?r解(p??q)?r?(?p??
4、q)?r（消去第一個?）??(?p??q)?r（消去第二個?）?(p?q)?r（否定號內(nèi)移——德?摩根律）這一步已為析取范式（兩個簡單合取式構(gòu)成）繼續(xù)：(p?q)?r?(p?r)?(q?r)（?對?分配律）這一步得到合取范式（由兩個簡單析取式構(gòu)成）7極小項與極大項定義在含有n個命題變項的簡單合取式(簡單析取式)中，若每個命題變項均以文字的形式在其中出現(xiàn)且僅出現(xiàn)一次，而且第i（1?i?n）個文字出現(xiàn)在左起第i位上，稱這樣的簡單合取式（簡單析取式）為極小項（極大項）.說明：n個命題變項產(chǎn)生2n個極小項和2n個極大項2n個極小項（極大項）均互不等值用mi表示第i個極小項，其中i是該極小項成真賦
5、值的十進制表示.用Mi表示第i個極大項，其中i是該極大項成假賦值的十進制表示,mi(Mi)稱為極小項(極大項)的名稱.mi與Mi的關系:?mi?Mi,?Mi?mi8極小項與極大項(續(xù))由p,q兩個命題變項形成的極小項與極大項公式成真賦值名稱公式成假賦值名稱?p??q?p?qp??qp?q00011011m0m1m2m3p?qp??q?p?q?p??q00011011M0M1M2M3極小項極大項9由p,q,r三個命題變項形成的極小項與極大項極小項極大項公式成真賦值名稱公式成假賦值名稱?p??q??r?p??q?r?p?q??r?p?q?rp??q??rp??q?rp?q??rp?q?r00
6、0001010011100101110111m0m1m2m3m4m5m6m7p?q?rp?q??rp??q?rp??q??r?p?q?r?p?q??r?p??q?r?p??q??r000001010011100101110111M0M1M2M3M4M5M6M710主析取范式與主合取范式主析取范式:由極小項構(gòu)成的析取范式主合取范式:由極大項構(gòu)成的合取范式例如，n=3,命題變項為p,q,r時，(?p??q?r)?(?p?q?r)?m1?m3是主析取范式(p?q??r)?(?p?q??r)?M1?M5是主合取范式A的主析取范式:與A等值的主析取范式A的主合取范式:與A等值的主合取范式.11主析
7、取范式與主合取范式(續(xù))定理任何命題公式都存在著與之等值的主析取范式和主合取范式,并且是惟一的.用等值演算法求公式的主范式的步驟：(1)先求析取范式（合取范式）(2)將不是極小項（極大項）的簡單合取式（簡單析取式）化成與之等值的若干個極小項的析取（極大項的合?。?，需要利用同一律（零律）、排中律（矛盾律）、分配律、冪等律等.(3)極小項（極大項）用名稱mi（Mi）表示，并按角標從小到大順序排序.12求公式的主范式例求公式A=(p??q
