離散數(shù)學(xué)：第二章 命題邏輯等值演算

第2章命題邏輯等值演算等值式與基本的等值式等值演算與置換規(guī)則析取范式與合取范式，主析取范式與主合取范式聯(lián)結(jié)詞完備集可滿足性問(wèn)題與消解法計(jì)算機(jī)科學(xué)與工程學(xué)院12.1等值式等值式：公式A，B的等價(jià)式A?B為永真式符號(hào)：ＡＢ，也稱A邏輯恒等于B

計(jì)算機(jī)科學(xué)與工程學(xué)院22.1等值式例子判斷??pp

p?p??p??p

pFTFTTFTT計(jì)算機(jī)科學(xué)與工程學(xué)院32.1等值式pq?ppq?pqpq

?pqFFTTTTFTTTTTTFFFFTTTFTTT例子判斷pq?pq

計(jì)算機(jī)科學(xué)與工程學(xué)院42.1等值式否定律雙重否定律??pp德摩根律?(p

q)?p?q?(p

q)?p

?q冪等律pp

p，p

p

p交換律p

q

q

p

p

q

q

p

p

q

q

p計(jì)算機(jī)科學(xué)與工程學(xué)院52.1等值式結(jié)合律(pq)rp

(q

r)(p

q)r

p

(q

r)(p

q)r

p

(qr)分配律p

(q

r)(p

q)(p

r)p

(q

r)(p

q)(p

r)計(jì)算機(jī)科學(xué)與工程學(xué)院62.1等值式吸收律p

(p

q)pp

(p

q)p常元律零律:p

TT，p

FF同一律:p

Fp，p

Tp排中律:p

?p

T矛盾律:p

?p

F計(jì)算機(jī)科學(xué)與工程學(xué)院72.1等值式蘊(yùn)含等值式p

q

?p

q等價(jià)等值式p

q

(p

q)(q

p)假言易位p

q

?q

?p等價(jià)否定等值式p

q

?p

?q歸繆律(p

q

)(p

?q)?p

計(jì)算機(jī)科學(xué)與工程學(xué)院82.1等值式說(shuō)明：(1)17組等值模式都可以給出無(wú)窮多個(gè)同類型的具體的等值式。(2)證明上述17組等值式的代入實(shí)例方法可用真值表法，把改為所得的命題公式為永真式，則成立。計(jì)算機(jī)科學(xué)與工程學(xué)院92.1等值式

置換規(guī)則：設(shè)φ(A)是含公式A的命題公式，φ(B)是用公式B置換了φ(A)中所有A后得到的命題公式，若ＡB，則φ(A)

φ(B)。說(shuō)明：等值演算過(guò)程中遵循的重要規(guī)則。一個(gè)命題公式A，經(jīng)多次置換，所得到的新公式與原公式等價(jià)。稱由已知的等值式推演出另外一些等值式的過(guò)程為等值演算。計(jì)算機(jī)科學(xué)與工程學(xué)院102.1等值式1.試證：p→(q→r)(pq)→r證明：p→(q→r)p→(?q∨r)p→(?q∨r)?p∨?q∨r

?p∨?q∨r?(pq)∨r?(pq)∨r(pq)→r計(jì)算機(jī)科學(xué)與工程學(xué)院112.1等值式2試證：?(pq)→(?p∨(?p∨q))(?p∨q)證明：左邊

??(pq)∨

(?p∨(?p∨q))

(pq)∨

(?p∨(?p∨q))

(pq)∨(?p∨q)(p∨?p∨q)(q∨?p∨q)(?p∨q)計(jì)算機(jī)科學(xué)與工程學(xué)院122.1等值式3.證明：((p∨q)?(?p(?q∨?r)))∨(?p?q)∨(?p?r)為一永真式證明：原式((p∨q)(p∨(qr)))∨?(p∨q)∨?(p∨r)

((p∨q)(p∨q)(p∨r))∨?((p∨q)(p∨r))

((p∨q)(p∨r))∨?((p∨q)(p∨r))Ｔ計(jì)算機(jī)科學(xué)與工程學(xué)院132.2析取范式和合取范式文字(literal):命題變?cè)捌浞穸ê?jiǎn)單析取式:僅由有限個(gè)文字構(gòu)成的析取式簡(jiǎn)單合取式:僅由有限個(gè)文字構(gòu)成的合取式稱作例：設(shè)p、q為二個(gè)命題變?cè)猵，q，p∨p，q∨q，?p∨q，?q∨?p，p∨q，p∨?q稱為簡(jiǎn)單析取式q，p∧p，q∧q，?p∧q，?q∧?p，p∧q，p∧?q稱為簡(jiǎn)單合取式。計(jì)算機(jī)科學(xué)與工程學(xué)院142.2析取范式和合取范式定理: 1)一個(gè)簡(jiǎn)單析取式是永真式當(dāng)且僅當(dāng)它同時(shí)含某個(gè)命題變?cè)八姆穸ㄊ?/p>

證明？

2)一個(gè)簡(jiǎn)單合取式是永假式當(dāng)且僅當(dāng)它同時(shí)含某個(gè)命題變?cè)八姆穸ㄊ?/p>

證明？計(jì)算機(jī)科學(xué)與工程學(xué)院152.2析取范式和合取范式析取范式:由有限個(gè)簡(jiǎn)單合取式構(gòu)成的析取式A1

…An,Ai

為合取式(p

q)(p

r)合取范式:由有限個(gè)簡(jiǎn)單析取式構(gòu)成的合取式A1

…An,Ai

為析取式(p

q)(p

r)析取范式與合取范式統(tǒng)稱為范式計(jì)算機(jī)科學(xué)與工程學(xué)院162.2析取范式和合取范式定理：Ai

簡(jiǎn)單合取式，A1

…An

F當(dāng)且僅當(dāng)

任意Ai，Ai

FAi

簡(jiǎn)單析取式，

A1

…An

T當(dāng)且僅當(dāng)

任意Ai，Ai

T計(jì)算機(jī)科學(xué)與工程學(xué)院172.2析取范式和合取范式范式存在定理:任意命題公式都存在著與之等值的析取范式與合取范式方法：步驟一：消去“”、“”聯(lián)結(jié)詞步驟二：消去雙重否定符，內(nèi)移否定符步驟三：使用分配律計(jì)算機(jī)科學(xué)與工程學(xué)院182.2析取范式和合取范式范式存在定理:任意命題公式都存在著與之等值的析取范式與合取范式方法：

步驟一：消去“”、“”聯(lián)結(jié)詞步驟二：消去雙重否定符，內(nèi)移否定符步驟三：使用分配律計(jì)算機(jī)科學(xué)與工程學(xué)院192.2析取范式和合取范式步驟一：利用等值公式：化去“→”、“”聯(lián)結(jié)詞

p

q

p

q

p

?q

(p

q)(q

p)計(jì)算機(jī)科學(xué)與工程學(xué)院202.2析取范式和合取范式范式存在定理:任意命題公式都存在著與之等值的析取范式與合取范式方法：步驟一：消去“”、“”聯(lián)結(jié)詞步驟二：消去雙重否定符，內(nèi)移否定符步驟三：使用分配律計(jì)算機(jī)科學(xué)與工程學(xué)院212.2析取范式和合取范式消去雙重否定符，內(nèi)移否定符德摩根律?(p

q)?p?q?(p

q)?p

?q雙重否定律??pp計(jì)算機(jī)科學(xué)與工程學(xué)院222.2析取范式和合取范式范式存在定理:任意命題公式都存在著與之等值的析取范式與合取范式方法：步驟一：消去“”、“”聯(lián)結(jié)詞步驟二：消去雙重否定符，內(nèi)移否定符步驟三：使用分配律計(jì)算機(jī)科學(xué)與工程學(xué)院232.2析取范式和合取范式利用“”對(duì)“”的分配，將公式化成為析取范式p

(q

r)(p

q)(p

r)計(jì)算機(jī)科學(xué)與工程學(xué)院242.2析取范式和合取范式例：求(pq)(pq)的析取范式化去

(pq)(pq)“”對(duì)“”分配，化為析取范式

(ppq)(qpq)最簡(jiǎn)析取范式p

q

計(jì)算機(jī)科學(xué)與工程學(xué)院252.2析取范式和合取范式例：求((pq)r)p的析取范式和合取范式(一)求析取范式原式((pq)r)p

((pq)r)p

((pq)r)p((pq)r)p((pr)(qr))pp(pr)(qr)

p(qr)計(jì)算機(jī)科學(xué)與工程學(xué)院262.2析取范式和合取范式(二)求合取范式原式((pq)r)p

((pq)r)p

((pq)r)p((pq)r)p(ppq)(p

r)(pq)(p

r)計(jì)算機(jī)科學(xué)與工程學(xué)院272.2析取范式和合取范式討論：一個(gè)命題公式的析取范式不是唯一的，但同一命題公式的析取范式一定是等值的計(jì)算機(jī)科學(xué)與工程學(xué)院282.2析取范式和合取范式極小項(xiàng)(極大項(xiàng)):含有n個(gè)命題變?cè)暮?jiǎn)單合取式(簡(jiǎn)單析取式)并滿足每個(gè)命題變?cè)退姆穸ㄊ讲煌瑫r(shí)出現(xiàn)，而二者之一必出現(xiàn)且僅出現(xiàn)一次第i個(gè)命題變?cè)蛩姆穸ㄊ匠霈F(xiàn)在從左算起的第i位上(若無(wú)角標(biāo)則按字典順序排列)若有ｎ個(gè)命題變?cè)瑒t有2n個(gè)極小項(xiàng)（極大項(xiàng)）如果我們把命題變?cè)闯?，命題變?cè)姆穸闯?，那么每一個(gè)極小項(xiàng)（極大項(xiàng)）都對(duì)應(yīng)一個(gè)二進(jìn)制數(shù)，因而也對(duì)應(yīng)一個(gè)十進(jìn)制數(shù)計(jì)算機(jī)科學(xué)與工程學(xué)院292.2析取范式和合取范式極小項(xiàng)的編碼:對(duì)應(yīng)成真賦值三個(gè)變?cè)猵、q、r可構(gòu)造8個(gè)極小項(xiàng)：

?p∧?q∧?rFFF0記作m0?p∧?q∧rFFT1記作m1?p∧q∧?rFTF2記作m2?p∧q∧rFTT3記作m3

p∧?q∧?rTFF4記作m4

p∧?q∧rTFT5記作m5

p∧q∧?rTTF6記作m6

p∧q∧rTTT7記作m7計(jì)算機(jī)科學(xué)與工程學(xué)院302.2析取范式和合取范式極大項(xiàng)的編碼:對(duì)應(yīng)成假賦值如三個(gè)變?cè)猵、q、r，其記法如下：p∨q∨rFFF0記作M0p∨q∨?rFFT1記作M1p∨?q∨rFTF2記作M2p∨?q∨?rFTT3記作M3……?p∨?q∨?rTTT7記作M7計(jì)算機(jī)科學(xué)與工程學(xué)院312.2析取范式和合取范式定理:設(shè)mi和Mi是命題變?cè)猵1,p2…pn形成的極小項(xiàng)和極大項(xiàng)，則：(1)mi

mj

F,(i≠j)(2)Mi

Mj

T,(i≠j)(3)

mi

T,(i=0,1,…,2n-1)(4)

Mi

F,(i=0,1,…,2n-1)(5)mi

Mi；

Mimi計(jì)算機(jī)科學(xué)與工程學(xué)院322.2析取范式和合取范式

主析取范式(主合取范式)：由n個(gè)命題變?cè)獦?gòu)成的析取范式(合取范式)中所有的簡(jiǎn)單合取式(簡(jiǎn)單析取式)都是極小項(xiàng)(極大項(xiàng))定理:任何命題公式都存在著與其等值的主析取范式和主合取范式，并且是唯一的。計(jì)算機(jī)科學(xué)與工程學(xué)院332.2析取范式和合取范式證法一在真值表中，使命題公式的真值為T的指派所對(duì)應(yīng)的極小項(xiàng)的析取，即為此公式的主析取范式證：給定一個(gè)命題公式A，使其為T的真值指派所對(duì)應(yīng)的極小項(xiàng)為m1’,m2’,…,mk’,這些極小項(xiàng)的析取記為B，為此要證AB，即要證A與B在相同的指派下具有相同的真值。計(jì)算機(jī)科學(xué)與工程學(xué)院342.2析取范式和合取范式首先對(duì)于使A為T的指派顯然使B為T對(duì)于使A為F的指派，它對(duì)應(yīng)的極小項(xiàng)(設(shè)為mj’

)不包含在m1’,m2’,…,mk’中。所以mj’

為使B為F的指派所以A

B得證計(jì)算機(jī)科學(xué)與工程學(xué)院352.2析取范式和合取范式一個(gè)公式的主析取范式即為令此公式的真值為T的指派所對(duì)應(yīng)的極小項(xiàng)的析取。一個(gè)命題公式的真值表是唯一的，因此一個(gè)命題公式的主析取范式也是唯一的計(jì)算機(jī)科學(xué)與工程學(xué)院362.2析取范式和合取范式pqrm1m3m5m6m7pqrp∧q∨rFFFFFFTTFTFFFTTTTFFFTFTTTTFTTTTTpqr的真值表計(jì)算機(jī)科學(xué)與工程學(xué)院372.2析取范式和合取范式證法二：構(gòu)造法用等值演算方法求命題公式主析取范式的方法將命題公式化歸為與其等值的析取范式添變?cè)?消去重復(fù)項(xiàng)唯一性Ai

(pjpj)(Ai

pj)(Ai

pj)計(jì)算機(jī)科學(xué)與工程學(xué)院382.2析取范式和合取范式例：求(p∧(p→q))∨q的主析取范式解：原式(p∧?p)∨(p∧q)∨q----(1)化為析取范式

(p∧q)∨q----(2)化簡(jiǎn)(p∧q)∨(q∧(p∨?p))(p∧q)∨(p∧q)∨(?p∧q)----(3)添項(xiàng)(p∧q)∨(?p∧q)----(4)合并相同最小項(xiàng)計(jì)算機(jī)科學(xué)與工程學(xué)院392.2析取范式和合取范式主析取范式的用途討論：求公式的成真與成假賦值判斷公式類型判斷兩個(gè)命題公式是否等值應(yīng)用主析取范式分析和解決實(shí)際問(wèn)題計(jì)算機(jī)科學(xué)與工程學(xué)院402.2析取范式和合取范式例：某研究所要從3名科研骨干A，B，C中挑選1～2名出國(guó)進(jìn)修，由于工作需要，選派時(shí)要滿足以下條件：若A去，則C同去。若B去，則C不能去。若C不去，則A或B可以去。解:設(shè)p：派A去；q：派B去；r：派C去。則(p→r)

∧(q→?r)∧(?r→(p∨q))計(jì)算機(jī)科學(xué)與工程學(xué)院412.2析取范式和合取范式經(jīng)演算可得：(p→r)

∧(q→?r)∧(?r→(p∨q))m1∨m2∨m5可知選派方案有三種：C去，A，B都不去。B去，A，C不去。A，C去，B不去。計(jì)算機(jī)科學(xué)與工程學(xué)院422.2析取范式和合取范式主合取范式任何一個(gè)命題公式都可求得它的主合取范式

一個(gè)命題公式的主合取范式是唯一的

在真值表中，令命題公式的真值為“F”的指派就對(duì)應(yīng)其主合取范式的一個(gè)極大項(xiàng)計(jì)算機(jī)科學(xué)與工程學(xué)院432.2析取范式和合取范式例:求p∧(p→q)∨q的主合取范式解：原式p∧(p∨q)∨q(p∧p)∨(p∧q)∨q(p∧q)∨q(p∨q)∧q(p∨q)∧(q∨(p∧p))

(p∨q)∧(p∨q)

M0

∧

M2

pq上式FFFFTTTFFTTT計(jì)算機(jī)科學(xué)與工程學(xué)院442.2析取范式和合取范式主合取范式與主析取范式轉(zhuǎn)換公式:A=mi1

mi2

…mis

A=mj1

mj2

…mjt，t=2n-sAA

(mj1

mj2

…mjt)mj1

mj2

…

mjtMj1

Mj2

…

Mjt計(jì)算機(jī)科學(xué)與工程學(xué)院452.2析取范式和合取范式討論：具有n個(gè)變?cè)拿}公式有多少個(gè)不同的主析取范式？對(duì)于含有ｎ個(gè)變?cè)拿}公式，必定可寫(xiě)出22n個(gè)主析取范式(包括F)。同理，含有ｎ個(gè)變?cè)拿}公式，也可寫(xiě)出22n個(gè)主合取范式(包括T)。計(jì)算機(jī)科學(xué)與工程學(xué)院462.3聯(lián)結(jié)詞的完備集性質(zhì)：p⊕q(?pΛq)∨(?qΛp)(p∨q)Λ(?p∨?q)p⊕q?

(pq)p⊕qq⊕p

(可交換的)(p⊕q)⊕rp⊕(q⊕r)(可結(jié)合的)排斥或(異或)符號(hào)：“⊕”()pqp⊕qFFFFTTTFTTTF47計(jì)算機(jī)科學(xué)與工程學(xué)院2.3聯(lián)結(jié)詞的完備集“與非”聯(lián)結(jié)詞：符號(hào)“↑”(p↑q)讀作：“p與q的否定”(p↑q)?(p∧q)pqp↑qFFTFTTTFTTTF48計(jì)算機(jī)科學(xué)與工程學(xué)院2.3聯(lián)結(jié)詞的完備集“或非”聯(lián)結(jié)詞：符號(hào)：“↓”

(p↓q)?(p∨q)pqp↓qFFTFTFTFFTTF計(jì)算機(jī)科學(xué)與工程學(xué)院492.3聯(lián)結(jié)詞的完備集真值函數(shù)F:{0,1}n

{0,1}聯(lián)結(jié)詞完備集S:S是一個(gè)聯(lián)接詞集合每一個(gè)真值函數(shù)都可以由僅含S中的聯(lián)接詞構(gòu)成的公式表示定理:S={，，}是聯(lián)接詞完備集證明：任何一個(gè)n（n1）元真值函數(shù)都與唯一的一個(gè)主析取范式等值，而主析取范式僅含，，計(jì)算機(jī)科學(xué)與工程學(xué)院502.3聯(lián)結(jié)詞的完備集推論:S={，}是聯(lián)接詞完備集證明：p

q

(p

q)(p

q)計(jì)算機(jī)科學(xué)與工程學(xué)院512.3聯(lián)結(jié)詞的完備集定理:{↑}，{↓}是聯(lián)接詞完備集證明：首先，p(pp)

p↑p其次，p

q

(p

q)(p↑q)(p↑q)↑(p↑q)(p↑q)(pq)計(jì)算機(jī)科學(xué)與工程學(xué)院522.4消解法可滿足性問(wèn)題：用于證明A是否永真用于驗(yàn)證邏輯蘊(yùn)涵A1…Ak

B永真當(dāng)且僅當(dāng)A1…Ak

B永假解決方法真值表主析取范式主合取范式缺點(diǎn)：計(jì)算量大引入消解法！計(jì)算機(jī)科學(xué)與工程學(xué)院532.4消解法文字l的補(bǔ)：lc=p，如果l

=plc=p，如果l

=p消解式：C1=C1′l,C2=C2′

lcRes(C1,C2)=C1′

C2′定理：C1C2?Res(C1,C2)消解式是原公式的邏輯推論討論！2.4消解法計(jì)算機(jī)科學(xué)與工程學(xué)院55定理：C1C2和Res(C1,C2)可滿足性相同

證明：C1=C1′l,C2=C2′

lc

(a)如果C1C2可滿足，則存在v，v(Ci)=T

假設(shè)v(l)=T，則v(C2′)=T。

(b)如果Res(C1,C2)可滿足，則存在v

存在l′在C1′使得v(l′)=T,v可以擴(kuò)展為

v(p)=F如果p=l

v(p)=T如果p=lc

v對(duì)C1C2賦值為Tv(C1′

C2′)=TC1

C2和Res(C1,C2)不等值例：C1=pqr,C2=prRes(C1,C2)=pqv=FTT滿足Res(C1,C2)但不滿足C1

C22.4消解法消解推導(dǎo)：S=C1…

Cn和C符號(hào)：{C1,…,Cn}?C存在公式序列A1,A2,…,Ak，對(duì)每個(gè)i(i=1,…,k),Ai是某個(gè)Cj或者Ai是有序列中前面的公式應(yīng)用消解得到Ak=C稱A1,…,Ak是由S到C的推導(dǎo)如果C為空子句□，則稱此序列是S的一個(gè)否證計(jì)算機(jī)科學(xué)與工程學(xué)院572.4消解法消解可靠性：如果合取范式S有否證，則S是不可滿足。

證明：每次使用消解，都保持可滿足性。如果消解結(jié)果不可滿足，則S必不可滿足。消解完全性：如果合取范式S是不可滿足，則S有否證。

計(jì)算機(jī)科學(xué)與工程學(xué)院582.4消解法消解算法（分層飽和法）輸入：合式公式A輸出：yes(A可滿足)，no(A不可滿足)計(jì)算機(jī)科學(xué)與工程學(xué)院592.4消解法求A的合取范式S.令i=0,S(0)=S的所有簡(jiǎn)單析取式組成的集合.若S(i)包含空子句，則S不可滿足，算法終止.

i=i+1.構(gòu)造S(i)={Res(C1,C2)|C1(S(0)?…?S(i-1))且C2

S(i-1)}.若S(i)

S(0)?…?S(i-1)則S是可滿足的，算法終止.轉(zhuǎn)3例1：A=(pq)(p