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

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

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

等值的定義：給定兩個命題公式A和B,而P1…Pn是出現(xiàn)于A和B中的所有命題變項,那么公式A和B共有2n個解釋,若對其中的任一解釋,公式A和B的真值都相等,就稱A和B是等值的(或等價的)。記作A=B或AB。注意邏輯關系詞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日等值定義補充說明：兩個公式等值并不要求它們一定含有相同的命題變項。若僅在等式一端的公式里有變項P出現(xiàn),那么等式兩端的公式其真值均與P無關。例1中公式(P∨P)∨Q與Q的真值都同P無關,例2中P∨P,Q∨Q都是重言式,它們的真值也都與P、Q無關。

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

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

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

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

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

(真值表驗證，Venn圖理解)2.2.1基本的等值公式(特別注意藍色字) 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

對蘊涵詞、雙條件詞作否定有

(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.補余律 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圖實例1.P∨(P∧Q)=P 2.P∧(P∨Q)=P3.(P∨Q)=P∧Q第十六頁，共六十五頁，2022年，8月28日Venn圖可以用來理解集合間、命題邏輯中、部分信息量間的一些關系。第十七頁，共六十五頁，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.從蘊涵詞描述雙條件詞

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命題公式與真值表關系第二十五頁，共六十五頁，2022年，8月28日2.3.1從T來列寫1.記憶方法：各項間用∨，每項內(nèi)用∧2.每項內(nèi)書寫方法：例真值表中P=F且Q=F等價于P∧Q=T3.簡化方法：有時A的表達通過A來描述第二十六頁，共六十五頁，2022年，8月28日2.3.2從F來列寫1.記憶方法：各項間用∧

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

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

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

異或

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

:PQ=(P∧Q)或非

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

第二十九頁，共六十五頁，2022年，8月28日例：一元聯(lián)結(jié)詞是聯(lián)結(jié)一個命題變項(如P)的。P有真假2種值，因此P(自變量)上可定義4種一元聯(lián)結(jié)詞(真值函項、函數(shù))：真值表見圖。 f0 f1 f2 f3或稱 f0(P)f1(P)f2(P)f3(P)第三十頁，共六十五頁，2022年，8月28日由真值表寫出真值函項的命題公式： f0(P)=F f1(P)=P f2(P)=P f3(P)=T第三十一頁，共六十五頁，2022年，8月28日例：二元聯(lián)結(jié)詞聯(lián)結(jié)兩個命題變項(如P、Q)，兩個變項共有4種取值情形,于是P、Q上可建立起16種不同的真值函項,相應的可定義出16個不同的二元聯(lián)結(jié)詞g0,g1,…,g15

圖2.4.2給出了這些聯(lián)結(jié)詞gi或說真值函項gi(P,Q)的真值表定義。

第三十二頁，共六十五頁，2022年，8月28日第三十三頁，共六十五頁，2022年，8月28日根據(jù)真值表寫出各真值函項的命題表達式: 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é)詞個數(shù)統(tǒng)計：對n個命題變元P1…Pn,,每個Pi有兩種取值,從而對P1…Pn來說共有2n種取值情形。于是相應的直值函項就有22n個,或說可定義22n個n元聯(lián)結(jié)詞。第三十五頁，共六十五頁，2022年，8月28日2.4.2聯(lián)結(jié)詞的完備集

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

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

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

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

8.{,∧,∨,,}是完備的,因為它包含了2中的集合。另外，{∨,∧,,}不是完備的，因為F不能僅由該集合的聯(lián)結(jié)詞表達出來。{,}也不是完備的。第三十七頁，共六十五頁，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日特別注意如果一個聯(lián)結(jié)詞的集合是不完備的，那么它的任何子集都是不完備的。因此，{∨,∧,,}的任何子集都是不完備的。{,}的任何子集也是不完備的。由此可推知，集合3,4,5,6,7都是獨立的完備集。事實上，6,7是僅有的兩個只有一個聯(lián)結(jié)詞的完備集(不證).{∨,∧}不是完備的(不證).第三十九頁，共六十五頁，2022年，8月28日2.5對偶式

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

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

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

A=A*－可用數(shù)學歸納法,施歸納于A中出現(xiàn)的聯(lián)結(jié)詞個數(shù)n來證明。第四十一頁，共六十五頁，2022年，8月28日定理2.5.4若A=B必有A*=B*證明:因為A=B等價于AB永真等價于AB永真。依定理2.5.3,A=A*－,B=B*－

于是A*－

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

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

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

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

((PQ)∧P)Q是不正確的推理形式第五十二頁，共六十五頁，2022年，8月28日2.正確推理形式的書寫方法使用邏輯關系詞：重言蘊涵AB表示命題A為真時命題B一定為真3.重言蘊涵的進一步應用(與2.8.1推理公式不同，是一些推理規(guī)則即證明推理公式的方法)第五十三頁，共六十五頁，2022年，8月28日如果AB,A為重言式，則B也是重言式。如果AB，BA同時成立，必有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的關系第五十五頁，共六十五頁，2022年，8月28日9.(P?Q)ù?Q

?P

拒取式10.(P?Q)ù(Q?R)(P?R)假言三段論、三段論11.(P?Q)ù(Q?R)(P?R)等價三段論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