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

第二章命題邏輯的等值和推理演算第一頁，共六十五頁，2022年，8月28日等值演算(考察邏輯關(guān)系符)：1)等值定理、公式2)由真值表寫命題公式(由T寫、由F寫)3)聯(lián)結(jié)詞的完備集(由個(gè)別聯(lián)結(jié)詞表示所有聯(lián)結(jié)詞的問題)4)對偶式(命題公式的對偶性)

5)范式(命題公式的統(tǒng)一標(biāo)準(zhǔn))第二頁，共六十五頁，2022年，8月28日推理演算(考察邏輯關(guān)系符)：1)推理形式(正確推理形式的表示)2)基本推理公式(各種三段論及五種證明方法)3)推理演算(證明推理公式的第六種方法，使用推理規(guī)則)4)歸結(jié)推理法(證明推理公式的第七種方法，常用反證法)第三頁，共六十五頁，2022年，8月28日2.1.1等值的定義

等值的定義：給定兩個(gè)命題公式A和B,而P1…Pn是出現(xiàn)于A和B中的所有命題變項(xiàng),那么公式A和B共有2n個(gè)解釋,若對其中的任一解釋,公式A和B的真值都相等,就稱A和B是等值的(或等價(jià)的)。記作A=B或AB。注意邏輯關(guān)系詞2.1等值定理

第四頁，共六十五頁，2022年，8月28日例1:證明(P∧P)∨Q=Q證明:畫出(P∧P)∨Q與Q的真值表可看出等式是成立的。第五頁，共六十五頁，2022年，8月28日例2:證明P∨P=Q∨Q

證明:畫出P∨P,Q∨Q的真值表,可看出它們是等值的,而且它們都是重言式。第六頁，共六十五頁，2022年，8月28日等值定義補(bǔ)充說明：兩個(gè)公式等值并不要求它們一定含有相同的命題變項(xiàng)。若僅在等式一端的公式里有變項(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)。

第七頁，共六十五頁，2022年，8月28日2.1.2等值定理

定理2.1.1對公式A和B,A=B的充分必要條件是AB是重言式。

即任意解釋下，A和B都有相同的真值。證明：定理中的兩部分都與上一行等同。第八頁，共六十五頁，2022年，8月28日“＝”作為邏輯關(guān)系符是一種

等價(jià)關(guān)系A(chǔ)=B是表示公式A與B的一種關(guān)系。這種關(guān)系具有三個(gè)性質(zhì):1.自反性A=A。2.對稱性若A=B則B=A。3.傳遞性若A=B,B=C則A=C。這三條性質(zhì)體現(xiàn)了“＝”的實(shí)質(zhì)含義。

第九頁，共六十五頁，2022年，8月28日2.2等值公式

(真值表驗(yàn)證，Venn圖理解)2.2.1基本的等值公式(特別注意藍(lán)色字) 1.雙重否定律

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

(PQ)R=P(QR)

第十頁，共六十五頁，2022年，8月28日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=T第十一頁，共六十五頁，2022年，8月28日6.吸收律 P∨(P∧Q)=P P∧(P∨Q)=P7.摩根律

(P∨Q)=P∧Q

(P∧Q)=P∨Q

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

(PQ)=P∧Q

(PQ)=PQ=PQ =(P∧Q)∨(P∧Q)第十二頁，共六十五頁，2022年，8月28日8.同一律 P∨F=P P∧T=P TP=P TP=P

還有 PF=P FP=P第十三頁，共六十五頁，2022年，8月28日9.零律 P∨T=T P∧F=F

還有 PT=T FP=T 10.補(bǔ)余律 P∨P=T P∧P=F

還有

PP=P

PP=P PP=F第十四頁，共六十五頁，2022年，8月28日Venn圖這種圖是將P、Q理解為某總體論域上的子集合,而規(guī)定P∧Q為兩集合的公共部分(交集合),P∨Q為兩集合的全部(并集合),P為總體論域(如矩形域)中P的余集。

第十五頁，共六十五頁，2022年，8月28日Venn圖實(shí)例1.P∨(P∧Q)=P 2.P∧(P∨Q)=P3.(P∨Q)=P∧Q第十六頁，共六十五頁，2022年，8月28日Venn圖可以用來理解集合間、命題邏輯中、部分信息量間的一些關(guān)系。第十七頁，共六十五頁，2022年，8月28日2.2.2若干常用的等值公式

等值演算中，由于人們對、∨、∧更為熟悉，常將含有和的公式化成僅含有、∨、∧的公式。這也是證明和理解含有，的公式的一般方法。但后面的推理演算中，更希望見到和.第十八頁，共六十五頁，2022年，8月28日12.逆否定理PQ=QP11.PQ=P∨Q第十九頁，共六十五頁，2022年，8月28日13.前提合并

P(QR)=(P∧Q)R17.前提交換P(QR)=Q(PR)18.另一種前提合并(PR)∧(QR)=(P∨Q)R第二十頁，共六十五頁，2022年，8月28日14.從取真來描述雙條件詞

PQ=(P∧Q)∨(P∧Q)15.從取假來描述雙條件詞

PQ=(P∨Q)∧(P∨Q)16.從蘊(yùn)涵詞描述雙條件詞

PQ=(PQ)∧(QP)第二十一頁，共六十五頁，2022年，8月28日2.2.3置換規(guī)則

(注意與代入規(guī)則p8的區(qū)別)置換定義：對公式A的子公式,用與之等值的公式來代換便稱置換。置換規(guī)則：將公式A的子公式置換后，A化為公式B,必有A=B。置換與代入是有區(qū)別的：代入規(guī)則要求操作重言式、對所有同一命題變元都作代換第二十二頁，共六十五頁，2022年，8月28日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 (同一律)

第二十三頁，共六十五頁，2022年，8月28日例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 (置換規(guī)則)

第二十四頁，共六十五頁，2022年，8月28日問題提出：由命題公式寫真值表是容易的，那么如何由真值表寫命題公式呢？2.3命題公式與真值表關(guān)系第二十五頁，共六十五頁，2022年，8月28日2.3.1從T來列寫1.記憶方法：各項(xiàng)間用∨，每項(xiàng)內(nèi)用∧2.每項(xiàng)內(nèi)書寫方法：例真值表中P=F且Q=F等價(jià)于P∧Q=T3.簡化方法：有時(shí)A的表達(dá)通過A來描述第二十六頁，共六十五頁，2022年，8月28日2.3.2從F來列寫1.記憶方法：各項(xiàng)間用∧

，每項(xiàng)內(nèi)用∨2.每項(xiàng)內(nèi)書寫方法：例真值表中P=T且Q=F等價(jià)于P∨Q=F3.簡化方法：有時(shí)A的表達(dá)通過A來描述4.任意值的問題(圖2.3.1)第二十七頁，共六十五頁，2022年，8月28日2.4聯(lián)結(jié)詞的完備集

問題的提出：對n個(gè)命題變項(xiàng)P1…Pn來說,共可定義出多少個(gè)聯(lián)結(jié)詞?在那么多聯(lián)結(jié)詞中有多少是相互獨(dú)立的?

介紹3個(gè)新型聯(lián)結(jié)詞：

異或

∨:P∨Q=(P∧Q)∨(P∧Q)與非

:PQ=(P∧Q)或非

:PQ=(P∨Q)第二十八頁，共六十五頁，2022年，8月28日2.4.1命題聯(lián)結(jié)詞的個(gè)數(shù)要解決本節(jié)提出的第一個(gè)問題，首先要把n個(gè)命題變項(xiàng)構(gòu)造出的無限多個(gè)合式公式分類。將等值的公式視為同一類，從中選一個(gè)作代表稱之為真值函項(xiàng)。對一個(gè)真值函項(xiàng)，或者說對于該類合式公式，就可定義一個(gè)聯(lián)結(jié)詞與之對應(yīng)。

第二十九頁，共六十五頁，2022年，8月28日例：一元聯(lián)結(jié)詞是聯(lián)結(jié)一個(gè)命題變項(xiàng)(如P)的。P有真假2種值，因此P(自變量)上可定義4種一元聯(lián)結(jié)詞(真值函項(xiàng)、函數(shù))：真值表見圖。 f0 f1 f2 f3或稱 f0(P)f1(P)f2(P)f3(P)第三十頁，共六十五頁，2022年，8月28日由真值表寫出真值函項(xiàng)的命題公式： f0(P)=F f1(P)=P f2(P)=P f3(P)=T第三十一頁，共六十五頁，2022年，8月28日例：二元聯(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)的真值表定義。

第三十二頁，共六十五頁，2022年，8月28日第三十三頁，共六十五頁，2022年，8月28日根據(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)=P g4(P,Q)=P∧Q g5(P,Q)=(P∧Q)∨(P∧Q)=(P∨P)∧Q=Q g6(P,Q)=P∨Q 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 g12(P,Q)=(P∧

Q)∨(P∧Q)=P∧(Q∨Q)=P g13(P,Q)=P∨Q=PQ g14(P,Q)=P∨Q=PQ g15(P,Q)=T第三十四頁，共六十五頁，2022年，8月28日聯(lián)結(jié)詞個(gè)數(shù)統(tǒng)計(jì)：對n個(gè)命題變元P1…Pn,,每個(gè)Pi有兩種取值,從而對P1…Pn來說共有2n種取值情形。于是相應(yīng)的直值函項(xiàng)就有22n個(gè),或說可定義22n個(gè)n元聯(lián)結(jié)詞。第三十五頁，共六十五頁，2022年，8月28日2.4.2聯(lián)結(jié)詞的完備集

關(guān)于本節(jié)提出的第二個(gè)問題，也就是說這些聯(lián)結(jié)詞是否能相互通過組合來表示呢?聯(lián)結(jié)詞的完備集定義:

設(shè)C是聯(lián)結(jié)詞的集合，如果對任一命題公式(能直接使用T和F)都有由C中的聯(lián)結(jié)詞表示出來的公式(不能直接使用T和F)與之等值，就說C是完備的聯(lián)結(jié)詞集合，或說C是聯(lián)結(jié)詞的完備集。第三十六頁，共六十五頁，2022年，8月28日書上的8個(gè)完備集(提問)：1.顯然全體聯(lián)結(jié)詞的無限集合是完備的。

2.定理:{,∨,∧}是完備的聯(lián)結(jié)詞集合。

證明：從2.3節(jié)介紹的由真值表列寫邏輯公式的過程可知,任一公式都可由,∨,∧表示出來,從而{,∨,∧}是完備的。

8.{,∧,∨,,}是完備的,因?yàn)樗?中的集合。另外，{∨,∧,,}不是完備的，因?yàn)镕不能僅由該集合的聯(lián)結(jié)詞表達(dá)出來。{,}也不是完備的。第三十七頁，共六十五頁，2022年，8月28日3.{,∨},4.{,∧}都是聯(lián)結(jié)詞的完備集。證明：P∧Q=(P∨Q) P∨Q=(P∧Q)這說明,∧可由{,∨}表示,∨可由{,∧}表示,故由定理2.4.1可證本結(jié)論。5.{,}是完備集。證明：

6.{}是完備集。證明：

7.{}是完備集。證明：第三十八頁，共六十五頁，2022年，8月28日特別注意如果一個(gè)聯(lián)結(jié)詞的集合是不完備的，那么它的任何子集都是不完備的。因此，{∨,∧,,}的任何子集都是不完備的。{,}的任何子集也是不完備的。由此可推知，集合3,4,5,6,7都是獨(dú)立的完備集。事實(shí)上，6,7是僅有的兩個(gè)只有一個(gè)聯(lián)結(jié)詞的完備集(不證).{∨,∧}不是完備的(不證).第三十九頁，共六十五頁，2022年，8月28日2.5對偶式

新符號“對偶式”：將A中出現(xiàn)的∨、∧、T、F分別以∧、∨、F、T代換,得到公式A*,則稱A*是A的對偶式,或說A和A*互為對偶式。

若A=B必有A*=B*?對僅含、∨、∧三個(gè)聯(lián)結(jié)詞的公式考察相似性第四十頁，共六十五頁，2022年，8月28日新符號“-”：若A=A(P1,…,Pn)令A(yù)－=A(P1,…,Pn)關(guān)于等值的三個(gè)定理(這不是2.1節(jié)的等值定理)定理2.5.1(A*)=(A)*, (A－)=(A)－

定理2.5.2(A*)*=A,(A－)－=A定理2.5.3摩根律

A=A*－可用數(shù)學(xué)歸納法,施歸納于A中出現(xiàn)的聯(lián)結(jié)詞個(gè)數(shù)n來證明。第四十一頁，共六十五頁，2022年，8月28日定理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* 永真故 A*=B*關(guān)于推理的三個(gè)定理第四十二頁，共六十五頁，2022年，8月28日定理2.5.5若AB永真,必有B*A*永真定理2.5.6A與A－同永真,同可滿足

A與A*同永真,同可滿足注意：“A與B同永真,同可滿足”的意思是：A永真可推出B永真,反之亦然。第四十三頁，共六十五頁，2022年，8月28日2.6范式(命題的統(tǒng)一形式)n個(gè)命題變項(xiàng)所能組成的具有不同真值表的命題公式僅有22n個(gè),然而與任何一個(gè)命題公式等值而形式不同的命題公式可以有無窮多個(gè)。這些等值的公式，能否都可以化為某一個(gè)統(tǒng)一的標(biāo)準(zhǔn)形式?第四十四頁，共六十五頁，2022年，8月28日2.6.1范式好多新概念文字、合取式、析取式、互補(bǔ)對、析取范式、合取范式范式定理：任一命題公式都存在與之等值的析取范式、合取范式。求范三步曲：1)消去和2)否定深入到變元3)使用分配律的等值變換第四十五頁，共六十五頁，2022年，8月28日范式功能：判斷兩公式是否等值(參主范式)；判斷重言式：合取范式中所有析取式都有互補(bǔ)對；判斷矛盾式：析取范式中所有合取式都有互補(bǔ)對；第四十六頁，共六十五頁，2022年，8月28日2.6.2主范式主析取范式極小項(xiàng)定義與編碼：主析取范式定義主析取范式唯一性定理由真值表寫主析取范式(從T寫)，例3由析取范式寫主析取范式，例4第四十七頁，共六十五頁，2022年，8月28日極小項(xiàng)性質(zhì)所有極小項(xiàng)的個(gè)數(shù)極小項(xiàng)為真的唯一解極小項(xiàng)互不相同坐標(biāo)系功能A與

A的主析取范式關(guān)系第四十八頁，共六十五頁，2022年，8月28日主合取范式極大項(xiàng)定義：主合取范式定義主合取范式唯一性定理由真值表寫主合取范式(從F寫)，例5由合取范式寫主合取范式，例6第四十九頁，共六十五頁，2022年，8月28日極大項(xiàng)性質(zhì)所有極大項(xiàng)的個(gè)數(shù)極大項(xiàng)為假的唯一解極大項(xiàng)互不相同坐標(biāo)系功能A與

A的主合取范式關(guān)系第五十頁，共六十五頁，2022年，8月28日主析取范式與主合取范式的轉(zhuǎn)化參見板書！！注意補(bǔ)集與數(shù)字補(bǔ)的不同含義。第五十一頁，共六十五頁，2022年，8月28日2.7推理形式1.通過蘊(yùn)涵詞建立正確(即條件真時(shí)，結(jié)論必真)或不正確的推理形式例：((PQ)∧P)Q是正確的推理形式

((PQ)∧Q)P是正確的推理形式

((PQ)∧P)Q是不正確的推理形式第五十二頁，共六十五頁，2022年，8月28日2.正確推理形式的書寫方法使用邏輯關(guān)系詞：重言蘊(yùn)涵AB表示命題A為真時(shí)命題B一定為真3.重言蘊(yùn)涵的進(jìn)一步應(yīng)用(與2.8.1推理公式不同，是一些推理規(guī)則即證明推理公式的方法)第五十三頁，共六十五頁，2022年，8月28日如果AB,A為重言式，則B也是重言式。如果AB，BA同時(shí)成立，必有A=B。如果AB，BC，則AC。如果AB，AC，則AB∧C。如果AC，BC，則AB

C。第五十四頁，共六十五頁，2022年，8月28日2.8基本的推理公式1.(PùQ)

P

化簡律2.?(P?Q)P3.?(P?Q)

?Q4.P

(PúQ)附加律5.?PP?Q6.Q

P?Q7.(PúQ)ù?P

Q

析取三段論8.(P?Q)ùP

Q假言推理、分離規(guī)則注意2、3、5、6的關(guān)系第五十五頁，共六十五頁，2022年，8月28日9.(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)(?Pú?R)破壞性二難15.(Q?R)((PúQ)?(P

úR))16.(Q?R)((P?Q)?(P?R))第五十六頁，共六十五頁，2022年，8月28日2.8.2證明推理公式的5種方法定理2.8.1AB成立的充分必要條件是AB為重言式。注意：2)證明AB為重言式的方法：等值演算、主析取范式、真值表第五十七頁，共六十五頁，2022年，8月28日例1用等值演算法證明(p?q)ùp?q為重言式

(p?q)ùp?q

?

?((?púq)ùp)úq?((pù?q)ú?p)úq

?

?pú?qúq

?T第五十八頁，共六十五頁，2022年，8月28日例2用主析取范式法證明(p?q)ùq?p不是重言式(p?q)ùq?p

?(?púq)ùq?p

?

?((?púq)ùq)úp

?

?qúp

?(?pù?q)ú(pù?q)ú(pù?q)ú(pùq)

?

m0úm2úm3缺少m1即?pùq,所以(p?q)ùq?p不是重言式，或者說推理形式(p?q)ùq?p不正確。第五十九頁，共六十五頁，2022年，8月28日2.定理2.8.2AB