離散數(shù)學(xué),命題邏輯等值演算.ppt

1、第二章 命題邏輯等值演算,2.1 等值式 2.2 析取范式與合取范式 2.3 聯(lián)結(jié)詞的完備集 2.4 可滿足性問題與消解法,重點(diǎn),難點(diǎn),2.1 等值式,定義2.1 設(shè)A、B是任意兩個(gè)命題公式，若等價(jià)式 A B為重言式，則稱A與B是等值的， 記作：A B 自反性，即對(duì)任意命題公式A， AA 對(duì)稱性，即對(duì)任意命題公式A和B， 若AB，則BA 傳遞性，即對(duì)任意命題公式A，B和C， 若AB，BC，則AC,兩點(diǎn)注意,“”與“=” “A=B”表示兩公式一樣， “A B”表示兩公式真值一樣 與是兩類完全不同的符號(hào) 是聯(lián)結(jié)詞、運(yùn)算符，AB是一個(gè)公式。 不是聯(lián)結(jié)詞， 而是兩個(gè)公式之間的關(guān)系符,真值表判斷等值,十

2、六組重要的等值式（模式）,1.雙重否定律 A A 2.冪等律 AA A，AA A 3.交換律 AB BA，AB BA 4.結(jié)合律 (AB)C A(BC) (AB)C A(BC),十六組重要的等值式,5.分配律 (提取公因式） A(BC) (AB)(AC) A(BC) ( AB)(AC) 6.德摩根律 (AB) AB (AB) AB,德摩根律的例子,“地大物博”的否定： 地不大或物不博 (AB) AB “用人民幣或港幣支付”的否定： 既不能用人民幣支付，也不能用港幣支付 (AB) AB,十六組重要的等值式,7.吸收律 A(AB)A，A(AB)A 8.零律 A11，A00 9.同一律 A0A，A1

3、A 10.排中律 AA 1 11.矛盾律 AA 0,十六組重要的等值式,12.蘊(yùn)涵等值式 AB AB 13.等價(jià)等值式 AB (AB)(BA) 14.假言易位 AB BA 15.等價(jià)否定等值式 AB AB 16.歸謬論 (AB)(AB) A,蘊(yùn)涵等值式的例子,蘊(yùn)涵等值式： AB AB 否定形式：并非（pq) (pq) p q 例： 并非招手即停 招手且不停車,歸謬論的應(yīng)用,歸謬論 (AB)(AB) A 反證法 如果非p，則q 如果非p，則非q 所以，p,歸謬論的例子,亞理士多德：物體的下落速度與物體的重量成正比。 伽利略的思想實(shí)驗(yàn)： A快B慢，AB比A快； A快B慢，AB比A慢。,歸謬論的例子

4、,一個(gè)島上有一個(gè)風(fēng)俗，凡是外鄉(xiāng)人都要作為祭品被殺掉。 但允許被殺的人在臨死前說一句話。 如果這句話是真的，則死在真理之神面前。 如果這句話是假的，則死在錯(cuò)誤之神面前。 一個(gè)哲學(xué)家說了一句話，而免于一死。,等值演算與置換規(guī)則,由已知的等值式推演出另外的等值式的過程稱為等值演算。 置換規(guī)則 設(shè)（A）是一個(gè)含有公式A的命題公式， （B）是用公式B置換了（A）中的公式A后得到的公式， 如果A B，那么 （A） （B）。,等值演算的例子,【例2.1】 用等值演算驗(yàn)證等值式 p（qr）（pq）r,等值演算的例子,【例2.2】用等值演算法判斷下列公式的類型。 q (pq)p) (pp)(q q)r) (pq

5、)p,等值演算的例子,解： q(pq)p) q(pp)(qp) (分配律) q(0(qp) (矛盾律) q(qp) (同一律) q(qp) (德摩根律) (qq)p (結(jié)合律) 1p (排中律) 1 (零律) 由此可知，為重言式。,等值演算的例子,解： (pp)(qq)r) 1(qq)r) (排中律) 1(0r) (矛盾律) 10 (零律) 0 (條件聯(lián)結(jié)詞的定義) 由此可知，為矛盾式。 (pq)p (pq)p (蘊(yùn)涵等值式) p (吸收律) 由此可知，是可滿足式。,練習(xí),1.用等值演算驗(yàn)證等值式 （1） (pq)r (pr) (qr) （2） （(pq) （pq） （p q） 2.判斷公式的

6、類型 （1）（pq）p q （2） （pq）q）r,判斷問題,【例2.6】判斷王教授是哪里人： 甲說王教授不是蘇州人，是上海人 乙說王教授不是上海人，是蘇州人 丙說不是上海人，也不是杭州人 王教授說三個(gè)人中一個(gè)說的全對(duì)，一個(gè)說對(duì)了一半，另一個(gè)全不對(duì)。 解：p：王教授是蘇州人 q：王教授是上海人 r：王教授是杭州人,解題思路,p q r 0 0 1 0 1 0 1 0 0 王教授的話是對(duì)的，寫出公式 A（p,q,r)，找出它的成真賦值,根據(jù)實(shí)際情況， 只有3個(gè)賦值， 而不是8個(gè),作業(yè),習(xí)題二 3839頁 題目： 3，4 17，18 19，20,2.2 析取范式與合取范式,定義2.2 將命題變?cè)?/p>

7、其否定統(tǒng)稱為文字（literal）。 簡(jiǎn)單析取式（基本和）： 僅由有限個(gè)文字構(gòu)成的析取式，也稱為子句（clause）。 簡(jiǎn)單合取式（基本積）：僅由有限個(gè)文字構(gòu)成的合取式。,例如： p、q既是一個(gè)文字的簡(jiǎn)單析取式， 又是一個(gè)文字的簡(jiǎn)單合取式。 pq，p r均是有兩個(gè)文字的簡(jiǎn)單析取式，即子句。 pqr，pq q均是有三個(gè)文字的簡(jiǎn)單合取式。,定理 2.1,(1) 一個(gè)簡(jiǎn)單析取式是重言式， 當(dāng)且僅當(dāng)它同時(shí)含有一個(gè)命題變?cè)捌浞穸ā?(2) 一個(gè)簡(jiǎn)單合取式是矛盾式， 當(dāng)且僅當(dāng)它同時(shí)含有一個(gè)命題變?cè)捌浞穸ā?例如， pq p 是重言式 p q q是矛盾式,范式（normal form）的定義,定義2.3

8、 析取范式 由有限個(gè)簡(jiǎn)單合取式構(gòu)成的析取式，簡(jiǎn)稱DNF（disjunctive normal form）。 合取范式 由有限個(gè)簡(jiǎn)單析取式構(gòu)成的合取式，簡(jiǎn)稱CNF（conjunctive normal form）。,析取范式的例子： A = A1 A2 An = (pqr) (pq q) p,范式存在定理,定理2.3 任一命題公式都存在著與之等值的析取范式 任一命題公式都存在著與之等值的合取范式,求范式的步驟如下： 消去聯(lián)結(jié)詞“”和“” 利用雙重否定律消去否定聯(lián)結(jié)詞“”或利用德摩根律將否定聯(lián)結(jié)詞“”移到各命題變?cè)?內(nèi)移)。 利用分配律，結(jié)合律將公式歸約為合取范式和析取范式。,例題,【例2.7】

9、 求(pq)p的合取范式和析取范式。,(pq)p (pq)p)(p(pq) (pq)p)(p(pq) (pq)p)(p(pq) (pp)(qp)(ppq) ) 1(qp)(1q) 1(qp)1 (qp),練習(xí),求析取范式與合取范式： (pq)r,合取范式 （pr) (qr) (pqr) 析取范式 （pqr）（ pr ）（ qr ）,極小項(xiàng)與極大項(xiàng),定義2.4 極小項(xiàng)：在含有n個(gè)命題變?cè)暮?jiǎn)單合取式中，若每個(gè)命題變?cè)退姆穸ㄊ讲煌瑫r(shí)出現(xiàn)，而二者之一必出現(xiàn)且僅出現(xiàn)一次，且第i個(gè)命題變?cè)ɑ蛩姆穸ㄊ剑┏霈F(xiàn)在從左算起的第i位上。 極大項(xiàng)：簡(jiǎn)單析取式中滿足如上條件。,極?。ù螅╉?xiàng)的核心性質(zhì),定理：n

10、個(gè)命題變?cè)灿?n個(gè)極小項(xiàng)（極大項(xiàng)）。 每個(gè)極?。ù螅╉?xiàng)只有一個(gè)成真（假）賦值，且各極小項(xiàng)的成真賦值互不相同。 極小項(xiàng)和它的成真賦值構(gòu)成了一一對(duì)應(yīng)的關(guān)系。,極小項(xiàng)的性質(zhì),可用成真賦值為極小項(xiàng)進(jìn)行編碼，并把編碼作為m的下標(biāo)來表示該極小項(xiàng)，叫做該極小項(xiàng)的名稱。 極小項(xiàng)與其成真賦值的對(duì)應(yīng)關(guān)系為：變?cè)獙?duì)應(yīng)1，而變?cè)姆穸▽?duì)應(yīng)0。,極小項(xiàng)的性質(zhì),極大項(xiàng),練習(xí),寫出極小項(xiàng)的公式： m4 m6 m7 當(dāng)變?cè)膫€(gè)數(shù)分別為3、4時(shí)。 寫出極大項(xiàng)的公式： M4 M6 M7 當(dāng)變?cè)膫€(gè)數(shù)分別為3、4時(shí)。,定理：極小項(xiàng)與極大項(xiàng),定理2.4 miMi mi Mi,定義：主范式,定義2.5 主析取范式：析取范式中所有的簡(jiǎn)

11、單合取式都是極小項(xiàng)。 主合取范式：合取范式中所有的簡(jiǎn)單析取式都是極大項(xiàng)。 問題： 對(duì)于n個(gè)命題變?cè)?有多少個(gè)主析（合）取范式？,例： m0m1m7 （n3） M0M2M6 （n3）,主范式的存在性與唯一性,定理2.5 任何命題公式都存在與之等值的主析取范式和主合取范式，并且是唯一的。 證明： （1）存在性：等值演算 （2）唯一性：反證法,例題與練習(xí),【例2.8】求主析取范式與主合取范式： (pq)r 練習(xí)： pq,合取范式 （pr) (qr) (pqr) 析取范式 （pqr）（ pr ）（ qr ）,主范式與真值表,定理： 若公式A中含n個(gè)命題變?cè)珹的主析取范式含s（0s2n）個(gè)極小項(xiàng)，則

12、A有s個(gè)成真賦值，它們是所含極小項(xiàng)編號(hào)的二進(jìn)制表示，其余2n s個(gè)賦值都是成假賦值。 反之也成立。 對(duì)主合取范式有相同的結(jié)果（對(duì)應(yīng)成假賦值）,從真值表求主范式,【例】用真值表法，求(pq)r的主范式。 m001m011m100m101m111 m1m3m4m5m7,“排斥或”的公式,排斥或： ( pq) (p q) m1 m2,通過主范式判別公式類型,定理 A為重言式當(dāng)且僅當(dāng)A的主析取范式含全部2n個(gè)極小項(xiàng)（主合取范式0個(gè)極大項(xiàng)） A為矛盾式當(dāng)且僅當(dāng)A的主析取范式不含任何極小項(xiàng)（主合取范式含所有的極大項(xiàng)） A為可滿足式當(dāng)且僅當(dāng)A的主析取范式至少含一個(gè)極小項(xiàng)。,主析取范式與主合取范式的關(guān)系,定理

13、： 同一公式的主析取范式中極小項(xiàng)m的下標(biāo)和主合取范式中極大項(xiàng)M的下標(biāo)是互補(bǔ)的。 換言之，對(duì)于任一公式， 在它的2n個(gè)賦值中， 非0即1， 因此其主析取范式中的極小項(xiàng)和其主合取范式中的極大項(xiàng)的個(gè)數(shù)之和恰為2n， 且其下標(biāo)不會(huì)相同。,練習(xí),由主析取范式，求主合取范式 （1）Am1m2 （兩個(gè)變?cè)?（2）Bm1m2m3 （三個(gè)變?cè)?作業(yè),習(xí)題二 3840頁 題目：5，6 7，8 9，10 11，12 13，14 25，26,2.3 聯(lián)結(jié)詞的完備集,定義2.6 n元真值函數(shù)F：0,1n 0,1 定理 每個(gè)真值函數(shù)，都一一對(duì)應(yīng)一個(gè)真值表。每個(gè)真值函數(shù)，都存在許多與之等值的命題公式。反之，每個(gè)命題公式

14、對(duì)應(yīng)唯一的與之等值的真值函數(shù)。 定義2.7 設(shè)S是聯(lián)結(jié)詞集合，如果任何n元真值函數(shù)都可以由僅含S中的聯(lián)結(jié)詞構(gòu)成的公式表示，則稱S是聯(lián)結(jié)詞完備集。,聯(lián)結(jié)詞的完備集,定理2.6 S，聯(lián)結(jié)詞完備集。 推論 以下集合都是完備集 ， ， ， ， ，,聯(lián)結(jié)詞的完備集,定義2.8 與非聯(lián)結(jié)詞：pq (pq) 或非聯(lián)結(jié)詞：pq (pq) 定理2.7 ，是聯(lián)結(jié)詞完備集。,2.4 可滿足性問題與消解法,命題公式的可滿足性問題 （SAT問題，satisfiability problem）是算法理論的核心問題之一。 真值表、主范式的計(jì)算量大。 從算法復(fù)雜度上講，SAT是第一個(gè)被證明為NP難的問題。,SAT問題,很多問

15、題可以轉(zhuǎn)化為SAT問題 著名的八皇后問題 鴿籠問題 圖著色問題等,合取范式的可滿足性問題,S表示合取范式，C表示簡(jiǎn)單析取式（子句），L表示文字 合取范式： SC1 C2 C3 Cn S是可滿足的當(dāng)且僅當(dāng)每個(gè)Ci都是可滿足的。 或者，只要一個(gè)子句不可滿足，則S不可滿足 進(jìn)一步，只要一部分不滿足，則整體不滿足,簡(jiǎn)單析取式（子句）,Ci L1 L2 L3 Lk 一個(gè)簡(jiǎn)單析取式中同時(shí)出現(xiàn)文字L（如p）及它的補(bǔ)Lc（如p），則它為永真式。 永真式可以從合取范式中除去，是多余的。 因此，假設(shè)簡(jiǎn)單析取式中不同時(shí)出現(xiàn)某個(gè)命題變項(xiàng)和它的否定。,空子句不可滿足,Ci L1 L2 L3 Lk 文字越多，越容易滿足

16、文字越少，越難滿足 空子句，記為，不可滿足。（沒有極小項(xiàng)，無成真賦值）。 因此，含有空子句的合取范式是不可滿足的。,如子句 p，在p1時(shí)被滿足， 而子句pq，在p0時(shí)也能滿足 （q0）。,通過“消解規(guī)則”產(chǎn)生“空子句”,定義2.9 C1與C2是兩個(gè)簡(jiǎn)單析取式 C1C1 L （ pq r ） C2C2 Lc （p r s t） 消解式（消解規(guī)則） Res（C1,C2） C1 C2,消解式： Res（C1,C2） q r r s t p q p s t Res(p, p)= ,通過消解規(guī)則化簡(jiǎn)合取式,定理2.8 C1 C2 Res（C1，C2） 即，C1 C2可滿足當(dāng)且僅當(dāng) 消解式Res（C1，C

17、2）可滿足,若 C1 p q r C2 p r 則 C1 C2 （ p q r ） （p r ） Res（C1,C2） p q,消解序列與否證,定義2.10 設(shè)S是一個(gè)合取范式，C1，C2， ，Cn是一個(gè)如下生成的子句序列： 對(duì)每一個(gè)i（1in），Ci是S中的一個(gè)簡(jiǎn)單析取式； 或者Ci是它之前的某兩個(gè)簡(jiǎn)單析取式Cj，Ck（1jki）的消解結(jié)果， 則稱此序列是由S導(dǎo)出的消解序列。 當(dāng)Cn時(shí)，稱此序列是S的一個(gè)否證。,消解的完全性,推論 如果合取范式S有否證，則S是不可滿足的。 定理2.10（消解的完全性） 如果合取范式S是不可滿足的，則S有否證。 推論 合取范式S是不可滿足的當(dāng)且僅當(dāng)S有否證。,

18、消解算法,輸入：合式公式A 輸出：當(dāng)A是可滿足的，回答“yes”； 否則回答“no”。 步驟如下： 求A的合取范式S S1為S的所有子句的集合，S0與S2為空集,運(yùn)用消解規(guī)則,3.對(duì)S0 中的每一個(gè)子句C1與S1中的每一個(gè)子句C2 如果C1、C2可以消解，則計(jì)算CRes（C1，C2） 如果C 則輸出“no”，計(jì)算結(jié)束 否則，如果S0與S1都不包含C 則將C加入S2,運(yùn)用消解規(guī)則,4.對(duì)S1 中的每一對(duì)子句C1與C2 如果C1、C2可以消解，則計(jì)算CRes（C1，C2） 如果C 則輸出“no”，計(jì)算結(jié)束 否則，如果S0與S1都不包含C 則將C加入S2,5 .如果S2中沒有任何元素則 輸出“yes”，計(jì)算結(jié)