復(fù)試2-離散結(jié)構(gòu)課件

11.5對偶與范式

對偶式與對偶原理

析取范式與合取范式

主析取范式與主合取范式

2對偶式和對偶原理定義

在僅含有聯(lián)結(jié)詞,∧,∨的命題公式A中，將∨換成∧,∧換成∨，若A中含有0或1，就將0換成1，1換成0，所得命題公式稱為A的對偶式，記為A*.從定義不難看出，(A*)*還原成A定理

設(shè)A和A*互為對偶式，p1,p2,…,pn是出現(xiàn)在A和A*中的全部命題變項，將A和A*寫成n元函數(shù)形式，則(1)A(p1,p2,…,pn)

A*(

p1,

p2,…,

pn)(2)A(

p1,

p2,…,

pn)

A*(p1,p2,…,pn)定理（對偶原理）設(shè)A，B為兩個命題公式，若AB，則A*

B*.3析取范式與合取范式

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

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

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

A1A2Ar,其中A1,A2,,Ar是簡單合取式例如:(pq)(pqr)合取范式:由有限個簡單析取式組成的合取式

A1A2Ar

,其中A1,A2,,Ar是簡單析取式例如:(pq)(pqr)范式:析取范式與合取范式的統(tǒng)稱

思考:pqr和pqr是析取范式,還是合取范式?5析取范式與合取范式(續(xù))范式:析取范式與合取范式的總稱

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

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

6命題公式的范式

定理

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

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

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

(3)使用分配律

對分配（析取范式）

對分配（合取范式）公式的范式存在，但不惟一7范式存在定理定理任何命題公式都存在著與之等值的析取范式與合取范式.證求公式A的范式的步驟：(1)消去A中的,ABAB

AB(AB)(BA)

(AB)(AB)8范式存在定理(2)否定聯(lián)結(jié)詞的內(nèi)移或消去 (AB)AB

(AB)ABAA(3)使用分配律

A(BC)(AB)(AC)求合取范式

A(BC)(AB)(AC)求析取范式9范式存在定理(續(xù))例1

求(pq)r的析取范式與合取范式10范式存在定理(續(xù))例1

求(pq)r的析取范式與合取范式解(pq)r

(pq)r(蘊涵等值式)(pq)r(德模根律)(pq)r(雙重否定律)

析取范式11范式存在定理(續(xù))注意:公式的析取范式與合取范式不惟一.(pq)r(pq)r

(pq)(r1)(同一律)(pq)(r(pp))(排中律)(pq)(rp)(rp))(分配律)12極小項與極大項

定義

在含有n個命題變項的簡單合取式(簡單析取式)中，若每個命題變項均以文字的形式在其中出現(xiàn)且僅出現(xiàn)一次，而且第i（1in）個文字出現(xiàn)在左起第i位上，稱這樣的簡單合取式（簡單析取式）為極小項（極大項）.說明：n個命題變項產(chǎn)生2n個極小項和2n個極大項

2n個極小項（極大項）均互不等值用mi表示第i個極小項，其中i是該極小項成真賦值的十進制表示.用Mi表示第i個極大項，其中i是該極大項成假賦值的十進制表示,mi(Mi)稱為極小項(極大項)的名稱.

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

mi

Mi,Mi

mi

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

公式

成真賦值名稱

公式

成假賦值名稱

p

qp

qp

qp

q00011011m0m1m2m3

p

q

p

q

p

q

p

q

00011011

M0M1M2M3

極小項

極大項

14

由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

15主析取范式與主合取范式

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

(pqr)(pqr)

m1m3

是主析取范式

(pqr)(pqr)

M1M5

是主合取范式

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

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

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

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

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

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

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

(3)極小項（極大項）用名稱mi（Mi）表示，并按角標從小到大順序排序.

17求主析取范式的步驟設(shè)公式A含命題變項p1,p2,…,pn(1)求A的析取范式A=B1B2…Bs,其中Bj是簡單合取式j(luò)=1,2,…,s

(2)若某個Bj既不含pi,又不含pi,則將Bj展開成

BjBj(pipi)(Bjpi)(Bjpi)

重復(fù)這個過程,直到所有簡單合取式都是長度為n的極小項為止(3)消去重復(fù)出現(xiàn)的極小項,即用mi代替mimi(4)將極小項按下標從小到大排列18求主合取范式的步驟設(shè)公式A含命題變項p1,p2,…,pn(1)求A的合取范式A=B1B2…Bs,其中Bj是簡單析取式j(luò)=1,2,…,s

(2)若某個Bj既不含pi,又不含pi,則將Bj展開成

BjBj(pipi)(Bjpi)(Bjpi)

重復(fù)這個過程,直到所有簡單析取式都是長度為n的極大項為止(3)消去重復(fù)出現(xiàn)的極大項,即用Mi代替MiMi(4)將極大項按下標從小到大排列19實例例1(續(xù))

求(pq)r的主析取范式與主合取范式解(1)(pq)r

(pq)r

20實例例1(續(xù))

求(pq)r的主析取范式與主合取范式解(1)(pq)r

(pq)r

pq

(pq)1同一律(pq)(rr)排中律

(pqr)(pqr)分配律

m4m5r(pp)(qq)r

同一律,排中律(pqr)(pqr)(pqr)(pqr)m0m2m4m6

分配律得(pq)r

m0m2m4m5m6可記作(0,2,4,5,6)21實例(續(xù))(2)(pq)r

(pr)(qr)

pr

p0r

同一律p(qq)r矛盾律(pqr)(pqr)

分配律M1M3qr

(pp)(qr)

同一律,矛盾律(pqr)(pqr)分配律M3M7得(pq)rM1M3M7可記作(1,3,7)22快速求法設(shè)公式含有n個命題變項,則長度為k的簡單析取式可展開成2nk個極大項的合取例如pr

(pqr)(pqr)

M1M3長度為k的簡單合取式可展開成2nk個極小項的析取例如公式含p,q,r

q

(pqr)(pqr)(pqr)(pqr)M5M4M1M023實例例2(1)求A(pq)(pqr)r的主析取范式解用快速求法24實例例2(1)求A(pq)(pqr)r的主析取范式解用快速求法pq

(pqr)(pqr)m2m3pqrm1r(pqr)(pqr)(pqr)(pqr)m1m3m5m7得Am1m2m3m5m7(1,2,3,5,7)25實例(續(xù))(2)求Bp(pqr)的主合取范式解26實例(續(xù))(2)求Bp(pqr)的主合取范式解p(pqr)(pqr)(pqr)(pqr)M4M5M6M7pqrM1得BM1M4M5M6M7(1,4,5,6,7)27主合取范式由主析取范式求主合取范式設(shè)沒有出現(xiàn)的極小項是其中t=2ns,于是28主合取范式(續(xù))例6

求A=(pqr)(pqr)(pqr)的主合取范式解A

m1m3m7(1,3,7)(0,2,4,5,6)M0M2M4M5M6矛盾式的主合取范式含全部2n個極大項重言式的主合取范式不含任何極大項,記作129實例例5

某單位要從A,B,C三人選派若干人出國考察,需滿足下述條件:(1)若A去,則C必須去;(2)若B去,則C不能去;(3)若C不去,則A或B可以去.問有幾種可能的選派方案?解記p:派A去,q:派B去,r:派C去(1)pr,(2)qr,(3)r(pq)求下式的成真賦值

A=(pr)(qr)(r(pq))30實例(續(xù))求A的主析取范式

A=(pr)(qr)(r(pq))(pr)(qr)(rpq)(蘊涵等值式,雙重否定律)(pqr)(pqr)(矛盾律,分配律)(pqr)(pqr)(矛盾律,分配律)

(pqr) (交換律)M4

M6

M3

M7

M0

(0,3,4,6,7)(1,2,5)成真賦值:001,010,101結(jié)論:方案1派C去,A和B不去;方案2派B去,A和C不去;

方案3派A和C去,B不去.31主范式的用途——與真值表相同

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

例如(pq)r

m1m3m5

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

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

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

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

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

A的主析取范式為0

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

33主范式的用途(續(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的主范式.34主范式的用途(續(xù))

例

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

(1)若趙去，錢也去；

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

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

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

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

將簡單命題符號化②

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

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

④

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

36例(續(xù))解

①

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

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