離散數(shù)學(xué)之等值演算

1.3命題邏輯等值演算

等值式基本等值式等值演算置換規(guī)則2021/5/91等值式

定義若等價(jià)式A

B是重言式，則稱A與B等值，記作A

B，并稱A

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

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

q)

((

p

q)

(

r

r))中，r為左邊公式的啞元.用真值表可驗(yàn)證兩個(gè)公式是否等值請(qǐng)驗(yàn)證：p

(q

r)

(p

q)

rp

(q

r)(p

q)

r

2021/5/92基本等值式

雙重否定律

:

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)2021/5/93基本等值式(續(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

02021/5/94基本等值式(續(xù))蘊(yùn)涵等值式:A

B

A

B等價(jià)等值式:A

B

(A

B)

(B

A)假言易位:A

B

B

A等價(jià)否定等值式:A

B

A

B歸謬論:(A

B)

(A

B)

A注意:A,B,C代表任意的命題公式牢記這些等值式是繼續(xù)學(xué)習(xí)的基礎(chǔ)2021/5/95等值演算與置換規(guī)則

等值演算:

由已知的等值式推演出新的等值式的過程置換規(guī)則：若A

B,則

(B)

(A)

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

(1)等值關(guān)系的性質(zhì)：自反、對(duì)稱、傳遞

(2)基本的等值式

(3)置換規(guī)則2021/5/96應(yīng)用舉例——證明兩個(gè)公式等值

例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ī)則）

說明:也可以從右邊開始演算（請(qǐng)做一遍）因?yàn)槊恳徊蕉加弥脫Q規(guī)則，故可不寫出熟練后，基本等值式也可以不寫出

2021/5/97應(yīng)用舉例——證明兩個(gè)公式不等值例2證明:p

(q

r)(p

q)

r

用等值演算不能直接證明兩個(gè)公式不等值,證明兩個(gè)公式不等值的基本思想是找到一個(gè)賦值使一個(gè)成真,另一個(gè)成假.

方法一真值表法（自己證）方法二觀察賦值法.容易看出000,010等是左邊的的成真賦值，是右邊的成假賦值.

方法三用等值演算先化簡(jiǎn)兩個(gè)公式，再觀察.2021/5/98應(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（零律）由最后一步可知，該式為矛盾式.

2021/5/99例3(續(xù))(2)(p

q)

(

q

p)解

(p

q)

(

q

p)

(

p

q)

(q

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

(

p

q)

(

p

q)（交換律）

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

2021/5/910例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)盡量使演算短些2021/5/9111.4范式

析取范式與合取范式

主析取范式與主合取范式

2021/5/912析取范式與合取范式

文字:命題變項(xiàng)及其否定的總稱簡(jiǎn)單析取式:有限個(gè)文字構(gòu)成的析取式如p,

q,p

q,p

q

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

q,p

q,p

q

r,…析取范式:由有限個(gè)簡(jiǎn)單合取式組成的析取式

A1

A2

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

A1

A2

Ar,其中A1,A2,,Ar是簡(jiǎn)單析取式2021/5/913析取范式與合取范式(續(xù))范式:析取范式與合取范式的總稱

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

單個(gè)文字既是簡(jiǎn)單析取式，又是簡(jiǎn)單合取式p

q

r,

p

q

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

2021/5/914命題公式的范式

定理

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

(1)消去A中的

,

（若存在）

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

的內(nèi)移或消去

(3)使用分配律

對(duì)

分配（析取范式）

對(duì)

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

例

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

q)

r解(p

q)

r

(

p

q)

r

（消去

）

p

q

r

（結(jié)合律）這既是A的析取范式（由3個(gè)簡(jiǎn)單合取式組成的析取式），又是A的合取范式（由一個(gè)簡(jiǎn)單析取式組成的合取式）2021/5/916求公式的范式舉例(續(xù))(2)B=(p

q)

r解

(p

q)

r

(

p

q)

r

（消去第一個(gè)

）

(

p

q)

r

（消去第二個(gè)

）

(p

q)

r

（否定號(hào)內(nèi)移——德

摩根律）這一步已為析取范式（兩個(gè)簡(jiǎn)單合取式構(gòu)成）繼續(xù)：

(p

q)

r

(p

r)

(q

r)（

對(duì)

分配律）這一步得到合取范式（由兩個(gè)簡(jiǎn)單析取式構(gòu)成）

2021/5/9172元真值函數(shù)對(duì)應(yīng)的真值表pq0001101100000000000011110011001101010101

pq0001101111111111000011110011001101010101

2021/5/918極小項(xiàng)與極大項(xiàng)

定義

在含有n個(gè)命題變項(xiàng)的簡(jiǎn)單合取式(簡(jiǎn)單析取式)中，若每個(gè)命題變項(xiàng)均以文字的形式出現(xiàn)且僅出現(xiàn)一次，稱這樣的簡(jiǎn)單合取式(簡(jiǎn)單析取式)為極小項(xiàng)(極大項(xiàng)）.說明：n個(gè)命題變項(xiàng)產(chǎn)生2n個(gè)極小項(xiàng)和2n個(gè)極大項(xiàng)2n個(gè)極小項(xiàng)（極大項(xiàng)）均互不等值在極小項(xiàng)和極大項(xiàng)中文字均按下標(biāo)或字母順序排列用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))的名稱.

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

mi

Mi,

Mi

mi

2021/5/919極小項(xiàng)與極大項(xiàng)(續(xù))由p,q兩個(gè)命題變項(xiàng)形成的極小項(xiàng)與極大項(xiàng)

公式

成真賦值名稱

公式

成假賦值名稱

p

q

p

qp

qp

q00011011m0m1m2m3

p

q

p

q

p

q

p

q

00011011

M0M1M2M3

極小項(xiàng)

極大項(xiàng)

2021/5/920

由p,q,r三個(gè)命題變項(xiàng)形成的極小項(xiàng)與極大項(xiàng)

極小項(xiàng)

極大項(xiàng)

公式

成真賦值名稱

公式

成假賦值名稱

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

2021/5/921主析取范式與主合取范式

主析取范式:由極小項(xiàng)構(gòu)成的析取范式主合取范式:由極大項(xiàng)構(gòu)成的合取范式例如，n=3,命題變項(xiàng)為p,q,r時(shí)，

(

p

q

r)

(

p

q

r)

m1

m3

是主析取范式

(p

q

r)

(

p

q

r)

M1

M5

是主合取范式

A的主析取范式:與A等值的主析取范式

A的主合取范式:與A等值的主合取范式.

2021/5/922主析取范式與主合取范式(續(xù))定理

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

用等值演算法求公式的主范式的步驟：

(1)先求析取范式（合取范式）

(2)將不是極小項(xiàng)（極大項(xiàng)）的簡(jiǎn)單合取式（簡(jiǎn)單析取式）化成與之等值的若干個(gè)極小項(xiàng)的析?。O大項(xiàng)的合取），需要利用同一律（零律）、排中律（矛盾律）、分配律、冪等律等.

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

2021/5/923求公式的主范式例

求公式

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

2021/5/925求公式的主范式(續(xù))(2)求A的主合取范式

(p

q)

r

(p

r)

(q

r),（合取范式）

①

p

r

p

(q

q)

r

(p

q

r)

(p

q

r)

M0

M2,

②2021/5/926求公式的主范式(續(xù))

q

r

(p

p)

q

r

(p

q

r)

(

p

q

r)

M0

M4③

②,③代入①并排序，得

(p

q)

r

M0

M2

M4（主合取范式）

2021/5/927主范式的用途——與真值表相同

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

例如(p

q)

r

m1

m3

m5

m6

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

類似地，由主合取范式也可立即求出成假賦值和成真賦值.2021/5/928主范式的用途(續(xù))(2)判斷公式的類型

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

A為重言式

A的主析取范式含2n個(gè)極小項(xiàng)

A的主合取范式為1.A為矛盾式

A的主析取范式為0

A的主合取范式含2n個(gè)極大項(xiàng)A為非重言式的可滿足式

A的主析取范式中至少含一個(gè)且不含全部極小項(xiàng)

A的主合取范式中至少含一個(gè)且不含全部極大項(xiàng)

2021/5/929主范式的用途(續(xù))例

用主析取范式判斷下述兩個(gè)公式是否等值：⑴

p

(q

r)與

(p

q)

r⑵

p

(q

r)與

(p

q)

r解

p

(q

r)=m0

m1

m2

m3

m4

m5

m7

(p

q)

r=m0

m1

m2

m3

m4

m5

m7(p

q)

r=m1

m3

m4

m5

m7故⑴中的兩公式等值，而⑵的不等值.

(3)判斷兩個(gè)公式是否等值說明：由公式A的主析取范式確定它的主合取范式，反之亦然.

用公式A的真值表求A的主范式.2021/5/930主范式的用途(續(xù))例

某公司要從趙、錢、孫、李、周五名新畢業(yè)的大學(xué)生中選派一些人出國(guó)學(xué)習(xí).選派必須滿足以下條件：

(1)若趙去，錢也去；

(2)李、周兩人中至少有一人去；

(3)錢、孫兩人中有一人去且僅去一人；

(4)孫、李兩人同去或同不去；

(5)若周去，則趙、錢也去.試用主析取范式法分析該公司如何選派他們出國(guó)？2021/5/931例(續(xù))解此類問題的步驟為：①

將簡(jiǎn)單命題符號(hào)化②

寫出各復(fù)合命題③

寫出由②中復(fù)合命題組成的合取式

④

求③中所得公式的主析取范式

2021/5/932例(續(xù))解

①

設(shè)p：派趙去，q：派錢去，r：派孫去，

s：派李去，u：派周去.②(1)(p

q)(2)(s

u)(3)