離散數(shù)學(xué)對(duì)偶和范式PPT課件

1、1對(duì)偶式和對(duì)偶原理定義 在僅含有聯(lián)結(jié)詞 , ,的命題公式A中，將換成, 換成，若A中含有0或1，就將0換成1，1換成0，所得命題公式稱為A的對(duì)偶式，記為A*.從定義不難看出，(A*)* 還原成A顯然，A也是A*的對(duì)偶式?？梢夾與A*互為對(duì)偶式。第1頁/共35頁2對(duì)偶式和對(duì)偶原理定理 設(shè)A和A*互為對(duì)偶式，p1,p2,pn是出現(xiàn)在A和A*中的全部命題變項(xiàng)，將A和A*寫成n元函數(shù)形式，則 (1) A(p1,p2,pn) A* ( p1, p2, pn) (2) A( p1, p2, pn) A* (p1,p2,pn) (1)表明，公式A的否定等價(jià)于其命題變?cè)穸ǖ膶?duì)偶式； (2)表明，命題變?cè)穸?/p>

2、的公式等價(jià)于對(duì)偶式之否定。第2頁/共35頁3對(duì)偶式和對(duì)偶原理定理（對(duì)偶原理）設(shè)A，B為兩個(gè)命題公式，若A B，則A* B*. .有了等值式、代入規(guī)則、替換規(guī)則和對(duì)偶定理，便可以得到更多的永真式，證明更多的等值式，使化簡(jiǎn)命題公式更為方便。第3頁/共35頁4判定問題真值表等值演算范式第4頁/共35頁5析取范式與合取范式 文字: :命題變項(xiàng)及其否定的總稱如 p, q簡(jiǎn)單析取式: :有限個(gè)文字構(gòu)成的析取式如 p, q, pq, p q r, 簡(jiǎn)單合取式: :有限個(gè)文字構(gòu)成的合取式如 p, q, pq, p q r, 注意：一個(gè)命題變?cè)蚱浞穸瓤梢允呛?jiǎn)單合取式，也可是簡(jiǎn)單析取式，如p， q等。第5頁/

3、共35頁6析取范式與合取范式 定理： 簡(jiǎn)單合取式為永假式的充要條件是：它同時(shí)含有某個(gè)命題變?cè)捌浞穸ā?定理： 簡(jiǎn)單析取式為永真式的充要條件是：它同時(shí)含有某個(gè)命題變?cè)捌浞穸?。?頁/共35頁7析取范式與合取范式 簡(jiǎn)單析取式: :有限個(gè)文字構(gòu)成的析取式如 p, q, pq, p q r, 簡(jiǎn)單合取式: :有限個(gè)文字構(gòu)成的合取式如 p, q, pq, p q r, 析取范式: :由有限個(gè)簡(jiǎn)單合取式組成的析取式 A1 A2Ar, 其中A1,A2,Ar是簡(jiǎn)單合取式合取范式: :由有限個(gè)簡(jiǎn)單析取式組成的合取式 A1 A2Ar , 其中A1,A2,Ar是簡(jiǎn)單析取式第7頁/共35頁8析取范式與合取范式(

4、(續(xù)) )范式: :析取范式與合取范式的總稱 公式A的析取范式: 與A等值的析取范式公式A的合取范式: 與A等值的合取范式說明： 單個(gè)文字既是簡(jiǎn)單析取式，又是簡(jiǎn)單合取式形如 pq r, p qr 的公式既是析取范式，又是合取范式 (為什么?) 第8頁/共35頁9命題公式的范式 定理 任何命題公式都存在著與之等值的析取范式與合取范式. .求公式A的范式的步驟： (1) 消去A中的, （若存在）（消去公式中除 、 和 以外公式中出現(xiàn)的所有聯(lián)結(jié)詞） ( 2 ) 否 定 聯(lián) 結(jié) 詞 的 內(nèi) 移 或 消 去 （ 使 用 ( P)P和德摩根律） (3) 使用分配律 對(duì) 分配（析取范式） 對(duì) 分配（合取范式

5、）公式的范式存在，但不惟一，這是它的局限性 第9頁/共35頁10求公式的范式舉例 例 求下列公式的析取范式與合取范式(1) A=(pq)r解 (pq)r ( pq)r （消去） pqr （結(jié)合律）這既是A的析取范式（由3個(gè)簡(jiǎn)單合取式組成的析取式），又是A的合取范式（由一個(gè)簡(jiǎn)單析取式組成的合取式）第10頁/共35頁11求公式的范式舉例( (續(xù)) )(2) B=(pq)r解 (pq)r ( pq)r （消去第一個(gè)） ( pq) r （消去第二個(gè)） (p q) r （否定號(hào)內(nèi)移德摩根律）這一步已為析取范式（兩個(gè)簡(jiǎn)單合取式構(gòu)成）繼續(xù)： (p q) r (p r) (q r) （ 對(duì) 分配律）這一步得到

6、合取范式（由兩個(gè)簡(jiǎn)單析取式構(gòu)成） 第11頁/共35頁12極小項(xiàng)與極大項(xiàng) 定義 在含有n個(gè)命題變項(xiàng)的簡(jiǎn)單合取式( (簡(jiǎn)單析取式) )中，若每個(gè)命題變項(xiàng)均以文字的形式在其中出現(xiàn)且僅出現(xiàn)一次，而且第i（1 i n）個(gè)文字出現(xiàn)在左起第i位上，稱這樣的簡(jiǎn)單合取式（簡(jiǎn)單析取式）為極小項(xiàng)（極大項(xiàng)）. 例如，兩個(gè)命題變?cè)猵和q，其構(gòu)成的小項(xiàng)有p q，pq， p q和 pq；而三個(gè)命題變?cè)猵、q和r，其構(gòu)成的小項(xiàng)有p q r，p qr，pq r，pqr， p q r ， p qr， pq r， pqr。第12頁/共35頁13極小項(xiàng)與極大項(xiàng) 定義 在含有n個(gè)命題變項(xiàng)的簡(jiǎn)單合取式( (簡(jiǎn)單析取式) )中，若每個(gè)命題

7、變項(xiàng)均以文字的形式在其中出現(xiàn)且僅出現(xiàn)一次，而且第i（1 i n）個(gè)文字出現(xiàn)在左起第i位上，稱這樣的簡(jiǎn)單合取式（簡(jiǎn)單析取式）為極小項(xiàng)（極大項(xiàng)）.例如，由兩個(gè)命題變?cè)猵和q，構(gòu)成大項(xiàng)有p q，pq， p q， pq；三個(gè)命題變?cè)猵，q和r，構(gòu)成p q r，p qr，pq r，pqr， p q r， p qr， pq r， pqr。第13頁/共35頁14極小項(xiàng)與極大項(xiàng) 說明：n個(gè)命題變項(xiàng)產(chǎn)生2n個(gè)極小項(xiàng)和2n個(gè)極大項(xiàng) 2n個(gè)極小項(xiàng)（極大項(xiàng)）均互不等值 用mi表示第i個(gè)極小項(xiàng)，其中i是該極小項(xiàng)成真賦值的十進(jìn)制表示. （將命題變?cè)醋值湫蚺帕校⑶野衙}變?cè)c1對(duì)應(yīng)，命題變?cè)姆穸ㄅc0對(duì)應(yīng)，則可對(duì)2n個(gè)

8、小項(xiàng)依二進(jìn)制數(shù)編碼） 用Mi表示第i個(gè)極大項(xiàng)，其中i是該極大項(xiàng)成假賦值的十進(jìn)制表示。（將n個(gè)命題變?cè)判?，并且把命題變?cè)c對(duì)應(yīng)，命題變?cè)姆穸ㄅc對(duì)應(yīng)，則可對(duì)2n個(gè)大項(xiàng)按二進(jìn)制數(shù)編碼） mi( (Mi) )稱為極小項(xiàng)( (極大項(xiàng)) )的名稱. mi與Mi的關(guān)系: : mi Mi , Mi mi 第14頁/共35頁15極小項(xiàng)與極大項(xiàng)( (續(xù)) )由p, q兩個(gè)命題變項(xiàng)形成的極小項(xiàng)與極大項(xiàng) 公式公式 成真賦值成真賦值名稱名稱 公式公式 成假賦值成假賦值名稱名稱 p q p q p q p q0 0 0 1 1 0 1 1 m0m1m2m3 p q p q p q p q 0 0 0 1 1 0 1

9、1 M0M1M2M3 極小項(xiàng)極小項(xiàng) 極大項(xiàng)極大項(xiàng) 第15頁/共35頁16 由p, q, r三個(gè)命題變項(xiàng)形成的極小項(xiàng)與極大項(xiàng) 極小項(xiàng)極小項(xiàng) 極大項(xiàng)極大項(xiàng) 公式公式 成真成真賦值賦值名稱名稱 公式公式 成假成假賦值賦值名稱名稱 p q r p q r p q r p q rp q rp q rp q rp q r0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1m0m1m2m3m4m5m6m7p q r p q r p q r p q r p q r p q r p q r p q r 0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1M

10、0M1M2M3M4M5M6M7 第16頁/共35頁小項(xiàng)的性質(zhì)： (a)沒有兩個(gè)小項(xiàng)是等價(jià)的，即是說各小項(xiàng)的真值表都是不同的； (b)任意兩個(gè)不同的小項(xiàng)的合取式是永假的：mimj，ij。 (c)所有小項(xiàng)之析取為永真： mi。 (d)每個(gè)小項(xiàng)只有一個(gè)解釋為真，且其真值1位于主對(duì)角線上。171ni第17頁/共35頁大項(xiàng)的性質(zhì)： (a)沒有兩個(gè)大項(xiàng)是等價(jià)的。 (b)任何兩個(gè)不同大項(xiàng)之析取是永真的，即MiMj，ij。 (c) 所有大項(xiàng)之合取為永假，即 Mi。 (d) 每個(gè)大項(xiàng)只有一個(gè)解釋為假，且其真值0位于主對(duì)角線上。181ni第18頁/共35頁19主析取范式與主合取范式 主析取范式: : 由極小項(xiàng)構(gòu)成

11、的析取范式主合取范式: : 由極大項(xiàng)構(gòu)成的合取范式例如，n=3, 命題變項(xiàng)為p, q, r時(shí)， ( pq r) ( p q r) m1 m3 是主析取范式 (p qr) ( p qr) M1 M5 是主合取范式 A的主析取范式: 與A等值的主析取范式 A的主合取范式: : 與A等值的主合取范式. 第19頁/共35頁20主析取范式與主合取范式( (續(xù)) )定理 任何命題公式都存在著與之等值的主析取范式和主合取范式, 并且是惟一的. . 用等值演算法求公式的主范式的步驟： (1) 先求析取范式（合取范式） (2) 將不是極小項(xiàng)（極大項(xiàng)）的簡(jiǎn)單合取式（簡(jiǎn) 單析取式）化成與之等值的若干個(gè)極小項(xiàng)的析 取

12、（極大項(xiàng)的合取），需要利用同一律（零 律）、排中律（矛盾律）、分配律、冪等律等. (3) 極小項(xiàng)（極大項(xiàng)）用名稱mi（Mi）表示，并按角標(biāo)從小到大順序排序. 第20頁/共35頁21主析取范式與主合取范式( (續(xù)) )用等值演算法求公式的主范式的步驟： (1) 先求析取范式 (2) 刪除析取范式中所有為永假的簡(jiǎn)單合取式 (3)用等冪律化簡(jiǎn)簡(jiǎn)單合取式中同一命題變?cè)闹貜?fù)出現(xiàn)為一次出現(xiàn)，如ppp。 (4) 用同一律補(bǔ)進(jìn)簡(jiǎn)單合取式中未出現(xiàn)的所有命題變?cè)鐀，則pp（ qq)，并用分配律展開之，將相同的簡(jiǎn)單合取式的多次出現(xiàn)化為一次出現(xiàn)， 這樣得到了給定公式的主析取范式。第21頁/共35頁從A的主析取范

13、式求其主合取范式的步驟 (a)求出A的主析取范式中設(shè)有包含的小項(xiàng)。(b) 求出與(a)中小項(xiàng)的下標(biāo)相同的大項(xiàng)。(c) 做(b)中大項(xiàng)之合取，即為A的主合取范式。例如，(pq) qm1 m3，則(pq) qM0 M2。22第22頁/共35頁23求公式的主范式例 求公式 A=(pq)r的主析取范式與主合 取范式. . (1) 求主析取范式 (pq)r (p q) r , （析取范式） (p q) (p q) ( r r) (p qr) (p q r) m6 m7 , 第23頁/共35頁24求公式的主范式( (續(xù)) ) r ( p p) ( q q) r ( pq r) ( p q r) (pq r

14、) (p q r) m1 m3 m5 m7 , 代入并排序，得 (pq)r m1 m3 m5 m6 m7（主析取范式） 第24頁/共35頁25求公式的主范式( (續(xù)) ) (2) 求A的主合取范式 (pq)r (p r) (q r) , （合取范式） p r p (qq) r (p q r) (pq r) M0 M2, 第25頁/共35頁26求公式的主范式( (續(xù)) ) q r (pp) q r (p q r) ( p q r) M0 M4 , 代入并排序，得 (pq)r M0 M2 M4 （主合取范式） 第26頁/共35頁27主范式的用途與真值表相同 (1) 求公式的成真賦值和成假賦值 例如

15、 (pq)r m1 m3 m5 m6 m7， 其成真賦值為001, 011, 101, 110, 111， 其余的賦值 000, 010, 100為成假賦值. 類似地，由主合取范式也可立即求出成 假賦值和成真賦值. 第27頁/共35頁28主范式的用途( (續(xù)) ) (2) 判斷公式的類型 設(shè)A含n個(gè)命題變項(xiàng)，則 A為重言式A的主析取范式含2n個(gè)極小項(xiàng) A的主合取范式為1.A為矛盾式 A的主析取范式為0 A的主合析取范式含2n個(gè)極大項(xiàng)A為非重言式的可滿足式A的主析取范式中至少含一個(gè)且不含全部極小項(xiàng)A的主合取范式中至少含一個(gè)且不含全部極大項(xiàng) 第28頁/共35頁29主范式的用途( (續(xù)) )例 用主

16、析取范式判斷下述兩個(gè)公式是否等值： p(qr) 與 (p q)r p(qr) 與 (pq)r解 p(qr) = m0 m1 m2 m3 m4 m5 m7 (p q)r = m0 m1 m2 m3 m4 m5 m7 (pq)r = m1 m3 m4 m5 m7顯見，中的兩公式等值，而的不等值. (3) 判斷兩個(gè)公式是否等值判斷兩個(gè)公式是否等值說明：說明： 由公式由公式A的主析取范式確定它的主合取范式，反之亦然的主析取范式確定它的主合取范式，反之亦然. 用公式用公式A的真值表求的真值表求A的主范式的主范式.第29頁/共35頁30主范式的用途( (續(xù)) ) 例 某公司要從趙、錢、孫、李、周五名新畢業(yè)

17、的大學(xué)生中選派一些人出國(guó)學(xué)習(xí). 選派必須滿足以下條件： (1)(1)若趙去，錢也去； (2)(2)李、周兩人中至少有一人去； (3)(3)錢、孫兩人中有一人去且僅去一人； (4)(4)孫、李兩人同去或同不去； (5)(5)若周去，則趙、錢也去. 試用主析取范式法分析該公司如何選派他們出國(guó)？第30頁/共35頁31例 (續(xù))解此類問題的步驟為： 將簡(jiǎn)單命題符號(hào)化 寫出各復(fù)合命題 寫出由中復(fù)合命題組成的合取式 求中所得公式的主析取范式 第31頁/共35頁32例 (續(xù))解 設(shè)p：派趙去，q：派錢去，r：派孫去， s：派李去，u：派周去. . (1) (pq) (2) (s u) (3) (qr) ( q r) (4) (r s) ( rs) (5) (u(p q) (1) (5)構(gòu)成的合取式為 A=(pq) (s u) (qr) ( q r) (r s) ( rs) (u(p q)第32頁/共35頁33例 (續(xù)) A ( pq r su) (p qrs u)結(jié)論：由可知，A的成真賦值為00110與11001，因而派孫、李去（趙、錢、周不去）或派趙、錢、周去（孫、李不去）. . A的演算過程如下: : A ( p q) (qr) ( q r) (s u) ( u (p q) (r s)