離散數(shù)學(xué)2課件

DiscreteMathematics

4/17/20241DiscreteMath.第一章命題邏輯等值演算ChapteronePropositionLogic4/17/20242DiscreteMath.2.1等值式2.2析取范式與合取范式2.3聯(lián)結(jié)詞的完備集等值式定義基本等值式等值演算（置換規(guī)則）簡單析?。ê先。┦綐O大（小）項（主）析（合）取范式真值函數(shù)聯(lián)結(jié)詞完備集2.4可滿足性問題與消解法第一章內(nèi)容4/17/20243DiscreteMath.設(shè)公式Ａ、Ｂ中總共含有命題變項p1,

p2,

…

pn，但Ａ或Ｂ并不全含有這些變項。如果某個變項未在公式Ａ中出現(xiàn)，則稱該變項為Ａ的啞元。同樣可定義Ｂ的啞元。在討論Ａ與Ｂ是否有相同的真值表時，應(yīng)將啞元考慮在內(nèi)，即將Ａ、Ｂ都看成含所有p1,

p2

,

…

pn的命題公式，如果在所有2n個賦值下，Ａ與Ｂ的真值相同，則Ａ

Ｂ為重言式。啞元4/17/20244DiscreteMath.定義2.1設(shè)A,B是兩個命題公式，若A,B構(gòu)成的等價式A?B為重言式，則稱A與B是等值的,記為A?B。例2.1判斷公式┐(p∨q)與┐p∧┐q是否等值。解：用真值表法判斷,如下：pq┐p┐qp∨q┐(p∨q)┐p∧┐q┐(p∨q)?(┐p∧┐q)00011011注：A與B等值當(dāng)且僅當(dāng)A與B的真值表相同。因此，檢驗A與B是否等值，也可通過檢查A與B的真值表是否相同來實現(xiàn)。從表中可見，┐(p∨q)與┐p∨┐q等值。110111101001011001001001定義4/17/20245DiscreteMath.(1)p→(q→r)與(p∧q)→r;(2)(p→q)→r與(p∧q)→r。解：所給的4個公式的真值表如下：pqrp→(q→r)(p∧q)→r(p→q)→r000001010011100101110111但(p→q)→r?(p∧q)→r.110111110111111111000111由真值表可見，p→(q→r)?(p∧q)→r,例2.2判斷下列兩組公式是否等值：4/17/20246DiscreteMath.當(dāng)命題公式中變項較多時，用上述方法判斷兩個公式是否等值計算量很大。為此，人們將一組經(jīng)檢驗為正確的等值式作為等值式模式，通過公式間的等值演算來判斷兩公式是否等值。常用的等值式模式如下：1.雙重否定律：A?┐(┐A)2.冪等律：A?A∨A,A?A∧A3.交換律:A∨B?B∨A,A∧B?B∧A4.結(jié)合律:(A∨B)∨C?A∨(B∨C),(A∧B)∧C?A∧(B∧C)5.分配律：A∨(B∧C)?(A∨B)∧(A∨C)(∨對∧的分配律)A∧(B∨C)?(A∧B)∨(A∧C)(∧對∨的分配律)6.德摩根律：┐(A∨B)?┐A∧┐B,┐(A∧B)?┐A∨┐B7.吸收律：A∨(A∧B)?A,A∧(A∨B)?A等值式模式4/17/20247DiscreteMath.8.零律：A∨1?1,A∧0?09.同一律：A∨0?A,A∧1?A10.排中律：A∨┐A?111.矛盾律：A∧┐A?012.蘊含等值式：A→B?┐A∨B13.等價等值式:(A?B)?(A→B)∧(B→A)14.假言易位:A→B?┐B→┐A15.等價否定等值式:A?B?┐A?┐B16.歸謬論:(A→B)∧(A→┐B)?┐A等值式模式（續(xù)）4/17/20248DiscreteMath.利用這16組24個等值式可以推演出更多的等值式。由已知的等值式推演出另一些等值式的過程稱為等值演算。在等值演算中,經(jīng)常用到如下置換規(guī)則。置換規(guī)則:設(shè)Φ(A)是含公式A的命題公式，Φ(B)是用公式B置換了Φ(A)中所有的A后所得的公式。若B?A,則Φ(B)?Φ(A)。等值演算4/17/20249DiscreteMath.例如，對公式(p→q)→r,如果用┐p∨q置換其中的p→q,則得(┐p∨q)→r.由于p→q?┐p∨q，故(p→q)→r?(┐p∨q)→r。類似地，可進(jìn)行如下等值演算：(p→q)→r?(┐p∨q)→r?┐(┐p∨q)∨r?(p∧┐q)∨r?(p∨r)∧(┐q∨r)為簡便起見,以后凡用到置換規(guī)則時,均不必標(biāo)出。(蘊含等值式，置換規(guī)則）(蘊含等值式，置換規(guī)則）(德摩根律，置換規(guī)則）(分配律，置換規(guī)則）等值演算-例子4/17/202410DiscreteMath.例2.3

用等值演算證明:(p∨q)→r?(p→r)∧(q→r)

注：用等值演算證明等值式時，既可以從左向右推演，也可以從右向左推演。證：(p→r)∧(q→r)?(┐p∨r)∧(┐q∨r)?(┐p∧┐q)∨r?┐(p∨q)∨r?(p∨q)→r

(蘊含等值式)(分配律)(德摩根律)(蘊含等值式)

例2.34/17/202411DiscreteMath.證明：(p→q)→r?p→(q→r）.方法三:記A=(p→q)→r,B=p→(q→r)。先將A,B等值演算化成易于觀察真值的公式，再進(jìn)行判斷。

A=(p→q)→r?(┐p∨q)→r?┐(┐p∨q)∨r?(p∧┐q)∨rB=p→(q→r)?┐p∨(┐q∨r)?┐p∨┐q∨r

易見，000，010是A的成假賦值，而它們是B的成真賦值。方法二：觀察法。(p→q)→r?p→(q→r)。證方法一：真值表法。故(蘊含等值式)(蘊含等值式)(德摩根律)(蘊含等值式)(結(jié)合律)例244/17/202412DiscreteMath.(1)（p→q)∧p→q;(2)┐(p→(p∨q))∧r;(3)p∧(((p∨q)∧┐p)→q).解:(1)（p→q)∧p→q?(┐p∨q)∧p→q?┐((┐p∨q)∧p)∨q?(┐(┐p∨q)∨┐p)∨q?((p∧┐q)∨┐p)∨q?((p∨┐p)∧(┐q∨┐p))∨q?(1∧(┐q∨┐p))∨q?(┐q∨┐p)∨q?(┐q∨q)∨┐p?1∨┐p?1故(p→q)∧p→q是重言式。用等值演算判斷下列公式的類型(蘊含等值式)(蘊含等值式)(德摩根律)(德摩根律)(分配律)(排中律)(同一律）(交換律，結(jié)合律）（排中律）（零律）例2.54/17/202413DiscreteMath.(2)┐(p→(p∨q))∧r?┐(┐p∨p∨q)∧r

?(p∧┐p∧┐q)∧r

?(0∧┐q)∧r

?0∧r

?0故┐(p→(p∨q))∧r是矛盾式。(蘊含等值式，結(jié)合律）(德摩根律）(矛盾律）(零律)(零律）例2.5（續(xù)）4/17/202414DiscreteMath.p∧(((p∨q)∧┐p)→q)?p∧(┐((p∨q)∧┐p)∨q)(蘊含等值式)?p∧(┐((p∧┐p)∨(q∧┐p))∨q)(分配律)?p∧(┐(0∨(q∧┐p))∨q)(矛盾律)?p∧(┐(q∧┐p))∨q)(同一律)?p∧((┐q∨p)∨q)(德摩根律，雙重否定律)?p∧((┐q∨q)∨p)(交換律，結(jié)合律)?p∧(1∨p)

（排中律）?p∧1

（零律）?p

（同一律）

可見，（3）中公式不是重言式，因為00，01都是成假賦值；它也不是矛盾式，因為10，11都是其成真賦值，故它是可滿足式。例2.5（續(xù)）4/17/202415DiscreteMath.例2.6在某次研討會的休息時間，3名與會者根據(jù)王教授的口音對他是哪個省市的人進(jìn)行了判斷：甲說王教授不是蘇州人，是上海人。乙說王教授不是上海人，是蘇州人。丙說王教授不是上海人，也不是杭州人。聽完3人的判斷，王教授笑著說，他們3人中有一人說得全對，有一人說對了一半，有一人說得全不對。試用邏輯演算法分析王教授到底是哪里的人？解：設(shè)命題p,q,r分別表示：王教授是蘇州、上海、杭州人。則p,q,r中必有一個真命題，兩個假命題。要通過邏輯演算將真命題找出來。設(shè)：甲的判斷為：A1=┐p∧q;乙的判斷為：A2=p∧┐q;丙的判斷為：A3=┐q∧┐r。例2.64/17/202416DiscreteMath.那么甲的判斷全對：B1=A1=┐p∧q甲的判斷對一半：B2=((┐p∧┐q)∨(p∧q))甲的判斷全錯：B3=p∧┐q乙的判斷全對：C1=A2=p∧┐q乙的判斷對一半：C2=((p∧q)∨(┐p∧┐q))乙的判斷全錯：C3=┐p∧q丙的判斷全對：D1=A3=┐q∧┐r丙的判斷對一半：D2=((q∧┐r)∨(┐q∧r))丙的判斷全錯：D3=q∧r由王教授所說E=(B1∧C2∧D3)∨(B1∧C3∧D2)∨(B2∧C1∧D3)∨(B2∧C3∧D1)∨(B3∧C1∧D2)∨(B3∧C2∧D1)為真命題.例2.6（續(xù)）4/17/202417DiscreteMath.B1∧C2∧D3=(┐p∧q)∧((p∧q)∨(┐p∧┐q))∧(q∧r)

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

0B1∧C3∧D2=(┐p∧q)∧(┐p∧q)∧((q∧┐r)∨(┐q∧r))

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

┐p∧q∧┐rB2∧C1∧D3=((┐p∧┐q)∨(p∧q))∧(p∧┐q)∧(q∧r)

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

0類似可得B2∧C3∧D1

0,B3∧C1∧D2

p∧┐q∧r,B3∧C2∧D1

0于是，由同一律可知E

(┐p∧q∧┐r)∨(p∧┐q∧r)但因為王教授不能既是蘇州人，又是杭州人，因而p,r必有一個為假命題，即p∧┐q∧r

0。于是E

┐p∧q∧┐r為真命題，因而必有p,r為假命題，q為真命題，即王教授為上海人，甲說得全對，丙說對了一半，而乙全說錯啦。例2.6（續(xù)）4/17/202418DiscreteMath.定義2.2

命題變項及其否定統(tǒng)稱作文字。僅由有限個文字構(gòu)成的析取式稱作簡單析取式；僅由有限個文字構(gòu)成的合取式稱作簡單合取式?！?.2析取范式與合取范式例如：p;┐p;q∨┐q;p∨┐q;┐p∨┐q∨r都是簡單析取式.p;┐p;q∧q;┐p∧┐q∧r;┐p∧p∧r都是簡單合取式。注：單個文字既是簡單析取式又是簡單合取式。定理2.1

(1)一個簡單析取式是重言式當(dāng)且僅當(dāng)它同時含有某個命題變項及它的否定式；(2)一個簡單合取式是矛盾式當(dāng)且僅當(dāng)它同時含有某個命題變項及其否定式。4/17/202419DiscreteMath.例如：(p∧┐q)∨(┐q∧┐r)∨r是一個析取范式，而(p∨q∨r)∧(┐p∨┐q)∧r是一個合取范式。注：單個文字既是簡單析取式又是簡單合取式。因此形如┐p∧q∧r的公式既是由一個簡單合取式構(gòu)成的析取范式，又是由三個簡單析取式構(gòu)成的合取范式。類似地，形如p∨┐q∨r的公式既可看成析取范式也可看成合取范式。定義2.3

由有限個簡單合取式構(gòu)成的析取式稱為析取范式；由有限個簡單析取式構(gòu)成的合取式成為合取范式；析取范式與合取范式統(tǒng)稱為范式。定義4/17/202420DiscreteMath.析取范式的一般形式：A?A1

A2

…

An,其中Ai(i=1,…,n)是簡單合取式；合取范式的一般形式：A?A1

A2

…

An,其中Ai(i=1,…,n)是簡單析取式。定理2.2（1）一個析取范式是矛盾式當(dāng)且僅當(dāng)它的每個簡單合取式都是矛盾式；（2）一個合取范式是重言式當(dāng)且僅當(dāng)它的每個簡單析取式都是重言式。范式的一般形式4/17/202421DiscreteMath.定理2.3（范式存在定理）任一命題公式都存在著與之等值的析取范式與合取范式。證明：首先由蘊含等值式和等價等值式可知：A→B?┐A∨B,A?B?(┐A∨B)∧(A∨┐B)。由雙重否定律和德摩根律可知：┐┐A?A,┐(A∧B)?┐A∨┐B,┐(A∨B)?┐A∧┐B。利用分配律，可得:A∧(B∨C)?(A∧B)∨(A∧C)，A∨(B∧C)?(A∨B)∧(A∨C)。使用這些等值式，便可將任一公式化成與之等值的析取范式或合取范式。

范式存在定理4/17/202422DiscreteMath.求給定公式的范式的步驟：(1)消去聯(lián)結(jié)詞→和?；(2)否定號┐的消去(雙重否定)或內(nèi)移(德摩根律)；(3)利用∨對∧的分配律求合取范式；利用∧對∨的分配律求析取范式。

求范式的步驟4/17/202423DiscreteMath.解:(1)合取范式：(p→q)?r?(┐p∨q)?r

?((┐p∨q)→r)∧(r→(┐p∨q))

?(┐(┐p∨q)∨r)∧(┐r∨(┐p∨q))

?((p∧┐q)∨r)∧(┐p∨q∨┐r)

?(p∨r)∧(┐q∨r)∧(┐p∨q∨┐r)(2)析取范式(p→q)?r?((p∧┐q)∨r)∧(┐p∨q∨┐r)?(p∧┐q∧┐p)∨(p∧┐q∧q)∨(p∧┐q∧┐r)∨(r∧┐p)∨(r∧q)∨(r∧┐r)

?(p∧┐q∧┐r)∨(┐p∧r)∨(q∧r)(消去→)(消去?)(消去→)(否定號內(nèi)移,結(jié)合律,交換律)(∨對∧的分配律)(見上述第一至四步)(∧對∨的分配律)(矛盾律和同一律)例2.7求公式(p→q)?r的析取范式與合取范式。4/17/202424DiscreteMath.注：在演算過程中，利用交換律，可使每個簡單析取式或簡單合取式中命題變項都按字典序出現(xiàn)。上述求析取范式的過程中，第二步和第三步結(jié)果都是析取范式。這說明命題公式的析取范式是不唯一的。同樣，合取范式也是不唯一的。為了得到唯一的規(guī)范化形式的范式，需要定義主析取范式和主合取范式。為此，先引入如下極小項和極大項概念。范式的注解4/17/202425DiscreteMath.定義2.4在含有n個命題變項的簡單合取式(簡單析取式)中，若每個命題變項和它的否定式恰好出現(xiàn)一個且僅出現(xiàn)一次，并且命題變項或其否定式按下標(biāo)從小到大或按字典序排列)，則稱該簡單合取式(簡單析取式)為極小項(極大項)。注：由于每個命題變項在極小項中以原形或否定式形式出現(xiàn)且僅出現(xiàn)一次，因而n個命題變項共可產(chǎn)生2n

個不同的極小項。每個極小項僅有一個成真賦值，若一個極小項的成真賦值對應(yīng)的二進(jìn)制數(shù)轉(zhuǎn)化為十進(jìn)制數(shù)為i，則將該極小項記為mi。類似地，n個命題變項可產(chǎn)生2n

個不同的極大項。每個極大項只有一個成假賦值。若一個極大項的成假賦值對應(yīng)的十進(jìn)制數(shù)為i，則將該極大項記為Mi

。極大、小項定義4/17/202426DiscreteMath.極小項極大項公式成真賦值名稱公式成假賦值名稱兩個變項p、q形成的極小項與極大項

00m001m110m211m300M001M110M211M3變項取1┐p∧┐q┐p∧qp∧┐qp∧qp∨qp∨┐q┐p∨q┐p∨┐q變項取0極大、小項真值表4/17/202427DiscreteMath.極小項

極大項

公式成真賦值名稱公式成假賦值名稱┐p∧┐q∧┐r000m0p∨q∨r000M0┐p∧┐q∧r001m1p∨q∨┐r001M1┐p∧q∧┐r010m2p∨┐q∨r010M2┐p∧q∧r011m3p∨┐q∨┐r011M3p∧┐q∧┐r100m4┐p∨q∨r100M4p∧┐q∧r101m5┐p∨q∨┐r101M5p∧q∧┐r110m6┐p∨┐q∨r110M6p∧q∧r111m7┐p∨┐q∨┐r111M7三個變項p,q,r形成的極小項與極大項變項取1變項取0極大、小項真值表（續(xù)）4/17/202428DiscreteMath.定理2.4設(shè)mi

與Mi

是命題變項p1,p2…,pn形成的極小項和極大項，則┐mi

?Mi，┐Mi?

mi

。證明：略，可從以上兩表驗證該定理。定義2.5如果由n個命題變項構(gòu)成的析取范式（合取范式）中所有的簡單合取式(簡單析取式)都是極小項（極大項),則稱該析取式（合取式）為主析取范式（主合取范式）。定理2.5任何命題公式都存在著與之等值的主析取范式和主合取范式，并且是唯一的。證明：見教材26頁。主范式定義4/17/202429DiscreteMath.注：主析取范式和主合取范式的求法：(1)先通過等值推演將所給的命題公式化為析取范式（合取范式）；(2)若某個簡單合取式（簡單析取式）A中既不含變項pi,又不含變項┐pi,則通過：A?A∧1?A∧(pi∨┐pi)?(A∧pi)∨(A∧┐pi)或：A?A∨0?A∨(pi∧┐pi)?(A∨pi)∧(A∨┐pi)補(bǔ)齊變項。(3)消去重復(fù)變項和矛盾式，如用p,mi,0分別代替p∧p，mi

∨mi和矛盾式，等。

主范式求法4/17/202430DiscreteMath.解:(1)主析取范式由例2.7知，(p→q)?r?(p∧┐q∧┐r)∨(┐p∧r)∨(q∧r)∵(┐p∧r)?┐p∧(┐q∨q)∧r

?(┐p∧┐q∧r)∨(┐p∧q∧r)

?m1∨m3(q∧r)?(┐p∨p)∧q∧r?(┐p∧q∧r)∨(p∧q∧r)?m3∨m7（p∧┐q∧┐r)?m4∴(p→q)?r?m1∨m3∨m4∨m7求公式(p→q)?r的主析(合)取范式。例2.84/17/202431DiscreteMath.(2)

主合取范式由例2.7知，(p→q)?r?(p∨r)∧(┐q∨r)∧(┐p∨q∨┐r)∵(p∨r)?p∨(q∧┐q)∨r?(p∨q∨r)∧(p∨┐q∨r)?M0∧M2(┐q∨r)?(p∧┐p)∨┐q∨r?(p∧┐q∨r)∧(┐p∨┐q∨r)?M2∧M6(┐p∨q∨┐r)?M5∴(p→q)?r?M0∧M2∧M5∧M6例2.8（續(xù)）4/17/202432DiscreteMath.例2.9求p→q的主析取范式和主合取范式解:(1)主合取范式p→q?┐p∨q?M2

(2)主析取范式p→q?(┐p∨q)

?(┐p∧(┐q∨q))∨((┐p∨p)∧q)?(┐p∧┐q)∨(┐p∧q)∨(┐p∧q)∨(p∧q)?(┐p∧┐q)∨(┐p∧q)∨(p∧q)

?m0∨m1∨m3例2.94/17/202433DiscreteMath.

主析取范式和主合取范式的用途（以主析取范式為例)。

1.求公式的成真與成假賦值對含有n個變項的命題公式A，若其主析取范式含s(0≤s≤2n)個極小項，則A有s個成真賦值，它們是極小項下標(biāo)的二進(jìn)制表示，其余2n–s個賦值都是成假賦值。例如，在例2.8中，(p→q)?r?m1∨m3∨m4∨m7,因各極小項含三個文字，故各極小項下標(biāo)的長為3的二進(jìn)制數(shù)001，011，100，111為該公式的成真賦值，而其余賦值000，010，101，110為成假賦值。范式的用途14/17/202434DiscreteMath.

2.判斷公式的類型設(shè)公式A中含n個變項，則(1)

A為重言式當(dāng)且僅當(dāng)A的主析取范式含全部2n

個極小項；(2)

A為矛盾式當(dāng)且僅當(dāng)A的主析取范式不含任取極小項。(此時，記A的主析取范式為0)。(3)

A為可滿足式當(dāng)且僅當(dāng)A的主析取范式中至少含一個極小項。范式的用途24/17/202435DiscreteMath.(1)┐(p→q)∧q;(2)p→(p∨q);(3)(p∨q)→r解：(1)┐(p→q)∧q

?┐(┐p∨q)∧q

?p∧┐q∧q

?0.

(2)p→(p∨q)?┐p∨p∨q

?(┐p∧(┐q∨q))∨(p∧(┐q∨q))∨((┐p∨p)∧q)

?(┐p∧┐q)∨(┐p∧q)∨(p∧┐q)∨(p∧q)∨(┐p∧q)∨(p∧q)

?(┐p∧┐q)∨(┐p∧q)∨(p∧┐q)∨(p∧q)

?m0∨m1∨m2∨m3`利用公式的主析取范式判斷公式的類型：注：另一種推演：p→(p∨q)?┐p∨p∨q?1∨q?1?m0∨m1∨m2∨m3該主析取范式含全部22個極小項，故p→(p∨q)是重言式。故

┐(p→q)∧q是矛盾式。例2.104/17/202436DiscreteMath.(3)（p∨q)→r

?┐(p∨q)∨r

?(┐p∧┐q)∨r

?(┐p∧┐q∧(┐r∨r))∨((┐p∨p)∧(┐q∨q)∧r)?(┐p∧┐q∧┐r)∨(┐p∧┐q∧r)∨(┐p∧┐q∧r)∨(┐p∧q∧r)∨(p∧┐q∧r)∨(p∧q∧r)

?m0∨m1∨m3∨m5∨m7故該公式是可滿足式,但不是重言式。例2.10（續(xù)）4/17/202437DiscreteMath.3.判斷兩公式是否等值設(shè)公式A,B共有n個變項。按n個變項求出A,B的主析取范式。若A與B有相同的主析取范式，則A?B;否則A?B。例2.11判斷下面兩組公式是否等值。(1)p與(p∧q)∨(p∧┐q);(2)(p→q)→r與(p∧q)→r解:(1)p?p∧(┐q∨q)?(p∧┐q)∨(p∧q)?m2∨m3而(p∧q)∨(p∧┐q)?m2∨m3，故p?(p∧q)∨(p∧┐q）(2)

因(p→q)→r?m1∨m3∨m4∨m5∨m7

而(p∧q)→r?m0∨m1∨m2∨m3∨m4∨m5∨m7故(p→q)→r?(p∧q)→r范式的用途34/17/202438DiscreteMath.例2.12某單位欲從三人A,B,C中挑選1～2人出國進(jìn)修。由于工作需要選派時要滿足以下條件(1)若A去，則C同去；(2)若B去，則C不能去；(3)若C不去，則A或B可以去。問應(yīng)如何選派？解：設(shè)p:派A去；q：派B去；r:派C去。由條件得：(p→r)∧(q→┐r)∧(┐r→(p∨q))經(jīng)演算得其主析取范式為：m1∨m2∨m5m1=┐p∧┐q∧r;m2=┐p∧q∧┐r;

m5=p∧┐q∧r由此可知,有3種選派方案：(1)C去，A,B都不去；(2)B去，A,C都不去；(3)A,C同去，B不去。4.利用主析取范式和主合取式解決應(yīng)用問題范式的用途44/17/202439DiscreteMath.1．主合取范式可由主析取范式直接得到。設(shè)公式A含有n個變項，A的主析取范式為未在主析取范式中出現(xiàn)的極小項設(shè)為事實上，因則A的主合取范式為：故關(guān)于主合取范式的兩點說明14/17/202440DiscreteMath.例2.13由公式的主析取范式，求主合取范式：(1)

A?m1∨m2,(A含兩個變項p,q);(2)B?m1∨m2∨m3，(B含三個變項p,q,r)。解：(1)主析取范式中未出現(xiàn)的極小項為：m0,m3,故A的主合取范式為：A?M0∧M3。(2)主析取范式中未出現(xiàn)的極小項為m0,m4,m5,m6,m7，故A的主合取范式為：A?M0∧M4∧M5∧M6∧M7。2.重言式與矛盾式的主合取范式重言式無成假賦值，因而其主合取范式不含任何極大項。重言式的主合取范式記為1。矛盾式無成真賦值，故其主合取范式含有所有2n個極大項。關(guān)于主合取范式的兩點說明24/17/202441DiscreteMath.含n個變項的所有公式，共有22n種不同的主析取范式(主合取范式)。這是因為n個變項共可產(chǎn)生2n個極小項(極大項)，因而可產(chǎn)生22n種主析取范式(主合取范式)(因每個極小項可以在主析取范式中出現(xiàn)或不出現(xiàn))。A?B當(dāng)且僅當(dāng)A與B有相同的真值表，又當(dāng)且僅當(dāng)A與B有相同的主析取范式(主合取范式)?？梢姡嬷当砼c主析取范式(主合取范式)是描述命題公式標(biāo)準(zhǔn)形式的兩種不同的等價形式。本節(jié)結(jié)束語4/17/202442DiscreteMath.定義2.6稱映射F:{0,1}n→{0,1}為n元真值函數(shù)。其中{0,1}n表示由0，1組成的長為n的字符串集合。注：1元真值函數(shù)有22=4個；2元真值函數(shù)有222=16個；3元真值函數(shù)有223=256個。4個一元真值函數(shù)pF0(1)F1(1)F2(1)F3(1)0100011011§2.3聯(lián)結(jié)詞的完備集4/17/202443DiscreteMath.pqF0(2)F1(2)F2(2)F3(2)F4(2)F5(2)F6(2)F7(2)0000000000010000111110001100111101010101pqF8(2)F9(2)F10(2)F11(2)F12