離散數(shù)學(xué)-屈婉玲-

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

2、) ( p q) ( r r) r為左邊公式的啞元為左邊公式的啞元. l用真值表可檢查兩個公式是否等值用真值表可檢查兩個公式是否等值請驗證：請驗證： 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蘊涵等值式蘊涵等值式 ABA B等價等值式等價等值式 AB(AB) (BA)假言易位假言易位 ABBA等價否定等值式等價否定等值式 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ì)：自反性、對稱性、傳遞性等值關(guān)系的性質(zhì)：自反性、對稱性、傳遞性 (2) 基本的等值式基本的等值式 (3) 置換規(guī)則（見置換規(guī)則（見3）3. 置換規(guī)則置換規(guī)則 設(shè)設(shè) (A) 是含公式是含公式 A 的命題公式，的命題公式， (B) 是用公式是用公式 B 置換置換 (A) 中所有的中所有的 A 后得到的命題公式后得到的命題公式 若若 BA，則，則 (B)(A)8等值演算的應(yīng)用舉例等值演算的應(yīng)用舉例證明兩個公式等值證明兩個公式等值例例2 證明證明 p(qr) (p q)r證證 p(qr) p ( q r) （蘊涵等

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

7、真賦值，是右邊的成假賦值邊的成假賦值 方法三方法三 先用等值演算化簡公式，然后再觀察先用等值演算化簡公式，然后再觀察 p(qr) pq r (pq)r ( p q) r(pq) r 更容易看出前面的兩個賦值分別是更容易看出前面的兩個賦值分別是左邊的成真賦左邊的成真賦 值和右邊的成假賦值值和右邊的成假賦值等值演算的應(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) （蘊涵等值式）（蘊涵等值式） q (pq) （德摩根律）（德摩根律） p (qq) （交換律，結(jié)合律）（交換律，結(jié)合律） p 0 （矛盾律）（矛盾律） 0 （零律）（零律）矛盾式矛盾式11判斷公式類型判斷公式類型(2) (pq)( qp) ( p q)(qp) （蘊涵等值式）（蘊涵等值式） ( 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) 文字文字命題變項及其否定的總稱命題變項及其否定的總稱(2) 簡單析取式簡單析取式有限個文字構(gòu)成的析取式有限個文字構(gòu)成的析取式 p, q, pq, p q r, (3) 簡單合取式簡單合取式有限個文字構(gòu)成的合取式有限個文字構(gòu)成的合取式 p, q, pq, p q r, (4) 析取范式析取范式由有限個簡單合取式組成的析取式由有限個簡單合取式組成的析取式 p, p q, pq, (pq) ( p qr) (q r)(5) 合取范式合取范式由有限

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

11、同時含有某個命題一個簡單合取式是矛盾式當(dāng)且僅當(dāng)它同時含有某個命題變項和它的否定式變項和它的否定式.定理定理2.2 (1) 一個析取范式是矛盾式當(dāng)且僅當(dāng)它每個簡單合一個析取范式是矛盾式當(dāng)且僅當(dāng)它每個簡單合取式都是矛盾式取式都是矛盾式.(2) 一個合取范式是重言式當(dāng)且僅當(dāng)它的每個簡單析取式都一個合取范式是重言式當(dāng)且僅當(dāng)它的每個簡單析取式都是重言式是重言式.15命題公式的范式命題公式的范式定理定理2.3（范式存在定理）（范式存在定理） 任何命題公式都存在與之等值的析取范式與合取范式任何命題公式都存在與之等值的析取范式與合取范式公式公式A的析取的析取(合取合取)范式范式與與A等值的等值的析取析取(合取

12、合取)范式范式求公式求公式A的范式的步驟：的范式的步驟： (1) 消去消去A中的中的, （若存在）（若存在） 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

13、)r解解 (1) (pq)r ( pq)r （消去（消去） pqr （結(jié)合律）（結(jié)合律）最后結(jié)果既是析取范式最后結(jié)果既是析取范式(由由3個簡單合取式組成的析取式個簡單合取式組成的析取式)，又，又是合取范式是合取范式(由一個簡單析取式組成的合取式由一個簡單析取式組成的合取式) 18 (2) (pq)r ( pq)r （消去第一個（消去第一個） ( pq) r （消去第二個（消去第二個） (p q) r （否定號內(nèi)移（否定號內(nèi)移德摩根律德摩根律) 析取范式析取范式 (p r) (q r) （ 對對 分配律）分配律） 合取范式合取范式求公式的范式求公式的范式19極小項與極大項極小項與極大項定義定義2

14、.4 在含有在含有n個命題變項的簡單合取式（簡單析取式）個命題變項的簡單合取式（簡單析取式）中，若每個命題變項均以文字的形式在其中出現(xiàn)且僅出現(xiàn)中，若每個命題變項均以文字的形式在其中出現(xiàn)且僅出現(xiàn)一次，而且第一次，而且第i個文字出現(xiàn)在左起第個文字出現(xiàn)在左起第i位上（位上（1 i n），稱這），稱這樣的簡單合取式（簡單析取式）為樣的簡單合取式（簡單析取式）為極小項極小項（極大項極大項）.幾點說明：幾點說明：l n個命題變項有個命題變項有2n個極小項和個極小項和2n個極大項個極大項l 2n個極小項（極大項）均互不等值個極小項（極大項）均互不等值l 用用mi表示第表示第i個極小項，其中個極小項，其中i是

15、該極小項成真賦值的十進(jìn)是該極小項成真賦值的十進(jìn)制表示制表示. 用用Mi表示第表示第i個極大項，其中個極大項，其中i是該極大項成假賦值是該極大項成假賦值的十進(jìn)制表示的十進(jìn)制表示. mi（Mi）稱為極小項（極大項）的名稱）稱為極小項（極大項）的名稱. 20實例實例由兩個命題變項由兩個命題變項 p, q 形成的極小項與極大項形成的極小項與極大項極小項極小項極大項極大項公式公式成真賦值成真賦值 名稱名稱公式公式成假賦值成假賦值名稱名稱 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實例實例極小項極

16、小項極大項極大項公式公式成真賦值成真賦值名稱名稱公式公式成假賦值成假賦值名稱名稱 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 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由三個命題變項由三個命題變項 p, q, r 形成的極小項與極大項形成的極小項與極大項. mi與與Mi的關(guān)系

17、：的關(guān)系： mi Mi, Mi mi 22主析取范式與主合取范式主析取范式與主合取范式主析取范式主析取范式由極小項構(gòu)成的析取范式由極小項構(gòu)成的析取范式主合取范式主合取范式由極大項構(gòu)成的合取范式由極大項構(gòu)成的合取范式例如，例如，n=3, 命題變項為命題變項為 p, q, r 時，時， ( pq r) ( p q r) m1 m3 主析取范式主析取范式 (p qr) ( pqr) M1 M7主合取范式主合取范式公式公式A的主析取的主析取(合取合取)范式范式與與A 等值的主析取等值的主析取(合取合取)范式范式 定理定理2.5 (主范式的存在惟一定理主范式的存在惟一定理) 任何命題公式都存在與之等值的

18、主析取范式和主合取范式任何命題公式都存在與之等值的主析取范式和主合取范式,并且是惟一的并且是惟一的23求公式主范式的步驟求公式主范式的步驟求公式主析取范式的步驟求公式主析取范式的步驟:設(shè)公式設(shè)公式A含命題變項含命題變項p1,p2,pn(1) 求求A的析取范式的析取范式A =B1 B2 Bs , 其中其中Bj是簡單合取是簡單合取 式式 j=1,2, ,s (2) 若某個若某個Bj既不含既不含pi, 又不含又不含 pi, 則將則將Bj展開成展開成 Bj Bj (pi pi) (Bj pi) (Bj pi) 重復(fù)這個過程重復(fù)這個過程, 直到所有簡單合取式都是長度為直到所有簡單合取式都是長度為n的極的

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

20、, 直到所有簡單析取式都是長度為直到所有簡單析取式都是長度為n的極的極 大項為止大項為止(3) 消去重復(fù)出現(xiàn)的極大項消去重復(fù)出現(xiàn)的極大項, 即用即用Mi代替代替Mi Mi(4) 將極大項按下標(biāo)從小到大排列將極大項按下標(biāo)從小到大排列25實例實例例例6 (1) 求公式求公式 A=(pq)r的主析取范式和主合取范式的主析取范式和主合取范式 解解 (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

21、, 代入代入并排序，得并排序，得 (pq)r m1 m3 m5 m6 m7 （主析取范式）（主析取范式）26實例實例 (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) ( p q r) M0 M4 , 代入代入 并排序，得并排序，得 (pq)r M0 M2 M4 （主合取范式（主合取范式）27主范式的應(yīng)用主范式的應(yīng)用1.1.求公式的成真成假賦求公式的成真成假賦值值 設(shè)公式設(shè)公式A含含n個命題變項個命題變項, A的主析取范式有的主析取范式有s個極小項個極小項, 則則A 有有s

22、個成真賦值個成真賦值, 它們是極小項下標(biāo)的二進(jìn)制表示它們是極小項下標(biāo)的二進(jìn)制表示, 其余其余2n-s 個賦值都是成假賦值個賦值都是成假賦值 例如例如 (pq)r m1 m3 m5 m6 m7成真賦值為成真賦值為 001, 011, 101, 110, 111，成假賦值為成假賦值為 000, 010, 100. 類似地，由主合取范式也立即求出成假賦值和成真賦值類似地，由主合取范式也立即求出成假賦值和成真賦值. 282. 判斷公式的類型判斷公式的類型 設(shè)設(shè)A含含n個命題變項個命題變項. A為重言式為重言式 A的主析取范式含全部的主析取范式含全部2n個極小項個極小項 A的主合取范式不含任何極大項的主

23、合取范式不含任何極大項, 記為記為1. A為矛盾式為矛盾式 A的主合析取范式含全部的主合析取范式含全部2n個極大項個極大項 A的主析取范式不含任何極小項的主析取范式不含任何極小項, 記為記為0. A為非重言式的可滿足式為非重言式的可滿足式 A的主析取范式中至少含一個、但不是全的主析取范式中至少含一個、但不是全 部極小項部極小項 A的主合取范式中至少含一個、但不是全的主合取范式中至少含一個、但不是全 部極大項部極大項.主范式的應(yīng)用主范式的應(yīng)用29例例7 用主析取范式判斷公式的類型用主析取范式判斷公式的類型:(1) A (pq) q (2) B p(p q) (3) C (p q)r解解 (1)

24、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 非重言式的可滿足式非重言式的可滿足式主范式的應(yīng)用主范式的應(yīng)用303. 判斷兩個公式是否等值判斷兩個公式是否等值例例8 用主析取范式判以下每一組公式是否等值用主析取范式判以下每一組公式是否等值 p(qr) 與與 (p q)r p(qr) 與與 (pq)r解解 p(qr) = m0 m1 m2 m3 m4 m5

25、m7 (p q)r = m0 m1 m2 m3 m4 m5 m7 (pq)r = m1 m3 m4 m5 m7顯見，顯見，中的兩公式等值，而中的兩公式等值，而的不等值的不等值.主范式的應(yīng)用主范式的應(yīng)用314. 解實際問題解實際問題例例9 某單位要從某單位要從A,B,C三人中選派若干人出國考察三人中選派若干人出國考察, 需滿足下需滿足下 述條件述條件: (1) 若若A去去, 則則C必須去必須去; (2) 若若B去去, 則則C不能去不能去; (3) A和和B必須去一人且只能去一人必須去一人且只能去一人. 問有幾種可能的選派方案問有幾種可能的選派方案?解解 記記 p:派派A去去, q:派派B去去,

26、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) (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é)論: 方案方

27、案1 派派A與與C去去, 方案方案2 派派B去去主范式的應(yīng)用主范式的應(yīng)用33由主析取范式確定主合取范式由主析取范式確定主合取范式例例10 設(shè)設(shè)A有有3個命題變項個命題變項, 且已知且已知A= m1 m3 m7, 求求A的主合取的主合取范式范式.解解 A的成真賦值是的成真賦值是1,3,7的二進(jìn)制表示的二進(jìn)制表示, 成假賦值是在主析取成假賦值是在主析取范式中沒有出現(xiàn)的極小項的下角標(biāo)范式中沒有出現(xiàn)的極小項的下角標(biāo)0,2,4,5,6的二進(jìn)制表示的二進(jìn)制表示, 它它們恰好是們恰好是A的主合取范式的極大項的下角標(biāo)的主合取范式的極大項的下角標(biāo), 故故 A M0 M2 M4 M5 M6用成真賦值和成假賦值確定

28、主范式用成真賦值和成假賦值確定主范式由主合取范式確定主析取范式由主合取范式確定主析取范式用真值表確定主范式用真值表確定主范式 342.3 聯(lián)結(jié)詞的完備集聯(lián)結(jié)詞的完備集定義定義2.6 稱稱F:0,1n 0,1 為為n元真值函數(shù)元真值函數(shù). 0,1n=000, 001, , 111，包含，包含 個長為個長為n的的0,1符號串符號串. 共有共有 個個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

29、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(0FFFFFFFF)2(15)2(14)2(13)2(12)2(11)2(10)2(9)2(8FFFFFFFF2元真值函數(shù)元真值函數(shù)36公式與真值函數(shù)公式與真值函數(shù))2(13F任何一個含任何一個含n個命題變項的命題公式個命題變項的命題公式A都對應(yīng)惟一的一個都對應(yīng)惟一的一個n元元真值函數(shù)真值函數(shù) F , F 恰

30、好為恰好為A的真值表的真值表. 等值的公式對應(yīng)的真值函數(shù)相同等值的公式對應(yīng)的真值函數(shù)相同. 例如：例如：pq, p q 都對應(yīng)都對應(yīng)37聯(lián)結(jié)詞完備集聯(lián)結(jié)詞完備集定義定義2.7 設(shè)設(shè)S是一個聯(lián)結(jié)詞集合，如果任何是一個聯(lián)結(jié)詞集合，如果任何n(n 1) 元真值函元真值函數(shù)都可以由僅含數(shù)都可以由僅含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é)詞完備集證明證明 由范式存在定理可證由范式存在定理可證3

31、8聯(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é)詞完備集中加入新的聯(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 為兩個命題為兩個命題, (p q

32、)稱作稱作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é)詞完備集. 證明證明 , , 為完備集為完備集 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é)詞完備集. 對對 類似可證類似可證402.4 可滿足性問題與消解法可滿足性問題與消解法不含任何文字

33、的簡單析取式稱作不含任何文字的簡單析取式稱作空簡單析取式空簡單析取式, ,記作記作 . .規(guī)定規(guī)定 是不可滿足的是不可滿足的. . 約定約定: :簡單析取式不同時含某個命題變項和它的否定簡單析取式不同時含某個命題變項和它的否定S:合取范式合取范式, C:簡單析取式簡單析取式, l:文字文字, :賦值賦值, 帶下角標(biāo)或帶下角標(biāo)或 文字文字l的補的補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 為為

34、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 , 其中其中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)

35、 , 故故 滿足滿足C. 反之反之, 假設(shè)假設(shè)C是可滿足的是可滿足的, 是它的滿足賦值是它的滿足賦值. C必有必有l(wèi) 使得使得 (l )=1, 不妨設(shè)不妨設(shè)C1 含含l , 于是于是 滿足滿足C1. 把擴張到把擴張到l(和和lc)上上:若若l=p, 則令則令 (p)=0; 若若lc=p, 則令則令 (p)=1. 恒有恒有 (lc)=1, 從而從而 滿足滿足C2. 得證得證C1 C2是可滿足的是可滿足的.注意注意: C1 C2與與Res(C1,C2)有相同的可滿足性有相同的可滿足性, 但不一定等值但不一定等值.42消解序列與合取范式的否證消解序列與合取范式的否證定義定義2.10 設(shè)設(shè)S是一個合取

36、范式是一個合取范式, C1,C2,Cn是一個簡單析取式是一個簡單析取式序列序列. 如果對每一個如果對每一個i(1 i n), Ci是是S的一個簡單析取式或者是的一個簡單析取式或者是Res(Cj,Ck)(1 jki), 則稱此序列是由則稱此序列是由S導(dǎo)出導(dǎo)出Cn的的消解序列消解序列. 當(dāng)當(dāng)Cn= 時時, 稱此序列是稱此序列是S的一個的一個否證否證.定理定理2.9 一個合取范式是不可滿足的當(dāng)且僅當(dāng)它有否證一個合取范式是不可滿足的當(dāng)且僅當(dāng)它有否證.例例11 用消解規(guī)則證明用消解規(guī)則證明S=( p q) (p qs) (q s)q是不可是不可滿足的滿足的.證證 C1= p q, C2= p qs, C

37、3=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是可滿足時是可滿足時, 回答回答“Yes”; 否則回答否則回答“No”.1. 求求A的合取范式的合取范式S2. 令令S0, S2, S1S的所有簡單析取式的所有簡單析取式3. For C1 S0和和C2 S14. If C1, C2可以消解可以消解 then5. 計算計算CRes(C1,C2)6. If C= then7. 輸出輸出“No”, 計算結(jié)束計算結(jié)

38、束 8. If C S0且且C S1 then9. S2S2 C44消解算法消解算法10. For C1 S1, C2 S1且且C1 C211. If C1, C2可以消解可以消解 then12. 計算計算CRes(C1,C2)13. If C= then14. 輸出輸出“No”, 計算結(jié)束計算結(jié)束 15. If C S0且且C S1 then16. S2S2 C17. If S2= then 18. 輸出輸出“Yes”, 計算結(jié)束計算結(jié)束19. Else S0S0 S1, S1S2, S2, goto 345消解算法例題消解算法例題例例12 用消解算法判斷下述公式是否是可滿足的用消解算法判斷

39、下述公式是否是可滿足的: 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)= 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,

40、 pr)=p S2= 輸出輸出“Yes”47第二章第二章 習(xí)題課習(xí)題課主要內(nèi)容主要內(nèi)容l等值式與等值演算等值式與等值演算l基本等值式（基本等值式（1616組，組，2424個公式）個公式）l主析取范式與主合取范式主析取范式與主合取范式l聯(lián)結(jié)詞完備集聯(lián)結(jié)詞完備集l消解法消解法48基本要求基本要求l 深刻理解等值式的概念深刻理解等值式的概念l 牢記基本等值式的名稱及它們的內(nèi)容牢記基本等值式的名稱及它們的內(nèi)容l 熟練地應(yīng)用基本等值式及置換規(guī)則進(jìn)行等值演算熟練地應(yīng)用基本等值式及置換規(guī)則進(jìn)行等值演算l 理解文字、簡單析取式、簡單合取式、析取范式、合取范理解文字、簡單析取式、簡單合取式、析取范式、合取范式的

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

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

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

44、2 m3 主析取范式主析取范式 1 主合取范式主合取范式2. 判斷下列公式的類型判斷下列公式的類型: (1) (pq)( qp)重言式重言式51練習(xí)題練習(xí)題2(續(xù)續(xù))解解 用等值演算法求公式的主范式用等值演算法求公式的主范式 (pq) q ( p q) q pq q 0 主析取范式主析取范式 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ù))非重言

45、式的可滿足式非重言式的可滿足式53練習(xí)練習(xí)3：求公式的主范式求公式的主范式3已知命題公式已知命題公式A中含中含3個命題變項個命題變項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 154練習(xí)練習(xí)4：聯(lián)結(jié)詞完

46、備集聯(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é)生中選派一些人出國學(xué)習(xí)派一些人出國學(xué)習(xí). 選派必須滿足以下條件：選派必須滿足以下