離散數(shù)學(xué)之等值演算

11.3命題邏輯等值演算

等值式基本等值式等值演算置換規(guī)則2等值式

定義若等價(jià)式AB是重言式，則稱(chēng)A與B等值，記作AB，并稱(chēng)AB是等值式說(shuō)明：定義中，A,B,均為元語(yǔ)言符號(hào),A或B中可能有啞元出現(xiàn).例如，在(pq)((pq)(rr))中，r為左邊公式的啞元.用真值表可驗(yàn)證兩個(gè)公式是否等值請(qǐng)驗(yàn)證：p(qr)(pq)rp(qr)(pq)r

3基本等值式

雙重否定律

:AA等冪律：

AAA,AAA交換律:ABBA,ABBA結(jié)合律:(AB)CA(BC)(AB)CA(BC)分配律:A(BC)(AB)(AC)

A(BC)(AB)(AC)4基本等值式(續(xù))德·摩根律:(AB)AB

(AB)AB吸收律:A(AB)A,A(AB)A零律:A11,A00同一律:A0A,

A1A排中律:AA1矛盾律:AA05基本等值式(續(xù))蘊(yùn)涵等值式:ABAB等價(jià)等值式:AB(AB)(BA)假言易位:ABBA等價(jià)否定等值式:ABAB歸謬論:(AB)(AB)A注意:A,B,C代表任意的命題公式牢記這些等值式是繼續(xù)學(xué)習(xí)的基礎(chǔ)6等值演算與置換規(guī)則

等值演算:

由已知的等值式推演出新的等值式的過(guò)程置換規(guī)則：若AB,則(B)(A)

等值演算的基礎(chǔ)：

(1)等值關(guān)系的性質(zhì)：自反、對(duì)稱(chēng)、傳遞

(2)基本的等值式

(3)置換規(guī)則7應(yīng)用舉例——證明兩個(gè)公式等值

例1證明

p(qr)(pq)r證

p(qr)p(qr)（蘊(yùn)涵等值式，置換規(guī)則）(pq)r

（結(jié)合律，置換規(guī)則）(pq)r

（德摩根律，置換規(guī)則）(pq)r

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

說(shuō)明:也可以從右邊開(kāi)始演算（請(qǐng)做一遍）因?yàn)槊恳徊蕉加弥脫Q規(guī)則，故可不寫(xiě)出熟練后，基本等值式也可以不寫(xiě)出

8應(yīng)用舉例——證明兩個(gè)公式不等值例2證明:p(qr)(pq)r

用等值演算不能直接證明兩個(gè)公式不等值,證明兩個(gè)公式不等值的基本思想是找到一個(gè)賦值使一個(gè)成真,另一個(gè)成假.

方法一真值表法（自己證）方法二觀察賦值法.容易看出000,010等是左邊的的成真賦值，是右邊的成假賦值.

方法三用等值演算先化簡(jiǎn)兩個(gè)公式，再觀察.9應(yīng)用舉例——判斷公式類(lèi)型

例3

用等值演算法判斷下列公式的類(lèi)型(1)q(pq)

解q(pq)

q(pq)（蘊(yùn)涵等值式）

q(pq)（德摩根律）

p(qq)（交換律，結(jié)合律）

p0（矛盾律）

0（零律）由最后一步可知，該式為矛盾式.

10例3(續(xù))(2)(pq)(qp)解

(pq)(qp)

(pq)(qp)（蘊(yùn)涵等值式）

(pq)(pq)（交換律）

1由最后一步可知，該式為重言式.問(wèn)：最后一步為什么等值于1？

11例3(續(xù))(3)((pq)(pq))r)解((pq)(pq))r)

(p(qq))r

（分配律）

p1r

（排中律）

pr

（同一律）這不是矛盾式，也不是重言式，而是非重言式的可滿(mǎn)足式.如101是它的成真賦值,000是它的成假賦值.總結(jié)：A為矛盾式當(dāng)且僅當(dāng)A0A為重言式當(dāng)且僅當(dāng)A1說(shuō)明：演算步驟不惟一,應(yīng)盡量使演算短些121.4范式

析取范式與合取范式

主析取范式與主合取范式

13析取范式與合取范式

文字:命題變項(xiàng)及其否定的總稱(chēng)簡(jiǎn)單析取式:有限個(gè)文字構(gòu)成的析取式如p,q,pq,pqr,…簡(jiǎn)單合取式:有限個(gè)文字構(gòu)成的合取式如p,q,pq,pqr,…析取范式:由有限個(gè)簡(jiǎn)單合取式組成的析取式

A1A2Ar,其中A1,A2,,Ar是簡(jiǎn)單合取式合取范式:由有限個(gè)簡(jiǎn)單析取式組成的合取式

A1A2Ar,其中A1,A2,,Ar是簡(jiǎn)單析取式14析取范式與合取范式(續(xù))范式:析取范式與合取范式的總稱(chēng)

公式A的析取范式:與A等值的析取范式公式A的合取范式:與A等值的合取范式說(shuō)明：

單個(gè)文字既是簡(jiǎn)單析取式，又是簡(jiǎn)單合取式pqr,pqr既是析取范式，又是合取范式(為什么?)

15命題公式的范式

定理

任何命題公式都存在著與之等值的析取范式與合取范式.求公式A的范式的步驟：

(1)消去A中的,（若存在）

(2)否定聯(lián)結(jié)詞的內(nèi)移或消去

(3)使用分配律

對(duì)分配（析取范式）

對(duì)分配（合取范式）公式的范式存在，但不惟一16求公式的范式舉例

例

求下列公式的析取范式與合取范式(1)A=(pq)r解(pq)r(pq)r

（消去）

pqr

（結(jié)合律）這既是A的析取范式（由3個(gè)簡(jiǎn)單合取式組成的析取式），又是A的合取范式（由一個(gè)簡(jiǎn)單析取式組成的合取式）17求公式的范式舉例(續(xù))(2)B=(pq)r解

(pq)r(pq)r

（消去第一個(gè)）

(pq)r

（消去第二個(gè)）

(pq)r

（否定號(hào)內(nèi)移——德摩根律）這一步已為析取范式（兩個(gè)簡(jiǎn)單合取式構(gòu)成）繼續(xù)：

(pq)r

(pr)(qr)（對(duì)分配律）這一步得到合取范式（由兩個(gè)簡(jiǎn)單析取式構(gòu)成）

182元真值函數(shù)對(duì)應(yīng)的真值表pq0001101100000000000011110011001101010101

pq0001101111111111000011110011001101010101

19極小項(xiàng)與極大項(xiàng)

定義

在含有n個(gè)命題變項(xiàng)的簡(jiǎn)單合取式(簡(jiǎn)單析取式)中，若每個(gè)命題變項(xiàng)均以文字的形式出現(xiàn)且僅出現(xiàn)一次，稱(chēng)這樣的簡(jiǎn)單合取式(簡(jiǎn)單析取式)為極小項(xiàng)(極大項(xiàng)）.說(shuō)明：n個(gè)命題變項(xiàng)產(chǎn)生2n個(gè)極小項(xiàng)和2n個(gè)極大項(xiàng)2n個(gè)極小項(xiàng)（極大項(xiàng)）均互不等值在極小項(xiàng)和極大項(xiàng)中文字均按下標(biāo)或字母順序排列用mi表示第i個(gè)極小項(xiàng)，其中i是該極小項(xiàng)成真賦值的十

進(jìn)制表示.用Mi表示第i個(gè)極大項(xiàng)，其中i是該極大項(xiàng)成

假賦值的十進(jìn)制表示,mi(Mi)稱(chēng)為極小項(xiàng)(極大項(xiàng))的名稱(chēng).

mi與Mi的關(guān)系:

mi

Mi,Mi

mi

20極小項(xiàng)與極大項(xiàng)(續(xù))由p,q兩個(gè)命題變項(xiàng)形成的極小項(xiàng)與極大項(xiàng)

公式

成真賦值名稱(chēng)

公式

成假賦值名稱(chēng)

p

qp

qp

qp

q00011011m0m1m2m3

p

q

p

q

p

q

p

q

00011011

M0M1M2M3

極小項(xiàng)

極大項(xiàng)

21

由p,q,r三個(gè)命題變項(xiàng)形成的極小項(xiàng)與極大項(xiàng)

極小項(xiàng)

極大項(xiàng)

公式

成真賦值名稱(chēng)

公式

成假賦值名稱(chēng)

pq

rpq

rpq

rpq

rpq

rpq

rpq

rpq

r000001010011100101110111m0m1m2m3m4m5m6m7p

q

r

p

q

r

p

q

r

p

q

r

p

q

r

p

q

r

p

q

r

p

q

r

000001010011100101110111M0M1M2M3M4M5M6M7

22主析取范式與主合取范式

主析取范式:由極小項(xiàng)構(gòu)成的析取范式主合取范式:由極大項(xiàng)構(gòu)成的合取范式例如，n=3,命題變項(xiàng)為p,q,r時(shí)，

(pqr)(pqr)

m1m3

是主析取范式

(pqr)(pqr)

M1M5

是主合取范式

A的主析取范式:與A等值的主析取范式

A的主合取范式:與A等值的主合取范式.

23主析取范式與主合取范式(續(xù))定理

任何命題公式都存在著與之等值的主析取范式和主合取范式,并且是唯一的.

用等值演算法求公式的主范式的步驟：

(1)先求析取范式（合取范式）

(2)將不是極小項(xiàng)（極大項(xiàng)）的簡(jiǎn)單合取式（簡(jiǎn)單析取式）化成與之等值的若干個(gè)極小項(xiàng)的析?。O大項(xiàng)的合?。枰猛宦桑懵桑?、排中律（矛盾律）、分配律、冪等律等.

(3)極小項(xiàng)（極大項(xiàng)）用名稱(chēng)mi（Mi）表示，并按角標(biāo)從小到大順序排序.

24求公式的主范式例

求公式

A=(pq)r的主析取范式與主合取范式.(1)求主析取范式

(pq)r

(pq)r,（析取范式）

①

(pq)

(pq)(rr)(pqr)(pqr)m6m7,②25求公式的主范式(續(xù))r(pp)(qq)r(pqr)(pqr)(pqr)(pqr)

m1m3m5m7

③②,③代入①并排序，得

(pq)r

m1m3m5

m6m7（主析取范式）

26求公式的主范式(續(xù))(2)求A的主合取范式

(pq)r(pr)(qr),（合取范式）

①

pr

p(qq)r

(pqr)(pqr)

M0M2,

②27求公式的主范式(續(xù))

qr

(pp)qr

(pqr)(pqr)

M0M4③

②,③代入①并排序，得

(pq)r

M0M2M4（主合取范式）

28主范式的用途——與真值表相同

(1)求公式的成真賦值和成假賦值

例如(pq)r

m1m3m5

m6m7，其成真賦值為001,011,101,110,111，其余的賦值000,010,100為成假賦值.

類(lèi)似地，由主合取范式也可立即求出成假賦值和成真賦值.29主范式的用途(續(xù))(2)判斷公式的類(lèi)型

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

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

A的主合取范式為1.A為矛盾式

A的主析取范式為0

A的主合取范式含2n個(gè)極大項(xiàng)A為非重言式的可滿(mǎn)足式A的主析取范式中至少含一個(gè)且不含全部極小項(xiàng)A的主合取范式中至少含一個(gè)且不含全部極大項(xiàng)

30主范式的用途(續(xù))例

用主析取范式判斷下述兩個(gè)公式是否等值：⑴

p(qr)與

(pq)r⑵

p(qr)與

(pq)r解

p(qr)=m0m1m2m3

m4m5

m7

(pq)r=m0m1m2m3

m4m5

m7(pq)r=m1m3

m4m5

m7故⑴中的兩公式等值，而⑵的不等值.

(3)判斷兩個(gè)公式是否等值說(shuō)明：由公式A的主析取范式確定它的主合取范式，反之亦然.

用公式A的真值表求A的主范式.31主范式的用途(續(xù))例

某公司要從趙、錢(qián)、孫、李、周五名新畢業(yè)的大學(xué)生中選派一些人出國(guó)學(xué)習(xí).選派必須滿(mǎn)足以下條件：

(1)若趙去，錢(qián)也去；

(2)李、周兩人中至少有一人去；

(3)錢(qián)、孫兩人中有一人去且僅去一人；

(4)孫、李兩人同去或同不去；

(5)若周去，則趙、錢(qián)也去.試用主析取范式法分析該公司如何選派他們出國(guó)？32例(續(xù))解此類(lèi)問(wèn)題的步驟為：①

將簡(jiǎn)單命題符號(hào)化②

寫(xiě)出各復(fù)合命題③

寫(xiě)出由②中復(fù)合命題組成的合取式

④

求③中所得公式的主析取范式

33例(續(xù))解

①

設(shè)p：派趙去，q：派錢(qián)去，r：派孫去，

s：派李去，u：派周去.②(1)(pq)(2)(su)(3)((qr)(qr))(4)((rs)(rs))(5)(u(p