離散數(shù)學(xué)第2章 命題邏輯等值演算

1、1主要內(nèi)容主要內(nèi)容l 等值式與基本的等值式等值式與基本的等值式l 等值演算與置換規(guī)則等值演算與置換規(guī)則l 析取范式與合取范式，主析取范式與主合取范式析取范式與合取范式，主析取范式與主合取范式l 聯(lián)結(jié)詞完備集聯(lián)結(jié)詞完備集l 可滿足性問題與消解法可滿足性問題與消解法第二章第二章 命題邏輯等值演算命題邏輯等值演算22.1 等值式等值式定義定義2.1 若等價(jià)式若等價(jià)式AB是重言式，則稱是重言式，則稱A與與B等值等值，記作，記作AB，并稱，并稱AB是是等值式等值式幾點(diǎn)說明：幾點(diǎn)說明：l定義中，定義中，A, B, 均為元語言符號(hào)均為元語言符號(hào)l A或或B中可能有啞元出現(xiàn)中可能有啞元出現(xiàn). 例如例如 (pq

2、) ( p q) ( r r) r為左邊公式的啞元為左邊公式的啞元. l用真值表可檢查兩個(gè)公式是否等值用真值表可檢查兩個(gè)公式是否等值請(qǐng)驗(yàn)證：請(qǐng)驗(yàn)證： p(qr) (p q) r p(qr) 不與不與 (pq) r 等值等值3等值式例題等值式例題例例1 判斷下列各組公式是否等值判斷下列各組公式是否等值: (1) p(qr) 與與 (p q) r 11111101 11111101 11011101 0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 (p q)rp(qr)qr p q rp q00000011 結(jié)論結(jié)論: : p(qr) (p q) r 4等值式例題

3、等值式例題 (2) p(qr) 與與 (pq) r 01011101 11111101 11011101 0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 (pq)rp(qr)qr p q rpq11110011 結(jié)論結(jié)論: : p(qr) 與與 (pq) r 不等值不等值5基本等值式基本等值式雙重否定律雙重否定律 AA冪等律冪等律 A AA, A AA交換律交換律 A BB A, A BB A結(jié)合律結(jié)合律 (A B) CA (B C), (A B) CA (B C)分配律分配律 A (B C)(A B) (A C), A (B C)(A B) (A C)德摩根

4、律德摩根律 (A B)AB (A B)AB吸收律吸收律 A (A B)A, A (A B)A6基本等值式基本等值式零律零律 A 11, A 00同一律同一律 A 0A. A 1A排中律排中律 AA1矛盾律矛盾律 AA0蘊(yùn)涵等值式蘊(yùn)涵等值式 ABA B等價(jià)等值式等價(jià)等值式 AB(AB) (BA)假言易位假言易位 ABBA等價(jià)否定等值式等價(jià)否定等值式 ABAB歸謬論歸謬論 (AB) (AB) A特別提示：必須牢記這特別提示：必須牢記這16組等值式，這是繼續(xù)學(xué)習(xí)的基礎(chǔ)組等值式，這是繼續(xù)學(xué)習(xí)的基礎(chǔ)7等值演算與置換規(guī)則等值演算與置換規(guī)則1. 等值演算等值演算由已知的等值式推演出新的等值式的過程由已知的等

5、值式推演出新的等值式的過程2. 等值演算的基礎(chǔ)：等值演算的基礎(chǔ)： (1) 等值關(guān)系的性質(zhì)：自反性、對(duì)稱性、傳遞性等值關(guān)系的性質(zhì)：自反性、對(duì)稱性、傳遞性 (2) 基本的等值式基本的等值式 (3) 置換規(guī)則（見置換規(guī)則（見3）3. 置換規(guī)則置換規(guī)則 設(shè)設(shè) (A) 是含公式是含公式 A 的命題公式，的命題公式， (B) 是用公式是用公式 B 置換置換 (A) 中所有的中所有的 A 后得到的命題公式后得到的命題公式 若若 BA，則，則 (B)(A)8等值演算的應(yīng)用舉例等值演算的應(yīng)用舉例證明兩個(gè)公式等值證明兩個(gè)公式等值例例2 證明證明 p(qr) (p q)r證證 p(qr) p ( q r) （蘊(yùn)涵等

6、值式，置換規(guī)則）（蘊(yùn)涵等值式，置換規(guī)則） ( pq) r （結(jié)合律，置換規(guī)則）（結(jié)合律，置換規(guī)則） (p q) r （德摩根律，置換規(guī)則）（德摩根律，置換規(guī)則） (p q)r （蘊(yùn)涵等值式，置換規(guī)則）（蘊(yùn)涵等值式，置換規(guī)則）今后在注明中省去置換規(guī)則今后在注明中省去置換規(guī)則注意：用等值演算不能直接證明兩個(gè)公式不等值注意：用等值演算不能直接證明兩個(gè)公式不等值9證明兩個(gè)公式不等值證明兩個(gè)公式不等值例例3 證明證明 p(qr) 與與 (pq)r 不等值不等值證證 方法一方法一 真值表法真值表法, 見例見例1(2)方法二方法二 觀察法觀察法. 觀察到觀察到000, 010是左邊的成真賦值，是右是左邊的成

7、真賦值，是右邊的成假賦值邊的成假賦值 方法三方法三 先用等值演算化簡(jiǎn)公式，然后再觀察先用等值演算化簡(jiǎn)公式，然后再觀察 p(qr) pq r (pq)r ( p q) r(pq) r 更容易看出前面的兩個(gè)賦值分別是更容易看出前面的兩個(gè)賦值分別是左邊的成真賦左邊的成真賦 值和右邊的成假賦值值和右邊的成假賦值等值演算的應(yīng)用舉例等值演算的應(yīng)用舉例10判斷公式類型判斷公式類型: A為矛盾式當(dāng)且僅當(dāng)為矛盾式當(dāng)且僅當(dāng)A 0 A為重言式當(dāng)且僅當(dāng)為重言式當(dāng)且僅當(dāng)A 1例例4 用等值演算法判斷下列公式的類型用等值演算法判斷下列公式的類型 (1) q(pq) (2) (pq)( qp) (3) (p q) (pq)

8、 r) 等值演算的應(yīng)用舉例等值演算的應(yīng)用舉例解解 (1) q(pq) q( p q) （蘊(yùn)涵等值式）（蘊(yùn)涵等值式） q (pq) （德摩根律）（德摩根律） p (qq) （交換律，結(jié)合律）（交換律，結(jié)合律） p 0 （矛盾律）（矛盾律） 0 （零律）（零律）矛盾式矛盾式11判斷公式類型判斷公式類型(2) (pq)( qp) ( p q)(qp) （蘊(yùn)涵等值式）（蘊(yùn)涵等值式） ( p q)( p q) （交換律）（交換律） 1重言式重言式(3) (p q) (pq) r) (p (qq) r （分配律）（分配律） p 1 r （排中律）（排中律） p r （同一律）（同一律）可滿足式，可滿足式，

9、101和和111是成真賦值，是成真賦值，000和和010等是成假賦值等是成假賦值. 122.2 析取范式與合取范式析取范式與合取范式基本概念基本概念(1) 文字文字命題變項(xiàng)及其否定的總稱命題變項(xiàng)及其否定的總稱(2) 簡(jiǎn)單析取式簡(jiǎn)單析取式有限個(gè)文字構(gòu)成的析取式有限個(gè)文字構(gòu)成的析取式 p, q, pq, p q r, (3) 簡(jiǎn)單合取式簡(jiǎn)單合取式有限個(gè)文字構(gòu)成的合取式有限個(gè)文字構(gòu)成的合取式 p, q, pq, p q r, (4) 析取范式析取范式由有限個(gè)簡(jiǎn)單合取式組成的析取式由有限個(gè)簡(jiǎn)單合取式組成的析取式 p, p q, pq, (pq) ( p qr) (q r)(5) 合取范式合取范式由有限

10、個(gè)簡(jiǎn)單析取式組成的合取式由有限個(gè)簡(jiǎn)單析取式組成的合取式 p, pq, p q, (p qp (p q r)(6) 范式范式析取范式與合取范式的總稱析取范式與合取范式的總稱13范式概念范式概念說明：說明：l 單個(gè)文字既是簡(jiǎn)單析取式，又是簡(jiǎn)單合取式單個(gè)文字既是簡(jiǎn)單析取式，又是簡(jiǎn)單合取式14范式的性質(zhì)范式的性質(zhì)定理定理2.1 (1) 一個(gè)簡(jiǎn)單析取式是重言式當(dāng)且僅當(dāng)它同時(shí)含有某一個(gè)簡(jiǎn)單析取式是重言式當(dāng)且僅當(dāng)它同時(shí)含有某個(gè)命題變項(xiàng)和它的否定式個(gè)命題變項(xiàng)和它的否定式.(2) 一個(gè)簡(jiǎn)單合取式是矛盾式當(dāng)且僅當(dāng)它同時(shí)含有某個(gè)命題一個(gè)簡(jiǎn)單合取式是矛盾式當(dāng)且僅當(dāng)它同時(shí)含有某個(gè)命題變項(xiàng)和它的否定式變項(xiàng)和它的否定式.定

11、理定理2.2 (1) 一個(gè)析取范式是矛盾式當(dāng)且僅當(dāng)它每個(gè)簡(jiǎn)單合一個(gè)析取范式是矛盾式當(dāng)且僅當(dāng)它每個(gè)簡(jiǎn)單合取式都是矛盾式取式都是矛盾式.(2) 一個(gè)合取范式是重言式當(dāng)且僅當(dāng)它的每個(gè)簡(jiǎn)單析取式都一個(gè)合取范式是重言式當(dāng)且僅當(dāng)它的每個(gè)簡(jiǎn)單析取式都是重言式是重言式.15命題公式的范式命題公式的范式定理定理2.3（范式存在定理）（范式存在定理） 任何命題公式都存在與之等值的析取范式與合取范式任何命題公式都存在與之等值的析取范式與合取范式公式公式A的析取的析取(合取合取)范式范式與與A等值的等值的析取析取(合取合取)范式范式求公式求公式A的范式的步驟：的范式的步驟： (1) 消去消去A中的中的, （若存在）（

12、若存在） ABA B AB( A B) (AB) (2) 否定聯(lián)結(jié)詞否定聯(lián)結(jié)詞 的內(nèi)移或消去的內(nèi)移或消去 A A (A B)AB (A B)AB16命題公式的范式命題公式的范式 (3) 使用分配律使用分配律 A (B C)(A B) (A C) 求合取范式求合取范式 A (B C) (A B) (A C) 求析取范式求析取范式公式范式的不足公式范式的不足不惟一不惟一17求公式的范式求公式的范式例例5 求下列公式的析取范式與合取范式求下列公式的析取范式與合取范式 (1) (pq)r (2) (pq)r解解 (1) (pq)r ( pq)r （消去（消去） pqr （結(jié)合律）（結(jié)合律）18 (2)

13、 (pq)r ( pq)r （消去第一個(gè)（消去第一個(gè)） ( pq) r （消去第二個(gè)（消去第二個(gè)） (p q) r （否定號(hào)內(nèi)移（否定號(hào)內(nèi)移德摩根律德摩根律) 析取范式析取范式 (p r) (q r) （ 對(duì)對(duì) 分配律）分配律） 合取范式合取范式求公式的范式求公式的范式19極小項(xiàng)與極大項(xiàng)極小項(xiàng)與極大項(xiàng)定義定義2.4 在含有在含有n個(gè)命題變項(xiàng)的簡(jiǎn)單合取式（簡(jiǎn)單析取式）個(gè)命題變項(xiàng)的簡(jiǎn)單合取式（簡(jiǎn)單析取式）中，若每個(gè)命題變項(xiàng)均以文字的形式在其中出現(xiàn)且僅出現(xiàn)中，若每個(gè)命題變項(xiàng)均以文字的形式在其中出現(xiàn)且僅出現(xiàn)一次，而且第一次，而且第i個(gè)文字出現(xiàn)在左起第個(gè)文字出現(xiàn)在左起第i位上（位上（1 i n），稱這）

14、，稱這樣的簡(jiǎn)單合取式（簡(jiǎn)單析取式）為樣的簡(jiǎn)單合取式（簡(jiǎn)單析取式）為極小項(xiàng)極小項(xiàng)（極大項(xiàng)極大項(xiàng)）.幾點(diǎn)說明：幾點(diǎn)說明：l n個(gè)命題變項(xiàng)有個(gè)命題變項(xiàng)有2n個(gè)極小項(xiàng)和個(gè)極小項(xiàng)和2n個(gè)極大項(xiàng)個(gè)極大項(xiàng)l 2n個(gè)極小項(xiàng)（極大項(xiàng)）均互不等值個(gè)極小項(xiàng)（極大項(xiàng)）均互不等值l 用用mi表示第表示第i個(gè)極小項(xiàng)，其中個(gè)極小項(xiàng)，其中i是該極小項(xiàng)成真賦值的十進(jìn)是該極小項(xiàng)成真賦值的十進(jìn)制表示制表示. 用用Mi表示第表示第i個(gè)極大項(xiàng)，其中個(gè)極大項(xiàng)，其中i是該極大項(xiàng)成假賦值是該極大項(xiàng)成假賦值的十進(jìn)制表示的十進(jìn)制表示. mi（Mi）稱為極小項(xiàng)（極大項(xiàng)）的名稱）稱為極小項(xiàng)（極大項(xiàng)）的名稱. 20實(shí)例實(shí)例由兩個(gè)命題變項(xiàng)由兩個(gè)命題變項(xiàng)

15、 p, q 形成的極小項(xiàng)與極大項(xiàng)形成的極小項(xiàng)與極大項(xiàng)極小項(xiàng)極小項(xiàng)極大項(xiàng)極大項(xiàng)公式公式成真賦值成真賦值名稱名稱公式公式成假賦值成假賦值名稱名稱 pq p qpqp q 0 0 0 1 1 0 1 1 m0m1m2m3 p q pq p q pq 0 0 0 1 1 0 1 1M0M1M2M321實(shí)例實(shí)例極小項(xiàng)極小項(xiàng)極大項(xiàng)極大項(xiàng)公式公式成真賦值成真賦值名稱名稱公式公式成假賦值成假賦值名稱名稱 p q r p q r p q r p q rp q rp q rp q rp q r0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 m0m1m2m3m4m5m6m7 p q

16、 r p q r p q r p q r p q r p q r p q r p q r0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 M0M1M2M3M4M5M6M7由三個(gè)命題變項(xiàng)由三個(gè)命題變項(xiàng) p, q, r 形成的極小項(xiàng)與極大項(xiàng)形成的極小項(xiàng)與極大項(xiàng). mi與與Mi的關(guān)系：的關(guān)系： mi Mi, Mi mi 22主析取范式與主合取范式主析取范式與主合取范式主析取范式主析取范式由極小項(xiàng)構(gòu)成的析取范式由極小項(xiàng)構(gòu)成的析取范式主合取范式主合取范式由極大項(xiàng)構(gòu)成的合取范式由極大項(xiàng)構(gòu)成的合取范式例如，例如，n=3, 命題變項(xiàng)為命題變項(xiàng)為 p, q, r 時(shí)，時(shí)， ( p

17、q r) ( p q r) m1 m3 主析取范式主析取范式 (p qr) ( pqr) M1 M7主合取范式主合取范式公式公式A的主析取的主析取(合取合取)范式范式與與A 等值的主析取等值的主析取(合取合取)范式范式 定理定理2.5 (主范式的存在惟一定理主范式的存在惟一定理) 任何命題公式都存在與之等值的主析取范式和主合取范式任何命題公式都存在與之等值的主析取范式和主合取范式,并且是惟一的并且是惟一的23求公式主范式的步驟求公式主范式的步驟求公式主析取范式的步驟求公式主析取范式的步驟:設(shè)公式設(shè)公式A含命題變項(xiàng)含命題變項(xiàng)p1,p2,pn(1) 求求A的析取范式的析取范式A =B1 B2 Bs

18、 , 其中其中Bj是簡(jiǎn)單合取是簡(jiǎn)單合取 式式 j=1,2, ,s (2) 若某個(gè)若某個(gè)Bj既不含既不含pi, 又不含又不含 pi, 則將則將Bj展開成展開成 Bj Bj (pi pi) (Bj pi) (Bj pi) 重復(fù)這個(gè)過程重復(fù)這個(gè)過程, 直到所有簡(jiǎn)單合取式都是長(zhǎng)度為直到所有簡(jiǎn)單合取式都是長(zhǎng)度為n的極的極 小項(xiàng)為止小項(xiàng)為止(3) 消去重復(fù)出現(xiàn)的極小項(xiàng)消去重復(fù)出現(xiàn)的極小項(xiàng), 即用即用mi代替代替mi mi(4) 將極小項(xiàng)按下標(biāo)從小到大排列將極小項(xiàng)按下標(biāo)從小到大排列24求公式主范式的步驟求公式主范式的步驟求公式的主合取范式的步驟求公式的主合取范式的步驟:設(shè)公式設(shè)公式A含命題變項(xiàng)含命題變項(xiàng)p1

19、,p2,pn(1) 求求A的合取范式的合取范式A =B1 B2 Bs , 其中其中Bj是簡(jiǎn)單析取是簡(jiǎn)單析取 式式 j=1,2, ,s (2) 若某個(gè)若某個(gè)Bj既不含既不含pi, 又不含又不含 pi, 則將則將Bj展開成展開成 Bj Bj (pi pi) (Bj pi) (Bj pi) 重復(fù)這個(gè)過程重復(fù)這個(gè)過程, 直到所有簡(jiǎn)單析取式都是長(zhǎng)度為直到所有簡(jiǎn)單析取式都是長(zhǎng)度為n的極的極 大項(xiàng)為止大項(xiàng)為止(3) 消去重復(fù)出現(xiàn)的極大項(xiàng)消去重復(fù)出現(xiàn)的極大項(xiàng), 即用即用Mi代替代替Mi Mi(4) 將極大項(xiàng)按下標(biāo)從小到大排列將極大項(xiàng)按下標(biāo)從小到大排列25實(shí)例實(shí)例例例6 (1) 求公式求公式 A=(pq)r的主

20、析取范式和主合取范式的主析取范式和主合取范式 解解 (pq)r (p q) r （析取范式）（析取范式） (p q) (p q) ( r r) (p qr) (p q r) m6 m7 r ( p p) ( q q) r ( pq r) ( p q r) (pq r) (p q r) m1 m3 m5 m7 , 代入代入并排序，得并排序，得 (pq)r m1 m3 m5 m6 m7 （主析取范式）（主析取范式）26實(shí)例實(shí)例 (pq)r (p r) (q r) （合取范式）（合取范式） p r p (qq) r (p q r) (pq r) M0 M2 q r (pp) q r (p q r)

21、( p q r) M0 M4 , 代入代入 并排序，得并排序，得 (pq)r M0 M2 M4 （主合取范式（主合取范式）27主范式的應(yīng)用主范式的應(yīng)用1.1.求公式的成真成假賦求公式的成真成假賦值值 設(shè)公式設(shè)公式A含含n個(gè)命題變項(xiàng)個(gè)命題變項(xiàng), A的主析取范式有的主析取范式有s個(gè)極小項(xiàng)個(gè)極小項(xiàng), 則則A 有有s個(gè)成真賦值個(gè)成真賦值, 它們是極小項(xiàng)下標(biāo)的二進(jìn)制表示它們是極小項(xiàng)下標(biāo)的二進(jìn)制表示, 其余其余2n-s 個(gè)賦值都是成假賦值個(gè)賦值都是成假賦值 例如例如 (pq)r m1 m3 m5 m6 m7成真賦值為成真賦值為 001, 011, 101, 110, 111，成假賦值為成假賦值為 000,

22、 010, 100. 類似地，由主合取范式也立即求出成假賦值和成真賦值類似地，由主合取范式也立即求出成假賦值和成真賦值. 282. 判斷公式的類型判斷公式的類型 設(shè)設(shè)A含含n個(gè)命題變項(xiàng)個(gè)命題變項(xiàng). A為重言式為重言式 A的主析取范式含全部的主析取范式含全部2n個(gè)極小項(xiàng)個(gè)極小項(xiàng) A的主合取范式不含任何極大項(xiàng)的主合取范式不含任何極大項(xiàng), 記為記為1. A為矛盾式為矛盾式 A的主合析取范式含全部的主合析取范式含全部2n個(gè)極大項(xiàng)個(gè)極大項(xiàng) A的主析取范式不含任何極小項(xiàng)的主析取范式不含任何極小項(xiàng), 記為記為0. A為非重言式的可滿足式為非重言式的可滿足式 A的主析取范式中至少含一個(gè)、但不是全的主析取范式中

23、至少含一個(gè)、但不是全 部極小項(xiàng)部極小項(xiàng) A的主合取范式中至少含一個(gè)、但不是全的主合取范式中至少含一個(gè)、但不是全 部極大項(xiàng)部極大項(xiàng).主范式的應(yīng)用主范式的應(yīng)用29例例7 用主析取范式判斷公式的類型用主析取范式判斷公式的類型:(1) A (pq) q (2) B p(p q) (3) C (p q)r解解 (1) A ( p q) q ( pq) q 0 矛盾式矛盾式(2) B p (p q) 1 m0 m1 m2 m3 重言式重言式(3) C (p q) r ( pq) r ( pq r) ( pqr) ( pq r) ( p q r) (pq r) (p q r) m0 m1 m3 m5 m7

24、非重言式的可滿足式非重言式的可滿足式主范式的應(yīng)用主范式的應(yīng)用303. 判斷兩個(gè)公式是否等值判斷兩個(gè)公式是否等值例例8 用主析取范式判以下每一組公式是否等值用主析取范式判以下每一組公式是否等值 p(qr) 與與 (p q)r p(qr) 與與 (pq)r解解 p(qr) = m0 m1 m2 m3 m4 m5 m7 (p q)r = m0 m1 m2 m3 m4 m5 m7 (pq)r = m1 m3 m4 m5 m7顯見，顯見，中的兩公式等值，而中的兩公式等值，而的不等值的不等值.主范式的應(yīng)用主范式的應(yīng)用314. 解實(shí)際問題解實(shí)際問題例例9 某單位要從某單位要從A,B,C三人中選派若干人出國(guó)考

25、察三人中選派若干人出國(guó)考察, 需滿足下需滿足下 述條件述條件: (1) 若若A去去, 則則C必須去必須去; (2) 若若B去去, 則則C不能去不能去; (3) A和和B必須去一人且只能去一人必須去一人且只能去一人. 問有幾種可能的選派方案問有幾種可能的選派方案?解解 記記 p:派派A去去, q:派派B去去, r:派派C去去(1) pr, (2) qr, (3) (pq) ( p q)求下式的成真賦值求下式的成真賦值 A=(pr) (qr) (pq) ( p q)主范式的應(yīng)用主范式的應(yīng)用32求求A的主析取范式的主析取范式 A=(pr) (qr) (pq) ( p q) ( p r) ( qr)

26、(pq) ( p q) ( pq) ( pr) (rq) (rr) (pq) ( p q) ( pq) (pq) ( pr) (pq) (rq) (pq) ( pq) ( p q) ( pr) ( p q) (rq) ( p q) (pq r) ( p qr)成真賦值成真賦值:101,010結(jié)論結(jié)論: 方案方案1 派派A與與C去去, 方案方案2 派派B去去主范式的應(yīng)用主范式的應(yīng)用33由主析取范式確定主合取范式由主析取范式確定主合取范式例例10 設(shè)設(shè)A有有3個(gè)命題變項(xiàng)個(gè)命題變項(xiàng), 且已知且已知A= m1 m3 m7, 求求A的主合取的主合取范式范式.解解 A的成真賦值是的成真賦值是1,3,7的二

27、進(jìn)制表示的二進(jìn)制表示, 成假賦值是在主析取成假賦值是在主析取范式中沒有出現(xiàn)的極小項(xiàng)的下角標(biāo)范式中沒有出現(xiàn)的極小項(xiàng)的下角標(biāo)0,2,4,5,6的二進(jìn)制表示的二進(jìn)制表示, 它它們恰好是們恰好是A的主合取范式的極大項(xiàng)的下角標(biāo)的主合取范式的極大項(xiàng)的下角標(biāo), 故故 A M0 M2 M4 M5 M6用成真賦值和成假賦值確定主范式用成真賦值和成假賦值確定主范式由主合取范式確定主析取范式由主合取范式確定主析取范式用真值表確定主范式用真值表確定主范式 342.3 聯(lián)結(jié)詞的完備集聯(lián)結(jié)詞的完備集定義定義2.6 稱稱F:0,1n 0,1 為為n元真值函數(shù)元真值函數(shù). 0,1n=000, 001, , 111，包含，包含

28、 個(gè)長(zhǎng)為個(gè)長(zhǎng)為n的的0,1符號(hào)串符號(hào)串. 共有共有 個(gè)個(gè)n元真值函數(shù)元真值函數(shù). n22n221元真值函數(shù)元真值函數(shù) p 0 0 0 1 1 1 0 1 0 1 )1(3)1(2)1(1)1(0FFFF35真值函數(shù)真值函數(shù)p q0 00 11 01 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1p q0 00 11 01 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1)2(7)2(6)2(5)2(4)2(3)2(2)2(1)2(

29、0FFFFFFFF)2(15)2(14)2(13)2(12)2(11)2(10)2(9)2(8FFFFFFFF2元真值函數(shù)元真值函數(shù)36公式與真值函數(shù)公式與真值函數(shù))2(13F任何一個(gè)含任何一個(gè)含n個(gè)命題變項(xiàng)的命題公式個(gè)命題變項(xiàng)的命題公式A都對(duì)應(yīng)惟一的一個(gè)都對(duì)應(yīng)惟一的一個(gè)n元元真值函數(shù)真值函數(shù) F , F 恰好為恰好為A的真值表的真值表. 等值的公式對(duì)應(yīng)的真值函數(shù)相同等值的公式對(duì)應(yīng)的真值函數(shù)相同. 例如：例如：pq, p q 都對(duì)應(yīng)都對(duì)應(yīng)37聯(lián)結(jié)詞完備集聯(lián)結(jié)詞完備集定義定義2.7 設(shè)設(shè)S是一個(gè)聯(lián)結(jié)詞集合，如果任何是一個(gè)聯(lián)結(jié)詞集合，如果任何n(n 1) 元真值函元真值函數(shù)都可以由僅含數(shù)都可以由僅

30、含S中的聯(lián)結(jié)詞構(gòu)成的公式表示，則稱中的聯(lián)結(jié)詞構(gòu)成的公式表示，則稱S是是聯(lián)結(jié)聯(lián)結(jié)詞完備集詞完備集若若S是聯(lián)結(jié)詞完備集是聯(lián)結(jié)詞完備集, 則任何命題公式都可由則任何命題公式都可由S中的聯(lián)結(jié)詞表示中的聯(lián)結(jié)詞表示定理定理2.6 S = , , 是聯(lián)結(jié)詞完備集是聯(lián)結(jié)詞完備集證明證明 由范式存在定理可證由范式存在定理可證38聯(lián)結(jié)詞完備集聯(lián)結(jié)詞完備集推論推論 以下都是聯(lián)結(jié)詞完備集以下都是聯(lián)結(jié)詞完備集 (1) S1 = , , , (2) S2 = , , , , (3) S3 = , (4) S4 = , (5) S5 = , 證明證明(1),(2) 在聯(lián)結(jié)詞完備集中加入新的聯(lián)結(jié)詞后仍為完備集在聯(lián)結(jié)詞完備集中

31、加入新的聯(lián)結(jié)詞后仍為完備集(3) A B ( AB)(4) A B ( AB)(5) ABA B , ,不是聯(lián)結(jié)詞完備集不是聯(lián)結(jié)詞完備集, 0不能用它表示不能用它表示它的子集它的子集 , , , , , ,等都不是等都不是39復(fù)合聯(lián)結(jié)詞復(fù)合聯(lián)結(jié)詞定義定義2.8 設(shè)設(shè) p, q 為兩個(gè)命題為兩個(gè)命題, (p q)稱作稱作p與與q的的與非式與非式, 記作記作p q, 即即 p q (p q), 稱為稱為與非聯(lián)結(jié)詞與非聯(lián)結(jié)詞 (p q) 稱作稱作 p 與與 q 的的或非式或非式, 記作記作 p q, 即即 p q (p q), 稱為稱為或非聯(lián)結(jié)詞或非聯(lián)結(jié)詞定理定理2.7 與與 為聯(lián)結(jié)詞完備集為聯(lián)結(jié)詞

32、完備集. 證明證明 , , 為完備集為完備集 p pp (p p) p p p q ( pq) pq (p p) (q q) p q (p q) (p q) (p q) (p q) 得證得證 為聯(lián)結(jié)詞完備集為聯(lián)結(jié)詞完備集. 對(duì)對(duì) 類似可證類似可證402.4 可滿足性問題與消解法可滿足性問題與消解法不含任何文字的簡(jiǎn)單析取式稱作不含任何文字的簡(jiǎn)單析取式稱作空簡(jiǎn)單析取式空簡(jiǎn)單析取式, ,記作記作 . .規(guī)定規(guī)定 是不可滿足的是不可滿足的. . 約定約定: :簡(jiǎn)單析取式不同時(shí)含某個(gè)命題變項(xiàng)和它的否定簡(jiǎn)單析取式不同時(shí)含某個(gè)命題變項(xiàng)和它的否定S:合取范式合取范式, C:簡(jiǎn)單析取式簡(jiǎn)單析取式, l:文字文字

33、, :賦值賦值, 帶下角標(biāo)或帶下角標(biāo)或 文字文字l的補(bǔ)的補(bǔ)lc:若若l=p,則則lc= p;若若l= p,則則lc=p.S S :S是可滿足的當(dāng)且僅當(dāng)是可滿足的當(dāng)且僅當(dāng)S 是可滿足的是可滿足的定義定義2.9 設(shè)設(shè)C1=l C1 , C2=lc C2 , C1 和和C2 不含不含l和和lc, 稱稱C1C2 為為C1和和C2(以以l和和lc為為消解文字消解文字)的的消解式消解式或或消解結(jié)果消解結(jié)果, 記作記作Res(C1,C2)例如例如, Res( p q r, p qs)= q rs41消解規(guī)則消解規(guī)則定理定理2.8 C1 C2 Res(C1,C2)證證 記記C= Res(C1,C2)=C1C2

34、 , 其中其中l(wèi)和和lc為消解文字為消解文字, C1=l C1 , C2=lc C2 , 且且C1 和和C2 不含不含l和和lc. 假設(shè)假設(shè)C1 C2是可滿足的是可滿足的, 是它的滿足賦值是它的滿足賦值, 不妨設(shè)不妨設(shè) (l)=1. C2必含有文字必含有文字l l, lc且且 (l )=1. C中含有中含有l(wèi) , 故故 滿足滿足C. 反之反之, 假設(shè)假設(shè)C是可滿足的是可滿足的, 是它的滿足賦值是它的滿足賦值. C必有必有l(wèi) 使得使得 (l )=1, 不妨設(shè)不妨設(shè)C1 含含l , 于是于是 滿足滿足C1. 把擴(kuò)張到把擴(kuò)張到l(和和lc)上上:若若l=p, 則令則令 (p)=0; 若若lc=p,

35、則令則令 (p)=1. 恒有恒有 (lc)=1, 從而從而 滿足滿足C2. 得證得證C1 C2是可滿足的是可滿足的.注意注意: C1 C2與與Res(C1,C2)有相同的可滿足性有相同的可滿足性, 但不一定等值但不一定等值.42消解序列與合取范式的否證消解序列與合取范式的否證定義定義2.10 設(shè)設(shè)S是一個(gè)合取范式是一個(gè)合取范式, C1,C2,Cn是一個(gè)簡(jiǎn)單析取式是一個(gè)簡(jiǎn)單析取式序列序列. 如果對(duì)每一個(gè)如果對(duì)每一個(gè)i(1 i n), Ci是是S的一個(gè)簡(jiǎn)單析取式或者是的一個(gè)簡(jiǎn)單析取式或者是Res(Cj,Ck)(1 jki), 則稱此序列是由則稱此序列是由S導(dǎo)出導(dǎo)出Cn的的消解序列消解序列. 當(dāng)當(dāng)C

36、n= 時(shí)時(shí), 稱此序列是稱此序列是S的一個(gè)的一個(gè)否證否證.定理定理2.9 一個(gè)合取范式是不可滿足的當(dāng)且僅當(dāng)它有否證一個(gè)合取范式是不可滿足的當(dāng)且僅當(dāng)它有否證.例例11 用消解規(guī)則證明用消解規(guī)則證明S=( p q) (p qs) (q s)q是不可是不可滿足的滿足的.證證 C1= p q, C2= p qs, C3=Res(C1,C2)=qs, C4=q s, C5=Res(C3,C4)=q, C6= q, C7=Res(C5,C6)= , 這是這是S的否證的否證.43消解算法消解算法消解算法消解算法輸入輸入: 合式公式合式公式A輸出輸出: 當(dāng)當(dāng)A是可滿足時(shí)是可滿足時(shí), 回答回答“Yes”; 否則

37、回答否則回答“No”.1. 求求A的合取范式的合取范式S2. 令令S0, S2, S1S的所有簡(jiǎn)單析取式的所有簡(jiǎn)單析取式3. For C1 S0和和C2 S14. If C1, C2可以消解可以消解 then5. 計(jì)算計(jì)算CRes(C1,C2)6. If C= then7. 輸出輸出“No”, 計(jì)算結(jié)束計(jì)算結(jié)束 8. If C S0且且C S1 then9. S2S2 C44消解算法消解算法10. For C1 S1, C2 S1且且C1 C211. If C1, C2可以消解可以消解 then12. 計(jì)算計(jì)算CRes(C1,C2)13. If C= then14. 輸出輸出“No”, 計(jì)算結(jié)

38、束計(jì)算結(jié)束 15. If C S0且且C S1 then16. S2S2 C17. If S2= then 18. 輸出輸出“Yes”, 計(jì)算結(jié)束計(jì)算結(jié)束19. Else S0S0 S1, S1S2, S2, goto 345消解算法例題消解算法例題例例12 用消解算法判斷下述公式是否是可滿足的用消解算法判斷下述公式是否是可滿足的: p (p q) (pq) (qr) (q r)解解 S= p (p q) (pq) (qr) (q r)循環(huán)循環(huán)1 S0=, S1=p, p q, pq, qr, q r, S2= Res(p q, pq)=p Res(pq, qr)=pr Res(pq, q r

39、)= p r Res(qr, q r)=q S2=p r, p r, q循環(huán)循環(huán)2 S0=p, p q, pq, qr, q r, S1=p r, p r, q, S2= Res(pq, q)=p46消解算法例題消解算法例題 Res(qr, p r)=p q Res(q r, pr)=p q Res(p r, pr)=p S2= 輸出輸出“Yes”47第二章第二章 習(xí)題課習(xí)題課主要內(nèi)容主要內(nèi)容l等值式與等值演算等值式與等值演算l基本等值式（基本等值式（1616組，組，2424個(gè)公式）個(gè)公式）l主析取范式與主合取范式主析取范式與主合取范式l聯(lián)結(jié)詞完備集聯(lián)結(jié)詞完備集l消解法消解法48基本要求基本要

40、求l 深刻理解等值式的概念深刻理解等值式的概念l 牢記基本等值式的名稱及它們的內(nèi)容牢記基本等值式的名稱及它們的內(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)的概念、名稱及下角標(biāo)與成真、深刻理解極小項(xiàng)、極大項(xiàng)的概念、名稱及下角標(biāo)與成真、成假賦值的關(guān)系，并理解簡(jiǎn)單析取式與極小項(xiàng)的關(guān)系成假賦值的關(guān)系，并理解簡(jiǎn)單析取式與極小項(xiàng)的關(guān)系l 熟練掌握求主范式的方法（等值演算、真值表等）熟練掌握求主范式的方法（等值演算、

41、真值表等）l 會(huì)用主范式求公式的成真賦值、成假賦值、判斷公式的類會(huì)用主范式求公式的成真賦值、成假賦值、判斷公式的類型、判斷兩個(gè)公式是否等值型、判斷兩個(gè)公式是否等值l 會(huì)將公式等值地化成指定聯(lián)結(jié)詞完備集中的公式會(huì)將公式等值地化成指定聯(lián)結(jié)詞完備集中的公式l 會(huì)用命題邏輯的概念及運(yùn)算解決簡(jiǎn)單的應(yīng)用問題會(huì)用命題邏輯的概念及運(yùn)算解決簡(jiǎn)單的應(yīng)用問題l 掌握消解規(guī)則及其性質(zhì)掌握消解規(guī)則及其性質(zhì)l 會(huì)用消解算法判斷公式的可滿足性會(huì)用消解算法判斷公式的可滿足性49練習(xí)練習(xí)1:概念概念1. 設(shè)設(shè)A與與B為含為含n個(gè)命題變項(xiàng)的公式，判斷下列命題是否為真？個(gè)命題變項(xiàng)的公式，判斷下列命題是否為真？(1) AB當(dāng)且僅當(dāng)當(dāng)

42、且僅當(dāng)A與與B有相同的主析取范式有相同的主析取范式(2) 若若A為重言式，則為重言式，則A的主合取范式為的主合取范式為0(3) 若若A為矛盾式，則為矛盾式，則A的主析取范式為的主析取范式為1(4) 任何公式都能等值地化成任何公式都能等值地化成 , 中的公式中的公式(5) 任何公式都能等值地化成任何公式都能等值地化成 , , 中的公式中的公式說明說明:(2) 重言式的主合取范式不含任何極大項(xiàng)，為重言式的主合取范式不含任何極大項(xiàng)，為1. (3) 矛盾式的主合析范式不含任何極小項(xiàng)矛盾式的主合析范式不含任何極小項(xiàng), 為為0. (4) , 不是完備集，如矛盾式不能寫成不是完備集，如矛盾式不能寫成 , 中

43、的公式中的公式. (5) , 是完備集是完備集. 真真假假假假假假真真50練習(xí)練習(xí)2: 判斷公式類型判斷公式類型解解 用等值演算法求主范式用等值演算法求主范式 (pq)( qp) ( p q) (qp) (pq) (qp) (pq) ( p q) (p q) ( pq) m2 m1 m3 m0 m0 m1 m2 m3 主析取范式主析取范式 1 主合取范式主合取范式2. 判斷下列公式的類型判斷下列公式的類型: (1) (pq)( qp)重言式重言式51練習(xí)題練習(xí)題2(續(xù)續(xù))解解 用等值演算法求公式的主范式用等值演算法求公式的主范式 (pq) q ( p q) q pq q 0 主析取范式主析取范

44、式 M0 M1 M2 M3 主合取范式主合取范式(2) (pq) q矛盾式矛盾式52解解 用等值演算法求公式的主范式用等值演算法求公式的主范式 (pq)p ( p q)p p ( pq) ( p q) m0 m1 主析取范式主析取范式 M2 M3 主合取范式主合取范式(3) (pq)p練習(xí)練習(xí)2(續(xù)續(xù))非重言式的可滿足式非重言式的可滿足式53練習(xí)練習(xí)3：求公式的主范式求公式的主范式3已知命題公式已知命題公式A中含中含3個(gè)命題變項(xiàng)個(gè)命題變項(xiàng)p, q, r，并知道它的成真，并知道它的成真賦值為賦值為001, 010, 111, 求求A的主析取范式和主合取范式，及的主析取范式和主合取范式，及A對(duì)對(duì)應(yīng)

45、的真值函數(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 154練習(xí)練習(xí)4：聯(lián)結(jié)詞完備集聯(lián)結(jié)詞完備集4將將A = (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)55練習(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) 說明：答案不惟一說明：答案不惟一56練習(xí)練習(xí)5：應(yīng)用題：應(yīng)用題5. 某公司要從趙、錢、孫、李、周五名新畢業(yè)的大學(xué)生中選某公司要從趙、錢、孫、李、周五名新畢業(yè)的大學(xué)生中選派一些人出國(guó)學(xué)習(xí)派一些人出國(guó)學(xué)習(xí). 選派必須滿足以下條件：選派必須滿足以下條件：(1) 若趙去，錢也去