第二章析取范式與合取范式

1、2.2 2.2 析取范式與合取范式析取范式與合取范式 簡單析取式簡單析取式(簡單合取式簡單合取式)命題變項及其否定稱為文字文字。如p, p僅有有限個文字構(gòu)成的析取式稱作簡單析取式。簡單析取式。 如 p, q; pp，pq ; pqr, pqr。 僅有有限個文字構(gòu)成的合取式稱作簡單合取式。簡單合取式。 如 p, q; pp，pq ; pqr, ppq 。注意： 一個文字既是簡單析取式，又是簡單合取式。 一般用A1,A2,As表示s個簡單析取式或s個簡單合取式。 定理定理2.1 一個簡單析取式是重言式當(dāng)且僅當(dāng)它同時含某個命題變項及它的否定式。 如：pp，ppr都是重言式； pq，pqr都不是重言式

2、。 一個簡單合取式是矛盾式當(dāng)且僅當(dāng)它同時含有某個命題變項及它的否定式。如：p p，p p r都是矛盾式； p q，p q r都不是矛盾式。 范式的定義范式的定義 由有限個簡單合取式構(gòu)成的析取式稱為析取范式。析取范式。 由有限個簡單析取式構(gòu)成的合取式稱為合取范式。合取范式。 析取范式與合取范式統(tǒng)稱為范式。范式。 設(shè) Ai(i=1,2,s)為簡單合取式,則析取范式的形式: A=A1A2As 例如A=(pq)(qr)p 設(shè) Ai(i=1,2,s)為簡單析取式,則合取范式的形式: A=A1A2As 例如A=(pqr)(pq)r 思考：pqr 與pqr屬于什么范式？ 定理定理2.2 一個析取范式是矛盾式

3、當(dāng)且僅當(dāng)它的每個簡單合取式都是矛盾式。 一個合取范式是重言式當(dāng)且僅當(dāng)它的每個簡單析取式都是重言式。 定理定理2.3 （范式存在定理）任一命題公式都存在著與之等值的析取范式與合取范式。 研究范式的目的是將給定公式化成與之等值的析取范式或合取范式，進而將公式化成與之等值的主析取范式或主合取范式。思考：怎樣將公式轉(zhuǎn)化為范式？例2.7 求下面公式的析取范式與合取范式： (pq) r 先求合取范式 (pq) r (pq) r （消去） (pq)r)(r(pq) （消去 ） (pq)r)(rpq) （消去） (pq)r)(pqr) （否定號內(nèi)移） (pr)(qr)(pqr) （對分配律） 將公式轉(zhuǎn)化為范式

4、的步驟將公式轉(zhuǎn)化為范式的步驟 消除聯(lián)結(jié)詞，AB AB A B (A B) (B A) (AB)(AB 縮小的作用范圍A A (AB) AB (AB) AB 利用分配率，轉(zhuǎn)化為析?。ê先。┓妒?A(BC) (AB)(AC) A(BC) (AB)(AC) 例2.7 求下面公式的析取范式與合取范式： (pq) r 求析取范式 (pq) r (pq) r （消去） (pq)r)(r(pq) （消去 ） (pq)r)(rpq) （消去） (pq)r)(pqr) （否定號內(nèi)移） (pqp)(pqq)(pqr） (rp)(rq)(rr) （對分配律） (pqr)(pr)(qr) 極小項與極大項的定義極小項與

5、極大項的定義極小項：極小項：在含有n個命題變項的簡單合取式中，若每個命題變項和它的否定式不同時出現(xiàn)，而二者之一必出現(xiàn)且僅出現(xiàn)一次，且第i個命題變項或它的否定式出現(xiàn)在從左算起的第i位上（若命題變項無角標(biāo)，就按字典順序排列），稱這樣的簡單合取式為極小項。例：p r q; p p r; p q p; p q r; p q r; p q r 思考思考: (1) n個命題變項共可產(chǎn)生多少個不同的極小項?(2)每個極小項有多少個成真賦值? 2n一個一個規(guī)定規(guī)定:成真賦值所對應(yīng)的二進制數(shù)轉(zhuǎn)換為十進制數(shù)i，就將所對應(yīng)極小項記作mi 極小項與極大項的定義極小項與極大項的定義極大項：極大項：在含有n個命題變項的簡

6、單析取式中，若每個命題變項和它的否定式不同時出現(xiàn)，而二者之一必出現(xiàn)且僅出現(xiàn)一次，且第i個命題變項或它的否定式出現(xiàn)在從左算起的第i位上（若命題變項無角標(biāo)，就按字典順序排列），稱這樣的簡單析取式為極大項。例：p r q; p p r; p q p; p q r; p q r; p q r 思考思考: (1) n個命題變項共可產(chǎn)生多少個不同的極大項?(2)每個極大項有多少個成假賦值? 2n一個一個規(guī)定規(guī)定:成假賦值所對應(yīng)的二進制數(shù)轉(zhuǎn)換為十進制數(shù)i，就將所對應(yīng)極大項記作Mi 極小項 解釋 記法極大項解釋記法pqr 000m0p q r000M0pqr 001m1p q r001 M1pqr 010m2

7、p q r010 M2pqr 011m3p q r011 M3pqr 100m4p q r100M4pqr 101m5p q r101M5pqr 110m6p q r110M6pqr 111m7p q r111M7p, q, r 形成的極小項與極大項 定理定理2.4 設(shè)mi與Mi是命題變項p1,p2,pn形成的極小項和極大項，則mi Mi ， Mi mi 主析取范式主析取范式(主合取范式主合取范式) 設(shè)由n個命題變項構(gòu)成的析取范式中所有的簡單合取式都是極小項，則稱該析取范式為主析取范式。 設(shè)由n個命題變項構(gòu)成的合取范式中所有的簡單析取式都是極大項，則稱該合取范式主合取范式。 例如：(pq) r

8、(pqr)(pr)(qr) (pqr) (pqr)(pqr) (pqr）(pqr) 例如：(pq) r(pr)(qr)(pqr) 定理定理2.5 任何命題公式都存在著與之等值的主析取范式和主合取范式,并且是唯一的。 如何求主析取范式（主合取范式）？ 首先求等價的析取范式（合取范式） 然后對非極小項（或者非極大項）進行擴展。A A (PP) （A P）（ A P ）A A (P P) （A P） （ A P ） 最后，求出某公式的主析取范式（主合取范式）后，將極小項（極大項）都用名稱寫出，并且按極小項（極大項）名稱的角標(biāo)由小到大順序排列。 求A=(rp)(q(pr)的主析取范式例例1：解：(rp

9、)(q(pr)(rp)(qp)(qr)(pr)(qp)(qr)(pr)(qq)(qp)(rr)(qr)(pp)(pqr)(pqr)(pqr)(pqr) m1 m3m6m7A A (P P) （A P） （ A P ）結(jié)論: 公式的所有成真賦值對應(yīng)主析取范式的所有極小項.(rp)(q(pr)的主合取范式(rp)(qp)(qr)(p r)(qp)(qr)(pr) q (pr) p (qr)(p q) (q r) (p p) (p r) (qr)(p q q) (q r q) (p r q) (p q r) (q r r) (p r r) (p q ) (q r) (p r q) (p q r) (

10、q r) (p r) (p q ) (q r) (p r q) (p q r) (p r)(p q r) (p q r) (p q r) (p q r)M4 M5 M0 M2結(jié)論: 公式的所有成假賦值對應(yīng)主合取范式的所有極大項.例例2：求A=(pq) r的主析取范式 (pq) r(pqr)(pr)(qr) (pqr) (pqr)(pqr) (pqr)(pqr) (pqr) (pqr)(pqr) (pqr) m4 m1 m3 m7求A=(pq) r的主合取范式(pq) r(pr)(qr)(pqr)(pq r) (p q r) ( p qr)(pqr)M0 M2 M6 M5如何求一個公式的主析取范

11、式？（1）利用等值轉(zhuǎn)化法（2）利用真值表（3）通過主合取范式求逆例例3：求命題公式pq的主析取范式和主合取范式。 方法1：真值表法pqp q001011100111pqm0 m1 m4( p q) ( p q) ( p q) 方法2：公式法pqp q p (q q) q (p p)( p q) ( p q) ( p q) M2 p qm0 m1 m4練習(xí): 求 ( p q) (q r) 的主析取范式公式法：( p q) (q r) (p q) (q r)(p q r) (q r)(p q r) (q r p ) (q r p ) (p q r) ( p q r)m3 m7練習(xí): 求 ( p q

12、) (q r) 的主析取范式真值表法：pqr p p qq r( p q) (q r)00010000011000010110001111111000100101010011001001110111( p q) (q r)m3 m7練習(xí): 求 ( p q) (q r) 的主析取范式求合取范式：( p q) (q r) (p q) (q r)(p q r) (p q r) (p q r) ( p q r) (p q r) (p q r) (p q r) (p q r) (p q r) ( p q r)M0 M1 M4 M5 M2 M6 因此主析取范式為：m3 m7歷史遺留問題: 我只給村里所有那

13、些不給自己理發(fā)的人理發(fā) 只要別人有困難,他就幫忙,除非困難解決. a:別人有困難, b: 他幫忙(1) a b作業(yè)作業(yè) 38 5題（題（1 、3） 注意總結(jié)規(guī)律注意總結(jié)規(guī)律 6題（題（2)作業(yè)問題: 整體較好,都交了. 個別書寫不認(rèn)真,應(yīng)付私事。 注意“” 的書寫P14 14題(10)除非天下大雨，否則他不乘車上班。 p:天下大雨 q:他乘車上班 q p 2和4是素數(shù)，這是不對的。 p: 2是素數(shù) q: 4是素數(shù) (p q)P38 4題(4) (p q) (pq) (p q) (p q)(p q) (pq)(p q) p (p q) q (p p) (q p) (p q) (q q)(q p)

14、 (p q)(p q) (p q)主析取范式的用途主析取范式的用途 求公式的成真與成假賦值 判斷公式的類型 判斷兩個命題公式是否等值 應(yīng)用主析取范式分析和解決實際問題例1: 求 (pq) (qp) 的成真賦值A(chǔ) m1m2ms(pq) (q p) (p q) (q p)(p q) (q p) (p q) (p q) (pq) m0 m2 m3即成真賦值為：0 0,1 0，1 1pq p pq q qp(pq) (qp)00 1011101 1100010 0111111 01011A m1m2ms(1)A為重言式當(dāng)且僅當(dāng)其主析取范式包含2n個極小項(2) A為矛盾式當(dāng)且僅當(dāng)其主析取范式包不含極小

15、項(3) A為可滿足式當(dāng)且僅當(dāng)其主析取范式包至少含一個極小項例2：判斷下列公式的類型 p (pq) p(pq) ( p q) (p q) (p q) (p q) (p q) (p q) m1 m0 m3 m2重言式 (2) (pq)r (p q) r (pqr)(pqr)(pqr)(pqr) (pqr)(pqr) m1 m0 m7 m3 m5pqrpq(pq)r0000100101010100111110010101111101011111 若公式A、B含有相同的命題變項， A與B等值的充要條件是它們有相同的主析取范式。例：問 (pq)r 與 p(qr) 是否等值(pq)r (pq) r (p

16、q) r(pqr)(pqr) (pqr)(pqr)(pqr)m5 m4 m7 m3 m1p(qr) p (qr) (pqr)(pqr) (pqr)(pqr) (pqr)(pqr) (pqr)(pqr) (pqr)(pqr) (pqr)(pqr)m3 m1 m2 m0 m5 m4 m7M6例例: 某科研所要從3名科研骨干A、B、C中挑選12名出國進修，由于工作需要，選派時要滿足以下條件：（1）若A去，則B同去；（2）若B去，則C不能去；（3）若C不去，則A或B可以去。問所里有哪些選派方案？解：設(shè) p: A去; q: B去; r: C去則選派方案應(yīng)滿足：(pr)(qr)(r(p q)(pr)(qr

17、)(r(p q) (pr) (qr)(r pq)(pqr)(pqr) (pqr)(pqr)( pqr)M4 M6 M3 M7 M0 m1m2m5因此,選派方案為（001，010，110）2.3 2.3 聯(lián)結(jié)詞的完備集 n元真值函數(shù)的定義元真值函數(shù)的定義 自變量：n個命題變項定義域：由0，1組成的長度為n的符號串全體。（2n） 值域：0，1思考：n個命題變項可構(gòu)成多少個不同的真值函數(shù)？ （22n） 每個真值函數(shù)對應(yīng)唯一一個主析取范式（主合取范式） 每個真值函數(shù)對應(yīng)無窮多個與之等值的命題公式每個命題公式對應(yīng)唯一一個真值函數(shù) 聯(lián)結(jié)詞完備聯(lián)結(jié)詞完備 設(shè)S是一個聯(lián)結(jié)詞集合，如果任何n(n1)元真值函數(shù)都

18、可以由 僅含S中的聯(lián)結(jié)詞構(gòu)成的公式表示，則稱S是聯(lián)結(jié)詞完備集。 定理定理2.6 S=,是聯(lián)結(jié)詞完備集 證：因為任何n(n1)元真值函數(shù)都與唯一的一個主析取范式等值，而在主析取范式中僅含聯(lián)結(jié)詞,，所以S=,是聯(lián)結(jié)詞完備集。 推論推論 以下聯(lián)結(jié)詞集都是完備集： (1) S1=, (2) S2=, (3) S3=, (4) S4=, (5) S5=, pq ( pq) (p q) 與非聯(lián)結(jié)詞與非聯(lián)結(jié)詞 根據(jù)需要，人們還可構(gòu)造形式上更為簡單的聯(lián)結(jié)詞完備集。例如，在計算機硬件設(shè)計中，用與非門或者或非門來設(shè)計邏輯線路時，就需要構(gòu)造新聯(lián)結(jié)詞完備集。 設(shè)p、q為兩個命題，復(fù)合命題“p與q的否定式”稱作p,q的

19、與非與非式式 記作pq。即 pq (pq）, 符號稱作與非聯(lián)結(jié)詞。 pq 表示或非式或非式 ，即pq (pq） 定理2.7 ，都是聯(lián)結(jié)詞完備集 小小 結(jié)結(jié)主要內(nèi)容： 等值式 基本的等值式 主析取范式與主合取范式 聯(lián)結(jié)詞完備 要求 熟練掌握等值演算 熟練掌握公式主析取范式（主合取范式）的求法 會用主析取范式解決一些問題一會將公式化為聯(lián)結(jié)詞完備集中的公式一、下列說法正確的是一、下列說法正確的是: A B 當(dāng)且僅當(dāng)AB是可滿足式 A B 當(dāng)且僅當(dāng)A和B有相同的主析取范式 若A為重言式,則A的主析取范式含有個 2n極小項 若A為矛盾式,則A的主析取范式為1 若A為矛盾式,則A的主合取范式為1 任何公式A都能等值的化為聯(lián)結(jié)詞, 中的公式 任何公式A都能等值的化為聯(lián)結(jié)詞集合, , 中的公式二、用等值演算法來判斷下列公式的類型、用等值演算法來判斷下列公式的類型(pq)r q(p q) r