離散數(shù)學(xué)(對偶和范式)

1.5對偶與范式

對偶式與對偶原理

析取范式與合取范式

主析取范式與主合取范式

1離散數(shù)學(xué)(對偶和范式)對偶式和對偶原理定義在僅含有聯(lián)結(jié)詞,∧,∨的命題公式A中，將∨換成∧,∧換成∨，若A中含有0或1，就將0換成1，1換成0，所得命題公式稱為A的對偶式，記為A*.從定義不難看出，(A*)*還原成A顯然，A也是A*的對偶式?？梢夾與A*互為對偶式。2離散數(shù)學(xué)(對偶和范式)對偶式和對偶原理定理

設(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)(1)表明，公式A的否定等價于其命題變元否定的對偶式；(2)表明，命題變元否定的公式等價于對偶式之否定。3離散數(shù)學(xué)(對偶和范式)對偶式和對偶原理定理（對偶原理）設(shè)A，B為兩個命題公式，若AB，則A*

B*.有了等值式、代入規(guī)則、替換規(guī)則和對偶定理，便可以得到更多的永真式，證明更多的等值式，使化簡命題公式更為方便。4離散數(shù)學(xué)(對偶和范式)判定問題真值表等值演算范式5離散數(shù)學(xué)(對偶和范式)析取范式與合取范式

文字:命題變項(xiàng)及其否定的總稱如p,q簡單析取式:有限個文字構(gòu)成的析取式如p,q,pq,pqr,…簡單合取式:有限個文字構(gòu)成的合取式如p,q,pq,pqr,…注意：一個命題變元或其否定既可以是簡單合取式，也可是簡單析取式，如p，q等。6離散數(shù)學(xué)(對偶和范式)析取范式與合取范式

定理：

簡單合取式為永假式的充要條件是：它同時含有某個命題變元及其否定。定理：

簡單析取式為永真式的充要條件是：它同時含有某個命題變元及其否定。7離散數(shù)學(xué)(對偶和范式)析取范式與合取范式

簡單析取式:有限個文字構(gòu)成的析取式如p,q,pq,pqr,…簡單合取式:有限個文字構(gòu)成的合取式如p,q,pq,pqr,…析取范式:由有限個簡單合取式組成的析取式

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

A1A2Ar,其中A1,A2,,Ar是簡單析取式8離散數(shù)學(xué)(對偶和范式)析取范式與合取范式(續(xù))范式:析取范式與合取范式的總稱

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

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

9離散數(shù)學(xué)(對偶和范式)命題公式的范式

定理

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

(1)消去A中的,（若存在）（消去公式中除、和以外公式中出現(xiàn)的所有聯(lián)結(jié)詞）

(2)否定聯(lián)結(jié)詞的內(nèi)移或消去（使用(P)P和德·摩根律）

(3)使用分配律

對分配（析取范式）

對分配（合取范式）公式的范式存在，但不惟一，這是它的局限性

10離散數(shù)學(xué)(對偶和范式)求公式的范式舉例

例

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

（消去）

pqr

（結(jié)合律）這既是A的析取范式（由3個簡單合取式組成的析取式），又是A的合取范式（由一個簡單析取式組成的合取式）11離散數(shù)學(xué)(對偶和范式)求公式的范式舉例(續(xù))(2)B=(pq)r解

(pq)r(pq)r

（消去第一個）

(pq)r

（消去第二個）

(pq)r

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

(pq)r

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

12離散數(shù)學(xué)(對偶和范式)極小項(xiàng)與極大項(xiàng)

定義

在含有n個命題變項(xiàng)的簡單合取式(簡單析取式)中，若每個命題變項(xiàng)均以文字的形式在其中出現(xiàn)且僅出現(xiàn)一次，而且第i（1in）個文字出現(xiàn)在左起第i位上，稱這樣的簡單合取式（簡單析取式）為極小項(xiàng)（極大項(xiàng)）.例如，兩個命題變元p和q，其構(gòu)成的小項(xiàng)有pq，pq，pq和pq；而三個命題變元p、q和r，其構(gòu)成的小項(xiàng)有pqr，pqr，pqr，pqr，pqr

，pqr，pqr，pqr。13離散數(shù)學(xué)(對偶和范式)極小項(xiàng)與極大項(xiàng)

定義

在含有n個命題變項(xiàng)的簡單合取式(簡單析取式)中，若每個命題變項(xiàng)均以文字的形式在其中出現(xiàn)且僅出現(xiàn)一次，而且第i（1in）個文字出現(xiàn)在左起第i位上，稱這樣的簡單合取式（簡單析取式）為極小項(xiàng)（極大項(xiàng)）.例如，由兩個命題變元p和q，構(gòu)成大項(xiàng)有pq，pq，pq，pq；三個命題變元p，q和r，構(gòu)成pqr，pqr，pqr，pqr，pqr，pqr，pqr，pqr。14離散數(shù)學(xué)(對偶和范式)極小項(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)制表示.（將命題變元按字典序排列，并且把命題變元與1對應(yīng)，命題變元的否定與0對應(yīng)，則可對2n個小項(xiàng)依二進(jìn)制數(shù)編碼）

用Mi表示第i個極大項(xiàng)，其中i是該極大項(xiàng)成假賦值的十進(jìn)制表示。（將n個命題變元排序，并且把命題變元與０對應(yīng)，命題變元的否定與１對應(yīng)，則可對2n個大項(xiàng)按二進(jìn)制數(shù)編碼）mi(Mi)稱為極小項(xiàng)(極大項(xiàng))的名稱.

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

mi

Mi,Mi

mi

15離散數(shù)學(xué)(對偶和范式)極小項(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)

16離散數(shù)學(xué)(對偶和范式)

由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

17離散數(shù)學(xué)(對偶和范式)小項(xiàng)的性質(zhì)：(a)沒有兩個小項(xiàng)是等價的，即是說各小項(xiàng)的真值表都是不同的；(b)任意兩個不同的小項(xiàng)的合取式是永假的：mi∧mjＦ，i≠j。(c)所有小項(xiàng)之析取為永真：miＴ。(d)每個小項(xiàng)只有一個解釋為真，且其真值1位于主對角線上。18離散數(shù)學(xué)(對偶和范式)大項(xiàng)的性質(zhì)：(a)沒有兩個大項(xiàng)是等價的。(b)任何兩個不同大項(xiàng)之析取是永真的，即Mi∨MjＴ，i≠j。(c)所有大項(xiàng)之合取為永假，即MiＦ。(d)每個大項(xiàng)只有一個解釋為假，且其真值0位于主對角線上。19離散數(shù)學(xué)(對偶和范式)主析取范式與主合取范式

主析取范式:由極小項(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等值的主合取范式.20離散數(shù)學(xué)(對偶和范式)主析取范式與主合取范式(續(xù))定理

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

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

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

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

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

21離散數(shù)學(xué)(對偶和范式)主析取范式與主合取范式(續(xù))用等值演算法求公式的主范式的步驟：

(1)先求析取范式

(2)刪除析取范式中所有為永假的簡單合取式

(3)用等冪律化簡簡單合取式中同一命題變元的重復(fù)出現(xiàn)為一次出現(xiàn)，如p∧pp。(4)

用同一律補(bǔ)進(jìn)簡單合取式中未出現(xiàn)的所有命題變元，如q，則pp∧（q∨q)，并用分配律展開之，將相同的簡單合取式的多次出現(xiàn)化為一次出現(xiàn)，這樣得到了給定公式的主析取范式。22離散數(shù)學(xué)(對偶和范式)從A的主析取范式求其主合取范式的步驟(a)求出A的主析取范式中設(shè)有包含的小項(xiàng)。

(b)求出與(a)中小項(xiàng)的下標(biāo)相同的大項(xiàng)。

(c)做(b)中大項(xiàng)之合取，即為A的主合取范式。

例如，(pq)qm1m3，則(pq)qM0M2。23離散數(shù)學(xué)(對偶和范式)求公式的主范式例

求公式

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

(pq)r

(pq)r,（析取范式）

①

(pq)

(pq)(rr)(pqr)(pqr)m6m7,②24離散數(shù)學(xué)(對偶和范式)求公式的主范式(續(xù))r(pp)(qq)r(pqr)(pqr)(pqr)(pqr)

m1m3m5m7

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

(pq)r

m1m3m5

m6m7（主析取范式）

25離散數(shù)學(xué)(對偶和范式)求公式的主范式(續(xù))(2)求A的主合取范式

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

①

pr

p(qq)r

(pqr)(pqr)

M0M2,

②26離散數(shù)學(xué)(對偶和范式)求公式的主范式(續(xù))

qr

(pp)qr

(pqr)(pqr)

M0M4③

②,③代入①并排序，得

(pq)r

M0M2M4（主合取范式）

27離散數(shù)學(xué)(對偶和范式)主范式的用途——與真值表相同

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

例如(pq)r

m1m3m5

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

類似地，由主合取范式也可立即求出成假賦值和成真賦值.28離散數(shù)學(xué)(對偶和范式)主范式的用途(續(xù))(2)判斷公式的類型

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

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

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

A的主析取范式為0

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

29離散數(shù)學(xué)(對偶和范式)主范式的用途(續(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的主范式.30離散數(shù)學(xué)(對偶和范式)主范式的用途(續(xù))

例

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

(1)若趙去，錢也去；

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

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

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

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

將簡單命題符號化②

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

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

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

32離散數(shù)學(xué)(對偶和范式)例(續(xù))解

①

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

s：派李去，u：派周去.②(1)(pq)(2)(su)(3)((qr)(qr))(4)((rs)(rs))(5)(u(pq))③(1)~(5)構(gòu)成的合取式為

A=(pq)(su)((qr)(qr))((r