《離散數(shù)學(xué)課件》命題邏輯2

1、上節(jié)課內(nèi)容,等值式、基本等值式等值演算復(fù)合聯(lián)結(jié)詞 排斥或 與非式 或非式聯(lián)結(jié)詞全功能集,1,?(A?B)??A??B ?(A?B)??A??B,A?(A?B)?A, A?(A?B)?A,A?B??A?B,第四講 對偶與范式（1.2.4--1.3）,對偶式與對偶原理 析取范式與合取范式 主析取范式與主合取范式,2,3/48,1.2.4 對偶式,定義 在僅含有聯(lián)結(jié)詞?, ∧,∨的

2、命題公式A中， 將∨換成∧, ∧換成∨， 若A中含有0或1，就將0換成1，1換成0， 所得命題公式稱為A的對偶式， 記為A*.,,例 已知 ? = P ?(Q??R）,?= ?P?(Q??R) ?*= ?P ?(Q??R)(

3、?*)*= ?P ?(Q??R),則:,4,定理 設(shè)A和A*互為對偶式，p1,p2,…,pn是出現(xiàn)在A和A*中的全部命題變項，將A和A*寫成n元函數(shù)形式，則 (1) ? A(p1,p2,…,pn) ? A* (? p1, ? p2,…, ? pn) (2) A(? p1, ? p2,…, ? pn) ? ? A* (p1,p2

4、,…,pn) 定理（對偶原理）設(shè)A，B為兩個命題公式，若A ? B，則A* ? B*.,例 設(shè)A*(P,Q,R)是?P∧(?Q∨R)，證明 A*(?P,?Q,?R)??A(P,Q,R),證：因A*(P,Q,R)??P∧(?Q∨R)，代入可得 A*(?P,?Q,?R)?P∧(Q∨?R)。而按對偶式的定義，由A*(P,Q,R)可寫出 Ａ(P,Q,R)??P∨(?Q∧R)故 ?Ａ

5、(P,Q,R)??(?P∨(?Q∧R)) ?P∧?(?Q∧R) (德·摩根律) ?P∧(Q∨?R) (德·摩根律) ? A*(?P,?Q,?R),6/48,1.3 范式及其應(yīng)用,合取式,析取式,析取范式,合取范式,主析取范式,主合取范式,,,,,主范式范式真假性,唯一兩者有關(guān)聯(lián)不唯一,成真解釋,

6、成假解釋,,,對于完全解釋，合(析)取式=極小(大)項,7/48,合取式、析取式,定義1 命題變元、或者命題變元的否定、或由它們利用合取詞組成的合式公式稱為（簡單）合取式。定義2 命題變元、或者命題變元的否定、或由它們利用析取詞組成的合式公式稱為（簡單）析取式。例 顯然， P，?P，P?Q，?P?Q??R 均為合取式； P，?P，P?Q，?P?Q??R 均為析取式。,,8/48,(

7、一) 解釋與合取式、析取式之間的關(guān)系,定理1 任給一個成真解釋有且僅有一個合取式與之對應(yīng)； 任給一個成假解釋有且僅有一個析取式與之對應(yīng)。,例 成真解釋(P,Q,R)= (1,0,1) 成假解釋(P,Q,R)= (0,0,1),合取式P??Q?R,析取式P?Q??R =?(?P??Q?R),,9/48,析取范式、合取范式,定義3 形如A1? A2?…? An的公式稱為析取范式， 其中Ai

8、(i=1,2…,n)為合取式。定義4 形如A1? A2?…? An的公式稱為合取范式， 其中Ai(i=1,2…,n)為析取式。例 P，?P，P?Q，P?Q ，(?P?Q)?(S??R) ——均為析取范式。 P，?P，P?Q，P?Q ， (?P?Q)?(S??R)——均為合取范式。,10/48,例: 考察公式 ?=P?Q的析取范式,對應(yīng)于兩個合取式為

9、 P∧Q, ?P∧?Q于是，有 ?= (P∧Q) ∨(?P∧?Q),有兩個成真解釋： (1, 1), (0, 0),11/48,例: 考察公式 ?=P?Q的合取范式,對應(yīng)析取式為 ?P∨Q, P∨?Q于是，有：

10、 ?= (?P∨Q) ∧(P∨?Q),成假解釋 (1, 0), (0, 1),12/48,定理2 任何命題演算公式均可以化為合取范式，也可以化為析取范式。,證明： (1)設(shè)公式?為永真公式 ? =P??P (2)設(shè)公式?為永假公式 ? =P??P,證明(3)： 設(shè)公式?既非永真又非永假。設(shè)公

11、式?的成真解釋為?1，?2，……，?n， 成假解釋為?1，?2，……，?t。根據(jù)解釋和范式的關(guān)系知：對應(yīng)于成真解釋?1，?2，……，?n的合取式為?1，?2，……，?n對應(yīng)于成假解釋?1，?2，……，?t的析取式為?1，?2，……，?t而公式 ?1??2?……??n的成真解釋為?1，?2，……，?n；公式?1??2?……??t的成假解釋

12、為?1，?2，……，?t。根據(jù)兩個公式邏輯等價的定義知 ?=?1??2?……??n =?1??2?……??t故公式?既可表示為析取范式又可表示為合取范式。,14/48,(二) 析取范式和合取范式的求解方法,等價變換法——利用等價公式進行變換，將范式變換出來。解 釋 法（真值表法） ——利用所有成真解釋或成假解釋，寫出范式。,15/48,

13、等價變換法,(1)去蘊含詞與等價詞： P?Q =?P ∨ Q P?Q = (?P ∨ Q) ∧ (P ∨ ?Q)(2)否定深入： ?(P ?Q)= ?P??Q ?(P ?Q)= ?P??Q， ??P = P(3)重復(fù)使用分配律： P ?(Q?R)=(P ?Q )?(

14、P? R) P ?(Q?R)=(P ?Q )?(P? R),16/48,解釋法,(1) 求所有成真解釋、成假解釋；(2) 寫出成真解釋對應(yīng)的合取式、 成假解釋對應(yīng)的析取式；(3) 把所有的合取式用析取詞聯(lián)結(jié)起來就構(gòu)成析取范式，把所有的析取式用合取詞聯(lián)結(jié)起來就構(gòu)成合取范式。,求公式的范式舉例,解 (p??q)??r ? (?p??q)??r （消

15、去?） ? ?p??q??r （結(jié)合律）這既是A的析取范式（由3個簡單合取式組成的析取式），又是A的合取范式（由一個簡單析取式組成的合取式）,例 求下列公式的析取范式與合取范式(1) A=(p??q)??r,解 (p??q)?r ? (?p??q)?r （消去第一個?） ? ?(?p??q)?r （消去第二個?） ? (p?q)?r （否定號內(nèi)移

16、——德摩根律）這一步已為析取范式（兩個簡單合取式構(gòu)成）繼續(xù)： (p?q)?r ? (p?r)?(q?r) （?對?分配律）這一步得到合取范式（由兩個簡單析取式構(gòu)成）,(2) B=(p??q)?r,19/48,例 求公式的范式 ?(P?Q)??((R??Q)??P),解：原式=?(?P?Q)??(?(?R??Q)??P) =(P??Q)?((?R??Q)?P)

17、 =(P??Q)?(P??R)?(P??Q) =(P??Q)?(P??R) 析取范式 = P?(?Q??R) 合取范式,20/48,解：P=1時, 原式=?(1?Q)∨?((R??Q)??1)=?Q∨?R P=0時, 原式=?(0?Q)∨?((R??Q)??0)=0 所以

18、有: 成真解釋為：(P,Q,R)=(1,0,1), (1,0,0), (1,1,0) 成假解釋為：(P,Q,R)=(1,1,1), (0,?, ?),例 求公式的范式 ?(P?Q)??((R??Q)??P),于是析取范式為: (P??Q?R)?(P? ?Q ??R)?(P ?Q ? ? R) 合取范式為：

19、 (?P ??Q??R)?P,21/48,范式不唯一性,例 求公式的范式 ?(P?Q)??((R??Q)??P),解1： 原式=(P??Q)?(P??R) 析取范式 = P?(?Q??R) 合取范式解2: 析取范式為:

20、(P??Q?R)?(P? ?Q ??R)?(P ?Q ? ? R) 合取范式為： (?P ??Q??R)?P,22/48,1.3.2 主范式,定義5 對于n個命題變元P1，P2，……，Pn，公式 Q1?Q2?……?Qn 稱為極小項，其中Qi=Pi或?Pi(i=1，……，n)。,例 由兩個命題變元P，Q組成的極小項有四個，它們分別為：?

21、P??Q ?P?QP??Q P?Q,(一) 主析取范式,極小項與極大項(續(xù)),由P, Q兩個命題變項形成的極小項,說明：n個命題變項產(chǎn)生2n個極小項和2n個極大項 2n個極小項（極大項）均互不等值 用mi表示第i個極小項，其中i是該極小項成真賦值的十進制表示.,由p, q, r三個命題變項形成的極小項與極大項,25/48,主析取范式,定義6

22、 僅有極小項構(gòu)成的析取范式稱為主析取 范式。 例如，n=3, 命題變項為p, q, r時， (?p??q?r)?(?p?q?r) ? m1?m3 是主析取范式 定理3 任何一個合式公式，均有惟一的一個主析取范式與該合式公式等價。,主析取范式就是公式的所有完全成真解釋對應(yīng)的極小項的析取。,26/48,求主析取范式的兩種方法,(1)解釋法: 根據(jù)公式的所有完全成真解釋，求

23、出與這些成真解釋對應(yīng)的合取式，所有合取式的析取就為公式的主析取范式。(2)等價變換法: 1) 先求析取范式; 2) 將不是極小項的簡單合取式化成與之等值的若 干個極小項的析取，缺少的項用P ? ?P填充，需 要利用同一律（零律）、排中律（矛盾律）、 分配律、冪等律等. 3) 極小項用名稱mi表示，并按角標從小到大順序排序.,27/48,

24、例 求公式的主析取范式 ?(P?Q)??((R??Q)??P),解：原式=?(?P?Q)??(?(?R??Q)??P) =(P??Q)?((?R??Q)?P) =(P??Q)?(P??R)?(P??Q) =(P??Q)?(P??R) 析取范式 =(P??Q?(R ??R))?(P ?(Q??Q)??R)

25、 = (P??Q?R) ?(P??Q? ?R)?(P ?Q??R) =101?100?110=m4?m5?m6,28/48,解：P=1時, 原式=?(1?Q)∨?((R??Q)??1)=?Q∨?R P=0時, 原式=?(0?Q)∨?((R??Q)??0)=0 所以有: 成真解釋為：(P,Q,R)=(1,0,1), (1,0,0), (1,1,0),例 求公式

26、的主析取范式 ?(P?Q)??((R??Q)??P),于是主析取范式為: (P??Q?R)?(P? ?Q ??R)?(P ?Q ? ? R) =101?100?110 =m4?m5?m6,例 求Q∧((P∨?Q)→R)的主析取范式。,,解：Q∧((P∨?Q)→R)? (?P∧Q)∨(Q∧R) (先化為析取范式)? (?P∧Q

27、∧(R∨?R))∨((P∨?P)∧Q∧R) (補入未出現(xiàn)的變元)(?P∧Q∧R)∨(?P∧Q∧?R)∨(P∧Q∧R)∨(?P∧Q∧R) (展開)? (?P∧Q∧?R)∨(?P∧Q∧R)∨(P∧Q∧R) (合并相同的小項)?

28、m2∨m3∨m7?∑2,3,7,解：給定命題公式的真值表為：,所以Q∧（(P∨?Q)→R）的主析取范式為: (?P∧Q∧?R)∨(?P∧Q∧R)∨(P∧Q∧R) ? ∑2,3,7 ；,例 求Q∧((P∨?Q)→R)的主析取范式。,31/48,(二) 主合取范式,定義7 對于n個命變元P1，P2，……，Pn，公式 Q1?Q2?……?Qn 稱為極大項，其中Qi=

29、Pi或?Pi(i=1，…，n)。,例 由兩個命題變元P，Q組成的極大項有四個，它們分別為： ?P??Q ?P?Q P??Q P?Q,由p, q兩個命題變項形成的極小項與極大項,由p, q, r三個命題變項形成的極小項與極大項,34/48,主合取范式,定義8

30、僅有極大項構(gòu)成的合取范式稱為主合取范式。 定理4 任何一個合式公式，均有惟一的一個主合取范式與該合式公式等價。,主合取范式就是公式的所有完全成假解釋對應(yīng)的極大項的合取。,35/48,求主合取范式的兩種方法,(1)解釋法 根據(jù)公式的所有完全成假解釋，求出與這些成假解釋對應(yīng)的析取式，所有析取式的合取就為公式的主合取范式。(2)等價變換法: 1) 先求合取范式; 2) 將不是極大項的簡單

31、析取式化成與之等值的若 干個極大項的合取，缺少的項用A??A填充，需 要利用同一律（零律）、排中律（矛盾律）、 分配律、冪等律等. 3) 極小項用名稱Mi表示，并按角標從小到大順序排序.,36/48,例 求公式的主合取范式 ?(P?Q)??((R??Q)??P),解：原式=?(?P?Q)??(?(?R??Q)??P) =(P??Q)?((?R??Q)?

32、P) =(P??Q)?(P??R)?(P??Q) =(P??Q)?(P??R) 析取范式 = P?(?Q??R) 合取范式 =(P?(Q??Q)?(R??R))?((?Q??R) ?(P??P)) =(P?Q?R)?(P?Q??R)? (P??Q?R

33、) ?(P??Q??R) ?(?P??Q??R) =000?001?010?011?111=0?1?2?3?7,37/48,解：P=1時, 原式=?(1?Q)∨?((R??Q)??1)=?Q∨?R P=0時, 原式=?(0?Q)∨?((R??Q)??0)=0 所以有: 成假解釋為：(P,Q,R)=(1,1,1), (0,

34、?, ?),例 求公式的主合取范式 ?(P?Q)??((R??Q)??P),于是主合取范式= (?P??Q??R) ?(P??Q??R)? (P??Q?R) ?(P?Q??R)?(P?Q?R) =111?011?010?001?000 =0?1?2?3?7,(F,TT),(F,T,F),(F

35、,F,T),(F,F,F),38/48,主合取范式和主析取范式緊密相關(guān),,,?(P?Q)??((R??Q)??P)=4?5?6 =0?1?2?3?7,(P?R)?(?P ?(Q ? ? R)) （P13） =2?5?7

36、 =0?1?3?4?6,(P?R)?(?P ?(?Q ?R))=1?4?6?7= ∑(1,4,6,7)= 0?2?3?5= ∏(0,2,3,5),設(shè)命題公式Ａ中含有ｎ個命題變元，且Ａ的主析取范式中含ｋ個極小項 ｍi1，ｍi2， …，ｍik，

37、即 A?ｍi1∨ｍi2∨…∨ｍik 那么，?Ａ的主析取范式中必含2n-k個極小項。設(shè)它們是ｍj1，ｍj2 ，…，mj(2n-k)，即 ?Ａ?ｍj1 ∨ｍj2∨…∨ｍj (2n-k) 注意到?ｍi?Mi，?Mi ? mi，所以 A???A ??(ｍj1 ∨ｍj2∨…∨ｍj(2n-k)) ??ｍj1 ∧?ｍj2 ∧…∧?ｍj(2n-k)，

38、 ?Mj1 ∧ Mj2 ∧… ∧ Mj(2n-k),主析、合取范式互求,例求Q∧((P∨?Q)→R)的主析取范式和主合取范式。,解：給定命題公式的真值表為：,主析取范式為: (?P∧Q∧?R)∨(?P∧Q∧R)∨(P∧Q∧R) ? ∑2,3,7 ； 主合取范式:(P∨Q∨R)∧(P∨Q∨?R)∧(?P∨Q∨R)∧(?P∨Q∨?R)∧(?P∨?Q∨R) ? ∏0,1,4,5,6,㈠．判定二命題公式是否等值。 Ａ

39、?Ｂ當且僅當Ａ與Ｂ有相同的主析（合）取范式㈡．判定命題公式的類型。設(shè)Ａ是含有ｎ個變元的命題公式：①Ａ為重言式，當且僅當Ａ的主析取范式中含有2n個小項。此時，主合取范式中不含任何大項，可令主合取范式為T。②Ａ為永假式，當且僅當Ａ的主合取范式中含有2n個大項。此時主析取范式中不含任何小項，可令主析取范式為F。㈢．求命題公式的成真和成假賦值。,1.3.3 范式的應(yīng)用,例７ 判斷下列命題公式的類型及成真賦值和成假賦值：⑴ ?(P→Q

40、)∧Q； ⑵ (P→Q)∧P→Q； ⑶ (P→Q)∧Q。解：⑴ ?(P→Q)∧Q ??(?P∨Q)∧Q? P∧?Q∧Q (? F) ?(P∨(?Q∧Q))∧(?Q∨(?P∧P))∧(Q∨(?P∧P)) ?(P∨?Q)∧(P∨Q)∧(?P∨?Q)∧(P∨?Q)∧(?P∨Q)∧(P∨Q) ?(P∨Q)∧(P∨?Q)∧(?P∨Q)∧(?P∨?Q) ?∏0,1,2,3

41、 （永假式）,范式的應(yīng)用（例）,43,⑵ (P→Q)∧（P→Q） ?(?P∧?Q)∨(?P∧Q)∨(P∧?Q)∨(P∧Q) ?ｍ0∨ｍ1∨ｍ2∨ｍ3? ∑0,1,2,3 （重言式）⑶ (P→Q)∧Q ? (?P∧Q)∨(P∧Q) ?ｍ1∨ｍ3 ? ∑1,3 （可滿足式）

42、在本例⑶中，成真賦值是：０１或１１；成假賦值是： １０或００。,44/48,你面前有兩扇門，其中一扇門后有寶藏，一扇門后有吃人妖怪。 在這兩扇門前面，有兩個人，這兩個人都知道哪扇門后有寶藏，哪扇門后有吃人妖怪，而這兩個人呢，一個人只說真話，一個人只說假話。 你只能問這兩個人每人一個問題。你怎么問才能找到寶藏？,蘋果考題：寶藏在哪里?,45/48,問： 對”此門后是否有寶藏”問題, 你的同伴回答”是”嗎？,

43、令 P：被問人說真話； Q：被問人回答“是”； R：其同伴回答“是” ； S：此門后有寶藏。根據(jù)題意可得真值表如圖所示。根據(jù)真值表知，主析取范式為： S=(P??Q)?(?P??Q) =(P??P)??Q =?Q因此被問人回答“是”時，此門后一定沒有寶藏。,T T T (假話) F,T F F (假話) T,F T F (真話)

44、 F,F F T (真話) T,結(jié)論: 否定被問人的回答!,46/48,專家的論證正確嗎?,在研討會上，三位專家分別發(fā)言如下:一位專家由此得出結(jié)論：通貨膨脹率將會下降。問這位專家的論證是否正確？,美元不貶值只要而且僅僅只要如果國家稅收增加，那么通貨膨脹率將下降。如果通貨膨脹率下降，或者美元不貶值，則國家稅收將不會增加?；蛘邍叶愂毡仨氃黾?，或者美元將貶值而且通貨膨脹率將下降。,47,P：國家稅收增加

45、 Q：通貨膨脹率下降R：美元貶值,1、美元不貶值只要而且僅僅只要如果國家稅收增加，那么通貨膨脹率將下降。,A ＝ ?R ?(P ?Q),2、如果通貨膨脹率下降，或者美元不貶值，則國家稅收將不會增加。,B ＝ (Q ??R) ??P,3、或者國家稅收必須增加，或者美元將貶值而且通貨膨脹率將下降"。,C ＝P ?(Q?R),P：國家稅收增加Q：通貨膨脹率下降R：美元貶值,A ＝ ?R ?(P ?Q)B ＝ (Q ??

46、R) ??PC ＝P ?(Q?R),(A?B?C) ?Q ＝ ?P?Q ??R≠T, 論證錯誤!,例 某公司要從趙、錢、孫、李、周五名新畢業(yè)的大學(xué)生中選派一些人出國學(xué)習(xí). 選派必須滿足以下條件： (1)若趙去，錢也去； (2)李、周兩人中至少有一人去； (3)錢、孫兩人中有一人去且僅去一人； (4)孫、李兩人同去或同不去； (5)若周去，則趙、錢也去. 試用主析取范式法分析該公司如何選派他們出國

47、？,49,解此類問題的步驟為：① 將簡單命題符號化② 寫出各復(fù)合命題③ 寫出由②中復(fù)合命題組成的合取式 ④ 求③中所得公式的主析取范式,50,例 (續(xù)),解 ① 設(shè)p：派趙去，q：派錢去，r：派孫去， s：派李去，u：派周去. ② (1)若趙去，錢也去； (p?q) (2)李、周兩人中至少有一人去；

48、 (s?u) (3)錢、孫兩人中有一人去且僅去一人； ((q??r)?(?q?r)) (4)孫、李兩人同去或同不去； ((r?s)?(?r??s)) (5)若周去，則趙、錢也去. (u?(p?q)),5

49、1,④ A的演算過程如下: A ? (?p?q)?((q??r)?(?q?r)) ?(s?u)?(?u?(p?q)) ? ((r?s)?(?r??s)) （交換律) B1= (?p?q)?((q??r)?(?q?r)) ? (?p?q??r)?(?p??q?r)?(q??r) （分配律）,52,③

50、(1) ~ (5)構(gòu)成的合取式為 A=(p?q)?(s?u)?[(q??r)?(?q?r)]? [(r?s)?(?r??s)]?[u?(p?q)],例 (續(xù)),B2= (s?u)?(?u?(p?q)) ? (s??u)?(p?q?s)?(p?q?u) （分配律）B1 ? (?p?q??r)?(?p??q?r)?(q??r)B1?B2 ? (?p?q??r?s??u)?(?

51、p??q?r?s??u) ?(q??r?s??u)?(p?q??r?s)?(p?q??r?u)再令 B3 = ((r?s)?(?r??s))得 A ? B1?B2?B3 ? (?p??q?r?s??u)?(p?q??r??s?u)結(jié)論：A的成真賦值為00110與11001，因而派孫、李去（趙、錢、周不去）或派趙、錢、周去（孫、李不去）.,53,54/48,本堂課的內(nèi)容、重點與難點,合(析)取

52、式與成真(假)解釋求解范式、主范式,等價公式的熟練運用等價變換法、解釋法、真值表法的靈活運用,合取式、析取式 合取范式、析取范式 極小項、極大項 主合取范式、主析取范式,55/48,作業(yè)02,1.8(1) 1.9(1) 補1. 試寫出下列公式的主范式：   (p→q)→r，p→(q→r)， (p∧q)→r補2(選做). 設(shè)在一個合式公式中，命題變元出現(xiàn)的次數(shù)為M，二元聯(lián)結(jié)詞出現(xiàn)的次數(shù)是N，試證明：