1、1第第2章命題邏輯等值演算章命題邏輯等值演算等值式與基本的等值式等值式與基本的等值式等值演算與置換規(guī)則等值演算與置換規(guī)則析取范式與合取范式，主析取范式與主合取析取范式與合取范式，主析取范式與主合取范式范式聯(lián)結(jié)詞完備集聯(lián)結(jié)詞完備集可滿足性問題與消解法可滿足性問題與消解法22.1 等值式等值式q等值式：公式等值式：公式A，B的等價(jià)式的等價(jià)式AB為永為永真式真式v符號：符號：，也稱，也稱A邏輯恒等于邏輯恒等于B 32.1 等值式等值式pppp pFTFTTFTTq例子例子v 判斷判斷pp 42.1 等值式等值式pqppqp qpq p qFFTTTTFTTTTTTFFFFTTTFTTTq例子例子v

2、判斷判斷 pq p q 52.1 等值式等值式q否定律否定律v雙重否定律雙重否定律 ppv德摩根律德摩根律 (p q) p q (p q) p qq冪等律冪等律 p p p， p p pq交換律交換律 vp q q p vp q q p ；vp q q p62.1 等值式等值式q結(jié)合律結(jié)合律v(p q) r p (q r)v(p q) r p (q r)v(p q) r p (q r)q分配律分配律vp (q r) (p q) (p r)vp (q r) (p q) (p r)72.1 等值式等值式q吸收律吸收律vp (p q) pvp (p q) pq常元律常元律v零律: p T T， p

3、F Fv同一律: p F p， p T pv排中律: p p Tv矛盾律: p p F82.1 等值式等值式q蘊(yùn)含等值式蘊(yùn)含等值式 p q p qq等價(jià)等值式等價(jià)等值式 p q (p q) (q p)q假言易位假言易位 p q q pq等價(jià)否定等值式等價(jià)否定等值式 p q p qq歸繆律歸繆律 (p q ) (p q ) p 92.1 等值式等值式說明：說明： (1)16組等值模式都可以給出無窮多個(gè)同類型的具組等值模式都可以給出無窮多個(gè)同類型的具體的等值式。體的等值式。 (2)證明上述證明上述16組等值式的組等值式的代入實(shí)例代入實(shí)例方法可用真值方法可用真值表法，把表法，把改為改為所得的命題公式

4、為永真式，則所得的命題公式為永真式，則成立。成立。102.1 等值式等值式q置換規(guī)則置換規(guī)則：設(shè)：設(shè)(A)是含公式是含公式A的命題公式，的命題公式， (B)是用公式是用公式B置換了置換了(A)中所有中所有A后得到的后得到的命題公式，若命題公式，若B ，則，則(A) (B) 。q說明：說明：v等值演算過程中遵循的重要規(guī)則。等值演算過程中遵循的重要規(guī)則。v一個(gè)命題公式一個(gè)命題公式A，經(jīng)多次置換，所得到的新公式經(jīng)多次置換，所得到的新公式與原公式等價(jià)。與原公式等價(jià)。v稱由已知的等值式推演出另外一些等值式的過程稱由已知的等值式推演出另外一些等值式的過程為等值演算。為等值演算。112.1 等值式等值式1.

5、試證：試證：p(qr) (p q)r證明：證明：a. p(qr)p(qr) b. p(qr)pqr c.pqr(p q) rd. (p q) r (p q)r122.1 等值式等值式2 試證：試證：(p q)(p(p q)(pq)左邊左邊 (p q) (p(p q) (p q) (p(p q) (p q) (p q) (p p q) (q p q) (p q)132.1 等值式等值式3. 證明：證明：(pq) (p (qr)(p q)(p r)為一為一永真式永真式證明：原式證明：原式 (pq) (p(q r)(pq)(pr) (pq) (pq) (pr)(pq) (pr) (pq) (pr)(

6、pq) (pr)P19 例例2.3 從左面演算從左面演算142.2 析取范式和合取范式析取范式和合取范式 q文字文字(literal): 命題變元及其否定命題變元及其否定q簡單析取式簡單析取式:僅由有限個(gè)文字構(gòu)成的析取式僅由有限個(gè)文字構(gòu)成的析取式q簡單合取式簡單合取式:僅由有限個(gè)文字構(gòu)成的合取式僅由有限個(gè)文字構(gòu)成的合取式q例：設(shè)例：設(shè)p、q為二個(gè)命題變元為二個(gè)命題變元vp，q，pp，qq，pq， q p，pq，p q 稱為簡單析取式稱為簡單析取式vq，pp，qq， pq， q p，pq，p q 稱為簡單合取式。稱為簡單合取式。152.2 析取范式和合取范式析取范式和合取范式q定理定理: 1)一

7、個(gè)簡單析取式是永真式當(dāng)且僅當(dāng)它同時(shí)含一個(gè)簡單析取式是永真式當(dāng)且僅當(dāng)它同時(shí)含某個(gè)命題變元及它的否定式某個(gè)命題變元及它的否定式證明？證明？2)一個(gè)簡單合取式是永假式當(dāng)且僅當(dāng)它同時(shí)含一個(gè)簡單合取式是永假式當(dāng)且僅當(dāng)它同時(shí)含某個(gè)命題變元及它的否定式某個(gè)命題變元及它的否定式證明？證明？162.2 析取范式和合取范式析取范式和合取范式q析取范式析取范式:由有限個(gè)簡單合取式構(gòu)成的析取式由有限個(gè)簡單合取式構(gòu)成的析取式vA1 An, Ai 為合取式為合取式v( p q) (p r)q合取范式合取范式:由有限個(gè)簡單析取式構(gòu)成的合取式由有限個(gè)簡單析取式構(gòu)成的合取式vA1 An, Ai 為合取式為合取式v( p q)

8、(p r)q析取范式與合取范式統(tǒng)稱為析取范式與合取范式統(tǒng)稱為范式范式17182.2 析取范式和合取范式析取范式和合取范式q定理：定理：v設(shè)設(shè)Ai 為簡單合取式，析取范式為簡單合取式，析取范式A1 An F 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) Ai F，任意，任意Aiv設(shè)設(shè)Ai 為簡單析取式，為簡單析取式， 合取范式合取范式A1 An T 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) Ai T，任意，任意Ai192.2 析取范式和合取范式析取范式和合取范式q范式存在定理范式存在定理: 任意命題公式都存在著與之等值任意命題公式都存在著與之等值的析取范式與合取范式的析取范式與合取范式方法：方法： 步驟一：步驟一：消去消去“”、“”聯(lián)結(jié)詞聯(lián)結(jié)詞步

9、驟二：步驟二：消去雙重否定符，內(nèi)移否定符消去雙重否定符，內(nèi)移否定符步驟三：步驟三：使用分配律使用分配律202.2 析取范式和合取范式q范式存在定理范式存在定理: 任意命題公式都存在著與之等值任意命題公式都存在著與之等值的析取范式與合取范式的析取范式與合取范式方法：方法： 步驟一：消去步驟一：消去“”、“”聯(lián)結(jié)詞聯(lián)結(jié)詞步驟二：消去雙重否定符，內(nèi)移否定符步驟二：消去雙重否定符，內(nèi)移否定符步驟三：使用分配律步驟三：使用分配律212.2 析取范式和合取范式q步驟一：利用等值公式：化去步驟一：利用等值公式：化去“”、“”聯(lián)結(jié)聯(lián)結(jié)詞詞v p q p qv p q (p q) (q p)222.2 析取范式

10、和合取范式q范式存在定理范式存在定理: 任意命題公式都存在著與之等值任意命題公式都存在著與之等值的析取范式與合取范式的析取范式與合取范式方法：方法： 步驟一：消去步驟一：消去“”、“”聯(lián)結(jié)詞聯(lián)結(jié)詞步驟二：消去雙重否定符，內(nèi)移否定符步驟二：消去雙重否定符，內(nèi)移否定符步驟三：使用分配律步驟三：使用分配律232.2 析取范式和合取范式q消去雙重否定符，內(nèi)移否定符消去雙重否定符，內(nèi)移否定符v德摩根律德摩根律 (p q) p q (p q) p qv雙重否定律雙重否定律 p p242.2 析取范式和合取范式q范式存在定理范式存在定理: 任意命題公式都存在著與之等值任意命題公式都存在著與之等值的析取范式與

11、合取范式的析取范式與合取范式方法：方法： 步驟一：消去步驟一：消去“”、“”聯(lián)結(jié)詞聯(lián)結(jié)詞步驟二：消去雙重否定符，內(nèi)移否定符步驟二：消去雙重否定符，內(nèi)移否定符步驟三：使用分配律步驟三：使用分配律252.2 析取范式和合取范式q利用利用“ ”對對“ ”的分配，將公式化成為析取范式的分配，將公式化成為析取范式vp (q r) (p q) (p r)262.2 析取范式和合取范式q 例：求例：求(p q) (p q)的析取范式的析取范式 1. 化去化去 ( p q) (p q)2. “ ”對對“ ”分配，化為析取范式分配，化為析取范式 ( p p q) (q p q) 3. 最簡析取范式最簡析取范式

12、p q 那么如何獲得合取范式呢？那么如何獲得合取范式呢？272.2 析取范式和合取范式q例：求例：求(p q) r) p的合取范式和析取范式的合取范式和析取范式 (一一) 求析取范式求析取范式原式原式 ( (p q) r) p ( (p q) r) p ( (p q) r) p (p q) r) p (p r) (q r) p p (p r) (q r) p (q r)282.2 析取范式和合取范式(二二)求合取范式求合取范式原式原式 ( (p q) r) p ( (p q) r) p ( (p q) r) p (p q) r) p (p p q) (p r) (p q) (p r)292.2

13、 析取范式和合取范式討論：討論：q一個(gè)命題公式的析取范式不是唯一的，但同一一個(gè)命題公式的析取范式不是唯一的，但同一命題公式的析取范式一定是等值的命題公式的析取范式一定是等值的q練習(xí)練習(xí)vP38 5(2) 6(2)302.2 析取范式和合取范式q極小項(xiàng)極小項(xiàng)(極大項(xiàng)極大項(xiàng)):含有含有n個(gè)命題變元的簡單合取式個(gè)命題變元的簡單合取式 (簡單析取式簡單析取式)并滿足并滿足v每個(gè)命題變元和它的否定式不同時(shí)出現(xiàn)，而二者之一每個(gè)命題變元和它的否定式不同時(shí)出現(xiàn)，而二者之一必出現(xiàn)且僅出現(xiàn)一次必出現(xiàn)且僅出現(xiàn)一次v第第i個(gè)命題變元或它的否定式出現(xiàn)在從左算起的第個(gè)命題變元或它的否定式出現(xiàn)在從左算起的第i位上位上(若無

14、角標(biāo)則按字典順序排列若無角標(biāo)則按字典順序排列)q若有若有個(gè)命題變元，則有個(gè)命題變元，則有2n個(gè)極小項(xiàng)（極大項(xiàng)）個(gè)極小項(xiàng)（極大項(xiàng)）312.2 析取范式和合取范式q極小項(xiàng)的編碼極小項(xiàng)的編碼:對應(yīng)成真賦值對應(yīng)成真賦值三個(gè)變元三個(gè)變元p、q、r可構(gòu)造可構(gòu)造8個(gè)極小項(xiàng)：個(gè)極小項(xiàng)： pqr FFF 0 記作記作 m0 pqr FFT 1 記作記作 m1 pqr FTF 2 記作記作 m2 pqr FTT 3 記作記作 m3 pqr TFF 4 記作記作 m4 pqr TFT 5 記作記作 m5 pqr TTF 6 記作記作 m6 pqr TTT 7 記作記作 m7322.2 析取范式和合取范式q極大項(xiàng)的編

15、碼極大項(xiàng)的編碼:對應(yīng)成假賦值對應(yīng)成假賦值如三個(gè)變元如三個(gè)變元 p、q、r，其記法如下：其記法如下：pqr F F F 0 記作記作 M0p q r F F T 1 記作記作 M1p qr F T F 2 記作記作 M2p q r F T T 3 記作記作 M3 p q r T T T 7 記作記作 M7332.2 析取范式和合取范式q定理定理:設(shè)設(shè)mi和和Mi是命題變元是命題變元p1, p2 pn形成的形成的極小項(xiàng)和極大項(xiàng)，則：極小項(xiàng)和極大項(xiàng)，則：(1) mi mj F, (ij)(2) Mi Mj T, (ij)(3) mi T, (i =0,1,2n-1) (4) Mi F, (i =0,

16、1,2n-1) (5) mi Mi； Mi mi342.2 析取范式和合取范式q 主析取范式主析取范式(主合取范式主合取范式)：由：由n個(gè)命題變元構(gòu)成個(gè)命題變元構(gòu)成的的析取范式析取范式(合取范式合取范式)中中所有的簡單合取式所有的簡單合取式(簡單簡單析取式析取式)都是極小項(xiàng)都是極小項(xiàng)(極大項(xiàng)極大項(xiàng))q定理定理: 任何命題公式都存在著與其等值的主析取任何命題公式都存在著與其等值的主析取范式和主合取范式，并且是唯一的。范式和主合取范式，并且是唯一的。352.2 析取范式和合取范式q證法一證法一v在真值表中，使命題公式的真值為在真值表中，使命題公式的真值為T的指派所對應(yīng)的的指派所對應(yīng)的極小項(xiàng)的析取，

17、即為此公式的主析取范式極小項(xiàng)的析取，即為此公式的主析取范式證：證：給定一個(gè)命題公式給定一個(gè)命題公式A，使其為使其為T的真值指派所的真值指派所對應(yīng)的極小項(xiàng)為對應(yīng)的極小項(xiàng)為m1, m2, mk,這些極小項(xiàng)的這些極小項(xiàng)的析取記為析取記為B，為此要證為此要證AB，即要證即要證A與與B在相在相同的指派下具有相同的真值。同的指派下具有相同的真值。362.2 析取范式和合取范式首先對于使首先對于使A為為T的指派顯然使的指派顯然使B為為T對于使對于使A為為F的指派，它對應(yīng)的極小項(xiàng)的指派，它對應(yīng)的極小項(xiàng)(設(shè)為設(shè)為mj )不不包含在包含在m1, m2, mk 中。所以中。所以 mj為使為使B為為F的指派的指派所以

18、所以A B 得證得證372.2 析取范式和合取范式q一個(gè)公式的主析取范式即為令此公式的真值為一個(gè)公式的主析取范式即為令此公式的真值為T的指派所對應(yīng)的極小項(xiàng)的析取。的指派所對應(yīng)的極小項(xiàng)的析取。q一個(gè)命題公式的真值表是唯一的，因此一個(gè)命一個(gè)命題公式的真值表是唯一的，因此一個(gè)命題公式的主析取范式也是唯一的題公式的主析取范式也是唯一的382.2 析取范式和合取范式析取范式和合取范式p q r m1 m3 m5 m6 m7pqrpqrFFFFFFTTFTFFFTTTTFFFTFTTTTFTTTTTp q r的真值表的真值表392.2 析取范式和合取范式析取范式和合取范式q證法二：構(gòu)造法證法二：構(gòu)造法v

19、用等值演算方法求命題公式主析取范式的方法用等值演算方法求命題公式主析取范式的方法 將命題公式化歸為與其等值的析取范式將命題公式化歸為與其等值的析取范式 添變元添變元: 消去重復(fù)項(xiàng)消去重復(fù)項(xiàng)Ai (pj pj) (Ai pj) (Ai pj) 402.2 析取范式和合取范式q例：求例：求(p(pq)q的主析取范式的主析取范式解：解：原式原式(pp)(pq)q v-(1)化為析取范式化為析取范式 (pq)q v-(2)化簡化簡(pq)(q(pp)(pq)(pq)(pq) v-(3)添項(xiàng)添項(xiàng)(pq)(pq) v-(4)合并相同最小項(xiàng)合并相同最小項(xiàng)412.2 析取范式和合取范式q主析取范式的用途討論：

20、主析取范式的用途討論： 求公式的成真與成假賦值求公式的成真與成假賦值 判斷公式類型判斷公式類型 判斷兩個(gè)命題公式是否等值判斷兩個(gè)命題公式是否等值 應(yīng)用主析取范式分析和解決實(shí)際問題應(yīng)用主析取范式分析和解決實(shí)際問題422.2 析取范式和合取范式q例：某研究所要從例：某研究所要從3名科研骨干名科研骨干A，B，C中挑中挑選選12名出國進(jìn)修，由于工作需要，選派時(shí)名出國進(jìn)修，由于工作需要，選派時(shí)要滿足以下條件：要滿足以下條件： 若若A去，則去，則C同去。同去。 若若B去，則去，則C不能去。不能去。 若若C不去，則不去，則A或或B可以去。可以去。解解:設(shè)設(shè)p：派：派A去；去；q：派：派B去；去；r：派：派C

21、去。去。則則(pr) (qr)(r (pq) 432.2 析取范式和合取范式經(jīng)演算可得：經(jīng)演算可得：(pr) (qr)(r (pq) m1m2m5可知選派方案有三種：可知選派方案有三種： C去，去，A，B都不去。都不去。 B去，去，A，C不去。不去。 A，C去，去，B不去。不去。442.2 析取范式和合取范式q主合取范式主合取范式v任何一個(gè)命題公式都可求得它的主合取范式任何一個(gè)命題公式都可求得它的主合取范式v一個(gè)命題公式的主合取范式是唯一的一個(gè)命題公式的主合取范式是唯一的v在真值表中，令命題公式的真值為在真值表中，令命題公式的真值為“F”的的指派就對應(yīng)其主合取范式的一個(gè)極大項(xiàng)指派就對應(yīng)其主合取

22、范式的一個(gè)極大項(xiàng)452.2 析取范式和合取范式q 例例:求求p(pq)q的主合取范式的主合取范式 解：原式解：原式 p( pq)q(p p)(pq)q(pq)q(pq) q(pq)(q(p p) (pq)( pq) M0 M2 pq上式上式FFFFTTTFFTTT462.2 析取范式和合取范式 主合取范式與主析取范式轉(zhuǎn)換主合取范式與主析取范式轉(zhuǎn)換q公式公式: A = mi1 mi2 misv A = mj1 mj2 mjt ，t=2n-sv A A (mj1 mj2 mjt ) mj1 mj2 mjt Mj1 Mj2 Mjt 472.2 析取范式和合取范式q討論：具有討論：具有n個(gè)變元的命題公

23、式有多少個(gè)不同的主個(gè)變元的命題公式有多少個(gè)不同的主析取范式？析取范式？q對于含有個(gè)變元的命題公式，必定可寫出對于含有個(gè)變元的命題公式，必定可寫出22n個(gè)個(gè)主析取范式主析取范式(包括包括F)。q同理，含有個(gè)變元的命題公式，也可寫出同理，含有個(gè)變元的命題公式，也可寫出22n個(gè)個(gè)主合取范式主合取范式(包括包括T)。練習(xí)練習(xí)8 (3), 11(3)48492.3 聯(lián)結(jié)詞的完備集性質(zhì)：pq(pq)(qp)(pq)(pq)pq (pq) pqqp(可交換的)(pq)rp(qr)(可結(jié)合的)pqpqFFFFTTTFTTTFn排斥或排斥或(異或異或) 符號：符號：“”( )502.3 聯(lián)結(jié)詞的完備集“與非與非

24、”聯(lián)結(jié)詞：聯(lián)結(jié)詞：符號符號“”(pq)讀作：讀作：“p與與q的的否定否定”q(pq)(pq)pqpqFFTFTTTFTTTF512.3聯(lián)結(jié)詞的完備集q“或非或非”聯(lián)結(jié)詞：聯(lián)結(jié)詞：(a)符號：符號：“” (b)(pq) (pq)pqpqFFTFTFTFFTTF522.3 聯(lián)結(jié)詞的完備集聯(lián)結(jié)詞的完備集q真值函數(shù)真值函數(shù)F: 0,1n 0,1q聯(lián)結(jié)詞完備集聯(lián)結(jié)詞完備集S: vS是一個(gè)聯(lián)接詞集合是一個(gè)聯(lián)接詞集合v每一個(gè)真值函數(shù)都可以由僅含每一個(gè)真值函數(shù)都可以由僅含S中的聯(lián)接詞構(gòu)成中的聯(lián)接詞構(gòu)成的公式表示的公式表示q定理定理: S = ， ， 是聯(lián)接詞完備集是聯(lián)接詞完備集 證明：證明：任何一個(gè)任何一個(gè)n

25、（n 1）元真值函數(shù)都與唯一）元真值函數(shù)都與唯一的一個(gè)主析取范式等值，而主析取范式僅含的一個(gè)主析取范式等值，而主析取范式僅含 ， ， 532.3 聯(lián)結(jié)詞的完備集聯(lián)結(jié)詞的完備集q推論推論: S = ， 是聯(lián)接詞完備集是聯(lián)接詞完備集 證明：證明：p q (p q) ( p q) 542.3 聯(lián)結(jié)詞的完備集聯(lián)結(jié)詞的完備集q定理定理: ， 是聯(lián)接詞完備集是聯(lián)接詞完備集證明：證明：首先，首先， p (p p) pp其次，其次，p q (p q) (pq) (pq) (pq) (pq) (p q)552.4 消解法消解法q可滿足性問題：可滿足性問題：v用于證明用于證明A是否永真是否永真v用于驗(yàn)證邏輯蘊(yùn)涵用

26、于驗(yàn)證邏輯蘊(yùn)涵 A1 Ak B 永真永真 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) A1 Ak B 永假永假q解決方法解決方法v真值表真值表v主析取范式主析取范式v主合取范式主合取范式u缺點(diǎn)：計(jì)算量大缺點(diǎn)：計(jì)算量大引入消解法！引入消解法！56q文字文字l的補(bǔ)：的補(bǔ)： vlc= p，如果，如果l =pvlc=p，如果，如果l = pq消解式：消解式： C1 , C2是簡單析取式，是簡單析取式，C1= C1 l, C2= C2 lcvRes(C1,C2)= C1 C2q定理定理：C1 C2 Res(C1,C2)v消解式是原公式的邏輯推論消解式是原公式的邏輯推論v討論！是簡單析取式討論！是簡單析取式2.4 消解法消解法57

27、q定理定理： C1 C2和和Res(C1,C2)可滿足性相同可滿足性相同 證明：證明：C1= C1 l, C2= C2 lc 如果如果C1 C2可滿足，則存在可滿足，則存在v，v(Ci)=T 假設(shè)假設(shè)v(l)=T，則，則v(C2)=T。 如果如果Res(C1,C2)可滿足，則存在可滿足，則存在v 存在存在l在在C1使得使得v(l)=T, v可以擴(kuò)展為可以擴(kuò)展為 v(p)=F 如果如果p=l v(p)=T 如果如果p=lc v對對C1 C2賦值為賦值為Tv(C1 C2)=T2.4 消解法消解法58qC1 C2和和Res(C1,C2)不等值不等值q例：例：C1=p q r, C2=prvRes(C

28、1,C2) = p qvv=FTT滿足滿足Res(C1,C2) 但不滿足但不滿足C1 C22.4 消解法消解法59q消解推導(dǎo)：消解推導(dǎo)：S=C1 Cn和和Cv符號：符號：C1,Cn Cv存在公式序列存在公式序列A1, A2,Ak，對每個(gè)，對每個(gè)i(i=1,k), Ai是某個(gè)是某個(gè)Cj或者或者 Ai是有序列中前面的公式應(yīng)用消解得到是有序列中前面的公式應(yīng)用消解得到 Ak=Cv稱稱A1,Ak是由是由S到到C的推導(dǎo)的推導(dǎo)v如果如果C 為空子句為空子句，則稱此序列是，則稱此序列是S的一個(gè)否證的一個(gè)否證2.4 消解法消解法60：如果合取范式如果合取范式S有否證，則有否證，則S是不是不可滿足可滿足 證明：證

29、明：每次使用消解，都保持可滿足性。如果每次使用消解，都保持可滿足性。如果消解結(jié)果不可滿足，則消解結(jié)果不可滿足，則S必不可滿足。必不可滿足。：如果合取范式如果合取范式S是不可滿足，則是不可滿足，則S有否證有否證 2.4 消解法消解法61q消解算法（分層飽和法）消解算法（分層飽和法）輸入：合式公式輸入：合式公式A輸出：輸出：yes (A可滿足可滿足)，no (A不可滿足不可滿足)2.4 消解法消解法1. 求求A的合取范式的合取范式S.2. 令令i=1, S(0)=S.3. 若若S(i)包含空子句，則包含空子句，則S不可滿足，算法終止不可滿足，算法終止. 4. i=i+1.5. 構(gòu)造構(gòu)造S(i)=R

30、es(C1,C2) | C1 (S(0) S(i-1)且且C2 S(i-1).6. 若若S(i) S(0) S(i-1)則則S是可滿足的，算法終止是可滿足的，算法終止.7. 轉(zhuǎn)轉(zhuǎn)362q書書P37頁例題頁例題2.14A=( p q) (p q) ( q)v循環(huán)循環(huán)1 開始，開始， S(0) = S(1) = p q, p q, q S(2) =通過對通過對S(0) 、S(1) ， S(1) 進(jìn)行消解得到進(jìn)行消解得到 S(2) = q, p, pv循環(huán)循環(huán)2開始，開始， S(0) = p q, p q, q S(1)=q, p, p S(2) =v得到得到，算法終止，算法終止2.4 消解法消解法

31、63q例例2：S= p q, p q, pq, pq2.4 消解法消解法 p qp q q p q q p p q q 6465：如果合取范式如果合取范式S含有文字含有文字l，S為為vS先刪除包含先刪除包含l的簡單析取式的簡單析取式v再刪除剩下的簡單析取式中再刪除剩下的簡單析取式中l(wèi)c則則S和和S可滿足性相同可滿足性相同 證明：證明： 如果如果v為滿足為滿足S的賦值，的賦值，S含有文字含有文字l，v(l)=T，對任意，對任意S中中C，必有，必有v(S)=T。 如果如果v為滿足為滿足S的賦值，則可以擴(kuò)展為滿足的賦值，則可以擴(kuò)展為滿足S的的賦值（驗(yàn)證）！賦值（驗(yàn)證）！ 2.4 消解法消解法66：如

32、果合取范式如果合取范式S是不可滿足，則是不可滿足，則S有否證有否證 證明：證明：對對S中所含命題個(gè)數(shù)中所含命題個(gè)數(shù)k歸納證明歸納證明 第一步驟第一步驟 k=1: S中有中有p, p 第二步驟第二步驟 假設(shè)假設(shè)kn時(shí)定理成立，證明時(shí)定理成立，證明k=n時(shí)定時(shí)定理成立理成立 1. 對對S p應(yīng)用引理應(yīng)用引理1，得到等滿足性的，得到等滿足性的S 2. 對對S p應(yīng)用引理應(yīng)用引理1，得到等滿足性的，得到等滿足性的S 由假設(shè)，存在由假設(shè)，存在S的否證的否證C1,Ci，S的否證的否證 D1,Dj2.4 消解法消解法67q 證明（繼續(xù)）：證明（繼續(xù)）： 1. 對對S p應(yīng)用引理應(yīng)用引理1，得到等滿足性的，得

33、到等滿足性的S 2. 對對S p應(yīng)用引理應(yīng)用引理1，得到等滿足性的，得到等滿足性的S 由假設(shè)，存在由假設(shè)，存在S的否證的否證C1,Ci，S的否證的否證 D1,Dj 情況情況1：Ct (i t 1)或或Ds (j t 1)都是由不含都是由不含p的簡單的簡單析取式消解得到，析取式消解得到， C1,Ci或或D1,Dj為為S的否證的否證 情況情況2： Ct (或或Ds)不滿足情況不滿足情況1條件，則擴(kuò)展條件，則擴(kuò)展Ct (或或Ds)得到得到Ct= Ct p (或或Ds = Ds p ) ，則，則Ct (或或Ds )屬于屬于S ，且，且 Ci= p， Dj=p，消解得到，消解得到空子句空子句2.4 消解

34、法消解法68第二章第二章 習(xí)題課習(xí)題課q主要內(nèi)容主要內(nèi)容l等值式與等值演算等值式與等值演算l基本等值式（基本等值式（1616組，組，2424個(gè)公式）個(gè)公式）l主析取范式與主合取范式主析取范式與主合取范式l聯(lián)結(jié)詞完備集聯(lián)結(jié)詞完備集l消解法消解法69基本要求基本要求l 深刻理解等值式的概念深刻理解等值式的概念l 牢記基本等值式的名稱及它們的內(nèi)容牢記基本等值式的名稱及它們的內(nèi)容l 熟練地應(yīng)用基本等值式及置換規(guī)則進(jìn)行等值演算熟練地應(yīng)用基本等值式及置換規(guī)則進(jìn)行等值演算l 理解文字、簡單析取式、簡單合取式、析取范式、合取范式的概理解文字、簡單析取式、簡單合取式、析取范式、合取范式的概念念l 深刻理解極小項(xiàng)

35、、極大項(xiàng)的概念、名稱及下角標(biāo)與成真、成假賦深刻理解極小項(xiàng)、極大項(xiàng)的概念、名稱及下角標(biāo)與成真、成假賦值的關(guān)系，并理解簡單析取式與極小項(xiàng)的關(guān)系值的關(guān)系，并理解簡單析取式與極小項(xiàng)的關(guān)系l 熟練掌握求主范式的方法（等值演算、真值表等）熟練掌握求主范式的方法（等值演算、真值表等）l 會(huì)用主范式求公式的成真賦值、成假賦值、判斷公式的類型、判會(huì)用主范式求公式的成真賦值、成假賦值、判斷公式的類型、判斷兩個(gè)公式是否等值斷兩個(gè)公式是否等值l 會(huì)將公式等值地化成指定聯(lián)結(jié)詞完備集中的公式會(huì)將公式等值地化成指定聯(lián)結(jié)詞完備集中的公式l 會(huì)用命題邏輯的概念及運(yùn)算解決簡單的應(yīng)用問題會(huì)用命題邏輯的概念及運(yùn)算解決簡單的應(yīng)用問題l

36、 掌握消解規(guī)則及其性質(zhì)掌握消解規(guī)則及其性質(zhì)l 會(huì)用消解算法判斷公式的可滿足性會(huì)用消解算法判斷公式的可滿足性70練習(xí)練習(xí)1:概念概念1. 設(shè)設(shè)A與與B為含為含n個(gè)命題變項(xiàng)的公式，判斷下列命題是個(gè)命題變項(xiàng)的公式，判斷下列命題是否為真？否為真？(1) AB當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)A與與B有相同的主析取范式有相同的主析取范式(2) 若若A為重言式，則為重言式，則A的主合取范式為的主合取范式為0(3) 若若A為矛盾式，則為矛盾式，則A的主析取范式為的主析取范式為1(4) 任何公式都能等值地化成任何公式都能等值地化成 , 中的公式中的公式(5) 任何公式都能等值地化成任何公式都能等值地化成 , , 中的公式中的公

37、式說明說明:(2) 重言式的主合取范式不含任何極大項(xiàng)，為重言式的主合取范式不含任何極大項(xiàng)，為1. (3) 矛盾式的主析取范式不含任何極小項(xiàng)矛盾式的主析取范式不含任何極小項(xiàng), 為為0. (4) , 不是完備集，如矛盾式不能寫成不是完備集，如矛盾式不能寫成 , 中的公式中的公式. (5) , 是完備集是完備集. 真真假假假假假假真真71練習(xí)練習(xí)2: 判斷公式類型判斷公式類型解解 用等值演算法求主范式用等值演算法求主范式 (pq)( qp) ( p q) (qp) (pq) (qp) (pq) ( p q) (p q) ( pq) m2 m1 m3 m0 m0 m1 m2 m3 主析取范式主析取范式

38、 1 主合取范式主合取范式2. 判斷下列公式的類型判斷下列公式的類型: (1) (pq)( qp)重言式重言式72練習(xí)題練習(xí)題2(續(xù)續(xù))解解 用等值演算法求公式的主范式用等值演算法求公式的主范式 (pq) q ( p q) q pq q 0 主析取范式主析取范式 M0 M1 M2 M3 主合取范式主合取范式(2) (pq) q矛盾式矛盾式73解解 用等值演算法求公式的主范式用等值演算法求公式的主范式 (pq)p ( p q)p p ( pq) ( p q) m0 m1 主析取范式主析取范式 M2 M3 主合取范式主合取范式(3) (pq)p練習(xí)練習(xí)2(續(xù)續(xù))非重言式的可滿足式非重言式的可滿足式

39、74練習(xí)練習(xí)3：求公式的主范式求公式的主范式3已知命題公式已知命題公式A中含中含3個(gè)命題變項(xiàng)個(gè)命題變項(xiàng)p, q, r，并知道它的成真，并知道它的成真賦值為賦值為001, 010, 111, 求求A的主析取范式和主合取范式，及的主析取范式和主合取范式，及A對應(yīng)的真值函數(shù)對應(yīng)的真值函數(shù).解解 A的主析取范式為的主析取范式為m1 m2 m7A的主合取范式為的主合取范式為M0 M3 M4 M5 M6 p q r F p q r F0 0 0 0 1 0 0 00 0 1 1 1 0 1 00 1 0 1 1 1 0 00 1 1 0 1 1 1 175練習(xí)練習(xí)4：聯(lián)結(jié)詞完備集聯(lián)結(jié)詞完備集4將將A =

40、(pq) r改寫成下述各聯(lián)結(jié)詞集中的公改寫成下述各聯(lián)結(jié)詞集中的公式式: (1) , , (2) , (3) , (4) , (5) (6) 解解 (1) (pq) r ( pq) r (2) (pq) r (p q) r (3) (pq) r ( pq) r ( ( pq)r)76練習(xí)練習(xí)4 解答解答 (4) (pq) r ( (pq)r) (pq)r) (5) (pq) r (p q) r (p q) r (p q) r) (p q) r) (p q) r) (6) (pq) r ( pq) r ( ( pq)r) ( pq)r (p p) (q q) (r r) 說明：答案不惟一說明：答案不惟一77練習(xí)練習(xí)5：應(yīng)用題：應(yīng)用題5. 某公司要從趙、錢、孫、李、周五名新畢業(yè)的大某公司要從趙、錢、孫、李、周五名新畢業(yè)的大學(xué)生中選學(xué)生中選派一些人出國學(xué)習(xí)派一些人出國學(xué)習(xí). 選派必須滿足以下條件：選派必須滿足以下條件：(1) 若趙去，錢也去若趙去，錢也去.(2) 李、周兩人中至少有一人去李、周兩人中至少有一人去(3) 錢、孫兩人中去且僅去一人錢、孫兩人中去且僅去一人.(4) 孫、李兩人同去或同不去孫、李兩人同去或同不去.(5) 若周去，則趙、錢也去若周去，則趙、錢也去. 用等值演算法分析該公司如何選派他們出國？用等值演算法分析該公司如何選派他們出國？