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

關(guān)于離散數(shù)學(xué)對(duì)偶和范式第1頁(yè)，講稿共35頁(yè)，2023年5月2日，星期三2對(duì)偶式和對(duì)偶原理定義

在僅含有聯(lián)結(jié)詞,∧,∨的命題公式A中，將∨換成∧,∧換成∨，若A中含有0或1，就將0換成1，1換成0，所得命題公式稱為A的對(duì)偶式，記為A*.從定義不難看出，(A*)*還原成A顯然，A也是A*的對(duì)偶式?？梢?jiàn)A與A*互為對(duì)偶式。第2頁(yè)，講稿共35頁(yè)，2023年5月2日，星期三3對(duì)偶式和對(duì)偶原理定理

設(shè)A和A*互為對(duì)偶式，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的否定等價(jià)于其命題變?cè)穸ǖ膶?duì)偶式；(2)表明，命題變?cè)穸ǖ墓降葍r(jià)于對(duì)偶式之否定。第3頁(yè)，講稿共35頁(yè)，2023年5月2日，星期三4對(duì)偶式和對(duì)偶原理定理（對(duì)偶原理）設(shè)A，B為兩個(gè)命題公式，若AB，則A*

B*.有了等值式、代入規(guī)則、替換規(guī)則和對(duì)偶定理，便可以得到更多的永真式，證明更多的等值式，使化簡(jiǎn)命題公式更為方便。第4頁(yè)，講稿共35頁(yè)，2023年5月2日，星期三5判定問(wèn)題真值表等值演算范式第5頁(yè)，講稿共35頁(yè)，2023年5月2日，星期三6析取范式與合取范式

文字:命題變項(xiàng)及其否定的總稱如p,q簡(jiǎn)單析取式:有限個(gè)文字構(gòu)成的析取式如p,q,pq,pqr,…簡(jiǎn)單合取式:有限個(gè)文字構(gòu)成的合取式如p,q,pq,pqr,…注意：一個(gè)命題變?cè)蚱浞穸瓤梢允呛?jiǎn)單合取式，也可是簡(jiǎn)單析取式，如p，q等。第6頁(yè)，講稿共35頁(yè)，2023年5月2日，星期三7析取范式與合取范式

定理：

簡(jiǎn)單合取式為永假式的充要條件是：它同時(shí)含有某個(gè)命題變?cè)捌浞穸?。定理?/p>

簡(jiǎn)單析取式為永真式的充要條件是：它同時(shí)含有某個(gè)命題變?cè)捌浞穸ā５?頁(yè)，講稿共35頁(yè)，2023年5月2日，星期三8析取范式與合取范式

簡(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)單析取式第8頁(yè)，講稿共35頁(yè)，2023年5月2日，星期三9析取范式與合取范式(續(xù))范式:析取范式與合取范式的總稱

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

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

第9頁(yè)，講稿共35頁(yè)，2023年5月2日，星期三10命題公式的范式

定理

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

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

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

(3)使用分配律

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

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

第10頁(yè)，講稿共35頁(yè)，2023年5月2日，星期三11求公式的范式舉例

例

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

（消去）

pqr

（結(jié)合律）這既是A的析取范式（由3個(gè)簡(jiǎn)單合取式組成的析取式），又是A的合取范式（由一個(gè)簡(jiǎn)單析取式組成的合取式）第11頁(yè)，講稿共35頁(yè)，2023年5月2日，星期三12求公式的范式舉例(續(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)成）

第12頁(yè)，講稿共35頁(yè)，2023年5月2日，星期三13極小項(xiàng)與極大項(xiàng)

定義

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

，pqr，pqr，pqr。第13頁(yè)，講稿共35頁(yè)，2023年5月2日，星期三14極小項(xiàng)與極大項(xiàng)

定義

在含有n個(gè)命題變項(xiàng)的簡(jiǎn)單合取式(簡(jiǎn)單析取式)中，若每個(gè)命題變項(xiàng)均以文字的形式在其中出現(xiàn)且僅出現(xiàn)一次，而且第i（1in）個(gè)文字出現(xiàn)在左起第i位上，稱這樣的簡(jiǎn)單合取式（簡(jiǎn)單析取式）為極小項(xiàng)（極大項(xiàng)）.例如，由兩個(gè)命題變?cè)猵和q，構(gòu)成大項(xiàng)有pq，pq，pq，pq；三個(gè)命題變?cè)猵，q和r，構(gòu)成pqr，pqr，pqr，pqr，pqr，pqr，pqr，pqr。第14頁(yè)，講稿共35頁(yè)，2023年5月2日，星期三15極小項(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)）均互不等值用mi表示第i個(gè)極小項(xiàng)，其中i是該極小項(xiàng)成真賦值的十進(jìn)制表示.（將命題變?cè)醋值湫蚺帕?，并且把命題變?cè)c1對(duì)應(yīng)，命題變?cè)姆穸ㄅc0對(duì)應(yīng)，則可對(duì)2n個(gè)小項(xiàng)依二進(jìn)制數(shù)編碼）

用Mi表示第i個(gè)極大項(xiàng)，其中i是該極大項(xiàng)成假賦值的十進(jìn)制表示。（將n個(gè)命題變?cè)判?，并且把命題變?cè)c０對(duì)應(yīng)，命題變?cè)姆穸ㄅc１對(duì)應(yīng)，則可對(duì)2n個(gè)大項(xiàng)按二進(jìn)制數(shù)編碼）mi(Mi)稱為極小項(xiàng)(極大項(xiàng))的名稱.

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

mi

Mi,Mi

mi

第15頁(yè)，講稿共35頁(yè)，2023年5月2日，星期三16極小項(xiàng)與極大項(xiàng)(續(xù))由p,q兩個(gè)命題變項(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頁(yè)，講稿共35頁(yè)，2023年5月2日，星期三17

由p,q,r三個(gè)命題變項(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頁(yè)，講稿共35頁(yè)，2023年5月2日，星期三18小項(xiàng)的性質(zhì)：(a)沒(méi)有兩個(gè)小項(xiàng)是等價(jià)的，即是說(shuō)各小項(xiàng)的真值表都是不同的；(b)任意兩個(gè)不同的小項(xiàng)的合取式是永假的：mi∧mjＦ，i≠j。(c)所有小項(xiàng)之析取為永真：miＴ。(d)每個(gè)小項(xiàng)只有一個(gè)解釋為真，且其真值1位于主對(duì)角線上。第18頁(yè)，講稿共35頁(yè)，2023年5月2日，星期三19大項(xiàng)的性質(zhì)：(a)沒(méi)有兩個(gè)大項(xiàng)是等價(jià)的。(b)任何兩個(gè)不同大項(xiàng)之析取是永真的，即Mi∨MjＴ，i≠j。(c)所有大項(xiàng)之合取為永假，即MiＦ。(d)每個(gè)大項(xiàng)只有一個(gè)解釋為假，且其真值0位于主對(duì)角線上。第19頁(yè)，講稿共35頁(yè)，2023年5月2日，星期三20主析取范式與主合取范式

主析取范式:由極小項(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等值的主合取范式.

第20頁(yè)，講稿共35頁(yè)，2023年5月2日，星期三21主析取范式與主合取范式(續(xù))定理

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

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

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

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

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

第21頁(yè)，講稿共35頁(yè)，2023年5月2日，星期三22主析取范式與主合取范式(續(xù))用等值演算法求公式的主范式的步驟：

(1)先求析取范式

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

(3)用等冪律化簡(jiǎn)簡(jiǎn)單合取式中同一命題變?cè)闹貜?fù)出現(xiàn)為一次出現(xiàn)，如p∧pp。(4)

用同一律補(bǔ)進(jìn)簡(jiǎn)單合取式中未出現(xiàn)的所有命題變?cè)?，如q，則pp∧（q∨q)，并用分配律展開(kāi)之，將相同的簡(jiǎn)單合取式的多次出現(xiàn)化為一次出現(xiàn)，這樣得到了給定公式的主析取范式。第22頁(yè)，講稿共35頁(yè)，2023年5月2日，星期三23從A的主析取范式求其主合取范式的步驟(a)求出A的主析取范式中設(shè)有包含的小項(xiàng)。

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

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

例如，(pq)qm1m3，則(pq)qM0M2。第23頁(yè)，講稿共35頁(yè)，2023年5月2日，星期三24求公式的主范式例

求公式

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

(pq)r

(pq)r,（析取范式）

①

(pq)

(pq)(rr)(pqr)(pqr)m6m7,②第24頁(yè)，講稿共35頁(yè)，2023年5月2日，星期三25求公式的主范式(續(xù))r(pp)(qq)r(pqr)(pqr)(pqr)(pqr)

m1m3m5m7

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

(pq)r

m1m3m5

m6m7（主析取范式）

第25頁(yè)，講稿共35頁(yè)，2023年5月2日，星期三26求公式的主范式(續(xù))(2)求A的主合取范式

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

①

pr

p(qq)r

(pqr)(pqr)

M0M2,

②第26頁(yè)，講稿共35頁(yè)，2023年5月2日，星期三27求公式的主范式(續(xù))

qr

(pp)qr

(pqr)(pqr)

M0M4③

②,③代入①并排序，得

(pq)r

M0M2M4（主合取范式）

第27頁(yè)，講稿共35頁(yè)，2023年5月2日，星期三28主范式的用途——與真值表相同

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

例如(pq)r

m1m3m5

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

類似地，由主合取范式也可立即求出成假賦值和成真賦值.第28頁(yè)，講稿共35頁(yè)，2023年5月2日，星期三29主范式的用途(續(xù))(2)判斷公式的類型

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

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

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

A的主析取范式為0

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

第29頁(yè)，講稿共35頁(yè)，2023年5月2日，星期三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顯見(jiàn)，⑴中的兩公式等值，而⑵的不等值.

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

用公式A的真值表求A的主范式.第30頁(yè)，講稿共35頁(yè)，2023年5月2日，星期三31主范式的用途(續(xù))

例

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

(1)若趙去，錢也去；

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

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

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

(5)若周去，則趙、錢也去.試用主析取范式法分析該公司如何選派他們出國(guó)？第31頁(yè)，講稿共35頁(yè)，2023年5月2日，星期三32例(續(xù))解此類問(wèn)題的步驟為：①

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

寫出各復(fù)合