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

1、第二章 命題邏輯的等值和推理演算 推理形式和推理演算是數(shù)理邏輯研究的基本內(nèi)容 推理形式是由前提和結(jié)論經(jīng)蘊(yùn)涵詞聯(lián)結(jié)而成的推理過程是從前提出發(fā)，根據(jù)所規(guī)定的規(guī)則來推導(dǎo)出結(jié)論的過程 重言式是重要的邏輯規(guī)律，正確的推理形式、等值式都是重言式本章對命題等值和推理演算進(jìn)行討論，是以語義的觀點(diǎn)進(jìn)行的非形式的描述，不僅直觀且容易理解，也便于實(shí)際問題的邏輯描述和推理。嚴(yán)格的形式化的討論見第三章所建立的公理系統(tǒng)。 等值演算(考察邏輯關(guān)系符(=)等值定理、公式聯(lián)結(jié)詞的完備集(由個(gè)別聯(lián)結(jié)詞表示所有聯(lián)結(jié)詞的問題)對偶式(命題公式的對偶性)范式(命題公式的統(tǒng)一標(biāo)準(zhǔn)) 由真值表寫命題公式(由T寫、由F寫)推理演算(考察邏輯

2、關(guān)系符)推理形式(正確推理形式的表示)基本推理公式(各種三段論及五種證明方法)推理演算(證明推理公式的第六種方法，使用推理規(guī)則)歸結(jié)推理法(證明推理公式的第七種方法，常用反證法)2.1 等值定理 若把初等數(shù)學(xué)里的、等運(yùn)算符看作是數(shù)與數(shù)之間的聯(lián)結(jié)詞，那么由這些聯(lián)結(jié)詞所表達(dá)的代數(shù)式之間，可建立許多等值式如下：x2y2 = (xy)(xy)(xy)2 = x22xyy2 sin2xcos2x = 1在命題邏輯里也同樣可建立一些重要的等值式 2.1.1 等值的定義 給定兩個(gè)命題公式A和B, 而P1Pn是出現(xiàn)于A和B中的所有命題變項(xiàng), 那么公式A和B共有2n個(gè)解釋, 若對其中的任一解釋, 公式A和B的真

3、值都相等, 就稱A和B是等值的(或等價(jià)的)。記作A = B或AB顯然，可以根據(jù)真值表來判明任何兩個(gè)公式是否是等值的 例1: 證明(PP)Q = Q證明: 畫出(PP)Q與Q的真值表可看出等式是成立的。例2: 證明PP = QQ證明: 畫出PP, QQ的真值表, 可看出它們是等值的, 而且它們都是重言式。從例1、2還可說明, 兩個(gè)公式等值并不一定要求它們一定含有相同的命題變項(xiàng)若僅在等式一端的公式里有變項(xiàng)P出現(xiàn), 那么等式兩端的公式其真值均與P無關(guān)。例1中公式(PP)Q與Q的真值都同P無關(guān)例2中PP, QQ都是重言式, 它們的真值也都與P、Q無關(guān)。 說明2.1.2 等值定理 定理 對公式A和B,

4、A=B的充分必要條件是AB是重言式。A、B不一定都是簡單命題, 可能是由簡單命題P1, , Pn構(gòu)成的. 對A, B的一個(gè)解釋, 指的是對P1, , Pn的一組具體的真值設(shè)定.若AB為重言式, 則在任一解釋下A和B都只能有相同的真值, 這就是定理的意思。 證明若A B是重言式, 即在任一解釋下, A B的真值都為T依A B的定義只有在A、B有相同的值時(shí), 才有A B = T。于是在任一解釋下, A和B都有相同的真值, 從而有A=B。反過來，若有A = B, 即在任一解釋下A和B都有相同的真值, 依A B的定義, A B只有為真, 從而A B是重言式。注：根據(jù)該等值定理，證明兩個(gè)公式等值，只要證

5、明由這兩個(gè)公式構(gòu)成的雙條件式是重言式即可“”作為邏輯關(guān)系符是一種等價(jià)關(guān)系不要將“”視作聯(lián)結(jié)詞，在合式公式定義里沒有“”出現(xiàn)A = B是表示公式A與B的一種關(guān)系。這種關(guān)系具有三個(gè)性質(zhì): 1. 自反性 A = A2. 對稱性 若A = B, 則B = A3. 傳遞性 若A = B, B = C, 則A = C 這三條性質(zhì)體現(xiàn)了“”的實(shí)質(zhì)含義。 2.2 等值公式2.2.1 基本的等值公式(命題定律, P和Q是任意的命題公式)1. 雙重否定律P = P2. 結(jié)合律(PQ)R = P(QR)(PQ)R = P(QR)(P Q) R = P (Q R)注: 所有這些公式，都可使用真值表加以驗(yàn)證3. 交換律

6、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對蘊(yùn)涵詞、雙條件詞作否定有(PQ) = PQ(PQ) = PQ = PQ= (PQ)(PQ)8. 同一律PF = PPT = PTP = PTP = P還有PF = PFP = P 9. 零律PT = TPF = F還有PT = TFP = T10. 補(bǔ)余律PP = TPP =

7、F還有PP = PPP = PPP = F Venn圖(理解等式)將P、Q理解為某總體論域上的子集合，并規(guī)定：PQ為兩集合的公共部分(交集合)PQ為兩集合的全部(并集合)P為總體論域(如矩形域)中P的余集Venn圖(理解等式)從Venn 圖，因PQ較P來得“小”, PQ較P來得“大”，從而有P(PQ) = PP(PQ) = P理解等式: Venn圖，自然語言(PQ) = PQVenn圖(理解集合間、命題邏輯中、部分信息量間的一些關(guān)系)對這些等式使用自然用語加以說明，將有助于理解如P表示張三是學(xué)生, Q表示李四是工人, 那么(PQ)就表示并非“張三是學(xué)生或者李四是工人”。這相當(dāng)于說，“張三不是學(xué)

8、生而且李四也不是工人”，即可由PQ表示, 從而有(PQ) = PQ2.2.2 常用的等值公式 由于人們對、更為熟悉，常將含有和的公式化成僅含有、的公式。這也是證明和理解含有，的公式的一般方法公式11-18是等值演算中經(jīng)常使用的, 也該掌握它們, 特別是能直觀地解釋它們的成立11. PQ = P Q通常對PQ進(jìn)行運(yùn)算時(shí), 不如用PQ來得方便。而且以PQ表示PQ幫助我們理解如果P則Q的邏輯含義問題是這種表示也有缺點(diǎn)，丟失了P、Q間的因果關(guān)系 12. PQ = QP逆否定理，假言易位如將PQ視為正定理, 那么QP就是相應(yīng)的逆否定理, 它們必然同時(shí)為真, 同時(shí)為假, 所以是等值的13. P(QR) =

9、 (PQ)R前提合并P是(QR)的前提, Q是R的前提, 于是可將兩個(gè)前提的合取PQ作為總的前提。 即如果P則如果Q則R, 等價(jià)于如果P與Q則R14. PQ = (PQ)(PQ)從取真來描述雙條件這可解釋為PQ為真, 有兩種可能的情形, 即(PQ)為真或(PQ)為真。而PQ為真, 必是在P = Q = T的情況下出現(xiàn); PQ為真, 必是在P = Q = F的情況下出現(xiàn)。從而可說, PQ為真, 是在P、Q同時(shí)為真或同時(shí)為假時(shí)成立。這就是從取真來描述這等式 15. PQ = (PQ)(PQ)從取假來描述雙條件這可解釋為PQ為假, 有兩種可能的情形, 即(PQ)為假或(PQ)為假, 而PQ為假, 必

10、是在P = F, Q = T的情況下出現(xiàn); PQ為假, 必是在P = T, Q = F的情況下出現(xiàn)。從而可說PQ為假, 是在P真Q假或P假Q(mào)真時(shí)成立。這就是從取假來描述這等式 16. PQ = (PQ)(QP)從蘊(yùn)含詞來描述雙條件這表明PQ成立, 等價(jià)于正定理PQ和逆定理QP都成立 17. P(QR) = Q(PR)前提交換前提條件P、Q可交換次序 18. (PR)(QR)=(PQ)R左端說明的是由P而且由Q都有R成立。從而可以說由P或Q就有R成立, 這就是等式右端補(bǔ)充等價(jià)否定等值式PQ = PQ歸謬論(PQ)(PQ) = P2.2.3 置換規(guī)則 置換定義對公式A的子公式, 用與之等值的公式來

11、代換便稱置換置換規(guī)則公式A的子公式置換后A化為公式B, 必有A = B當(dāng)A是重言式時(shí), 置換后的公式B必也是重言式置換與代入是有區(qū)別的。置換只要求A的某一子公式作代換, 不必對所有同一的子公式都作代換代入規(guī)則回顧 A是一個(gè)公式，對A使用代入規(guī)則得公式B，若A是重言式，則B也是重言式為保證重言式經(jīng)代入規(guī)則仍得到保持，要求公式中被代換的只能是命題變元(原子命題), 而不能是復(fù)合命題對公式中某命題變元施以代入，必須對該公式中出現(xiàn)的所有同一命題變元代換以同一公式2.2.4 等值演算舉例 例1: 證明(P(QR)(QR)(PR) = R證明: 左端= (P(QR) (QP)R)(分配律)= (PQ)R)

12、(QP)R)(結(jié)合律)= (PQ)R)(QP)R)(摩根律)= (PQ)(QP)R(分配律)= (PQ)(PQ)R(交換律)= TR(置 換)= R(同一律) 例2: 試證 (PQ)(P(QR) (PQ)(PR) = T證明:左端=(PQ)(P(QR)(PQ)(PR)(摩根律)=(PQ)(PQ)(PR)(PQ)(PR)(分配律)=(PQ)(PR)(PQ)(PR)(等冪律)=T舉例 問題提出：由命題公式寫真值表是容易的，那么如何由真值表寫命題公式呢？2.3 命題公式與真值表關(guān)系2.3.1 從T來列寫記憶方法：各項(xiàng)間用，每項(xiàng)內(nèi)用每項(xiàng)內(nèi)書寫方法：例真值表中P=T且Q=F等價(jià)于PQ=T簡化方法：有時(shí)A

13、的表達(dá)通過A來描述2.3.2 從F來列寫記憶方法：各項(xiàng)間用 ，每項(xiàng)內(nèi)用每項(xiàng)內(nèi)書寫方法：例真值表中P=T且Q=F等價(jià)于PQ=F簡化方法：有時(shí)A的表達(dá)通過A來描述舉例從A的真值T直接: A = (P Q) (P Q) (P Q)間接: A = A = (P Q) = P Q從B的真值FB = (P Q) (P Q)當(dāng)C可取任意值C與P, Q = T, T無關(guān), 可適當(dāng)選取C的真值, 使其表達(dá)式簡單PQAABCFFTFTTFTTFTFTFFTFTTTTFFX作業(yè)(1)(P37) 1(1, 3), 22.4 聯(lián)結(jié)詞的完備集 問題的提出對n 個(gè)命題變項(xiàng)P1Pn來說, 共可定義出多少個(gè)聯(lián)結(jié)詞? 在那么多聯(lián)

14、結(jié)詞中有多少是相互獨(dú)立的?3個(gè)新聯(lián)結(jié)詞： 思考：考慮異或聯(lián)結(jié)詞與雙條件聯(lián)結(jié)詞的關(guān)系(可利用真值表)2.4.1 命題聯(lián)結(jié)詞的個(gè)數(shù)第一個(gè)問題?？啥x多少個(gè)聯(lián)結(jié)詞？由命題變項(xiàng)和命題聯(lián)結(jié)詞可以構(gòu)成無限多個(gè)合式公式把所有的合式公式分類：將等值的公式視為同一類，從中選一個(gè)作代表稱之為真值函項(xiàng)。對一個(gè)真值函項(xiàng)，或者說對于該類合式公式，就可定義一個(gè)聯(lián)結(jié)詞與之對應(yīng)例：等價(jià)類。自然數(shù)集合N被3除余數(shù)相同的自然數(shù)構(gòu)成3個(gè)集合N0 , N1 , N2一元聯(lián)結(jié)詞是聯(lián)結(jié)一個(gè)命題變項(xiàng)(如P)的P有真假2種值，因此P(自變量)上可定義4種一元聯(lián)結(jié)詞fi 或說真值函項(xiàng)fi(P), i = 1, 2, 3, 4一元聯(lián)結(jié)詞的個(gè)數(shù)由

15、真值表寫出真值函項(xiàng)的命題公式：f0(P) = F(永假式)f1(P) = P(P自身)f2(P) = P(否定詞)f3(P) = T(永真式)新的公式只有f2(P), 與之對應(yīng)的聯(lián)結(jié)詞是否定詞一元聯(lián)結(jié)詞二元聯(lián)結(jié)詞聯(lián)結(jié)兩個(gè)命題變項(xiàng)(如P、Q)兩個(gè)變項(xiàng)共有4種取值情形,于是P、Q上可建立起16種不同的真值函項(xiàng),相應(yīng)的可定義出16個(gè)不同的二元聯(lián)結(jié)詞g0, g1, , g15 圖2.4.2給出了這些聯(lián)結(jié)詞gi或說真值函項(xiàng)gi(P,Q)的真值表定義二元聯(lián)結(jié)詞的個(gè)數(shù)根據(jù)真值表寫出各真值函項(xiàng)的命題表達(dá)式:g0(P,Q) = F(永假式)g1(P,Q) = PQ (合取式)g2(P,Q) = PQ g3(P,

16、Q) = (PQ)(PQ) = P(QQ) = Pg4(P,Q) = PQ g5(P,Q) = (PQ)(PQ) = (PP)Q = Qg6(P,Q) = P Q (異或式)g7(P,Q) = PQ (析取式)g8(P,Q) = PQ = P Q(或非式) g9(P,Q) = P Q (雙條件式)g10(P,Q) = (PQ)(PQ) = (PP)Q = Qg11(P,Q) = PQ = QP(蘊(yùn)涵式)g12(P,Q) = (P Q)(PQ) = P(QQ) = Pg13(P,Q) = PQ = PQ(蘊(yùn)涵式)g14(P,Q) = PQ = P Q (與非式)g15(P,Q) = T (永真式

17、)n元聯(lián)結(jié)詞對n個(gè)命題變元P1 , , Pn , 每個(gè)Pi有兩種取值, 從而對P1Pn來說共有2n種取值情形于是相應(yīng)的真值函項(xiàng)就有22n個(gè), 或說可定義22n個(gè)n元聯(lián)結(jié)詞n元聯(lián)結(jié)詞的個(gè)數(shù)2.4.2 聯(lián)結(jié)詞的完備集 第二個(gè)問題。聯(lián)結(jié)詞是否都是獨(dú)立的，或者說能否相互表示?聯(lián)結(jié)詞的完備集定義: 設(shè)C是聯(lián)結(jié)詞的集合，如果對任一命題公式(能直接使用T和F)都有由C中的聯(lián)結(jié)詞表示出來的公式(不能直接使用T和F)與之等值，就說C是完備的聯(lián)結(jié)詞集合，或說C是聯(lián)結(jié)詞的完備集。1. 全體聯(lián)結(jié)詞的無限集合是完備的2. , , 是完備的聯(lián)結(jié)詞集合 證明：從2.3節(jié)介紹的由真值表列寫邏輯公式的過程可知, 任一公式都可由

18、, , 表示出來, 從而, , 是完備的3. , 是聯(lián)結(jié)詞的完備集(獨(dú)立的完備集)證明：PQ = (PQ)，因此可由, 表示4. , 是聯(lián)結(jié)詞的完備集(獨(dú)立的完備集)證明：PQ = (PQ)，因此可由, 表示完備集 5. , 是完備集(獨(dú)立的完備集)因?yàn)椋篜Q = PQ6. 是完備集(獨(dú)立的完備集)7. 是完備集(獨(dú)立的完備集)8. , , , , 是完備的 因?yàn)樗?中的集合完備集 , 不是完備的因?yàn)镕不能僅由該集合的聯(lián)結(jié)詞表達(dá)出, 不是完備的, 的任何子集都是不完備的 , 的任何子集也是不完備的(如果一個(gè)聯(lián)結(jié)詞的集合是不完備的，那么它的任何子集都是不完備的),不是完備的不完備集 最小的

19、聯(lián)結(jié)詞的完備集基底 基底：完備的聯(lián)結(jié)詞集合的聯(lián)結(jié)詞是獨(dú)立的，也就是說這些聯(lián)結(jié)詞不能相互表示任取四個(gè)一元或二元聯(lián)結(jié)詞，它們必組不成基底基底 只含一個(gè)聯(lián)結(jié)詞的: NK;NA含兩個(gè)聯(lián)結(jié)詞的:N,C; N,K; N,A; N,NC; F,C; T,NC; C,NE; E,NC; C,NC含三個(gè)聯(lián)結(jié)詞的:F,K,E; F,A,E; T,K,NE; T,A,NE; K,E,NE; A,E,NE其中：A- K- E- C- N- 2.5 對偶式 研究目的簡化等值公式的討論希望一個(gè)公式成立，能夠?qū)С雠c其“相像”的公式成立邏輯關(guān)系上看，是一種邏輯規(guī)律對偶式定義：將A中出現(xiàn)的、T、F分別以、F、T代換, 得到公式

20、A*, 則稱A*是A的對偶式, 或說A和A*互為對偶式注：這里假定A中僅出現(xiàn) 、三個(gè)聯(lián)結(jié)詞若A = B，必有A*=B*?新符號“-”: (代入規(guī)則、內(nèi)否式)若A=A(P1, , Pn)，令A(yù)= A(P1, , Pn)關(guān)于等值的三個(gè)定理定理2.5.1 (A*) = (A)*, (A) = (A) 定理2.5.2 (A*)* = A, (A)=A定理2.5.3 A = A* (摩根律的另一種形式)更多：(A B)* = A* B*，(A B)- = A- B- (A B)* = A* B*，(A B)- = A- B-對偶式相關(guān)定理 56性質(zhì)舉例A= (P (Q R) TA*= (P (Q R)

21、FA-= (P) (Q R) TA*- = (P) (Q R) FA-* = (P) (Q R) F定理2.5.3 A = A*證明: 可用數(shù)學(xué)歸納法, 施歸納于A中出現(xiàn)的 聯(lián)結(jié)詞個(gè)數(shù)n來證明基始: 設(shè)n=0, A中無聯(lián)結(jié)詞, 便有 A=P, 從而 A = P但 A* = P n=0時(shí)定理成立。歸納： 設(shè)n k時(shí)定理成立，來證n = k+1時(shí)定理也成立 n = k + 1 1, A中至少有一個(gè)聯(lián)結(jié)詞，可分為三種情形A = A1, A = A1A2, A = A1A2 其中A1, A2中聯(lián)結(jié)詞個(gè)數(shù)k。依歸納法假設(shè)，A1 = A1*, A2 = A2*定理2.5.3 A = A*當(dāng) A = A1時(shí)

22、 A = (A1) A = A1 = (A1*)歸納法假設(shè) = (A1)*定理2.5.1, 2.5.2 = A* A = A1定理2.5.3 A = A*當(dāng)A = A1A2時(shí)， A = (A1A2) = A1A2摩根律 = A1*A2*歸納法假設(shè) = (A1*A2*)A定義 = (A1A2)* A*定義 = A*另一種情況同理，從而定理得證。定理2.5.3 (摩根律) A = A*定理2.5.6 (1) A與A同永真, 同可滿足 (2) A與A*同永真, 同可滿足注：“A和B”同永真表示：A永真當(dāng)且僅當(dāng)B永真證明：設(shè)A是由命題變項(xiàng)P1,Pn構(gòu)成的命題公式。(1) 如果A永真，根據(jù)代入規(guī)則，則A

23、-永真。 如果A-永真，則(A-)-永真，又根據(jù)定理2.5.2有 A=(A-)-, 所以A永真(2) 根據(jù)定理2.5.3，A = A*，所以根據(jù)(1)可得(2)成立對偶式相關(guān)定理 定理 2.5.4 若A = B，必有A*=B*證明: 因?yàn)锳 = B等價(jià)于AB 永真等價(jià)于AB永真。依定理2.5.3, A = A*, B = B* 于是A* B*永真，則(A*- B*-)-永真(根據(jù)代入規(guī)則，A永真，A-永真)亦即 A* B* 永真故 A* = B*對偶式相關(guān)定理 定理2.5.5 若AB永真, 必有B*A*永真或者，AB和B*A*同永真證明:(1) 如果AB永真，則BA永真(逆否命題)根據(jù)定理2.

24、5.3，A= A*-, B= B*-所以B*-A*-永真，則(B*-A*-)-永真(代入規(guī)則)，即B*A*永真(2) 如果B*A*永真，根據(jù)(1)有: (A*)*(B*)*永真根據(jù)定理2.5.2，A=(A*)*, B=(B*)*所以AB永真 對偶式相關(guān)定理 作業(yè)(2)(P37) 3，4(2)2.6 范式n 個(gè)命題變項(xiàng)所能組成的具有不同真值的命題公式僅有22n個(gè), 然而與任何一個(gè)命題公式等值而形式不同的命題公式可以有無窮多個(gè)等值的公式，能否都可以化為某一個(gè)統(tǒng)一的標(biāo)準(zhǔn)形式？希望這種標(biāo)準(zhǔn)形能為我們的討論帶來些方便，如借助于標(biāo)準(zhǔn)形對任意兩個(gè)形式上不同的公式，可判斷它們的是否等值借助于標(biāo)準(zhǔn)形容易判斷任一

25、公式是否為重言式或矛盾式2.6.1 范式若干術(shù)語簡單命題P及其否定式P統(tǒng)稱為文字一些文字的合取稱為合取式一些文字的析取稱為析取式(也稱子句)P與P稱為互補(bǔ)對析取范式，形如：A1A2 An其中Ai(i=1, , n)為合取式合取范式，形如： A1A2 An其中Ai(i=1, , n)為析取式67范式舉例p, qp1p2 , q1q2范式定理范式定理：任一命題公式都存在與之等值的析取范式、合取范式求范式三步曲：1) 消去和2) 否定深入到命題變項(xiàng)3) 使用分配律的等值變換舉例求(PQ)(PQ)的析取范式(PQ)(PQ)=(PQ)(PQ)(PQ)(PQ)=(PQPQ)(PQ)(PQ)=(PQPQ)(

26、PP)(PQ)(QP)(QQ) (析取范式)= (PQ)(QP) (析取范式，簡化)注：范式的不唯一性舉例求(PQ)(PQ)的合取范式(PQ)(PQ)=(PQ)(QP) (析取范式，簡化)=(PQ)(PP)(QQ)(QP)(合取范式)=(PQ)(QP) (合取范式，簡化)注：已知一種范式，可以使用分配律求另一種范式 判斷重言式合取范式中所有析取式都有互補(bǔ)對 判斷矛盾式析取范式中所有合取式都有互補(bǔ)對 判斷兩公式是否等值范式不唯一，引入唯一的主范式，便于判別公式相等范式功能2.6.2 主范式主析取范式極小項(xiàng)定義與編碼Q1Qn是由n個(gè)命題變項(xiàng)P1, , Pn組成的公式, 其中Qi=Pi或者Pi, 我

27、們稱其為極小項(xiàng), 一般用mj表示例：P1, P2的極小項(xiàng)有四個(gè)P1 P2 (m0), P1 P2 (m1), P1 P2 (m2), P1P2 (m3)主析取范式定義 僅由極小項(xiàng)構(gòu)成的析取范式主析取范式唯一性定理任一含有n個(gè)命題變項(xiàng)的公式，都有唯一一個(gè)與之等值的恰僅含這n個(gè)命題變項(xiàng)的主析取范式極小項(xiàng)必須含有Q1, , Qn全部n個(gè)文字由真值表寫主析取范式：從T寫P Q=(PQ)(PQ)=m0m3= 0,3由析取范式寫主析取范式：填滿命題變項(xiàng)法, 永真式P = P(QQ) = (PQ)(PQ) Q = Q(PP) = (QP)(QP)PQ = PQ = (PQ)(PQ) (QP)(QP) = (

28、PQ)(PQ)(PQ) = m0m1m3 = 0,1,3主析取范式PQPQ m0FFT m1FTFm2TFFm3TTT所有可能極小項(xiàng)的個(gè)數(shù)：2n每個(gè)極小項(xiàng)只在一個(gè)解釋下為真對于每個(gè)解釋只有一個(gè)極小項(xiàng)為真 極小項(xiàng)互不相等，且mi mj=F (i j)任一含有n個(gè)變項(xiàng)的公式，都可由k個(gè)(k2n)極小項(xiàng)的析取來表示；或者說所有的極小項(xiàng)可建立一個(gè)“坐標(biāo)系”恰由2n個(gè)極小項(xiàng)的析取構(gòu)成的公式，必為重言式 A與A的主析取范式關(guān)系A(chǔ)由k個(gè)極小項(xiàng)的析取組成，那么其余的2n-k個(gè)極小項(xiàng)的析取必是A例如P1, P2, P3構(gòu)成的A= 0,2,4, A= 1,3,5,6,7極小項(xiàng)性質(zhì)主合取范式極大項(xiàng)定義與編碼Q1 Q

29、n是由n個(gè)命題變項(xiàng)P1, , Pn組成的公式, 其中Qi=Pi或者Pi(i = 1, , n), 我們稱其為極大項(xiàng), 一般用Mj表示(0j2n-1)例：P1, P2的極大項(xiàng)有四個(gè)P1P2 (M0), P1P2 (M1), P1P2 (M2), P1P2 (M3)主合取范式定義僅由極大項(xiàng)構(gòu)成的合取范式主合取范式唯一性定理任一含有n個(gè)命題變項(xiàng)的公式，都有唯一一個(gè)與之等值的恰僅含這n個(gè)命題變項(xiàng)的主合取范式由真值表寫主合取范式(從F寫)由合取范式寫主合取范式(填滿命題變項(xiàng)法, 矛盾式)極大項(xiàng)必須含有Q1, , Qn全部n個(gè)文字極大項(xiàng)性質(zhì)所有可能極大項(xiàng)的個(gè)數(shù)：2n每個(gè)極大項(xiàng)只在一個(gè)解釋下為假對于每個(gè)解釋

30、只有一個(gè)極大項(xiàng)為假 極大項(xiàng)互不相等，且Mi Mj=T (i j)任一含有n個(gè)變項(xiàng)的公式，都可由k個(gè)(k2n)極大項(xiàng)的合取來表示；或者說所有的極大項(xiàng)可建立一個(gè)“坐標(biāo)系”恰由2n個(gè)極大項(xiàng)的合取構(gòu)成的公式，必為矛盾式A與A的主合取范式關(guān)系A(chǔ)由k個(gè)極大項(xiàng)的合取組成，那么其余的2n-k個(gè)極大項(xiàng)的合取必是A例如P1, P2, P3構(gòu)成的A= 0,2,5, A= 1,3,4,6,7主析取范式與主合取范式的轉(zhuǎn)換設(shè)A是由命題變項(xiàng)P1, P2, P3構(gòu)成的公式已知主析取范式A = 0,1,4,5,7 = (0,1,7-0,1,4,5,7)補(bǔ) = 2,3,6補(bǔ) = 5,4,1已知主合取范式A = 1,4,5 = (

31、0,1,7-1,4,5補(bǔ)) = (0,1,7-6,3,2) = 0,1,4,5,7極小項(xiàng)編碼P1P2P3A極大項(xiàng)編碼m0FFFTMm1FFTTMm2FTFFMm3FTTFMm4TFFTMm5TFTTMm6TTFFMm7TTTTM主析取范式與主合取范式的轉(zhuǎn)換注意從真值表列寫公式的主析取范式和主合取范式時(shí)，除了分別從T和F列寫外，在填寫合取式和析取式時(shí)是取變項(xiàng)還是其否定是有區(qū)別的，這就是主合取范式、主析取范式轉(zhuǎn)換過程要求補(bǔ)的原因數(shù)字補(bǔ)不同于補(bǔ)集。這里的數(shù)字求補(bǔ)是對2n-1=23-1=7而言的，如2的補(bǔ)是5，因?yàn)?+5=7主范式的用途與真值表相同 (1) 求公式的成真賦值和成假賦值例如：(PQ)R

32、m1m3m5 m6m7，其成真指派為001, 011, 101, 110, 111，其余的指派 000, 010, 100為成假指派. 類似地，由主合取范式也可立即求出成假指派和成真指派 主范式的用途(續(xù))(2) 判斷公式的類型 設(shè)A含n個(gè)命題變項(xiàng)，則 A為重言式A的主析取范式含2n個(gè)極小項(xiàng) A的主合取范式為TA為矛盾式 A的主析取范式為F A的主合取范式含2n個(gè)極大項(xiàng)A為非重言式的可滿足式A的主析取范式中至少含一個(gè)且不含全部極小項(xiàng)A的主合取范式中至少含一個(gè)且不含全部極大項(xiàng) 主范式的用途(續(xù))判斷兩個(gè)公式是否等值例 用主析取范式判斷下述兩個(gè)公式是否等值： P(QR) 與 (PQ)R P(QR)

33、 與 (PQ)R解 P(QR) = m0m1m2m3m4m5m7 (PQ)R = m0m1m2m3m4m5m7 (PQ)R = m1m3 m4m5 m7顯見，中的兩公式等值，而的不等值.作業(yè)(3)(P37) 5(1，5，8)2.7 推理形式自然語言推理前提1：如果我今天病了，那么我沒來上課前提2：今天我病了結(jié)論：所以今天我沒來上課推理形式引入符號, 形式化并用條件式表示出來例：(PQ)P)Q正確的推理形式前提真，結(jié)論必真的推理形式(PQ)Q)P 正確的推理形式(PQ)P)Q 不正確的推理形式PQPQ重言蘊(yùn)涵重言蘊(yùn)涵對于公式A, B, 如果當(dāng)A取值為真時(shí)，B必取值為真，則稱A重言(永真)蘊(yùn)涵B，

34、或稱B是A的邏輯推論。記為： A B(是真值關(guān)系，并非邏輯聯(lián)結(jié)詞)重言蘊(yùn)涵與正確推理形式如果A B，則AB是正確的推理形式如果AB是正確的推理形式，可以用A B來表示用真值表法判斷A B查看真值表，如果所有使A為真的解釋，亦能使B為真，則A B 如果A B, A為重言式, 則B也是重言式 如果A B, B A同時(shí)成立, 必有A = B如果A = B, 必有A B和B A 如果A B, B C, 則A C 如果A B, A C, 則A BC 如果A C, B C, 則AB C重言蘊(yùn)涵的結(jié)果2.8 基本的推理公式1. (PQ) P化簡律2. (PQ) P 3. (PQ) Q4. P (PQ)附加律

35、 5. P PQ6. Q PQ7. (PQ)P Q 析取三段論8. (PQ)P Q 假言推理、分離規(guī)則9. (PQ)Q P 拒取式10. (PQ)(QR) (PR) 假言三段論、三段論11. (PQ)(QR) (PR)等價(jià)三段論12. (PR)(QR)(PQ) R 構(gòu)造性二難(特殊形式)13. (PQ)(RS)(PR) (QS)構(gòu)造性二難14. (PQ)(RS)(Q S) (PR) 破壞性二難15. (QR) (PQ)(PR)16. (QR) (PQ)(PR)注：真值表證明，或者語義上直接說明基本的推理公式2.8.2 證明推理公式的方法(五種)A B成立的充分必要條件是AB(或AB) 為重言式

36、證明：如果A B, 那么在任一解釋下, A真B必真, 而不會出現(xiàn)A真B假的情況, 于是AB為重言式。如果AB為重言式, 則在任一解釋下, 若A為真, B只能為真不可能為假, 從而有A B證明AB為重言式的方法真值表、等值演算、范式例1 用等值演算法證明(PQ)PQ為重言式 (PQ)PQ (PQ)P)Q(PQ)P)Q QPQ T 舉例例2 用主析取范式法證明(PQ)QP不是重言式 (PQ)QP (PQ)Q)P(PQ)Q)P (吸收律)QP(QP)(QP)(PQ)(PQ) (PQ)(PQ)(PQ) m0m2m3缺少m1即(PQ), 所以(PQ)QP不是重言式，或者說推理形式(PQ)QP不正確舉例2. AB成立的充分必要條件是AB為重言式, 即AB是矛盾式3. (逆否定理) AB成立的充分必要條件B A4. 解釋法例: (PQ)(QR) (PR)若(PQ)(QR)T, 則同時(shí)有PQT, QR=T若P=T, 則Q=T, 進(jìn)而R=T. 故PRT若P=F, 則Q可取任意值: (1) Q=T, 則R=T; (2) Q=F, 則R取何值無論如何, PR=T5. 真