離散數(shù)學(xué)1.5

1、1,1.5 對偶與范式,對偶式與對偶原理 析取范式與合取范式 主析取范式與主合取范式,2,對偶式和對偶原理,定義 在僅含有聯(lián)結(jié)詞?, ∧,∨的命題公式A中，將∨換成∧, ∧換成∨，若A中含有0或1，就將0換成1，1換成0，所得命題公式稱為A的對偶式，記為A*.從定義不難看出，(A*)* 還原成A定理 設(shè)A和A*互為對偶式，p1,p2,…,pn是出現(xiàn)在A和A*中的全部命題變項，將A和A*寫成n元函數(shù)形式，則 (1) ? A

2、(p1,p2,…,pn) ? A* (? p1, ? p2,…, ? pn) (2) A(? p1, ? p2,…, ? pn) ? ? A* (p1,p2,…,pn) 定理（對偶原理）設(shè)A，B為兩個命題公式，若A ? B，則A* ? B*.,3,析取范式與合取范式,文字:命題變項及其否定的總稱簡單析取式:有限個文字構(gòu)成的析取式如 p, ?q, p??q, p?q?r, …簡單合取式:有限個文字構(gòu)成的合取式如 p,

3、 ?q, p??q, p?q?r, …析取范式:由有限個簡單合取式組成的析取式 A1?A2???Ar, 其中A1,A2,?,Ar是簡單合取式合取范式:由有限個簡單析取式組成的合取式 A1?A2???Ar , 其中A1,A2,?,Ar是簡單析取式,4,析取范式與合取范式(續(xù)),范式:析取范式與合取范式的總稱 公式A的析取范式: 與A等值的析取范式公式A的合取范式: 與A等值的合取范式說明： 單個文字既

4、是簡單析取式，又是簡單合取式形如 p??q?r, ?p?q??r 的公式既是析取范式，又是合取范式 (為什么?),5,命題公式的范式,定理 任何命題公式都存在著與之等值的析取范式與合取范式.求公式A的范式的步驟： (1) 消去A中的?, ?（若存在） (2) 否定聯(lián)結(jié)詞?的內(nèi)移或消去 (3) 使用分配律 ?對?分配（析取范式） ?對?分配（合取范式）公式的范

5、式存在，但不惟一，這是它的局限性,6,求公式的范式舉例,例 求下列公式的析取范式與合取范式(1) A=(p??q)??r解 (p??q)??r ? (?p??q)??r （消去?） ? ?p??q??r （結(jié)合律）這既是A的析取范式（由3個簡單合取式組成的析取式），又是A的合取范式（由一個簡單析取式組成的合取式）,7,求公式的范式舉例(續(xù)),(2) B=(p??q)?r解 (

6、p??q)?r ? (?p??q)?r （消去第一個?） ? ?(?p??q)?r （消去第二個?） ? (p?q)?r （否定號內(nèi)移——德摩根律）這一步已為析取范式（兩個簡單合取式構(gòu)成）繼續(xù)： (p?q)?r ? (p?r)?(q?r) （?對?分配律）這一步得到合取范式（由兩個簡單析取式構(gòu)成）,8,極小項與極大項,定義 在含有n個命題變

7、項的簡單合取式(簡單析取式)中，若每個命題變項均以文字的形式在其中出現(xiàn)且僅出現(xiàn)一次，而且第i（1?i?n）個文字出現(xiàn)在左起第i位上，稱這樣的簡單合取式（簡單析取式）為極小項（極大項）.說明：n個命題變項產(chǎn)生2n個極小項和2n個極大項 2n個極小項（極大項）均互不等值 用mi表示第i個極小項，其中i是該極小項成真賦值的十進(jìn)制表示. 用Mi表示第i個極大項，其中i是該極大項成假賦值的十進(jìn)制表示, mi(Mi)稱為極小

8、項(極大項)的名稱. mi與Mi的關(guān)系: ?mi ? Mi , ?Mi ? mi,9,極小項與極大項(續(xù)),由p, q兩個命題變項形成的極小項與極大項,10,,由p, q, r三個命題變項形成的極小項與極大項,11,主析取范式與主合取范式,主析取范式: 由極小項構(gòu)成的析取范式主合取范式: 由極大項構(gòu)成的合取范式例如，n=3, 命題變項為p, q, r時， (?p??q?r)?(?p?q?r) ? m1?

9、m3 是主析取范式 (p?q??r)?(?p?q??r) ? M1?M5 是主合取范式 A的主析取范式: 與A等值的主析取范式 A的主合取范式: 與A等值的主合取范式.,12,主析取范式與主合取范式(續(xù)),定理 任何命題公式都存在著與之等值的主析取范式和主合取范式, 并且是惟一的. 用等值演算法求公式的主范式的步驟： (1) 先求析取范式（合取范式） (2) 將不是極小項（極大項）的簡單合取式（簡

10、 單析取式）化成與之等值的若干個極小項的析 取（極大項的合?。?，需要利用同一律（零 律）、排中律（矛盾律）、分配律、冪等律等. (3) 極小項（極大項）用名稱mi（Mi）表示，并按角標(biāo)從小到大順序排序.,13,求公式的主范式,例 求公式 A=(p??q)?r的主析取范式與主合 取范式. (1) 求主析取范式 (p??q)?r ? (p?q)?r , （析取

11、范式） ① (p?q) ? (p?q)?(?r?r) ? (p?q??r)?(p?q?r) ? m6?m7 , ②,14,求公式的主范式(續(xù)),r ?(?p?p)?(?q?q)?r ?(?p??q?r)?(?p?q?r)?(p??q?r)?(p?q?r) ? m1?m3?m5?m7

12、 ③②, ③代入①并排序，得 (p??q)?r ? m1?m3?m5? m6?m7（主析取范式）,15,求公式的主范式(續(xù)),(2) 求A的主合取范式 (p??q)?r ? (p?r)?(q?r) , （合取范式） ① p?r ? p?(q??q)?r ? (p?q?r)?(p??q?r)

13、 ? M0?M2, ②,16,求公式的主范式(續(xù)),q?r ? (p??p)?q?r ? (p?q?r)?(?p?q?r) ? M0?M4 ③ ②, ③代入①并排序，得 (p??q)?r ? M