離散數(shù)學(xué)第一章命題演算基礎(chǔ)-范式及其應(yīng)用省名師優(yōu)質(zhì)課賽課獲獎(jiǎng)?wù)n件市賽課一等獎(jiǎng)?wù)n件

第一章命題演算基礎(chǔ)1.1命題和聯(lián)結(jié)詞1.2真假性1.3范式及其應(yīng)用

1.3.1范式

1.3.2主范式1.3.3范式應(yīng)用1/52合取式、析取式定義1命題變元、或者命題變元否定、或由它們利用合取詞組成合式公式稱為合取式。定義2命題變元、或者命題變元否定、或由它們利用析取詞組成合式公式稱為析取式。例顯然，P，

P，P

Q，

P

Q

R均為合取式；

P，

P，P

Q，

P

Q

R均為析取式。2/52(一)解釋與合取式、析取式之間關(guān)系

定理1

任給一個(gè)成真解釋有且僅有一個(gè)合取式與之對應(yīng)；任給一個(gè)成假解釋有且僅有一個(gè)析取式與之對應(yīng)。反之亦然。例成真解釋(P，Q，R)=(T,F,T)

成假解釋(P，Q，R)=(F,F,T)合取式P

Q

R析取式P

Q

R3/52析取范式、合取范式定義3形如A1

A2

…

An公式稱為析取范式，

其中Ai(i=1,2…,n)為合取式。定義4形如A1

A2

…

An公式稱為合取范式，其中Ai(i=1,2…,n)為析取式。例如：P，

P，P

Q，P

Q

，(

P

Q)

(S

R)

均為析取范式。如：P，

P，P

Q，P

Q

，

(

P

Q)

(S

R)均為合取范式。4/52例:考查公式

=PQ析取范式有兩個(gè)成真解釋：

(T,T),(F,F),分別對應(yīng)于兩個(gè)合取式為P∧Q,P∧Q于是，有

=(P∧Q)∨(P∧Q)PQP

QTTTTFFFTFFFT5/52例:考查公式

=PQ合取范式成假解釋(T,F),(F,T),對應(yīng)析取式為

P∨Q,P∨Q于是，有：

=(P∨Q)∧(P∨Q)PQP

QTTTTFFFTFFFT6/52定理2任何命題演算公式均能夠化為合取范式，也能夠化為析取范式。證實(shí)：

(1)設(shè)公式

為永真公式 因?yàn)槿魏我粋€(gè)永真公式均與公式P

P邏輯等價(jià)，而P

P既是析取范式又是合取范式，所以公式既可表示為析取范式又可表示為合取范式。

(2)設(shè)公式為永假公式 因?yàn)槿魏我粋€(gè)永假公式均與公式P

P邏輯等價(jià)，而P

P既是析取范式又是合取范式，所以公式既可表示為析取范式又可表示為合取范式。7/52定理2證實(shí)(續(xù))(3)設(shè)公式

既非永真又非永假 設(shè)公式

成真解釋為

1，

2，……，

n，成假解釋為

1，

2，……，

t。 依據(jù)解釋和范式關(guān)系知： 對應(yīng)于成真解釋

1，

2，……，

n合取式為

1，

2，……，

n

對應(yīng)于成假解釋

1，

2，……，

t析取式為

1，

2，……，

t

而公式

1

2

……

n成真解釋為

1，

2，……，

n； 公式

1

2

……

t成假解釋為

1，

2，……，

t。 依據(jù)兩個(gè)公式邏輯等價(jià)定義知

=

1

2

……

n=

1

2

……

t

故公式

既可表示為析取范式又可表示為合取范式。8/52(二)析取范式和合取范式求解方法

等價(jià)變換法解釋法9/52等價(jià)變換法(1)利用前面介紹等價(jià)公式消去公式中聯(lián)結(jié)詞“

”和“

”；(2)重復(fù)使用等值公式，把否定詞內(nèi)移到命題變元上，等值公式以下：

(P

Q)=

P

Q

(P

Q)=

P

Q，

P=P(3)重復(fù)使用分配律將公式化為合取式析取或析取式合取，等值公式以下：

P

(Q

R)=(P

Q)

(P

R)

P

(Q

R)=(P

Q)

(P

R)10/52解釋法(1)求出公式全部成真(假)解釋；(2)寫出全部成真(假)解釋對應(yīng)有合(析)取式；(3)把全部合(析)取式用析(合)取詞聯(lián)結(jié)起來就組成析(合)取范式。11/52例(p11)

求公式范式

((P

Q)

(R

P))

((R

Q)

P)解法一：求析取范式原式=((

P

Q)(

R

P))

((

R

Q)

P)=(

(

P

Q)

(

R

P))((

(

R

Q)

P)=(P

Q)

(R

P)((R

Q)

P)=(P

Q)(R

P)(P

R)

(P

Q)=(P

Q)

(P

R)

(

P

R)12/52解法一：再求合取范式原式=(P

Q)

(P

R)

(

P

R)

(析取范式)

=(P(Q

R))

(

P

R)=(P

(

P

R))((Q

R)

(P

R))(分配率)

=((P

P)(P

R))

(

P

Q

R)(Q

R

R)=(P

R)

(

P

Q

R)例(p11)

求公式范式

((P

Q)

(R

P))

((R

Q)

P)13/52例(p11)

求公式范式

((P

Q)

(R

P))

((R

Q)

P)另解:

由析取范式，有

=(P∧

Q)∨(P∧

R)∨(

P∧R)

于是，

=(

P∨Q)∧(P∨R)∧(P∨

R) =(P∧Q∧R)∨(

P∧

R)

所以

=(P∨Q∨R)∧(P∨R)14/52解法二：先求公式全部成真解釋和成假解釋(見下一張)

成真解釋為：(P,Q,R)=(T,F,),(F,,T),(T,,F)

成假解釋為：(P,Q,R)=(T,T,T),(F,,F)由成真解釋可分別求出對應(yīng)合取式：

P

Q，

P

R，P

R

公式析取范式即為上面合取式析取：

(P

Q)

(P

R)

(

P

R)由成假解釋可分別求出對應(yīng)析取式：

P

Q

R，P

R

公式合取范式為上面析取式合?。?/p>

(

P

Q

R)

(P

R)例(p11)

求公式范式

((P

Q)

(R

P))

((R

Q)

P)15/52解：P=T時(shí),原式=((T

Q)∧(RT))∨((R

Q)T)

=(Q∧T)∨

((R

Q)) =

Q∨(R

Q)

=

Q∨(R∨Q)=Q∨

RP=F時(shí),原式=((F

Q)∧(RF))∨((R

Q)F)

=(T∧R)∨T=(R)=R

所以有:

成真解釋為：(P,Q,R)=(T,F,),(F,,T),(T,,F)

成假解釋為：(P,Q,R)=(T,T,T),(F,,F)6？例(補(bǔ))求公式成真(假)解釋

((P

Q)

(R

P))

((R

Q)

P)16/52例(補(bǔ))求公式成真(假)解釋

((P

Q)

(R

P))

((R

Q)

P)P

QPQRPRPP

QRQ

QPP(P

Q)P(P

Q)

(R

P)((P

Q)

(R

P))

((P

Q)P)

17/52另解：所以有:成真解釋為：(P,Q,R)=(T,F,),(F,,T),(T,,F)

成假解釋為：(P,Q,R)=(T,T,T),(F,,F)(P,Q,R)A=P

QB=R

PC=(AB)D=R

QE=DPCE(T,T,T)TTFFTF(T,T,F)TTFTFT(T,F,T)FTTTFT(T,F,F)FTTTFT(F,T,T)TFTFTT(F,T,F)TTFTTF(F,F,T)TFTTTT(F,F,F)TTFTTF例(補(bǔ))求公式成真(假)解釋

((P

Q)

(R

P))

((R

Q)

P)18/52范式不唯一性例

求(P

Q)

P析取范式和合取范式．解:(P

Q)

P=((

P∨Q))∨P

=(P∧

Q)∨P

析取范式

=

P析取范式

(P

Q)

P=(P∧

Q)∨P

析取范式

=P∧(

Q∨P)合取范式

=P合取范式19/52第一章命題演算基礎(chǔ)1.1命題和聯(lián)結(jié)詞1.2真假性1.3范式及其應(yīng)用

1.3.1范式

1.3.2主范式1.3.3范式應(yīng)用20/52(一)主析取范式定義1對于n個(gè)命題變元P1，P2，……，Pn，公式Q1

Q2

……

Qn

稱為極小項(xiàng)，其中Qi=Pi或Pi(i=1，……，n)。例由兩個(gè)命題變元P，Q組成極小項(xiàng)有四個(gè)，它們分別為：

P

Q

PQ

PQ

PQ21/52三個(gè)命題變元P、Q和R可結(jié)構(gòu)8個(gè)極小項(xiàng)把命題變元否定形式看成0，必定形式看成1，則每個(gè)極小項(xiàng)對應(yīng)一個(gè)二進(jìn)制數(shù)，也對應(yīng)一個(gè)十進(jìn)制數(shù)。它們對應(yīng)以下：

P

Q

R與000或0對應(yīng)，簡記為m0

P

Q

R與001或1對應(yīng)，簡記為m1

P

Q

R與010或2對應(yīng)，簡記為m2

P

Q

R與011或3對應(yīng)，簡記為m3

P

Q

R與100或4對應(yīng)，簡記為m4

P

Q

R與101或5對應(yīng)，簡記為m5

P

Q

R與110或6對應(yīng)，簡記為m6

P

Q

R與111或7對應(yīng)，簡記為m722/52n個(gè)命題變元組成極小項(xiàng)有2n個(gè)公式每一個(gè)完全成真解釋對應(yīng)一個(gè)極小項(xiàng)公式全部完全成真解釋對應(yīng)極小項(xiàng)析取例:考查公式

=PQ有兩個(gè)成真解釋：

(T,T),(F,F)

分別對應(yīng)于兩個(gè)極小項(xiàng)(合取式)為P∧Q,P∧Q于是，有

=(P∧Q)∨(P∧Q)23/52主析取范式

定義2僅有極小項(xiàng)組成析取范式稱為主析取范式。定理1任何一個(gè)合式公式，都有惟一一個(gè)主析取范式與該合式公式等價(jià)。主析取范式就是公式全部完全成真解釋對應(yīng)極小項(xiàng)析取。

24/52求主析取范式兩種方法(1)解釋法:

依據(jù)公式全部完全成真解釋，求出與這些成真解釋對應(yīng)合取式，全部合取式析取就為公式主析取范式。(2)等價(jià)變換法:

將析取范式中每一個(gè)合取式用A

A填滿命題變元，然后用等價(jià)公式進(jìn)行變換，消去相同部分，即得公式主析取范式。25/52例(p12)求(P

R)

(P

(Q

R))

主析取范式。解法1：等價(jià)變換法原式=(

P

R)((

P

Q

R)(P

(Q

R)))

(去蘊(yùn)涵詞、等價(jià)詞)

=(P

R)((

P

Q

R)(P

(

Q

R)))（否定深入）

=(

P

R)((

P

Q

R)((P

Q)

(P

R)))（分配率）

=(P

Q

R)(P

Q

R)(P

R)

(分解后，六項(xiàng)剩三項(xiàng)）=(P

Q

R)(P

Q

R)((P

R)(Q

Q))

26/52例(p12)求(P

R)

(P

(Q

R))

主析取范式。解法1：等價(jià)變換法（續(xù)上頁）原式=(P

Q

R)(P

Q

R)((P

R)(Q

Q))

=(P

Q

R)(P

Q

R)((P

Q

R)

(P

Q

R))

=(P

Q

R)(P

Q

R)((P

Q

R)

=010101111

=m2m5m7=去等價(jià)詞兩個(gè)公式需要靈活利用，才能將原式快速轉(zhuǎn)化為析取范式！27/52解法2：解釋法公式全部成真解釋為：(P，Q，R)=(F，T，F(xiàn)),(T，F(xiàn)，T),(T，T，T)對應(yīng)于成真解釋極小項(xiàng)為：

P

Q

R,P

Q

R,

P

Q

R

故主析取范式為：

(P

Q

R)(P

Q

R)(P

Q

R)例(p12)求(P

R)

(P

(Q

R))

主析取范式。28/52例(p12)

補(bǔ)求(P

R)

(P

(Q

R))解釋解:P=T時(shí),原式=(T

R)

(T

(Q

R))

=R

(Q

R))

=R

(

Q

R))

=(R

Q)

R=

RP=F時(shí),原式=(F

R)

(F

(Q

R)

=T

(Q

R)

=Q

R

于是,全部成真解釋為：

(T，*，T)、(F，T，F(xiàn))全部成假解釋為：

(T，*，F(xiàn))、(F，F(xiàn)，*)、(F，T，T)29/52(二)主合取范式定義3對于n個(gè)命變元P1，P2，……，Pn，公式

Q1

Q2……

Qn

稱為極大項(xiàng)，其中Qi=Pi或

Pi(i=1，…，n)。例由兩個(gè)命題變元P，Q組成極大項(xiàng)有四個(gè)，它們分別為：

PQ

PQ

PQ

PQ30/52三個(gè)命題變元P、Q和R可結(jié)構(gòu)8個(gè)極大項(xiàng)

把命題變元否定形式看成1，必定形式看成0，則每個(gè)極大項(xiàng)對應(yīng)一個(gè)二進(jìn)制數(shù)，也對應(yīng)一個(gè)十進(jìn)制數(shù)。它們對應(yīng)以下：

P

Q

R與000或0對應(yīng)，簡記為M0

P

Q

R與001或1對應(yīng)，簡記為M1

P

Q

R與010或2對應(yīng)，簡記為M2

P

Q

R與011或3對應(yīng)，簡記為M3

P

Q

R與100或4對應(yīng)，簡記為M4

P

Q

R與101或5對應(yīng)，簡記為M5

P

Q

R與110或6對應(yīng)，簡記為M6

P

Q

R與111或7對應(yīng)，簡記為M731/52n個(gè)命題變元組成極大項(xiàng)有2n個(gè)公式每一個(gè)完全成假解釋對應(yīng)一個(gè)極大項(xiàng)公式全部完全成假解釋對應(yīng)極大項(xiàng)合取例:考查公式

=PQ有兩個(gè)成假解釋：

(T,F),(F,T)

分別對應(yīng)于兩個(gè)極大項(xiàng)(析取式)為

P∨Q,P∨Q于是，有

=(P∨Q)∧(P∨Q)32/52主合取范式定義4僅有極大項(xiàng)組成合取范式稱為主合取范式。定理2任何一個(gè)合式公式，都有惟一一個(gè)主合取范式與該合式公式等價(jià)。主合取范式就是公式全部完全成假解釋對應(yīng)極大項(xiàng)合取。33/52求主合取范式兩種方法(1)解釋法依據(jù)公式全部完全成假解釋，求出與這些成假解釋對應(yīng)析取式，全部析取式合取就為公式主合取范式。(2)等價(jià)變換法將合取范式中每一個(gè)析取式用A

A填滿命題變元，然后用等價(jià)公式進(jìn)行變換，消去相同部份，即得公式主合取范式。34/52解：原式=(

P

R)

((P

(Q

R))

(

P

(Q

R)))（去蘊(yùn)涵詞、等價(jià)詞）

=(

P

R)

(P

Q)

(P

R)

(

P

Q

R)于是，(

P

R)=(

P

R)

(QQ)=(

P

R

Q)

(

P

RQ)(P

Q)=(PQ)

(RR)=(P

Q

R)

(PQ

R)(P

R)=(P

R)

(QQ)=(PQR)

(PQR)原式=(100110)(000001)(001011)110=100110000001011=例(p12)求(P

R)

(P

(Q

R))主合取范式勘誤！35/52例試求α=(P

R)

(

P

(

Q

R))

主析取范式和主合取范式解:α=(P∨R)

((P∧(Q∧R))∨(P∧((Q∧R))))（去蘊(yùn)涵詞、等價(jià)詞）=(

P∨R)((

P∧Q∧R)∨(P∧Q)∨(P∧R))（化簡）=(P∧R)

∨(

P∧Q∧R)∨(P∧Q)∨(P∧R)（去蘊(yùn)涵詞）=(P∧R)∨(

P∧Q∧R)∨(P∧Q)=(110∨100)∨001∨(111∨110)=∑(1,4,6,7)36/52例試求(P

R)

(

P

(

Q

R))

主析取范式和主合取范式解:已經(jīng)得到

α

=(

P∧Q∧R)∨(P∧Q)∨(P∧R)∴α=((

P∨P)∧(

P∨Q)∧(Q∨P)∧(Q∨Q)∧(P∨R)∧(Q∨R))∨(P∧R)=((

P∨Q)∧(Q∨P)∧(P∨R)∧(Q∨R))∨(P∧R)=(T∧(P∨Q∨R))

∧((Q∨P)∧(P∨Q∨R)) ∧((P∨R)∧T)∧((P∨Q∨R)∧T)=101∧(010∧011)∧(010∧000)∧000=∏(0,2,3,5)37/52例試求(P

R)

(

P

(

Q

R))

主析取范式和主合取范式另解:已經(jīng)得到

α

=(

P∧Q∧R)∨(P∧Q)∨(P∧R)

α=(P∨Q∨R)∧(P∨

Q)∧(P∨R)=(P∨Q∨R

)∧(P∨(Q∧R))=(P∧Q∧R)∨(Q∧

P)∨(R∧P)分解,共6項(xiàng)=(P∧Q∧R)∨(Q∧

P∧R) ∨(Q∧P∧R)∨(R∧Q∧P)

∴α=(P∨Q∨R))∧(P∨Q∨R) ∧(P∨Q∨R)∧(P∨Q∨R)=∏(0,2,3,5)38/52主合取范式和主析取范式關(guān)系(1)緊密相關(guān)性：

一個(gè)公式主合取范式和主析取范式是緊密相關(guān)。

如例：

=(P

R)

(

P

(Q

R))=

=(P

R)

(

P

(Q

R))=(2)惟一性：任何一個(gè)命題演算公式，含有惟一主合取范式和主析取范式，所以假如兩個(gè)公式含有相同主析取范式或主合取范式，則稱兩公式邏輯等價(jià)。39/52第一章命題演算基礎(chǔ)1.1命題和聯(lián)結(jié)詞1.2真假性1.3范式及其應(yīng)用

1.3.1范式

1.3.2主范式

1.3.3范式應(yīng)用40/52例運(yùn)籌學(xué)問題從甲、乙、丙、丁4個(gè)人之中派兩個(gè)出去執(zhí)行任務(wù),按以下3個(gè)條件共有幾個(gè)派法？怎樣派?(1)假如派甲去,那么丙和丁之中最少要派一;(2)乙和丙不能同時(shí)都去;(3)假如派丙去,那么丁必須留下。41/52解:分別用A、B、C、D表示依次派甲、乙、丙、丁去,則依據(jù)題意,三種派法分別翻譯為:A→(C∨D),﹁(B∧C),C→﹁D都是真命題。于是T=(A→(C∨D))∧﹁(B∧C)∧(C→﹁D)=(﹁A∨C∨D)∧(﹁B∨﹁C)∧(﹁C∨﹁D)=(﹁A∧﹁B∧﹁C)∨(﹁A∧﹁B∧﹁D)∨(﹁A∧﹁C)∨(﹁A∧﹁C∧﹁D)∨(C∧﹁B∧﹁D)∨(D∧﹁B∧﹁C)∨(D∧﹁C)=(﹁A∧﹁B∧﹁C)∨(﹁A∧﹁B∧﹁D)∨(﹁A∧﹁C∧D)∨(﹁A∧﹁C∧﹁D)∨(C∧﹁B∧﹁D)∨(D∧﹁B∧﹁C)∨(D∧B∧﹁C)42/52解:=(﹁A∧﹁B∧﹁C)∨(﹁A∧﹁B∧﹁D)∨(﹁A∧﹁C∧D)∨(﹁A∧﹁C∧﹁D)∨(C∧﹁B∧﹁D)∨(D∧﹁B∧﹁C)∨(D∧B∧﹁C)=(﹁A∧﹁B∧﹁C)∨(﹁A∧﹁B∧﹁D)∨(﹁A∧B∧﹁C∧D)∨(﹁A∧﹁B∧﹁C∧D)

∨(﹁A∧﹁C∧﹁D)∨(A∧C∧﹁B∧﹁D)∨(﹁A∧C∧﹁B∧﹁D)∨(A∧D∧﹁B∧﹁C)∨(﹁A∧D∧﹁B∧﹁C)∨(A∧D∧B∧﹁C)∨(﹁A∧D∧B∧﹁C)43/52另解：從4人中任意取出2人，共有6種取法：(1)挑出甲、乙，不符合第一條。(2)挑出甲、丙，符合全部條件。(3)挑出甲、丁，符合全部條件。(4)挑出乙、丙，不符合第二條。(5)挑出乙、丁，符合全部條件。(6)挑出丙、丁，不符合第三條。44/52例問路問題有A、B兩個(gè)相鄰小島。A島居民都是老實(shí)人，B島居民都是騙子。一個(gè)旅游者獨(dú)自登上了兩島中某個(gè)島，他分辨不清這個(gè)島是A島還是B島，只知道這個(gè)島上人現(xiàn)有本島，也有另一島，他能夠向一個(gè)人問路1次。