命題邏輯的等值和推理演算第1頁，課件共74頁，創(chuàng)作于2023年2月本章對(duì)命題等值和推理演算進(jìn)行討論，是以語義的觀點(diǎn)進(jìn)行的非形式的描述，不僅直觀且容易理解，也便于實(shí)際問題的邏輯描述和推理。嚴(yán)格的形式化的討論見第三章所建立的公理系統(tǒng)。

第2頁，課件共74頁，創(chuàng)作于2023年2月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

……在命題邏輯里也同樣可建立一些重要的等值式。

第3頁，課件共74頁，創(chuàng)作于2023年2月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。

第4頁，課件共74頁，創(chuàng)作于2023年2月顯然，可以根據(jù)真值表來判明任何兩個(gè)公式是否是等值的。第5頁，課件共74頁，創(chuàng)作于2023年2月例1:證明(P∧P)∨Q=Q證明:畫出(P∧P)∨Q與Q的真值表可看出等式是成立的。第6頁，課件共74頁，創(chuàng)作于2023年2月例2:證明P∨P=Q∨Q證明:畫出P∨P,Q∨Q的真值表,可看出它們是等值的,而且它們都是重言式。第7頁，課件共74頁，創(chuàng)作于2023年2月從例1、2還可說明,兩個(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)。

第8頁，課件共74頁，創(chuàng)作于2023年2月2.1.2等值定理

定理

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

第9頁，課件共74頁，創(chuàng)作于2023年2月證明若AB是重言式,即在任一解釋下,AB的真值都為T。依AB的定義只有在A、B有相同的值時(shí),才有AB=T。于是在任一解釋下,A和B都有相同的真值,從而有A=B。反過來，若有A=B,即在任一解釋下A和B都有相同的真值,依AB的定義,AB只有為真,從而AB是重言式。

第10頁，課件共74頁，創(chuàng)作于2023年2月有了這個(gè)等值定理，證明兩個(gè)公式等值，只要證明由這兩個(gè)公式構(gòu)成的雙條件式是重言式即可。

第11頁，課件共74頁，創(chuàng)作于2023年2月不要將“＝”視作聯(lián)結(jié)詞，在合式公式定義里沒有“＝”出現(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ì)含義。

第12頁，課件共74頁，創(chuàng)作于2023年2月2.2等值公式2.2.1基本的等值公式(命題定律) 1.雙重否定律

P=P 2.結(jié)合律

(P∨Q)∨R=P∨(Q∨R) (P∧Q)∧R=P∧(Q∧R) (PQ)R=P(QR)

第13頁，課件共74頁，創(chuàng)作于2023年2月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第14頁，課件共74頁，創(chuàng)作于2023年2月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)第15頁，課件共74頁，創(chuàng)作于2023年2月8.同一律

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

還有

PF=P FP=P第16頁，課件共74頁，創(chuàng)作于2023年2月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第17頁，課件共74頁，創(chuàng)作于2023年2月所有這些公式，都可使用直值表加以驗(yàn)證。

第18頁，課件共74頁，創(chuàng)作于2023年2月Venn圖若使用Venn圖也容易理解這些等值式,這種圖是將P、Q理解為某總體論域上的子集合,而規(guī)定P∧Q為兩集合的公共部分(交集合),P∨Q為兩集合的全部(并集合),P為總體論域(如矩形域)中P的余集。

第19頁，課件共74頁，創(chuàng)作于2023年2月從Venn圖因P∧Q較P來得“小”,P∨Q較P來得“大”，從而有

P∨(P∧Q)=P P∧(P∨Q)=P第20頁，課件共74頁，創(chuàng)作于2023年2月對(duì)這些等式使用自然用語加以說明，將有助于理解。如P表示張三是學(xué)生,Q表示李四是工人,那么(P∨Q)就表示并非“張三是學(xué)生或者李四是工人”。這相當(dāng)于說，“張三不是學(xué)生而且李四也不是工人”，即可由P∧Q表示,從而有(P∨Q)=P∧Q。

第21頁，課件共74頁，創(chuàng)作于2023年2月2.2.2若干常用的等值公式

由于人們對(duì)、∨、∧更為熟悉，常將含有和的公式化成僅含有、∨、∧的公式。這也是證明和理解含有，的公式的一般方法。公式11-18是等值演算中經(jīng)常使用的,也該掌握它們,特別是能直觀地解釋它們的成立。

第22頁，課件共74頁，創(chuàng)作于2023年2月11.PQ=P∨Q通常對(duì)PQ進(jìn)行運(yùn)算時(shí),不如用P∨Q來得方便。而且以P∨Q表示PQ幫助我們理解如果P則Q的邏輯含義。問題是這種表示也有缺點(diǎn)，丟失了P、Q間的因果關(guān)系。

第23頁，課件共74頁，創(chuàng)作于2023年2月12.PQ=QP 如將PQ視為正定理,那么QP就是相應(yīng)的逆否定理,它們必然同時(shí)為真,同時(shí)為假,所以是等值的。

第24頁，課件共74頁，創(chuàng)作于2023年2月13.P(QR)=(P∧Q)RP是(QR)的前提,Q是R的前提,于是可將兩個(gè)前提的合取P∧Q作為總的前提。

即如果P則如果Q則R,等價(jià)于如果P與Q則R。

第25頁，課件共74頁，創(chuàng)作于2023年2月14.PQ=(P∧Q)∨(P∧Q)

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

第26頁，課件共74頁，創(chuàng)作于2023年2月15.PQ=(P∨Q)∧(P∨Q)

這可解釋為PQ為假,有兩種可能的情形,即(P∨Q)為假或(P∨Q)為假,而P∨Q為假,必是在P=F,Q=T的情況下出現(xiàn),P∨Q為假,必是在P=T,Q=F的情況下出現(xiàn)。從而可說PQ為假,是在P真Q假或P假Q(mào)真

時(shí)成立。這就是從取假來描述這等式

第27頁，課件共74頁，創(chuàng)作于2023年2月16.PQ=(PQ)∧(QP)這表明PQ成立,等價(jià)于正定理PQ和逆定理QP都成立。

第28頁，課件共74頁，創(chuàng)作于2023年2月17.P(QR)=Q(PR)

前提條件P、Q可交換次序。

第29頁，課件共74頁，創(chuàng)作于2023年2月18.(PR)∧(QR)=(P∨Q)R

左端說明的是由P而且由Q都有R成立。從而可以說由P或Q就有R成立,這就是等式右端。第30頁，課件共74頁，創(chuàng)作于2023年2月2.2.3置換規(guī)則

定理:對(duì)公式A的子公式,用與之等值的公式來代換便稱置換。

置換規(guī)則

公式A的子公式置換后A化為公式B,必有A=B。

當(dāng)A是重言式時(shí),置換后的公式B必也是重言式。

置換與代入是有區(qū)別的。置換只要求A的某一子公式作代換,不必對(duì)所有同一的子公式都作代換。

第31頁，課件共74頁，創(chuàng)作于2023年2月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 (同一律)第32頁，課件共74頁，創(chuàng)作于2023年2月例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 第33頁，課件共74頁，創(chuàng)作于2023年2月2.6范式n個(gè)命題變項(xiàng)所能組成的具有不同真值的命題公式僅有22n個(gè),然而與任何一個(gè)命題公式等值而形式不同的命題公式可以有無窮多個(gè)。這樣，首先就要問凡與命題公式A等值的公式，能否都可以化為某一個(gè)統(tǒng)一的標(biāo)準(zhǔn)形式。希望這種標(biāo)準(zhǔn)形能為我們的討論帶來些方便，如借助于標(biāo)準(zhǔn)形對(duì)任意兩個(gè)形式上不同的公式，可判斷它們的是否等值。借助于標(biāo)準(zhǔn)形容易判斷任一公式是否為重言式或矛盾式。第34頁，課件共74頁，創(chuàng)作于2023年2月求解公式的成真指派和成假指派

一個(gè)公式，其中含有命題變?cè)狿1,,Pn,表示為

[P1,,Pn]，（P1,,Pn）稱為變?cè)M，公式的變?cè)M（P1,,Pn）的任意一組確定的值，稱為對(duì)該公式的關(guān)于該變?cè)M（P1,,Pn）的一個(gè)完全指派。如果僅對(duì)變?cè)M中的部分變?cè)_定值，其余變?cè)獩]有賦以確定的值，則稱這樣的一組值為該公式的關(guān)于變?cè)M的一個(gè)部分指派。第35頁，課件共74頁，創(chuàng)作于2023年2月完全指派與部分指派例如公式

：

p(qr)。

變?cè)M為（p，q，r），一個(gè)完全指派為（T，F(xiàn)，F(xiàn)），在此指派下，公式取真值。即

=T?？蛇@樣來表示：（p，q，r）=（T，F(xiàn)，F(xiàn)）├

=T或者有時(shí)記為：

（p，q，r）=（T，F(xiàn)，F(xiàn)）

=T

一個(gè)部分指派為（T，T，╳）這時(shí)候

的值不能確定，當(dāng)r=T時(shí)，

=T，當(dāng)r=F時(shí)，=F。這一點(diǎn)通常都能理解，因?yàn)橐粋€(gè)公式的值取決于公式中所含變?cè)闹?，?dāng)其中某些變?cè)创_定時(shí)，公式最終的值也不能定。但是這一點(diǎn)也未必絕對(duì)，例如，賦（p，q，r）以（F，X，X）時(shí)，公式肯定是取假值，即=F。這時(shí)候可看出對(duì)q，r的指派已經(jīng)無關(guān)緊要了。第36頁，課件共74頁，創(chuàng)作于2023年2月成真指派與成假指派定義：對(duì)于任一公式，凡是使得

取真值

=T的指派，不管是完全指派還是部分指派，都稱為

的成真指派。凡是使

取假值

=F的指派，不管是完全指派還是部分指派，都稱為

的成假指派。

第37頁，課件共74頁，創(chuàng)作于2023年2月例子：P的成真指派

P=F,成假指派P=T。：PQ的成真指派（P，Q）=（T，T）

成假指派（P，Q）=（F，F(xiàn)），（F，T），（T，F(xiàn)）：PQ的成真指派（P，Q）=（T，T），（T，F(xiàn)），（F，T）

成假指派（P，Q）=（F，F(xiàn)）第38頁，課件共74頁，創(chuàng)作于2023年2月永真式、永假式、可滿足式有的公式?jīng)]有成真指派，如：PP,稱為永假式（反駁式）；有的公式?jīng)]有成假指派，如：PP,稱為永真式（重言式）。永假式，又稱為矛盾式，不可滿足。如果一個(gè)公式，有成真指派，則稱為公式

可滿足。與它相對(duì)的，如果沒有成真指派，就是不可滿足的。如果一個(gè)公式，有成假指派，則稱該公式為非永真公式。第39頁，課件共74頁，創(chuàng)作于2023年2月部分指派公式

的變?cè)M（P1,,Pn），一個(gè)部分指派

：（V1,Vi-1,X,Vi+1,Vn），其中Vi為具體真假值。它為公式

的成真指派，當(dāng)且僅當(dāng)：（V1,Vi-1,T,Vi+1,Vn）及（V1,Vi-1,F,Vi+1,Vn）均為成真指派。成假指派情況是相似的。第40頁，課件共74頁，創(chuàng)作于2023年2月求解成真指派和成假指派的方法一個(gè)直截了當(dāng)?shù)霓k法是將公式

的所有完全指派全都列舉出來，逐個(gè)驗(yàn)算該指派下

取的真假值，從而確定每個(gè)完全指派是成真指派還是成假指派。但是，含n個(gè)變?cè)墓剑灿?n個(gè)完全指派，當(dāng)n為5、6、……時(shí)，指數(shù)的總數(shù)就會(huì)相當(dāng)可觀，按指數(shù)級(jí)數(shù)增長(zhǎng)，難以全部枚舉。因此應(yīng)當(dāng)選擇更為簡(jiǎn)單、可行的辦法——部分指派。求部分指派的前提是將原來的公式

化簡(jiǎn)，使得原來含有n個(gè)變?cè)墓交癁榭赡芎冊(cè)獢?shù)更少的公式，于是便大大地削減了運(yùn)算的數(shù)量。第41頁，課件共74頁，創(chuàng)作于2023年2月部分指派的步驟第一步，否定深入。將外層的否定深入到內(nèi)層，一直深入到變?cè)獮橹?。第二步，部分指派。選定一個(gè)變?cè)獙?duì)其作真和假兩種指派，得到兩個(gè)不含該變?cè)^原式簡(jiǎn)單的公式。如果這兩個(gè)公式直接得到真假值，則得部分指派，否則第三步，化簡(jiǎn)。得到的兩公式雖然較原公式簡(jiǎn)單，但仍含有變?cè)?，于是重?fù)第二步，逐個(gè)減少變?cè)钡酱_定真假值為止。第二步中如何選定一個(gè)變?cè)?，希望化?jiǎn)效果最好，因此選擇在公式中出現(xiàn)次數(shù)最多的變?cè)髦概伞＿€有一種情況就是對(duì)該變?cè)x以一個(gè)指派后，立即使整個(gè)公式有確定的真假值。第42頁，課件共74頁，創(chuàng)作于2023年2月試求給定公式的成真成假指派：(p

r)

((pq)

(p

(qr)))第一步

否定深入：

(p

r)((pq)(p(q

r)))第二步

部分指派：選擇出現(xiàn)最多的命題，指派以T,F。（分別情況）。

上式中，P出現(xiàn)最多，故

分為

p=T

p=F兩種情況。第43頁，課件共74頁，創(chuàng)作于2023年2月

p=T

：(T

r)（（Tq）（T(q

r)））

化簡(jiǎn)(q(q

r))也可最終化簡(jiǎn)為r，

p=F

：(F

r)（（Fq）（F(q

r)））

化簡(jiǎn)得

r

（TF）最終化簡(jiǎn)得r組合起來，的成真指派（p,q,r）=(T,X,F),(F,X,T),

成假指派（p,q,r）=(T,X,T),(F,X,F)。第44頁，課件共74頁，創(chuàng)作于2023年2月不完全成真指派

(p,q,r):(T,X,F)可以生成相應(yīng)的完全成真指派

(T,T,F)和

(T,F,F)。

(p,q,r):(F,X,T)(F,T,T)和

(F,F,T)。因此，寫完整的話，的完全成真指派：

(T,T,F)，(T,F,F)，(F,T,T)，(F,F,T)。相仿地，的完全成假指派：

(T,X,T)(T,T,T)，(T,F,T)，

(F,X,F)(F,T,F)，(F,F,F)完全成假指派：(T,T,T)，(T,F,T)，(F,T,F)，(F,F,F)。

第45頁，課件共74頁，創(chuàng)作于2023年2月析取范式如果一個(gè)完全指派能使一個(gè)合取式取真值，那么這個(gè)完全指派和合取式之間是１－１對(duì)應(yīng)的。例如：

(T,T,F)，(T,F,F)，

(F,T,T)，

(F,F,T)pq

rp

q

rpqrp

qr

將上述四個(gè)合取式再析取，即得析取范式：（pq

r）（p

q

r）（pqr）（p

qr）第46頁，課件共74頁，創(chuàng)作于2023年2月合取范式相仿地：對(duì)應(yīng)于成假指派對(duì)應(yīng)的析取式為：(T,T,T)，(T,F,T)，(F,T,F)，(F,F,F)pqr

pqr

pqr

pqr將四個(gè)析取式再合取，即得合取范式：（pqr）（pqr）（pqr）（pqr）第47頁，課件共74頁，創(chuàng)作于2023年2月求范式等值變換法消去和否定深入到變?cè)戎底儞Q第48頁，課件共74頁，創(chuàng)作于2023年2月主范式主析取范式主合取范式第49頁，課件共74頁，創(chuàng)作于2023年2月2.4聯(lián)結(jié)詞的完備集

除了所詳述過的五個(gè)聯(lián)結(jié)詞外,還可定義更多的聯(lián)結(jié)詞。像計(jì)算機(jī)的硬件電路設(shè)計(jì)分析就常使用

異或(半加)

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

與非:PQ=(P∧Q)

或非:PQ=(P∨Q)等聯(lián)結(jié)詞。

問題是對(duì)n個(gè)命題變項(xiàng)P1…Pn

來說,共可定義出多少個(gè)聯(lián)結(jié)詞?還可以問,在那么多聯(lián)結(jié)詞中有多少是獨(dú)立的?第50頁，課件共74頁，創(chuàng)作于2023年2月2.4.1命題聯(lián)結(jié)詞的個(gè)數(shù)按照合式公式的定義，由命題變項(xiàng)和命題聯(lián)結(jié)詞可以構(gòu)造出無限多個(gè)合式公式?？砂阉械暮鲜焦郊右苑诸?/p>

，將等值的公式視為同一類，從中選一個(gè)作代表稱之為真值函項(xiàng)。對(duì)一個(gè)真值函項(xiàng)就有一個(gè)聯(lián)結(jié)詞與之對(duì)應(yīng)。

第51頁，課件共74頁，創(chuàng)作于2023年2月一元聯(lián)結(jié)詞是聯(lián)結(jié)一個(gè)命題變項(xiàng)的，如P。它取值只有真假兩種情形，于是聯(lián)結(jié)詞作用于P,可建立四種不同的真值函項(xiàng),相應(yīng)的可定義出四個(gè)不同的一元聯(lián)結(jié)詞f0f1f2f3。圖6.2.4.1給出這些聯(lián)結(jié)詞fi或說真值函數(shù)fi(P)的定義。

第52頁，課件共74頁，創(chuàng)作于2023年2月寫出真值函項(xiàng)：

f0(P)=F f1(P)=P f2(P)=P f3(P)=T其中f0(P)是永假式,f3(P)是永真式,均與P無關(guān),而f1(P)就是變項(xiàng)P本身,從而新的公式只有f2(P),這就是由否定詞所建立的真值函項(xiàng)。

第53頁，課件共74頁，創(chuàng)作于2023年2月二元聯(lián)結(jié)詞聯(lián)結(jié)兩個(gè)命題變項(xiàng)，兩個(gè)變項(xiàng)PQ共有四種取值情形,于是聯(lián)結(jié)詞作用于PQ可建立起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)的定義。

第54頁，課件共74頁，創(chuàng)作于2023年2月第55頁，課件共74頁，創(chuàng)作于2023年2月寫出各真值函項(xiàng): 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第56頁，課件共74頁，創(chuàng)作于2023年2月一般地說，對(duì)n個(gè)命題變?cè)狿1…Pn,,每個(gè)Pi有兩種取值,從而對(duì)P1…Pn來說共有2n種取值情形。于是相應(yīng)的直值函項(xiàng)就有22n個(gè),或說可定義22n個(gè)n元聯(lián)結(jié)詞。第57頁，課件共74頁，創(chuàng)作于2023年2月2.4.2聯(lián)結(jié)詞的完備集

由于可定義的聯(lián)結(jié)詞的數(shù)量是極大的,需要考慮它們是否都是獨(dú)立的?也就是說這些聯(lián)結(jié)詞是否能相互表示呢?定義:設(shè)C是聯(lián)結(jié)詞的集合，如果對(duì)任一命題公式都有由C中的聯(lián)結(jié)詞表示出來的公式與之等值，就說C是完備的聯(lián)結(jié)詞集合，或說C是聯(lián)結(jié)詞的完備集。

第58頁，課件共74頁，創(chuàng)作于2023年2月顯然全體聯(lián)結(jié)詞的無限集合是完備的,而{∨},{∨,∧}就不是完備的。

定理

{,∨,∧}是完備的聯(lián)結(jié)詞集合

從節(jié)2.3介紹的由真值表列寫邏輯公式的過程可知,任一公式都可由,∨,∧表示出來,從而{,∨,∧}是完備的,一般情形下,這定理的證明可使用數(shù)學(xué)歸納法,施歸納于聯(lián)結(jié)詞的個(gè)數(shù)來論證。

第59頁，課件共74頁，創(chuàng)作于2023年2月又由于

P∧Q=(P∨Q) P∨Q=(P∧Q)這說明,∧可由{,∨}表示,∨可由{,∧}表示,故{,∨},{,∧}都是聯(lián)結(jié)詞的完備集。還可證明{,},{},{}也都是聯(lián)結(jié)詞的完備集。但{∨,∧},{,}不是完備的。

盡管{,∨},{,∧}是完備的,但使用起來并不夠方便,我們?cè)敢獠扇≌壑苑桨?不是僅用兩個(gè)也不是使用過多的聯(lián)結(jié)詞,還是選用詳細(xì)討論過的五個(gè)聯(lián)結(jié)詞集{,∧,∨,,},當(dāng)然是完備的,只是相互并不獨(dú)立。

第60頁，課件共74頁，創(chuàng)作于2023年2月最小的聯(lián)結(jié)詞的完備集——基底

基底：完備的聯(lián)結(jié)詞集合的聯(lián)結(jié)詞是獨(dú)立的，

也就是說這些聯(lián)結(jié)詞不能相互表示第61頁，課件共74頁，創(chuàng)作于2023年2月基底

只含一個(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--第62頁，課件共74頁，創(chuàng)作于2023年2月基底

任取四個(gè)一元或二元聯(lián)結(jié)詞，它們必組不成基底。第63頁，課件共74頁，創(chuàng)作于2023年2月加法器

Ai00001111Bi00110011Ei01010101_______________________Ci01101001Ei+100010111Ci=(Ai∧Bi∧Ei)∨(Ai∧Bi∧Ei)∨(Ai∧Bi∧Ei)∨(Ai∧Bi∧Ei)Ei+1=(Ai∧Bi∧Ei)∨(Ai∧Bi∧Ei)∨(Ai∧Bi∧Ei)∨(Ai∧Bi∧Ei)E1=0Cn+1=En+1第64頁，課件共74頁，創(chuàng)作于2023年2月2.5對(duì)偶式

假定公式A僅出現(xiàn)、∨、∧這三個(gè)聯(lián)結(jié)詞定義

將A中出現(xiàn)的∨、∧分別以∧、∨代換,得到公式A*,則稱A*是A的對(duì)偶式,或說A和A*互為對(duì)偶式。

(P∨Q)∧R 的對(duì)偶式為(P∧Q)∨R不難知道,若(P∨Q)∧R=(P∧R)∨(Q∧R)成立,相應(yīng)的對(duì)偶式

(P∧Q)∨R=(P∨R)∧(Q∨R)也成立。第65頁，課件共74頁，創(chuàng)作于2023年2月為方便,若A=A(P1,…,Pn)

令

A－=A(P1,…,Pn)定理2.5.1(A*)=(A*),(A－)=(A)－

定理2.5.2(A*)*=A,(A－)－=A定理