高等數(shù)學-離散數(shù)學及其應用-課件-第二章-命題邏輯等值演算

1、第二章 命題邏輯等值演算,主要內容等值式與基本的等值式等值演算與置換規(guī)則析取范式與合取范式，主析取范式與主合取范式聯(lián)結詞完備集,1,2.1 等值式,定義2.1 若等價式A?B是重言式，則稱A與B等值，記作A?B，并稱A?B是等值式幾點說明：不要把?與?混為一談. A或B可以是任何命題公式, 公式中還可能有啞元出現(xiàn). 例如 (p?q) ? ((?p?q)?(?r?r)) r為左邊公式的啞元 用真值表可檢查

2、兩個公式是否等值,2,等值式例題,例1 判斷下列各組公式是否等值: (1) p?(q?r) 與 (p?q) ?r,3,結論: p?(q?r) ? (p?q) ?r,等值式例題,(2) p?(q?r) 與 (p?q) ?r,4,結論: p?(q?r) 與 (p?q) ?r 不等值,基本等值式,雙重否定律 ??A?A冪等律 A?A?A, A?A?A交換律 A?B?B?A, A?B?B

3、?A結合律 (A?B)?C?A?(B?C), (A?B)?C?A?(B?C)分配律 A?(B?C)?(A?B)?(A?C), A?(B?C)?(A?B)?(A?C)德摩根律 ?(A?B)??A??B ?(A?B)??A??B吸收律 A?(A?B)?A, A?(A?B

4、)?A,5,基本等值式,零律 A?1?1, A?0?0同一律 A?0?A. A?1?A排中律 A??A?1矛盾律 A??A?0蘊涵等值式 A?B??A?B等價等值式 A?B?(A?B)?(B?A)假言易位

5、 A?B??B??A等價否定等值式 A?B??A??B歸謬論 (A?B)?(A??B) ??A特別提示：必須牢記這16組等值式，這是繼續(xù)學習的基礎,6,等值演算與置換規(guī)則,1. 等值演算——由已知的等值式推演出新的等值式的過程2. 等值演算的基礎： (1) 等值關系的性質：自反性、對稱性、傳遞性 (2) 基本的等值式 (3) 置換規(guī)則3. 置換規(guī)則 設

6、?(A) 是含公式 A 的命題公式，?(B) 是用公式 B 置換 ?(A) 中所有的 A 后得到的命題公式 若 B?A，則 ?(B)??(A).,7,等值演算的應用舉例,證明兩個公式等值例2 證明 p?(q?r) ? (p?q)?r證 p?(q?r) ? ?p?(?q?r) （蘊涵等值式，置換規(guī)則） ? (?p??q)?r （結合律，置換規(guī)則） ? ?(

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

8、算化簡公式，然后再觀察 p?(q?r) ??p??q?r (p?q)?r ??(?p?q)?r?(p??q)?r 更容易看出前面的兩個賦值分別是左邊的成真賦 值和右邊的成假賦值,9,等值演算的應用舉例,判斷公式類型: A為矛盾式當且僅當A ? 0

9、 A為重言式當且僅當A ? 1例4 用等值演算法判斷下列公式的類型 (1) q??(p?q) (2) (p?q)?(?q??p) (3) ((p?q)?(p??q))?r,10,解 (1) q??(p?q) ? q??(?p?q) （蘊涵等值式） ? q?(p??q) （德摩根律） ? p?(q??q) （交換律，結合律）

10、? p?0 （矛盾律） ? 0 （零律）矛盾式,判斷公式類型,(2) (p?q)?(?q??p) ? (?p?q)?(q??p) （蘊涵等值式） ? (?p?q)?(?p?q) （交換律） ? 1重言式,11,(3) ((p?q)?(p??q))?r ? (p?(q??q))?r （分配律） ? p

11、?1?r （排中律） ? p?r （同一律）可滿足式，101和111是成真賦值，000和010等是成假賦值.,2.2 析取范式與合取范式,基本概念(1) 文字——命題變項及其否定的總稱(2) 簡單析取式——有限個文字構成的析取式 如 p, ?q, p??q, p?q?r, …(3) 簡單合取式——有限個文字構成的合取

12、式 如 p, ?q, p??q, p?q?r, …(4) 析取范式——由有限個簡單合取式組成的析取式 如 p, ?p?q, p??q, (p??q)?(?p?q??r)?(q?r)(5) 合取范式——由有限個簡單析取式組成的合取式 如 p, p??q, ?p?q, (p?q??p?(p??q??r)(6) 范式——析取范式與合取范式的總稱,12,范式概念,說明：

13、單個文字既是簡單析取式，又是簡單合取式形如 p??q?r, ?p?q??r 的公式既是析取范式，又是合取范式,13,范式的性質,定理2.1 (1) 一個簡單析取式是重言式當且僅當它同時含有某個命題變項和它的否定式.(2) 一個簡單合取式是矛盾式當且僅當它同時含有某個命題變項和它的否定式.定理2.2 (1) 一個析取范式是矛盾式當且僅當它每個簡單合取式都是矛盾式.(2) 一個合取范式是重言式當且僅當它的每個簡單析取式都

14、是重言式.,14,命題公式的范式,定理2.3（范式存在定理） 任何命題公式都存在與之等值的析取范式與合取范式公式A的析取(合取)范式??與A等值的析取(合取)范式求公式A的范式的步驟： (1) 消去A中的?, ?（若存在） A?B??A?B A?B?(?A?B)?(A??B) (2) 否定聯(lián)結詞?的內移或消去 ? ?A? A ?(A?B)?

15、?A??B ?(A?B)??A??B,15,命題公式的范式,(3) 使用分配律 A?(B?C)?(A?B)?(A?C) 求合取范式 A?(B?C)? (A?B)?(A?C) 求析取范式公式范式的不足??不惟一,16,求公式的范式,例5 求下列公式的析取范式與合取范式 (1) (p??q)??r (2) (p??q

16、)?r解 (1) (p??q)??r ? (?p??q)??r （消去?） ? ?p??q??r （結合律）最后結果既是析取范式(由3個簡單合取式組成的析取式)，又是合取范式(由一個簡單析取式組成的合取式),17,求公式的范式,(2) (p??q)?r ? (?p??q)?r （消去第一個?） ? ?(?p??q)?r （消

17、去第二個?） ? (p?q)?r （否定號內移——德摩根律) 析取范式 ? (p?r)?(q?r) （?對?分配律） 合取范式,18,極小項與極大項,定義2.4 在含有n個命題變項的簡單合取式（簡單析取式）中，若每個命題變項均以文字的形式在其中出現(xiàn)且僅出現(xiàn)一次，而且第i個文字出現(xiàn)在左起第i位上（1?i?n），稱這樣的簡單合取式（簡單析取式）為極小項（極大項）.幾點說明：

18、n個命題變項有2n個極小項和2n個極大項2n個極小項（極大項）均互不等值用mi表示第i個極小項，其中i是該極小項成真賦值的十進制表示. 用Mi表示第i個極大項，其中i是該極大項成假賦值的十進制表示. mi（Mi）稱為極小項（極大項）的名稱.,19,實例,兩個命題變項 p, q 的極小項與極大項,20,實例,21,三個命題變項 p, q, r 的極小項與極大項.,mi與Mi的關系： ?mi ? Mi, ?Mi ? mi,主析取范

19、式與主合取范式,主析取范式——由極小項構成的析取范式主合取范式——由極大項構成的合取范式例如，n=3, 命題變項為 p, q, r 時， (?p??q?r)?(?p?q?r) ? m1?m3 ——主析取范式 (p?q??r)?(?p??q??r) ? M1?M7——主合取范式公式A的主析取(合取)范式——與A 等值的主析取(合取)范式 定理2.5 (主范式的存在惟一定理) 任何命題公式都存

20、在與之等值的主析取范式和主合取范式,并且是惟一的,22,求公式主范式的步驟,23,求公式主析取范式的步驟:設公式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)

21、 重復這個過程, 直到所有簡單合取式都是長度為n的極 小項為止(3) 消去重復出現(xiàn)的極小項, 即用mi代替mi?mi(4) 將極小項按下標從小到大排列,求公式主范式的步驟,求公式的主合取范式的步驟:設公式A含命題變項p1,p2,…,pn(1) 求A的合取范式A?=B1?B2? … ?Bs , 其中Bj是簡單析取 式, j=1,2, … ,s (2) 若某個Bj既不含pi, 又不含?p

22、i, 則將Bj展開成 Bj ? Bj?(pi??pi) ? (Bj?pi)?(Bj??pi) 重復這個過程, 直到所有簡單析取式都是長度為n的極 大項為止(3) 消去重復出現(xiàn)的極大項, 即用Mi代替Mi?Mi(4) 將極大項按下標從小到大排列,24,實例,例6 (1) 求公式 A=(p??q)?r的主析取范式和主合取范式 解 (p??q)?r ? (p?q)?r

23、 （析取范式） ① (p?q) ? (p?q)?(?r?r) ? (p?q??r)?(p?q?r) ? m6?m7 ② r ? (?p?p)?(?q?q)?r ? (?p??q?r)?(?p?q?r)?(p??q?r)?(

24、p?q?r) ? m1?m3?m5?m7 ③ ②, ③代入①并排序，得 (p??q)?r ? m1?m3?m5? m6?m7 （主析取范式）,25,實例,(p??q)?r ? (p?r)?(q?r) （合取范式） ④ p?r ? p?(q??q)?r ? (p?

25、q?r)?(p??q?r) ? M0?M2 ⑤ q?r ? (p??p)?q?r ? (p?q?r)?(?p?q?r) ? M0?M4 ⑥

26、 ⑤, ⑥代入④ 并排序，得 (p??q)?r ? M0?M2?M4 （主合取范式）,26,主范式的應用,1.求公式的成真賦值和成假賦值 設公式A含n個命題變項, A的主析取范式有s個極小項, 則A 有s個成真賦值, 它們是極小項下標的二進制表示, 其余2n-s 個賦值都是成假賦值 例如 (p??q)?r ? m1?m3?m5? m6?m7成真賦值為 001,

27、011, 101, 110, 111，成假賦值為 000, 010, 100. 類似地，由主合取范式也立即求出成假賦值和成真賦值.,27,主范式的應用,2. 判斷公式的類型 設A含n個命題變項. A為重言式 ? A的主析取范式含全部2n個極小項 ? A的主合取范式不含任何極大項, 記為1. A為矛盾式 ? A的主合析取范式含全部2n個極大項

28、 ? A的主析取范式不含任何極小項, 記為0. A為非重言式的可滿足式 ? A的主析取范式中至少含一個、但不是全 部極小項 ? A的主合取范式中至少含一個、但不是全

29、 部極大項.,28,主范式的應用,例7 用主析取范式判斷公式的類型:(1) A? ?(p?q)?q (2) B? p?(p?q) (3) C? (p?q)?r解 (1) A ? ?(? p?q)?q ? ( p??q)?q ? 0 矛盾式(2) B ? ? p?(p?q) ? 1 ? m0?m1?m2?m3 重言式(3) C ? ?(p?q)?r ? (?p??q

30、)?r ? (?p??q?r)?(?p??q??r)?(?p??q?r) ?(?p?q?r)?(p??q?r)?(p?q?r) ? m0?m1?m3? m5?m7 非重言式的可滿足式,29,主范式的應用,3. 判斷兩個公式是否等值例8 用主析取范式判以下每一組公式是否等值 ⑴ p?(q?r) 與 (p?q)?r ⑵ p?(q?r)

31、與 (p?q)?r解 p?(q?r) = m0?m1?m2?m3? m4?m5? m7 (p?q)?r = m0?m1?m2?m3? m4?m5? m7 (p?q)?r = m1?m3? m4?m5? m7顯見，⑴中的兩公式等值，而⑵的不等值.,30,主范式的應用,4. 解實際問題例9 某單位要從A,B,C三人中選派若干人出國考察, 需滿足下 述條件: (1) 若A去, 則C必須去; (2)

32、若B去, 則C不能去; (3) A和B必須去一人且只能去一人. 問有幾種可能的選派方案?解 記 p:派A去, q:派B去, r:派C去(1) p?r, (2) q??r, (3) (p??q)?(?p?q)求下式的成真賦值 A=(p?r)?(q??r)?((p??q)?(?p?q)),31,主范式的應用,求A的主析取范式 A=(p?r)?(q??r)?((p??q)?(?p?q))

33、 ? (?p?r)?(?q??r)?((p??q)?(?p?q)) ? ((?p??q)?(?p??r)?(r??q)?(r??r)) ?((p??q)?(?p?q)) ? ((?p??q)?(p??q))?((?p??r)?(p??q)) ?((r??q)?(p??q))?((?p??q)?(?p?q)) ?((?p??r)?(?p?q))

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

35、表示, 它們恰好是A的主合取范式的極大項的下角標, 故 A ? M0?M2?M4?M5?M6,33,由主合取范式確定主析取范式用真值表確定主范式,2.3 聯(lián)結詞的完備集,34,,定義2.6 稱F:{0,1}n? {0,1} 為n元真值函數(shù). {0,1}n={00…0, 00…1, …, 11…1}，包含 個長為n的0,1符號串. 共有 個n元真值函數(shù).,真值函數(shù),35,,,,,,,

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

37、{?, ?, ?}是聯(lián)結詞完備集證明 由范式存在定理可證,37,聯(lián)結詞完備集,推論 以下都是聯(lián)結詞完備集 (1) S1 = {?, ?, ?, ?} (2) S2 = {?, ?, ?, ?, ?} (3) S3 = {?, ?} (4) S4 = {?, ?} (5) S5 = {?, ?}證明(1),(2) 在聯(lián)結詞完備集中加入新的聯(lián)結詞后仍為完備集

38、(3) A?B ? ?(?A??B)(4) A?B ? ?(?A??B)(5) A?B??A?B, 及(4),38,{?,?,?,?}不是聯(lián)結詞完備集, 0不能用它表示它的子集{?},{?},{?},{?},{?,?},{?,?,?}等都不是,復合聯(lián)結詞,定義2.8 設 p, q 為兩個命題, ?(p?q)稱作p與q的與非式, 記作p?q, 即 p?q ? ?(p?q), ?稱為與非聯(lián)結詞?(p?q) 稱作 p 與 q

39、 的或非式, 記作 p?q, 即 p?q ? ?(p?q), ?稱為或非聯(lián)結詞定理2.7 {?}與{?}為聯(lián)結詞完備集. 證明 {?, ?, ?}為完備集 ?p ? ?p??p ? ?(p?p) ? p?p p?q ? ?(?p??q) ? ?p??q ? (p?p)?(q?q) p?q ? ??(p?q)

40、? ?(p?q) ? (p?q)?(p?q) 得證{?}為聯(lián)結詞完備集. 對{?}類似可證,39,第二章 習題課,主要內容等值式與等值演算基本等值式（16組，24個公式）主析取范式與主合取范式聯(lián)結詞完備集,40,基本要求,深刻理解等值式的概念牢記基本等值式的名稱及其內容熟練地應用基本等值式及置換規(guī)則進行等值演算理解文字、簡單析取式、簡單合取式、析取范式、合取范式的概念深刻理解極小項、極大項的概念、

41、名稱及下角標與成真賦值、成假賦值的關系，理解簡單析取式與極小項的關系熟練掌握求主范式的方法（用等值演算、真值表等）會用主范式求公式的成真賦值、成假賦值、判斷公式的類型、判斷兩個公式是否等值會將公式等值地化成指定聯(lián)結詞完備集中的公式會用命題邏輯的概念及運算解決簡單的應用問題,41,練習1:概念,1. 設A與B為含n個命題變項的公式，判斷下列命題是否為真？(1) A?B當且僅當A與B有相同的主析取范式(2) 若A為重言式，則A的

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

43、類型,解 用等值演算法求主范式 (p?q)?(?q??p) ? ?(?p?q)?(q??p) ? (p??q)?(q??p) ? (p??q)?(?p?q)?(p?q)?(?p??q) ? m2 ? m1 ? m3 ? m0 ? m0 ? m1 ? m2 ? m3

44、 主析取范式 ? 1 主合取范式,43,2. 判斷下列公式的類型: (1) (p?q)?(?q??p),重言式,練習題2(續(xù)),解 用等值演算法求公式的主范式 ?(p?q)?q ? ?(?p?q)?q

45、 ? p??q?q ? 0 主析取范式 ? M0 ? M1 ? M2 ? M3 主合取范式,44,(2) ?(p?q)?q,矛盾式,練習2(續(xù)),解 用等值演算法求公式

46、的主范式 (p?q)??p ? (?p?q)??p ? ?p ? (?p??q)?(?p?q) ? m0 ? m1 主析取范式 ? M2 ? M3 主合取范式,45,(3) (p?q)??p,非重言式的可滿足式,練習3：求公式的主范式,3．已知命題公式A中含3個命題變項p,

47、q, r，并知道它的成真賦值為001, 010, 111, 求A的主析取范式和主合取范式，及A對應的真值函數(shù).解,46,A的主析取范式為m1 ? m2 ? m7,A的主合取范式為M0 ? M3 ? M4 ? M5 ? M6,這是,練習4：聯(lián)結詞完備集,4．將A = (p??q)?r改寫成下述各聯(lián)結詞集中的公式: (1) {?, ?, ?} (2) {?, ?} (3) {?, ?} (4) {?, ?} (5) {?}

48、 (6) {?},47,解 (1) (p??q)?r ? (?p??q)?r (2) (p??q)?r ? ?(p?q)?r (3) (p??q)?r ? (?p??q)?r ? ?(?(?p??q)??r),練習4 解答,(4) (p??q)?r ? ?(?(p??q)??r)

49、 ? ?((p??q)??r) (5) (p??q)?r ? ?(p?q)?r ? (p?q)?r ? ? ?((p?q)?r) ? ((p?q)?r)?((p?q)?r) (6) (p??q)?r ?(?p??q)?r

50、 ? ?(?(?p??q)??r) ? (?p??q)??r ? ((p?p)?(q?q)?(r?r) 說明：答案不惟一,48,練習5：應用題,5. 某公司要從趙、錢、孫、李、周五名新畢業(yè)的大學生中選派一些人出國學習. 選派必須滿足以下條件：(1) 若趙去，錢也去.(2) 李、周兩人中至少有

51、一人去(3) 錢、孫兩人中去且僅去一人.(4) 孫、李兩人同去或同不去.(5) 若周去，則趙、錢也去. 用等值演算法分析該公司應選派誰出國？,49,練習5解答,解此類問題的步驟：1.設簡單命題并符號化2. 用復合命題描述各條件3. 寫出由復合命題組成的合取式4. 將合取式化成析取式（最好是主析取范式）5. 求成真賦值, 并做出解釋和結論,50,練習5解答,解1. 設簡單命題并符號化設 p: 派趙去，q: 派錢

52、去，r: 派孫去，s: 派李去，u: 派周去2. 寫出復合命題(1) 若趙去，錢也去 p?q(2) 李、周兩人中至少有一人去 s?u(3) 錢、孫兩人中去且僅去一人 (q??r)?(?q?r)(4) 孫、李兩人同去或同不去 (r?s)?(?r??s)(5)

53、若周去，則趙、錢也去 u?(p?q),51,,3. 由(1)—(5)構成合取式 A = (p?q)?(s?u)?((q??r)?(?q?r))? ((r?s)?(?r??s))?(u?(p?q))4. 化成析取式 A ? B1?B2?B3 B1= (p?q)?((q??r)?(?q?r)) ?(?p?q)?((q??r)?

54、(?q?r)) ? ((?p?q??r)?(?p??q?r)?(q??r)) B2= (s?u)?(u?(p?q)) ?(s?u)?(?u?(p?q)) ? ((s??u)?(p?q?s)?(p?q?u)),52,練習5解答,練習5解答,B1?B2 ? (?p?q??r?s??u)?(?p??q?r?s??u) ?(q??r?s??u)?(p?q??r?s)?(p?q??r?u) B3