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

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

2、=)),等值定理、公式聯(lián)結(jié)詞的完備集(由個(gè)別聯(lián)結(jié)詞表示所有聯(lián)結(jié)詞的問題)對(duì)偶式(命題公式的對(duì)偶性)范式(命題公式的統(tǒng)一標(biāo)準(zhǔn)) 由真值表寫命題公式(由T寫、由F寫),推理演算(考察邏輯關(guān)系符?),推理形式(正確推理形式的表示)基本推理公式(各種三段論及五種證明方法)推理演算(證明推理公式的第六種方法，使用推理規(guī)則)歸結(jié)推理法(證明推理公式的第七種方法，常用反證法),2.1 等值定理,若把初等數(shù)學(xué)里的＋、－、×

3、、÷等運(yùn)算符看作是數(shù)與數(shù)之間的聯(lián)結(jié)詞，那么由這些聯(lián)結(jié)詞所表達(dá)的代數(shù)式之間，可建立許多等值式如下：x2－y2 = (x＋y)(x－y)(x＋y)2 = x2＋2xy＋y2 sin2x＋cos2x = 1……在命題邏輯里也同樣可建立一些重要的等值式,2.1.1 等值的定義,給定兩個(gè)命題公式A和B, 而P1…Pn是出現(xiàn)于A和B中的所有命題變項(xiàng), 那么公式A和B共有2n個(gè)解釋, 若對(duì)其中的任一解釋

4、, 公式A和B的真值都相等, 就稱A和B是等值的(或等價(jià)的)。記作A = B或A?B顯然，可以根據(jù)真值表來判明任何兩個(gè)公式是否是等值的,例1: 證明(P∧?P)∨Q = Q,證明: 畫出(P∧?P)∨Q與Q的真值表可看出等式是成立的。,例2: 證明P∨?P = Q∨?Q,證明: 畫出P∨?P, Q∨?Q的真值表, 可看出它們是等值的, 而且它們都是重言式。,從例1、2還可說明, 兩個(gè)公式等值并不一定要求它們一定含有相同的命題變項(xiàng)若僅

5、在等式一端的公式里有變項(xiàng)P出現(xiàn), 那么等式兩端的公式其真值均與P無關(guān)。例1中公式(P∧?P)∨Q與Q的真值都同P無關(guān)例2中P∨?P, Q∨?Q都是重言式, 它們的真值也都與P、Q無關(guān)。,說明,2.1.2 等值定理,定理 對(duì)公式A和B, A=B的充分必要條件是A?B是重言式。A、B不一定都是簡單命題, 可能是由簡單命題P1, …, Pn構(gòu)成的. 對(duì)A, B的一個(gè)解釋, 指的是對(duì)P1, …, Pn的一組具體的真值設(shè)定.若A?B為

6、重言式, 則在任一解釋下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è)

7、公式等值，只要證明由這兩個(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. 對(duì)稱性 若A = B, 則B = A3. 傳遞性 若A = B, B = C, 則A = C 這三條性質(zhì)體現(xiàn)了“＝”的實(shí)質(zhì)含義。,2.2 等值公式,2.2.1 基本

8、的等值公式(命題定律, P和Q是任意的命題公式)1. 雙重否定律??P = P2. 結(jié)合律(P∨Q)∨R = P∨(Q∨R)(P∧Q)∧R = P∧(Q∧R)(P ? Q) ? R = P ? (Q ? R),3. 交換律P∨Q = Q∨PP∧Q = Q∧PP ? Q = Q ? P4. 分配律P∨(Q∧R) = (P∨Q)∧(P∨R)P∧(Q∨R) = (P∧Q)∨(P∧

9、R)P?(Q?R) = (P?Q)?(P?R)5. 等冪律(恒等律)P∨P = PP∧P = PP?P = TP?P = T,,,6. 吸收律P∨(P∧Q) = PP∧(P∨Q) = P7. 摩根律?(P∨Q) = ?P∧?Q?(P∧Q) = ?P∨?Q對(duì)蘊(yùn)涵詞、雙條件詞作否定有?(P?Q) = P∧?Q?(P?Q) = ?P?Q = P??Q= (?P

10、∧Q)∨(P∧?Q),,,8. 同一律P∨F = PP∧T = PT?P = PT?P = P還有P?F = ?PF?P = ?P,,,9. 零律P∨T = TP∧F = F還有P?T = TF?P = T10. 補(bǔ)余律P∨?P = TP∧?P = F還有P??P = ?P?P?P = PP??P = F,,,注: 所有這些公式，都可

11、使用真值表加以驗(yàn)證,Venn圖(理解等式),將P、Q理解為某總體論域上的子集合，并規(guī)定：P∧Q為兩集合的公共部分(交集合)P∨Q為兩集合的全部(并集合)?P為總體論域(如矩形域)中P的余集,Venn圖(理解等式),從Venn 圖，因P∧Q較P來得“小”, P∨Q較P來得“大”，從而有P∨(P∧Q) = PP∧(P∨Q) = P,理解等式: Venn圖，自然語言,?(P∨Q) = ?P∧?QVenn圖(理解集合間、命題邏

12、輯中、部分信息量間的一些關(guān)系)對(duì)這些等式使用自然用語加以說明，將有助于理解如P表示張三是學(xué)生, Q表示李四是工人, 那么?(P∨Q)就表示并非“張三是學(xué)生或者李四是工人”。這相當(dāng)于說，“張三不是學(xué)生而且李四也不是工人”，即可由?P∧?Q表示, 從而有?(P∨Q) = ?P∧?Q,2.2.2 常用的等值公式,由于人們對(duì)?、∨、∧更為熟悉，常將含有?和?的公式化成僅含有?、∨、∧的公式。這也是證明和理解含有?，?的公式的一般方法公式

13、11-18是等值演算中經(jīng)常使用的, 也該掌握它們, 特別是能直觀地解釋它們的成立,11. P?Q = ?P ∨Q,通常對(duì)P?Q進(jìn)行運(yùn)算時(shí), 不如用?P∨Q來得方便。而且以?P∨Q表示P?Q幫助我們理解如果P則Q的邏輯含義問題是這種表示也有缺點(diǎn)，丟失了P、Q間的因果關(guān)系,12. P?Q = ?Q??P,逆否定理，假言易位如將P?Q視為正定理, 那么?Q??P就是相應(yīng)的逆否定理, 它們必然同時(shí)為真, 同時(shí)為假, 所以是等值的,13. P

14、?(Q?R) = (P∧Q)?R,前提合并P是(Q?R)的前提, Q是R的前提, 于是可將兩個(gè)前提的合取P∧Q作為總的前提。 即如果P則如果Q則R, 等價(jià)于如果P與Q則R,14. P?Q = (P∧Q)∨(?P∧?Q),從取真來描述雙條件這可解釋為P?Q為真, 有兩種可能的情形, 即(P∧Q)為真或(?P∧?Q)為真。而P∧Q為真, 必是在P = Q = T的情況下出現(xiàn); ?P∧?Q為真, 必是在P = Q = F的情況下出現(xiàn)。從而

15、可說, P?Q為真, 是在P、Q同時(shí)為真或同時(shí)為假時(shí)成立。這就是從取真來描述這等式,15. P?Q = (P∨?Q)∧(?P∨Q),從取假來描述雙條件這可解釋為P?Q為假, 有兩種可能的情形, 即(P∨?Q)為假或(?P∨Q)為假, 而P∨?Q為假, 必是在P = F, Q = T的情況下出現(xiàn); ?P∨Q為假, 必是在P = T, Q = F的情況下出現(xiàn)。從而可說P?Q為假, 是在P真Q假或P假Q(mào)真時(shí)成立。這就是從取假來描述這等式,1

16、6. P?Q = (P?Q)∧(Q?P),從蘊(yùn)含詞來描述雙條件這表明P?Q成立, 等價(jià)于正定理P?Q和逆定理Q?P都成立,17. P?(Q?R) = Q?(P?R),前提交換前提條件P、Q可交換次序,18. (P?R)∧(Q?R)=(P∨Q)?R,左端說明的是由P而且由Q都有R成立。從而可以說由P或Q就有R成立, 這就是等式右端,補(bǔ)充,等價(jià)否定等值式P?Q = ?P??Q歸謬論(P?Q)?(P??Q) = ?P,小節(jié)一下常

17、用的等值式,1. ? ，? 的結(jié)合律，交換律，分配律，吸收律2. De Morgan定理和廣義 De Morgan定理3. P? Q 等值 ?P ? Q (E16) 4. P ? Q = (P? Q ) ? (Q? P ),2.2.3 置換規(guī)則,置換定義對(duì)公式A的子公式, 用與之等值的公式來代換便稱置換置換規(guī)則公式A的子公式置換后A化為公式B, 必有A = B當(dāng)A是重言式時(shí), 置換后的公式B必也是重言

18、式置換與代入是有區(qū)別的。置換只要求A的某一子公式作代換, 不必對(duì)所有同一的子公式都作代換,代入規(guī)則回顧,A是一個(gè)公式，對(duì)A使用代入規(guī)則得公式B，若A是重言式，則B也是重言式為保證重言式經(jīng)代入規(guī)則仍得到保持，要求公式中被代換的只能是命題變元(原子命題), 而不能是復(fù)合命題對(duì)公式中某命題變元施以代入，必須對(duì)該公式中出現(xiàn)的所有同一命題變元代換以同一公式,2.2.4 等值演算舉例,例1: 證明(?P∧(?Q∧R))∨(Q∧R)∨(P∧

19、R) = R證明: 左端= (?P∧(?Q∧R)) ∨((Q∨P)∧R)(分配律)= ((?P∧?Q)∧R))∨((Q∨P)∧R)(結(jié)合律)= (?(P∨Q)∧R)∨((Q∨P)∧R)(摩根律)= (?(P∨Q)∨(Q∨P))∧R(分配律) = (?(P∨Q)∨(P∨Q))∧R(交換律)= T∧R(置 換)= R(同一律),例2: 試證 ((P∨Q)∧?(

20、?P∧(?Q∨?R))) ∨(?P∧?Q)∨(?P∧?R) = T證明:左端=((P∨Q)∧(P∨(Q∧R)))∨?((P∨Q)∧(P∨R))(摩根律)=((P∨Q)∧(P∨Q)∧(P∨R))∨?((P∨Q)∧(P∨R))(分配律)=((P∨Q)∧(P∨R))∨?((P∨Q)∧(P∨R))(等冪律)=T,舉例,問題提出：由命題公式寫真值表是容易的，那么如何由真值表寫命

21、題公式呢？,2.3 命題公式與真值表關(guān)系,2.3.1 從T來列寫,記憶方法：各項(xiàng)間用∨，每項(xiàng)內(nèi)用∧每項(xiàng)內(nèi)書寫方法：例真值表中P=T且Q=F等價(jià)于P∧?Q=T簡化方法：有時(shí)A的表達(dá)通過?A來描述,2.3.2 從F來列寫,記憶方法：各項(xiàng)間用∧ ，每項(xiàng)內(nèi)用∨每項(xiàng)內(nèi)書寫方法：例真值表中P=T且Q=F等價(jià)于?P∨Q=F簡化方法：有時(shí)A的表達(dá)通過?A來描述,舉例,從A的真值T直接: A = (¬P ∧¬Q)

22、∨ (¬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á)式簡單,,應(yīng)用,在電路設(shè)計(jì)的時(shí)候簡化邏輯設(shè)計(jì)，節(jié)省邏輯單元 。 計(jì)算機(jī) or 單片機(jī) or

23、 邏輯電路?CPU的核心單元ALU （ Arithmetic-Logic Unit ），主要負(fù)責(zé)整數(shù)運(yùn)算。,,,應(yīng)用,【生活中的例子】 雙控照明開關(guān)。 K1 K2 燈光 0 0 0 1 0 1 0 1 1 1 1 0,,,主范式 的應(yīng)用,【生活中的例子】

24、 雙控照明開關(guān)。,,,作業(yè)(1),(P37) 1(1, 3), 2,,2.4 聯(lián)結(jié)詞的完備集,問題的提出對(duì)n 個(gè)命題變項(xiàng)P1…Pn來說, 共可定義出多少個(gè)聯(lián)結(jié)詞? 在那么多聯(lián)結(jié)詞中有多少是相互獨(dú)立的?3個(gè)新聯(lián)結(jié)詞：,思考：考慮異或聯(lián)結(jié)詞與雙條件聯(lián)結(jié)詞的關(guān)系(可利用真值表),2.4.1 命題聯(lián)結(jié)詞的個(gè)數(shù),第一個(gè)問題。可定義多少個(gè)聯(lián)結(jié)詞？由命題變項(xiàng)和命題聯(lián)結(jié)詞可以構(gòu)成無限多個(gè)合式公式把所有的合式公式分類：將等值的公式視為同一類

25、，從中選一個(gè)作代表稱之為真值函項(xiàng)。對(duì)一個(gè)真值函項(xiàng)，或者說對(duì)于該類合式公式，就可定義一個(gè)聯(lián)結(jié)詞與之對(duì)應(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ù),由真值表寫出真值函項(xiàng)的命題公式：f0(P) = F(永假式)f1

26、(P) = P(P自身)f2(P) = ?P (否定詞)√f3(P) = T(永真式)新的公式只有f2(P), 與之對(duì)應(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è)

27、數(shù),,,根據(jù)真值表寫出各真值函項(xiàng)的命題表達(dá)式:g0(P,Q) = F(永假式)g1(P,Q) = P∧Q (合取式)g2(P,Q) = P∧?Q g3(P,Q) = (P∧?Q)∨(P∧Q) = P∧(?Q∨Q) = Pg4(P,Q) = ?P∧Q g5(P,Q) = (?P∧Q)∨(P∧Q) = (?P∨P)∧Q = Qg6(P,Q) = P Q (異或式)

28、g7(P,Q) = P∨Q (析取式)g8(P,Q) = ?P∧?Q = P ? Q(或非式) g9(P,Q) = P ?Q (雙條件式)g10(P,Q) = (?P∧?Q)∨(P∧?Q) = (?P∨P)∧?Q = ?Qg11(P,Q) = P∨?Q = Q?P(蘊(yùn)涵式)g12(P,Q) = (?P∧ ?Q)∨(?P∧Q) = ?P∧(?Q∨Q) = ?Pg13(P,Q) = ?P∨Q =

29、 P?Q(蘊(yùn)涵式)g14(P,Q) = ?P∨?Q = P ? Q (與非式)g15(P,Q) = T (永真式),,,n元聯(lián)結(jié)詞對(duì)n個(gè)命題變元P1 , … , Pn , 每個(gè)Pi有兩種取值, 從而對(duì)P1…Pn來說共有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é)詞的完備集

30、定義: 設(shè)C是聯(lián)結(jié)詞的集合，如果對(duì)任一命題公式(能直接使用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é)介紹的由真值表列寫邏輯公式的過程可知, 任一公式都可由?, ∨, ∧表示出來, 從而{?, ∨, ∧}是完備的3. {?, ∨}是聯(lián)結(jié)詞的完備集(獨(dú)立的完

31、備集)證明：P∧Q = ?(?P∨?Q)，因此∧可由{?, ∨}表示4. {?, ∧}是聯(lián)結(jié)詞的完備集(獨(dú)立的完備集)證明：P∨Q = ?(?P∧?Q)，因此∨可由{?, ∧}表示,完備集,5. {?, ?}是完備集(獨(dú)立的完備集)因?yàn)椋篜∨Q = ?P?Q6. {?}是完備集(獨(dú)立的完備集)7. {?}是完備集(獨(dú)立的完備集)8. {?, ∧, ∨, ?, ?}是完備的 因?yàn)樗?中的集合,完備集,{∨

32、,∧,?, ?}不是完備的因?yàn)?不能僅由該集合的聯(lián)結(jié)詞表達(dá)出{?, ?}不是完備的{∨,∧,?, ?}的任何子集都是不完備的 {?, ?}的任何子集也是不完備的(如果一個(gè)聯(lián)結(jié)詞的集合是不完備的，那么它的任何子集都是不完備的){∨,∧}不是完備的,不完備集,最小的聯(lián)結(jié)詞的完備集—基底,基底：完備的聯(lián)結(jié)詞集合的聯(lián)結(jié)詞是獨(dú)立的，也就是說這些聯(lián)結(jié)詞不能相互表示任取四個(gè)一元或二元聯(lián)結(jié)詞，它們必組不成基底,基底,只含一個(gè)聯(lián)結(jié)

33、詞的: 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-- ?,聯(lián)結(jié)詞的功能完全集,{ }和{ }都是聯(lián)結(jié)詞的最小功能完全集。

34、 證明基本思路： 可以表示其他功能完全集。如： x & y = (x y) (x y)能不能在生活中找到和 相似的運(yùn)算？,,,,§1.5.2 聯(lián)結(jié)詞的功能完全集,與非門電路能不能在生活中找到與非相似的運(yùn)算？ FPGA,,,,2.5 對(duì)偶式,研究目的簡化等值公式的討論希望一個(gè)公式成立，能夠?qū)С雠c其“相像”的公式成立邏輯關(guān)系上看，是一種邏輯規(guī)律對(duì)偶式定義：將A中出現(xiàn)的∨、∧、

35、T、F分別以∧、∨、F、T代換, 得到公式A*, 則稱A*是A的對(duì)偶式, 或說A和A*互為對(duì)偶式注：這里假定A中僅出現(xiàn)? 、∨、∧三個(gè)聯(lián)結(jié)詞若A = B，必有A*=B*?,新符號(hào)“-”: (代入規(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－)－

36、=A定理2.5.3 ?A = A*－ (摩根律的另一種形式)更多：(A ? B)* = A* ? B*，(A ? B)- = A- ? B- (A ? B)* = A* ? B*，(A ? B)- = A- ? B-,對(duì)偶式相關(guān)定理,62,性質(zhì)舉例,A= (?P ? (Q ? R)) ?TA*= (?P ? (Q ? R)) ? FA-= (?(?P) ? (?Q ? ?R)) ?TA*- = (?(?

37、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中至少有一

38、個(gè)聯(lián)結(jié)詞，可分為三種情形A = ?A1, A = A1∧A2, A = A1∨A2 其中A1, A2中聯(lián)結(jié)詞個(gè)數(shù)≤k。依歸納法假設(shè)，?A1 = A1*－, ?A2 = A2*－,定理2.5.3 ?A = A*－,當(dāng) A = ?A1時(shí) ?A = ?(?A1) A = ?A1 = ?(A1*－)歸納法假設(shè) = (?A1)*－定理2.5.1, 2.5.2 = A*

39、－ A = ?A1,定理2.5.3 ?A = A*－,當(dāng)A = A1∧A2時(shí)， ?A = ?(A1∧A2) = ?A1∨?A2摩根律 = A1*－∨A2*－歸納法假設(shè) = (A1*∨A2*)－A－定義 = (A1∧A2)*－ A*定義 = A*－ 另一種情況同理，從而定理得證。,定理2.5.3 (摩根律

40、) ?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-永真。 如果A-永真，則(A-)-永真，又根據(jù)定理2.5.2有 A=(A-)-, 所以A永真(2) 根據(jù)定理2.5.3，?A = A*－，所以根據(jù)(1)可得(2)

41、成立,對(duì)偶式相關(guān)定理,定理 2.5.4 若A = B，必有A*=B*證明: 因?yàn)锳 = B 等價(jià)于A?B 永真 等價(jià)于?A??B永真。依定理2.5.3, ?A = A*－, ?B = B*－ 于是A*－? B*－永真，則(A*-? B*-)-永真(根據(jù)代入規(guī)則，A永真，A-永真)亦即 A* ? B* 永真故 A* = B*,對(duì)偶式相關(guān)定理,定理2.5.5 若A?B永真, 必有B*?A*永真或者，A?B和B*?A*同永

42、真證明:(1) 如果A?B永真，則?B??A永真(逆否命題)根據(jù)定理2.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*)*所以A?B永真

43、 ?,對(duì)偶式相關(guān)定理,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)形對(duì)任意兩個(gè)形式上不同的公式，可判斷它們的是否等值借助于標(biāo)準(zhǔn)形容易判斷任一公式是否為重言式或矛盾式,2.6.1 范式,若干術(shù)語簡單命題P及其

44、否定式?P統(tǒng)稱為文字一些文字的合取稱為(簡單)合取式一些文字的析取稱為(簡單)析取式(也稱子句)P與?P稱為互補(bǔ)對(duì)析取范式，形如：A1∨A2∨ … ∨An其中Ai(i=1, …, n)為合取式合取范式，形如： A1∧A2∧ … ∧An其中Ai(i=1, …, n)為析取式,72,范式舉例,p, ?q (既是簡單合取式，又是簡單析取式)p1∨p2 , q1∧q2,范式定理,范式定理：任一命題公式都存在與之等值的析取

45、范式、合取范式求范式三步曲：1) 消去?和?2) 否定深入到命題變項(xiàng)3) 使用分配律的等值變換,舉例,求¬(P∨Q)?(P∧Q)的析取范式¬(P∨Q)?(P∧Q)=(¬(P∨Q)∧(P∧Q))∨(¬¬(P∨Q)∧¬(P∧Q))=(¬P∧¬Q∧P∧Q)∨((P∨Q)∧(¬P∨¬Q))=(¬P∧¬Q∧

46、P∧Q)∨(P∧¬P)∨(P∧¬Q)∨(Q∧¬P)∨(Q∧¬Q) (析取范式)= (P∧¬Q)∨(Q∧¬P) (析取范式，簡化)注：范式的不唯一性,舉例,求¬(P∨Q)?(P∧Q)的合取范式¬(P∨Q)?(P∧Q)=(P∧¬Q)∨(Q∧¬P) (析取范式，簡化)=(P∨Q)∧(P∨¬P)∧(¬Q∨Q)∧(&

47、#172;Q∨¬P)(合取范式)=(P∨Q)∧(¬Q∨¬P) (合取范式，簡化)注：已知一種范式，可以使用分配律求另一種范式,判斷重言式合取范式中所有析取式都有互補(bǔ)對(duì) 判斷矛盾式析取范式中所有合取式都有互補(bǔ)對(duì) 判斷兩公式是否等值范式不唯一，引入唯一的主范式，便于判別公式相等,范式功能,2.6.2 主范式,主析取范式極小項(xiàng)定義與編碼Q1∧…∧Qn是由n個(gè)命題變項(xiàng)P1, …,

48、 Pn組成的公式, 其中Qi=Pi或者¬Pi, 我們稱其為極小項(xiàng), 一般用mj表示例：P1, P2的極小項(xiàng)有四個(gè)¬P1∧ ¬P2 (m0), ¬P1∧ P2 (m1), P1∧ ¬P2 (m2), P1∧P2 (m3)主析取范式定義 僅由極小項(xiàng)構(gòu)成的析取式主析取范式唯一性定理任一含有n個(gè)命題變項(xiàng)的公式，都有唯一一個(gè)與之等值的恰僅含這n個(gè)命題變項(xiàng)的主

49、析取范式,極小項(xiàng)必須含有Q1, …, Qn全部n個(gè)文字,由真值表寫主析取范式：從T寫P ? Q=(¬P∧¬Q)∨(P∧Q)=m0∨m3= ∨0,3由析取范式寫主析取范式：填滿命題變項(xiàng)法, 永真式¬P = ¬P∧(Q∨¬Q) = (¬P∧Q)∨(¬P∧¬Q) Q = Q∧(P∨¬P) = (Q∧P)∨(Q∧¬P)P→Q

50、 = ¬P∨Q = (¬P∧Q)∨(¬P∧¬Q) ∨ (Q∧P)∨(Q∧¬P) = (¬P∧¬Q)∨(¬P∧Q)∨(P∧Q) = m0∨m1∨m3 = ∨0,1,3,主析取范式,所有可能極小項(xiàng)的個(gè)數(shù)：2n每個(gè)極小項(xiàng)只在一個(gè)解釋下為真對(duì)于每個(gè)解釋只有一個(gè)極小項(xiàng)為真 極小項(xiàng)互不相等，且mi ∧ mj=F (i ≠ j)

51、任一含有n個(gè)變項(xiàng)的公式，都可由k個(gè)(k≤2n)極小項(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∨ … ∨Qn是由n個(gè)命題變項(xiàng)P1, …, Pn組

52、成的公式, 其中Qi=Pi或者¬Pi(i = 1, …, n), 我們稱其為極大項(xiàng), 一般用Mj表示(0≤j≤2n-1)例：P1, P2的極大項(xiàng)有四個(gè)¬P1∨¬P2 (M0), ¬P1∨P2 (M1), P1∨¬P2 (M2), P1∨P2 (M3)主合取范式定義僅由極大項(xiàng)構(gòu)成的合取式主合取范式唯一性定理任一含有n個(gè)命題變項(xiàng)的公式，都有唯一一個(gè)與之

53、等值的恰僅含這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è)解釋下為假對(duì)于每個(gè)解釋只有一個(gè)極大項(xiàng)為假 極大項(xiàng)互不相等，且Mi ∨ Mj=T (i ≠ j)任一含有n個(gè)變項(xiàng)的公式，都可由k個(gè)(k≤2n)極大項(xiàng)的合取來表示；或者說所有的極大項(xiàng)可建立一個(gè)“坐標(biāo)系”恰由

54、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

55、,4,1已知主合取范式A = ∧1,4,5 = ∨({0,1,…,7}-{1,4,5}補(bǔ)) = ∨({0,1,…,7}-{6,3,2}) = ∨0,1,4,5,7,主析取范式與主合取范式的轉(zhuǎn)換,注意從真值表列寫公式的主析取范式和主合取范式時(shí)，除了分別從T和F列寫外，在填寫合取式和析取式時(shí)是取變項(xiàng)還是其否定是有區(qū)別的，這就是主合取范式、主析取范式轉(zhuǎn)換過程要求補(bǔ)的原因數(shù)字補(bǔ)不同于補(bǔ)集。這里的數(shù)字求補(bǔ)是對(duì)2n-1=23-1=7而言的

56、，如2的補(bǔ)是5，因?yàn)?+5=7,主范式的用途——與真值表相同,(1) 求公式的成真賦值和成假賦值例如：(P??Q)?R ? m1?m3?m5? m6?m7，其成真指派為001, 011, 101, 110, 111，其余的指派 000, 010, 100為成假指派. 類似地，由主合取范式也可立即求出成假指派和成真指派,主范式的用途(續(xù)),(2) 判斷公式的類型 設(shè)A含n個(gè)命題變項(xiàng)，則 A為重言式?A的主析取范式含2n

57、個(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?(Q?R) 與 (P?Q)?R ⑵ P?

58、(Q?R) 與 (P?Q)?R解 P?(Q?R) = m0?m1?m2?m3?m4?m5?m7 (P?Q)?R = m0?m1?m2?m3?m4?m5?m7 (P?Q)?R = m1?m3? m4?m5? m7顯見，⑴中的兩公式等值，而⑵的不等值.,作業(yè)(2),(P37) 3, 4(2), 5(8)董老師書： (P24) 2 (2,3), 4(4) ,5,,2.7 推理形式,自然語言推理前提1：如果我

59、今天病了，那么我沒來上課前提2：今天我病了結(jié)論：所以今天我沒來上課推理形式引入符號(hào), 形式化并用條件式表示出來例：((P?Q)∧P)?Q正確的推理形式前提真，結(jié)論必真的推理形式((P?Q)∧?Q)??P 正確的推理形式((P?Q)∧?P)??Q 不正確的推理形式,重言蘊(yùn)涵,重言蘊(yùn)涵對(duì)于公式A, B, 如果當(dāng)A取值為真時(shí)，B必取值為真，則稱A永真蘊(yùn)涵B，或稱B是A的邏輯推論。記為： A ? B(?是真值關(guān)系，并非邏

60、輯聯(lián)結(jié)詞)重言蘊(yùn)涵與正確推理形式如果A ? B，則A?B是正確的推理形式如果A?B是正確的推理形式，可以用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,

61、A ? C, 則A ? B∧C 如果A ? C, B ? C, 則A∨B ? C,重言蘊(yùn)涵的結(jié)果,2.8 基本的推理公式,1. (P∧Q) ? P化簡律2. ?(P?Q) ? P 3. ?(P?Q) ? ?Q4. P ? (P∨Q)附加律 5. ?P ? P?Q6. Q ? P?Q7. (P∨Q)∧?P ? Q 析取三段論8. (P?Q)∧P ? Q 假言推理、分離規(guī)則,9.

62、 (P?Q)∧?Q ? ?P 拒取式10. (P?Q)∧(Q?R) ? (P?R) 假言三段論、三段論11. (P?Q)∧(Q?R) ? (P?R)等價(jià)三段論12. (P?R)∧(Q?R)∧(P∨Q) ? R 構(gòu)造性二難(特殊形式)13. (P?Q)∧(R?S)∧(P∨R) ? (Q∨S)構(gòu)造性二難14. (P?Q)∧(R?S)∧(?Q∨? S)

63、 ? (?P∨?R) 破壞性二難15. (Q?R) ? ((P∨Q)?(P∨R))16. (Q?R) ? ((P?Q)?(P?R))注：真值表證明，或者語義上直接說明,基本的推理公式,2.8.2 證明推理公式的方法(五種),A ? B成立的充分必要條件是A?B(或¬A∨B) 為重言式證明：如果A ? B, 那么在任一解釋下, A真B必真, 而不會(huì)出現(xiàn)A真B假的情況, 于是A?B為重言式。如果

64、A?B為重言式, 則在任一解釋下, 若A為真, B只能為真不可能為假, 從而有A ? B證明A?B為重言式的方法真值表、等值演算、范式,例1 用等值演算法證明(P?Q)∧P?Q為重言式 (P?Q)∧P?Q ?¬((¬P∨Q)∧P)∨Q?((P∧¬Q)∨¬P)∨Q? ¬Q∨¬P∨Q? T,舉例,例2 用主析取范式法證明(P?Q)∧Q?P不是重言式 　(

65、P?Q)∧Q?P ?¬((¬P∨Q)∧Q)∨P?((P∧¬Q)∨¬Q)∨P (吸收律)?¬Q∨P?((¬Q∧P)∨(¬Q∧¬P))∨((P∧Q)∨(P∧¬Q))? (¬P∧¬Q)∨(P∧¬Q)∨(P∧Q)? m0∨m2∨m3缺少m1即(¬P∧Q), 所以(P?Q)∧Q?P不是重言式，或者說推理

66、形式(P?Q)∧Q?P不正確,舉例,2. A?B成立的充分必要條件是A?B為重言式, 即 A∧¬B是矛盾式3. (逆否定理) A?B成立的充分必要條件¬B? ¬A4. 解釋法　例: (P?Q)∧(Q?R) ? (P?R)若(P?Q)∧(Q?R)＝T, 則同時(shí)有P?Q＝T, Q?R=T若P=T, 則Q=T, 進(jìn)而R=T. 故P?R＝T若P=F, 則Q可取任意值: (1) Q=T, 則R=

67、T; (2) Q=F, 則R取何值無論如何, P?R=T5. 真值表法, 即通過真值表檢驗(yàn)A為真時(shí)B一定為真注： 證明A?B時(shí)不考慮A為假的情況,證明推理公式的方法,上述方法的特點(diǎn),都是從真值的角度進(jìn)行論證和解釋看不出由前提A到結(jié)論B的推演過程難于擴(kuò)展到謂詞邏輯的推演過程,2.9 推理演算(證明推理公式A?B的新方法),基本思想：從前提A1, …, An出發(fā)(即A= A1?A2? … ?An)運(yùn)用推理規(guī)則和基本推理公式，逐

68、步推演出結(jié)論B，即證明A?B推理規(guī)則前提引入規(guī)則（P規(guī)則）推理過程中可以隨時(shí)引入前提A1, …, An結(jié)論引用規(guī)則（T規(guī)則）推理過程中得到的中間結(jié)論可作為后續(xù)推理的前提代入規(guī)則(參考P8)推理過程中對(duì)重言式的命題變項(xiàng)可使用該規(guī)則,推理規(guī)則,置換規(guī)則(參考P18)推理過程中命題公式中任何部分公式都可由與之等值的公式置換分離規(guī)則(假言推理)已知命題公式A?B和A, 則有命題公式B(B被分離出來)條件證明規(guī)則

69、(附加前提)（CP規(guī)則）A1 ? A2?B與A1?A2 ? B是等價(jià)的。即結(jié)論方的條件A2移到了前提方, 作為條件使用。,例1 證明R是P?Q, Q?R, P的邏輯推論 特點(diǎn): 前提引入規(guī)則、分離規(guī)則例2 證明R∨S可以由前提C∨D, (C∨D)?¬E, ¬E?(A∧¬B ), (A∧¬B)?R∨S推演出來特點(diǎn): 基本推理公式(三段論)例3 證明(P∨Q)∧(P?R)∧(Q?S) ?

70、S∨R特點(diǎn): 置換規(guī)則例4 證明(P?(Q?S))∧(¬R∨P)∧Q ? R?S特點(diǎn): 條件證明規(guī)則(附加前提引入)例5 證明 (¬(P?Q)?¬(R∨S))∧((Q?P)∨¬R)∧R ? (P?Q)特點(diǎn): 反證法、條件證明、結(jié)論引入,舉例,設(shè)R1=B∨A’1, R2=?B∨A’2為兩個(gè)子句有互補(bǔ)對(duì)B和?B則新子句R(R1, R2)= A’1∨A’2稱為R1, R2的歸結(jié)式.