Home}目錄§2.1等值式§2.2

析取范式與合取范式第二章命題邏輯等值演算兩公式什么時候代表了同一個命題呢？抽象地看，它們的真假取值完全相同時即代表了相同的命題。設(shè)公式A,B共同含有n個命題變項(xiàng)，可能對A或B有啞元，若A與B有相同的真值表，則說明在2n個賦值的每個賦值下，A與B的真值都相同。于是等價式A

B應(yīng)為重言式。

§2.1等值式1、等值的定義及說明定義2.1設(shè)A,B是兩個命題公式，若A,B構(gòu)成的等價式A

B為重言式,則稱A與B是等值的,記作A

B。說明注意

與

的區(qū)別。A或B中可能有啞元出現(xiàn)。

p→q

(┐p∨q)∨(┐r∧r)

r為左邊公式中的啞元。用真值表可以驗(yàn)證兩個公式是否等值。例2.1判斷下面兩個公式是否等值

┐(p∨q)與┐p∧┐q

解答說明在用真值表法判斷A

B是否為重言式時，真值表的最后一列可以省略。等值例題2.2判斷下列各組公式是否等值

(1)p→(q→r)與(p∧q)→r

(2)(p→q)→r與(p∧q)→r

解答等值不等值2、基本等值式1.雙重否定律

A

┐┐A2.冪等律 A

A∨A, A

A∧A3.交換律 A∨B

B∨A， A∧B

B∧A4.結(jié)合律 (A∨B)∨C

A∨(B∨C)

(A∧B)∧C

A∧(B∧C)5.分配律

A∨(B∧C)

(A∨B)∧(A∨C)

（∨對∧的分配律）

A∧(B∨C)

(A∧B)∨(A∧C)

（∧對∨的分配律）6.德·摩根律

┐(A∨B)

┐A∧┐B

┐(A∧B)

┐A∨┐B

7.吸收律

A∨(A∧B)

A，A∧(A∨B)

A

8.零律

A∨1

1,A∧0

09.同一律

A∨0

A，A∧1

A10.排中律

A∨┐A

111.矛盾律

A∧┐A

012.蘊(yùn)涵等值式

A→B

┐A∨B13.等價等值式

A

B

(A→B)∧(B→A)14.假言易位

A→B

┐B→┐A15.等價否定等值式

A

B

┐A

┐B16.歸謬論

(A→B)∧(A→┐B)

┐A3、對偶原理一個邏輯等值式，如果只含有┐、∨、∧、0、1那么同時 把∨和∧互換

把0和1互換得到的還是等值式。4、等值演算與置換規(guī)則各等值式都是用元語言符號書寫的，其中A,B,C可以代表任意的公式，稱這樣的等值式為等值式模式。每個等值式模式都給出了無窮多個同類型的具體的等值式。

例如，在蘊(yùn)涵等值式A→B

┐A∨B中，

取A=p，B=q時，得等值式p→q

┐p∨q

取A=p∨q∨r，B=p∧q時，得等值式

(p∨q∨r)→(p∧q)

┐(p∨q∨r)∨(p∧q)這些具體的等值式都被稱為原來的等值式模式的代入實(shí)例。由已知的等值式推演出另外一些等值式的過程為等值演算。置換規(guī)則設(shè)Φ(A)是含公式A的命題公式，Φ(B)是用公式B置換了Φ(A)中所有的A后得到的命題公式，若B

A，則Φ(B)

Φ(A)。關(guān)于等值演算的說明等值演算的基礎(chǔ)等值關(guān)系的性質(zhì)：

自反性：A

A。

對稱性：若AB，則BA。

傳遞性：若AB且BC，則AC。基本的等值式置換規(guī)則等值演算的應(yīng)用證明兩個公式等值判斷公式類型解判定問題等值演算的應(yīng)用舉例證明兩個公式等值

(p→q)→r

(p∨r)∧(┐q∨r)(p→q)→r

(┐p∨q)→r

（蘊(yùn)含等值式、置換規(guī)則）

┐(┐p∨q)∨r （蘊(yùn)含等值式、置換規(guī)則）

(p∧┐q)∨r （德摩根律、置換規(guī)則）

(p∨r)∧(┐q∨r) （分配律、置換規(guī)則）說明也可以從右邊開始演算因?yàn)槊恳徊蕉加弥脫Q規(guī)則，故可不寫出熟練后，基本等值式也可以不寫出通常不用等值演算直接證明兩個公式不等值解答例2.3用等值演算法驗(yàn)證等值式

(p∨q)→r

(p→r)∧(q→r)(p→r)∧(q→r)

(┐p∨r)∧(┐q∨r) (蘊(yùn)含等值式)

(┐p∧┐q)∨r (分配律)

┐(p∨q)∨r (德摩根律)

(p∨q)→r (蘊(yùn)含等值式)解答例題2.4

用等值演算判斷下列公式的類型：（1）(p→(p∨q))∧r（2）p∧(((p∨q)∧┐p)→q)（3）(p→q)∧p→q(1)┐(p→(p∨q))∧r

┐(┐p∨p∨q)∧r

(p∧┐p∧┐q)∧r

0∧r

0(2)p∧(((p∨q)∧┐p)→q)p∧(┐((p∨q)∧┐p)∨q)p∧(┐((p∧┐p)∨(q∧┐p))∨q)

p∧(┐(0∨(q∧┐p))∨q)p∧(┐q∨p∨q)

p∧1p解答(3)(p→q)∧p→q

(┐p∨q)∧p→q （蘊(yùn)涵等值式）

┐((┐p∨q)∧p)∨q （蘊(yùn)涵等值式）

(┐(┐p∨q)∨┐p)∨q （德摩根律）

((p∧┐q)∨┐p)∨q （德摩根律）

((p∨┐p)∧(┐q∨┐p))∨q （分配律）

(1∧(┐q∨┐p))∨q （排中律）

(┐q∨q)∨┐p （同一律）

1∨┐p （排中律）

1 （零律）定義1

命題變項(xiàng)及其否定統(tǒng)稱作文字。

僅由有限個文字構(gòu)成的析取式稱作簡單析取式。

僅由有限個文字構(gòu)成的合取式稱作簡單合取式。簡單析取式舉例：

p,┐q p∨┐p，┐p∨q ┐p∨┐q∨r,p∨┐q∨r簡單合取式舉例：

┐p,q ┐p∧p，p∧┐q p∧q∧┐r,┐p∧p∧q§2.2析取范式和合取范式1、簡單析取式與簡單合取式一個文字既是簡單析取式，又是簡單合取式。為討論方便，有時用A1,A2,…,As表示s個簡單析取式或s個簡單合取式。定理1(1)一個簡單析取式是重言式當(dāng)且僅當(dāng)它同時含有某個命題變項(xiàng)及它的否定式。(2)一個簡單合取式是矛盾式當(dāng)且僅當(dāng)它同時含有某個命題變項(xiàng)及它的否定式。定義2(1)由有限個簡單合取式構(gòu)成的析取式稱為析取范式。(2)由有限個簡單析取式構(gòu)成的合取式稱為合取范式。(3)析取范式與合取范式統(tǒng)稱為范式。2、析取范式與合取范式設(shè)Ai(i=1,2,…,s)為簡單合取式，則A=A1∨A2∨…∨As為析取范式。例如，A1=p∧┐q，A2=┐q∧┐r，A3=p，則由A1,A2,A3構(gòu)造的析取范式為

A=A1∨A2∨A3=(p∧┐q)∨(┐q∧┐r)∨p設(shè)Ai(i=1,2,…,s)為簡單析取式，則A=A1∧A2∧…∧As為合取范式。例如，取A1=p∨q∨r，A2=┐p∨┐q，A3=r，則由A1,A2,A3組成的合取范式為

A=A1∧A2∧A3=(p∨q∨r)∧(┐p∨┐q)∧r定理2(1)一個析取范式是矛盾式當(dāng)且僅當(dāng)它的每個簡單合取式都是矛盾式。(2)一個合取范式是重言式當(dāng)且僅當(dāng)它的每個簡單析取式都是重言式。定理3

任一命題公式都存在著與之等值的析取范式與合取范式。3、析取范式和合取范式的性質(zhì)說明研究范式的目的在于，將給定公式化成與之等值的析取范式或合取范式，進(jìn)而將公式化成與之等值的主析取范式或主合取范式。4、求給定公式范式的步驟(1)消去聯(lián)結(jié)詞→、(若存在)。

A→B┐A∨B

A

B(┐A∨B)∧(A∨┐B)(2)否定號的消去(利用雙重否定律)或內(nèi)移(利用德摩根律)。

┐┐AA

┐(A∧B)┐A∨┐B

┐(A∨B)┐A∧┐B(3)利用分配律：利用∧對∨的分配律求析取范式，

∨對∧的分配律求合取范式。

A∧(B∨C)(A∧B)∨(A∧C)

A∨(B∧C)(A∨B)∧(A∨C)例題1

求下面公式的析取范式與合取范式： (p→q)

r

(1)求合取范式(p→q)

r

(┐p∨q)

r

（消去→）

((┐p∨q)→r)∧(r→(┐p∨q))

（消去

）

(┐(┐p∨q)∨r)∧(┐r∨┐p∨q)

（消去→）

((p∧┐q)∨r)∧(┐p∨q∨┐r)

（否定號內(nèi)移）

(p∨r)∧(┐q∨r)∧(┐p∨q∨┐r)（∨對∧分配律）解答(2)求析取范式(p→q)

r

((p∧┐q)∨r)∧(┐p∨q∨┐r)

(p∧┐q∧┐p)∨(p∧┐q∧q)∨(p∧┐q∧┐r) ∨(r∧┐p)∨(r∧q)∨(r∧┐r)

(p∧┐q∧┐r)∨(┐p∧r)∨(q∧r)說明由此例可知，命題公式的析取范式不唯一。同樣，合取范式也是不唯一的。5、范式的規(guī)范化形式定義3

在含有n個命題變項(xiàng)的簡單合取式（簡單析取式）中，若每個命題變項(xiàng)和它的否定式不同時出現(xiàn)，而二者之一必出現(xiàn)且僅出現(xiàn)一次，且第i個命題變項(xiàng)或它的否定式出現(xiàn)在從左算起的第i位上（若命題變項(xiàng)無角標(biāo)，就按字典順序排列），稱這樣的簡單合取式（簡單析取式）為極小項(xiàng)（極大項(xiàng)）。n個命題變項(xiàng)共可產(chǎn)生2n個不同的極小項(xiàng)。其中每個極小項(xiàng)都有且僅有一個成真賦值。若成真賦值所對應(yīng)的二進(jìn)制數(shù)轉(zhuǎn)換為十進(jìn)制數(shù)i，就將所對應(yīng)極小項(xiàng)記作mi

。類似地，n個命題變項(xiàng)共可產(chǎn)生2n個極大項(xiàng)，每個極大項(xiàng)只有一個成假賦值，將其對應(yīng)的十進(jìn)制數(shù)i做極大項(xiàng)的角標(biāo)，記作Mi。表1p,q形成的極小項(xiàng)與極大項(xiàng)

PQP∧QP∧

Q

P∧Q

P∧

Q000110110001

0010

0100

1000PQP∨QP∨

Q

P∨Q

P∨

Q000110110111

1011

1101

1110表2p,q,r形成的極小項(xiàng)與極大項(xiàng)

定理4設(shè)mi與Mi是命題變項(xiàng)p1,p2,…,pn形成的極小項(xiàng)和極大項(xiàng)，則

┐mi

Mi，┐Mi

mi

定義4

設(shè)由n個命題變項(xiàng)構(gòu)成的析取范式（合取范式）中所有的簡單合取式（簡單析取式）都是極小項(xiàng)（極大項(xiàng)），則稱該析取范式（合取范式）為主析取范式（主合取范式）.定理5任何命題公式都存在著與之等值的主析取范式和主合取范式，并且是唯一的。定理5的證明(1)證明存在性。設(shè)A是任一含n個命題變項(xiàng)的公式。由定理2.3可知，存在與A等值的析取范式A′，即A

A′，若A′的某個簡單合取式Ai中既不含命題變項(xiàng)pj，也不含它的否定式┐pj，則將Ai展成如下形式： Ai

Ai∧1

Ai∧(pj∨┐pj)

(Ai∧pj)∨(Aj∧┐pj)繼續(xù)這個過程，直到所有的簡單合取式都含任意命題變項(xiàng)或它的否定式。若在演算過程中出現(xiàn)重復(fù)的命題變項(xiàng)以及極小項(xiàng)和矛盾式時，都應(yīng)“消去”：如用p代替p∧p，mi代替mi∨mi，0代替矛盾式等。最后就將A化成與之等值的主析取范式A''。

(2)證明唯一性。假設(shè)某一命題公式A存在兩個與之等值的主析取范式B和C，即A

B且A

C，則B

C。由于B和C是不同的主析取范式，不妨設(shè)極小項(xiàng)mi只出現(xiàn)在B中而不出現(xiàn)在C中。于是，角標(biāo)i的二進(jìn)制表示為B的成真賦值，而為C的成假賦值。這與B

C矛盾，因而B與C必相同。6、求公式A的主析取范式的方法與步驟方法一、等值演算法(1)化歸為析取范式。(2)除去析取范式中所有永假的析取項(xiàng)。(3)將析取式中重復(fù)出現(xiàn)的合取項(xiàng)和相同的變元合并。(4)對合取項(xiàng)補(bǔ)入沒有出現(xiàn)的命題變元，即添加如(p∨┐p)式，然后應(yīng)用分配律展開公式。方法二、真值表法(1)寫出A的真值表。(2)找出A的成真賦值。(3)求出每個成真賦值對應(yīng)的極小項(xiàng)（用名稱表示），按角標(biāo)從小到大順序析取。方法一、等值演算法(1)化歸為合取范式。(2)除去合取范式中所有永真的合取項(xiàng)。(3)將合取式中重復(fù)出現(xiàn)的析取項(xiàng)和相同的變元合并。(4)對析取項(xiàng)補(bǔ)入沒有出現(xiàn)的命題變元，即添加如(p∧┐p)式，然后應(yīng)用分配律展開公式。方法二、真值表法(1)寫出A的真值表。(2)找出A的成假賦值。(3)求出每個成假賦值對應(yīng)的極大項(xiàng)（用名稱表示），按角標(biāo)從小到大順序析取。7、求公式A的主合取范式的方法與步驟(1)求主合取范式p→q

┐p∨qM2(2)求析取范式p→q

┐p∨q （┐p∧（┐q∨q））∨（(┐p∨p)∧q）

(┐p∧┐q)∨(┐p∧q)∨(┐p∧q)∨(p∧q) (┐p∧┐q)∨(┐p∧q)∨(p∧q) m0∨m1∨m3

解答pqp→q0

01011100111例2求命題公式p→q的主析取范式和主合取范式。例3求的主析取范式和主合取范式。解：(1)列真值表

(2)成真賦值有010，100，101，110，111(3)成假賦值有000，001，011主析取范式為主合取范式為方法一、真值表法方法二、等值演算法主析取范式方法二、等值演算法主合取范式已知一種主范式,求另一種主范式分析:主析取范式中沒有出現(xiàn)的極小項(xiàng)有主合取范式為主析取范式的用途

求公式的成真賦值與成假賦值判斷公式的類型判斷兩個命題公式是否等值應(yīng)用主析取范式分析和解決實(shí)際問題求公式的成真賦值與成假賦值若公式A中含n個命題變項(xiàng)，A的主析取范式含s(0≤s≤2n)個極小項(xiàng)，則A有s個成真賦值，它們是所含極小項(xiàng)角標(biāo)的二進(jìn)制表示，其余2n-s個賦值都是成假賦值。在例2.8中，(p→q)

r

m1∨m3∨m4∨m7,各極小項(xiàng)均含三個文字，因而各極小項(xiàng)的角標(biāo)均為長為3的二進(jìn)制數(shù)，它們分別是001，011，100，111，這四個賦值為該公式的成真賦值,其余的為成假賦值。在例2.9中，p→q

m0∨m1∨m3，這三個極小項(xiàng)均含兩個文字，它們的角標(biāo)的二進(jìn)制表示00，01，11為該公式的成真賦值，10是它的成假賦值。判斷公式的類型設(shè)公式A中含n個命題變項(xiàng)，容易看出：A為重言式當(dāng)且僅當(dāng)A的主析取范式含全部2n個極小項(xiàng)。A為矛盾式當(dāng)且僅當(dāng)A的主析取范式不含任何極小項(xiàng)。此時，記A的主析取范式為0。A為可滿足式當(dāng)且僅當(dāng)A的主析取范式至少含一個極小項(xiàng)。判斷公式的類型例2.10用公式的主析取范式判斷公式的類型：(1)┐(p→q)∧q(2)p→(p∨q)(3)(p∨q)→r解答(1)┐(p→q)∧q

┐（┐p∨q）∧q

(p∧┐q)∧q

0(2)p→(p∨q)m0∨m1∨m2∨m3

(3)(p∨q)→rm0∨m1∨m3∨m5∨m7

矛盾式重言式可滿足式判斷兩個命題公式是否等值設(shè)公式A,B共含有n個命題變項(xiàng)，按n個命題變項(xiàng)求出A與B的主析取范式A‘與B’。若A‘＝B’,則A

B；否則，A與B不等值。例2.11判斷下面兩組公式是否等值：(1)p與(p∧q)∨(p∧┐q)(2)

(p→q)→r與(ｐ∧q)→r(1)p

p∧(┐q∨q)

(p∧┐q)∨(p∧q)

m2∨m3

(p∧q)∨(p∧┐q)

m2∨m3

兩公式等值。(2)(p→q)→r

m1∨m3∨m4∨m5∨m7

(ｐ∧q)→r

m0∨m1∨m2∨m3∨m4∨m5∨m7

兩公式不等值。解答應(yīng)用主析取范式分析和解決實(shí)際問題例2.12某科研所要從3名科研骨干A,B,C中挑選1～2名出國進(jìn)修。由于工作原因，選派時要滿足以下條件：

(1)若A去，則C同去。

(2)若B去，則C不能去。

(3)若C不去，則A或B可以去。

問應(yīng)如何選派他們?nèi)ィ糠治觯?/p>

(1) 將簡單命題符號化 (2) 寫出各復(fù)合命題 (3) 寫出由(2)中復(fù)合命題組成的合取式（前提） (4) 將(3)中公式化成析取式（最好是主析取范式） (5) 這樣每個小項(xiàng)就是一種可能產(chǎn)生的結(jié)果。

去掉不符合題意的小項(xiàng)，即得結(jié)論。應(yīng)用主析取范式分析和解決實(shí)際問題設(shè)p:派A去，q:派B去，r:派C去由已知條件可得公式 (p→r)∧(q→┐r)∧(┐r→(p∨q))經(jīng)過演算可得 (p→r)∧(q→┐r)∧(┐r→(p∨q))m1∨m2∨m5

由于m1=┐p∧┐q∧r,m2=┐p∧q∧┐r,m5=p∧┐q∧r可知，選派方案有3種： (a)C去，而A,B都不去。

(b)B去，而A,C都不去。

(c)A,C去，而B不去。解答由公式的主析取范式求主合取范式設(shè)公式A含n個命題變項(xiàng)。A的主析取范式含s(0<s<2n)個極小項(xiàng)，即沒有出現(xiàn)的極小項(xiàng)設(shè)為它們的角標(biāo)的二進(jìn)制表示為┐A的成真賦值，因而┐A的主析取范式為例2.13由公式的主析取范式，求主合取范式：

(1)A

m1∨m2(A中含兩個命題變項(xiàng)p,q)(2)Bm1∨m2∨m3(B中含兩個命題變項(xiàng)p,q,r)

解答(1)A

M0∧M3

(2)BM0∧M4∧M5∧M6∧M7

重言式與矛盾式的主合取范式設(shè)n為公式中命題變項(xiàng)個數(shù)矛盾式無成真賦值，因而矛盾式的主合取范式含2n個極大項(xiàng)。重言式無成假賦值，因而主合取范式不含任何極大項(xiàng)。將重言式的主合取范式記為1。可滿足式的主合取范式中極大項(xiàng)的個數(shù)一定小于2n。真值表與范式的關(guān)系A(chǔ)

B當(dāng)且僅當(dāng)A與B有相同的真值表，又當(dāng)且僅當(dāng)A與B有相同的主析取范式（主合取范式）。真值表與主析取范式（主合取范式）是描述命題公式標(biāo)準(zhǔn)形式的兩種不同的等價形式。n個命題變項(xiàng)共可產(chǎn)生2n個極小項(xiàng)（極大項(xiàng)）可以產(chǎn)生的主析取范式（主合取范式）數(shù)目為：本章主要內(nèi)容等值式與等值演算。基本的等值式，其中含：雙重否定律、冪等律、交換律、結(jié)合律、分配律、德·摩根律、吸收律、零律、同一律、排中律、矛盾律、蘊(yùn)含等值式、等價等值式、假言易位、等價否定等值式、歸謬論。與主析取范式及主合取范式有關(guān)的概念：簡單合取式、簡單析取式、析取范式、合取范式、極小項(xiàng)、極大項(xiàng)、主析取范式、主合取范式。

本章學(xué)習(xí)要求深刻理解等值式的概念。