命題邏輯的等值和推理演算課件

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

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

由真值表寫(xiě)命題公式(由T寫(xiě)、由F寫(xiě))等值演算(考察邏輯關(guān)系符?(=))等值定理、公式推理演算(考察邏輯關(guān)系符?)推理形式(正確推理形式的表示)基本推理公式(各種三段論及五種證明方法)推理演算(證明推理公式的第六種方法，使用推理規(guī)則)歸結(jié)推理法(證明推理公式的第七種方法，常用反證法)推理演算(考察邏輯關(guān)系符?)推理形式(正確推理形式的表示)2.1等值定理若把初等數(shù)學(xué)里的＋、－、×、÷等運(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等值定理若把初等數(shù)學(xué)里的＋、－、×、÷等運(yùn)算符看2.1.1等值的定義給定兩個(gè)命題公式A和B,而P1…Pn是出現(xiàn)于A和B中的所有命題變項(xiàng),那么公式A和B共有2n個(gè)解釋,若對(duì)其中的任一解釋,公式A和B的真值都相等,就稱A和B是等值的(或等價(jià)的)。記作A=B或AB顯然，可以根據(jù)真值表來(lái)判明任何兩個(gè)公式是否是等值的

2.1.1等值的定義給定兩個(gè)命題公式A和B,而P1…例1:證明(P∧P)∨Q=Q證明:畫(huà)出(P∧P)∨Q與Q的真值表可看出等式是成立的。例1:證明(P∧P)∨Q=Q證明:畫(huà)出(P∧P)例2:證明P∨P=Q∨Q證明:畫(huà)出P∨P,Q∨Q的真值表,可看出它們是等值的,而且它們都是重言式。例2:證明P∨P=Q∨Q證明:畫(huà)出P∨P,Q從例1、2還可說(shuō)明,兩個(gè)公式等值并不一定要求它們一定含有相同的命題變項(xiàng)若僅在等式一端的公式里有變項(xiàng)P出現(xiàn),那么等式兩端的公式其真值均與P無(wú)關(guān)。例1中公式(P∧P)∨Q與Q的真值都同P無(wú)關(guān)例2中P∨P,Q∨Q都是重言式,它們的真值也都與P、Q無(wú)關(guān)。說(shuō)明從例1、2還可說(shuō)明,兩個(gè)公式等值并不一定要求它們一定含有相2.1.2等值定理定理

對(duì)公式A和B,A=B的充分必要條件是AB是重言式。A、B不一定都是簡(jiǎn)單命題,可能是由簡(jiǎn)單命題P1,…,Pn構(gòu)成的.對(duì)A,B的一個(gè)解釋,指的是對(duì)P1,…,Pn的一組具體的真值設(shè)定.若AB為重言式,則在任一解釋下A和B都只能有相同的真值,這就是定理的意思。

2.1.2等值定理定理對(duì)公式A和B,A=B的充分證明若AB是重言式,即在任一解釋下,AB的真值都為T(mén)依AB的定義只有在A、B有相同的值時(shí),才有AB=T。于是在任一解釋下,A和B都有相同的真值,從而有A=B。反過(guò)來(lái)，若有A=B,即在任一解釋下A和B都有相同的真值,依AB的定義,AB只有為真,從而AB是重言式。注：根據(jù)該等值定理，證明兩個(gè)公式等值，只要證明由這兩個(gè)公式構(gòu)成的雙條件式是重言式即可證明若AB是重言式,即在任一解釋下,AB“＝”作為邏輯關(guān)系符是一種等價(jià)關(guān)系不要將“＝”視作聯(lián)結(jié)詞，在合式公式定義里沒(méi)有“＝”出現(xiàn)A=B是表示公式A與B的一種關(guān)系。這種關(guān)系具有三個(gè)性質(zhì):

1.自反性 A=A 2.對(duì)稱性 若A=B,則B=A 3.傳遞性 若A=B,B=C,則A=C這三條性質(zhì)體現(xiàn)了“＝”的實(shí)質(zhì)含義。“＝”作為邏輯關(guān)系符是一種等價(jià)關(guān)系不要將“＝”視作聯(lián)結(jié)詞，在2.2等值公式2.2.1基本的等值公式(命題定律,P和Q是任意的命題公式) 1.雙重否定律

P=P 2.結(jié)合律 (P∨Q)∨R=P∨(Q∨R) (P∧Q)∧R=P∧(Q∧R) (PQ)R=P(QR)

注:所有這些公式，都可使用真值表加以驗(yàn)證2.2等值公式2.2.1基本的等值公式(命題定律,3.交換律

P∨Q=Q∨P P∧Q=Q∧P PQ=QP4.分配律

P∨(Q∧R)=(P∨Q)∧(P∨R) P∧(Q∨R)=(P∧Q)∨(P∧R) P(QR)=(PQ)(PR)5.等冪律(恒等律)

P∨P=P P∧P=P PP=T PP=T3.交換律6.吸收律

P∨(P∧Q)=P P∧(P∨Q)=P7.摩根律

(P∨Q)=P∧Q

(P∧Q)=P∨Q

對(duì)蘊(yùn)涵詞、雙條件詞作否定有

(PQ)=P∧Q

(PQ)=PQ=PQ =(P∧Q)∨(P∧Q)6.吸收律8.同一律

P∨F=P P∧T=P TP=P TP=P

還有

PF=P FP=P8.同一律9.零律

P∨T=T P∧F=F

還有

PT=T FP=T10.補(bǔ)余律

P∨P=T P∧P=F

還有

PP=P

PP=P PP=F9.零律Venn圖(理解等式)將P、Q理解為某總體論域上的子集合，并規(guī)定：P∧Q為兩集合的公共部分(交集合)P∨Q為兩集合的全部(并集合)P為總體論域(如矩形域)中P的余集Venn圖(理解等式)將P、Q理解為某總體論域上的子集合，并Venn圖(理解等式)從Venn圖，因P∧Q較P來(lái)得“小”,P∨Q較P來(lái)得“大”，從而有

P∨(P∧Q)=P P∧(P∨Q)=PVenn圖(理解等式)從Venn圖，因P∧Q較P來(lái)得“小”理解等式:Venn圖，自然語(yǔ)言(P∨Q)=P∧QVenn圖(理解集合間、命題邏輯中、部分信息量間的一些關(guān)系)對(duì)這些等式使用自然用語(yǔ)加以說(shuō)明，將有助于理解如P表示張三是學(xué)生,Q表示李四是工人,那么(P∨Q)就表示并非“張三是學(xué)生或者李四是工人”。這相當(dāng)于說(shuō)，“張三不是學(xué)生而且李四也不是工人”，即可由P∧Q表示,從而有(P∨Q)=P∧Q理解等式:Venn圖，自然語(yǔ)言(P∨Q)=P∧Q2.2.2常用的等值公式由于人們對(duì)、∨、∧更為熟悉，常將含有和的公式化成僅含有、∨、∧的公式。這也是證明和理解含有，的公式的一般方法公式11-18是等值演算中經(jīng)常使用的,也該掌握它們,特別是能直觀地解釋它們的成立2.2.2常用的等值公式由于人們對(duì)、∨、∧更為熟悉，11.PQ=P∨Q通常對(duì)PQ進(jìn)行運(yùn)算時(shí),不如用P∨Q來(lái)得方便。而且以P∨Q表示PQ幫助我們理解如果P則Q的邏輯含義問(wèn)題是這種表示也有缺點(diǎn)，丟失了P、Q間的因果關(guān)系11.PQ=P∨Q12.PQ=QP 逆否定理，假言易位如將PQ視為正定理,那么QP就是相應(yīng)的逆否定理,它們必然同時(shí)為真,同時(shí)為假,所以是等值的12.PQ=QP 逆否定理，假言易位13.P(QR)=(P∧Q)R前提合并P是(QR)的前提,Q是R的前提,于是可將兩個(gè)前提的合取P∧Q作為總的前提。即如果P則如果Q則R,等價(jià)于如果P與Q則R13.P(QR)=(P∧Q)R前提合并14.PQ=(P∧Q)∨(P∧Q)從取真來(lái)描述雙條件這可解釋為PQ為真,有兩種可能的情形,即(P∧Q)為真或(P∧Q)為真。而P∧Q為真,必是在P=Q=T的情況下出現(xiàn);P∧Q為真,必是在P=Q=F的情況下出現(xiàn)。從而可說(shuō),PQ為真,是在P、Q同時(shí)為真或同時(shí)為假時(shí)成立。這就是從取真來(lái)描述這等式14.PQ=(P∧Q)∨(P∧Q)從取真來(lái)描述雙15.PQ=(P∨Q)∧(P∨Q)從取假來(lái)描述雙條件這可解釋為PQ為假,有兩種可能的情形,即(P∨Q)為假或(P∨Q)為假,而P∨Q為假,必是在P=F,Q=T的情況下出現(xiàn);P∨Q為假,必是在P=T,Q=F的情況下出現(xiàn)。從而可說(shuō)PQ為假,是在P真Q假或P假Q(mào)真時(shí)成立。這就是從取假來(lái)描述這等式15.PQ=(P∨Q)∧(P∨Q)從取假來(lái)描述雙16.PQ=(PQ)∧(QP)從蘊(yùn)含詞來(lái)描述雙條件這表明PQ成立,等價(jià)于正定理PQ和逆定理QP都成立16.PQ=(PQ)∧(QP)從蘊(yùn)含詞來(lái)描述雙條17.P(QR)=Q(PR)前提交換前提條件P、Q可交換次序17.P(QR)=Q(PR)前提交換18.(PR)∧(QR)=(P∨Q)R左端說(shuō)明的是由P而且由Q都有R成立。從而可以說(shuō)由P或Q就有R成立,這就是等式右端18.(PR)∧(QR)=(P∨Q)R左端說(shuō)明的是由補(bǔ)充等價(jià)否定等值式 PQ=PQ歸謬論 (PQ)(PQ)=P補(bǔ)充等價(jià)否定等值式2.2.3置換規(guī)則置換定義 對(duì)公式A的子公式,用與之等值的公式來(lái)代換便稱置換置換規(guī)則公式A的子公式置換后A化為公式B,必有A=B當(dāng)A是重言式時(shí),置換后的公式B必也是重言式置換與代入是有區(qū)別的。置換只要求A的某一子公式作代換,不必對(duì)所有同一的子公式都作代換2.2.3置換規(guī)則置換定義代入規(guī)則回顧A是一個(gè)公式，對(duì)A使用代入規(guī)則得公式B，若A是重言式，則B也是重言式為保證重言式經(jīng)代入規(guī)則仍得到保持，要求公式中被代換的只能是命題變?cè)?原子命題),而不能是復(fù)合命題對(duì)公式中某命題變?cè)┮源?，必須?duì)該公式中出現(xiàn)的所有同一命題變?cè)鷵Q以同一公式代入規(guī)則回顧A是一個(gè)公式，對(duì)A使用代入規(guī)則得公式B，若A是2.2.4等值演算舉例例1:證明(P∧(Q∧R))∨(Q∧R)∨(P∧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.2.4等值演算舉例例1:證明(P∧(Q∧R)例2:試證((P∨Q)∧(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 舉例例2:試證((P∨Q)∧(P∧(Q∨R)))舉問(wèn)題提出：由命題公式寫(xiě)真值表是容易的，那么如何由真值表寫(xiě)命題公式呢？2.3命題公式與真值表關(guān)系問(wèn)題提出：2.3命題公式與真值表關(guān)系2.3.1從T來(lái)列寫(xiě)記憶方法：各項(xiàng)間用∨，每項(xiàng)內(nèi)用∧每項(xiàng)內(nèi)書(shū)寫(xiě)方法：例 真值表中P=T且Q=F等價(jià)于P∧Q=T簡(jiǎn)化方法：有時(shí)A的表達(dá)通過(guò)A來(lái)描述2.3.1從T來(lái)列寫(xiě)記憶方法：各項(xiàng)間用∨，每項(xiàng)內(nèi)用∧2.3.2從F來(lái)列寫(xiě)記憶方法：各項(xiàng)間用∧

，每項(xiàng)內(nèi)用∨每項(xiàng)內(nèi)書(shū)寫(xiě)方法：例 真值表中P=T且Q=F等價(jià)于P∨Q=F簡(jiǎn)化方法：有時(shí)A的表達(dá)通過(guò)A來(lái)描述2.3.2從F來(lái)列寫(xiě)記憶方法：各項(xiàng)間用∧，每項(xiàng)內(nèi)用∨舉例從A的真值T直接:A=(?P∧?Q)∨(?P∧Q)∨(P∧Q)間接:A=??A=?(P∧?Q)=?P∨Q從B的真值F B=(?P∨

Q)∧

(?P∨?Q)當(dāng)C可取任意值 C與{P,Q}={T,T}無(wú)關(guān),可適當(dāng)選取C的真值,使其表達(dá)式簡(jiǎn)單PQA?ABCFFTFTTFTTFTFTFFTFTTTTFFX舉例從A的真值TPQA?ABCFFTFTTFTTFTFTFF作業(yè)(1)(P37)1(1,3),2作業(yè)(1)(P37)1(1,3),22.4聯(lián)結(jié)詞的完備集問(wèn)題的提出 對(duì)n個(gè)命題變項(xiàng)P1…Pn來(lái)說(shuō),共可定義出多少個(gè)聯(lián)結(jié)詞?在那么多聯(lián)結(jié)詞中有多少是相互獨(dú)立的?3個(gè)新聯(lián)結(jié)詞：思考：考慮異或聯(lián)結(jié)詞與雙條件聯(lián)結(jié)詞的關(guān)系(可利用真值表)2.4聯(lián)結(jié)詞的完備集問(wèn)題的提出思考：考慮異或聯(lián)結(jié)詞與雙2.4.1命題聯(lián)結(jié)詞的個(gè)數(shù)第一個(gè)問(wèn)題?？啥x多少個(gè)聯(lián)結(jié)詞？由命題變項(xiàng)和命題聯(lián)結(jié)詞可以構(gòu)成無(wú)限多個(gè)合式公式把所有的合式公式分類(lèi)：將等值的公式視為同一類(lèi)，從中選一個(gè)作代表稱之為真值函項(xiàng)。對(duì)一個(gè)真值函項(xiàng)，或者說(shuō)對(duì)于該類(lèi)合式公式，就可定義一個(gè)聯(lián)結(jié)詞與之對(duì)應(yīng) 例：等價(jià)類(lèi)。自然數(shù)集合N被3除余數(shù)相同的自然數(shù)構(gòu)成3個(gè)集合N0,N1,N22.4.1命題聯(lián)結(jié)詞的個(gè)數(shù)第一個(gè)問(wèn)題?？啥x多少個(gè)聯(lián)結(jié)詞一元聯(lián)結(jié)詞是聯(lián)結(jié)一個(gè)命題變項(xiàng)(如P)的P有真假2種值，因此P(自變量)上可定義4種一元聯(lián)結(jié)詞fi或說(shuō)真值函項(xiàng)fi(P),i=1,2,3,4一元聯(lián)結(jié)詞的個(gè)數(shù)一元聯(lián)結(jié)詞是聯(lián)結(jié)一個(gè)命題變項(xiàng)(如P)的一元聯(lián)結(jié)詞的個(gè)數(shù)由真值表寫(xiě)出真值函項(xiàng)的命題公式：

f0(P)=F (永假式)

f1(P)=P (P自身)

f2(P)=P(否定詞)√

f3(P)=T (永真式)新的公式只有f2(P),與之對(duì)應(yīng)的聯(lián)結(jié)詞是否定詞一元聯(lián)結(jié)詞由真值表寫(xiě)出真值函項(xiàng)的命題公式：一元聯(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或說(shuō)真值函項(xiàng)gi(P,Q)的真值表定義二元聯(lián)結(jié)詞的個(gè)數(shù)二元聯(lián)結(jié)詞聯(lián)結(jié)兩個(gè)命題變項(xiàng)(如P、Q)二元聯(lián)結(jié)詞的個(gè)數(shù)命題邏輯的等值和推理演算課件根據(jù)真值表寫(xiě)出各真值函項(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)=P g4(P,Q)=P∧Q g5(P,Q)=(P∧Q)∨(P∧Q)=(P∨P)∧Q=Q g6(P,Q)=PQ (異或式) g7(P,Q)=P∨Q (析取式) g8(P,Q)=P∧Q=PQ (或非式)

g9(P,Q)=PQ (雙條件式) g10(P,Q)=(P∧Q)∨(P∧Q)=(P∨P)∧Q=Q g11(P,Q)=P∨Q=QP (蘊(yùn)涵式) g12(P,Q)=(P∧Q)∨(P∧Q)=P∧(Q∨Q)=P g13(P,Q)=P∨Q=PQ (蘊(yùn)涵式) g14(P,Q)=P∨Q=PQ(與非式) g15(P,Q)=T (永真式)根據(jù)真值表寫(xiě)出各真值函項(xiàng)的命題表達(dá)式:n元聯(lián)結(jié)詞 對(duì)n個(gè)命題變?cè)狿1,…,Pn,每個(gè)Pi有兩種取值,從而對(duì)P1…Pn來(lái)說(shuō)共有2n種取值情形 于是相應(yīng)的真值函項(xiàng)就有22n個(gè),或說(shuō)可定義22n個(gè)n元聯(lián)結(jié)詞n元聯(lián)結(jié)詞的個(gè)數(shù)n元聯(lián)結(jié)詞n元聯(lián)結(jié)詞的個(gè)數(shù)2.4.2聯(lián)結(jié)詞的完備集第二個(gè)問(wèn)題。聯(lián)結(jié)詞是否都是獨(dú)立的，或者說(shuō)能否相互表示?聯(lián)結(jié)詞的完備集定義:設(shè)C是聯(lián)結(jié)詞的集合，如果對(duì)任一命題公式(能直接使用T和F)都有由C中的聯(lián)結(jié)詞表示出來(lái)的公式(不能直接使用T和F)與之等值，就說(shuō)C是完備的聯(lián)結(jié)詞集合，或說(shuō)C是聯(lián)結(jié)詞的完備集。2.4.2聯(lián)結(jié)詞的完備集第二個(gè)問(wèn)題。聯(lián)結(jié)詞是否都是獨(dú)立1.全體聯(lián)結(jié)詞的無(wú)限集合是完備的2.{,∨,∧}是完備的聯(lián)結(jié)詞集合

證明：從2.3節(jié)介紹的由真值表列寫(xiě)邏輯公式的過(guò)程可知,任一公式都可由,∨,∧表示出來(lái),從而{,∨,∧}是完備的3.{,∨}是聯(lián)結(jié)詞的完備集(獨(dú)立的完備集)

證明：P∧Q=(P∨Q)，因此∧可由{,∨}表示4.{,∧}是聯(lián)結(jié)詞的完備集(獨(dú)立的完備集)

證明：P∨Q=(P∧Q)，因此∨可由{,∧}表示完備集1.全體聯(lián)結(jié)詞的無(wú)限集合是完備的完備集5.{,}是完備集(獨(dú)立的完備集) 因?yàn)椋篜∨Q=PQ6.{}是完備集(獨(dú)立的完備集)7.{}是完備集(獨(dú)立的完備集)8.{,∧,∨,,}是完備的

因?yàn)樗?中的集合完備集5.{,}是完備集(獨(dú)立的完備集)完備集{∨,∧,,}不是完備的 因?yàn)镕不能僅由該集合的聯(lián)結(jié)詞表達(dá)出{,}不是完備的{∨,∧,,}的任何子集都是不完備的

{,}的任何子集也是不完備的

(如果一個(gè)聯(lián)結(jié)詞的集合是不完備的，那么它的任何子集都是不完備的){∨,∧}不是完備的不完備集{∨,∧,,}不是完備的不完備集最小的聯(lián)結(jié)詞的完備集—基底基底：完備的聯(lián)結(jié)詞集合的聯(lián)結(jié)詞是獨(dú)立的，也就是說(shuō)這些聯(lián)結(jié)詞不能相互表示任取四個(gè)一元或二元聯(lián)結(jié)詞，它們必組不成基底最小的聯(lián)結(jié)詞的完備集—基底基底：完備的聯(lián)結(jié)詞集合的聯(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--基底只含一個(gè)聯(lián)結(jié)詞的:2.5對(duì)偶式研究目的簡(jiǎn)化等值公式的討論 希望一個(gè)公式成立，能夠?qū)С雠c其“相像”的公式成立邏輯關(guān)系上看，是一種邏輯規(guī)律對(duì)偶式定義：將A中出現(xiàn)的∨、∧、T、F分別以∧、∨、F、T代換,得到公式A*,則稱A*是A的對(duì)偶式,或說(shuō)A和A*互為對(duì)偶式 注：這里假定A中僅出現(xiàn)、∨、∧三個(gè)聯(lián)結(jié)詞若A=B，必有A*=B*?2.5對(duì)偶式研究目的新符號(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－)－=A 定理2.5.3A=A*－(摩根律的另一種形式)更多：(AB)*=A*B*，(AB)-=A-

B-

(AB)*=A*B*，(AB)-=A-B-

對(duì)偶式相關(guān)定理新符號(hào)“-”:(代入規(guī)則、內(nèi)否式)對(duì)偶式相關(guān)定理56性質(zhì)舉例A=(P

(QR))TA*=(P

(QR))FA-=((P)(Q

R))TA*-=((P)(Q

R))FA-*=((P)(Q

R))F56性質(zhì)舉例A=(P(QR))T定理2.5.3A=A*－證明:可用數(shù)學(xué)歸納法,施歸納于A中出現(xiàn)的 聯(lián)結(jié)詞個(gè)數(shù)n來(lái)證明基始:設(shè)n=0,A中無(wú)聯(lián)結(jié)詞,便有

A=P,從而A=P但A*－=P∴n=0時(shí)定理成立。定理2.5.3A=A*－證明:可用數(shù)學(xué)歸納法,施歸納：設(shè)n≤k時(shí)定理成立，來(lái)證n=k+1時(shí)定理也成立 ∵n=k+1≥1,A中至少有一個(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.3A=A*－歸納：設(shè)n≤k時(shí)定理成立，來(lái)證n=k+1時(shí)定理也成立

當(dāng)A=A1時(shí)

A=(A1)A=A1 =(A1*－) 歸納法假設(shè) =(A1)*－

定理2.5.1,2.5.2 =A*－A=A1定理2.5.3A=A*－ 當(dāng)A=A1時(shí)定理2.5.3A=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(摩根律)A=A*－當(dāng) A=A1∧A2時(shí)，定理2.5.3(摩根律)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)成立對(duì)偶式相關(guān)定理定理2.5.6(1)A與A－同永真,同可滿足對(duì)偶式相關(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*對(duì)偶式相關(guān)定理定理2.5.4若A=B，必有A*=B*對(duì)偶式相關(guān)定定理2.5.5若AB永真,必有B*A*永真或者，AB和B*A*同永真證明:(1)如果AB永真，則BA永真(逆否命題)根據(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*)*所以AB永真

?對(duì)偶式相關(guān)定理定理2.5.5若AB永真,必有B*A*永真對(duì)偶式相作業(yè)(2)(P37)

3，4(2)作業(yè)(2)(P37)3，4(2)2.6范式n個(gè)命題變項(xiàng)所能組成的具有不同真值的命題公式僅有22n個(gè),然而與任何一個(gè)命題公式等值而形式不同的命題公式可以有無(wú)窮多個(gè)等值的公式，能否都可以化為某一個(gè)統(tǒng)一的標(biāo)準(zhǔn)形式？希望這種標(biāo)準(zhǔn)形能為我們的討論帶來(lái)些方便，如借助于標(biāo)準(zhǔn)形對(duì)任意兩個(gè)形式上不同的公式，可判斷它們的是否等值借助于標(biāo)準(zhǔn)形容易判斷任一公式是否為重言式或矛盾式2.6范式n個(gè)命題變項(xiàng)所能組成的具有不同真值的命題公式2.6.1范式若干術(shù)語(yǔ)簡(jiǎn)單命題P及其否定式P統(tǒng)稱為文字一些文字的合取稱為合取式一些文字的析取稱為析取式(也稱子句)P與P稱為互補(bǔ)對(duì)析取范式，形如：A1∨A2∨…∨An

其中Ai(i=1,…,n)為合取式合取范式，形如：A1∧A2∧…∧An

其中Ai(i=1,…,n)為析取式2.6.1范式若干術(shù)語(yǔ)67范式舉例p,qp1∨p2,

q1∧q267范式舉例p,q范式定理范式定理：任一命題公式都存在與之等值的析取范式、合取范式求范式三步曲： 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∧P∧Q)∨(P∧?P)∨(P∧?Q)∨(Q∧?P)∨(Q∧?Q)(析取范式)=(P∧?Q)∨(Q∧?P)(析取范式，簡(jiǎn)化)注：范式的不唯一性舉例求?(P∨Q)(P∧Q)的析取范式舉例求?(P∨Q)(P∧Q)的合取范式?(P∨Q)(P∧Q)=(P∧?Q)∨(Q∧?P)(析取范式，簡(jiǎn)化)=(P∨Q)∧(P∨?P)∧(?Q∨Q)∧(?Q∨?P) (合取范式)=(P∨Q)∧(?Q∨?P)(合取范式，簡(jiǎn)化)注：已知一種范式，可以使用分配律求另一種范式舉例求?(P∨Q)(P∧Q)的合取范式判斷重言式 合取范式中所有析取式都有互補(bǔ)對(duì)判斷矛盾式 析取范式中所有合取式都有互補(bǔ)對(duì)判斷兩公式是否等值 范式不唯一，引入唯一的主范式， 便于判別公式相等范式功能判斷重言式范式功能2.6.2主范式主析取范式極小項(xiàng)定義與編碼 Q1∧…∧Qn是由n個(gè)命題變項(xiàng)P1,…,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)的主析取范式極小項(xiàng)必須含有Q1,…,Qn全部n個(gè)文字2.6.2主范式主析取范式極小項(xiàng)必須含有Q1,…,Qn由真值表寫(xiě)主析取范式：從T寫(xiě)

PQ=(?P∧?Q)∨(P∧Q)=m0∨m3=∨0,3由析取范式寫(xiě)主析取范式：填滿命題變項(xiàng)法,永真式

?P=?P∧(Q∨?Q)=(?P∧Q)∨(?P∧?Q) Q=Q∧(P∨?P)=(Q∧P)∨(Q∧?P) P→Q=?P∨Q=(?P∧Q)∨(?P∧?Q)∨(Q∧P)∨(Q∧?P) =(?P∧?Q)∨(?P∧Q)∨(P∧Q) =m0∨m1∨m3 =∨0,1,3主析取范式PQPQm0FFTm1FTFm2TFFm3TTT由真值表寫(xiě)主析取范式：從T寫(xiě)主析取范式PQPQm0FFT所有可能極小項(xiàng)的個(gè)數(shù)：2n每個(gè)極小項(xiàng)只在一個(gè)解釋下為真對(duì)于每個(gè)解釋只有一個(gè)極小項(xiàng)為真

極小項(xiàng)互不相等，且mi∧mj=F(i≠j)任一含有n個(gè)變項(xiàng)的公式，都可由k個(gè)(k≤2n)極小項(xiàng)的析取來(lái)表示；或者說(shuō)所有的極小項(xiàng)可建立一個(gè)“坐標(biāo)系”恰由2n個(gè)極小項(xiàng)的析取構(gòu)成的公式，必為重言式

A與A的主析取范式關(guān)系 A由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)的個(gè)數(shù)：2n極小項(xiàng)性質(zhì)主合取范式極大項(xiàng)定義與編碼

Q1∨

…∨Qn是由n個(gè)命題變項(xiàng)P1,…,Pn組成的公式,其中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è)與之等值的恰僅含這n個(gè)命題變項(xiàng)的主合取范式由真值表寫(xiě)主合取范式(從F寫(xiě))由合取范式寫(xiě)主合取范式(填滿命題變項(xiàng)法,矛盾式)極大項(xiàng)必須含有Q1,…,Qn全部n個(gè)文字主合取范式極大項(xiàng)定義與編碼極大項(xiàng)必須含有Q1,…,Qn全極大項(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)的合取來(lái)表示；或者說(shuō)所有的極大項(xiàng)可建立一個(gè)“坐標(biāo)系”恰由2n個(gè)極大項(xiàng)的合取構(gòu)成的公式，必為矛盾式

A與A的主合取范式關(guān)系 A由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極大項(xiàng)性質(zhì)所有可能極大項(xiàng)的個(gè)數(shù)：2n主析取范式與主合取范式的轉(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=∨({0,1,…,7}-{1,4,5}補(bǔ))

=∨({0,1,…,7}-{6,3,2})

=∨0,1,4,5,7極小項(xiàng)編碼P1P2P3A極大項(xiàng)編碼m0FFFTM７m1FFTTM６m2FTFFM５m3FTTFM４m4TFFTM３m5TFTTM２m6TTFFM１m7TTTTM０主析取范式與主合取范式的轉(zhuǎn)換設(shè)A是由命題變項(xiàng)P1,P2,主析取范式與主合取范式的轉(zhuǎn)換注意從真值表列寫(xiě)公式的主析取范式和主合取范式時(shí)，除了分別從T和F列寫(xiě)外，在填寫(xiě)合取式和析取式時(shí)是取變項(xiàng)還是其否定是有區(qū)別的，這就是主合取范式、主析取范式轉(zhuǎn)換過(guò)程要求補(bǔ)的原因數(shù)字補(bǔ)不同于補(bǔ)集。這里的數(shù)字求補(bǔ)是對(duì)2n-1=23-1=7而言的，如2的補(bǔ)是5，因?yàn)?+5=7主析取范式與主合取范式的轉(zhuǎn)換注意主范式的用途——與真值表相同

(1)求公式的成真賦值和成假賦值例如：(PQ)Rm1m3m5m6m7，其成真指派為001,011,101,110,111，其余的指派000,010,100為成假指派.類(lèi)似地，由主合取范式也可立即求出成假指派和成真指派

主范式的用途——與真值表相同(1)求公式的成真賦值和成假主范式的用途(續(xù))(2)判斷公式的類(lèi)型

設(shè)A含n個(gè)命題變項(xiàng)，則

A為重言式A的主析取范式含2n個(gè)極小項(xiàng)

A的主合取范式為T(mén)A為矛盾式

A的主析取范式為F

A的主合取范式含2n個(gè)極大項(xiàng)A為非重言式的可滿足式A的主析取范式中至少含一個(gè)且不含全部極小項(xiàng)A的主合取范式中至少含一個(gè)且不含全部極大項(xiàng)主范式的用途(續(xù))(2)判斷公式的類(lèi)型主范式的用途(續(xù))判斷兩個(gè)公式是否等值例用主析取范式判斷下述兩個(gè)公式是否等值：⑴P(QR)與(PQ)R⑵P(QR)與(PQ)R解P(QR)=m0m1m2m3m4m5m7(PQ)R=m0m1m2m3m4m5m7(PQ)R=m1m3m4m5m7顯見(jiàn)，⑴中的兩公式等值，而⑵的不等值.主范式的用途(續(xù))判斷兩個(gè)公式是否等值作業(yè)(3)(P37)5(1，5，8)作業(yè)(3)(P37)5(1，5，8)2.7推理形式自然語(yǔ)言推理前提1：如果我今天病了，那么我沒(méi)來(lái)上課前提2：今天我病了結(jié)論：所以今天我沒(méi)來(lái)上課推理形式引入符號(hào),形式化并用條件式表示出來(lái) 例：((PQ)∧P)Q正確的推理形式前提真，結(jié)論必真的推理形式((PQ)∧Q)P正確的推理形式 ((PQ)∧P)Q不正確的推理形式PQPQ2.7推理形式自然語(yǔ)言推理PQPQ重言蘊(yùn)涵重言蘊(yùn)涵對(duì)于公式A,B,如果當(dāng)A取值為真時(shí)，B必取值為真，則稱A重言(永真)蘊(yùn)涵B，或稱B是A的邏輯推論。記為：AB(是真值關(guān)系，并非邏輯聯(lián)結(jié)詞)重言蘊(yùn)涵與正確推理形式如果AB，則AB是正確的推理形式如果AB是正確的推理形式，可以用AB來(lái)表示用真值表法判斷AB查看真值表，如果所有使A為真的解釋，亦能使B為真，則AB重言蘊(yùn)涵重言蘊(yùn)涵

如果AB,A為重言式,則B也是重言式如果AB,BA同時(shí)成立,必有A=B如果A=B,必有AB和BA如果AB,BC,則AC如果AB,AC,則AB∧C如果AC,BC,則A∨B

C重言蘊(yùn)涵的結(jié)果如果AB,A為重言式,則B也是重言式重言蘊(yùn)涵的結(jié)2.8基本的推理公式1.(P∧Q)P 化簡(jiǎn)律2.(PQ)P3.(PQ)

Q4.P(P∨Q) 附加律5.PPQ6.Q

PQ7.(P∨Q)∧PQ 析取三段論8.(PQ)∧PQ 假言推理、分離規(guī)則2.8基本的推理公式1.(P∧Q)P 化簡(jiǎn)律9.(PQ)∧Q

P 拒取式10.(PQ)∧(QR)(PR) 假言三段論、三段論11.(PQ)∧(QR)(PR) 等價(jià)三段論12.(PR)∧(QR)∧(P∨Q)R 構(gòu)造性二難(特殊形式)13.(PQ)∧(RS)∧(P∨R)(Q∨S) 構(gòu)造性二難14.(PQ)∧(RS)∧(Q∨S)(P∨R) 破壞性二難15.(QR)((P∨Q)(P∨R))16.(QR)((PQ)(PR))注：真值表證明，或者語(yǔ)義上直接說(shuō)明基本的推理公式9.(PQ)∧QP 2.8.2證明推理公式的方法(五種)AB成立的充分必要條件是AB(或?A∨B)

為重言式證明：如果A

B,那么在任一解釋下,A真B必真,而不會(huì)出現(xiàn)A真B假的情況,于是AB為重言式。 如果AB為重言式,則在任一解釋下,若A為真,B只能為真不可能為假,從而有A

B證明AB為重言式的方法真值表、等值演算、范式2.8.2證明推理公式的方法(五種)AB成立的充分例1用等值演算法證明(PQ)∧PQ為重言式(PQ)∧PQ?((?P∨Q)∧P)∨Q((P∧?Q)∨?P)∨Q

?Q∨?P∨Q

T

舉例例1用等值演算法證明(PQ)∧PQ為重言式舉例例2用主析取范式法證明(PQ)∧QP不是重言式

(PQ)∧QP?((?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),所以(PQ)∧QP不是重言式，或者說(shuō)推理形式(PQ)∧QP不正確舉例例2用主析取范式法證明(PQ)∧QP不是重言式舉例2.AB成立的充分必要條件是AB為重言式,即A∧?B是矛盾式3.(逆否定理)AB成立的充分必要條件?B?A4.解釋法

例:(PQ)∧(QR)(PR) 若(PQ)∧(QR)＝T,則同時(shí)有PQ＝T,QR=T

若P=T,則Q=T,進(jìn)而R=T.故PR＝T

若P=F,則Q可取任意值: (1)Q=T,則R=T;(2)Q=F,則R取何值

無(wú)論如何,PR=T5.真值表法,即通過(guò)真值表檢驗(yàn)A為真時(shí)B一定為真注：證明AB時(shí)不考慮A為假的情況證明推理公式的方法2.AB成立的充分必要條件是AB為重言式,即A∧?B上述方法的特點(diǎn)都是從真值的角度進(jìn)行論證和解釋看不出由前提A到結(jié)論B的推演過(guò)程難于擴(kuò)展到謂詞邏輯的推演過(guò)程上述方法的特點(diǎn)都是從真值的角度進(jìn)行論證和解釋2.9推理演算(證明推理公式AB的新方法)基本思想：從前提A1,…,An出發(fā)(即A=A1A2…An)運(yùn)用推理規(guī)則和基本推理公式，逐步推演出結(jié)論B，即證明AB推理規(guī)則前提引入規(guī)則 推理過(guò)程中可以隨時(shí)引入前提A1,…,An結(jié)論引用規(guī)則 推理過(guò)程中得到的中間結(jié)論可作為后續(xù)推理的前提代入規(guī)則(參考P8) 推理過(guò)程中對(duì)重言式的命題變項(xiàng)可使用該規(guī)則2.9推理演算(證明推理公式AB的新方法)基本思想：從前推理規(guī)則置換規(guī)則(參考P18) 推理過(guò)程中命題公式中任何部分公式都可由與之等值的公式置換分離規(guī)則(假言推理) 已知命題公式AB和A,則有命題公式B(B被分離出來(lái))條件證明規(guī)則(附加前提)

A1

A2B與A1A2

B是等價(jià)的。即結(jié)論方的條件A2移到了前提方,作為條件使用。推理規(guī)則置換規(guī)則(參考P18)例1證明R是PQ,QR,P的邏輯推論特點(diǎn):前提引入規(guī)則、分離規(guī)則例2證明R∨S可以由前提C∨D,(C∨D)?E,?E(A∧?B),(A∧?B)R∨S推演出來(lái)特點(diǎn):基本推理公式(三段論)例3證明(P∨Q)∧(PR)∧(QS)S∨R特點(diǎn):置換規(guī)則例4證明(P(QS))∧(?R∨P)∧QRS特點(diǎn):條件證明規(guī)則(附加前提引入)例5證明(?(PQ)?(R∨S))∧((QP)∨?R)∧R(PQ)特點(diǎn):反證法、條件證明、結(jié)論引入舉例例1證明R是PQ,QR,P的邏輯推論舉例2.10歸結(jié)推理法(證明推理公式AB的新方法)特點(diǎn)定理機(jī)器證明方法只有一條歸結(jié)推理規(guī)則易于機(jī)器實(shí)現(xiàn)可推廣到謂詞邏輯推理基本思想證明AB等價(jià)于證明AB是矛盾式用反證法,即假設(shè)AB在某種解釋下為真,最后導(dǎo)出矛盾,得以證明2.10歸結(jié)推理法(證明推理公式AB的新方法)特點(diǎn)歸結(jié)證明過(guò)程從AB出發(fā)建立子句集S 將AB化為合取范式,每個(gè)析取式均作為一個(gè)子句,構(gòu)成這些子句的集合,記為S對(duì)S作歸結(jié) 即用歸結(jié)推理規(guī)則消互補(bǔ)對(duì),將得到的新的歸結(jié)式放入S中，重復(fù)此過(guò)程直至歸結(jié)出矛盾,結(jié)束 即出現(xiàn)P與P歸結(jié)證明過(guò)程從AB出發(fā)建立子句集S歸結(jié)推理規(guī)則歸結(jié)式定義

設(shè)R1=P∨Q1,R2=P∨Q2為兩個(gè)子句 有互補(bǔ)對(duì)P和P 則新子句R(R1,R2)=Q1∨Q2稱為R1,R2的歸結(jié)式推理規(guī)則R1R2

R(R1,R2)設(shè)在任一解釋下,R1R2=T,則R1=T且R2=T若P=T,則P=F,Q2=T,R(R1,R2)=Q1∨Q2=T若P=F,則P=T,Q1=T,R(R1,R2)=Q1∨Q2=T若Q1=T或者Q2=T,都有R(R1,R2)=Q1∨Q2=T歸結(jié)推理規(guī)則歸結(jié)式定義舉例證明(PQ)∧(QR)(PR)1.將(PQ)∧(QR)∧?(PR)化成合取范式(?P∨Q)∧(?Q∨R)∧P∧

?R2.建立子句集S={?P∨Q,

?Q∨R,P,?R}3.歸結(jié)過(guò)程(1)?P∨Q (2)?Q∨R (3)P

(4)?R

(5)?P∨R (1)(2)歸結(jié)，新子句(6)R (3)(5)歸結(jié)

(7) (4)(6)歸結(jié)舉例證明(PQ)∧(QR)(PR)作業(yè)(4)(P37)7(10,11),9(1),12(1)作業(yè)(4)(P37)第二章命題邏輯的等值和推理演算

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

由真值表寫(xiě)命題公式(由T寫(xiě)、由F寫(xiě))等值演算(考察邏輯關(guān)系符?(=))等值定理、公式推理演算(考察邏輯關(guān)系符?)推理形式(正確推理形式的表示)基本推理公式(各種三段論及五種證明方法)推理演算(證明推理公式的第六種方法，使用推理規(guī)則)歸結(jié)推理法(證明推理公式的第七種方法，常用反證法)推理演算(考察邏輯關(guān)系符?)推理形式(正確推理形式的表示)2.1等值定理若把初等數(shù)學(xué)里的＋、－、×、÷等運(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等值定理若把初等數(shù)學(xué)里的＋、－、×、÷等運(yùn)算符看2.1.1等值的定義給定兩個(gè)命題公式A和B,而P1…Pn是出現(xiàn)于A和B中的所有命題變項(xiàng),那么公式A和B共有2n個(gè)解釋,若對(duì)其中的任一解釋,公式A和B的真值都相等,就稱A和B是等值的(或等價(jià)的)。記作A=B或AB顯然，可以根據(jù)真值表來(lái)判明任何兩個(gè)公式是否是等值的

2.1.1等值的定義給定兩個(gè)命題公式A和B,而P1…例1:證明(P∧P)∨Q=Q證明:畫(huà)出(P∧P)∨Q與Q的真值表可看出等式是成立的。例1:證明(P∧P)∨Q=Q證明:畫(huà)出(P∧P)例2:證明P∨P=Q∨Q證明:畫(huà)出P∨P,Q∨Q的真值表,可看出它們是等值的,而且它們都是重言式。例2:證明P∨P=Q∨Q證明:畫(huà)出P∨P,Q從例1、2還可說(shuō)明,兩個(gè)公式等值并不一定要求它們一定含有相同的命題變項(xiàng)若僅在等式一端的公式里有變項(xiàng)P出現(xiàn),那么等式兩端的公式其真值均與P無(wú)關(guān)。例1中公式(P∧P)∨Q與Q的真值都同P無(wú)關(guān)例2中P∨P,Q∨Q都是重言式,它們的真值也都與P、Q無(wú)關(guān)。說(shuō)明從例1、2還可說(shuō)明,兩個(gè)公式等值并不一定要求它們一定含有相2.1.2等值定理定理

對(duì)公式A和B,A=B的充分必要條件是AB是重言式。A、B不一定都是簡(jiǎn)單命題,可能是由簡(jiǎn)單命題P1,…,Pn構(gòu)成的.對(duì)A,B的一個(gè)解釋,指的是對(duì)P1,…,Pn的一組具體的真值設(shè)定.若AB為重言式,則在任一解釋下A和B都只能有相同的真值,這就是定理的意思。

2.1.2等值定理定理對(duì)公式A和B,A=B的充分證明若AB是重言式,即在任一解釋下,AB的真值都為T(mén)依AB的定義只有在A、B有相同的值時(shí),才有AB=T。于是在任一解釋下,A和B都有相同的真值,從而有A=B。反過(guò)來(lái)，若有A=B,即在任一解釋下A和B都有相同的真值,依AB的定義,AB只有為真,從而AB是重言式。注：根據(jù)該等值定理，證明兩個(gè)公式等值，只要證明由這兩個(gè)公式構(gòu)成的雙條件式是重言式即可證明若AB是重言式,即在任一解釋下,AB“＝”作為邏輯關(guān)系符是一種等價(jià)關(guān)系不要將“＝”視作聯(lián)結(jié)詞，在合式公式定義里沒(méi)有“＝”出現(xiàn)A=B是表示公式A與B的一種關(guān)系。這種關(guān)系具有三個(gè)性質(zhì):

1.自反性 A=A 2.對(duì)稱性 若A=B,則B=A 3.傳遞性 若A=B,B=C,則A=C這三條性質(zhì)體現(xiàn)了“＝”的實(shí)質(zhì)含義?！埃健弊鳛檫壿嬯P(guān)系符是一種等價(jià)關(guān)系不要將“＝”視作聯(lián)結(jié)詞，在2.2等值公式2.2.1基本的等值公式(命題定律,P和Q是任意的命題公式) 1.雙重否定律

P=P 2.結(jié)合律 (P∨Q)∨R=P∨(Q∨R) (P∧Q)∧R=P∧(Q∧R) (PQ)R=P(QR)

注:所有這些公式，都可使用真值表加以驗(yàn)證2.2等值公式2.2.1基本的等值公式(命題定律,3.交換律

P∨Q=Q∨P P∧Q=Q∧P PQ=QP4.分配律

P∨(Q∧R)=(P∨Q)∧(P∨R) P∧(Q∨R)=(P∧Q)∨(P∧R) P(QR)=(PQ)(PR)5.等冪律(恒等律)

P∨P=P P∧P=P PP=T PP=T3.交換律6.吸收律

P∨(P∧Q)=P P∧(P∨Q)=P7.摩根律

(P∨Q)=P∧Q

(P∧Q)=P∨Q

對(duì)蘊(yùn)涵詞、雙條件詞作否定有

(PQ)=P∧Q

(PQ)=PQ=PQ =(P∧Q)∨(P∧Q)6.吸收律8.同一律

P∨F=P P∧T=P TP=P TP=P

還有

PF=P FP=P8.同一律9.零律

P∨T=T P∧F=F

還有

PT=T FP=T10.補(bǔ)余律

P∨P=T P∧P=F

還有

PP=P

PP=P PP=F9.零律Venn圖(理解等式)將P、Q理解為某總體論域上的子集合，并規(guī)定：P∧Q為兩集合的公共部分(交集合)P∨Q為兩集合的全部(并集合)P為總體論域(如矩形域)中P的余集Venn圖(理解等式)將P、Q理解為某總體論域上的子集合，并Venn圖(理解等式)從Venn圖，因P∧Q較P來(lái)得“小”,P∨Q較P來(lái)得“大”，從而有

P∨(P∧Q)=P P∧(P∨Q)=PVenn圖(理解等式)從Venn圖，因P∧Q較P來(lái)得“小”理解等式:Venn圖，自然語(yǔ)言(P∨Q)=P∧QVenn圖(理解集合間、命題邏輯中、部分信息量間的一些關(guān)系)對(duì)這些等式使用自然用語(yǔ)加以說(shuō)明，將有助于理解如P表示張三是學(xué)生,Q表示李四是工人,那么(P∨Q)就表示并非“張三是學(xué)生或者李四是工人”。這相當(dāng)于說(shuō)，“張三不是學(xué)生而且李四也不是工人”，即可由P∧Q表示,從而有(P∨Q)=P∧Q理解等式:Venn圖，自然語(yǔ)言(P∨Q)=P∧Q2.2.2常用的等值公式由于人們對(duì)、∨、∧更為熟悉，常將含有和的公式化成僅含有、∨、∧的公式。這也是證明和理解含有，的公式的一般方法公式11-18是等值演算中經(jīng)常使用的,也該掌握它們,特別是能直觀地解釋它們的成立2.2.2常用的等值公式由于人們對(duì)、∨、∧更為熟悉，11.PQ=P∨Q通常對(duì)PQ進(jìn)行運(yùn)算時(shí),不如用P∨Q來(lái)得方便。而且以P∨Q表示PQ幫助我們理解如果P則Q的邏輯含義問(wèn)題是這種表示也有缺點(diǎn)，丟失了P、Q間的因果關(guān)系11.PQ=P∨Q12.PQ=QP 逆否定理，假言易位如將PQ視為正定理,那么QP就是相應(yīng)的逆否定理,它們必然同時(shí)為真,同時(shí)為假,所以是等值的12.PQ=QP 逆否定理，假言易位13.P(QR)=(P∧Q)R前提合并P是(QR)的前提,Q是R的前提,于是可將兩個(gè)前提的合取P∧Q作為總的前提。即如果P則如果Q則R,等價(jià)于如果P與Q則R13.P(QR)=(P∧Q)R前提合并14.PQ=(P∧Q)∨(P∧Q)從取真來(lái)描述雙條件這可解釋為PQ為真,有兩種可能的情形,即(P∧Q)為真或(P∧Q)為真。而P∧Q為真,必是在P=Q=T的情況下出現(xiàn);P∧Q為真,必是在P=Q=F的情況下出現(xiàn)。從而可說(shuō),PQ為真,是在P、Q同時(shí)為真或同時(shí)為假時(shí)成立。這就是從取真來(lái)描述這等式14.PQ=(P∧Q)∨(P∧Q)從取真來(lái)描述雙15.PQ=(P∨Q)∧(P∨Q)從取假來(lái)描述雙條件這可解釋為PQ為假,有兩種可能的情形,即(P∨Q)為假或(P∨Q)為假,而P∨Q為假,必是在P=F,Q=T的情況下出現(xiàn);P∨Q為假,必是在P=T,Q=F的情況下出現(xiàn)。從而可說(shuō)PQ為假,是在P真Q假或P假Q(mào)真時(shí)成立。這就是從取假來(lái)描述這等式15.PQ=(P∨Q)∧(P∨Q)從取假來(lái)描述雙16.PQ=(PQ)∧(QP)從蘊(yùn)含詞來(lái)描述雙條件這表明PQ成立,等價(jià)于正定理PQ和逆定理QP都成立16.PQ=(PQ)∧(QP)從蘊(yùn)含詞來(lái)描述雙條17.P(QR)=Q(PR)前提交換前提條件P、Q可交換次序17.P(QR)=Q(PR)前提交換18.(PR)∧(QR)=(P∨Q)R左端說(shuō)明的是由P而且由Q都有R成立。從而可以說(shuō)由P或Q就有R成立,這就是等式右端18.(PR)∧(QR)=(P∨Q)R左端說(shuō)明的是由補(bǔ)充等價(jià)否定等值式 PQ=PQ歸謬論 (PQ)(PQ)=P補(bǔ)充等價(jià)否定等值式2.2.3置換規(guī)則置換定義 對(duì)公式A的子公式,用與之等值的公式來(lái)代換便稱置換置換規(guī)則公式A的子公式置換后A化為公式B,必有A=B當(dāng)A是重言式時(shí),置換后的公式B必也是重言式置換與代入是有區(qū)別的。置換只要求A的某一子公式作代換,不必對(duì)所有同一的子公式都作代換2.2.3置換規(guī)則置換定義代入規(guī)則回顧A是一個(gè)公式，對(duì)A使用代入規(guī)則得公式B，若A是重言式，則B也是重言式為保證重言式經(jīng)代入規(guī)則仍得到保持，要求公式中被代換的只能是命題變?cè)?原子命題),而不能是復(fù)合命題對(duì)公式中某命題變?cè)┮源耄仨殞?duì)該公式中出現(xiàn)的所有同一命題變?cè)鷵Q以同一公式代入規(guī)則回顧A是一個(gè)公式，對(duì)A使用代入規(guī)則得公式B，若A是2.2.4等值演算舉例例1:證明(P∧(Q∧R))∨(Q∧R)∨(P∧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.2.4等值演算舉例例1:證明(P∧(Q∧R)例2:試證((P∨Q)∧(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 舉例例2:試證((P∨Q)