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*中的全部命題變項(xiàng)，將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析取范式與合取范式

文字:命題變項(xiàng)及其否定的總稱簡單析取式:有限個文字構(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)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極小項(xiàng)與極大項(xiàng)

定義

在含有n個命題變項(xiàng)的簡單合取式(簡單析取式)中，若每個命題變項(xiàng)均以文字的形式在其中出現(xiàn)且僅出現(xiàn)一次，而且第i（1in）個文字出現(xiàn)在左起第i位上，稱這樣的簡單合取式（簡單析取式）為極小項(xiàng)（極大項(xiàng)）.說明：n個命題變項(xiàng)產(chǎn)生2n個極小項(xiàng)和2n個極大項(xiàng)2n個極小項(xiàng)（極大項(xiàng)）均互不等值用mi表示第i個極小項(xiàng)，其中i是該極小項(xiàng)成真賦值的十進(jìn)制表示.用Mi表示第i個極大項(xiàng)，其中i是該極大項(xiàng)成假賦值的十進(jìn)制表示,mi(Mi)稱為極小項(xiàng)(極大項(xiàng))的名稱.

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

mi

Mi,Mi

mi

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

公式

成真賦值名稱

公式

成假賦值名稱

p

qp

qp

qp

q00011011m0m1m2m3

p

q

p

q

p

q

p

q

00011011

M0M1M2M3

極小項(xiàng)

極大項(xiàng)

11

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

極小項(xiàng)

極大項(xià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

12主析取范式與主合取范式

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

m1m3

是主析取范式

(pqr)(pqr)

M1M5

是主合取范式

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

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

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

用等值演算法求公式的主范式的步驟：(1)先求析取范式（合取范式）(2)將不是極小項(xiàng)（極大項(xiàng)）的簡單合取式（簡單析取式）化成與之等值的若干個極小項(xiàng)的析?。O大項(xiàng)的合取），需要利用同一律（零律）、排中律（矛盾律）、分配律、冪等律等.

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

14求主析取范式的步驟設(shè)公式A含命題變項(xiàng)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的極小項(xiàng)為止(3)消去重復(fù)出現(xiàn)的極小項(xiàng),即用mi代替mimi(4)將極小項(xiàng)按下標(biāo)從小到大排列15求主合取范式的步驟設(shè)公式A含命題變項(xiàng)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的極大項(xiàng)為止(3)消去重復(fù)出現(xiàn)的極大項(xiàng),即用Mi代替MiMi(4)將極大項(xiàng)按下標(biāo)從小到大排列16快速求法設(shè)公式含有n個命題變項(xiàng),則長度為k的簡單析取式可展開成2nk個極大項(xiàng)的合取例如pr

(pqr)(pqr)

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

q

(pqr)(pqr)(pqr)(pqr)M5M4M1M017實(shí)例例2(1)求A(pq)(pqr)r的主析取范式解用快速求法18實(shí)例例2(1)求A(pq)(pqr)r的主析取范式解用快速求法pq

(pqr)(pqr)m2m3pqrm1r(pqr)(pqr)(pqr)(pqr)m1m3m5m7得Am1m2m3m5m7(1,2,3,5,7)19主合取范式由主析取范式求主合取范式設(shè)沒有出現(xiàn)的極小項(xiàng)是其中t=2ns,于是20主合取范式(續(xù))例6求A=(pqr)(pqr)(pqr)的主合取范式解A

m1m3m7(1,3,7)(0,2,4,5,6)M0M2M4M5M6矛盾式的主合取范式含全部2n個極大項(xiàng)重言式的主合取范式不含任何極大項(xiàng),記作121主范式的用途——與真值表相同

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

例如(pq)r

m1m3m5

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

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

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