命題邏輯等值演算

命題邏輯等值演算第一頁，共四十二頁，編輯于2023年，星期五基本要求：1.深刻理解等值式的概念。

2.牢記24個基本等值式，這是等值演算的基礎(chǔ)；能熟練地應(yīng)用它們進行等值演算。

3.了解簡單析取式、簡單合取式、析取范式、合取范式的概念。

4.深刻理解極小項及極大項的定義及它們的名稱，及名稱下角標與成真賦值的關(guān)系。

5.熟練掌求公式的主析取范式的方法。

6.熟練掌握由公式的主析取范式求公式的主合取范式的方法。

7.會用公式的主析取范式（主合取范式）求公式的成真賦值、成假賦值。8.會將公式等值地化為任何聯(lián)結(jié)詞完備集中的公式。第二頁，共四十二頁，編輯于2023年，星期五某公司派小李或小張去上海出差，若派小李去，則小趙要加班。若派小張去，小王也得去。小趙沒加班。問公司是如何派遣的？解：復(fù)合命題（公式）例題(p∨q)(pr)(qs)r∧∧∧A=第三頁，共四十二頁，編輯于2023年，星期五(p∨q)(pr)(qs)r∧∧∧A=pqrsp∨qprqsr(p∨q)∧(pr)∧(qs)∧r000001110000101110001001100001101100010011010010111111011011000011111100100010110100110110101011100101111100110010010110110110111011000111111100麻煩?。∮嬎懔看螅。》椒ê芏啵?/p>

真值表法等值演算法第四頁，共四十二頁，編輯于2023年，星期五2.1等值式1.例子看下面三個公式的真值表

PQPQP∨QQP00111011111000011111

從真值表可以看出，不論對P、Q作何指派，都使得PQ、P∨Q和QP的真值相同，表明它們之間彼此等價。第五頁，共四十二頁，編輯于2023年，星期五2.定義：A、B是含有命題變元P1,P2,…,

Pn的命題公式，如不論對P1,P2,…,

Pn作任何指派，都使得A和B的真值相同，則稱之為A與B等價，記作AB。顯然PQP∨QQP3.重要的等價公式⑴雙重否定律AA⑵冪等律A∨AAA∧AA⑶交換律A∨BB∨AA∧BB∧A⑷結(jié)合律A∨(B∨C)(A∨B)∨C

A∧(B∧C)(A∧B)∧C

第六頁，共四十二頁，編輯于2023年，星期五(6)德摩根律(A∨B)A∧B

(A∧B)A∨B(7)吸收律A∨(A∧B)AA∧(A∨B)A(8)零律A∨11A∧00(9)同一律A∨0AA∧1A(10)排中律A∨A1(11)矛盾律A∧A0⑸分配律A∨(B∧C)(A∨B)∧(A∨C)A∧(B∨C)(A∧B)∨(A∧C)(∨對∧的分配律)互補律(∧對∨的分配律)第七頁，共四十二頁，編輯于2023年，星期五(13)等價等值式AB(AB)∧(BA)

AB(A∨B)∧(A∨B)AB(A∧B)∨(A∧B)(14)假言易位ABBA(15)等價否定等值式

ABAB

(16)歸謬論

(AB)∧(AB)A(12)蘊含等值式ABA∨B

第八頁，共四十二頁，編輯于2023年，星期五4.等價公式的證明方法方法1：用列真值表。（不再舉例）方法2：用公式的等價變換.(用置換定律)置換定律:A是一個命題公式，X是A中的一部分且也是合式公式，如果XY，用Y代替A中的X得到公式B，則AB。應(yīng)用置換定律以及前面列出的等價公式可以對給定公式進行等價變換。等值演算：由已知等值式推演出新的等值式的過程。第九頁，共四十二頁，編輯于2023年，星期五例題1.用等值演算法證明下面等值式：((p∨q)∧(p∧q))(pq)q(pr)(p∧q)r證明：(1)從左邊開始演算(p∨q)∧(p∧q)

(p∨q)∧(p∧q)(雙重否定律)

((p∨q)∨(p∧q))(德摩根律)

((p∧q)∨(p∧q))(德摩根律)

((p∨p)∧(p∨q)∧(q∨p)∧(q∨q))(分配律)

((p∨q)∧(q∨p))(同一律)((p

q)∧(qp))(蘊含等值式)(pq)(等價等值式)11第十頁，共四十二頁，編輯于2023年，星期五例題1.用等值演算法證明下面等值式：(2)q(pr)(p∧q)r證明：(2)從右邊開始演算

(p∧q)r

(p∧q)∨r(蘊含等值式)

p∨q∨r(德摩根律)

q∨(p∨r)(交換律)

q∨(pr)(蘊含等值式)q(pr)(蘊含等值式)

第十一頁，共四十二頁，編輯于2023年，星期五例題2.用等值演算法判斷下列公式的類型：(p∨q)→(p∧q)p→(p∨q∨r)((p→q)∧q)∧r解：(1)(p∨q)→(p∧q)

(p∨q)∨(p∧q)(蘊含等值式)(p∧q)∨(p∧q)(德摩根定律)(p∧q)∨(p∧q)(雙重否定律)

p∧(q∨q)(分配律)

p∧1(排中律)

p(同一律)因為p是可滿足式，故式(1)為可滿足式第十二頁，共四十二頁，編輯于2023年，星期五例題2.用等值演算法判斷下列公式的類型：(2)p→(p∨q∨r)解：(2)

p→(p∨q∨r)

p∨(p∨q∨r)(蘊含等值式)(p∨p)∨(q∨r)(分配律)1∨(q∨r)(排中律)

1(零律)因為1是重言式，故式(2)為重言式第十三頁，共四十二頁，編輯于2023年，星期五例題2.用等值演算法判斷下列公式的類型：(3)((p→q)∧q)∧r解：(3)

((p→q)∧q)∧r

(p∨q)∧q)∧r

(蘊含等值式)p∧(q∧q)∧r

(德摩根律、結(jié)合律)p∧0∧r(矛盾律)

0(零律)因為p是矛盾式，故式(3)為矛盾式第十四頁，共四十二頁，編輯于2023年，星期五某公司派小李或小張去上海出差，若派小李去，則小趙要加班。若派小張去，小王也得去。小趙沒加班。問公司是如何派遣的？(p∨q)(pr)(qs)r∧∧∧A=例題.用等值演算法解決實際問題p：派小李去上海出差q：派小張去上海出差r：小趙要加班s：小王也去上海出差(p∨q)∧(p∨r)∧(q∨s)∧r(德摩根律)(p∨q)∧(p∨r)∧r∧

(q∨s)(交換律)(p∨q)∧(p∧r)∧

(q∨s)(分配律、矛盾律)((p∧p∧r)∨(q∧p∧r))∧(q∨s)(分配律)(q∧p∧r)∧(q∨s)(矛盾律)(q∧p∧r∧s)(分配律、矛盾律)結(jié)論：派遣方案為：派小張和小王去上海出差，只有這一種方案第十五頁，共四十二頁，編輯于2023年，星期五2.2.范式范式就是命題公式形式的規(guī)范形式。這里約定在范式中只含有聯(lián)結(jié)詞、∨和∧。一.析取范式與合取范式1.合取式與析取式

合取式：是用“∧”聯(lián)結(jié)命題變元或變元的否定構(gòu)成的式子。如P、P、P∧Q、P∧Q∧R

析取式：是用“∨”聯(lián)結(jié)命題變元或變元的否定構(gòu)成的式子。如P、P、P∨Q、P∨Q∨R注:∵P∨PPP∧PP∴P是合(析)取式.第十六頁，共四十二頁，編輯于2023年，星期五2.析取范式公式A如果寫成如下形式：A1∨A2∨...∨An(n≥1)其中每個Ai(i=1,2..n)是合取式，稱之為A的析取范式。

3.合取范式公式A如果寫成如下形式：A1∧A2∧...∧An(n≥1)

其中每個Ai(i=1,2..n)是析取式，稱之為A的合取范式。例如，PQ的析取范式與合取范式：PQ(P∧Q)∨(P∧Q)----析取范式PQ(P∨Q)∧(P∨Q)----合取范式第十七頁，共四十二頁，編輯于2023年，星期五4.析取范式與合取范式的寫法

⑴先用相應(yīng)的公式去掉和。蘊含等值式PQP∨Q等價等值式PQ(P∧Q)∨(P∧Q)

PQ(PQ)∧(QP)

PQ(P∨Q)∧(P∨Q)

⑵用公式的否定公式或德摩根律將后移到命題變元之前。

A(P1,P2,…,Pn)A*(P1,P2,…,Pn)

(P∨Q)P∧Q

(P∧Q)P∨Q

⑶用分配律、冪等律等公式進行整理，使之成為所要求的形式。

(對偶式)第十八頁，共四十二頁，編輯于2023年，星期五例如求(PQ)R的析取范式與合取范式(PQ)R((P∨Q)∧(P∨Q))∨R(P∧Q)∨(P∧Q)∨R------析取范式(PQ)R((P∧Q)∨(P∧Q))∨R((P∨Q)∧(P∨Q))∨R(P∨Q∨R)∧(P∨Q∨R)---合取范式第十九頁，共四十二頁，編輯于2023年，星期五二.主析取范式與主合取范式一個公式的析取范式與合取范式的形式是不唯一的。下面定義形式唯一的主析取范式與主合取范式。㈠主析取范式1.極小項⑴定義：在一個有n個命題變元的合取式中，每個變元必出現(xiàn)且僅出現(xiàn)一次，稱這個合取式是個極小項。例如，有兩個變元的極小項：P∧Q、P∧Q、P∧Q、P∧Q

第二十頁，共四十二頁，編輯于2023年，星期五

⑵極小項的性質(zhì)m3m2m1

m0PQP∧QP∧QP∧QP∧Q00FFFFFT01FTFFTF10TFFTFF11TTTFFF

a).有n個變元，則有2n個極小項。

b).每一組指派有且只有一個極小項為T。為了記憶方便，可將各組指派對應(yīng)的為T的極小項分別記作m0,m1,m2,…,m2n-1上例中m0P∧Qm1P∧Q

m2P∧Qm3P∧Q第二十一頁，共四十二頁，編輯于2023年，星期五2.主析取范式定義

析取范式A1∨A2∨...∨An,,其中每個Ai(i=1,2..n)都是極小項，稱之為主析取范式。3.主析取范式的寫法

方法Ⅰ：列真值表⑴列出給定公式的真值表。⑵找出真值表中每個“T”對應(yīng)的極小項。(如何根據(jù)一組指派寫對應(yīng)的為“T”的項：如果變元P被指派為T，P在極小項中以P形式出現(xiàn)；如變元P被指派為F,P在極小項中以P形式出現(xiàn)(因要保證該極小項為T))。⑶用“∨”聯(lián)結(jié)上述極小項，即可。第二十二頁，共四十二頁，編輯于2023年，星期五例如求PQ和PQ的主析取范式

PQPQPQFFTTFTTFTFFFTTTT

PQm0∨m1∨m3

(P∧Q)∨(P∧Q)∨(P∧Q)PQm0∨m3(P∧Q)∨(P∧Q)思考題:永真式的主析取范式是什么樣？第二十三頁，共四十二頁，編輯于2023年，星期五方法Ⅱ：用公式的等價變換⑴先寫出給定公式的析取范式

A1∨A2∨...∨An

。⑵為使每個Ai都變成極小項，對缺少變元的Ai補全變元，比如缺變元R，就用∧聯(lián)結(jié)永真式(R∨R)形式補R。⑶用分配律等公式加以整理。

PQP∨Q(P∧(Q∨Q))∨((P∨P)∧Q)(P∧Q)∨(P∧Q)∨(P∧Q)∨(P∧Q)(P∧Q)∨(P∧Q)∨(P∧Q)第二十四頁，共四十二頁，編輯于2023年，星期五㈡主合取范式1.極大項⑴定義:在有n個命題變元的析取式中，每個變元必出現(xiàn)且僅出現(xiàn)一次,稱之為極大項。例如，有兩個變元的極大項及其真值表：M0M1M2M3PQP∨QP∨QP∨QP∨QFF

FTTTFTT

FTTTFTTFTTTTTT

F第二十五頁，共四十二頁，編輯于2023年，星期五⑵極大項的性質(zhì)a).有n個變元，則有2n個極大項。

b).每一組指派有且只有一個極大項為F。為了記憶方便，可將各組指派對應(yīng)的為F的極大項分別記作M0,M1,M2,…,M2n-1。上例中M0P∨QM1P∨Q

M2

P∨QM3P∨Q第二十六頁，共四十二頁，編輯于2023年，星期五⑵極大項與極小項之間的關(guān)系

定理2.3：第二十七頁，共四十二頁，編輯于2023年，星期五2.主合取范式定義合取范式A1∧A2∧...∧An,,其中每個Ai(i=1,2..n)都是極大項，稱之為主合取范式。3.主合取范式的寫法

方法Ⅰ：列真值表⑴列出給定公式的真值表。⑵找出真值表中每個“F”對應(yīng)的極大項。

如何根據(jù)一組指派寫對應(yīng)的為“F”的極大項：如果變元P被指派為F，P在極大項中以P形式出現(xiàn)；如變元P被指派為T，P在極大項中以P形式出現(xiàn)(確保該極大項為F)。⑶用“∧”聯(lián)結(jié)上述大項，即可。第二十八頁，共四十二頁，編輯于2023年，星期五例如求PQ和PQ的主合取范式

PQPQPQFFTTFTTFTFFFTTTT

PQM2P∨QPQM1∧M2(P∨Q

)∧(P∨Q)第二十九頁，共四十二頁，編輯于2023年，星期五方法Ⅱ：用公式的等價變換⑴先寫出給定公式的合取范式

A1∧A2∧...∧An

。⑵為使每個Ai變成極大項，對缺少變元的析取式Ai補全變元，比如缺變元R，就用∨聯(lián)結(jié)永假式(R∧R)形式補R。⑶用分配律等公式加以整理。第三十頁，共四十二頁，編輯于2023年，星期五例如，求(PQ)R的主合取范式(PQ)R(P∨Q)∨R(P∧Q)∨R(P∨R)∧(Q∨R)(P∨(Q∧Q)∨R)∧((P∧P)∨Q∨R)(P∨Q∨R)∧(P∨Q∨R)∧

(P∨Q∨R)∧(P∨Q∨R)第三十一頁，共四十二頁，編輯于2023年，星期五三.主范式的應(yīng)用

1.應(yīng)用主析取范式解決實際問題某公司派小李或小張去上海出差，若派小李去，則小趙要加班。若派小張去，小王也得去。小趙沒加班。問公司是如何派遣的？A＝(p∨q)∧(pr)∧(qs)∧r(p∨q)∧(p∨r)∧(q∨s)∧r

((p∧p)∨(p∧s)∨(q∧p)∨(q∧s))∧

((q∧r)∨(r∧r))00((p∧s)∨(q∧p)∨(q∧s))∧(q∧r)(p∧s∧q∧r)∨0∨0(p∧s∧q∧r)m9第三十二頁，共四十二頁，編輯于2023年，星期五應(yīng)用2

用主析取范式或主合取范式判斷兩個命題公式是否等值(1)設(shè)A=(p∧q)∨(p∧q∧r)，B=(p∨(q∧r))∧(q∨(p∧r))解：求A與B的主析取范式A=(p∧q)∨(p∧q∧r)(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)

(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)m6m7m3m3∨m6∨m7B=(p∨(q∧r))∧(q∨(p∧r))(p∧q)∨(p∧p∧r)∨(q∧r∧q)∨(q∧r∧p∧r)(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)m3∨m6∨m7m7m6m3m3∨m6∨m7由于A與B有相同的主析取范式，所以A

B第三十三頁，共四十二頁，編輯于2023年，星期五解：求A與B的主合取范式A=(p∧q)∨(p∧q∧r)(p∨p)

∧(p∨q)∧(p∨r)∧(q∨p)∧(q∨p)∧(q∨r)

(p∨q)∧(p∨r)∧(q∨p)∧(q∨p)∧(q∨r)(p∨q)∧(p∨r)∧(p∨q)∧(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)應(yīng)用2

用主析取范式或主合取范式判斷兩個命題公式是否等值(1)設(shè)A=(p∧q)∨(p∧q∧r)，B=(p∨(q∧r))∧(q∨(p∧r))M1M0M2M5M4M0∧M1∧M2∧M4∧M5M0∧M1∧M2∧M4∧M5第三十四頁，共四十二頁，編輯于2023年，星期五B=(p∨(q∧r))∧(q∨(p∧r))

(p∨q)∧(p∨r)∧(q∨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)

解：求A與B的主合取范式A=(p∧q)∨(p∧q∧r)應(yīng)用2

用主析取范式或主合取范式判斷兩個命題公式是否等值(1)設(shè)A=(p∧q)∨(p∧q∧r)，B=(p∨(q∧r))∧(q∨(p∧r))M1M0M2M5M4M0∧M1∧M2∧M4∧M5M0∧M1∧M2∧M4∧M