離散數(shù)學(xué)：第一章1-5 對偶與范式

1第一章命題邏輯

1.1命題符號化及聯(lián)結(jié)詞1.2命題公式及分類1.3等值演算1.4聯(lián)結(jié)詞全功能集1.5對偶與范式1.6推理理論2§5對偶與范式

一、對偶式與對偶原理二、析取范式與合取范式三、主析取范式與主合取范式1.極小項和極大項2.求法3.用途3一、對偶式和對偶原理定義

在僅含有聯(lián)結(jié)詞

,∧,∨的命題公式A中，將∨換成∧,∧換成∨，若A中含有0或1，就將0換成1，1換成0，所得命題公式稱為A的對偶式，記為A*.p∧q

與

pVq是對偶式；┐(p∧q)

與┐(pVq)是對偶式。4一、對偶式和對偶原理(續(xù))定理

設(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)例如:A(p,q,r)=p∧(┐qVr)┐A(p,q,r)=┐(p∧(┐qVr))┐pV(q∧┐r)A*(p,q,r)=pV(┐q∧r)A*(┐p,┐q,┐r)=┐pV(q∧┐r)┐A*(p,q,r)=┐(pV(┐q∧r))┐p∧(qV┐r)A(┐p,┐q,┐r)=┐p∧(qV┐r)5對偶原理設(shè)A,B為兩命題公式,若AB,則A*B*,其中A*,B*分別為A,B的對偶式.例如:(p∧q)V(┐pV(┐pVq))┐pVq(p∧q)V(┐pV(┐pVq))(p∧q)v(┐pvq)

(pv(┐pvq))∧(qv(┐pvq))1∧(┐pvq)┐pVq對偶式(pvq)∧(┐p∧(┐p∧q))┐p∧q

(pvq)∧(┐p∧(┐p∧q))(pvq)∧(┐p∧q)(p∧(┐p∧q))v(q∧(┐p∧q))0v(┐p∧q)┐p∧q6二、析取范式與合取范式

簡單析取式:有限個命題變項及其否定構(gòu)成的析取式…如p,

q,p

q,p

q

r,…簡單合取式:有限個命題變項及其否定構(gòu)成的合取式如p,

q,p

q,p

q

r,

析取范式:由有限個簡單合取式組成的析取式A1

A2

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

A2

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

公式A的析取范式:與A等值的析取范式公式A的合取范式:與A等值的合取范式任何析(合)取范式的對偶式為合(析)取范式；一個析取范式為矛盾式，當(dāng)且僅當(dāng)它的每個簡單合取式都是矛盾式；一個合取范式為重言式，當(dāng)且僅當(dāng)它的每個簡單析取式都是重言式。

8命題公式的范式

定理(范式存在定理)

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

(1)消去A中的

,

（若存在）

(2)否定聯(lián)結(jié)詞

的內(nèi)移或消去

(3)使用分配律

對

分配（析取范式）

對

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

例

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

q)

r解(p

q)

r

(

p

q)

r

（消去

）

p

q

r

（結(jié)合律）這(單個命題變元)既是A的析取范式（由3個簡單合取式組成的析取式），又是A的合取范式（由一個簡單析取式組成的合取式）10求公式的范式舉例(續(xù))解

(p

q)

r

(

p

q)

r

（消去第一個

）

(

p

q)

r

（消去第二個

）

(p

q)

r

（否定號內(nèi)移——德

摩根律）這一步已為析取范式（兩個簡單合取式構(gòu)成）繼續(xù)：

(p

q)

r

(p

r)

(q

r)（

對

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

(2)B=(p

q)

r11三、主析取范式與主合取范式——極小項與極大項

定義

在含有n個命題變項的簡單合取式(簡單析取式)中，若每個命題變項及其否定在其中出現(xiàn)且僅出現(xiàn)一次，而第i（1

i

n）個文字出現(xiàn)在左起第i位上，稱這樣的簡單合取式（簡單析取式）為極小項（極大項）.說明：n個命題變項產(chǎn)生2n個極小項和2n個極大項

2n個極小項（極大項）均互不等值

mi極小項，i成真賦值.Mi極大項，i成假賦值

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

mi

Mi,

Mi

mi

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

公式

成真賦值名稱

公式

成假賦值名稱

p

q

p

qp

qp

q00011011

m0m1m2m3

p

q

p

q

p

q

p

q

00011011

M0M1M2M3

極小項

極大項

13

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

極小項

極大項

公式

成真賦值名稱

公式

成假賦值名稱

p

q

r

p

q

r

p

q

r

p

q

rp

q

rp

q

rp

q

rp

q

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

142.主析取范式與主合取范式

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

(

p

q

r)

(

p

q

r)

m1

m3

是主析取范式

(p

q

r)

(

p

q

r)

M1

M5

是主合取范式

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

A的主合取范式:

與A等值的主合取范式.15主析取范式與主合取范式(續(xù))定理

任何命題公式都存在著與之等值的主析取范式和主合取范式,并且是惟一的.用等值演算法求公式的主范式的步驟：

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

(2)對命題中不含某個變項的采用

BB∧1(B∧p)∨(B∧┐p)BB∨0(B∨p)∧(B∨┐p)(3)極小項（極大項）用名稱mi（Mi）表示，按角標(biāo)從小到大順序排序，并去掉重復(fù)的.

16求公式的主范式例

求公式

A=(p

q)

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

(p

q)

r

(p

q)

r,（析取范式）

①

(p

q)

(p

q)

(

r

r)

(p

q

r)

(p

q

r)

m6

m7,②17求公式的主范式(續(xù))r

(

p

p)

(

q

q)

r

(

p

q

r)

(

p

q

r)

(p

q

r)

(p

q

r)

m1

m3

m5

m7

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

(p

q)

r

m1

m3

m5

m6

m7（主析取范式）

18主析取范式與主合取范式的關(guān)系存在

mi

Mi關(guān)系（單個）.所以A

m0

m1

m5

m7

∑(0,1,5,7)

M0

M1

M5

M7

(M0

M1

M5

M7)

(M2

M3

M4

M6)∏(2,3,4,6)

19求公式的主范式(續(xù))(2)求A的主合取范式

(p

q)

r

(p

r)

(q

r),（合取范式）

①

p

r

p

(q

q)

r

(p

q

r)

(p

q

r)

M0

M2,

②20求公式的主范式(續(xù))

q

r

(p

p)

q

r

(p

q

r)

(

p

q

r)

M0

M4③

②,③代入①并排序，得

(p

q)

r

M0

M2

M4（主合取范式）

213.主范式的用途——與真值表相同

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

例如(p

q)

r

m1

m3

m5

m6

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

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

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

A為重言式

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

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

A的主析取范式為0

A的主合取范式含2n個極大項A為非重言式的可滿足式

A的主析取范式中至少含一個且不含全部極小項

A的主合取范式中至少含一個且不含全部極大項

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

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

p

(q

r)與

(p

q)

r⑵

p

(q

r)與

(p

q)

r解

p

(q

r)=m0

m1

m2

m3

m4

m5

m7

(p

q)

r=m0

m1

m2

m3

m4

m5

m7(p

q)

r=m1

m3

m4

m5

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

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

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

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

(1)若趙去，錢也去；

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

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

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

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

將簡單命題符號化②

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

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

④

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

26解答解

①

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

s：派李去，u：派周去.②(1)(p

q)(2)(s

u)(3)((q

r)

(

q

r))(4)((r

s)

(

r

s))(5)(u

(p

q))③(1)~(5)構(gòu)成的合取式為

A=(p

q)

(s

u)

((q

r)

(

q

r))

((r

s)

(