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

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

p?p??p??p

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

?pqFFTTTTFTTTTTTFFFFTTTFTTT例子判斷pq?pq

計算機科學(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計算機科學(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)計算機科學(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計算機科學(xué)與工程學(xué)院72.1等值式蘊含等值式p

q

?p

q等價等值式p

q

(p

q)(q

p)假言易位p

q

?q

?p等價否定等值式p

q

?p

?q歸繆律(p

q

)(p

?q)?p

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

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

φ(B)。說明：等值演算過程中遵循的重要規(guī)則。一個命題公式A，經(jīng)多次置換，所得到的新公式與原公式等價。稱由已知的等值式推演出另外一些等值式的過程為等值演算。計算機科學(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計算機科學(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)計算機科學(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))Ｔ計算機科學(xué)與工程學(xué)院132.2析取范式和合取范式文字(literal):命題變元及其否定簡單析取式:僅由有限個文字構(gòu)成的析取式簡單合取式:僅由有限個文字構(gòu)成的合取式稱作例：設(shè)p、q為二個命題變元p，q，p∨p，q∨q，?p∨q，?q∨?p，p∨q，p∨?q稱為簡單析取式q，p∧p，q∧q，?p∧q，?q∧?p，p∧q，p∧?q稱為簡單合取式。計算機科學(xué)與工程學(xué)院142.2析取范式和合取范式定理: 1)一個簡單析取式是永真式當且僅當它同時含某個命題變元及它的否定式

證明？

2)一個簡單合取式是永假式當且僅當它同時含某個命題變元及它的否定式

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

…An,Ai

為合取式(p

q)(p

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

…An,Ai

為析取式(p

q)(p

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

簡單合取式，A1

…An

F當且僅當

任意Ai，Ai

FAi

簡單析取式，

A1

…An

T當且僅當

任意Ai，Ai

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

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

p

q

p

q

p

?q

(p

q)(q

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

q)?p?q?(p

q)?p

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

(q

r)(p

q)(p

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

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

(ppq)(qpq)最簡析取范式p

q

計算機科學(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)計算機科學(xué)與工程學(xué)院262.2析取范式和合取范式(二)求合取范式原式((pq)r)p

((pq)r)p

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

r)(pq)(p

r)計算機科學(xué)與工程學(xué)院272.2析取范式和合取范式討論：一個命題公式的析取范式不是唯一的，但同一命題公式的析取范式一定是等值的計算機科學(xué)與工程學(xué)院282.2析取范式和合取范式極小項(極大項):含有n個命題變元的簡單合取式(簡單析取式)并滿足每個命題變元和它的否定式不同時出現(xiàn)，而二者之一必出現(xiàn)且僅出現(xiàn)一次第i個命題變元或它的否定式出現(xiàn)在從左算起的第i位上(若無角標則按字典順序排列)若有ｎ個命題變元，則有2n個極小項（極大項）如果我們把命題變元看成1，命題變元的否定看成0，那么每一個極小項（極大項）都對應(yīng)一個二進制數(shù)，因而也對應(yīng)一個十進制數(shù)計算機科學(xué)與工程學(xué)院292.2析取范式和合取范式極小項的編碼:對應(yīng)成真賦值三個變元p、q、r可構(gòu)造8個極小項：

?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計算機科學(xué)與工程學(xué)院302.2析取范式和合取范式極大項的編碼:對應(yīng)成假賦值如三個變元p、q、r，其記法如下：p∨q∨rFFF0記作M0p∨q∨?rFFT1記作M1p∨?q∨rFTF2記作M2p∨?q∨?rFTT3記作M3……?p∨?q∨?rTTT7記作M7計算機科學(xué)與工程學(xué)院312.2析取范式和合取范式定理:設(shè)mi和Mi是命題變元p1,p2…pn形成的極小項和極大項，則：(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計算機科學(xué)與工程學(xué)院322.2析取范式和合取范式

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

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

為使B為F的指派所以A

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

(pjpj)(Ai

pj)(Ai

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

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

∧(q→?r)∧(?r→(p∨q))計算機科學(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不去。計算機科學(xué)與工程學(xué)院422.2析取范式和合取范式主合取范式任何一個命題公式都可求得它的主合取范式

一個命題公式的主合取范式是唯一的

在真值表中，令命題公式的真值為“F”的指派就對應(yīng)其主合取范式的一個極大項計算機科學(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計算機科學(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計算機科學(xué)與工程學(xué)院452.2析取范式和合取范式討論：具有n個變元的命題公式有多少個不同的主析取范式？對于含有ｎ個變元的命題公式，必定可寫出22n個主析取范式(包括F)。同理，含有ｎ個變元的命題公式，也可寫出22n個主合取范式(包括T)。計算機科學(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é)合的)排斥或(異或)符號：“⊕”()pqp⊕qFFFFTTTFTTTF47計算機科學(xué)與工程學(xué)院2.3聯(lián)結(jié)詞的完備集“與非”聯(lián)結(jié)詞：符號“↑”(p↑q)讀作：“p與q的否定”(p↑q)?(p∧q)pqp↑qFFTFTTTFTTTF48計算機科學(xué)與工程學(xué)院2.3聯(lián)結(jié)詞的完備集“或非”聯(lián)結(jié)詞：符號：“↓”

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

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

q

(p

q)(p

q)計算機科學(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)計算機科學(xué)與工程學(xué)院522.4消解法可滿足性問題：用于證明A是否永真用于驗證邏輯蘊涵A1…Ak

B永真當且僅當A1…Ak

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

=plc=p，如果l

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

lcRes(C1,C2)=C1′

C2′定理：C1C2?Res(C1,C2)消解式是原公式的邏輯推論討論！2.4消解法計算機科學(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可以擴展為

v(p)=F如果p=l

v(p)=T如果p=lc

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

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

計算機科學(xué)與工程學(xué)院582.4消解法消解算法（分層飽和法）輸入：合式公式A輸出：yes(A可滿足)，no(A不可滿足)計算機科學(xué)與工程學(xué)院592.4消解法求A的合取范式S.令i=0,S(0)=S的所有簡單析取式組成的集合.若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