離散數(shù)學(xué)課件 第一章

離散數(shù)學(xué)

DiscreteMathematics教師：喻建平張勇2010.3.151聯(lián)系方式Tel：26732054QQ:110329Office:科技樓1516房間

2

研究離散結(jié)構(gòu)的數(shù)學(xué)分科。（辭海）DiscreteMath.離散數(shù)學(xué)研究離散量的結(jié)構(gòu)及其相互關(guān)系的數(shù)學(xué)學(xué)科，是現(xiàn)代數(shù)學(xué)的一個重要分支。3離散數(shù)學(xué)的內(nèi)容：數(shù)理邏輯（MathematicsLogic)集合論(Sets)組合論（Combination)圖論（GraphTheory)代數(shù)結(jié)構(gòu)（AlgbraStructure)線性代數(shù)(LinearAlgbra)概率論（PropobilityTheory)……

4

離散數(shù)學(xué)的由來與發(fā)展:歷史:計數(shù):自然數(shù)發(fā)展:圖論:Konigsberg七橋問題(一筆畫)（柯尼斯堡，又譯：哥尼斯堡，德語：K?nigsberg，今KALININGRAD[加里寧格勒]，俄羅斯）新生:計算機(jī):二進(jìn)制運(yùn)算5離散數(shù)學(xué)課程設(shè)置：計算機(jī)系核心課程信息類專業(yè)必修課程其它類專業(yè)的重要選修課程6離散數(shù)學(xué)的后繼課程：數(shù)據(jù)結(jié)構(gòu)、編譯技術(shù)、算法分析與設(shè)計、人工智能、數(shù)據(jù)庫、程序設(shè)計語言、操作系統(tǒng)、理論計算機(jī)科學(xué)基礎(chǔ)、……7開設(shè)目的：

通過離散數(shù)學(xué)的學(xué)習(xí)，不但可以掌握處理離散結(jié)構(gòu)的描述工具和方法，為后續(xù)課程的學(xué)習(xí)創(chuàng)造條件，而且可以提高抽象思維和嚴(yán)格的邏輯推理能力，為將來參與創(chuàng)新性的研究和開發(fā)工作打下堅實的基礎(chǔ)。8離散數(shù)學(xué)課程的學(xué)習(xí)方法:強(qiáng)調(diào)：邏輯性、抽象性；注重：概念、方法與應(yīng)用9教材：耿素云、屈婉玲、張立昂離散數(shù)學(xué)（第四版）清華大學(xué)出版社2008年10上課時間：1~17周周一1、2節(jié)；周三3、4節(jié)考核：考勤：30%（作業(yè)+簽到，低于1/3取消考試資格）考試：70%11教學(xué)內(nèi)容:

數(shù)理邏輯（MathematicsLogic）集合論（Sets）代數(shù)結(jié)構(gòu)（AlgebraStructure）圖論（GraphTheory）

組合論（Combination）12數(shù)理邏輯部分第1章命題邏輯第2章一階邏輯13第1章命題邏輯

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

命題與真值原子命題復(fù)合命題聯(lián)結(jié)詞

15命題與真值

命題:判斷結(jié)果唯一的陳述句命題的真值:判斷的結(jié)果真值的取值:真與假真命題:真值為真的命題假命題:真值為假的命題注意:感嘆句、祈使句、疑問句都不是命題陳述句中的悖論以及判斷結(jié)果不惟一確定的也不是命題16例

下列句子中那些是命題？

(1)是無理數(shù).(2)2+5＝8.(3)x+5＞3.(4)你有鉛筆嗎？(5)這只兔子跑得真快呀！(6)請不要講話！(7)我正在說謊話.真命題假命題真值不確定疑問句感嘆句祈使句悖論(3)~(7)都不是命題17命題的分類

簡單命題(原子命題)：簡單陳述句構(gòu)成的命題

復(fù)合命題：由簡單命題與聯(lián)結(jié)詞按一定規(guī)則復(fù)合而成的命題

18簡單命題符號化

用小寫英文字母p,q,r,…,pi,qi,ri(i≥1）表示簡單命題用“1”表示真，用“0”表示假例如，令p：是有理數(shù)，則p的真值為0q：2+5=7，則q的真值為1

19聯(lián)結(jié)詞與復(fù)合命題

1.否定式與否定聯(lián)結(jié)詞“

”

定義

設(shè)p為命題，復(fù)合命題“非p”（或“p的否定”）稱為p的否定式，記作

p.符號

稱作否定聯(lián)結(jié)詞，并規(guī)定

p

為真當(dāng)且僅當(dāng)p為假.p﹁p011020聯(lián)結(jié)詞與復(fù)合命題

2.合取式與合取聯(lián)結(jié)詞“∧”

定義

設(shè)p,q為二命題,復(fù)合命題“p并且q”(或“p與q”)稱為p與q的合取式，記作p∧q.∧稱作合取聯(lián)結(jié)詞，并規(guī)定p∧q為真當(dāng)且僅當(dāng)p與q同時為真注意：描述合取式的靈活性與多樣性分清簡單命題與復(fù)合命題pqp∧q00001010011121例

將下列命題符號化.(1)王曉既用功又聰明.(2)王曉不僅聰明，而且用功.(3)王曉雖然聰明，但不用功.(4)

張輝與王麗都是三好生.(5)張輝與王麗是同學(xué).解

令

p：王曉用功，q：王曉聰明，則(1)p∧q(2)p∧q(3)p∧

q.22

例(續(xù))

令

r:張輝是三好學(xué)生，s:王麗是三好學(xué)生(4)r∧s.(5)令

t:張輝與王麗是同學(xué)，t是簡單命題.說明:(1)~(4)說明描述合取式的靈活性與多樣性.(5)中“與”聯(lián)結(jié)的是兩個名詞，整個句子是一個簡單命題.23聯(lián)結(jié)詞與復(fù)合命題(續(xù))

定義設(shè)p,q為二命題，復(fù)合命題“p或q”稱作p與q的析取式，記作p∨q.∨稱作析取聯(lián)結(jié)詞，并規(guī)定p∨q為假當(dāng)且僅當(dāng)p與q同時為假.3.析取式與析取聯(lián)結(jié)詞“∨”pqp∨q00001110111124聯(lián)結(jié)詞與復(fù)合命題(續(xù))例

將下列命題符號化(1)2或4是素數(shù).(2)2或3是素數(shù).(3)4或6是素數(shù).(4)小元元只能拿一個蘋果或一個梨.(5)王曉紅生于1975年或1976年.

25解

令p:2是素數(shù),q:3是素數(shù),r:4是素數(shù),s:6是素數(shù),則(1),(2),(3)均為相容或.分別符號化為:p∨r,p∨q,r∨s,

它們的真值分別為1,1,0.

而(4),(5)為排斥或.

令t:小元元拿一個蘋果，u:小元元拿一個梨，則(4)符號化為(t∧

u)∨(

t∧u).

令v:王曉紅生于1975年,w:王曉紅生于1976年,則(5)既可符號化為(v∧

w)∨(

v∧w),又可符號化為v∨w,為什么?

26聯(lián)結(jié)詞與復(fù)合命題(續(xù))

定義設(shè)p,q為二命題，復(fù)合命題“如果p,則q”稱作p與q的蘊(yùn)涵式，記作p

q，并稱p是蘊(yùn)涵式的前件，q為蘊(yùn)涵式的后件.

稱作蘊(yùn)涵聯(lián)結(jié)詞，并規(guī)定，p

q為假當(dāng)且僅當(dāng)p為真q為假.4.蘊(yùn)涵式與蘊(yùn)涵聯(lián)結(jié)詞“

”pqp→q00101110011127p

q的邏輯關(guān)系：q為p的必要條件“如果p，則q”的不同表述法很多：若p，就q只要p，就qp僅當(dāng)q只有q

才p除非q,才p或除非q,否則非p.當(dāng)p為假時，p

q為真常出現(xiàn)的錯誤：不分充分與必要條件聯(lián)結(jié)詞與復(fù)合命題(續(xù))28例

設(shè)p:天冷，q:小王穿羽絨服，將下列命題符號化

(1)只要天冷，小王就穿羽絨服.(2)因為天冷，所以小王穿羽絨服.(3)若小王不穿羽絨服，則天不冷.(4)只有天冷，小王才穿羽絨服.(5)除非天冷，小王才穿羽絨服.(6)除非小王穿羽絨服，否則天不冷.(7)如果天不冷，則小王不穿羽絨服.(8)小王穿羽絨服僅當(dāng)天冷的時候.注意：

p

q與

q

p

等值（真值相同）p

qp

qp

qp

qq

p

q

pq

pq

p29聯(lián)結(jié)詞與復(fù)合命題(續(xù))定義設(shè)p，q為二命題，復(fù)合命題“p當(dāng)且僅當(dāng)q”稱作p與q的等價式，記作p

q.

稱作等價聯(lián)結(jié)詞.并規(guī)定p

q為真當(dāng)且僅當(dāng)p與q同時為真或同時為假.說明:(1)p

q的邏輯關(guān)系:p與q互為充分必要條件(2)p

q為真當(dāng)且僅當(dāng)p與q同真或同假5.等價式與等價聯(lián)結(jié)詞“

”pqp

q00101010011130例

求下列復(fù)合命題的真值(1)2+2＝4當(dāng)且僅當(dāng)3+3＝6.(2)2+2＝4當(dāng)且僅當(dāng)3是偶數(shù).(3)2+2＝4當(dāng)且僅當(dāng)太陽從東方升起.(4)2+2＝4當(dāng)且僅當(dāng)美國位于非洲.(5)函數(shù)

f(x)在x0

可導(dǎo)的充要條件是它在

x0連續(xù).它們的真值分別為1，0，1，0，0.31聯(lián)結(jié)詞與復(fù)合命題(續(xù))以上給出了5個聯(lián)結(jié)詞：

,

,

,

,

，組成一個聯(lián)結(jié)詞集合{

,

,

,

,

}，

聯(lián)結(jié)詞的優(yōu)先順序為：

,

,

,

,;

如果出現(xiàn)的聯(lián)結(jié)詞同級，又無括號時，則按從左到右的順序運(yùn)算;若遇有括號時，應(yīng)該先進(jìn)行括號中的運(yùn)算.

注意:本書中使用的

括號全為園括號.

321.2命題公式及分類命題變項與合式公式公式的賦值真值表命題的分類重言式矛盾式可滿足式33命題變項與合式公式

命題常項：簡單命題，也叫命題常元命題變項：真值不確定的陳述句，也叫命題變元定義

合式公式(命題公式,公式)遞歸定義如下：(1)單個命題常項或變項p,q,r,…,pi,qi,ri,…,0,1是合式公式(2)若A是合式公式，則(

A)也是合式公式(3)若A,B是合式公式，則(A

B),(A

B),(A

B),(A

B)也是合式公式(4)只有有限次地應(yīng)用(1)~(3)形成的符號串才是合式公式說明:元語言與對象語言的外層括號可以省去

34合式公式的層次

定義

(1)若公式A是單個的命題變項,則稱A為0層公式.(2)稱A是n+1(n≥0)層公式是指下面情況之一：(a)A=

B,B是n層公式；(b)A=B

C,其中B,C分別為i層和j層公式，且n=max(i,j)；(c)A=B

C,其中B,C的層次及n同(b)；(d)A=B

C,其中B,C的層次及n同(b)；(e)A=B

C,其中B,C的層次及n同(b).35合式公式的層次(續(xù))例如公式p0層

p1層

p

q2層

(p

q)

r3層

((

p

q)

r)

(

r

s)4層36公式的賦值

定義

給公式A中的命題變項p1,p2,…,pn指定一組真值稱為對A的一個賦值或解釋成真賦值:使公式為真的賦值成假賦值:使公式為假的賦值說明：

賦值

=

1

2…

n之間不加標(biāo)點(diǎn)符號，

i=0或1.

A中僅出現(xiàn)p1,p2,…,pn，給A賦值

1

2…

n是指p1=

1,p2=

2,…,pn=

n

A中僅出現(xiàn)p,

q,r,…,給A賦值

1

2

3…是指p=

1,q=

2,r=

3…

含n個變項的公式有2n個賦值.

37公式的賦值

命題賦值時應(yīng)注意下列事項：（1）確定所給句子是否為命題。（2）句子中聯(lián)結(jié)詞是否為命題聯(lián)結(jié)詞。（3）要正確的選擇原子命題和合適的命題聯(lián)結(jié)詞。解：設(shè)p：上午下雨；q：我去看電影；r：我在家里讀書；s：我在家里看報。本例可表示為：（

p

q）∧（p

（r∨s））。

例：假如上午不下雨，我去看電影，否則就在家里讀書或看報。

38真值表

真值表:公式A在所有賦值下的取值情況列成的表構(gòu)造真值表的方法如下：（1）找出公式A中的全部命題變元，并按一定的順序排列成P1，P2，…，Pn。（2）列出A的2n個解釋，賦值從00…0（n個）開始，按二進(jìn)制遞加順序依次寫出各賦值，直到11…1為止（或從11…1開始，按二進(jìn)制遞減順序?qū)懗龈髻x值，直到00…0為止），然后從低到高的順序列出A的層次。（3）根據(jù)賦值依次計算各層次的真值并最終計算出A的真值。39真值表

例給出公式的真值表A=(q

p)

q

p的真值表pqq

p

(q

p)

q

(q

p)

q

p

00011011

1011

0001

111140例B=(

p

q)

q的真值表pq

p

p

q

(

p

q)

(

p

q)

q00011011

1100110100100000實例41例C=(p

q)

r的真值表pqrp

q

r

(p

q)

r

000001010011100101110111

00111111

10101010

1110101042公式的類型

定義設(shè)A為一個命題公式(1)若A無成假賦值，則稱A為重言式(也稱永真式)(2)若A無成真賦值，則稱A為矛盾式(也稱永假式)(3)若A不是矛盾式，則稱A為可滿足式注意：重言式是可滿足式，但反之不真.上例中A為重言式，B為矛盾式，C為可滿足式

A=(q

p)

q

p，B=(

p

q)

q，C=(p

q)

r431.3等值演算

等值式基本等值式等值演算置換規(guī)則44等值式

定義設(shè)A和B是兩個命題公式，若等價式A

B是重言式，即A和B在任意賦值情況下都具有相同的真值，則稱A與B等值，記作A

B，并稱A

B是等值式。說明：定義中，A,B,

均為元語言符號,A或B中可能有啞元出現(xiàn).例如，在(p

q)

((

p

q)

(

r

r))中，r為左邊公式的啞元.

45等值式

用真值表可驗證兩個公式是否等值請驗證：p

(q

r)

(p

q)

rp

(q

r)(p

q)

r

性質(zhì)：定理設(shè)A、B、C是公式，則（1）A

A（2）若A

B則B

A（3）若A

B且B

C則A

C46基本等值式

設(shè)A、B、C是任意命題公式，則下述等價公式成立：雙重否定律

:

A

A等冪律：

A

A

A,A

A

A交換律:A

B

B

A,A

B

B

A結(jié)合律:(A

B)

C

A

(B

C)(A

B)

C

A

(B

C)分配律:A

(B

C)

(A

B)

(A

C)

A

(B

C)

(A

B)

(A

C)47基本等值式(續(xù))德·摩根律:

(A

B)

A

B

(A

B)

A

B吸收律:A

(A

B)

A,A

(A

B)

A零律:A

1

1,A

0

0同一律:A

0

A,

A

1

A排中律:A

A

1矛盾律:A

A

048基本等值式(續(xù))蘊(yùn)涵等值式:A

B

A

B等價等值式:A

B

(A

B)

(B

A)假言易位:A

B

B

A等價否定等值式:A

B

A

B歸謬論:(A

B)

(A

B)

A注意:牢記這些等值式是繼續(xù)學(xué)習(xí)的基礎(chǔ)49等值演算與置換規(guī)則

等值演算:由已知的等值式推演出新的等值式的過程置換規(guī)則：設(shè)

（A）是一個含有子公式A的命題公式，

（B）是用公式B置換了

（A）中的子公式A后得到的公式，如果A

B，那么

（A）

（B）。

簡言之：若A

B,則

(B)

(A)

等值演算的基礎(chǔ)：

(1)等值關(guān)系的性質(zhì)：自反、對稱、傳遞(2)基本的等值式(3)置換規(guī)則50應(yīng)用舉例——證明兩個公式等值

例1證明

p

(q

r)

(p

q)

r證

p

(q

r)

p

(

q

r)（蘊(yùn)涵等值式，置換規(guī)則）

(

p

q)

r

（結(jié)合律，置換規(guī)則）

(p

q)

r

（德

摩根律，置換規(guī)則）

(p

q)

r

（蘊(yùn)涵等值式，置換規(guī)則）

說明:也可以從右邊開始演算（請做一遍）因為每一步都用置換規(guī)則，故可不寫出熟練后，基本等值式也可以不寫出

51應(yīng)用舉例——證明兩個公式不等值例2證明:p

(q

r)(p

q)

r用等值演算不能直接證明兩個公式不等值,證明兩個公式不等值的基本思想是找到一個賦值使一個成真,另一個成假.方法一真值表法（自己證）方法二觀察賦值法.容易看出000,010等是左邊的的成真賦值，是右邊的成假賦值.方法三用等值演算先化簡兩個公式，再觀察.52應(yīng)用舉例——判斷公式類型

例3

用等值演算法判斷下列公式的類型(1)q

(p

q)

解q

(p

q)

q

(

p

q)（蘊(yùn)涵等值式）

q

(p

q)（德

摩根律）

p

(q

q)（交換律，結(jié)合律）

p

0（矛盾律）

0（零律）由最后一步可知，該式為矛盾式.

53例3(續(xù))(2)(p

q)

(

q

p)解(p

q)

(

q

p)

(

p

q)

(q

p)（蘊(yùn)涵等值式）

(

p

q)

(

p

q)（交換律）

1由最后一步可知，該式為重言式.問：最后一步為什么等值于1？

54例3(續(xù))(3)((p

q)

(p

q))

r)解((p

q)

(p

q))

r)

(p

(q

q))

r

（分配律）

p

1

r

（排中律）

p

r

（同一律）這不是矛盾式，也不是重言式，而是非重言式的可滿足式.如101是它的成真賦值,000是它的成假賦值.總結(jié)：A為矛盾式當(dāng)且僅當(dāng)A

0A為重言式當(dāng)且僅當(dāng)A

1說明：演算步驟不惟一,應(yīng)盡量使演算短些551.4聯(lián)結(jié)詞全功能集

復(fù)合聯(lián)結(jié)詞排斥或與非式或非式真值函數(shù)聯(lián)結(jié)詞全功能集56復(fù)合聯(lián)結(jié)詞

排斥或:設(shè)p，q為兩命題，復(fù)合命題“p、q之中恰有一個成立”稱為p與q的排斥或或異或即：p

q

(p

q)

(

p

q)pqp

q00001110111057復(fù)合聯(lián)結(jié)詞

與非式:設(shè)p，q為兩命題，復(fù)合命題“p與q的否定”稱為p與q的與非式。即：p

q(p

q)pqp↑q001011101110性質(zhì)：（1）p↑p

﹁（p∧p）

﹁p；（2）（p↑q）↑（p↑q）

﹁（p↑q）

p∧q；（3）（p↑p）↑（q↑q）

﹁p↑﹁q

p∨q。58復(fù)合聯(lián)結(jié)詞

或非式:設(shè)p，q為兩命題，復(fù)合命題“p或q的否定”稱為p與q的或非式。即：p

q(p

q)

pqp↓q001010100110性質(zhì)：（1）p↓p

﹁（p∨p）﹁p；（2）（p↓q）↓（p↓q）﹁（p↓q）p∨q；（3）（p↓p）↓（q↓q）﹁p↓﹁q﹁（﹁p∨﹁q）p∧q。59真值函數(shù)

問題：含n個命題變項的所有公式共產(chǎn)生多少個互不相同的真值表？答案為個，為什么？定義

稱定義域為{00…0,00…1,…,11…1}，值域為{0,1}的函數(shù)是n元真值函數(shù)，定義域中的元素是長為n的0,1串.常用F:{0,1}n

{0,1}表示F是n元真值函數(shù).共有個n元真值函數(shù).例如F:{0,1}2

{0,1}，且F(00)=F(01)=F(11)=0，F(xiàn)(01)=1，則F為一個確定的2元真值函數(shù).60命題公式與真值函數(shù)

對于任何一個含n個命題變項的命題公式A，都存在唯一的一個n元真值函數(shù)F為A的真值表.等值的公式對應(yīng)的真值函數(shù)相同.下表給出所有2元真值函數(shù)對應(yīng)的真值表,每一個含2個命題變項的公式的真值表都可以在下表中找到.

例如：p

q,

p

q,(

p

q)

(

(p

q)

q)等都對應(yīng)表中的612元真值函數(shù)對應(yīng)的真值表pq0001101100000000000011110011001101010101

pq0001101111111111000011110011001101010101

62聯(lián)結(jié)詞的全功能集

定義

在一個聯(lián)結(jié)詞的集合中，如果一個聯(lián)結(jié)詞可由集合中的其他聯(lián)結(jié)詞定義，則稱此聯(lián)結(jié)詞為冗余的聯(lián)結(jié)詞，否則稱為獨(dú)立的聯(lián)結(jié)詞.例如,在聯(lián)結(jié)詞集{

,

,

,

,

}中，由于

p

q

p

q,所以，

為冗余的聯(lián)結(jié)詞;類似地，

也是冗余的聯(lián)結(jié)詞.又在{

,

,

}中，由于

p

q(p

q)，所以，

是冗余的聯(lián)結(jié)詞.類似地，

也是冗余的聯(lián)結(jié)詞.

63聯(lián)結(jié)詞的全功能集(續(xù))定義

設(shè)S是一個聯(lián)結(jié)詞集合，如果任何n(n

1)元真值函數(shù)都可以由僅含S中的聯(lián)結(jié)詞構(gòu)成的公式表示，則稱S是聯(lián)結(jié)詞全功能集.說明：若S是聯(lián)結(jié)詞全功能集，則任何命題公式都可用S中的聯(lián)結(jié)詞表示.

若S1,S2是兩個聯(lián)結(jié)詞集合，且S1

S2.若S1是全功能集，則S2也是全功能集.

64聯(lián)結(jié)詞的全功能集(續(xù))定義若S是聯(lián)結(jié)詞的全功能集且S的任何真子集都不是全功能集（S中沒有冗余的聯(lián)結(jié)詞），則稱S是最小全功能集，又稱最小聯(lián)結(jié)詞組。定理{

，∧，∨，→，

}是聯(lián)結(jié)詞的全功能集。定理{

，∧，∨}是聯(lián)結(jié)詞的全功能集。

定理{

，∧}，{

、∨}，{

，→}是最小聯(lián)結(jié)詞全功能集。定理{↑}，{↓}是最小聯(lián)結(jié)詞全功能集。65聯(lián)結(jié)詞的全功能集實例(1)S1={

,

,

,

}(2)S2={

,

,

,

,

}

(3)S3={

,

}(4)S4={

,

}(5)S5={

,

}(6)S6={

}(7)S8={

}而{

},{

}等則不是聯(lián)結(jié)詞全功能集.Page14.

661.5對偶與范式

對偶式與對偶原理

析取范式與合取范式

主析取范式與主合取范式

67對偶式和對偶原理定義

在僅含有聯(lián)結(jié)詞,∧,∨的命題公式A中，將∨換成∧,∧換成∨，若A中含有0或1，就將0換成1，1換成0，所得命題公式稱為A的對偶式，記為A*.從定義不難看出，(A*)*還原成A例：公式（

P∨Q）∧（P∨

Q）的對偶式為：（

P∧Q）∨（P∧

Q）68對偶式和對偶原理定理

設(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)定理（對偶原理）設(shè)A，B為兩個命題公式，若A

B，則A*

B*.若A為重言式，則A*必是矛盾式？？Page15

69析取范式與合取范式

文字:命題變項及其否定的總稱簡單析取式:有限個文字構(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是簡單析取式70析取范式與合取范式(續(xù))范式:析取范式與合取范式的總稱

公式A的析取范式:與A等值的析取范式公式A的合取范式:與A等值的合取范式說明：

單個文字既是簡單析取式，又是簡單合取式p

q

r,

p

q

r既是析取范式，又是合取范式(為什么?)

71命題公式的范式

定理

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

,

（若存在）(2)否定聯(lián)結(jié)詞

的內(nèi)移或消去(3)使用分配律

對

分配（析取范式）

對

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

例

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

q)

r解(p

q)

r

(

p

q)

r

（消去

）

p

q

r

（結(jié)合律）這既是A的析取范式（由3個簡單合取式組成的析取式），又是A的合取范式（由一個簡單析取式組成的合取式）73求公式的范式舉例(續(xù))(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)成）

74極小項與極大項

定義

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

i

n）個文字出現(xiàn)在左起第i位上，稱這樣的簡單合取式（簡單析取式）為極小項（極大項）.說明：n個命題變項產(chǎn)生2n個極小項和2n個極大項2n個極小項（極大項）均互不等值用mi表示第i個極小項，其中i是該極小項成真賦值的十進(jìn)制表示.用Mi表示第i個極大項，其中i是該極大項成假賦值的十進(jìn)制表示,mi(Mi)稱為極小項(極大項)的名稱.

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

mi

Mi,

Mi

mi

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

公式

成真賦值名稱

公式

成假賦值名稱

p

q

p

qp

qp

q00011011m0m1m2m3

p

q

p

q

p

q

p

q

00011011

M0M1M2M3

極小項

極大項

76由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

77主析取范式與主合取范式

主析取范式:由極小項構(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等值的主合取范式.

78主析取范式與主合取范式(續(xù))定理

任何命題公式都存在著與之等值的主析取范式和主合取范式,并且是惟一的.

用等值演算法求公式的主范式的步驟：(1)先求析取范式（合取范式）(2)將不是極小項（極大項）的簡單合取式（簡單析取式）化成與之等值的若干個極小項的析取（極大項的合?。枰猛宦桑懵桑⑴胖新桑苈桑?、分配律、冪等律等.

(3)極小項（極大項）用名稱mi（Mi）表示，并按角標(biāo)從小到大順序排序.

79主析取范式與主合取范式(續(xù))用等值演算求主析取范式步驟如下：（1）求A的析取范式A'；（2）若A中某個簡單合取式m中沒有出現(xiàn)某個命題變元Pi或其否定

Pi，則將m作如下等價變換：m

m∧（Pi∨

Pi）

（m∧Pi）∨（m∧

Pi）（3）將重復(fù)出現(xiàn)的命題變元、矛盾式和重復(fù)出現(xiàn)的極小項都消去；（4）重復(fù)步驟（2）、（3），直到每一個簡單合取式都為極小項；（5）將極小項按腳標(biāo)由小到大的順序排列，并用∑表示。如m0∨m1∨m7可表示為∑（0，1，7）。80求公式的主范式例

求公式

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,②81求公式的主范式(續(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（主析取范式）

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

(p

q)

r

(p

r)

(q

r),（合取范式）

①

p

r

p

(q

q)

r

(p

q

r)

(p

q

r)

M0

M2,

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

q

r

(p

p)

q

r

(p

q

r)

(

p

q

r)

M0

M4③

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

q)

r

M0

M2

M4（主合取范式）

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

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

例如(p

q)

r

m1

m3

m5

m6

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

類似地，由主合取