離散數(shù)學(xué)(對(duì)偶和范式).ppt

1、a,1,1.5 對(duì)偶與范式,對(duì)偶式與對(duì)偶原理 析取范式與合取范式 主析取范式與主合取范式,a,2,對(duì)偶式和對(duì)偶原理,定義 在僅含有聯(lián)結(jié)詞, ,的命題公式A中，將換成, 換成，若A中含有0或1，就將0換成1，1換成0，所得命題公式稱為A的對(duì)偶式，記為A*. 從定義不難看出，(A*)* 還原成A 顯然，A也是A*的對(duì)偶式。可見A與A*互為對(duì)偶式。,a,3,對(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* (p

2、1,p2,pn) (1)表明，公式A的否定等價(jià)于其命題變?cè)穸ǖ膶?duì)偶式； (2)表明，命題變?cè)穸ǖ墓降葍r(jià)于對(duì)偶式之否定。,a,4,對(duì)偶式和對(duì)偶原理,定理（對(duì)偶原理）設(shè)A，B為兩個(gè)命題公式， 若A B，則A* B*. 有了等值式、代入規(guī)則、替換規(guī)則和對(duì)偶定理，便可以得到更多的永真式，證明更多的等值式，使化簡(jiǎn)命題公式更為方便。,a,5,判定問題,真值表 等值演算 范式,a,6,析取范式與合取范式,文字:命題變項(xiàng)及其否定的總稱 如 p, q 簡(jiǎn)單析取式:有限個(gè)文字構(gòu)成的析取式 如 p, q, pq, pqr, 簡(jiǎn)單合取式:有限個(gè)文字構(gòu)成的合取式 如 p, q, pq, pqr, 注意：一個(gè)命題變

3、元或其否定既可以是簡(jiǎn)單合取式，也可是簡(jiǎn)單析取式，如p，q等。,a,7,析取范式與合取范式,定理： 簡(jiǎn)單合取式為永假式的充要條件是：它同時(shí)含有某個(gè)命題變?cè)捌浞穸ā?定理： 簡(jiǎn)單析取式為永真式的充要條件是：它同時(shí)含有某個(gè)命題變?cè)捌浞穸ā?a,8,析取范式與合取范式,簡(jiǎn)單析取式:有限個(gè)文字構(gòu)成的析取式 如 p, q, pq, pqr, 簡(jiǎn)單合取式:有限個(gè)文字構(gòu)成的合取式 如 p, q, pq, pqr, 析取范式:由有限個(gè)簡(jiǎn)單合取式組成的析取式 A1A2Ar, 其中A1,A2,Ar是簡(jiǎn)單合取式 合取范式:由有限個(gè)簡(jiǎn)單析取式組成的合取式 A1A2Ar , 其中A1,A2,Ar是簡(jiǎn)單析取式,a,9,

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

5、的局限性,a,11,求公式的范式舉例,例 求下列公式的析取范式與合取范式 (1) A=(pq)r 解 (pq)r (pq)r （消去） pqr （結(jié)合律） 這既是A的析取范式（由3個(gè)簡(jiǎn)單合取式組成的析 取式），又是A的合取范式（由一個(gè)簡(jiǎn)單析取式 組成的合取式）,a,12,求公式的范式舉例(續(xù)),(2) B=(pq)r 解 (pq)r (pq)r （消去第一個(gè)） (pq)r （消去第二個(gè)） (pq)r （否定號(hào)內(nèi)移德摩根律） 這一步已為析取范式（兩個(gè)簡(jiǎn)單合取式構(gòu)成） 繼續(xù)： (pq)r (pr)(qr) （對(duì)分配律） 這一步得到合取范式（由兩個(gè)簡(jiǎn)單析取式構(gòu)成）,a,13,極小項(xiàng)與極大項(xiàng),定義 在

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

7、大項(xiàng)）. 例如，由兩個(gè)命題變?cè)猵和q，構(gòu)成大項(xiàng)有pq，pq，pq，pq；三個(gè)命題變?cè)猵，q和r，構(gòu)成pqr，pqr，pqr，pqr，pqr，pqr，pqr，pqr。,a,15,極小項(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è)小項(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)制

8、數(shù)編碼） mi(Mi)稱為極小項(xiàng)(極大項(xiàng))的名稱. mi與Mi的關(guān)系: mi Mi , Mi mi,a,16,極小項(xiàng)與極大項(xiàng)(續(xù)),由p, q兩個(gè)命題變項(xiàng)形成的極小項(xiàng)與極大項(xiàng),a,17,由p, q, r三個(gè)命題變項(xiàng)形成的極小項(xiàng)與極大項(xiàng),a,18,小項(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ì)角線上。,a,19,大項(xiàng)的性質(zhì)：,(a)沒有兩個(gè)大項(xiàng)是等價(jià)的。 (b)任何兩個(gè)不同大項(xiàng)之析取是永真的，即MiMj，ij。 (c)

9、所有大項(xiàng)之合取為永假，即 Mi。 (d) 每個(gè)大項(xiàng)只有一個(gè)解釋為假，且其真值0位于主對(duì)角線上。,a,20,主析取范式與主合取范式,主析取范式: 由極小項(xiàng)構(gòu)成的析取范式 主合取范式: 由極大項(xiàng)構(gòu)成的合取范式 例如，n=3, 命題變項(xiàng)為p, q, r時(shí)， (pqr)(pqr) m1m3 是主析取范式 (pqr)(pqr) M1M5 是主合取范式 A的主析取范式: 與A等值的主析取范式 A的主合取范式: 與A等值的主合取范式.,a,21,主析取范式與主合取范式(續(xù)),定理 任何命題公式都存在著與之等值的主析取范 式和主合取范式, 并且是惟一的. 用等值演算法求公式的主范式的步驟： (1) 先求析取范

10、式（合取范式） (2) 將不是極小項(xiàng)（極大項(xiàng)）的簡(jiǎn)單合取式（簡(jiǎn) 單析取式）化成與之等值的若干個(gè)極小項(xiàng)的析 ?。O大項(xiàng)的合?。?，需要利用同一律（零 律）、排中律（矛盾律）、分配律、冪等律等. (3) 極小項(xiàng)（極大項(xiàng)）用名稱mi（Mi）表示，并 按角標(biāo)從小到大順序排序.,a,22,主析取范式與主合取范式(續(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è)?，如q，則pp（qq)，并用分配律展開之，將相同的簡(jiǎn)單合取式

11、的多次出現(xiàn)化為一次出現(xiàn)， 這樣得到了給定公式的主析取范式。,a,23,從A的主析取范式求其主合取范式的步驟,(a)求出A的主析取范式中設(shè)有包含的小項(xiàng)。(b) 求出與(a)中小項(xiàng)的下標(biāo)相同的大項(xiàng)。(c) 做(b)中大項(xiàng)之合取，即為A的主合取范式。例如，(pq)qm1m3，則(pq)qM0M2。,a,24,求公式的主范式,例 求公式 A=(pq)r的主析取范式與主合 取范式. (1) 求主析取范式 (pq)r (pq)r , （析取范式） (pq) (pq)(rr) (pqr)(pqr) m6m7 , ,a,25,求公式的主范式(續(xù)),r (pp)(qq)r (pqr)(pqr)(pqr)(pqr

12、) m1m3m5m7 , 代入并排序，得 (pq)r m1m3m5 m6m7（主析取范式）,a,26,求公式的主范式(續(xù)),(2) 求A的主合取范式 (pq)r (pr)(qr) , （合取范式） pr p(qq)r (pqr)(pqr) M0M2, ,a,27,求公式的主范式(續(xù)),qr (pp)qr (pqr)(pqr) M0M4 , 代入并排序，得 (pq)r M0M2M4 （主合取范式）,a,28,主范式的用途與真值表相同,(1) 求公式的成真賦值和成假賦值 例如 (pq)r m1m3m5 m6m7， 其成真賦值為001, 011, 101, 110, 111， 其余的賦值 000,

13、010, 100為成假賦值. 類似地，由主合取范式也可立即求出成 假賦值和成真賦值.,a,29,主范式的用途(續(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),a,30,主范式的用途(續(xù)),例 用主析取范式判斷下述兩個(gè)公式是否等值： p(qr) 與 (pq)r p(qr) 與 (pq)r 解 p(qr) = m0m1m2m3 m4m5 m7 (pq)r =

14、 m0m1m2m3 m4m5 m7 (pq)r = m1m3 m4m5 m7 顯見，中的兩公式等值，而的不等值.,(3) 判斷兩個(gè)公式是否等值,說明： 由公式A的主析取范式確定它的主合取范式，反之亦然. 用公式A的真值表求A的主范式.,a,31,主范式的用途(續(xù)),例 某公司要從趙、錢、孫、李、周五名新畢 業(yè)的大學(xué)生中選派一些人出國(guó)學(xué)習(xí). 選派必須 滿足以下條件： (1)若趙去，錢也去； (2)李、周兩人中至少有一人去； (3)錢、孫兩人中有一人去且僅去一人； (4)孫、李兩人同去或同不去； (5)若周去，則趙、錢也去. 試用主析取范式法分析該公司如何選派他們出 國(guó)？,a,32,例 (續(xù)),解

15、此類問題的步驟為： 將簡(jiǎn)單命題符號(hào)化 寫出各復(fù)合命題 寫出由中復(fù)合命題組成的合取式 求中所得公式的主析取范式,a,33,例 (續(xù)),解 設(shè)p：派趙去，q：派錢去，r：派孫去， s：派李去，u：派周去. (1) (pq) (2) (su) (3) (qr)(qr) (4) (rs)(rs) (5) (u(pq) (1) (5)構(gòu)成的合取式為 A=(pq)(su)(qr)(qr) (rs)(rs)(u(pq),a,34,例 (續(xù)), A (pqrsu)(pqrsu) 結(jié)論：由可知，A的成真賦值為00110與11001， 因而派孫、李去（趙、錢、周不去）或派趙、錢、 周去（孫、李不去）. A的演算過程如