離散數(shù)學(xué)析取范式與合取范式.ppt

1、1,1.4 析取范式與合取范式,簡單析取式與簡單合取式 析取范式與合取范式 主析取范式與主合取范式,2,定義 文字:命題變項及其否定的總稱. 簡單析取式:有限個文字構(gòu)成的析取式. 如 p, q, pq, pqr, 簡單合取式:有限個文字構(gòu)成的合取式. 如 p, q, pq, pqr, ,1）一個簡單析取式為重言式當(dāng)且僅當(dāng)它同時含 有一個命題變項及它的否定；,2）一個簡單和取式為矛盾式當(dāng)且僅當(dāng)它同時含 有一個命題變項及它的否定.,由定義易知：,3,由有限個簡單合取式組成的析取式. A1A2Ar , 其中A1, A2, , Ar 是簡單合取式 合取范式:由有限個簡單析取式組成的合取式. A1A2A

2、r , 其中A1, A2, , Ar 是簡單析取式,由定義易知：,析取范式:,1）在析取范式（合取范式）中沒有聯(lián)結(jié)詞,2）聯(lián)結(jié)詞 只出現(xiàn)在原子命題前面.,3）析取范式（合取范式）是合取式（析取式）的析取式（合取式）.,4,范式:析取范式與合取范式的總稱. 公式A的析取范式: 與A等值的析取范式 公式A的合取范式: 與A等值的合取范式 說明： 單個文字既是簡單析取式，又是簡單合取式 形如pqr, pqr 的公式既是析取范式， 又是合取范式 (為什么?),5,任何命題公式都存在著 與之等值的析取范式與合取范式. 求公式A的范式的步驟： (1) 消去A中的, （若存在） (2) 內(nèi)移或消去否定聯(lián)結(jié)詞

3、 (3) 利用分配律 對分配（析取范式） 對分配（合取范式） 公式的范式存在，但不惟一，這是它的局限性.,定理（范式存在定理）,6,求公式的范式舉例,例1.15 求下列公式的析取范式與合取范式: (1) A = ( pq)r 解 (pq)r (pq)r （消去） pqr （結(jié)合律） 這既是A的析取范式（由3個簡單合取式組成的 析取式），又是A的合取范式（由一個簡單析 取式組成的合取式）,7,(2) B = ( pq)r 解: (pq)r (pq)r （消去第一個） (pq)r （消去第二個） (pq)r （否定號內(nèi)移德摩根律） 這一步已為析取范式（兩個簡單合取式構(gòu)成） 繼續(xù)： (pq)r (p

4、r)(qr) （對分配律） 這一步得到合取范式（由兩個簡單析取式構(gòu)成）,8,例1.16 (1)求( pq) (p r) 的析取范式; 解: ( pq) (p r) ( pq) ( p r) （消去） ( pq) ( p r) （雙重否定律） ( p p)(q p)( p r)(q r) （對分配） (q p)( p r)(q r) （零律,同一律）,9,(2) 求 ( p q) (p r) 的合取范式。 解: ( p q) (p r) (p q) ( p r) （消去） (p q p) (pq r) （ 對 分配） p q r （排中律,同一律）,10,極小項,定義 在含有n個命題變項的簡單合

5、取式中， 若每個命題變項均以文字的形式在其中出現(xiàn) 且只出現(xiàn)一次，而且第i（1 i n）個文字出 現(xiàn)在左起第 i 位上，這樣的簡單合取式稱為 極小項. 如： p q， p q r,11,說明：n個命題變項產(chǎn)生2n個極小項，2n個極小 項均互不等值. 用mi 表示第i個極小項，其中i是 該極小項成真賦值的十進制表示, mi 稱為極小 項的名稱.,12,p q,p q,p q,p q,0 0,0 1,1 0,1 1,由 p, q 兩個命題變項形成的極小項:,13,由 p, q, r 三個命題變項形成的極小項:,14,主析取范式,主析取范式: 由極小項構(gòu)成的析取范式. 例如，n=3, 命題變項為p,

6、q, r時， (pqr)(pqr) m1m3 是主析取范式 A的主析取范式: 與A等值的主析取范式.,15,定理 任何命題公式都存在著與之等值的主析取 范式, 并且是惟一的. 用等值演算法求公式的主析取范式的步驟： (1) 先求析取范式; (2) 將不是極小項的簡單合取式化成與之等值的 若干個極小項的析取，需要利用同一律、排中 律、分配律、等冪律 (3) 極小項用名稱mi 表示，按角標(biāo)從小到大順序排序.,16,求公式的主析取范式,例1.17 求公式 (pq)r 的主析取范式. (pq)r (pq)r , （析取范式） 其中 (pq) (pq)(rr) (pqr)(pqr) m6m7 , ,17

7、,r (pp)(qq)r (pqr)(pqr)(pqr)(pqr) m1m3m5m7 , 代入并排序，得 (pq)r m1m3m5 m6m7（主析取范式）,18,例1.18 求下列公式的主析取范式. (pq) ( p r ) ( p q) r ) p 答案: (1) (pq) ( p r ) m2 m3m5 m7 (2) ( p q) r ) p m2 m4m5 m6m7,19,例1.19 由( p q) r 的真值表求其主析取范式.,0 0 0,0 0 1,0 1 0,1 1 1,0 1 1,1 0 0,1 0 1,1 1 0,1,1,1,0,0,1,1,1,1,1,1,0,0,0,0,0,

8、主析取范式為： m3m5m7,20,作業(yè):P36 17(1)(3)，18(1)，19,21,1. 證明： p(qr) (pq)r (p q) (p q) p 2. 求主析取范式： (p q) r ( pq) ( qr ) (3) ( pq) q r (4) ( pq) r,課堂練習(xí)：,(0, 1, 3, 7),(1, 3, 5, 7),(5),(1, 3, 4, 5, 7),22,主范式的用途與真值表相同,(1) 求公式的成真賦值和成假賦值 例如 (pq)r m1m3m5 m6m7， 其成真賦值為001, 011, 101, 110, 111， 其余的賦值 000, 010, 100為成假賦值

9、.,23,設(shè)A含n個命題變項，則 A為重言式 A的主析取范式含2n個極小項 A為矛盾式 A的主析取范式為0 A為非重言式的可滿足式 A的主析取范式中至少含一個但不含 全部極小項,(2) 判斷公式的類型,24,例1.20 用主析取范式判斷下述兩公式是否等值： p(qr) 與 (pq)r p(qr) 與 (pq)r 解: p(qr) m0m1m2m3 m4m5 m7 (pq)r m0m1m2m3 m4m5 m7 (pq)r m1m3 m4m5 m7 顯見，中兩公式等值，而的兩公式不等值.,(3) 判斷兩個公式是否等值,25,(4) 分析和解決一些實際問題,例1.21 某公司要從趙、錢、孫三名新畢業(yè)

10、的 大學(xué)生中選派一些人出國學(xué)習(xí)，選派必須滿足 以下條件： (1) 若趙去，則孫也可以去； (2) 若錢去，則孫不能去； (3) 若孫不去，則趙或錢可以去. 試用主析取范式法分析該公司如何選派他們出國？,26,解此類問題的步驟為： 將簡單命題符號化； 寫出各復(fù)合命題； 寫出由中復(fù)合命題組成的合取式； 求中所得公式的主析取范式。,27,解: 設(shè)p：派趙去，q：派錢去，r：派孫去. (1) p r (2) q r (3) r (p q) (1) (3)構(gòu)成的合取式為 A=( p r )(q r)(r (p q),28, A的演算: A (pqr)(pqr)(pqr) (1, 2, 5) 結(jié)論： 由可

11、知，A的成真賦值為001、010、101， 因而方案有三個： 孫去（趙、錢不去）； 錢去（趙、孫不去）； 趙、孫（錢不去）.,29,極大項,定義 在含有n個命題變項的簡單析取式中， 若每個命題變項均以文字的形式在其中出現(xiàn) 且只出現(xiàn)一次，而且第i（1 i n）個文字出 現(xiàn)在左起第 i 位上，這樣的簡單析取式稱為 極大項.,30,說明：n個命題變項產(chǎn)生2n個極大項，2n個極大 項均互不等值. 用Mi 表示第i個極大項，其中i是 該極大項成假賦值的十進制表示, Mi 稱為極大 項的名稱.,31,p q,p q,p q,p q,0 0,1 0,0 1,1 1,由 p, q 兩個命題變項形成的極大項,3

12、2,由p, q, r三個命題變項形成的極大項,33,極小項與極大項比較,由p, q兩個命題變項形成的極小項與極大項,34,由p, q, r三個命題變項形成的極小項與極大項,35,主合取范式: 由極大項構(gòu)成的合取范式. 例如，n = 3, 命題變項為p, q, r時， (pqr)(pqr) M1M5 是主合取范式 A的主合取范式: 與A等值的主合取范式.,由上述比較可知：,極小項mi 與極大項Mi的關(guān)系: mi Mi , Mi mi,36,求主合取范式的方法：,1. 等值演算法： (1) 先求合取范式; (2) 將不是極大項的簡單析取式化成與之等值的 若干個極大項的合取，需要利用零律、同一律、 排中律、分配律、等冪律 ; (3) 極大項用名稱Mi 表示，按角標(biāo)從小到大順序排序.,37,求公式的主合取范式,例1.22 求公式 (pq)r的主合取范式. (pq)r (pr)(qr) , （合取范式） pr p(qq)r (pqr)(pqr) M0M2 ,38,qr (pp)qr (pqr)(pqr) M0M4 , 代入并排序，得 (pq)r M0