離散結(jié)構(gòu) 2.2課件

2.2.2主析取范式與主合取范式

音樂能激發(fā)或撫慰情懷，繪畫使人賞心悅目，詩歌能動(dòng)人心弦，哲學(xué)使人獲得智慧，科學(xué)可改善物質(zhì)生活，但數(shù)學(xué)能給予以上的一切----克萊因

命題等值驗(yàn)算的一個(gè)應(yīng)用：將下圖所示的邏輯電路簡化解：將上述邏輯電路寫成命題公式：

利用等值式將公式化簡

離散結(jié)構(gòu)2.2分配律

結(jié)合律

等冪律

所以，該電路可簡化為下圖

：離散結(jié)構(gòu)2.22.2.2主析取范式與主合取范式

1、簡單析取式，簡單合取式。

簡單析取式:由有限個(gè)命題變元或其否定構(gòu)成的析取式簡單合取式:由有限個(gè)命題變項(xiàng)或其否定構(gòu)成的合取式例如：等都是簡單析取式。，，，例如：等都是簡單合取式。

，，，離散結(jié)構(gòu)2.22、析取范式，合取范式。

例如：

為析取范式，

為合取范式。

定義：

由有限個(gè)簡單合取式構(gòu)成的析取式稱作析取范式。由有限個(gè)簡單析取式構(gòu)成的合取式稱作合取范式。離散結(jié)構(gòu)2.22、析取范式，合取范式。

例如：

為析取范式，

顯然，

為合取范式

，為合取范式。

例如：

為析取范式。

離散結(jié)構(gòu)2.22、析取范式，合取范式。

范式存在定理：任一命題公式都存在與之等值的析取范式和合取范式。離散結(jié)構(gòu)2.2求范式步驟：

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

(3)利用分配律。

(1)消去聯(lián)結(jié)詞

離散結(jié)構(gòu)2.2解：原式

消去

內(nèi)移

消去

上式即析取范式

例1、求公式的析取范式和合取范式。分配律

對(分配)離散結(jié)構(gòu)2.2解：原式

消去

內(nèi)移

消去

上式即合取范式

例1、求公式的析取范式和合取范式。分配律

(分配)對離散結(jié)構(gòu)2.22.2.2主析取范式與主合取范式

數(shù)學(xué)中的一些美麗定理具有這樣的特性：它們極易從事實(shí)中歸納出來，但證明卻隱藏的極深。――高斯

極小項(xiàng)與極大項(xiàng)的定義

在含有n個(gè)命題變項(xiàng)的簡單合（析）取式中，若每個(gè)命題變項(xiàng)和它的否定不同時(shí)出現(xiàn)，而二者之一必出現(xiàn)且僅出現(xiàn)一次，稱這樣的簡單合（析）取式為極小（大）項(xiàng)minimal(maximal)item。如命題公式(pq)∨

(p∧

r)的極小項(xiàng)有p∧q∧r、p∧┐q∧r、p∧q∧┐r、┐p∧q∧r等。p∧┐q∧r∧┐r和p∧┐q是否為上述公式的極小項(xiàng)？考慮：n個(gè)命題變項(xiàng)可產(chǎn)生多少個(gè)極?。ù螅╉?xiàng)？離散結(jié)構(gòu)2.22.2.2析取范式(disjunctionnormalform)每個(gè)極小項(xiàng)，如p1

∧p2

∧p3

∧…

∧pn,有且僅有一個(gè)成真賦值，若成真賦值所對應(yīng)的二進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)為i，就將所對應(yīng)的極小項(xiàng)記作mi。極小項(xiàng)二進(jìn)制十進(jìn)制編碼┐P∧┐Q∧┐R0000m0┐P∧┐Q∧R0011m1┐P∧Q∧┐R0102m2┐P∧Q∧R0113m3P∧┐Q∧┐R1004m4P∧┐Q∧R1015m5P∧Q∧┐R1106m6P∧Q∧R111┐m┐離散結(jié)構(gòu)2.2極大項(xiàng)

成假賦值

(二進(jìn)制數(shù))000001010011100101110111對應(yīng)十進(jìn)制數(shù)

01234567記法

離散結(jié)構(gòu)2.2主析取范式與主合取范式的定義主析取范式——每個(gè)簡單合取式都是極小項(xiàng)的析取范式。

主合取范式——每個(gè)簡單析取式都是極大項(xiàng)的合取范式。

兩種求法，等值式法和真值表法。

定理：任何命題公式的主析取范式、主合取范式

都存在且都是唯一的。離散結(jié)構(gòu)2.2disjunctionnormalform求解方法1：1。將命題公式轉(zhuǎn)換為析（合）取范式；2。判斷析（合）取范式中的簡單合（析）取式是否為命題公式的極小（大）項(xiàng)，若不是則進(jìn)行補(bǔ)項(xiàng)。

Ai

Ai

∧1Ai∧(pj∨

pj)

(Ai∧pj)∨(Ai∧

pj)

Ai

Ai

∨0Ai∨(pj∧

pj)

(Ai∨pj)∧(Ai∨

pj)求解方法2:1.求命題公式的真值表;2.列出使命題公式為真的指派所對應(yīng)的極小項(xiàng);3.將2列出的極小項(xiàng)進(jìn)行析取.離散結(jié)構(gòu)2.2disjunctionnormalform例：求(pq)r的主析取/合取范式。接前(p∧q∧

r)∨(r∧p)∨(r∧q)(析取范式)

(p∧q∧

r)∨((q∨q)∧(r∧p))∨((p∨p)∧(r∧q))

(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)

m1∨m3∨m4∨m┐(主析取范式)離散結(jié)構(gòu)2.2disjunctionnormalform例：求(pq)r的主析取/合取范式。接前(p∨r)∧(q∨r)∧(

r∨p∨q)

(合取范式）((p∨r)∨(q∧q))∧((p∧p)∨(q∨r))∧(

r∨p∨q)

(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)M0∧M2∧M5∧M6離散結(jié)構(gòu)2.2解：(1)列真值表

例用真值表求的主析取范式。離散結(jié)構(gòu)2.2解：(2)的成真賦值有010，100，101，110，111(3)對應(yīng)的十進(jìn)制數(shù)為2，4，5，6，7所以的主析取范式為

例3、用真值表求的主析取范式。離散結(jié)構(gòu)2.2disjunctionnormalform練習(xí)：求主析取/合取范式。1、(

pq)∧(pr)2、(pq)∨(p∧

r)1(p∨q∨r)∧(p∨q∨

r)∧(p∨q∨r)∧

(p∨q∨r)(主合取范式)

M0∧M1∧M4∧M6(p∧q∧r)∨

(p∧

q∧r)∨(p∧q∧r)∨(p∧q∧

r)

(主析取范式)

2p∨q∨r(主合取范式)

m0∨m1

∨m2

∨m3∨m5∨m6∨m┐離散結(jié)構(gòu)2.2disjunctionnormalform主析取范式的用途（主合取范式類似討論）：1、求公式的成真/成假賦值：若公式A中含有n個(gè)命題變項(xiàng)，且A的主析取范式含s個(gè)極小項(xiàng)，則A有s個(gè)成真賦值，有2n-s個(gè)成假賦值。2、判斷公式的類型：設(shè)公式A中含有n個(gè)命題變項(xiàng)，則：（1）A為重言式

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

A的主析取范式不含任何極小項(xiàng)，記A的主析取范式為0。（3）A為可滿足式A的主析取范式至少含一個(gè)極小項(xiàng)。離散結(jié)構(gòu)2.2disjunctionnormalform練習(xí)：求下列公式的主析取范式，并判斷公式的類型。1、(

pq)(qp)2、(p∨

p)

((q∧

q)∧

r)3、((pq)∧(q

r))(pr)3、判斷兩個(gè)命題是否等值：設(shè)公式A、B中共含有n個(gè)命題變項(xiàng)，按n個(gè)命題變項(xiàng)求出A、B的主析取范式A`、B`。若A`=B`，則AB，否則A、B不等值。練習(xí)：1、(pq)∧(p

r)與

p(q∧r)2、p(q∧r)與p∨(qr)離散結(jié)構(gòu)2.2disjunctionnormalform解：1、(pq)∧(p

r)

(p∨q)∧(p

∨r)

p∨(q∧

r)

m0∨m1

∨m2

∨m3∨m┐p(q∧r)p∨(q∧

r)

m0∨m1

∨m2

∨m3∨m┐所以(pq)∧(p

r)

p(q∧r)離散結(jié)構(gòu)2.2disjunctionnormalform解：2、p(q∧r)

p∨(q∧

r)

m0∨m1

∨m2

∨m3∨m┐p∨(qr)p∨q∨

r

m0∨m1

∨m3∨m4

∨m5∨m6∨m┐所以(pq)∧(p

r)與

p(q∧r)不等值。

離散結(jié)構(gòu)2.2disjunctionnormalform4、解決實(shí)際問題：某勘探隊(duì)有3名隊(duì)員，有一天取得一塊礦樣，3人判斷如下：甲說：這不是鐵，也不是銅。乙說：這不是鐵，是錫。丙說：這不是錫，是鐵。經(jīng)實(shí)驗(yàn)室鑒定發(fā)現(xiàn)，其中一人的兩個(gè)判斷全對，一人判對一半，另一人全錯(cuò)。試根據(jù)以上情況，判斷礦樣的種類。離散結(jié)構(gòu)2.2disjunctionnormalform解:

設(shè)p:礦樣是鐵。q:礦樣是銅。r:礦樣是錫。根據(jù)題設(shè)知有六種情況：①甲正確，乙對一半，丙全錯(cuò)；②甲正確，乙全錯(cuò)，丙對一半；③甲對一半，乙正確，丙全錯(cuò)；④甲對一半，乙全錯(cuò)，丙正確；⑤甲全錯(cuò)，乙正確，丙對一半；⑥甲全錯(cuò)，乙對一半，丙正確。離散結(jié)構(gòu)2.2disjunctionnormalform以上六種情況對應(yīng)公式分別為：①(p∧q)∧((p∧r)∨(p∧r))

∧(p∧r)0②(p∧q)∧(p∧r)∧((p∧r)∨(p∧

r))

0③((p∧q)∨(p∧q))∧(p∧r)∧(p∧r)p∧q∧r④((p∧q)∨(p∧q))∧(p∧r)∧(p∧

r)p∧

q∧r⑤(p∧q)∧(p∧r)∧((p∧r)∨(p∧

r))

0⑥(p∧q)∧((p∧r)∨(p∧r))

∧

(p∧

r)0離散結(jié)構(gòu)2.2disjunctionnormalform解:

設(shè)判斷經(jīng)過為F，則：F①∨②∨③∨④∨⑤∨⑥(p∧q∧r)∨(p∧

q∧r)但不能同時(shí)為銅又為錫，因而只能對應(yīng)p∧

q∧r，即不是銅，也不是錫，而是鐵。離散結(jié)構(gòu)2.22.2.2合取范式(conjunctionnormalform)每個(gè)極大項(xiàng)，如p1

∨p2

∨p3

∨…

∨pn,有且僅有一個(gè)成假賦值，若成假賦值所對應(yīng)的二進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)為i，就將所對應(yīng)的極小項(xiàng)記作Mi。極大項(xiàng)二進(jìn)制十進(jìn)制編碼P∨Q∨R0000M0P∨Q∨┐R0011M1P∨┐Q∨R0102M2P∨┐Q∨┐R0113M3┐P∨Q∨R1004M4┐P∨Q∨┐R1015M5┐P∨┐Q∨R1106M6┐P∨┐Q∨┐R111┐M┐離散結(jié)構(gòu)2.2conjunctionnormalform定理2極小項(xiàng)與極大項(xiàng)關(guān)系設(shè)mi和Mi是命題變項(xiàng)p1

，

p2

，…

∧pn形成的極小項(xiàng)和極大項(xiàng)，則

mi

Mi

，

Mi

mi離散結(jié)構(gòu)2.2

用真值表求的主合取范式。解：(1)由例3知真值表，的離散結(jié)構(gòu)2.2(3)對應(yīng)的十進(jìn)制數(shù)為0，1，3。

用真值表求的主合取范式。解：(2)的成假賦值有000，001，011，所以的主合取范式：思考：命題公式間有什么聯(lián)系，能否通過其中一個(gè)求另一個(gè)？(觀察例3，例5)的主合取范式，主析取范式離散結(jié)構(gòu)2.2conjunctionnormalform關(guān)于主合取范式1、由公式的主析取范式求主合取范式設(shè)公式A中含有n個(gè)命題變項(xiàng)，且A的主析取范式含s個(gè)極小項(xiàng)，即Ami1∨

mi2∨