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

11.3命題邏輯等值演算

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

定義若等價式AB是重言式，則稱A與B等值，記作AB，并稱AB是等值式說明：定義中，A,B,均為元語言符號,A或B中可能有啞元出現(xiàn).例如，在(pq)((pq)(rr))中，r為左邊公式的啞元.用真值表可驗證兩個公式是否等值請驗證：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ù))蘊涵等值式:ABAB等價等值式:AB(AB)(BA)假言易位:ABBA等價否定等值式:ABAB歸謬論:(AB)(AB)A注意:A,B,C代表任意的命題公式牢記這些等值式是繼續(xù)學(xué)習(xí)的基礎(chǔ)6等值演算與置換規(guī)則

等值演算:

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

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

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

(2)基本的等值式

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

例1證明

p(qr)(pq)r證

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

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

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

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

說明:也可以從右邊開始演算（請做一遍）因為每一步都用置換規(guī)則，故可不寫出熟練后，基本等值式也可以不寫出

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

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

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

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

例3

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

解q(pq)

q(pq)（蘊涵等值式）

q(pq)（德摩根律）

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

p0（矛盾律）

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

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

(pq)(qp)

(pq)(qp)（蘊涵等值式）

(pq)(pq)（交換律）

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

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

(p(qq))r

（分配律）

p1r

（排中律）

pr

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

析取范式與合取范式

主析取范式與主合取范式

13析取范式與合取范式

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

A1A2Ar,其中A1,A2,,Ar是簡單合取式合取范式:由有限個簡單析取式組成的合取式

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

公式A的析取范式:與A等值的析取范式公式A的合取范式:與A等值的合取范式說明：

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

15命題公式的范式

定理

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

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

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

(3)使用分配律

對分配（析取范式）

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

例

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

（消去）

pqr

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

(pq)r(pq)r

（消去第一個）

(pq)r

（消去第二個）

(pq)r

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

(pq)r

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

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

pq0001101111111111000011110011001101010101

19極小項與極大項

定義

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

進制表示.用Mi表示第i個極大項，其中i是該極大項成

假賦值的十進制表示,mi(Mi)稱為極小項(極大項)的名稱.

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

mi

Mi,Mi

mi

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

公式

成真賦值名稱

公式

成假賦值名稱

p

qp

qp

qp

q00011011m0m1m2m3

p

q

p

q

p

q

p

q

00011011

M0M1M2M3

極小項

極大項

21

由p,q,r三個命題變項形成的極小項與極大項

極小項

極大項

公式

成真賦值名稱

公式

成假賦值名稱

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主析取范式與主合取范式

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

(pqr)(pqr)

m1m3

是主析取范式

(pqr)(pqr)

M1M5

是主合取范式

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

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

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

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

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

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

(2)將不是極小項（極大項）的簡單合取式（簡單析取式）化成與之等值的若干個極小項的析?。O大項的合?。?，需要利用同一律（零律）、排中律（矛盾律）、分配律、冪等律等.

(3)極小項（極大項）用名稱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為成假賦值.

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

設(shè)A含n個命題變項，則

A為重言式A的主析取范式含2n個極小項

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

A的主析取范式為0

A的主合取范式含2n個極大項A為非重言式的可滿足式A的主析取范式中至少含一個且不含全部極小項A的主合取范式中至少含一個且不含全部極大項

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

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

p(qr)與

(pq)r⑵

p(qr)與

(pq)r解

p(qr)=m0m1m2m3

m4m5

m7

(pq)r=m0m1m2m3

m4m5

m7(pq)r=m1m3

m4m5

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

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

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

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

(1)若趙去，錢也去；

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

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

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

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

將簡單命題符號化②

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

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

④

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

33例(續(xù))解

①

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

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