第二章命題邏輯的等值和推理演算

1、第二章 命題邏輯的等值和推理演算 n推理形式和推理演算是數理邏輯研究的基本內容 n推理過程是從前提出發(fā)，根據所規(guī)定的規(guī)則來推導出結論的過程 n重言式是重要的邏輯規(guī)律，正確的推理形式，等值式都是重言式。 n本章對命題等值和推理演算進行討論，是以語義的觀點進行的非形式的描述，不僅直觀且容易理解，也便于實際問題的邏輯描述和推理。n嚴格的形式化的討論見第三章所建立的公理系統(tǒng)。 2.1 等值定理 n若把初等數學里的、等運算符看作是數與數之間的聯(lián)結詞，那么由這些聯(lián)結詞所表達的代數式之間，可建立許多等值式如下：x2y2 = (xy)(xy)(xy)2 = x22xyy2 sin2xcos2x = 1在命題邏

2、輯里也同樣可建立一些重要的等值式。 2.1.1 等值的定義 n給定兩個命題公式A和B, 而P1Pn是出現(xiàn)于A和B中的所有命題變項, 那么公式A和B共有2n個解釋, 若對其中的任一解釋, 公式A和B的真值都相等, 就稱A和B是等值的(或等價的)。記作A = B或A B。 n顯然，可以根據真值表來判明任何兩個公式是否是等值的。例1: 證明(PP)Q = Q證明: 畫出(PP)Q與Q的真值表可看出等式是成立的。例2: 證明PP = QQn證明: 畫出PP, QQ的真值表, 可看出它們是等值的, 而且它們都是重言式。n從例1、2還可說明, 兩個公式等值并不要求它們一定含有相同的命題變項。若僅在等式一端

3、的公式里有變項P出現(xiàn), 那么等式兩端的公式其真值均與P無關。例1中公式(PP) Q與Q的真值都同P無關, 例2中PP, QQ都是重言式, 它們的真值也都與P、Q無關。 2.1.2 等值定理 n定理 對公式A和B, A = B的充分必要條件是A B是重言式。n若A B為重言式(A、B不一定都是簡單命題, 可能是由簡單命題P1, , Pn構成的對A, B的一個解釋, 指的是對P1, , Pn的一組具體的真值設定), 則在任一解釋下A和B都只能有相同的真值, 這就是定理的意思。 證明n若A B是重言式, 即在任一解釋下, A B的真值都為T。依A B的定義只有在A、B有相同的值時, 才有A B =

4、T。于是在任一解釋下, A和B都有相同的真值, 從而有A=B。反過來，若有A = B, 即在任一解釋下A和B都有相同的真值, 依A B的定義, A B只有為真, 從而A B是重言式。 n有了這個等值定理，證明兩個公式等值，只要證明由這兩個公式構成的雙條件式是重言式即可。 不要將“”視作聯(lián)結詞，在合式公式定義里沒有“”出現(xiàn)。A = B是表示公式A與B的一種關系。這種關系具有三個性質: 1. 自反性 A = A。2. 對稱性 若A = B則B = A。3. 傳遞性 若A = B, B = C則A = C。這三條性質體現(xiàn)了“”的實質含義。 2.2 等值公式2.2.1 基本的等值公式(命題定律)1.

5、雙重否定律P = P2. 結合律(PQ) R = P(QR)(PQ) R = P(QR)(P Q) R = P (Q R)3. 交換律PQ = QPPQ = QPP Q = Q P4. 分配律P(QR) = (PQ)(PR)P(QR) = (PQ)(PR)P(QR) = (PQ)(PR)5. 等冪律(恒等律)PP = PPP = PPP = TPP = T6. 吸收律P(PQ) = PP(PQ) = P7. 摩根律(PQ) = PQ(PQ) = PQ對蘊涵詞、雙條件詞作否定有(PQ) = PQ(PQ) = PQ = PQ= (PQ)(PQ)n8. 同一律nPF = PnPT = PnTP =

6、PnTP = Pn還有nPF = PnFP = P 9. 零律PT = TPF = F還有PT = TFP = T10. 補余律PP = TPP = F還有PP = PPP = PPP = F n所有這些公式，都可使用直值表加以驗證。 Venn圖n若使用Venn圖也容易理解這些等值式, 這種圖是將P、Q理解為某總體論域上的子集合, 而規(guī)定PQ為兩集合的公共部分(交集合), PQ為兩集合的全部(并集合), P為總體論域(如矩形域)中P的余集。 從Venn 圖因PQ較P來得“小”, PQ較P來得“大”，從而有P(PQ) = PP(PQ) = P對這些等式使用自然用語加以說明，將有助于理解。如P表示

7、張三是學生, Q表示李四是工人, 那么(PQ)就表示并非“張三是學生或者李四是工人”。這相當于說，“張三不是學生而且李四也不是工人”，即可由PQ表示, 從而有(PQ) = PQ。 2.2.2 若干常用的等值公式 n由于人們對、更為熟悉，常將含有和的公式化成僅含有、的公式。這也是證明和理解含有，的公式的一般方法。n公式11-18是等值演算中經常使用的,也該掌握它們, 特別是能直觀地解釋它們的成立。 11. PQ = P Qn通常對PQ進行運算時, 不如用PQ來得方便。而且以PQ表示PQ幫助我們理解如果P則Q的邏輯含義。問題是這種表示也有缺點，丟失了P、Q間的因果關系。 12. PQ = QPn如

8、將PQ視為正定理, 那么QP就是相應的逆否定理, 它們必然同時為真, 同時為假, 所以是等值的。 13. P(QR) = (PQ)RnP是(QR)的前提, Q是R的前提, 于是可將兩個前提的合取PQ作為總的前提。 即如果P則如果Q則R, 等價于如果P與Q則R。 14. PQ = (PQ)(PQ)n這可解釋為PQ為真, 有兩種可能的情形, 即(PQ)為真或(PQ)為真。而PQ為真, 必是在P = Q = T的情況下出現(xiàn), PQ為真, 必是在P = Q = F的情況下出現(xiàn)。從而可說, PQ為真, 是在P、Q同時為真或同時為假時成立。這就是從取真來描述這等式。 15. PQ = (PQ)(PQ)n這

9、可解釋為PQ為假, 有兩種可能的情形, 即(PQ)為假或(PQ)為假, 而PQ為假, 必是在P = F, Q = T的情況下出現(xiàn), PQ為假, 必是在P = T, Q = F的情況下出現(xiàn)。從而可說PQ為假, 是在P真Q假或P假Q真 時成立。這就是從取假來描述這等式 16. PQ = (PQ)(QP)n這表明PQ成立, 等價于正定理PQ和逆定理QP都成立。 17. P(QR) = Q(PR)n前提條件P、Q可交換次序。 18. (PR) (QR)=(PQ)Rn左端說明的是由P而且由Q都有R成立。從而可以說由P或Q就有R成立, 這就是等式右端。2.2.3 置換規(guī)則 定理: 對公式A的子公式, 用與

10、之等值的公式來代換便稱置換。置換規(guī)則 公式A的子公式置換后A化為公式B, 必有A = B。當A是重言式時, 置換后的公式B必也是重言式。n置換與代入是有區(qū)別的。置換只要求A的某一子公式作代換, 不必對所有同一的子公式都作代換。 2.2.4 等值演算舉例 例1: 證明(P(QR)(QR)(PR) = R證明: 左端= (P(QR) (QP)R)(分配律)=(PQ)R)(QP)R)(結合律)=(PQ)R)(QP)R)(摩根律)=(PQ)(QP)R(分配律)=(PQ)(PQ)R(交換律)=TR(置 換)=R(同一律) 例2: 試證 (PQ)(P(QR) (PQ)(PR) = T證明:左端=(PQ)(

11、P(QR)(PQ)(PR)(摩根律)=(PQ)(PQ)(PR)(PQ)(PR) (分配律)=(PQ)(PR)(PQ)(PR)(等冪律)=T2.6 范式nn 個命題變項所能組成的具有不同真值的命題公式僅有22n個, 然而與任何一個命題公式等值而形式不同的命題公式可以有無窮多個。這樣，首先就要問凡與命題公式A等值的公式，能否都可以化為某一個統(tǒng)一的標準形式。希望這種標準形能為我們的討論帶來些方便，如借助于標準形對任意兩個形式上不同的公式，可判斷它們的是否等值。借助于標準形容易判斷任一公式是否為重言式或矛盾式。求解公式的成真指派和成假指派 n一個公式，其中含有命題變元P1, ,Pn, 表示為 P1,

12、,Pn，（P1, ,Pn）稱為變元組，公式的變元組（P1, ,Pn）的任意一組確定的值，稱為對該公式的關于該變元組（P1, ,Pn）的一個完全指派。如果僅對變元組中的部分變元確定值，其余變元沒有賦以確定的值，則稱這樣的一組值為該公式的關于變元組的一個部分指派。完全指派與部分指派例如公式 ： p(qr)。 變元組為（p，q，r），一個完全指派為（T，F(xiàn)，F(xiàn)），在此指派下，公式取真值。即 = T?？蛇@樣來表示：（p，q，r）=（T，F(xiàn)，F(xiàn)） = T或者有時記為： （p，q，r）=（T，F(xiàn)，F(xiàn)） = T 一個部分指派為（T，T，）這時候 的值不能確定，當r = T時， = T，當r = F時，= F

13、。這一點通常都能理解，因為一個公式的值取決于公式中所含變元的值，當其中某些變元未確定時，公式最終的值也不能定。但是這一點也未必絕對，例如，賦（p，q，r）以（F，X，X）時，公式肯定是取假值，即= F。這時候可看出對q，r 的指派已經無關緊要了。成真指派與成假指派n定義：對于任一公式，凡是使得 取真值 = T 的指派，不管是完全指派還是部分指派，都稱為 的成真指派。凡是使 取假值 = F 的指派，不管是完全指派還是部分指派，都稱為 的成假指派。 例子：P 的成真指派 P=F, 成假指派P=T。：PQ 的成真指派（P，Q）=（T，T） 成假指派（P，Q）=（F，F(xiàn)），（F，T），（T，F(xiàn)）：PQ

14、 的成真指派（P，Q）=（T，T），（T，F(xiàn)），（F，T） 成假指派（P，Q）=（F，F(xiàn)）永真式、永假式、可滿足式有的公式沒有成真指派，如：PP, 稱為永假式（反駁式）；有的公式沒有成假指派，如：PP, 稱為永真式（重言式）。永假式，又稱為矛盾式，不可滿足。如果一個公式，有成真指派，則稱為公式 可滿足。與它相對的，如果沒有成真指派，就是不可滿足的。如果一個公式，有成假指派，則稱該公式為非永真公式。部分指派公式 的變元組（P1, ,Pn），一個部分指派 ：（V1, Vi-1, X, Vi+1, Vn），其中Vi為具體真假值。它為公式 的成真指派，當且僅當：（V1, Vi-1, T, Vi+1,

15、Vn）及（V1, Vi-1, F, Vi+1, Vn）均為成真指派。成假指派情況是相似的。求解成真指派和成假指派的方法n一個直截了當的辦法是將公式 的所有完全指派全都列舉出來，逐個驗算該指派下 取的真假值，從而確定每個完全指派是成真指派還是成假指派。但是，含n個變元的公式，共有2n個完全指派，當n為5、6、時，指數的總數就會相當可觀，按指數級數增長，難以全部枚舉。因此應當選擇更為簡單、可行的辦法部分指派。求部分指派的前提是將原來的公式 化簡，使得原來含有n個變元的公式化為可能含變元數更少的公式，于是便大大地削減了運算的數量。部分指派的步驟n第一步，否定深入。將外層的否定深入到內層，一直深入到變

16、元為止。n第二步，部分指派。選定一個變元對其作真和假兩種指派，得到兩個不含該變元但較原式簡單的公式。如果這兩個公式直接得到真假值，則得部分指派，否則n第三步，化簡。得到的兩公式雖然較原公式簡單，但仍含有變元，于是重復第二步，逐個減少變元，直到確定真假值為止。n第二步中如何選定一個變元，希望化簡效果最好，因此選擇在公式中出現(xiàn)次數最多的變元作指派。還有一種情況就是對該變元賦以一個指派后，立即使整個公式有確定的真假值。試求給定公式的成真成假指派n：(p r) ( (p q) ( p (q r) ) )n第一步 否定深入：n (p r) ( (p q) (p (q r) ) )n第二步 部分指派：選擇

17、出現(xiàn)最多的命題，指派以T, F。（分別情況）。n 上式中，P出現(xiàn)最多，故 分為 p = T n p = F兩種情況。 p = T ：(T r ) （T q ）（T (q r)） 化簡(q (q r)也可最終化簡為r， p = F ：(F r ) （F q ）（F (q r)） 化簡得 r（T F）最終化簡得r組合起來，的成真指派（p, q, r）= ( T, X, F ), (F, X, T ), 成假指派（p, q, r）= ( T, X, T ), (F, X, F )。不完全成真指派 (p, q, r): (T, X, F)可以生成相應的完全成真指派 (T, T, F ) 和 (T, F

18、, F )。 (p, q, r): (F, X, T) (F, T, T ) 和 (F, F, T )。因此，寫完整的話，的完全成真指派：(T, T, F )，(T, F, F )，(F, T, T )，(F, F, T )。相仿地，的完全成假指派：(T, X, T ) (T, T, T) ，(T, F, T )，(F, X, F ) (F, T, F )，(F, F, F )完全成假指派：(T, T, T) ，(T, F, T )，(F, T, F )，(F, F, F )。 析取范式如果一個完全指派能使一個合取式取真值，那么這個完全指派和合取式之間是對應的。例如： (T, T, F )，(

19、T, F, F )， (F, T, T )， (F, F, T )p q r p q r p q r p q r 將上述四個合取式再析取，即得析取范式：（p q r）（p q r）（p q r）（p q r）合取范式相仿地：對應于成假指派對應的析取式為：(T, T, T) ，(T, F, T )，(F, T, F )，(F, F, F )pqrpqrpqrp q r將四個析取式再合取，即得合取范式：（pqr）（pqr）（pqr）（pqr）求范式等值變換法n消去和n否定深入到變元n等值變換主范式n主析取范式n主合取范式2.4 聯(lián)結詞的完備集 除了所詳述過的五個聯(lián)結詞外, 還可定義更多的聯(lián)結詞。像

20、計算機的硬件電路設計分析就常使用異或(半加) : PQ = (PQ)(PQ)與非: P Q = (PQ)或非: P Q = (PQ)等聯(lián)結詞。問題是對n 個命題變項P1Pn 來說, 共可定義出多少個聯(lián)結詞? 還可以問, 在那么多聯(lián)結詞中有多少是獨立的? 2.4.1 命題聯(lián)結詞的個數n按照合式公式的定義，由命題變項和命題聯(lián)結詞可以構造出無限多個合式公式。可把所有的合式公式加以分類 ，將等值的公式視為同一類，從中選一個作代表稱之為真值函項。對一個真值函項就有一個聯(lián)結詞與之對應。 n一元聯(lián)結詞是聯(lián)結一個命題變項的，如P。它取值只有真假兩種情形，于是聯(lián)結詞作用于P , 可建立四種不同的真值函項, 相應

21、的可定義出四個不同的一元聯(lián)結詞f0f1f2f3。圖6.2.4.1給出這些聯(lián)結詞fi或說真值函數fi(P)的定義。 寫出真值函項：f0(P) = Ff1(P) = Pf2(P) = Pf3(P) = T其中f0(P)是永假式, f3(P)是永真式, 均與P無關, 而f1(P)就是變項P本身, 從而新的公式只有f2(P), 這就是由否定詞所建立的真值函項。 n二元聯(lián)結詞聯(lián)結兩個命題變項，兩個變項PQ共有四種取值情形, 于是聯(lián)結詞作用于PQ可建立起16種不同的真值函項, 相應的可定義出16個不同的二元聯(lián)結詞g0, g1, , g15 。圖2.4.2給出了這些聯(lián)結詞gI或說真值函項gi(P, Q)的定

22、義。 寫出各真值函項:g0 (P,Q) = Fg1(P,Q) = PQg2(P,Q) = PQg3(P,Q) = (PQ)(PQ) = P(QQ) = Pg4(P,Q) = PQg5(P,Q) = (PQ)(PQ) = (PP)Q = Qg6(P,Q) = PQg7(P,Q) = PQg8(P,Q) = PQ = P Qg9(P,Q) = P Qg10(P,Q) = (PQ)(PQ) = (PP)Q = Qg11(P,Q) = PQ = QPg12(P,Q) = (P Q)(PQ) = P(QQ) = Pg13(P,Q) = PQ = P Qg14(P,Q) = PQ = P Qg15(P,Q

23、) = Tn一般地說，對n 個命題變元P1Pn, 每個Pi有兩種取值, 從而對P1Pn來說共有2n種取值情形。于是相應的直值函項就有22n個, 或說可定義22n個n元聯(lián)結詞。2.4.2 聯(lián)結詞的完備集 n由于可定義的聯(lián)結詞的數量是極大的, 需要考慮它們是否都是獨立的? 也就是說這些聯(lián)結詞是否能相互表示呢?n定義: 設C是聯(lián)結詞的集合，如果對任一命題公式都有由C中的聯(lián)結詞表示出來的公式與之等值，就說C是完備的聯(lián)結詞集合，或說C是聯(lián)結詞的完備集。 n顯然全體聯(lián)結詞的無限集合是完備的, 而, , 就不是完備的。n定理 , , 是完備的聯(lián)結詞集合n從節(jié)2.3介紹的由真值表列寫邏輯公式的過程可知, 任一

24、公式都可由, , 表示出來, 從而, , 是完備的, 一般情形下, 這定理的證明可使用數學歸納法, 施歸納于聯(lián)結詞的個數來論證。 又由于PQ = (PQ)PQ = (PQ)這說明, 可由, 表示, 可由, 表示, 故, , , 都是聯(lián)結詞的完備集。還可證明, , , 也都是聯(lián)結詞的完備集。但, , , 不是完備的。盡管, , 是完備的, 但使用起來并不夠方便, 我們愿意采取折衷方案, 不是僅用兩個也不是使用過多的聯(lián)結詞, 還是選用詳細討論過的五個聯(lián)結詞集, , , , , 當然是完備的, 只是相互并不獨立。 最小的聯(lián)結詞的完備集基底 n基底：完備的聯(lián)結詞集合的聯(lián)結詞是獨立的， 也就是說這些聯(lián)結

25、詞不能相互表示基底 n只含一個聯(lián)結詞的: NK;NAn含兩個聯(lián)結詞的:N,C; N,K; N,A; N,NC; F,C; T,NC; C,NE; E,NC; C,NC;n含三個聯(lián)結詞的:F,K,E; F,A,E; T,K,NE; T,A,NE; K,E,NE; A,E,NE;A- K- E- C- N- 基底 n任取四個一元或二元聯(lián)結詞，它們必組不成基底。加法器 Ai 0 0 0 0 1 1 1 1Bi 0 0 1 1 0 0 1 1Ei 0 1 0 1 0 1 0 1_Ci 0 1 1 0 1 0 0 1Ei+1 0 0 0 1 0 1 1 1Ci=(AiBiEi)(AiBiEi)(AiBiEi)(AiBiEi)Ei+1=(AiBiEi)(AiBiEi)(Ai BiEi)(AiBiEi)E1=0Cn+1=En+12.5 對偶式 n假定公式A僅出現(xiàn) 、這三個聯(lián)結詞n定義 將A中出現(xiàn)的、分別以、代換, 得到公式A*, 則稱A*是A的對偶式, 或說A和A*互為對偶式。 (PQ)R的對偶式為(PQ)R不難知道, 若(PQ)R = (PR)(QR)成立, 相應的對偶式 (PQ)R = (PR)(QR)也成立。為方便, 若A=A(P1, , Pn)令 A= A(