離散數學(高教版)第2章

1、1主要內容主要內容l 等值式與基本的等值式等值式與基本的等值式l 等值演算與置換規(guī)則等值演算與置換規(guī)則l 析取范式與合取范式，主析取范式與主合取范式析取范式與合取范式，主析取范式與主合取范式l 聯(lián)結詞完備集聯(lián)結詞完備集l 可滿足性問題與消解法可滿足性問題與消解法第二章第二章 命題邏輯等值演算命題邏輯等值演算22.1 等值式等值式定義定義2.1 若等價式若等價式AB是重言式，則稱是重言式，則稱A與與B等值等值，記作，記作AB，并稱，并稱AB是是等值式等值式幾點說明：幾點說明：l定義中，定義中，A, B, 均為元語言符號均為元語言符號l A或或B中可能有啞元出現中可能有啞元出現. 例如例如 (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 結論結論: : 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 結論結論: : p(qr) 與與 (pq) r 不等值不等值5基本等值式基本等值式雙重否定律雙重否定律 AA冪等律冪等律 A AA, A AA交換律交換律 A BB A, A BB A結合律結合律 (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ù)學習的基礎組等值式，這是繼續(xù)學習的基礎7等值演算與置換規(guī)則等值演算與置換規(guī)則1. 等值演算等值演算由已知的等值式推演出新的等值式的過程由已知的等

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

6、規(guī)則）（蘊涵等值式，置換規(guī)則） ( pq) r （分配律，置換規(guī)則）（分配律，置換規(guī)則） (p q) r （德摩根律，置換規(guī)則）（德摩根律，置換規(guī)則） (p q)r （蘊涵等值式，置換規(guī)則）（蘊涵等值式，置換規(guī)則）今后在注明中省去置換規(guī)則今后在注明中省去置換規(guī)則注意：用等值演算不能直接證明兩個公式不等值注意：用等值演算不能直接證明兩個公式不等值9等值演算的應用舉例等值演算的應用舉例練習：練習：證明證明 p(qr) (p q)r證證 p(qr) p ( q r) （蘊涵等值式）（蘊涵等值式） ( pq) r （結合律）（結合律） (p q) r （德摩根律）（德摩根律） (p q)r （蘊涵等值

7、式）（蘊涵等值式）10證明兩個公式不等值證明兩個公式不等值例例3 證明證明 p(qr) 與與 (pq)r 不等值不等值證證 方法一方法一 真值表法真值表法, 見例見例1(2)方法二方法二 觀察法觀察法. 觀察到觀察到000, 010是左邊的成真賦值，是右是左邊的成真賦值，是右邊的成假賦值邊的成假賦值 方法三方法三 先用等值演算化簡公式，然后再觀察先用等值演算化簡公式，然后再觀察 p(qr) pq r (pq)r ( p q) r(pq) r 更容易看出前面的兩個賦值分別是更容易看出前面的兩個賦值分別是左邊的成真賦左邊的成真賦 值和右邊的成假賦值值和右邊的成假賦值等值演算的應用舉例等值演算的應用

8、舉例11判斷公式類型判斷公式類型: A為矛盾式當且僅當為矛盾式當且僅當A 0 A為重言式當且僅當為重言式當且僅當A 1例例4 用等值演算法判斷下列公式的類型用等值演算法判斷下列公式的類型 (1) q(pq) (2) (pq)( qp) (3) (p q) (pq) r) 等值演算的應用舉例等值演算的應用舉例解解 (1) q(pq) q( p q) （蘊涵等值式）（蘊涵等值式） q (pq) （德摩根律）（德摩根律） p (qq) （交換律，結合律）（交換律，結合律） p 0 （矛盾律）（矛盾律） 0 （零律）（零律）矛盾式矛盾式12判斷公式類型判斷公式類型(2) (pq)( qp) ( p q

9、)(qp) （蘊涵等值式）（蘊涵等值式） ( p q)( p q) （交換律）（交換律） 1重言式重言式(3) (p q) (pq) r) (p (qq) r （分配律）（分配律） p 1 r （排中律）（排中律） p r （同一律）（同一律）可滿足式，可滿足式，101和和111是成真賦值，是成真賦值，000和和010等是成假賦值等是成假賦值. 132.2 析取范式與合取范式析取范式與合取范式基本概念基本概念(1) 文字文字命題變項及其否定的總稱命題變項及其否定的總稱(2) 簡單析取式簡單析取式有限個文字構成的析取式（意味著不含有限個文字構成的析取式（意味著不含合取蘊含等價等聯(lián)結詞）合取蘊含等

10、價等聯(lián)結詞） p, q, pq, p q r, (p q) r(3) 簡單合取式簡單合取式有限個文字構成的合取式（意味著不含有限個文字構成的合取式（意味著不含析取蘊含等價等聯(lián)結詞）析取蘊含等價等聯(lián)結詞） p, q, pq, p q r, (pq) r(4) 析取范式析取范式由有限個簡單合取式組成的析取式由有限個簡單合取式組成的析取式 p, p q, pq, (pq) ( p qr) (q r)(5) 合取范式合取范式由有限個簡單析取式組成的合取式由有限個簡單析取式組成的合取式 p, pq, p q, (p qp (p q r)(6) 范式范式析取范式與合取范式的總稱析取范式與合取范式的總稱14

11、范式概念范式概念說明：說明：l 單個文字既是簡單析取式，又是簡單合取式單個文字既是簡單析取式，又是簡單合取式l 形如形如 pq r, p qr 的的公式既是析取范式，又是合取公式既是析取范式，又是合取范式范式15范式的性質范式的性質定理定理2.1 (1) 一個簡單析取式是重言式當且僅當它同時含有某一個簡單析取式是重言式當且僅當它同時含有某個命題變項和它的否定式個命題變項和它的否定式.(2) 一個簡單合取式是矛盾式當且僅當它同時含有某個命題一個簡單合取式是矛盾式當且僅當它同時含有某個命題變項和它的否定式變項和它的否定式.定理定理2.2 (1) 一個析取范式是矛盾式當且僅當它每個簡單合一個析取范式

12、是矛盾式當且僅當它每個簡單合取式都是矛盾式取式都是矛盾式.(2) 一個合取范式是重言式當且僅當它的每個簡單析取式都一個合取范式是重言式當且僅當它的每個簡單析取式都是重言式是重言式.16命題公式的范式命題公式的范式定理定理2.3（范式存在定理）（范式存在定理） 任何命題公式都存在與之等值的析取范式與合取范式任何命題公式都存在與之等值的析取范式與合取范式公式公式A的析取的析取(合取合取)范式范式與與A等值的等值的析取析取(合取合取)范式范式求公式求公式A的范式的步驟：的范式的步驟： (1) 消去消去A中的中的, （若存在）（若存在） ABA B AB( A B) (AB) (2) 否定聯(lián)結詞否定聯(lián)

13、結詞 的內移或消去的內移或消去 A A (A B)AB (A B)AB17命題公式的范式命題公式的范式 (3) 使用分配律使用分配律 A (B C)(A B) (A C) 求合取范式求合取范式 A (B C) (A B) (A C) 求析取范式求析取范式公式范式的不足公式范式的不足不惟一不惟一18求公式的范式求公式的范式例例7 求下列公式的析取范式與合取范式求下列公式的析取范式與合取范式 (pq) r解解 (1) 先求合取范式先求合取范式 (pq) r ( p q) r （消去（消去） ( p q) r ) (r ( p q) ) （消去（消去 ） ( ( p q) r ) ( r ( p q

14、) ) （消去（消去） ( (p q) r ) ( r ( p q) ) (否定符內移否定符內移) ( (p r) （ q r ) ( p qr) 19求公式的范式求公式的范式練習：求下列公式的析取范式與合取范式練習：求下列公式的析取范式與合取范式 (1) (pq)r (2) (pq)r解解 (1) (pq)r ( pq)r （消去（消去） pqr （結合律）（結合律）最后結果既是析取范式最后結果既是析取范式(由由3個簡單合取式組成的析取式個簡單合取式組成的析取式)，又，又是合取范式是合取范式(由一個簡單析取式組成的合取式由一個簡單析取式組成的合取式) 20 (2) (pq)r ( pq)r

15、（消去第一個（消去第一個） ( pq) r （消去第二個（消去第二個） (p q) r （否定號內移（否定號內移德摩根律德摩根律) 析取范式析取范式 (p r) (q r) （ 對對 分配律）分配律） 合取范式合取范式求公式的范式求公式的范式21極小項與極大項極小項與極大項定義定義2.4 在含有在含有n個命題變項的簡單合取式（簡單析取式）個命題變項的簡單合取式（簡單析取式）中，若每個命題變項和它的否定式在其中出現且僅出現中，若每個命題變項和它的否定式在其中出現且僅出現一次，而且命題變項和它的否定式按照下標從小到大或者按一次，而且命題變項和它的否定式按照下標從小到大或者按照字典順序排列，稱這樣的

16、簡單合取式（簡單析取式）為照字典順序排列，稱這樣的簡單合取式（簡單析取式）為極極小項小項（極大項極大項）.幾點說明：幾點說明：ln個命題變項有個命題變項有2n個極小項和個極小項和2n個極大項個極大項l2n個極小項（極大項）均互不等值個極小項（極大項）均互不等值l每個極小項有且僅有一個成真賦值，若該成真賦值所對應的二進制數等于十每個極小項有且僅有一個成真賦值，若該成真賦值所對應的二進制數等于十進制數進制數i，就將這個極小項記作，就將這個極小項記作mi. l每個極大項有且僅有一個成假賦值，若該成假賦值所對應的二進制數等于十每個極大項有且僅有一個成假賦值，若該成假賦值所對應的二進制數等于十進制數進制

17、數i，就將這個極大項記作，就將這個極大項記作 Mi22實例實例由兩個命題變項由兩個命題變項 p, q 形成的極小項與極大項形成的極小項與極大項極小項極小項極大項極大項公式公式成真賦值成真賦值名稱名稱公式公式成假賦值成假賦值名稱名稱 pq p qpqp q p q pq p q pq 0 0 0 1 1 0 1 1 m0m1m2m3 0 0 0 1 1 0 1 1M0M1M2M323實例實例極小項極小項極大項極大項公式公式成真賦值成真賦值名稱名稱公式公式成假賦值成假賦值名稱名稱 p q r p q r p q r p q rp q rp q rp q rp q r由三個命題變項由三個命題變項 p

18、, q, r 形成的極小項與極大項形成的極小項與極大項. mi與與Mi的關系：的關系： mi Mi, Mi mi 0 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 M0M1M2M3M4M5M6M724主析取范式與主合取范式主析取范式與主合取范式主析取范式主析取范式由極小項構成的析取范式由極小項構成的析取范式主合取范式主合取范式由極大項構成的合取范式由極大項

19、構成的合取范式例如，例如，n=3, 命題變項為命題變項為 p, q, r 時，時， ( pq r) ( p q r) m1 m3 (p qr) ( pqr) M1 M7公式公式A的主析取的主析取(合取合取)范式范式與與A 等值的主析取等值的主析取(合取合取)范式范式 定理定理2.5 (主范式的存在惟一定理主范式的存在惟一定理) 任何命題公式都存在與之等值的主析取范式和主合取范式任何命題公式都存在與之等值的主析取范式和主合取范式,并且是惟一的并且是惟一的主析取范式主析取范式 主合取范式主合取范式25求公式主范式的步驟求公式主范式的步驟求公式主析取范式的步驟求公式主析取范式的步驟:設公式設公式A含

20、命題變項含命題變項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) 重復這個過程重復這個過程, 直到所有簡單合取式都是長度為直到所有簡單合取式都是長度為n的極的極 小項為止小項為止(3) 消去重復出現的極小項消去重復出現的極小項, 即用即用mi代替代替mi mi(4) 將極小項按下標從小到大排列將極小項按下標從小到大排列26求公式主范式的步驟求公式主范式的步

21、驟求公式的主合取范式的步驟求公式的主合取范式的步驟:設公式設公式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) 重復這個過程重復這個過程, 直到所有簡單析取式都是長度為直到所有簡單析取式都是長度為n的極的極 大項為止大項為止(3) 消去重復出現的極大項消去重復出現的極大項, 即用即用Mi代替代替Mi Mi(4) 將極大項按下標從小到大

22、排列將極大項按下標從小到大排列27例例2.9：求公式：求公式 pq 的主析取范式和主合取范式的主析取范式和主合取范式 解解 (1) 求主合取范式求主合取范式 pq p q M2 （2）主析取范式）主析取范式 pq p q ( p ( q q) (q ( p p) ( pq) ( p q) (q p) (q p) ( pq) ( p q) (q p) m0 m1 m3 28實例實例練習：練習：(1) 求公式求公式 A=(pq)r的主析取范式和主合取范式的主析取范式和主合取范式 解解 (pq)r (p q) r （析取范式）（析取范式） (p q) (p q) ( r r) (p qr) (p q

23、 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 （主析取范式）（主析取范式）29實例實例 (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 （主合取范式（主合取范式）30主范式的應用主范式的應用1.1.求公式的

24、成真成假賦求公式的成真成假賦值值 設公式設公式A含含n個命題變項個命題變項, A的主析取范式有的主析取范式有s個極小項個極小項, 則則A 有有s個成真賦值個成真賦值, 它們是極小項下標的二進制表示它們是極小項下標的二進制表示, 其余其余2n-s 個賦值都是成假賦值個賦值都是成假賦值 例如例如 (pq)r m1 m3 m5 m6 m7成真賦值為成真賦值為 001, 011, 101, 110, 111，成假賦值為成假賦值為 000, 010, 100. 類似地，由主合取范式也立即求出成假賦值和成真賦值類似地，由主合取范式也立即求出成假賦值和成真賦值. 312. 判斷公式的類型判斷公式的類型 設設

25、A含含n個命題變項個命題變項. A為重言式為重言式 A的主析取范式含全部的主析取范式含全部2n個極小項個極小項 A的主合取范式不含任何極大項的主合取范式不含任何極大項, 記為記為1. A為矛盾式為矛盾式 A的主合析取范式含全部的主合析取范式含全部2n個極大項個極大項 A的主析取范式不含任何極小項的主析取范式不含任何極小項, 記為記為0. A為非重言式的可滿足式為非重言式的可滿足式 A的主析取范式中至少含一個、但不是全的主析取范式中至少含一個、但不是全 部極小項部極小項 A的主合取范式中至少含一個、但不是全的主合取范式中至少含一個、但不是全 部極大項部極大項.主范式的應用主范式的應用32例例10

26、 用主析取范式判斷公式的類型用主析取范式判斷公式的類型:(1) (pq) q (2) p(p q) (3) (p q)r解解 (1) (pq) q ( ) q 0 矛盾式矛盾式主范式的應用主范式的應用 p q ( ) q pq33(2) p(p q) 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 非重言式的可滿足式非重言式的可滿足式主范式的應用主范式的應用34(2) B p(p q) (3) C (p q)r解解 (1

27、) 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 非重言式的可滿足式非重言式的可滿足式主范式的應用主范式的應用3536 判斷兩個公式是否等值判斷兩個公式是否等值 設公式設公式A,B共含有共含有n個命題變項，按個命題變項，按n個命題變項求出個命題變項求出A與與B的主析取范式的主析取范式A1與與B1,如果如果A1=B1，則，則A B，否則，否則A B例例11

28、 判斷下面兩組公式是否等值判斷下面兩組公式是否等值 (1) p與與(p q) (p q）主范式的應用主范式的應用37 (2) p(qr) 與 (pq)r 解 公式中含有3個命題變項，因而極小項含3個文字。 p(qr) p(qr) p(qr) = m0m1m2m3 m4m5 m7 (pq)r = m0m1m2m3 m4m5 m7 (pq)r = m1m3 m4m5 m7顯見，中的兩公式等值，而的不等值.384. 解實際問題解實際問題例例9 某單位要從某單位要從A,B,C三人中選派若干人出國考察三人中選派若干人出國考察, 需滿足下需滿足下 述條件述條件: (1) 若若A去去, 則則C必須去必須去;

29、 (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)主范式的應用主范式的應用39求求A的主析取范式的主析取范式 A=(pr) (qr) (pq) ( p q) ( p r) ( qr) (pq) ( p q) ( pq) ( pr) (rq) (rr) (pq) ( p q) ( pq) (

30、pq) ( pr) (pq) (rq) (pq) ( pq) ( p q) ( pr) ( p q) (rq) ( p q) (pq r) ( p qr)成真賦值成真賦值:101,010結論結論: 方案方案1 派派A與與C去去, 方案方案2 派派B去去主范式的應用主范式的應用40由主析取范式確定主合取范式由主析取范式確定主合取范式例例10 設設A有有3個命題變項個命題變項, 且已知且已知A= m1 m3 m7, 求求A的主合取的主合取范式范式.解解 A的成真賦值是的成真賦值是1,3,7的二進制表示的二進制表示, 成假賦值是在主析取成假賦值是在主析取范式中沒有出現的極小項的下角標范式中沒有出現的

31、極小項的下角標0,2,4,5,6的二進制表示的二進制表示, 它它們恰好是們恰好是A的主合取范式的極大項的下角標的主合取范式的極大項的下角標, 故故 A M0 M2 M4 M5 M6用成真賦值和成假賦值確定主范式用成真賦值和成假賦值確定主范式由主合取范式確定主析取范式由主合取范式確定主析取范式用真值表確定主范式用真值表確定主范式 412.3 聯(lián)結詞的完備集聯(lián)結詞的完備集定義定義2.6 稱稱F:0,1n 0,1 為為n元真值函數元真值函數. 0,1n=000, 001, , 111，包含，包含 個長為個長為n的的0,1符號串符號串. 共有共有 個個n元真值函數元真值函數. n22n221元真值函數

32、元真值函數 p 0 0 0 1 1 1 0 1 0 1 )1(3)1(2)1(1)1(0FFFF42真值函數真值函數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(0FFFFFFFF)2(15)2(14)2(13)2(12)2(11)2(10)2(9)2(8FFFFFF

33、FF2元真值函數元真值函數43公式與真值函數公式與真值函數)2(13F任何一個含任何一個含n個命題變項的命題公式個命題變項的命題公式A都對應惟一的一個都對應惟一的一個n元元真值函數真值函數 F , F 恰好為恰好為A的真值表的真值表. 等值的公式對應的真值函數相同等值的公式對應的真值函數相同. 例如：例如：pq, p q 都對應都對應44聯(lián)結詞完備集聯(lián)結詞完備集定義定義2.7 設設S是一個聯(lián)結詞集合，如果任何是一個聯(lián)結詞集合，如果任何n(n 1) 元真值函元真值函數都可以由僅含數都可以由僅含S中的聯(lián)結詞構成的公式表示，則稱中的聯(lián)結詞構成的公式表示，則稱S是是聯(lián)結聯(lián)結詞完備集詞完備集若若S是聯(lián)結

34、詞完備集是聯(lián)結詞完備集, 則任何命題公式都可由則任何命題公式都可由S中的聯(lián)結詞表示中的聯(lián)結詞表示定理定理2.6 S = , , 是聯(lián)結詞完備集是聯(lián)結詞完備集證明證明 由范式存在定理可證由范式存在定理可證45聯(lián)結詞完備集聯(lián)結詞完備集推論推論 以下都是聯(lián)結詞完備集以下都是聯(lián)結詞完備集 (1) S1 = , , , (2) S2 = , , , , (3) S3 = , (4) S4 = , (5) S5 = , 證明證明(1),(2) 在聯(lián)結詞完備集中加入新的聯(lián)結詞后仍為完備集在聯(lián)結詞完備集中加入新的聯(lián)結詞后仍為完備集(3) A B ( AB)(4) A B ( AB)(5) ABA B , ,不

35、是聯(lián)結詞完備集不是聯(lián)結詞完備集, 0不能用它表示不能用它表示它的子集它的子集 , , , , , ,等都不是等都不是46復合聯(lián)結詞復合聯(lián)結詞定義定義2.8 設設 p, q 為兩個命題為兩個命題, (p q)稱作稱作p與與q的的與非式與非式, 記作記作p q, 即即 p q (p q), 稱為稱為與非聯(lián)結詞與非聯(lián)結詞 (p q) 稱作稱作 p 與與 q 的的或非式或非式, 記作記作 p q, 即即 p q (p q), 稱為稱為或非聯(lián)結詞或非聯(lián)結詞定理定理2.7 與與 為聯(lián)結詞完備集為聯(lián)結詞完備集. 證明證明 , , 為完備集為完備集 p pp (p p) p p p q ( pq) pq (p

36、 p) (q q) p q (p q) (p q) (p q) (p q) 得證得證 為聯(lián)結詞完備集為聯(lián)結詞完備集. 對對 類似可證類似可證472.4 可滿足性問題與消解法可滿足性問題與消解法不含任何文字的簡單析取式稱作不含任何文字的簡單析取式稱作空簡單析取式空簡單析取式, ,記作記作 . .規(guī)定規(guī)定 是不可滿足的是不可滿足的. . 約定約定: :簡單析取式不同時含某個命題變項和它的否定簡單析取式不同時含某個命題變項和它的否定S:合取范式合取范式, C:簡單析取式簡單析取式, l:文字文字, :賦值賦值, 帶下角標或帶下角標或 文字文字l的補的補lc:若若l=p,則則lc= p;若若l= p,

37、則則lc=p.S S :S是可滿足的當且僅當是可滿足的當且僅當S 是可滿足的是可滿足的定義定義2.9 設設C1=l C1 , C2=lc C2 , C1 和和C2 不含不含l和和lc, 稱稱C1C2 為為C1和和C2(以以l和和lc為為消解文字消解文字)的的消解式消解式或或消解結果消解結果, 記作記作Res(C1,C2)例如例如, Res( p q r, p qs)= q rs48消解規(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 和和C

38、2 不含不含l和和lc. 假設假設C1 C2是可滿足的是可滿足的, 是它的滿足賦值是它的滿足賦值, 不妨設不妨設 (l)=1. C2必含有文字必含有文字l l, lc且且 (l )=1. C中含有中含有l(wèi) , 故故 滿足滿足C. 反之反之, 假設假設C是可滿足的是可滿足的, 是它的滿足賦值是它的滿足賦值. C必有必有l(wèi) 使得使得 (l )=1, 不妨設不妨設C1 含含l , 于是于是 滿足滿足C1. 把擴張到把擴張到l(和和lc)上上:若若l=p, 則令則令 (p)=0; 若若lc=p, 則令則令 (p)=1. 恒有恒有 (lc)=1, 從而從而 滿足滿足C2. 得證得證C1 C2是可滿足的是

39、可滿足的.注意注意: C1 C2與與Res(C1,C2)有相同的可滿足性有相同的可滿足性, 但不一定等值但不一定等值.49消解序列與合取范式的否證消解序列與合取范式的否證定義定義2.10 設設S是一個合取范式是一個合取范式, C1,C2,Cn是一個簡單析取式是一個簡單析取式序列序列. 如果對每一個如果對每一個i(1 i n), Ci是是S的一個簡單析取式或者是的一個簡單析取式或者是Res(Cj,Ck)(1 jki), 則稱此序列是由則稱此序列是由S導出導出Cn的的消解序列消解序列. 當當Cn= 時時, 稱此序列是稱此序列是S的一個的一個否證否證.定理定理2.9 一個合取范式是不可滿足的當且僅當

40、它有否證一個合取范式是不可滿足的當且僅當它有否證.例例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的否證的否證.50消解算法消解算法消解算法消解算法輸入輸入: 合式公式合式公式A輸出輸出: 當當A是可滿足時是可滿足時, 回答回答“Yes”; 否則回答否則回答“No”.1. 求求A的合取范式的合取范式S2. 令令S0, S2, S1S的所有簡單析取式的

41、所有簡單析取式3. For C1 S0和和C2 S14. If C1, C2可以消解可以消解 then5. 計算計算CRes(C1,C2)6. If C= then7. 輸出輸出“No”, 計算結束計算結束 8. If C S0且且C S1 then9. S2S2 C51消解算法消解算法10. For C1 S1, C2 S1且且C1 C211. If C1, C2可以消解可以消解 then12. 計算計算CRes(C1,C2)13. If C= then14. 輸出輸出“No”, 計算結束計算結束 15. If C S0且且C S1 then16. S2S2 C17. If S2= then

42、 18. 輸出輸出“Yes”, 計算結束計算結束19. Else S0S0 S1, S1S2, S2, goto 352消解算法例題消解算法例題例例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)= p r Res(qr, q r)=q S2=p r, p r, q循環(huán)循環(huán)2 S0=p, p q,

43、pq, qr, q r, S1=p r, p r, q, S2= Res(pq, q)=p53消解算法例題消解算法例題 Res(qr, p r)=p q Res(q r, pr)=p q Res(p r, pr)=p S2= 輸出輸出“Yes”54第二章第二章 習題課習題課主要內容主要內容l等值式與等值演算等值式與等值演算l基本等值式（基本等值式（1616組，組，2424個公式）個公式）l主析取范式與主合取范式主析取范式與主合取范式l聯(lián)結詞完備集聯(lián)結詞完備集l消解法消解法55基本要求基本要求l 深刻理解等值式的概念深刻理解等值式的概念l 牢記基本等值式的名稱及它們的內容牢記基本等值式的名稱及它

44、們的內容l 熟練地應用基本等值式及置換規(guī)則進行等值演算熟練地應用基本等值式及置換規(guī)則進行等值演算l 理解文字、簡單析取式、簡單合取式、析取范式、合取范理解文字、簡單析取式、簡單合取式、析取范式、合取范式的概念式的概念l 深刻理解極小項、極大項的概念、名稱及下角標與成真、深刻理解極小項、極大項的概念、名稱及下角標與成真、成假賦值的關系，并理解簡單析取式與極小項的關系成假賦值的關系，并理解簡單析取式與極小項的關系l 熟練掌握求主范式的方法（等值演算、真值表等）熟練掌握求主范式的方法（等值演算、真值表等）l 會用主范式求公式的成真賦值、成假賦值、判斷公式的類會用主范式求公式的成真賦值、成假賦值、判斷

45、公式的類型、判斷兩個公式是否等值型、判斷兩個公式是否等值l 會將公式等值地化成指定聯(lián)結詞完備集中的公式會將公式等值地化成指定聯(lián)結詞完備集中的公式l 會用命題邏輯的概念及運算解決簡單的應用問題會用命題邏輯的概念及運算解決簡單的應用問題l 掌握消解規(guī)則及其性質掌握消解規(guī)則及其性質l 會用消解算法判斷公式的可滿足性會用消解算法判斷公式的可滿足性56練習練習1:概念概念1. 設設A與與B為含為含n個命題變項的公式，判斷下列命題是否為真？個命題變項的公式，判斷下列命題是否為真？(1) AB當且僅當當且僅當A與與B有相同的主析取范式有相同的主析取范式(2) 若若A為重言式，則為重言式，則A的主合取范式為的

46、主合取范式為0(3) 若若A為矛盾式，則為矛盾式，則A的主析取范式為的主析取范式為1(4) 任何公式都能等值地化成任何公式都能等值地化成 , 中的公式中的公式(5) 任何公式都能等值地化成任何公式都能等值地化成 , , 中的公式中的公式說明說明:(2) 重言式的主合取范式不含任何極大項，為重言式的主合取范式不含任何極大項，為1. (3) 矛盾式的主合析范式不含任何極小項矛盾式的主合析范式不含任何極小項, 為為0. (4) , 不是完備集，如矛盾式不能寫成不是完備集，如矛盾式不能寫成 , 中的公式中的公式. (5) , 是完備集是完備集. 真真假假假假假假真真57練習練習2: 判斷公式類型判斷公

47、式類型解解 用等值演算法求主范式用等值演算法求主范式 (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)重言式重言式58練習題練習題2(續(xù)續(xù))解解 用等值演算法求公式的主范式用等值演算法求公式的主范式 (pq) q ( p q) q pq q 0 主析取范式主析取范式 M0 M1 M2 M3 主合取范式主合取范式(2) (pq) q矛盾式矛盾式59解解 用等值演算法求公

48、式的主范式用等值演算法求公式的主范式 (pq)p ( p q)p p ( pq) ( p q) m0 m1 主析取范式主析取范式 M2 M3 主合取范式主合取范式(3) (pq)p練習練習2(續(xù)續(xù))非重言式的可滿足式非重言式的可滿足式60練習練習3：求公式的主范式求公式的主范式3已知命題公式已知命題公式A中含中含3個命題變項個命題變項p, q, r，并知道它的成真，并知道它的成真賦值為賦值為001, 010, 111, 求求A的主析取范式和主合取范式，及的主析取范式和主合取范式，及A對對應的真值函數應的真值函數.解解 A的主析取范式為的主析取范式為m1 m2 m7A的主合取范式為的主合取范式為

49、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 161練習練習4：聯(lián)結詞完備集聯(lián)結詞完備集4將將A = (pq) r改寫成下述各聯(lián)結詞集中的公式改寫成下述各聯(lián)結詞集中的公式: (1) , , (2) , (3) , (4) , (5) (6) 解解 (1) (pq) r ( pq) r (2) (pq) r (p q) r (3) (pq) r ( pq) r ( ( pq)r)62練習練習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) 說明：答案不惟一說明：答案不惟一63練習