等值式東南大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院課件

1、1第第2章命題邏輯等值演算章命題邏輯等值演算等值式與基本的等值式等值式與基本的等值式等值演算與置換規(guī)則等值演算與置換規(guī)則析取范式與合取范式，主析取范式與主合取析取范式與合取范式，主析取范式與主合取范式范式聯(lián)結(jié)詞完備集聯(lián)結(jié)詞完備集可滿(mǎn)足性問(wèn)題與消解法可滿(mǎn)足性問(wèn)題與消解法22.1 等值式等值式q等值式：公式等值式：公式a，b的等價(jià)式的等價(jià)式ab為永為永真式真式v符號(hào)：符號(hào)：，也稱(chēng)，也稱(chēng)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 等值式等值式說(shuō)明：說(shuō)明： (1)16組等值模式都可以給出無(wú)窮多個(gè)同類(lèi)型的具組等值模式都可以給出無(wú)窮多個(gè)同類(lèi)型的具體的等值式。體的等值式。 (2)證明上述證明上述16組等值式的組等值式的代入實(shí)例代入實(shí)例方法可用真值方法可用真值表法，把表法，把改為改為所得的命題公式

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

5、試證：試證：p(qr) (p q)r證明：證明：q p(qr)p(qr) q p(qr)pqr q pqr(p q) ra. (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)(pq

6、) (pr)p19 例例2.3 從左面演算從左面演算142.2 析取范式和合取范式析取范式和合取范式 q文字文字(literal): 命題變?cè)捌浞穸}變?cè)捌浞穸╭簡(jiǎn)單析取式簡(jiǎn)單析取式:僅由有限個(gè)文字構(gòu)成的析取式僅由有限個(gè)文字構(gòu)成的析取式q簡(jiǎn)單合取式簡(jiǎn)單合取式:僅由有限個(gè)文字構(gòu)成的合取式僅由有限個(gè)文字構(gòu)成的合取式q例：設(shè)例：設(shè)p、q為二個(gè)命題變?cè)獮槎€(gè)命題變?cè)獀p，q，pp，qq，pq， q p，pq，p q 稱(chēng)為簡(jiǎn)單析取式稱(chēng)為簡(jiǎn)單析取式vq，pp，qq， pq， q p，pq，p q 稱(chēng)為簡(jiǎn)單合取式。稱(chēng)為簡(jiǎn)單合取式。152.2 析取范式和合取范式析取范式和合取范式q定理定理: 1)一個(gè)簡(jiǎn)

7、單析取式是永真式當(dāng)且僅當(dāng)它同時(shí)含一個(gè)簡(jiǎn)單析取式是永真式當(dāng)且僅當(dāng)它同時(shí)含某個(gè)命題變?cè)八姆穸ㄊ侥硞€(gè)命題變?cè)八姆穸ㄊ阶C明？證明？2)一個(gè)簡(jiǎn)單合取式是永假式當(dāng)且僅當(dāng)它同時(shí)含一個(gè)簡(jiǎn)單合取式是永假式當(dāng)且僅當(dāng)它同時(shí)含某個(gè)命題變?cè)八姆穸ㄊ侥硞€(gè)命題變?cè)八姆穸ㄊ阶C明？證明？162.2 析取范式和合取范式析取范式和合取范式q析取范式析取范式:由有限個(gè)簡(jiǎn)單合取式構(gòu)成的析取式由有限個(gè)簡(jiǎn)單合取式構(gòu)成的析取式va1 an, ai 為合取式為合取式v( p q) (p r)q合取范式合取范式:由有限個(gè)簡(jiǎn)單析取式構(gòu)成的合取式由有限個(gè)簡(jiǎn)單析取式構(gòu)成的合取式va1 an, ai 為合取式為合取式v( p q) (p

8、 r)q析取范式與合取范式統(tǒng)稱(chēng)為析取范式與合取范式統(tǒng)稱(chēng)為范式范式17182.2 析取范式和合取范式析取范式和合取范式q定理：定理：v設(shè)設(shè)ai 為簡(jiǎn)單合取式，析取范式為簡(jiǎn)單合取式，析取范式a1 an f 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng) ai f，任意，任意aiv設(shè)設(shè)ai 為簡(jiǎn)單析取式，為簡(jiǎn)單析取式， 合取范式合取范式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利用利用“ ”對(duì)對(duì)“ ”的分配，將公式化成為析取范式的分配，將公式化成為析取范式vp (q r) (p q) (p r)262.2 析取范式和合取范式q 例：求例：求(p q) (p q)的析取范式的析取范式 v 化去化去 ( p q) (p q)v “ ”對(duì)對(duì)“ ”分配，化為析取范式分配，化為析取范式 ( p p q) (q p q) v 最簡(jiǎn)析取范式最簡(jiǎn)析取范式 p q 那

12、么如何獲得合取范式呢？那么如何獲得合取范式呢？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è)命題變?cè)暮?jiǎn)單合取式個(gè)命題變?cè)暮?jiǎn)單合取式 (簡(jiǎn)單析取式簡(jiǎn)單析取式)并滿(mǎn)足并滿(mǎn)足v每個(gè)命題變?cè)退姆穸ㄊ讲煌瑫r(shí)出現(xiàn)，而二者之一每個(gè)命題變?cè)退姆穸ㄊ讲煌瑫r(shí)出現(xiàn)，而二者之一必出現(xiàn)且僅出現(xiàn)一次必出現(xiàn)且僅出現(xiàn)一次v第第i個(gè)命題變?cè)蛩姆穸ㄊ匠霈F(xiàn)在從左算起的第個(gè)命題變?cè)蛩姆穸ㄊ匠霈F(xiàn)在從左算起的第i位上位上(若無(wú)角標(biāo)則按字

14、典順序排列若無(wú)角標(biāo)則按字典順序排列)q若有若有個(gè)命題變?cè)?，則有個(gè)命題變?cè)瑒t有2n個(gè)極小項(xiàng)（極大項(xiàng)）個(gè)極小項(xiàng)（極大項(xiàng)）312.2 析取范式和合取范式q極小項(xiàng)的編碼極小項(xiàng)的編碼:對(duì)應(yīng)成真賦值對(duì)應(yīng)成真賦值三個(gè)變?cè)齻€(gè)變?cè)猵、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)的編碼極大項(xiàng)的

15、編碼:對(duì)應(yīng)成假賦值對(duì)應(yīng)成假賦值如三個(gè)變?cè)缛齻€(gè)變?cè)?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是命題變?cè)敲}變?cè)猵1, 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,1,2n-

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

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

18、 得證得證372.2 析取范式和合取范式q一個(gè)公式的主析取范式即為令此公式的真值為一個(gè)公式的主析取范式即為令此公式的真值為t的指派所對(duì)應(yīng)的極小項(xiàng)的析取。的指派所對(duì)應(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、方法求命題公式主析取范式的方法用等值演算方法求命題公式主析取范式的方法q將命題公式化歸為與其等值的析取范式將命題公式化歸為與其等值的析取范式q添變?cè)碜冊(cè)? q消去重復(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)化簡(jiǎn)化簡(jiǎn)(pq)(q(pp)(pq)(pq)(pq) v-(3)添項(xiàng)添項(xiàng)(pq)(pq) v-(4)合并相同最小項(xiàng)合并相同最小項(xiàng)412.2 析取范式和合取范式q主析取范式的用途討論：主析取范

20、式的用途討論：q求公式的成真與成假賦值求公式的成真與成假賦值q判斷公式類(lèi)型判斷公式類(lèi)型q判斷兩個(gè)命題公式是否等值判斷兩個(gè)命題公式是否等值 應(yīng)用主析取范式分析和解決實(shí)際問(wèn)題應(yīng)用主析取范式分析和解決實(shí)際問(wèn)題422.2 析取范式和合取范式q例：某研究所要從例：某研究所要從3名科研骨干名科研骨干a，b，c中挑中挑選選12名出國(guó)進(jìn)修，由于工作需要，選派時(shí)名出國(guó)進(jìn)修，由于工作需要，選派時(shí)要滿(mǎn)足以下條件：要滿(mǎn)足以下條件：q若若a去，則去，則c同去。同去。q若若b去，則去，則c不能去。不能去。q若若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可知選派方案有三種：可知選派方案有三種：qc去，去，a，b都不去。都不去。qb去，去，a，c不去。不去。qa，c去，去，b不去。不去。442.2 析取范式和合取范式q主合取范式主合取范式v任何一個(gè)命題公式都可求得它的主合取范式任何一個(gè)命題公式都可求得它的主合取范式v一個(gè)命題公式的主合取范式是唯一的一個(gè)命題公式的主合取范式是唯一的v在真值表中，令命題公式的真值為在真值表中，令命題公式的真值為“f”的的指派就對(duì)應(yīng)其主合取范式的一個(gè)極大項(xiàng)指派就對(duì)應(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è)變?cè)拿}公式有多少

23、個(gè)不同的主個(gè)變?cè)拿}公式有多少個(gè)不同的主析取范式？析取范式？q對(duì)于含有個(gè)變?cè)拿}公式，必定可寫(xiě)出對(duì)于含有個(gè)變?cè)拿}公式，必定可寫(xiě)出22n個(gè)個(gè)主析取范式主析取范式(包括包括f)。q同理，含有個(gè)變?cè)拿}公式，也可寫(xiě)出同理，含有個(gè)變?cè)拿}公式，也可寫(xiě)出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排斥或排斥或(異或異或) 符號(hào)：符號(hào)：“”( )502.3 聯(lián)結(jié)詞的完備集“與非與非”聯(lián)結(jié)詞

24、：聯(lián)結(jié)詞：符號(hào)符號(hào)“”(pq)讀作：讀作：“p與與q的的否定否定”q(pq)(pq)pqpqfftftttftttf512.3聯(lián)結(jié)詞的完備集q“或非或非”聯(lián)結(jié)詞：聯(lián)結(jié)詞：(a)符號(hào)：符號(hào)：“” (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（n 1

25、）元真值函數(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可滿(mǎn)足性問(wèn)題：可滿(mǎn)足性問(wèn)題：v用于證明用于證明a是否永真是否永真v用于驗(yàn)證邏輯蘊(yùn)涵用于驗(yàn)證邏

26、輯蘊(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是簡(jiǎn)單析取式，是簡(jiǎn)單析取式，c1= c1 l, c2= c2 lcvres(c1,c2)= c1 c2q定理定理：c1 c2 res(c1,c2)v消解式是原公式的邏輯推論消解式是原公式的邏輯推論v討論！是簡(jiǎn)單析取式討論！是簡(jiǎn)單析取式2.4 消解法消解法57q定理定

27、理： c1 c2和和res(c1,c2)可滿(mǎn)足性相同可滿(mǎn)足性相同 證明：證明：c1= c1 l, c2= c2 lc 如果如果c1 c2可滿(mǎn)足，則存在可滿(mǎn)足，則存在v，v(ci)=t 假設(shè)假設(shè)v(l)=t，則，則v(c2)=t。 如果如果res(c1,c2)可滿(mǎn)足，則存在可滿(mǎn)足，則存在v 存在存在l在在c1使得使得v(l)=t, v可以擴(kuò)展為可以擴(kuò)展為 v(p)=f 如果如果p=l v(p)=t 如果如果p=lc v對(duì)對(duì)c1 c2賦值為賦值為tv(c1 c2)=t2.4 消解法消解法58qc1 c2和和res(c1,c2)不等值不等值q例：例：c1=p q r, c2=prvres(c1,c2

28、) = p qvv=ftt滿(mǎn)足滿(mǎn)足res(c1,c2) 但不滿(mǎn)足但不滿(mǎn)足c1 c22.4 消解法消解法59q消解推導(dǎo)：消解推導(dǎo)：s=c1 cn和和cv符號(hào)：符號(hào)：c1,cn cv存在公式序列存在公式序列a1, a2,ak，對(duì)每個(gè)，對(duì)每個(gè)i(i=1,k), ai是某個(gè)是某個(gè)cj或者或者 ai是有序列中前面的公式應(yīng)用消解得到是有序列中前面的公式應(yīng)用消解得到 ak=cv稱(chēng)稱(chēng)a1,ak是由是由s到到c的推導(dǎo)的推導(dǎo)v如果如果c 為空子句為空子句，則稱(chēng)此序列是，則稱(chēng)此序列是s的一個(gè)否證的一個(gè)否證2.4 消解法消解法60：如果合取范式如果合取范式s有否證，則有否證，則s是不是不可滿(mǎn)足可滿(mǎn)足 證明：證明：每次

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

30、) s(i-1)且且c2 s(i-1).若若s(i) s(0) s(i-1)則則s是可滿(mǎn)足的，算法終止是可滿(mǎn)足的，算法終止.轉(zhuǎn)轉(zhuǎn)362q書(shū)書(shū)p37頁(yè)例題頁(yè)例題2.14a=( p q) (p q) ( q)v循環(huán)循環(huán)1 開(kāi)始，開(kāi)始， s(0) = s(1) = p q, p q, q s(2) =通過(guò)對(duì)通過(guò)對(duì)s(0) 、s(1) ， s(1) 進(jìn)行消解得到進(jìn)行消解得到 s(2) = q, p, pv循環(huán)循環(huán)2開(kāi)始，開(kāi)始， s(0) = p q, p q, q s(1)=q, p, p s(2) =v得到得到，算法終止，算法終止2.4 消解法消解法63q例例2：s= p q, p q, pq, p

31、q2.4 消解法消解法 p qp q q p q q p p q q 6465：如果合取范式如果合取范式s含有文字含有文字l，s為為vs先刪除包含先刪除包含l的簡(jiǎn)單析取式的簡(jiǎn)單析取式v再刪除剩下的簡(jiǎn)單析取式中再刪除剩下的簡(jiǎn)單析取式中l(wèi)c則則s和和s可滿(mǎn)足性相同可滿(mǎn)足性相同 證明：證明： 如果如果v為滿(mǎn)足為滿(mǎn)足s的賦值，的賦值，s含有文字含有文字l，v(l)=t，對(duì)任意，對(duì)任意s中中c，必有，必有v(s)=t。 如果如果v為滿(mǎn)足為滿(mǎn)足s的賦值，則可以擴(kuò)展為滿(mǎn)足的賦值，則可以擴(kuò)展為滿(mǎn)足s的的賦值（驗(yàn)證）！賦值（驗(yàn)證）！ 2.4 消解法消解法66：如果合取范式如果合取范式s是不可滿(mǎn)足，則是不可滿(mǎn)足，

32、則s有否證有否證 證明：證明：對(duì)對(duì)s中所含命題個(gè)數(shù)中所含命題個(gè)數(shù)k歸納證明歸納證明 第一步驟第一步驟 k=1: s中有中有p, p 第二步驟第二步驟 假設(shè)假設(shè)kn時(shí)定理成立，證明時(shí)定理成立，證明k=n時(shí)定時(shí)定理成立理成立 1. 對(duì)對(duì)s p應(yīng)用引理應(yīng)用引理1，得到等滿(mǎn)足性的，得到等滿(mǎn)足性的s 2. 對(duì)對(duì)s p應(yīng)用引理應(yīng)用引理1，得到等滿(mǎn)足性的，得到等滿(mǎn)足性的s 由假設(shè)，存在由假設(shè)，存在s的否證的否證c1,ci，s的否證的否證 d1,dj2.4 消解法消解法67q 證明（繼續(xù)）：證明（繼續(xù)）： 1. 對(duì)對(duì)s p應(yīng)用引理應(yīng)用引理1，得到等滿(mǎn)足性的，得到等滿(mǎn)足性的s 2. 對(duì)對(duì)s p應(yīng)用引理應(yīng)用引理1

33、，得到等滿(mǎn)足性的，得到等滿(mǎn)足性的s 由假設(shè)，存在由假設(shè)，存在s的否證的否證c1,ci，s的否證的否證 d1,dj 情況情況1：ct (i t 1)或或ds (j t 1)都是由不含都是由不含p的簡(jiǎn)單的簡(jiǎn)單析取式消解得到，析取式消解得到， c1,ci或或d1,dj為為s的否證的否證 情況情況2： ct (或或ds)不滿(mǎn)足情況不滿(mǎn)足情況1條件，則擴(kuò)展條件，則擴(kuò)展ct (或或ds)得到得到ct= ct p (或或ds = ds p ) ，則，則ct (或或ds )屬于屬于s ，且，且 ci= p， dj=p，消解得到，消解得到空子句空子句2.4 消解法消解法68第二章第二章 習(xí)題課習(xí)題課q主要內(nèi)容主

34、要內(nèi)容l等值式與等值演算等值式與等值演算l基本等值式（基本等值式（1616組，組，2424個(gè)公式）個(gè)公式）l主析取范式與主合取范式主析取范式與主合取范式l聯(lián)結(jié)詞完備集聯(lián)結(jié)詞完備集l消解法消解法69基本要求基本要求l 深刻理解等值式的概念深刻理解等值式的概念l 牢記基本等值式的名稱(chēng)及它們的內(nèi)容牢記基本等值式的名稱(chēng)及它們的內(nèi)容l 熟練地應(yīng)用基本等值式及置換規(guī)則進(jìn)行等值演算熟練地應(yīng)用基本等值式及置換規(guī)則進(jìn)行等值演算l 理解文字、簡(jiǎn)單析取式、簡(jiǎn)單合取式、析取范式、合取范式的概理解文字、簡(jiǎn)單析取式、簡(jiǎn)單合取式、析取范式、合取范式的概念念l 深刻理解極小項(xiàng)、極大項(xiàng)的概念、名稱(chēng)及下角標(biāo)與成真、成假賦深刻理解

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

36、消解算法判斷公式的可滿(mǎn)足性會(huì)用消解算法判斷公式的可滿(mǎn)足性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) 任何公式都能等值地化成任何公式都能等值地化成 , , 中的公式中的公式說(shuō)明說(shuō)明:(2) 重言式的主合取范式不含任何極大

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

38、判斷下列公式的類(lèi)型: (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ù))非重言式的可滿(mǎn)足式非重言式的可滿(mǎn)足式74練習(xí)練習(xí)3：求公式的主范式求公式的主范式3已知

39、命題公式已知命題公式a中含中含3個(gè)命題變項(xiàng)個(gè)命題變項(xiàng)p, q, r，并知道它的成真，并知道它的成真賦值為賦值為001, 010, 111, 求求a的主析取范式和主合取范式，及的主析取范式和主合取范式，及a對(duì)對(duì)應(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 = (pq) r改寫(xiě)成下述各聯(lián)結(jié)詞集中的公式改寫(xiě)成下述

40、各聯(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) 說(shuō)明：答案不惟一說(shuō)明：答案不惟一77練習(xí)練習(xí)5：應(yīng)用題：應(yīng)用題5. 某公司要從趙、錢(qián)、孫、李、周五名新畢業(yè)的大某公司要從趙、錢(qián)、孫、李、周五名新畢業(yè)的大學(xué)生中選學(xué)生中選派一些人出國(guó)學(xué)習(xí)派一些人出國(guó)學(xué)習(xí). 選派必須滿(mǎn)足以下條件：選派必須滿(mǎn)足以下條件：(1) 若趙去，錢(qián)也去若趙去，錢(qián)也去.(2) 李、周兩人中至少有一人去李、周兩人中至少有一人去(3) 錢(qián)、孫兩人中去且僅去一人錢(qián)、孫兩人中去且僅去一人.(4) 孫、李兩人同去或同不去孫、李兩人同去或同不去.(5) 若周去，則趙、錢(qián)也去若周去，則趙、錢(qián)也去. 用等值演算法分析該公司如何選派他們出國(guó)？用等值演算法分析該公司如何選派他們出國(guó)？78練