離散數(shù)學(xué)chapter02

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

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

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

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

5、。注：根據(jù)該等值定理，證明兩個公式等值，只要證明由這兩個公式構(gòu)成的雙條件式是重言式即可“”作為邏輯關(guān)系符是一種等價關(guān)系n不要將“”視作聯(lián)結(jié)詞，在合式公式定義里沒有“”出現(xiàn)nA = B是表示公式A與B的一種關(guān)系。這種關(guān)系具有三個性質(zhì): 1. 自反性 A = A2. 對稱性 若A = B, 則B = A3. 傳遞性 若A = B, B = C, 則A = C 這三條性質(zhì)體現(xiàn)了“”的實質(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)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對蘊涵詞、雙條件詞作否定有(PQ) = PQ(PQ) = PQ = PQ= (PQ)(PQ)8. 同一律PF = PPT = PTP = PTP = P還有PF = PFP = P 9. 零律PT = TPF = F還有PT = TFP = T10. 補余律PP = TP

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

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

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

10、可解釋為PQ為假, 有兩種可能的情形, 即(PQ)為假或(PQ)為假, 而PQ為假, 必是在P = F, Q = T的情況下出現(xiàn); PQ為假, 必是在P = T, Q = F的情況下出現(xiàn)。從而可說PQ為假, 是在P真Q假或P假Q(mào)真時成立。這就是從取假來描述這等式 16. PQ = (PQ)(QP)n從蘊含詞來描述雙條件n這表明PQ成立, 等價于正定理PQ和逆定理QP都成立 17. P(QR) = Q(PR)n前提交換n前提條件P、Q可交換次序 18. (PR)(QR)=(PQ)Rn左端說明的是由P而且由Q都有R成立。從而可以說由P或Q就有R成立, 這就是等式右端補充n等價否定等值式PQ = P

11、Qn歸謬論(PQ)(PQ) = P小節(jié)一下常用的等值式n1. ， 的結(jié)合律，交換律，分配律，吸收律n2. De Morgan定理和廣義 De Morgan定理n3. P Q 等值 P Q (E16) n4. P Q = (P Q ) (Q P ) 2.2.3 置換規(guī)則 n置換定義對公式A的子公式, 用與之等值的公式來代換便稱置換n置換規(guī)則q公式A的子公式置換后A化為公式B, 必有A = Bq當A是重言式時, 置換后的公式B必也是重言式n置換與代入是有區(qū)別的。置換只要求A的某一子公式作代換, 不必對所有同一的子公式都作代換代入規(guī)則回顧 nA是一個公式，對A使用代入規(guī)則得公式B，若A是重言式，則B

12、也是重言式n為保證重言式經(jīng)代入規(guī)則仍得到保持，要求q公式中被代換的只能是命題變元(原子命題), 而不能是復(fù)合命題q對公式中某命題變元施以代入，必須對該公式中出現(xiàn)的所有同一命題變元代換以同一公式2.2.4 等值演算舉例 例1: 證明(P(QR)(QR)(PR) = R證明: 左端= (P(QR) (QP)R)(分配律)= (PQ)R)(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)(P

13、R)(摩根律)=(PQ)(PQ)(PR)(PQ)(PR)(分配律)=(PQ)(PR)(PQ)(PR)(等冪律)=T舉例 問題提出：問題提出：由命題公式寫真值表是容易的，那么如由命題公式寫真值表是容易的，那么如何由真值表寫命題公式呢？何由真值表寫命題公式呢？2.3 命題公式與真值表關(guān)系2.3.1 從從T來列寫來列寫o 記憶方法：各項間用記憶方法：各項間用，每項內(nèi)用每項內(nèi)用o 每項內(nèi)書寫方法：例每項內(nèi)書寫方法：例真值表中真值表中P=T且且Q=F等價于等價于P Q=To 簡化方法：有時簡化方法：有時A的表達通過的表達通過 A來描述來描述2.3.2 從從F來列寫來列寫o 記憶方法：各項間用記憶方法：各

14、項間用 ，每項內(nèi)用每項內(nèi)用o 每項內(nèi)書寫方法：例每項內(nèi)書寫方法：例真值表中真值表中P=T且且Q=F等價于等價于 PQ=Fo 簡化方法：有時簡化方法：有時A的表達通過的表達通過 A來描述來描述舉例n從A的真值Tq直接: A = (P Q) (P Q) (P Q)q間接: A = A = (P Q) = P Qn從B的真值FB = (P Q) (P Q)n當C可取任意值C與P, Q = T, T無關(guān), 可適當選取C的真值, 使其表達式簡單PQAABCFFTFTTFTTFTFTFFTFTTTTFFX應(yīng)用n在電路設(shè)計的時候簡化邏輯設(shè)計，節(jié)省邏輯單元 。 計算機 or 單片機 or 邏輯電路?nCPU的

15、核心單元ALU （ Arithmetic-Logic Unit ），主要負責(zé)整數(shù)運算。應(yīng)用n【生活中的例子例子】 雙控照明開關(guān)。 K1 K2 燈光 0 0 0 1 0 1 0 1 1 1 1 0 主范式 的應(yīng)用n【生活中的例子例子】 雙控照明開關(guān)。作業(yè)(1)(P37) 1(1, 3), 22.4 聯(lián)結(jié)詞的完備集 o問題的提出問題的提出對對n 個命題變項個命題變項P1Pn來說來說, 共可定義出多少個共可定義出多少個聯(lián)結(jié)詞聯(lián)結(jié)詞? 在那么多聯(lián)結(jié)詞中有多少是相互獨立的在那么多聯(lián)結(jié)詞中有多少是相互獨立的?o3個新聯(lián)結(jié)詞：個新聯(lián)結(jié)詞： P QP QPQP Q(P Q)P Q(P Q) ：= =( ()

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

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

18、F(永假式)g1(P,Q) = PQ (合取式)g2(P,Q) = PQ g3(P,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(蘊涵式)g12(P,Q) = (P Q)(PQ) = P(QQ) = Pg13(P,Q) = PQ = PQ(蘊涵式)

19、g14(P,Q) = PQ = P Q (與非式)g15(P,Q) = T (永真式)nn元聯(lián)結(jié)詞對n個命題變元P1 , , Pn , 每個Pi有兩種取值, 從而對P1Pn來說共有2n種取值情形于是相應(yīng)的真值函項就有22n個, 或說可定義22n個n元聯(lián)結(jié)詞n元聯(lián)結(jié)詞的個數(shù)2.4.2 聯(lián)結(jié)詞的完備集 n第二個問題。聯(lián)結(jié)詞是否都是獨立的，或者說能否相互表示?n聯(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. , ,

20、是完備的聯(lián)結(jié)詞集合 證明：從2.3節(jié)介紹的由真值表列寫邏輯公式的過程可知, 任一公式都可由, , 表示出來, 從而, , 是完備的3. 是聯(lián)結(jié)詞的完備集(獨立的完備集)證明：PQ = (PQ)，因此可由, 表示4. , 是聯(lián)結(jié)詞的完備集(獨立的完備集)證明：PQ = (PQ)，因此可由, 表示完備集 5. , 是完備集(獨立的完備集)因為：PQ = PQ6. 是完備集(獨立的完備集)7. 是完備集(獨立的完備集)8. , , , , 是完備的 因為它包含了2中的集合完備集 o , 不是完備的不是完備的因為因為 不能僅由該集合的聯(lián)結(jié)詞表達出不能僅由該集合的聯(lián)結(jié)詞表達出o , 不是完備的不是完備的

21、o , 的任何子集都是不完備的的任何子集都是不完備的 , 的任何子集也是不完備的的任何子集也是不完備的(如果一個聯(lián)結(jié)詞的集合是不完備的，那如果一個聯(lián)結(jié)詞的集合是不完備的，那么它的任何子集都是不完備的么它的任何子集都是不完備的)o ,不是完備的不是完備的不完備集不完備集 最小的聯(lián)結(jié)詞的完備集基底 n基底：完備的聯(lián)結(jié)詞集合的聯(lián)結(jié)詞是獨立的，也就是說這些聯(lián)結(jié)詞不能相互表示n任取四個一元或二元聯(lián)結(jié)詞，它們必組不成基底基底 n只含一個聯(lián)結(jié)詞的: NK;NAn含兩個聯(lián)結(jié)詞的:N,C; N,K; N,A; N,NC; F,C; T,NC; C,NE; E,NC; C,NCn含三個聯(lián)結(jié)詞的:F,K,E; F,

22、A,E; T,K,NE; T,A,NE; K,E,NE; A,E,NE其中：A- K- E- C- N- 聯(lián)結(jié)詞的功能完全集n 和 都是聯(lián)結(jié)詞的最小功能完全集。 證明基本思路： 可以表示其他功能完全集。如： x & y = (x y) (x y)能不能在生活中找到和 相似的運算？1.5.2 聯(lián)結(jié)詞的功能完全集與非門電路能不能在生活中找到與非相似的運算？ FPGA2.5 對偶式 n研究目的q簡化等值公式的討論希望一個公式成立，能夠?qū)С雠c其“相像”的公式成立q邏輯關(guān)系上看，是一種邏輯規(guī)律n對偶式定義：將A中出現(xiàn)的、T、F分別以、F、T代換, 得到公式A*, 則稱A*是A的對偶式, 或說A和

23、A*互為對偶式注：這里假定A中僅出現(xiàn) 、三個聯(lián)結(jié)詞n若A = B，必有A*=B*?p新符號“-”: (代入規(guī)則、內(nèi)否式)若A=A(P1, , Pn)，令A(yù)= A(P1, , Pn)p關(guān)于等值的三個定理定理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)定理 62性質(zhì)舉例A= (P (Q R) TA*= (P (Q R) FA-= (P) (Q R) TA

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

25、= (A1*)歸納法假設(shè) = (A1)*定理2.5.1, 2.5.2 = A* A = A1定理2.5.3 A = A*當A = A1A2時， 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永真當且僅當B永真證明：設(shè)A是由命題變項P1,Pn構(gòu)成的命題公式。(1) 如果A永真，根據(jù)代入規(guī)則，則A-永真。 如果A-永真，則(A-

26、)-永真，又根據(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*證明: 因為A = B 等價于AB 永真 等價于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.5.3，A= A*-, B=

27、 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)定理 2.6 范式nn 個命題變項所能組成的具有不同真值的命題公式僅有22n個, 然而與任何一個命題公式等值而形式不同的命題公式可以有無窮多個n等值的公式，能否都可以化為某一個統(tǒng)一的標準形式？q希望這種標準形能為我們的討論帶來些方便，如借助于標準形對任意兩個形式上不同的公式，可判斷它們的是否等值q借助于標準形容易判斷任一公式是否為重言式或矛盾式2.6.1 范式n若干術(shù)語q簡

28、單命題P及其否定式P統(tǒng)稱為文字q一些文字的合取稱為(簡單)合取式q一些文字的析取稱為(簡單)析取式(也稱子句)qP與P稱為互補對q析取范式，形如：A1A2 An其中Ai(i=1, , n)為合取式q合取范式，形如： A1A2 An其中Ai(i=1, , n)為析取式72范式舉例np, q (既是簡單合取式，又是簡單析取式)np1p2 , q1q2范式定理n范式定理：任一命題公式都存在與之等值的析取范式、合取范式n求范式三步曲：1) 消去和2) 否定深入到命題變項3) 使用分配律的等值變換舉例n求(PQ)(PQ)的析取范式(PQ)(PQ)=(PQ)(PQ)(PQ)(PQ)=(PQPQ)(PQ)(

29、PQ)=(PQPQ)(PP)(PQ)(QP)(QQ) (析取范式)= (PQ)(QP) (析取范式，簡化)注：范式的不唯一性舉例n求(PQ)(PQ)的合取范式(PQ)(PQ)=(PQ)(QP) (析取范式，簡化)=(PQ)(PP)(QQ)(QP)(合取范式)=(PQ)(QP) (合取范式，簡化)注：已知一種范式，可以使用分配律求另一種范式p 判斷重言式判斷重言式合取范式中所有析取式都有互補對合取范式中所有析取式都有互補對p 判斷矛盾式判斷矛盾式析取范式中所有合取式都有互補對析取范式中所有合取式都有互補對p 判斷兩公式是否等值判斷兩公式是否等值范式不唯一，引入唯一的主范式，范式不唯一，引入唯一的

30、主范式，便于判別公式相等便于判別公式相等范式功能范式功能2.6.2 主范式n主析取范式q極小項定義與編碼Q1Qn是由n個命題變項P1, , Pn組成的公式, 其中Qi=Pi或者Pi, 我們稱其為極小項, 一般用mj表示例：P1, P2的極小項有四個P1 P2 (m0), P1 P2 (m1), P1 P2 (m2), P1P2 (m3)q主析取范式定義 僅由極小項構(gòu)成的析取式q主析取范式唯一性定理任一含有n個命題變項的公式，都有唯一一個與之等值的恰僅含這n個命題變項的主析取范式極小項必須含有極小項必須含有Q1, , Qn全部全部n個文字個文字n由真值表寫主析取范式：從T寫P Q=(PQ)(PQ

31、)=m0m3= 0,3n由析取范式寫主析取范式：填滿命題變項法, 永真式P = P(QQ) = (PQ)(PQ) Q = Q(PP) = (QP)(QP)PQ = PQ = (PQ)(PQ) (QP)(QP) = (PQ)(PQ)(PQ) = m0m1m3 = 0,1,3主析取范式PQPQ m0FFT m1FTFm2TFFm3TTTp所有可能極小項的個數(shù)：所有可能極小項的個數(shù)：2np每個極小項只在一個解釋下為真每個極小項只在一個解釋下為真p對于每個解釋只有一個極小項為真對于每個解釋只有一個極小項為真 p極小項互不相等，且極小項互不相等，且mi mj=F (i j)p任一含有任一含有n個變項的公

32、式，都可由個變項的公式，都可由k個個(k2n)極小項的析取來極小項的析取來表示；或者說所有的極小項可建立一個表示；或者說所有的極小項可建立一個“坐標系坐標系”p恰由恰由2n個極小項的析取構(gòu)成的公式，必為重言式個極小項的析取構(gòu)成的公式，必為重言式 pA與與 A的主析取范式關(guān)系的主析取范式關(guān)系A(chǔ)由由k個極小項的析取組成，那么其余的個極小項的析取組成，那么其余的2n-k個極小項的析取必個極小項的析取必是是 A例如例如P1, P2, P3構(gòu)成的構(gòu)成的A= 0,2,4, A= 1,3,5,6,7極小項性質(zhì)極小項性質(zhì)n21ii1mT主合取范式主合取范式o極大項定義與編碼極大項定義與編碼Q1 Qn是由是由n

33、個命題變項個命題變項P1, , Pn組成的公式組成的公式, 其中其中Qi=Pi或或者者Pi(i = 1, , n), 我們稱其為極大項我們稱其為極大項, 一般用一般用Mj表示表示(0j2n-1)例：例：P1, P2的極大項有四個的極大項有四個P1P2 (M0), P1P2 (M1), P1P2 (M2), P1P2 (M3)o主合取范式定義主合取范式定義僅由極大項構(gòu)成的合取式僅由極大項構(gòu)成的合取式o主合取范式唯一性定理主合取范式唯一性定理任一含有任一含有n個命題變項的公式，都有唯一一個與之等值的恰僅含個命題變項的公式，都有唯一一個與之等值的恰僅含這這n個命題變項的主合取范式個命題變項的主合取范

34、式o由真值表寫主合取范式由真值表寫主合取范式(從從F寫寫)o由合取范式寫主合取范式由合取范式寫主合取范式(填滿命題變項法填滿命題變項法, 矛盾式矛盾式)極大項必須含有極大項必須含有Q1, , Qn全部全部n個文字個文字極大項性質(zhì)極大項性質(zhì)p所有可能極大項的個數(shù)：所有可能極大項的個數(shù)：2np每個極大項只在一個解釋下為假每個極大項只在一個解釋下為假p對于每個解釋只有一個極大項為假對于每個解釋只有一個極大項為假 p極大項互不相等，且極大項互不相等，且Mi Mj=T (i j)p任一含有任一含有n個變項的公式，都可由個變項的公式，都可由k個個(k2n)極大項的合取來極大項的合取來表示；或者說所有的極大

35、項可建立一個表示；或者說所有的極大項可建立一個“坐標系坐標系”p恰由恰由2n個極大項的合取構(gòu)成的公式，必為矛盾式個極大項的合取構(gòu)成的公式，必為矛盾式pA與與 A的主合取范式關(guān)系的主合取范式關(guān)系A(chǔ)由由k個極大項的合取組成，那么其余的個極大項的合取組成，那么其余的2n-k個極大項的合取必個極大項的合取必是是 A例如例如P1, P2, P3構(gòu)成的構(gòu)成的A= 0,2,5, A= 1,3,4,6,7n21ii1mF主析取范式與主合取范式的轉(zhuǎn)換設(shè)A是由命題變項P1, P2, P3構(gòu)成的公式n已知主析取范式A = 0,1,4,5,7 = (0,1,7-0,1,4,5,7)補 = 2,3,6補 = 5,4,1

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

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

38、析取范式判斷下述兩個公式是否等值：用主析取范式判斷下述兩個公式是否等值： P(QR) 與與 (P Q)R P(QR) 與與 (PQ)R解解 P(QR) = m0 m1 m2 m3 m4 m5 m7 (P Q)R = m0 m1 m2 m3 m4 m5 m7 (PQ)R = m1 m3 m4 m5 m7顯見，中的兩公式等值，而的不等值顯見，中的兩公式等值，而的不等值.作業(yè)(2)(P37) 3, 4(2), 5(8)董老師書： (P24) 2 (2,3), 4(4) ,52.7 推理形式o 自然語言推理自然語言推理n前提前提1：如果我今天病了，那么我沒來上課：如果我今天病了，那么我沒來上課n前提前

39、提2：今天我病了：今天我病了n結(jié)論：所以今天我沒來上課結(jié)論：所以今天我沒來上課o 推理形式推理形式n引入符號引入符號, 形式化并用形式化并用條件式條件式表示出來表示出來例：例：(PQ)P)Qn正確的推理形式正確的推理形式o 前提真，結(jié)論必真的推理形式前提真，結(jié)論必真的推理形式o(PQ) Q) P 正確的推理形式正確的推理形式(PQ) P) Q 不正確的推理形式不正確的推理形式PQPQ重言蘊涵重言蘊涵o 重言蘊涵重言蘊涵n對于公式對于公式A, B, 如果當如果當A取值為真時，取值為真時，B必取值為真，則必取值為真，則稱稱A永真永真蘊涵蘊涵B，或稱，或稱B是是A的邏輯推論。記為：的邏輯推論。記為：

40、 A B(是真值關(guān)系，并非邏輯聯(lián)結(jié)詞是真值關(guān)系，并非邏輯聯(lián)結(jié)詞)o 重言蘊涵與正確推理形式重言蘊涵與正確推理形式n如果如果A B，則，則AB是正確的推理形式是正確的推理形式n如果如果AB是正確的推理形式，可以用是正確的推理形式，可以用A B來表示來表示o 用真值表法判斷用真值表法判斷A Bn查看真值表，如果所有使查看真值表，如果所有使A為真的解釋，亦能使為真的解釋，亦能使B為真，為真，則則A B 如果如果A B, A為重言式為重言式, 則則B也是重言式也是重言式 如果如果A B, B A同時成立同時成立, 必有必有A = B如果如果A = B, 必有必有A B和和B A 如果如果A B, B

41、C, 則則A C 如果如果A B, A C, 則則A BC 如果如果A C, B C, 則則AB C重言蘊涵的結(jié)果重言蘊涵的結(jié)果2.8 基本的推理公式1. (PQ) P化簡律化簡律2. (PQ) P 3. (PQ) Q4. P (PQ)附加律附加律 5. P PQ6. Q PQ7. (PQ) P Q 析取三段論析取三段論8. (PQ)P Q 9. (PQ) Q P 拒取式拒取式10. (PQ)(QR) (PR) 假言三段論、假言三段論、11. (PQ)(QR) (PR)等價三段論等價三段論12. (PR)(QR)(PQ) R 構(gòu)造性二難構(gòu)造性二難(特殊形式特殊形式)13. (PQ)(RS)(P

42、R) (QS)構(gòu)造性二難構(gòu)造性二難14. (PQ)(RS)( Q S) ( P R) 破破壞性二難壞性二難15. (QR) (PQ)(PR)16. (QR) (PQ)(PR)注：真值表證明，或者語義上直接說明注：真值表證明，或者語義上直接說明基本的推理公式基本的推理公式2.8.2 證明推理公式的方法(五種)1. A B成立的充分必要條件是成立的充分必要條件是AB(或或AB) 為重言式為重言式證明：如果證明：如果A B, 那么在任一解釋下那么在任一解釋下, A真真B必真必真, 而而不會出現(xiàn)不會出現(xiàn)A真真B假的情況假的情況, 于是于是AB為重言式。為重言式。如果如果AB為重言式為重言式, 則則在任

43、一解釋下在任一解釋下, 若若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不是重言式，不是重

44、言式，或者說推理形式或者說推理形式(PQ)QP不正確不正確舉例舉例2. AB成立的充分必要條件是成立的充分必要條件是AB為重言式為重言式, 即即 AB是是矛盾式矛盾式3. (逆否定理逆否定理) AB成立的充分必要條件成立的充分必要條件B A4. 解釋法解釋法例例: (PQ)(QR) (PR)若若(PQ)(QR)T, 則同時有則同時有PQT, QR=T若若P=T, 則則Q=T, 進而進而R=T. 故故PRT若若P=F, 則則Q可取任意值可取任意值: (1) Q=T, 則則R=T; (2) Q=F, 則則R取何值取何值無論如何無論如何, PR=T5. 真值表法真值表法, 即通過真值表檢驗即通過真值

45、表檢驗A為真時為真時B一定為真一定為真注：注： 證明證明AB時不考慮時不考慮A為假的情況為假的情況證明推理公式的方法證明推理公式的方法上述方法的特點上述方法的特點o 都是從真值的角度進行論證和解釋都是從真值的角度進行論證和解釋o 看不出由前提看不出由前提A到結(jié)論到結(jié)論B的推演過程的推演過程o 難于擴展到謂詞邏輯的推演過程難于擴展到謂詞邏輯的推演過程2.9 推理演算(證明推理公式證明推理公式AB的新方的新方法法)o基本思想：從前提基本思想：從前提A1, , An出發(fā)出發(fā)(即即A= A1 A2 An)運用推理規(guī)則和基本推理公式，運用推理規(guī)則和基本推理公式，逐步推演出結(jié)論逐步推演出結(jié)論B，即證明即證

46、明ABo推理規(guī)則推理規(guī)則1. 前提引入規(guī)則（前提引入規(guī)則（P規(guī)則規(guī)則）推理過程中可以隨時引入前提推理過程中可以隨時引入前提A1, , An2. 結(jié)論引用規(guī)則（結(jié)論引用規(guī)則（T規(guī)則規(guī)則）推理過程中得到的中間結(jié)論可作為后續(xù)推理的前提推理過程中得到的中間結(jié)論可作為后續(xù)推理的前提3. 代入規(guī)則代入規(guī)則(參考參考P8)推理過程中對推理過程中對重言式重言式的命題變項可使用該規(guī)則的命題變項可使用該規(guī)則推理規(guī)則推理規(guī)則4.置換規(guī)則置換規(guī)則(參考參考P18)推理過程中命題公式中任何部分公式都可由與之推理過程中命題公式中任何部分公式都可由與之等值等值的的公式公式置換置換5.分離規(guī)則分離規(guī)則(假言推理假言推理)已知命題公式已知命題公式AB和和A, 則