離散數(shù)學析取范式與合取范式

定義文字:命題變項及其否定的總稱.簡單析取式:有限個文字構(gòu)成的析取式.如

p,

q,p

q,p

q

r,…簡單合取式:有限個文字構(gòu)成的合取式.如

p,

q,p

q,p

q

r,…1）一個簡單析取式為重言式當且僅當它同時含有一個命題變項及它的否定；2）一個簡單和取式為矛盾式當且僅當它同時含有一個命題變項及它的否定.由定義易知：第一頁1第二頁，共40頁。

由有限個簡單合取式組成的析取式.

A1

A2

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

A1

A2

Ar,其中A1,A2,,Ar是簡單析取式由定義易知：析取范式:1）在析取范式（合取范式）中沒有聯(lián)結(jié)詞2）聯(lián)結(jié)詞只出現(xiàn)在原子命題前面.3）析取范式（合取范式）是合取式（析取式）的析取式（合取式）.第二頁2第三頁，共40頁。范式:析取范式與合取范式的總稱.公式A的析取范式:與A等值的析取范式公式A的合取范式:與A等值的合取范式說明：單個文字既是簡單析取式，又是簡單合取式形如p

q

r,

p

q

r的公式既是析取范式，又是合取范式(為什么?)第三頁3第四頁，共40頁。

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

(1)消去A中的

,

（若存在）

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

(3)利用分配律

對

分配（析取范式）

對

分配（合取范式）公式的范式存在，但不惟一，這是它的局限性.定理（范式存在定理）第四頁4第五頁，共40頁。求公式的范式舉例例1.15求下列公式的析取范式與合取范式:(1)A=(p

q)

r解(p

q)

r

(

p

q)

r

（消去

）

p

q

r

（結(jié)合律）這既是A的析取范式（由3個簡單合取式組成的析取式），又是A的合取范式（由一個簡單析取式組成的合取式）第五頁5第六頁，共40頁。(2)B=(p

q)

r解:(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)成）第六頁6第七頁，共40頁。例1.16(1)求(

p

q)(p

r)的析取范式;解:(

p

q)(p

r)

(

p

q)

(

p

r)（消去

）

(

p

q)

(

p

r)（雙重否定律）

(

p

p)

(q

p)

(

p

r)

(q

r)

（對分配）

(q

p)

(

p

r)

(q

r)（零律,同一律）第七頁7第八頁，共40頁。(2)求(p

q)

(p

r)

的合取范式。解:(p

q)

(p

r)

(

p

q)

(p

r)

（消去

）

(

p

q

p)

(

p

q

r)

（對分配）

p

q

r

（排中律,同一律）

第八頁8第九頁，共40頁。極小項定義在含有n個命題變項的簡單合取式中，若每個命題變項均以文字的形式在其中出現(xiàn)且只出現(xiàn)一次，而且第i（1

i

n）個文字出現(xiàn)在左起第i位上，這樣的簡單合取式稱為極小項.如：p

q，p

q

r第九頁9第十頁，共40頁。說明：n個命題變項產(chǎn)生2n個極小項，2n個極小項均互不等值.用mi表示第i個極小項，其中i是該極小項成真賦值的十進制表示,mi稱為極小項的名稱.第十頁10第十一頁，共40頁。公式成真賦值極小項

p

q

p

qp

qp

q00011011由p,q兩個命題變項形成的極小項:第十一頁11第十二頁，共40頁。

由p,q,r三個命題變項形成的極小項:公式成真賦值極小項

p

q

r

p

q

r

p

q

r

p

q

rp

q

rp

q

rp

q

rp

q

r000001010011100101110111m0m1m2m3m4m5m6m7第十二頁12第十三頁，共40頁。主析取范式主析取范式:由極小項構(gòu)成的析取范式.例如，n=3,命題變項為p,q,r時，(

p

q

r)

(

p

q

r)

m1

m3

是主析取范式

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

第十三頁13第十四頁，共40頁。定理

任何命題公式都存在著與之等值的主析取范式,并且是惟一的.用等值演算法求公式的主析取范式的步驟：(1)先求析取范式;(2)將不是極小項的簡單合取式化成與之等值的若干個極小項的析取，需要利用同一律、排中律、分配律、等冪律……(3)極小項用名稱mi表示，按角標從小到大順序排序.第十四頁14第十五頁，共40頁。求公式的主析取范式例1.17求公式(p

q)

r的主析取范式.(p

q)

r

(p

q)

r,（析取范式）①其中(p

q)

(p

q)

(

r

r)

(p

q

r)

(p

q

r)

m6

m7,②第十五頁15第十六頁，共40頁。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（主析取范式）第十六頁16第十七頁，共40頁。例1.18求下列公式的主析取范式.(

p

q)

(p

r)((p

q)

r)

p答案:(1)(

p

q)

(p

r)

m2

m3

m5

m7

(2)((p

q)

r)

p

m2

m4

m5

m6

m7

第十七頁17第十八頁，共40頁。例1.19由(p

q)

r的真值表求其主析取范式.pqrp

q(p

q)

r

0000010101110111001011101110011111100000主析取范式為：m3

m5

m7第十八頁18第十九頁，共40頁。作業(yè):

P3617(1)(3)，18(1)，19

第十九頁19第二十頁，共40頁。1.證明：⑴p

(q

r)

(p

q)

r⑵(p

q)

(p

q)

p2.求主析取范式：⑴

(p

q)

r⑵(p

q)

(q

r)

(3)

(p

q)

q

r

(4)(p

q)

r課堂練習：∑(0,1,3,7)∑(1,3,5,7)∑(5)∑(1,3,4,5,7)第二十頁20第二十一頁，共40頁。主范式的用途——與真值表相同(1)求公式的成真賦值和成假賦值

例如(p

q)

r

m1

m3

m5

m6

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

第二十一頁21第二十二頁，共40頁。

設(shè)A含n個命題變項，則A為重言式

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

A的主析取范式為0A為非重言式的可滿足式

A的主析取范式中至少含一個但不含全部極小項(2)判斷公式的類型第二十二頁22第二十三頁，共40頁。例1.20用主析取范式判斷下述兩公式是否等值：⑴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)判斷兩個公式是否等值第二十三頁23第二十四頁，共40頁。(4)分析和解決一些實際問題例1.21某公司要從趙、錢、孫三名新畢業(yè)的大學生中選派一些人出國學習，選派必須滿足以下條件：

(1)若趙去，則孫也可以去；

(2)若錢去，則孫不能去；

(3)若孫不去，則趙或錢可以去.試用主析取范式法分析該公司如何選派他們出國？第二十四頁24第二十五頁，共40頁。解此類問題的步驟為：①將簡單命題符號化；②寫出各復合命題；③寫出由②中復合命題組成的合取式；④求③中所得公式的主析取范式。第二十五頁25第二十六頁，共40頁。解:①設(shè)p：派趙去，q：派錢去，r：派孫去.②(1)p

r(2)q

r(3)

r(p

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

A=(p

r)

(q

r)

(

r(p

q))第二十六頁26第二十七頁，共40頁。④A的演算:A

(

p

q

r)

(

p

q

r)

(p

q

r)

∑(1,2,5)結(jié)論：由④可知，A的成真賦值為001、010、101，因而方案有三個：孫去（趙、錢不去）；錢去（趙、孫不去）；趙、孫（錢不去）.第二十七頁27第二十八頁，共40頁。極大項定義在含有n個命題變項的簡單析取式中，若每個命題變項均以文字的形式在其中出現(xiàn)且只出現(xiàn)一次，而且第i（1

i

n）個文字出現(xiàn)在左起第i位上，這樣的簡單析取式稱為極大項.第二十八頁28第二十九頁，共40頁。說明：n個命題變項產(chǎn)生2n個極大項，2n個極大項均互不等值.用Mi表示第i個極大項，其中i是該極大項成假賦值的十進制表示,Mi稱為極大項的名稱.第二十九頁29第三十頁，共40頁。公式成假賦值極大項

p

qp

q

p

qp

q00100111由p,q兩個命題變項形成的極大項第三十頁30第三十一頁，共40頁。

由p,q,r三個命題變項形成的極大項公式成假賦值名稱p

q

r

p

q

r

p

q

r

p

q

r

p

q

r

p

q

r

p

q

r

p

q

r

000001010011100101110111M0M1M2M3M4M5M6M7

第三十一頁31第三十二頁，共40頁。極小項與極大項比較由p,q兩個命題變項形成的極小項與極大項公式成真賦值名稱公式成假賦值名稱

p

q

p

qp

qp

q00011011m0m1m2m3

p

q

p

q

p

q

p

q

00011011M0M1M2M3

極小項極大項第三十二頁32第三十三頁，共40頁。

由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

第三十三頁33第三十四頁，共40頁。主合取范式:由極大項構(gòu)成的合取范式.例如，n=3,命題變項為p,q,r時，(p

q

r)

(

p

q

r)

M1

M5

是主合取范式A的主合取范式:與A等值的主合取范式.由上述比較可知：極小項mi與極大項Mi的關(guān)系:

mi

Mi,

Mi

mi

第三十四頁34第三十五頁，共40頁。求主合取范式的方法：1.

等值演算法：(1)先求合取范式;(2)將不是極大項的簡單析取式化成與之等值的若干個極大項的合取，需要利用零律、同一律、排中律、分配律、等