清華離散數(shù)學(xué)(第2版)課件

2.2命題邏輯等值演算2.2.1等值式與等值演算等值式與基本等值式真值表法與等值演算法2.2.2聯(lián)結(jié)詞完備集真值函數(shù)聯(lián)結(jié)詞完備集與非聯(lián)結(jié)詞和或非聯(lián)結(jié)詞12.2命題邏輯等值演算2.2.1等值式與等值演算1等值式定義2.11若等價式AB是重言式,則稱A與B等值,記作AB,并稱AB是等值式說明:(1)是元語言符號,不要混同于和=(2)A與B等值當(dāng)且僅當(dāng)A與B在所有可能賦值下的真值都相同,即A與B有相同的真值表(3)n個命題變項(xiàng)的真值表共有個,故每個命題公式都有無窮多個等值的命題公式(4)可能有啞元出現(xiàn).在B中出現(xiàn),但不在A中出現(xiàn)的命題變項(xiàng)稱作A的啞元.同樣,在A中出現(xiàn),但不在B中出現(xiàn)的命題變項(xiàng)稱作B的啞元.啞元的值不影響命題公式的真值.2等值式定義2.11若等價式AB是重言式,則稱A與B等值真值表法例1

判斷(pq)與

pq

是否等值解結(jié)論:(pq)(pq)

pqpqpq(pq)pq(pq)(pq)001101110110100110011001110010013真值表法例1判斷(pq)與pq是否等值結(jié)真值表法(續(xù))例2判斷下述3個公式之間的等值關(guān)系:

p(qr),(pq)r,(pq)r解

pqrp(qr)(pq)r(pq)r000101001111010101011111100111101111110000111111p(qr)與(pq)r等值,但與(pq)r不等值4真值表法(續(xù))例2判斷下述3個公式之間的等值關(guān)系:p基本等值式雙重否定律

AA冪等律

AAA,AAA交換律

ABBA,ABBA結(jié)合律(AB)CA(BC)(AB)CA(BC)分配律

A(BC)(AB)(AC)

A(BC)(AB)(AC)德摩根律

(AB)AB

(AB)AB吸收律

A(AB)A,A(AB)A5基本等值式雙重否定律AA5基本等值式(續(xù))零律

A11,A00同一律

A0A,

A1A排中律

AA1矛盾律

AA0蘊(yùn)涵等值式

ABAB等價等值式

AB(AB)(BA)假言易位

ABBA等價否定等值式

ABAB歸謬論(AB)(AB)A6基本等值式(續(xù))零律等值演算等值演算:由已知的等值式推演出新的等值式的過程置換規(guī)則:若AB,則(B)(A)

例3

證明

p(qr)(pq)r證

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

（結(jié)合律）(pq)r

（德摩根律）(pq)r

（蘊(yùn)涵等值式）7等值演算等值演算:由已知的等值式推演出新的等值式的過程7實(shí)例等值演算不能直接證明兩個公式不等值.證明兩個公式不等值的基本思想是找到一個賦值使一個成真,另一個成假.例4證明:p(qr)(pq)r方法一真值表法（見例2）方法二觀察法.容易看出000使左邊成真,使右邊成假.方法三先用等值演算化簡公式,再觀察.8實(shí)例等值演算不能直接證明兩個公式不等值.證明兩個公式不8實(shí)例例5

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

解q(pq)

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

q(pq)（德摩根律）

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

p0（矛盾律）

0（零律）該式為矛盾式.9實(shí)例例5用等值演算法判斷下列公式的類型9實(shí)例(續(xù))(2)(pq)(qp)解(pq)(qp)

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

(pq)(pq)（交換律）

1該式為重言式.10實(shí)例(續(xù))(2)(pq)(qp)10實(shí)例(續(xù))(3)((pq)(pq))r)解((pq)(pq))r)

(p(qq))r

（分配律）

p1r

（排中律）

pr

（同一律）非重言式的可滿足式.如101是它的成真賦值,000是它的成假賦值.總結(jié):A為矛盾式當(dāng)且僅當(dāng)A0;A為重言式當(dāng)且僅當(dāng)A1說明:演算步驟不惟一,應(yīng)盡量使演算短些11實(shí)例(續(xù))(3)((pq)(pq))r)總結(jié)真值函數(shù)定義2.12稱F:{0,1}n{0,1}為n元真值函數(shù)n元真值函數(shù)共有個每一個命題公式對應(yīng)于一個真值函數(shù)每一個真值函數(shù)對應(yīng)無窮多個命題公式1元真值函數(shù)

p

000111010112真值函數(shù)定義2.12稱F:{0,1}n{0,1}為n元真2元真值函數(shù)

pq

0000000000010000111110001100111101010101pq

0011111111010000111110001100111101010101132元真值函數(shù)pq13聯(lián)結(jié)詞完備集定義2.13

設(shè)S是一個聯(lián)結(jié)詞集合,如果任何n(n1)元真值函數(shù)都可以由僅含S中的聯(lián)結(jié)詞構(gòu)成的公式表示,則稱S是聯(lián)結(jié)詞完備集定理2.1下述聯(lián)結(jié)詞集合都是完備集:(1)S1={,,,,}(2)S2={,,,}(3)S3={,,}(4)S4={,}(5)S5={,}(6)S6={,}AB(AB)(BA)ABABAB(AB)(AB)AB(AB)AB(A)B

AB14聯(lián)結(jié)詞完備集定義2.13設(shè)S是一個聯(lián)結(jié)詞集合,如果任何n復(fù)合聯(lián)結(jié)詞與非式:pq(pq),稱作與非聯(lián)結(jié)詞或非式:pq(pq),稱作或非聯(lián)結(jié)詞pq為真當(dāng)且僅當(dāng)p,q不同時為真pq為真當(dāng)且僅當(dāng)p,q不同時為假定理2.2{},{}是聯(lián)結(jié)詞完備集證p(pp)pppq(pq)(pq)(pq)(pq)得證{}是聯(lián)結(jié)詞完備集.對于{}可類似證明.15復(fù)合聯(lián)結(jié)詞與非式:pq(pq),稱作與非聯(lián)結(jié)2.3范式2.3.1析取范式與合取范式簡單析取式與簡單合取式析取范式與合取范式2.3.2主析取范式與主合取范式極小項(xiàng)與極大項(xiàng)主析取范式與主合取范式主范式的用途162.3范式2.3.1析取范式與合取范式16簡單析取式與簡單合取式文字:命題變項(xiàng)及其否定的統(tǒng)稱簡單析取式:有限個文字構(gòu)成的析取式如p,q,pq,pqr,…簡單合取式:有限個文字構(gòu)成的合取式如p,q,pq,pqr,…定理2.3

(1)一個簡單析取式是重言式當(dāng)且僅當(dāng)它同時含某個命題變項(xiàng)和它的否定(2)一個簡單合取式是矛盾式當(dāng)且僅當(dāng)它同時含某個命題變項(xiàng)和它的否定17簡單析取式與簡單合取式文字:命題變項(xiàng)及其否定的統(tǒng)稱17析取范式與合取范式析取范式:由有限個簡單合取式組成的析取式

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

A1A2Ar,其中A1,A2,,Ar是簡單析取式范式:析取范式與合取范式的統(tǒng)稱

定理2.4(1)一個析取范式是矛盾式當(dāng)且僅當(dāng)它的每一個簡單合取式都是矛盾式(2)一個合取范式是重言式當(dāng)且僅當(dāng)它的每一個簡單析取式都是重言式18析取范式與合取范式析取范式:由有限個簡單合取式組成的析取式1范式存在定理定理2.5

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

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

(AB)AB19范式存在定理定理2.5任何命題公式都存在著與之等值的析取范范式存在定理(續(xù))(3)使用分配律A(BC)(AB)(AC)求合取范式

A(BC)(AB)(AC)求析取范式例1

求(pq)r的析取范式與合取范式解(pq)r

(pq)r

(pq)r

析取范式(pr)(qr)合取范式注意:公式的析取范式與合取范式不惟一.20范式存在定理(續(xù))(3)使用分配律20極小項(xiàng)與極大項(xiàng)定義2.17

在含有n個命題變項(xiàng)的簡單合取式(簡單析取式)中,若每個命題變項(xiàng)均以文字的形式出現(xiàn)且僅出現(xiàn)一次，而且第i(1in)個文字(按下標(biāo)或字母順序排列)出現(xiàn)在左起第i位上,稱這樣的簡單合取式(簡單析取式)為極小項(xiàng)(極大項(xiàng))說明:(1)

n個命題變項(xiàng)產(chǎn)生2n個極小項(xiàng)和2n個極大項(xiàng)(2)2n個極小項(xiàng)(極大項(xiàng))均互不等值(3)用mi表示第i個極小項(xiàng),其中i是該極小項(xiàng)成真賦值的十進(jìn)制表示.用Mi表示第i個極大項(xiàng),其中i是該極大項(xiàng)成假賦值的十進(jìn)制表示,mi(Mi)稱為極小項(xiàng)(極大項(xiàng))的名稱.

21極小項(xiàng)與極大項(xiàng)定義2.17在含有n個命題變項(xiàng)的簡單合取式(極小項(xiàng)與極大項(xiàng)(續(xù))定理2.6設(shè)mi與Mi是由同一組命題變項(xiàng)形成的極小項(xiàng)和極大項(xiàng),則mi

Mi,Mi

mi極小項(xiàng)極大項(xiàng)公式成真賦值名稱公式成假賦值名稱pq00m0

pq00M0

pq01m1

pq01M1pq10m2

pq10M2

pq11m3

pq11M3p,q形成的極小項(xiàng)與極大項(xiàng)22極小項(xiàng)與極大項(xiàng)(續(xù))定理2.6設(shè)mi與Mi是由同一組命題主析取范式與主合取范式主析取范式:由極小項(xiàng)構(gòu)成的析取范式主合取范式:由極大項(xiàng)構(gòu)成的合取范式例如，n=3,命題變項(xiàng)為p,q,r時，(pqr)(pqr)

m1m3

是主析取范式

(pqr)(pqr)

M1M5

是主合取范式定理2.7任何命題公式都存在著與之等值的主析取范式和主合取范式,并且是惟一的.23主析取范式與主合取范式主析取范式:由極小項(xiàng)構(gòu)成的析取范式23求主析取范式的步驟設(shè)公式A含命題變項(xiàng)p1,p2,…,pn(1)求A的析取范式A=B1B2…Bs,其中Bj是簡單合取式j(luò)=1,2,…,s

(2)若某個Bj既不含pi,又不含pi,則將Bj展開成

BjBj(pipi)(Bjpi)(Bjpi)重復(fù)這個過程,直到所有簡單合取式都是長度為n的極小項(xiàng)為止(3)消去重復(fù)出現(xiàn)的極小項(xiàng),即用mi代替mimi(4)將極小項(xiàng)按下標(biāo)從小到大排列24求主析取范式的步驟設(shè)公式A含命題變項(xiàng)p1,p2,…,pn24求主合取范式的步驟設(shè)公式A含命題變項(xiàng)p1,p2,…,pn(1)求A的合取范式A=B1B2…Bs,其中Bj是簡單析取式j(luò)=1,2,…,s

(2)若某個Bj既不含pi,又不含pi,則將Bj展開成

BjBj(pipi)(Bjpi)(Bjpi)重復(fù)這個過程,直到所有簡單析取式都是長度為n的極大項(xiàng)為止(3)消去重復(fù)出現(xiàn)的極大項(xiàng),即用Mi代替MiMi(4)將極大項(xiàng)按下標(biāo)從小到大排列25求主合取范式的步驟設(shè)公式A含命題變項(xiàng)p1,p2,…,pn25實(shí)例例1(續(xù))

求(pq)r的主析取范式與主合取范式解(1)(pq)r

(pq)r

pq

(pq)1同一律(pq)(rr)排中律

(pqr)(pqr)分配律

m4m5r(pp)(qq)r

同一律,排中律(pqr)(pqr)(pqr)(pqr)m0m2m4m6

分配律得(pq)r

m0m2m4m5m6可記作(0,2,4,5,6)26實(shí)例例1(續(xù))求(pq)r的主析取范式與主合取范實(shí)例(續(xù))(2)(pq)r

(pr)(qr)

pr

p0r

同一律p(qq)r矛盾律(pqr)(pqr)

分配律M1M3qr

(pp)qr

同一律,矛盾律(pqr)(pqr)分配律M3M7得

(pq)rM1M3M7可記作(1,3,7)27實(shí)例(續(xù))(2)(pq)r(pr)(快速求法設(shè)公式含有n個命題變項(xiàng),則長度為k的簡單合取式可展開成2n-k個極小項(xiàng)的析取例如公式含p,q,r

q

(pqr)(pqr)(pqr)(pqr)m2m3m6m7長度為k的簡單析取式可展開成2n-k個極大項(xiàng)的合取例如pr

(pqr)(pqr)

M1M328快速求法設(shè)公式含有n個命題變項(xiàng),則28實(shí)例例2(1)求A(pq)(pqr)r的主析取范式解用快速求法(1)pq

(pqr)(pqr)m2m3pqrm1r(pqr)(pqr)(pqr)(pqr)m1m3m5m7得A

m1m2m3m5m7(1,2,3,5,7)29實(shí)例例2(1)求A(pq)(pqr實(shí)例(續(xù))(2)求B

p(pqr)的主合取范式解p(pqr)(pqr)(pqr)(pqr)M4M5M6M7pqrM1得BM1M4M5M6M7(1,4,5,6,7)30實(shí)例(續(xù))(2)求Bp(pqr)的主合取范主析取范式的用途(1)求公式的成真賦值和成假賦值設(shè)公式A含n個命題變項(xiàng),A的主析取范式有s個極小項(xiàng),則A有s個成真賦值,它們是極小項(xiàng)下標(biāo)的二進(jìn)制表示,其余2n-s個賦值都是成假賦值例如

(pq)r

m0m2m4m5m6

成真賦值:000,010,100,101,110;成假賦值:001,011,11131主析取范式的用途(1)求公式的成真賦值和成假賦值31主析取范式的用途(續(xù))(2)判斷公式的類型

設(shè)A含n個命題變項(xiàng)，則

A為重言式當(dāng)且僅當(dāng)A的主析取范式含2n個極小項(xiàng)A為矛盾式當(dāng)且僅當(dāng)

A的主析取范式不含任何極小項(xiàng),記作0A為可滿足式當(dāng)且僅當(dāng)A的主析取范式中至少含一個極小項(xiàng)32主析取范式的用途(續(xù))(2)判斷公式的類型32實(shí)例例3用主析取范式判斷公式的類型:(1)A

(pq)q(2)B

p(pq)(3)C(pq)r解(1)A

(

pq)q(pq)q0矛盾式(2)B

p(pq)1m0m1m2m3

重言式(3)C(pq)r(pq)r(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)m0m1m3m5m7

非重言式的可滿足式33實(shí)例例3用主析取范式判斷公式的類型:33主析取范式的用途(續(xù))(3)判斷兩個公式是否等值例4用主析取范式判斷下面2組公式是否等值:(1)p與(pq)(pq)解pp(qq)(pq)(pq)m2m3(pq)(pq)(pq)(pq)

(pq)(pq)m2m3故p(pq)(pq)34主析取范式的用途(續(xù))(3)判斷兩個公式是否等值34實(shí)例(續(xù))(2)(pq)r與p(qr)解(pq)r

(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)m1m3m5m6m7p(qr)(pq)(pr)(pqr)(pqr)(pqr)(pqr)m5m6m7故(pq)r

p(qr)35實(shí)例(續(xù))(2)(pq)r與p(qr)35實(shí)例例5某單位要從A,B,C三人中選派若干人出國考察,需滿足下述條件:(1)若A去,則C必須去;(2)若B去,則C不能去;(3)A和B必須去一人且只能去一人.問有幾種可能的選派方案?解記p:派A去,q:派B去,r:派C去(1)pr,(2)qr,(3)(pq)(pq)求下式的成真賦值A(chǔ)=(pr)(qr)((pq)(pq))36實(shí)例例5某單位要從A,B,C三人中選派若干人出國考察,需實(shí)例(續(xù))求A的主析取范式A=(pr)(qr)((pq)(pq))(pr)(qr)((pq)(pq))((pq)(pr)(rq)(rr))((pq)(pq))((pq)(pq))((pr)(pq))

((rq)(pq))((pq)(pq))((pr)(pq))((rq)(pq))(pqr)(pqr)成真賦值:101,010結(jié)論:方案1派A與C去,方案2派B去37實(shí)例(續(xù))求A的主析取范式37主合取范式由主析取范式求主合取范式設(shè)沒有出現(xiàn)的極小項(xiàng)是其中t=2n-s,于是38主合取范式由主析取范式求主合取范式?jīng)]有出現(xiàn)的極小項(xiàng)是其中t=主合取范式(續(xù))例6求A=(pqr)(pqr)(pqr)的主合取范式解A

m1m3m7

M0M2M4M5M6矛盾式的主合取范式含全部2n個極大項(xiàng)重言式的主合取范式不含任何極大項(xiàng),記作139主合取范式(續(xù))例6求A=(pqr)(pq2.2命題邏輯等值演算2.2.1等值式與等值演算等值式與基本等值式真值表法與等值演算法2.2.2聯(lián)結(jié)詞完備集真值函數(shù)聯(lián)結(jié)詞完備集與非聯(lián)結(jié)詞和或非聯(lián)結(jié)詞402.2命題邏輯等值演算2.2.1等值式與等值演算1等值式定義2.11若等價式AB是重言式,則稱A與B等值,記作AB,并稱AB是等值式說明:(1)是元語言符號,不要混同于和=(2)A與B等值當(dāng)且僅當(dāng)A與B在所有可能賦值下的真值都相同,即A與B有相同的真值表(3)n個命題變項(xiàng)的真值表共有個,故每個命題公式都有無窮多個等值的命題公式(4)可能有啞元出現(xiàn).在B中出現(xiàn),但不在A中出現(xiàn)的命題變項(xiàng)稱作A的啞元.同樣,在A中出現(xiàn),但不在B中出現(xiàn)的命題變項(xiàng)稱作B的啞元.啞元的值不影響命題公式的真值.41等值式定義2.11若等價式AB是重言式,則稱A與B等值真值表法例1

判斷(pq)與

pq

是否等值解結(jié)論:(pq)(pq)

pqpqpq(pq)pq(pq)(pq)0011011101101001100110011100100142真值表法例1判斷(pq)與pq是否等值結(jié)真值表法(續(xù))例2判斷下述3個公式之間的等值關(guān)系:

p(qr),(pq)r,(pq)r解

pqrp(qr)(pq)r(pq)r000101001111010101011111100111101111110000111111p(qr)與(pq)r等值,但與(pq)r不等值43真值表法(續(xù))例2判斷下述3個公式之間的等值關(guān)系:p基本等值式雙重否定律

AA冪等律

AAA,AAA交換律

ABBA,ABBA結(jié)合律(AB)CA(BC)(AB)CA(BC)分配律

A(BC)(AB)(AC)

A(BC)(AB)(AC)德摩根律

(AB)AB

(AB)AB吸收律

A(AB)A,A(AB)A44基本等值式雙重否定律AA5基本等值式(續(xù))零律

A11,A00同一律

A0A,

A1A排中律

AA1矛盾律

AA0蘊(yùn)涵等值式

ABAB等價等值式

AB(AB)(BA)假言易位

ABBA等價否定等值式

ABAB歸謬論(AB)(AB)A45基本等值式(續(xù))零律等值演算等值演算:由已知的等值式推演出新的等值式的過程置換規(guī)則:若AB,則(B)(A)

例3

證明

p(qr)(pq)r證

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

（結(jié)合律）(pq)r

（德摩根律）(pq)r

（蘊(yùn)涵等值式）46等值演算等值演算:由已知的等值式推演出新的等值式的過程7實(shí)例等值演算不能直接證明兩個公式不等值.證明兩個公式不等值的基本思想是找到一個賦值使一個成真,另一個成假.例4證明:p(qr)(pq)r方法一真值表法（見例2）方法二觀察法.容易看出000使左邊成真,使右邊成假.方法三先用等值演算化簡公式,再觀察.47實(shí)例等值演算不能直接證明兩個公式不等值.證明兩個公式不8實(shí)例例5

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

解q(pq)

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

q(pq)（德摩根律）

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

p0（矛盾律）

0（零律）該式為矛盾式.48實(shí)例例5用等值演算法判斷下列公式的類型9實(shí)例(續(xù))(2)(pq)(qp)解(pq)(qp)

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

(pq)(pq)（交換律）

1該式為重言式.49實(shí)例(續(xù))(2)(pq)(qp)10實(shí)例(續(xù))(3)((pq)(pq))r)解((pq)(pq))r)

(p(qq))r

（分配律）

p1r

（排中律）

pr

（同一律）非重言式的可滿足式.如101是它的成真賦值,000是它的成假賦值.總結(jié):A為矛盾式當(dāng)且僅當(dāng)A0;A為重言式當(dāng)且僅當(dāng)A1說明:演算步驟不惟一,應(yīng)盡量使演算短些50實(shí)例(續(xù))(3)((pq)(pq))r)總結(jié)真值函數(shù)定義2.12稱F:{0,1}n{0,1}為n元真值函數(shù)n元真值函數(shù)共有個每一個命題公式對應(yīng)于一個真值函數(shù)每一個真值函數(shù)對應(yīng)無窮多個命題公式1元真值函數(shù)

p

000111010151真值函數(shù)定義2.12稱F:{0,1}n{0,1}為n元真2元真值函數(shù)

pq

0000000000010000111110001100111101010101pq

0011111111010000111110001100111101010101522元真值函數(shù)pq13聯(lián)結(jié)詞完備集定義2.13

設(shè)S是一個聯(lián)結(jié)詞集合,如果任何n(n1)元真值函數(shù)都可以由僅含S中的聯(lián)結(jié)詞構(gòu)成的公式表示,則稱S是聯(lián)結(jié)詞完備集定理2.1下述聯(lián)結(jié)詞集合都是完備集:(1)S1={,,,,}(2)S2={,,,}(3)S3={,,}(4)S4={,}(5)S5={,}(6)S6={,}AB(AB)(BA)ABABAB(AB)(AB)AB(AB)AB(A)B

AB53聯(lián)結(jié)詞完備集定義2.13設(shè)S是一個聯(lián)結(jié)詞集合,如果任何n復(fù)合聯(lián)結(jié)詞與非式:pq(pq),稱作與非聯(lián)結(jié)詞或非式:pq(pq),稱作或非聯(lián)結(jié)詞pq為真當(dāng)且僅當(dāng)p,q不同時為真pq為真當(dāng)且僅當(dāng)p,q不同時為假定理2.2{},{}是聯(lián)結(jié)詞完備集證p(pp)pppq(pq)(pq)(pq)(pq)得證{}是聯(lián)結(jié)詞完備集.對于{}可類似證明.54復(fù)合聯(lián)結(jié)詞與非式:pq(pq),稱作與非聯(lián)結(jié)2.3范式2.3.1析取范式與合取范式簡單析取式與簡單合取式析取范式與合取范式2.3.2主析取范式與主合取范式極小項(xiàng)與極大項(xiàng)主析取范式與主合取范式主范式的用途552.3范式2.3.1析取范式與合取范式16簡單析取式與簡單合取式文字:命題變項(xiàng)及其否定的統(tǒng)稱簡單析取式:有限個文字構(gòu)成的析取式如p,q,pq,pqr,…簡單合取式:有限個文字構(gòu)成的合取式如p,q,pq,pqr,…定理2.3

(1)一個簡單析取式是重言式當(dāng)且僅當(dāng)它同時含某個命題變項(xiàng)和它的否定(2)一個簡單合取式是矛盾式當(dāng)且僅當(dāng)它同時含某個命題變項(xiàng)和它的否定56簡單析取式與簡單合取式文字:命題變項(xiàng)及其否定的統(tǒng)稱17析取范式與合取范式析取范式:由有限個簡單合取式組成的析取式

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

A1A2Ar,其中A1,A2,,Ar是簡單析取式范式:析取范式與合取范式的統(tǒng)稱

定理2.4(1)一個析取范式是矛盾式當(dāng)且僅當(dāng)它的每一個簡單合取式都是矛盾式(2)一個合取范式是重言式當(dāng)且僅當(dāng)它的每一個簡單析取式都是重言式57析取范式與合取范式析取范式:由有限個簡單合取式組成的析取式1范式存在定理定理2.5

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

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

(AB)AB58范式存在定理定理2.5任何命題公式都存在著與之等值的析取范范式存在定理(續(xù))(3)使用分配律A(BC)(AB)(AC)求合取范式

A(BC)(AB)(AC)求析取范式例1

求(pq)r的析取范式與合取范式解(pq)r

(pq)r

(pq)r

析取范式(pr)(qr)合取范式注意:公式的析取范式與合取范式不惟一.59范式存在定理(續(xù))(3)使用分配律20極小項(xiàng)與極大項(xiàng)定義2.17

在含有n個命題變項(xiàng)的簡單合取式(簡單析取式)中,若每個命題變項(xiàng)均以文字的形式出現(xiàn)且僅出現(xiàn)一次，而且第i(1in)個文字(按下標(biāo)或字母順序排列)出現(xiàn)在左起第i位上,稱這樣的簡單合取式(簡單析取式)為極小項(xiàng)(極大項(xiàng))說明:(1)

n個命題變項(xiàng)產(chǎn)生2n個極小項(xiàng)和2n個極大項(xiàng)(2)2n個極小項(xiàng)(極大項(xiàng))均互不等值(3)用mi表示第i個極小項(xiàng),其中i是該極小項(xiàng)成真賦值的十進(jìn)制表示.用Mi表示第i個極大項(xiàng),其中i是該極大項(xiàng)成假賦值的十進(jìn)制表示,mi(Mi)稱為極小項(xiàng)(極大項(xiàng))的名稱.

60極小項(xiàng)與極大項(xiàng)定義2.17在含有n個命題變項(xiàng)的簡單合取式(極小項(xiàng)與極大項(xiàng)(續(xù))定理2.6設(shè)mi與Mi是由同一組命題變項(xiàng)形成的極小項(xiàng)和極大項(xiàng),則mi

Mi,Mi

mi極小項(xiàng)極大項(xiàng)公式成真賦值名稱公式成假賦值名稱pq00m0

pq00M0

pq01m1

pq01M1pq10m2

pq10M2

pq11m3

pq11M3p,q形成的極小項(xiàng)與極大項(xiàng)61極小項(xiàng)與極大項(xiàng)(續(xù))定理2.6設(shè)mi與Mi是由同一組命題主析取范式與主合取范式主析取范式:由極小項(xiàng)構(gòu)成的析取范式主合取范式:由極大項(xiàng)構(gòu)成的合取范式例如，n=3,命題變項(xiàng)為p,q,r時，(pqr)(pqr)

m1m3

是主析取范式

(pqr)(pqr)

M1M5

是主合取范式定理2.7任何命題公式都存在著與之等值的主析取范式和主合取范式,并且是惟一的.62主析取范式與主合取范式主析取范式:由極小項(xiàng)構(gòu)成的析取范式23求主析取范式的步驟設(shè)公式A含命題變項(xiàng)p1,p2,…,pn(1)求A的析取范式A=B1B2…Bs,其中Bj是簡單合取式j(luò)=1,2,…,s

(2)若某個Bj既不含pi,又不含pi,則將Bj展開成

BjBj(pipi)(Bjpi)(Bjpi)重復(fù)這個過程,直到所有簡單合取式都是長度為n的極小項(xiàng)為止(3)消去重復(fù)出現(xiàn)的極小項(xiàng),即用mi代替mimi(4)將極小項(xiàng)按下標(biāo)從小到大排列63求主析取范式的步驟設(shè)公式A含命題變項(xiàng)p1,p2,…,pn24求主合取范式的步驟設(shè)公式A含命題變項(xiàng)p1,p2,…,pn(1)求A的合取范式A=B1B2…Bs,其中Bj是簡單析取式j(luò)=1,2,…,s

(2)若某個Bj既不含pi,又不含pi,則將Bj展開成

BjBj(pipi)(Bjpi)(Bjpi)重復(fù)這個過程,直到所有簡單析取式都是長度為n的極大項(xiàng)為止(3)消去重復(fù)出現(xiàn)的極大項(xiàng),即用Mi代替MiMi(4)將極大項(xiàng)按下標(biāo)從小到大排列64求主合取范式的步驟設(shè)公式A含命題變項(xiàng)p1,p2,…,pn25實(shí)例例1(續(xù))

求(pq)r的主析取范式與主合取范式解(1)(pq)r

(pq)r

pq

(pq)1同一律(pq)(rr)排中律

(pqr)(pqr)分配律

m4m5r(pp)(qq)r

同一律,排中律(pqr)(pqr)(pqr)(pqr)m0m2m4m6

分配律得(pq)r

m0m2m4m5m6可記作(0,2,4,5,6)65實(shí)例例1(續(xù))求(pq)r的主析取范式與主合取范實(shí)例(續(xù))(2)(pq)r

(pr)(qr)

pr

p0r

同一律p(qq)r矛盾律(pqr)(pqr)

分配律M1M3qr

(pp)qr

同一律,矛盾律(pqr)(pqr)分配律M3M7得

(pq)rM1M3M7可記作(1,3,7)66實(shí)例(續(xù))(2)(pq)r(pr)(快速求法設(shè)公式含有n個命題變項(xiàng),則長度為k的簡單合取式可展開成2n-k個極小項(xiàng)的析取例如公式含p,q,r

q

(pqr)(pqr)(pqr)(pqr)m2m3m6m7長度為k的簡單析取式可展開成2n-k個極大項(xiàng)的合取例如pr

(pqr)(pqr)

M1M367快速求法設(shè)公式含有n個命題變項(xiàng),則28實(shí)例例2(1)求A(pq)(pqr)r的主析取范式解用快速求法(1)pq

(pqr)(pqr)m2m3pqrm1r(pqr)(pqr)(pqr)(pqr)m1m3m5m7得A

m1m2m3m5m7(1,2,3,5,7)68實(shí)例例2(1)求A(pq)(pqr實(shí)例(續(xù))(2)求B

p(pqr)的主合取范式解p(pqr)(pqr)(pqr)(pqr)M4M5M6M7pqrM1得BM1M4M5M6M7(1,4,5,6,7)69實(shí)例(續(xù))(2)求Bp(pqr)的主合取范主析取范式的用途(1)求公式的成真賦值和成假賦值設(shè)公式A含n個命題變項(xiàng)