1、第2章 命題邏輯等值演算離 散 數 學介紹本章說明本章的主要內容等值式與基本的等值式等值演算與置換規(guī)則析取范式與合取范式、主析取范式與主合取范式聯(lián)結詞完備集(不講)可滿足性問題與消解法（不講）本章與后續(xù)各章的關系是第一章的抽象與延伸是后續(xù)各章的現行準備2.1 等值式兩公式什么時候代表了同一個命題呢？ 抽象地看，它們的真假取值完全相同時即 代表了相同的命題。設公式A,B共同含有n個命題變項，可能對A或B有啞元，若A與B有相同的真值表，則說明在2n個賦值的每個賦值下，A與B的真值都相同。于是等價式AB應為重言式。 等值的定義及說明 設A,B是兩個命題公式，若A,B構成的等價式AB為重言式，則稱A與

2、B是等值的，記作AB。 說明定義中,A,B,都是元語言符號。A或B中可能有啞元出現。pq (pq)(rr)r為左邊公式中的啞元。用真值表可以驗證兩個公式是否等值。例題例2.1 判斷下面兩個公式是否等值(pq) 與 pq 解答說明在用真值表法判斷AB是否為重言式時，真值表的最后一列可以省略。等值例題 判斷下列各組公式是否等值(1)p(qr)與(pq)r (2)(pq)r與(pq)r 解答等值不等值基本等值式A A2.冪等律A AA,A AA 3.交換律AB BA，AB BA4.結合律(AB)C A(BC) (AB)C A(BC) 5.分配律A(BC) (AB)(AC) （對的分配律）A(BC)

3、(AB)(AC)（對的分配律）摩根律(AB) AB(AB) AB 7.吸收律A(AB) A，A(AB) A 基本等值式 8.零律A1 1,A0 0 9.同一律A0 A，A1 A 10.排中律AA 1 11.矛盾律AA 0 12.蘊涵等值式AB AB13.等價等值式AB (AB)(BA)14.假言易位AB BA15.等價否定等值式AB AB16.歸謬論(AB)(AB) A 對偶原理一個邏輯等值式，如果只含有、0、1那么同時把和互換把0和1互換得到的還是等值式。等值演算與置換規(guī)則各等值式都是用元語言符號書寫的，其中A,B,C可以代表任意的公式，稱這樣的等值式為等值式模式。每個等值式模式都給出了無窮

4、多個同類型的具體的等值式。例如，在蘊涵等值式 ABAB 中，取A=p，B=q時，得等值式 pqpq 取A=pqr，B=pq時，得等值式(pqr)(pq) (pqr)(pq)這些具體的等值式都被稱為原來的等值式模式的代入實例。由已知的等值式推演出另外一些等值式的過程為等值演算。置換規(guī)則 設(A)是含公式A的命題公式，(B)是用公式B置換了(A)中所有的A后得到的命題公式，若BA，則(B)(A)。關于等值演算的說明等值演算的基礎等值關系的性質：自反性：AA。對稱性：若AB，則BA。傳遞性：若AB且BC，則AC。基本的等值式置換規(guī)則等值演算的應用證明兩個公式等值判斷公式類型解判定問題例題利用基本的等

5、價關系，完成如下工作：（1）判斷公式的類型： 證明 () ()()()是一個永真公式。（2）證明公式之間的等價關系：證明() = ()（3）化簡公式：證明(P(R)(R)(PR) = R 等值演算的應用舉例證明兩個公式等值(pq)r (pr)(qr)(pq)r (pq)r（蘊含等值式、置換規(guī)則） (pq)r（蘊含等值式、置換規(guī)則） (pq)r（德摩根律、置換規(guī)則） (pr)(qr)（分配律、置換規(guī)則）說明也可以從右邊開始演算因為每一步都用置換規(guī)則，故可不寫出熟練后，基本等值式也可以不寫出通常不用等值演算直接證明兩個公式不等值解答例題 用等值演算法驗證等值式(pq)r (pr)(qr) (pr)

6、(qr) (pr)(qr)(蘊含等值式) (pq)r(分配律) (pq)r(德摩根律) (pq)r(蘊含等值式) 解答例題 證明：(pq)r 與 p(qr) 不等值方法一、真值表法。 方法二、觀察法。易知，010是(pq)r的成假賦值，而010是p(qr)的成真賦值，所以原不等值式成立。 方法三、通過等值演算化成容易觀察真值的情況，再進行判斷。A=(pq)r (pq)r （蘊涵等值式） (pq)r （蘊涵等值式） (pq)r （德摩根律） B=p(qr) p(qr) （蘊涵等值式） pqr （結合律） 000，010是A的成假賦值，而它們是B的成真賦值。 解答例題 用等值演算判斷下列公式的類型

7、：（1）(pq)pq （2）(p(pq)r （3）p(pq)p)q) 例2.5 解答(1) (pq)pq (pq)pq （蘊涵等值式） (pq)p)q （蘊涵等值式） (pq)p)q （德摩根律） (pq)p)q（德摩根律） (pp)(qp)q （分配律） (1(qp)q （排中律） (qq)p （同一律） 1p（排中律） 1 （零律）例2.5 解答(2) (p(pq)r (ppq)r (ppq)r 0r 0(3) p(pq)p)q) p(pq)p)q) p(pp)(qp)q) p(0(qp)q) p(qpq) p1 p例2.6 應用題在某次研討會的中間休息時間，3名與會者根據王教授的口音對他

8、是哪個省市的人進行了判斷：甲說王教授不是蘇州人，是上海人。乙說王教授不是上海人，是蘇州人。丙說王教授既不是上海人，也不是杭州人。聽完以上3人的判斷后，王教授笑著說，他們3人中有一人說的全對，有一人說對了一半，另一人說的全不對。試用邏輯演算法分析王教授到底是哪里人？ 例2.6 解答設命題 p：王教授是蘇州人。 q：王教授是上海人。 r：王教授是杭州人。p,q,r中必有一個真命題，兩個假命題，要通過邏輯演算將真命題找出來。設甲的判斷為A1=pq乙的判斷為A2=pq 丙的判斷為A3=qr 例2.6 解答甲的判斷全對B1=A1=pq甲的判斷對一半 B2=(pq)(pq)甲的判斷全錯 B3=pq乙的判斷

9、全對 C1=A2=pq乙的判斷對一半 C2=(pq)(pq)乙的判斷全錯 C3=pq丙的判斷全對 D1=A3=qr丙的判斷對一半 D2=(qr)(qr)丙的判斷全錯 D3=qr例2.6 解答由王教授所說E = (B1C2D3)(B1C3D2)(B2C1D3) (B2C3D1)(B2C1D2)(B3C2D1)為真命題。 經過等值演算后,可得E (pqr)(pqr) 由題設，王教授不能既是上海人，又是杭州人，因而p,r中必有一個假命題，即pqr0，于是E pqr為真命題，因而必有p,r為假命題，q為真命題，即王教授是上海人。甲說的全對，丙說對了一半，而乙全說錯了。例的進一步思考王教授只可能是其中一

10、個城市的人或者三個城市都不是。所以，丙至少說對了一半。因此，可得甲或乙必有一人全錯了。又因為，若甲全錯了，則有pq，因此乙全對。同理，乙全錯則甲全對。所以丙必是一對一錯。根據上述推理，可對公式E進行簡化，方便等值演算。(如何簡化，請同學們課后思考)命題公式的應用 例1. 利用基本的等價關系，化簡下列電路圖 &11&TSRQPRPSQPSPQRP解：上述電路圖可描述為：（1）(PQR)(PQS)(PR)(PS)（2）(PQR)(PQS)(PST)1.（續(xù)）利用16個基本等價關系，化簡公式(1)、(2)可得： （1）(PQR)(PQS)(PR)(PS) = (PQ(RS)(P(RS) = PQ(R

11、S)； （2）(PQR)(PQS)(PST) = (PQS)(PST) = (PQS)。 SRQPPSQ1例2將下面程序語言進行化簡。If A then if B then X else Y else if B then X else Y TFFTFTStartAXYEndBB 解：執(zhí)行X的條件為： ()() 執(zhí)行Y的條件為： ()()例2(續(xù)） 執(zhí)行X的條件可化簡為：()()( )執(zhí)行Y的條件可化簡為：()() ()TXYEndStartAF程序可簡化為：If B then X else Y 例3有一邏輯學家誤入某部落，被拘于勞獄，酋長意欲放行，他對邏輯學家說： “今有兩門，一為自由，一為死

12、亡，你可任意開啟一門。為協(xié)助你脫逃，今加派兩名戰(zhàn)士負責解答你所提的任何問題。惟可慮者，此兩戰(zhàn)士中一名天性誠實，一名說謊成性，今后生死由你自己選擇?！?邏輯學家沉思片刻，即向一戰(zhàn)士發(fā)問，然后開門從容離去。該邏輯學家應如何發(fā)問？ 解：P:被問戰(zhàn)士是誠實人； Q:被問戰(zhàn)士的回答是“是”R:另一名戰(zhàn)士的回答是“是”S:這扇門是死亡門。 P QR S 0 011 0 100 1 001 1 110邏輯學家手指一門問身旁的一名戰(zhàn)士說:“這扇門是死亡門，他(指另一名戰(zhàn)士)將回答是,對嗎？” 當被問戰(zhàn)士回答“對”,則邏輯學家開啟所指的門從容離去。當被問的戰(zhàn)士回答“否”,則邏輯學家開啟另一扇門從容離去。邏輯學家

13、能夠從容離去嗎？例4一家航空公司，為了保證安全，用計算機復核飛行計劃。每臺計算機能給出飛行計劃正確或有誤的回答。由于計算機也有可能發(fā)生故障，因此采用三臺計算機同時復核。由所給答案，再根據“少數服從多數”的原則作出判斷，試將結果用命題公式表示，并加以簡化，畫出電路圖。 解：設C1，C2，C3分別表示三臺計算機的答案。S表示判斷結果。 C1 C2 C3 S 0 0 0 0 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 真值表則根據真值表，利用聯(lián)結詞的定義，S可用C1，C2，C3所對應的命題公式表示出來，同時可畫出該命題公式所對應的電

14、路圖。解：（續(xù)） S= (C1C2C3)(C1C2C3) (C1C2C3)(C1C2C3) =(C1C1)C2C3)(C1(C2C2) C3)(C1C2(C3C3) =(C2C3)(C1C3)(C1C2) C1C2C3S&112.2 析取范式和合取范式 命題變項及其否定統(tǒng)稱作文字（letters）。僅由有限個文字構成的析取式稱作簡單析取式。僅由有限個文字構成的合取式稱作簡單合取式。簡單析取式舉例：p,qpp，pq pqr,pqr簡單合取式舉例：p,qpp，pqpqr,ppq說明一個文字既是簡單析取式，又是簡單合取式。2.2 析取范式和合取范式為討論方便，有時用A1,A2,As表示s個簡單析取式

15、或s個簡單合取式。設Ai是含n個文字的簡單析取式，若Ai中既含某個命題變項pj，又含它的否定式pj， 即pjpj，則Ai為重言式。反之，若Ai為重言式，則它必同時含某個命題變項和它的否定式，否則，若將Ai中的不帶否定符號的命題變項都取0值，帶否定號的命題變項都取1值，此賦值為Ai的成假賦值，這與Ai是重言式相矛盾。類似的討論可知，若Ai是含n個命題變項的簡單合取式，且Ai為矛盾式，則Ai中必同時含某個命題變項及它的否定式，反之亦然。 2.2 析取范式和合取范式(1)一個簡單析取式是重言式當且僅當它同時含有某個命題變項及它的否定式。(2)一個簡單合取式是矛盾式當且僅當它同時含有某個命題變項及它的

16、否定式。 (1)由有限個簡單合取式構成的析取式稱為析取范式（disjunctive normal form）。(2)由有限個簡單析取式構成的合取式稱為合取范式（conjunctive normal form）。(3)析取范式與合取范式統(tǒng)稱為范式。 2.2 析取范式和合取范式設Ai(i=1,2,s)為簡單合取式，則A=A1A2As為析取范式。例如，A1=pq，A2=qr，A3=p，則由A1,A2,A3構造的析取范式為A=A1A2A3=(pq)(qr)p 設Ai(i=1,2,s)為簡單析取式，則A=A1A2As為合取范式。例如，取A1=pqr，A2=pq，A3=r，則由A1,A2,A3組成的合取范

17、式為A=A1A2A3=(pqr)(pq)r說明形如pqr的公式既是一個簡單合取式構成的析取范式，又是由三個簡單析取式構成的合取范式。形如pqr的公式既是含三個簡單合取式的析取范式，又是含一個簡單析取式的合取范式。析取范式和合取范式的性質(1)一個析取范式是矛盾式當且僅當它的每個簡單合取式都是矛盾式。(2)一個合取范式是重言式當且僅當它的每個簡單析取式都是重言式。 說明研究范式的目的在于，將給定公式化成與之等值的析取范式或合取范式，進而將公式化成與之等值的主析取范式或主合取范式。范式存在的討論在范式中不會出現聯(lián)結詞與，否則可使用等值式消除AB ABAB (AB)(AB)在范式中不會出現形如A,(

18、AB),(AB)的公式：A A(AB) AB (AB)AB在析取范式中不會出現形如A(BC)的公式：A(BC) (AB)(AC)在合取范式中不出現形A(BC)的公式：A(BC) (AB)(AC) 任一命題公式都存在著與之等值的析取范式與合取范式。 求給定公式范式的步驟 (1)消去聯(lián)結詞、(若存在)。AB ABAB (AB)(AB)(2)否定號的消去(利用雙重否定律)或內移(利用德摩根律)。A A(AB) AB(AB)AB(3)利用分配律：利用對的分配律求析取范式， 對的分配律求合取范式。A(BC) (AB)(AC)A(BC) (AB)(AC)例題 求下面公式的析取范式與合取范式：(pq) r

19、(1) 求合取范式 (pq) r (pq) r （消去） (pq)r)(r(pq) （消去） (pq)r)(rpq)（消去） (pq)r)(pqr) （否定號內移） (pr)(qr)(pqr)（對分配律）解答例題(2) 求析取范式 (pq) r (pq)r)(pqr) (pqp)(pqq)(pqr) (rp)(rq)(rr) (pqr)(pr)(qr) 說明由此例可知，命題公式的析取范式不唯一。同樣，合取范式也是不唯一的。范式的規(guī)范化形式 在含有n個命題變項的簡單合取式（簡單析取式）中，若每個命題變項和它的否定式不同時出現，而二者之一必出現且僅出現一次，且第i個命題變項或它的否定式出現在從左算

20、起的第i位上（若命題變項無角標，就按字典順序排列），稱這樣的簡單合取式（簡單析取式）為極小項（極大項）。n個命題變項共可產生2n個不同的極小項。其中每個極小項都有且僅有一個成真賦值。若成真賦值所對應的二進制數轉換為十進制數i，就將所對應極小項記作mi 。類似地，n個命題變項共可產生2n個極大項，每個極大項只有一個成假賦值，將其對應的十進制數i做極大項的角標，記作Mi。表2.3 p,q形成的極小項與極大項 表2.4 p,q,r形成的極小項與極大項 范式的規(guī)范化形式 設mi與Mi是命題變項p1,p2,pn形成的極小項和極大項，則 mi Mi， Mi mi 設由n個命題變項構成的析取范式（合取范式）

21、中所有的簡單合取式（簡單析取式）都是極小項（極大項），則稱該析取范式（合取范式）為主析取范式（主合取范式）。 任何命題公式都存在著與之等值的主析取范式和主合取范式，并且是唯一的。 定理的證明(只證主析取范式的存在和唯一性)(1)證明存在性。設A是任一含n個命題變項的公式。由定理2.3可知，存在與A等值的析取范式A，即AA，若A的某個簡單合取式Ai中既不含命題變項pj，也不含它的否定式pj，則將Ai展成如下形式：Ai Ai1 Ai(pjpj) (Aipj)(Ajpj) 繼續(xù)這個過程，直到所有的簡單合取式都含任意命題變項或它的否定式。 若在演算過程中出現重復的命題變項以及極小項和矛盾式時，都應“消

22、去”：如用p代替pp，mi代替mimi，0代替矛盾式等。最后就將A化成與之等值的主析取范式A。 定理(2)證明唯一性。假設某一命題公式A存在兩個與之等值的主析取范式B和C，即AB且AC，則BC。由于B和C是不同的主析取范式，不妨設極小項mi只出現在B中而不出現在C中。于是，角標i的二進制表示為B的成真賦值，而為C的成假賦值。這與BC矛盾，因而B與C必相同。 需要說明求任何一個公式的主析取范式和主合取范式不僅要取決于該公式，而且取決于該公式所包含的命題變元。如公式： G1 = (PQ)Q， G2(P, Q, R) = (PQ)Q。前者是依賴于兩個命題變元的，后者應依賴于三個命題變元。 求主析取范

23、式和主合取范式的方法公式轉換法利用基本等價公式進行變換主范式真值表技術對公式的真值結果進行分解，分解成等價的極小項的析取或者極大項的合取求公式A的主析取范式的方法與步驟方法一、等值演算法(1)化歸為析取范式。 (2)除去析取范式中所有永假的析取項。(3)將析取式中重復出現的合取項和相同的變元合并。(4)對合取項補入沒有出現的命題變元，即添加如(pp)式，然后應用分配律展開公式。方法二、真值表法(1)寫出A的真值表。(2)找出A的成真賦值。(3)求出每個成真賦值對應的極小項（用名稱表示），按角標從小到大順序析取。求公式A的主合取范式的方法與步驟方法一、等值演算法(1)化歸為合取范式。 (2)除去

24、合取范式中所有永真的合取項。(3)將合取式中重復出現的析取項和相同的變元合并。(4)對析取項補入沒有出現的命題變元，即添加如(pp)式，然后應用分配律展開公式。方法二、真值表法(1)寫出A的真值表。(2)找出A的成假賦值。(3)求出每個成假賦值對應的極大項（用名稱表示），按角標從小到大順序析取。例2.8 求例2.7中公式的主析取范式和主合取范式。(1)求主析取范式(pq)r (pqr)(pr)(qr)pqr m4pr p（qq）r (pqr)(pqr) m1m3 qr (pp)qr (pqr)(pqr) m3m7 (pq)r m1m3m4m7例2.8 求例2.7中公式的主析取范式和主合取范式。

25、(2)求主合取范式(pq)r (pr)(qr)(pqr) pqr M5 pr p(qq)r (pqr)(pqr) M0M2 qr (pp)qr (pqr)(pqr) M2M6 (pq)r M0M2M5M6 例題 求命題公式 pq 的主析取范式和主合取范式。(1)求主合取范式pq pq M2(2)求析取范式pq pq （p（qq） （(pp)q） (pq)(pq)(pq)(pq) (pq)(pq)(pq) m0m1m3 解答pqp q001011100111主析取范式的用途 求公式的成真賦值與成假賦值判斷公式的類型 判斷兩個命題公式是否等值 應用主析取范式分析和解決實際問題 求公式的成真賦值與成

26、假賦值若公式A中含n個命題變項，A的主析取范式含s(0s2n)個極小項，則A有s個成真賦值，它們是所含極小項角標的二進制表示，其余2n-s個賦值都是成假賦值。在例2.8中，(pq)r m1m3m4m7,各極小項均含三個文字，因而各極小項的角標均為長為3的二進制數，它們分別是001，011，100，111，這四個賦值為該公式的成真賦值,其余的為成假賦值。在例2.9中，pq m0m1m3，這三個極小項均含兩個文字，它們的角標的二進制表示00，01，11為該公式的成真賦值，10是它的成假賦值。 判斷公式的類型設公式A中含n個命題變項，容易看出：A為重言式當且僅當A的主析取范式含全部2n個極小項。A為

27、矛盾式當且僅當A的主析取范式不含任何極小項。此時，記A的主析取范式為0。A為可滿足式當且僅當A的主析取范式至少含一個極小項。判斷公式的類型 用公式的主析取范式判斷公式的類型：(1) (pq)q (2) p(pq) (3) (pq)r解答(1)(pq)q （pq）q (pq)q 0 (2)p(pq) m0m1m2m3 (3)(pq)r m0m1m3m5m7 矛盾式重言式可滿足式判斷兩個命題公式是否等值設公式A,B共含有n個命題變項，按n個命題變項求出A與B的主析取范式A與B。若AB,則AB；否則，A與B不等值。 判斷下面兩組公式是否等值：(1) p與(pq)(pq) (2)(pq)r與(q)r

28、(1) p p(qq) (pq)(pq) m2m3 (pq)(pq) m2m3 兩公式等值。(2) (pq)r m1m3m4m5m7 (q)r m0m1m2m3m4m5m7 兩公式不等值。解答應用主析取范式分析和解決實際問題某科研所要從3名科研骨干A,B,C中挑選12名出國進修。由于工作原因，選派時要滿足以下條件：(1)若A去，則C同去。(2)若B去，則C不能去。(3)若C不去，則A或B可以去。問應如何選派他們去？ 分析：(1)將簡單命題符號化(2)寫出各復合命題(3)寫出由(2)中復合命題組成的合取式（前提）(4)將(3)中公式化成析取式（最好是主析取范式）(5)這樣每個小項就是一種可能產生

29、的結果。去掉不符合題意的小項，即得結論。 應用主析取范式分析和解決實際問題設 p:派A去，q:派B去，r:派C去 由已知條件可得公式 (pr)(qr)(r(pq) 經過演算可得 (pr)(qr)(r(pq) m1m2m5 由于 m1=pqr, m2=pqr, m5=pqr可知，選派方案有3種：(a)C去，而A,B都不去。(b)B去，而A,C都不去。(c)A,C去，而B不去。解答由公式的主析取范式求主合取范式 設公式A含n個命題變項。A的主析取范式含s(0s2n)個極小項，即沒有出現的極小項設為它們的角標的二進制表示為A的成真賦值，因而A的主析取范式為例題 由公式的主析取范式，求主合取范式： (

30、1) A m1m2 (A中含兩個命題變項p,q)(2) B m1m2m3 (B中含兩個命題變項p,q,r) 解答(1) A M0M3 (2) B M0M4M5M6M7 重言式與矛盾式的主合取范式設n為公式中命題變項個數矛盾式無成真賦值，因而矛盾式的主合取范式含2n個極大項。重言式無成假賦值，因而主合取范式不含任何極大項。將重言式的主合取范式記為1?？蓾M足式的主合取范式中極大項的個數一定小于2n。 真值表與范式的關系 AB當且僅當A與B有相同的真值表，又當且僅當A與B有相同的主析取范式（主合取范式）。真值表與主析取范式（主合取范式）是描述命題公式標準形式的兩種不同的等價形式。 n個命題變項共可產

31、生2n個極小項（極大項）可以產生的主析取范式（主合取范式）數目為：聯(lián)結詞的完備集定義2.6 稱F:0,1n0,1為n元真值函數n元真值函數共有 個每一個命題公式對應于一個真值函數每一個真值函數對應無窮多個命題公式1元真值函數 p 0 0 0 1 1 1 0 1 0 1 真值函數2元真值函數 p q 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 p q 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1聯(lián)結詞完備集定義2.7 設S是一個聯(lián)結詞集合, 如果任何n(n1) 元真值函數都可以