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

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

p,

q,p

q,p

q

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

p,

q,p

q,p

q

r,…1）一個(gè)簡(jiǎn)單析取式為重言式當(dāng)且僅當(dāng)它同時(shí)含有一個(gè)命題變項(xiàng)及它的否定；2）一個(gè)簡(jiǎn)單和取式為矛盾式當(dāng)且僅當(dāng)它同時(shí)含有一個(gè)命題變項(xiàng)及它的否定.由定義易知：第一頁(yè)1第二頁(yè)，共40頁(yè)。

由有限個(gè)簡(jiǎn)單合取式組成的析取式.

A1

A2

Ar,其中A1,A2,,Ar是簡(jiǎn)單合取式合取范式:由有限個(gè)簡(jiǎn)單析取式組成的合取式.

A1

A2

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

q

r,

p

q

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

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

(1)消去A中的

,

（若存在）

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

(3)利用分配律

對(duì)

分配（析取范式）

對(duì)

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

q)

r解(p

q)

r

(

p

q)

r

（消去

）

p

q

r

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

q)

r解:(p

q)

r

(

p

q)

r

（消去第一個(gè)

）

(

p

q)

r

（消去第二個(gè)

）

(p

q)

r

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

q)

r

(p

r)

(q

r)（

對(duì)

分配律）這一步得到合取范式（由兩個(gè)簡(jiǎn)單析取式構(gòu)成）第六頁(yè)6第七頁(yè)，共40頁(yè)。例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)

（對(duì)分配）

(q

p)

(

p

r)

(q

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

q)

(p

r)

的合取范式。解:(p

q)

(p

r)

(

p

q)

(p

r)

（消去

）

(

p

q

p)

(

p

q

r)

（對(duì)分配）

p

q

r

（排中律,同一律）

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

i

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

q，p

q

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

p

q

p

qp

qp

q00011011由p,q兩個(gè)命題變項(xiàng)形成的極小項(xiàng):第十一頁(yè)11第十二頁(yè)，共40頁(yè)。

由p,q,r三個(gè)命題變項(xiàng)形成的極小項(xiàng):公式成真賦值極小項(xiàng)

p

q

r

p

q

r

p

q

r

p

q

rp

q

rp

q

rp

q

rp

q

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

p

q

r)

(

p

q

r)

m1

m3

是主析取范式

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

第十三頁(yè)13第十四頁(yè)，共40頁(yè)。定理

任何命題公式都存在著與之等值的主析取范式,并且是惟一的.用等值演算法求公式的主析取范式的步驟：(1)先求析取范式;(2)將不是極小項(xiàng)的簡(jiǎn)單合取式化成與之等值的若干個(gè)極小項(xiàng)的析取，需要利用同一律、排中律、分配律、等冪律……(3)極小項(xiàng)用名稱mi表示，按角標(biāo)從小到大順序排序.第十四頁(yè)14第十五頁(yè)，共40頁(yè)。求公式的主析取范式例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,②第十五頁(yè)15第十六頁(yè)，共40頁(yè)。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（主析取范式）第十六頁(yè)16第十七頁(yè)，共40頁(yè)。例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

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

q)

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

q(p

q)

r

0000010101110111001011101110011111100000主析取范式為：m3

m5

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

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

第十九頁(yè)19第二十頁(yè)，共40頁(yè)。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課堂練習(xí)：∑(0,1,3,7)∑(1,3,5,7)∑(5)∑(1,3,4,5,7)第二十頁(yè)20第二十一頁(yè)，共40頁(yè)。主范式的用途——與真值表相同(1)求公式的成真賦值和成假賦值

例如(p

q)

r

m1

m3

m5

m6

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

第二十一頁(yè)21第二十二頁(yè)，共40頁(yè)。

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

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

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

A的主析取范式中至少含一個(gè)但不含全部極小項(xiàng)(2)判斷公式的類型第二十二頁(yè)22第二十三頁(yè)，共40頁(yè)。例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顯見(jiàn)，⑴中兩公式等值，而⑵的兩公式不等值.(3)判斷兩個(gè)公式是否等值第二十三頁(yè)23第二十四頁(yè)，共40頁(yè)。(4)分析和解決一些實(shí)際問(wèn)題例1.21某公司要從趙、錢(qián)、孫三名新畢業(yè)的大學(xué)生中選派一些人出國(guó)學(xué)習(xí)，選派必須滿足以下條件：

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

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

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

r(2)q

r(3)

r(p

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

A=(p

r)

(q

r)

(

r(p

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

(

p

q

r)

(

p

q

r)

(p

q

r)

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

i

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

p

qp

q

p

qp

q00100111由p,q兩個(gè)命題變項(xiàng)形成的極大項(xiàng)第三十頁(yè)30第三十一頁(yè)，共40頁(yè)。

由p,q,r三個(gè)命題變項(xiàng)形成的極大項(xiàng)公式成假賦值名稱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

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

p

q

p

qp

qp

q00011011m0m1m2m3

p

q

p

q

p

q

p

q

00011011M0M1M2M3

極小項(xiàng)極大項(xiàng)第三十二頁(yè)32第三十三頁(yè)，共40頁(yè)。

由p,q,r三個(gè)命題變項(xiàng)形成的極小項(xiàng)與極大項(xiàng)極小項(xiàng)極大項(xiàng)公式成真賦值名稱公式成假賦值名稱

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

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

q

r)

(

p

q

r)

M1

M5

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

mi

Mi,

Mi

mi

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

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