真值函數(shù)-1元真值函數(shù)-2元真值函數(shù)省名師優(yōu)質(zhì)課賽課獲獎(jiǎng)?wù)n件市賽課一等獎(jiǎng)?wù)n件

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

{0,1}為n元真值函數(shù)n元真值函數(shù)共有個(gè)每一個(gè)命題公式對(duì)應(yīng)于一個(gè)真值函數(shù)每一個(gè)真值函數(shù)對(duì)應(yīng)無窮多個(gè)命題公式1元真值函數(shù)

p

00011101012.2命題邏輯等值演算（續(xù)）第1頁12元真值函數(shù)

pq

0000000000010000111110001100111101010101pq

0011111111010000111110001100111101010101第2頁2聯(lián)結(jié)詞完備集定義2.13

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

1)元真值函數(shù)都能夠由僅含S中聯(lián)結(jié)詞組成公式表示,則稱S是聯(lián)結(jié)詞完備集定理2.1下述聯(lián)結(jié)詞集合都是完備集:(1)S1={

,

,

,

,

}(2)S2={

,

,

,

}(3)S3={

,

,

}(4)S4={

,

}(5)S5={

,

}(6)S6={

,

}A

B(A

B)(B

A)A

B

A

BA

B

(A

B)

(A

B)A

B

(A

B)A

B

(A)B

A

B第3頁3復(fù)合聯(lián)結(jié)詞與非式:p

q(p

q),

稱作與非聯(lián)結(jié)詞或非式:p

q(p

q),

稱作或非聯(lián)結(jié)詞p

q為真當(dāng)且僅當(dāng)p,q不一樣時(shí)為真p

q為真當(dāng)且僅當(dāng)p,q不一樣時(shí)為假定理2.2{

},{

}是聯(lián)結(jié)詞完備集證

p(p

p)

p

pp

q(p

q)(p

q)(p

q)(p

q)得證{

}是聯(lián)結(jié)詞完備集.對(duì)于{

}可類似證實(shí).第4頁42.3范式2.3.1析取范式與合取范式簡(jiǎn)單析取式與簡(jiǎn)單合取式析取范式與合取范式2.3.2主析取范式與主合取范式極小項(xiàng)與極大項(xiàng)第5頁5簡(jiǎn)單析取式與簡(jiǎn)單合取式文字:命題變項(xiàng)及其否定統(tǒng)稱簡(jiǎn)單析取式:有限個(gè)文字組成析取式如p,

q,p

q,p

q

r,…簡(jiǎn)單合取式:有限個(gè)文字組成合取式如p,

q,p

q,p

q

r,…定理2.3

(1)一個(gè)簡(jiǎn)單析取式是重言式當(dāng)且僅當(dāng)它同時(shí)含某個(gè)命題變項(xiàng)和它否定(2)一個(gè)簡(jiǎn)單合取式是矛盾式當(dāng)且僅當(dāng)它同時(shí)含某個(gè)命題變項(xiàng)和它否定第6頁6析取范式與合取范式析取范式:由有限個(gè)簡(jiǎn)單合取式組成析取式

A1

A2

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

A1

A2

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

定理2.4

(1)一個(gè)析取范式是矛盾式當(dāng)且僅當(dāng)它每一個(gè)簡(jiǎn)單合取式都是矛盾式(2)一個(gè)合取范式是重言式當(dāng)且僅當(dāng)它每一個(gè)簡(jiǎn)單析取式都是重言式第7頁7范式存在定理定理2.5

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

,

A

B

A

B

A

B

(

A

B)

(A

B)(2)否定聯(lián)結(jié)詞

內(nèi)移或消去

A

A

(A

B)

A

B

(A

B)

A

B(3)使用分配律A

(B

C)

(A

B)

(A

C)求合取范式

A

(B

C)

(A

B)

(A

C)求析取范式第8頁8范式存在定理(續(xù))例1

求

(p

q)

r析取范式與合取范式解

(p

q)

r

(

p

q)

r

(p

q)

r

析取范式

(p

r)(q

r)合取范式注意:公式析取范式與合取范式不惟一.第9頁9極小項(xiàng)與極大項(xiàng)定義2.17

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

i

n)個(gè)文字(按下標(biāo)或字母次序排列)出現(xiàn)在左起第i位上,稱這么簡(jiǎn)單合取式(簡(jiǎn)單析取式)為極小項(xiàng)(極大項(xiàng))Note:(1)

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

第10頁10極小項(xiàng)與極大項(xiàng)(續(xù))定理2.6設(shè)mi與Mi是由同一組命題變項(xiàng)形成極小項(xiàng)和極大項(xiàng),則

mi

Mi,

Mi

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

p

q00m0

p

q00M0

p

q01m1

p

q01M1p

q10m2

p

q10M2

p

q11m3

p

q11M3p,q形成極小項(xiàng)與極大項(xiàng)第11頁11主析取范式與主合取范式主析取范式:由極小項(xiàng)組成析取范式主合取范式:由極大項(xiàng)組成合取范式比如，n=3,命題變項(xiàng)為p,q,r時(shí)，(

p

q

r)

(

p

q

r)

m1

m3

是主析取范式

(p

q

r)

(

p

q

r)

M1

M5

是主合取范式定理2.7任何命題公式都存在著與之等值主析取范式和主合取范式,而且是惟一.第12頁12求主析取范式步驟設(shè)公式A含命題變項(xiàng)p1,p2,…,pn(1)求A析取范式A

=B1

B2

…

Bs,其中Bj是簡(jiǎn)單合取式j(luò)=1,2,…,s

(2)若某個(gè)Bj既不含pi,又不含

pi,則將Bj展開成

Bj

Bj

(pi

pi)(Bj

pi)(Bj

pi)重復(fù)這個(gè)過程,直到全部簡(jiǎn)單合取式都是長(zhǎng)度為n極小項(xiàng)為止(3)消去重復(fù)出現(xiàn)極小項(xiàng),即用mi代替mi

mi(4)將極小項(xiàng)按下標(biāo)從小到大排列第13頁13求主合取范式步驟設(shè)公式A含命題變項(xiàng)p1,p2,…,pn(1)求A合取范式A

=B1

B2

…

Bs,其中Bj是簡(jiǎn)單析取式j(luò)=1,2,…,s

(2)若某個(gè)Bj既不含pi,又不含

pi,則將Bj展開成

Bj

Bj

(pi

pi)(Bj

pi)(Bj

pi)重復(fù)這個(gè)過程,直到全部簡(jiǎn)單析取式都是長(zhǎng)度為n極大項(xiàng)為止(3)消去重復(fù)出現(xiàn)極大項(xiàng),即用Mi代替Mi

Mi(4)將極大項(xiàng)按下標(biāo)從小到大排列第14頁14實(shí)例例1(續(xù))

求

(p

q)

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

(p

q)

r

(p

q)

r

p

q

(p

q)1同一律

(p

q)(r

r)排中律

(p

q

r)

(p

q

r)分配律

m4

m5

r

(p

p)(q

q)

r

同一律,排中律

(p

q

r)(p

q

r)(p

q

r)(p

q

r)

m0

m2

m4

m6

分配律得

(p

q)

r

m0

m2

m4

m5

m6可記作

(0,2,4,5,6)第15頁15實(shí)例(續(xù))(2)

(p

q)

r

(p

r)(q

r)

p

r

p0r

同一律

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

M1

M3

M7可記作

(1,3,7)第16頁16快速求法設(shè)公式含有n個(gè)命題變項(xiàng),則長(zhǎng)度為k簡(jiǎn)單合取式可展開成2n

k個(gè)極小項(xiàng)析取比如公式含p,q,r

q

(p

q

r)(p

q

r)(p

q

r)(p

q

r)

m2

m3

m6

m7長(zhǎng)度為k簡(jiǎn)單析取式可展開成2n

k個(gè)極大項(xiàng)合取比如p

r

(p

q

r)(p

q

r)

M1

M3第17頁17實(shí)例例2(1)求A(p

q)(p

q

r)

r主析取范式解用快速求法(1)

p

q

(

p

q

r)

(

p

q

r)

m2

m3

p

q

r

m1r(

p

q

r)

(

p

q

r)

(p

q

r)

(p

q

r)

m1

m3

m5

m7得A

m1

m2

m3

m5

m7

(1,2,3,5,7)第18頁18實(shí)例(續(xù))(2)求B

p(p

q

r)主合取范式解

p(

p

q

r)(

p

q

r)

(

p

q

r)

(

p

q

r)

M4

M5

M6

M7p

q

r

M1得B

M1

M4

M5

M6

M7

(1,4,5,6,7)第19頁19主析取范式用途(1)求公式成真賦值和成假賦值設(shè)公式A含n個(gè)命題變項(xiàng),A主析取范式有s個(gè)極小項(xiàng),則A有s個(gè)成真賦值,它們是極小項(xiàng)下標(biāo)二進(jìn)制表示,其余2n

s個(gè)賦值都是成假賦值比如

(p

q)

r

m0

m2

m4

m5

m6

成真賦值:000,010,100,101,110;成假賦值:001,011,111第20頁20主析取范式用途(續(xù))(2)判斷公式類型

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

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

A主析取范式不含任何極小項(xiàng),記作0A為可滿足式當(dāng)且僅當(dāng)A主析取范式中最少含一個(gè)極小項(xiàng)第21頁21實(shí)例例3用主析取范式判斷公式類型:(1)A

(p

q)

q(2)B

p(p

q)(3)C(p

q)r解(1)A

(

p

q)

q

(p

q)

q0矛盾式(2)B

p(p

q)1m0

m1

m2

m3

重言式(3)C

(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

m1

m3

m5

m7

非重言式可滿足式第22頁22主析取范式用途(續(xù))(3)判斷兩個(gè)公式是否等值例4用主析取范式判斷下面2組公式是否等值:(1)p與(p

q)(p

q)解p

p(q

q)(p

q)(p

q)

m2

m3(p

q)(p

q)(p

q)(p

q)

(p

q)(p

q)

m2

m3故p

(p

q)(p

q)第23頁23實(shí)例(續(xù))(2)(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

m5

m6

m7p(q

r)(p

q)(p

r)(p

q

r)(p

q

r)(p

q

r)(p

q

r)

m5

m6

m7故(p

q)r

p(q

r)第24頁24實(shí)例例5某單位要從A,B,C三人選派若干人出國考查,需滿足下述條件:(1)若A去,則C必須去;(2)若B去,則C不能去;(3)A和B必須去一人且只能去一人.問有幾個(gè)可能選派方