第二章析取范式與合取范式PPT課件VIP

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

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

3、單析取式都是重言式。,定理2.3 （范式存在定理）任一命題公式都存在著與之等值的析取范式與合取范式。,研究范式的目的是將給定公式化成與之等值的析取范式或合取范式，進(jìn)而將公式化成與之等值的主析取范式或主合取范式。,思考：怎樣將公式轉(zhuǎn)化為范式？,.,5,例2.7 求下面公式的析取范式與合取范式：,(pq) r,.,6,將公式轉(zhuǎn)化為范式的步驟,消除聯(lián)結(jié)詞，,AB AB,縮小的作用范圍,利用分配率，轉(zhuǎn)化為析?。ê先。┓妒?.,7,例2.7 求下面公式的析取范式與合取范式：,(pq) r,(pqr)(pr)(qr),.,8,極小項(xiàng)與極大項(xiàng)的定義,極小項(xiàng)：在含有n個(gè)命題變項(xiàng)的簡(jiǎn)單合取式中，若每個(gè)命題變項(xiàng)和

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

5、的否定式出現(xiàn)在從左算起的第i位上（若命題變項(xiàng)無角標(biāo)，就按字典順序排列），稱這樣的簡(jiǎn)單析取式為極大項(xiàng)。,例：p r q; p p r; p q p; p q r; p q r; p q r,思考: (1) n個(gè)命題變項(xiàng)共可產(chǎn)生多少個(gè)不同的極大項(xiàng)? (2)每個(gè)極大項(xiàng)有多少個(gè)成假賦值?,2n,一個(gè),規(guī)定:成假賦值所對(duì)應(yīng)的二進(jìn)制數(shù)轉(zhuǎn)換為十進(jìn)制數(shù)i，就將所對(duì)應(yīng)極大項(xiàng)記作Mi,.,10,p, q, r 形成的極小項(xiàng)與極大項(xiàng),.,11,定理2.4 設(shè)mi與Mi是命題變項(xiàng)p1,p2,pn形成的極小項(xiàng)和極大項(xiàng)，則,mi Mi ， Mi mi,主析取范式(主合取范式),設(shè)由n個(gè)命題變項(xiàng)構(gòu)成的析取范式中所有的簡(jiǎn)單合

6、取式都是極小項(xiàng)，則稱該析取范式為主析取范式。,設(shè)由n個(gè)命題變項(xiàng)構(gòu)成的合取范式中所有的簡(jiǎn)單析取式都是極大項(xiàng)，則稱該合取范式主合取范式。,例如：(pq) r,(pqr)(pr)(qr),(pqr) (pqr)(pqr) (pqr）(pqr),例如：(pq) r,(pr)(qr)(pqr),.,12,定理2.5,任何命題公式都存在著與之等值的主析取范式和主合取范式,并且是唯一的。,如何求主析取范式（主合取范式）？ 首先求等價(jià)的析取范式（合取范式） 然后對(duì)非極小項(xiàng)（或者非極大項(xiàng)）進(jìn)行擴(kuò)展。,最后，求出某公式的主析取范式（主合取范式）后，將極小項(xiàng)（極大項(xiàng)）都用名稱寫出，并且按極小項(xiàng)（極大項(xiàng)）名稱的角標(biāo)由

7、小到大順序排列。,.,13,求A=(rp)(q(pr)的主析取范式,例1：,解：,(rp)(q(pr) (rp)(qp)(qr) (pr)(qp)(qr) (pr)(qq)(qp)(rr)(qr)(pp) (pqr)(pqr)(pqr)(pqr) m1 m3m6m7,結(jié)論: 公式的所有成真賦值對(duì)應(yīng)主析取范式的所有極小項(xiàng).,.,14,(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) (

8、p r r) (p q ) (q r) (p r q) (p q r) (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é)論: 公式的所有成假賦值對(duì)應(yīng)主合取范式的所有極大項(xiàng).,.,15,例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)

9、,(pq r) (p q r) ( p qr)(pqr),M0 M2 M6 M5,.,16,如何求一個(gè)公式的主析取范式？ （1）利用等值轉(zhuǎn)化法 （2）利用真值表 （3）通過主合取范式求逆,.,17,例3：,求命題公式pq的主析取范式和主合取范式。,方法1：真值表法,pq,m0 m1 m4,( p q) ( p q) ( p q),方法2：公式法,pq p q p (q q) q (p p) ( p q) ( p q) ( p q),m0 m1 m4,.,18,練習(xí): 求 ( p q) (q r) 的主析取范式,公式法：,( p q) (q r) (p q) (q r) (p q r) (q r

10、) (p q r) (q r p ) (q r p ) (p q r) ( p q r) m3 m7,.,19,練習(xí): 求 ( p q) (q r) 的主析取范式,真值表法：,( p q) (q r),m3 m7,.,20,練習(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,.,21,歷史遺留問題: 我

11、只給村里所有那些不給自己理發(fā)的人理發(fā) 只要?jiǎng)e人有困難,他就幫忙,除非困難解決. a:別人有困難, b: 他幫忙 a b,作業(yè) 38 5題（1 、3） 注意總結(jié)規(guī)律 6題（2),.,22,作業(yè)問題: 整體較好,都交了. 個(gè)別書寫不認(rèn)真,應(yīng)付私事。 注意“” 的書寫 P14 14題,(10)除非天下大雨，否則他不乘車上班。 p:天下大雨 q:他乘車上班 q p,2和4是素?cái)?shù)，這是不對(duì)的。 p: 2是素?cái)?shù) q: 4是素?cái)?shù) (p q),.,23,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) (

12、q q) (q p) (p q) (p q) (p q),.,24,主析取范式的用途,求公式的成真與成假賦值 判斷公式的類型 判斷兩個(gè)命題公式是否等值 應(yīng)用主析取范式分析和解決實(shí)際問題,.,25,例1: 求 (pq) (qp) 的成真賦值,(pq) (q p) (p q) (q p) (p q) (q p) (p q) (p q) (pq) m0 m2 m3,即成真賦值為：0 0,1 0，1 1,.,26,(1)A為重言式當(dāng)且僅當(dāng)其主析取范式包含2n個(gè)極小項(xiàng) (2) A為矛盾式當(dāng)且僅當(dāng)其主析取范式包不含極小項(xiàng) (3) A為可滿足式當(dāng)且僅當(dāng)其主析取范式包至少含一個(gè)極小項(xiàng),例2：判斷下列公式的類型

13、,p (pq) p(pq) ( p q) (p q) (p q) (p q) (p q) (p q),m1 m0 m3 m2,重言式,.,27,(2) (pq)r (p q) r (pqr)(pqr)(pqr)(pqr) (pqr)(pqr),m1 m0 m7 m3 m5,.,28,若公式A、B含有相同的命題變項(xiàng)， A與B等值的充要條件是它們有相同的主析取范式。,例：?jiǎn)?(pq)r 與 p(qr) 是否等值,(pq)r (pq) r (pq) r (pqr)(pqr) (pqr)(pqr)(pqr) m5 m4 m7 m3 m1,p(qr) p (qr) (pqr)(pqr) (pqr)(pq

14、r) (pqr)(pqr) (pqr)(pqr) (pqr)(pqr) (pqr)(pqr) m3 m1 m2 m0 m5 m4 m7,.,29,例: 某科研所要從3名科研骨干A、B、C中挑選12名出國(guó)進(jìn)修，由于工作需要，選派時(shí)要滿足以下條件： （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)(r(p q) (pr) (qr)(r pq) (pqr)(pqr) (pqr)(pqr)( pqr) M4 M6 M3 M7 M

15、0 m1m2m5,因此,選派方案為（001，010，110）,.,30,2.3 聯(lián)結(jié)詞的完備集,n元真值函數(shù)的定義,自變量：n個(gè)命題變項(xiàng) 定義域：由0，1組成的長(zhǎng)度為n的符號(hào)串全體。（2n） 值域：0，1 思考：n個(gè)命題變項(xiàng)可構(gòu)成多少個(gè)不同的真值函數(shù)？,（22n）,每個(gè)真值函數(shù)對(duì)應(yīng)唯一一個(gè)主析取范式（主合取范式） 每個(gè)真值函數(shù)對(duì)應(yīng)無窮多個(gè)與之等值的命題公式 每個(gè)命題公式對(duì)應(yīng)唯一一個(gè)真值函數(shù),.,31,聯(lián)結(jié)詞完備 設(shè)S是一個(gè)聯(lián)結(jié)詞集合，如果任何n(n1)元真值函數(shù)都可以由 僅含S中的聯(lián)結(jié)詞構(gòu)成的公式表示，則稱S是聯(lián)結(jié)詞完備集。,定理2.6 S=,是聯(lián)結(jié)詞完備集,證：因?yàn)槿魏蝞(n1)元真值函數(shù)都

16、與唯一的一個(gè)主析取范式等值，而在主析取范式中僅含聯(lián)結(jié)詞,，所以S=,是聯(lián)結(jié)詞完備集。,推論 以下聯(lián)結(jié)詞集都是完備集：(1) S1=, (2) S2=, (3) S3=, (4) S4=, (5) S5=,.,32,與非聯(lián)結(jié)詞,根據(jù)需要，人們還可構(gòu)造形式上更為簡(jiǎn)單的聯(lián)結(jié)詞完備集。例如，在計(jì)算機(jī)硬件設(shè)計(jì)中，用與非門或者或非門來設(shè)計(jì)邏輯線路時(shí)，就需要構(gòu)造新聯(lián)結(jié)詞完備集。,定理2.7 ，都是聯(lián)結(jié)詞完備集,.,33,小 結(jié) 主要內(nèi)容： 等值式 基本的等值式 主析取范式與主合取范式 聯(lián)結(jié)詞完備 要求 熟練掌握等值演算 熟練掌握公式主析取范式（主合取范式）的求法 會(huì)用主析取范式解決一些問題 會(huì)將公式化為聯(lián)結(jié)

17、詞完備集中的公式,.,34,一、下列說法正確的是: A B 當(dāng)且僅當(dāng)AB是可滿足式 A B 當(dāng)且僅當(dāng)A和B有相同的主析取范式 若A為重言式,則A的主析取范式含有個(gè) 2n極小項(xiàng) 若A為矛盾式,則A的主析取范式為1 若A為矛盾式,則A的主合取范式為1 任何公式A都能等值的化為聯(lián)結(jié)詞, 中的公式 任何公式A都能等值的化為聯(lián)結(jié)詞集合, , 中的公式,.,35,二、用等值演算法來判斷下列公式的類型,(pq)r q (p q) r q p0r 0 所有,該公式為矛盾式,三、用主析取范式法來判斷下列公式的類型,并求其成真賦值,(pq) ( p q) (pq) (p q ) (p q) p q (p q) (p q) (p q) (p q) ( p q) (p q) (p q) ( p q) m2 m3 m0 該公式為可滿足式,成真賦值為10,11,00,.,36,四、用主合取范式法來判斷下列公式的類型,并求其成假賦值,(pq) ( p q),(pq) (p q ) (p q) p q (p p q) ( qp q) p q M1 該公式為可滿足式, 成假賦值為01,.,37,五、已知公式A含3個(gè)命題變項(xiàng)p,q,r，并且它的成真賦值為001， 011,110，求A 的