1、12.2 命題邏輯等值演算 2.2.1 等值式與等值演算等值式與等值演算 等值式與基本等值式等值式與基本等值式 真值表法與等值演算法真值表法與等值演算法 2.2.2 聯(lián)結(jié)詞完備集聯(lián)結(jié)詞完備集 真值函數(shù)真值函數(shù) 聯(lián)結(jié)詞完備集聯(lián)結(jié)詞完備集 與非聯(lián)結(jié)詞和或非聯(lián)結(jié)詞與非聯(lián)結(jié)詞和或非聯(lián)結(jié)詞2等值式定義定義2.11 若等價(jià)式若等價(jià)式AB是重言式是重言式, 則稱則稱A與與B等值等值, 記作記作AB, 并稱并稱AB是是等值式等值式說明說明: (1) 是是元語言符號元語言符號, 不要混同于不要混同于和和=(2) A與與B等值當(dāng)且僅當(dāng)?shù)戎诞?dāng)且僅當(dāng)A與與B在所有可能賦值下的真值都相在所有可能賦值下的真值都相同同,

2、即即A與與B有相同的真值表有相同的真值表(3) n個(gè)命題變項(xiàng)的真值表共有個(gè)命題變項(xiàng)的真值表共有 個(gè)個(gè), 故每個(gè)命題公式都有故每個(gè)命題公式都有無窮多個(gè)等值的命題公式無窮多個(gè)等值的命題公式(4) 可能有啞元出現(xiàn)可能有啞元出現(xiàn). 在在B中出現(xiàn)中出現(xiàn), 但不在但不在A中出現(xiàn)的命題變中出現(xiàn)的命題變項(xiàng)稱作項(xiàng)稱作A的的啞元啞元. 同樣同樣,在在A中出現(xiàn)中出現(xiàn), 但不在但不在B中出現(xiàn)的命題變中出現(xiàn)的命題變項(xiàng)稱作項(xiàng)稱作B的啞元的啞元. 啞元的值不影響命題公式的真值啞元的值不影響命題公式的真值.n223真值表法例例1 判斷判斷 (p q) 與與 p q 是否等值是否等值解解結(jié)論結(jié)論: (p q) ( p q) p

3、 q p q p q (p q) p q (p q)( p q) 0 0 1 1 0 1 1 1 0 1 1 0 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 0 1 0 0 14真值表法(續(xù))例例2 判斷下述判斷下述3個(gè)公式之間的等值關(guān)系個(gè)公式之間的等值關(guān)系: p(qr), (pq)r, (p q)r解解 p q r p(qr) (pq)r (p q)r 0 0 0 1 0 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 p(qr)與與(p q)r等值等值

4、, 但與但與(pq)r不等值不等值5基本等值式雙重否定律雙重否定律 AA (還原律還原律 reductive law)冪等律冪等律 A AA, A AA (idempotent law)交換律交換律 A BB A, A BB A (commutative law)結(jié)合律結(jié)合律 (A B) CA (B C) (A B) CA (B C) (associative law)分配律分配律 A (B C)(A B) (A C) A (B C)(A B) (A C) (distributive law)德摩根律德摩根律 (A B)AB (A B)AB (De Morgan law)吸收律吸收律 A (A

5、 B)A A (A B)A (absorbing law)6基本等值式(續(xù))零律零律 A 11, A 00 同一律同一律 A 0A, A 1A (0-1 law)排中律排中律 AA1 (excluded middle law)矛盾律矛盾律 AA0 (contradiction law)蘊(yùn)涵等值式蘊(yùn)涵等值式 ABA B等價(jià)等值式等價(jià)等值式 AB(AB) (BA)假言易位假言易位 ABBA等價(jià)否定等值式等價(jià)否定等值式 ABAB歸謬論歸謬論 (AB) (AB)A7等值演算等值演算等值演算: 由已知的等值式推演出新的等值式的過程由已知的等值式推演出新的等值式的過程置換規(guī)則置換規(guī)則: 若若AB, 則則

6、(B) (A) 例例3 證明證明 p(qr) (p q)r證證 p(qr) p ( q r) （蘊(yùn)涵等值式）蘊(yùn)涵等值式） ( pq) r （結(jié)合律）結(jié)合律） (p q) r （德摩根律）德摩根律） (p q)r （蘊(yùn)涵等值式）蘊(yùn)涵等值式）8實(shí)例等值演算不能直接證明兩個(gè)公式不等值等值演算不能直接證明兩個(gè)公式不等值. 證明兩個(gè)公式不證明兩個(gè)公式不等值的基本思想是找到一個(gè)賦值使一個(gè)成真等值的基本思想是找到一個(gè)賦值使一個(gè)成真, 另一個(gè)成假另一個(gè)成假.例例4 證明證明: p(qr) (pq)r方法一方法一 真值表法（見例真值表法（見例2）方法二方法二 觀察法觀察法. 容易看出容易看出000使左邊成真使左

7、邊成真, 使右邊成假使右邊成假.方法三方法三 先用等值演算化簡公式先用等值演算化簡公式, 再觀察再觀察.9實(shí)例例例5 用等值演算法判斷下列公式的類型用等值演算法判斷下列公式的類型(1) q(pq) 解解 q(pq) q( p q) （蘊(yùn)涵等值式）蘊(yùn)涵等值式） q (pq) （德摩根律）德摩根律） p (qq) （交換律，結(jié)合律）交換律，結(jié)合律） p 0 （矛盾律）矛盾律） 0 （零律）（零律）該式為矛盾式該式為矛盾式.10實(shí)例(續(xù))(2) (pq)( qp) 解解 (pq)( qp) ( p q)(qp) （蘊(yùn)涵等值式）蘊(yùn)涵等值式） ( p q)( p q) （交換律）交換律） 1該式為重言式

8、該式為重言式.11實(shí)例(續(xù))(3) (p q) (pq) r) 解解 (p q) (pq) r) (p (qq) r （分配律）分配律） p 1 r （排中律）排中律） p r （同一律）同一律）非重言式的可滿足式非重言式的可滿足式. .如如101是它的成真賦值是它的成真賦值, ,000是它的是它的成假賦值成假賦值.總結(jié)總結(jié):A為矛盾式當(dāng)且僅當(dāng)為矛盾式當(dāng)且僅當(dāng)A0; A為重言式當(dāng)且僅當(dāng)為重言式當(dāng)且僅當(dāng)A1說明說明:演算步驟不惟一演算步驟不惟一, ,應(yīng)盡量使演算短些應(yīng)盡量使演算短些12真值函數(shù)定義定義2.12 稱稱F:0,1n0,1為為n元元真值函數(shù)真值函數(shù)n元真值函數(shù)共有元真值函數(shù)共有 個(gè)個(gè)每

9、一個(gè)命題公式對應(yīng)于一個(gè)真值函數(shù)每一個(gè)命題公式對應(yīng)于一個(gè)真值函數(shù)每一個(gè)真值函數(shù)對應(yīng)無窮多個(gè)命題公式每一個(gè)真值函數(shù)對應(yīng)無窮多個(gè)命題公式n221元真值函數(shù)元真值函數(shù) p 0 0 0 1 1 1 0 1 0 1 )1(3)1(2)1(1)1(0FFFF132元真值函數(shù)元真值函數(shù) p q 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 p q 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 1

10、0 1)2(7)2(6)2(5)2(4)2(3)2(2)2(1)2(0FFFFFFFF)2(15)2(14)2(13)2(12)2(11)2(10)2(9)2(8FFFFFFFF14聯(lián)結(jié)詞完備集定義定義2.13 設(shè)設(shè)S是一個(gè)聯(lián)結(jié)詞集合是一個(gè)聯(lián)結(jié)詞集合, 如果任何如果任何n(n 1) 元真值元真值函數(shù)都可以由僅含函數(shù)都可以由僅含S中的聯(lián)結(jié)詞構(gòu)成的公式表示中的聯(lián)結(jié)詞構(gòu)成的公式表示, ,則稱則稱S是是聯(lián)結(jié)詞完備集聯(lián)結(jié)詞完備集定理定理2.1 下述聯(lián)結(jié)詞集合都是完備集下述聯(lián)結(jié)詞集合都是完備集:(1) S1= , , , , (2) S2= , , , (3) S3= , , (4) S4= , (5)

11、S5= , (6) S6= , AB (AB) (BA)AB A BA B (A B) ( AB)A B ( AB)A B ( A) B AB15復(fù)合聯(lián)結(jié)詞與非式與非式: p q(p q), 稱作稱作與非聯(lián)結(jié)詞與非聯(lián)結(jié)詞或非式或非式: p q(p q), 稱作稱作或非聯(lián)結(jié)詞或非聯(lián)結(jié)詞p q為真當(dāng)且僅當(dāng)為真當(dāng)且僅當(dāng)p,q不同時(shí)為真不同時(shí)為真p q為真當(dāng)且僅當(dāng)為真當(dāng)且僅當(dāng)p,q不同時(shí)為假不同時(shí)為假定理定理2.2 , 是聯(lián)結(jié)詞完備集是聯(lián)結(jié)詞完備集證證 p (p p) p p p q (p q) (p q) (p q) (p q)得證得證 是聯(lián)結(jié)詞完備集是聯(lián)結(jié)詞完備集. 對于對于 可類似證明可類似證明

12、.16作業(yè)：P81 15（1）， 16（1）， 17， 18（2） 19（1）， 20， 21（1）思考題：1 聯(lián)結(jié)詞完備集 2 其它聯(lián)結(jié)詞172.3 范式(normal form) 2.3.1 析取范式與合取范式析取范式與合取范式 簡單析取式與簡單合取式簡單析取式與簡單合取式 析取范式與合取范式析取范式與合取范式 2.3.2 主析取范式與主合取范式主析取范式與主合取范式 極小項(xiàng)與極大項(xiàng)極小項(xiàng)與極大項(xiàng)18簡單析取式與簡單合取式文字文字: :命題變項(xiàng)及其否定的統(tǒng)稱命題變項(xiàng)及其否定的統(tǒng)稱簡單析取式簡單析取式: :有限個(gè)文字構(gòu)成的析取式有限個(gè)文字構(gòu)成的析取式如如 p, q, pq, p q r, 簡

13、單合取式簡單合取式: :有限個(gè)文字構(gòu)成的合取式有限個(gè)文字構(gòu)成的合取式如如 p, q, pq, p q r, 定理定理2.3 (1) 一個(gè)簡單析取式是重言式當(dāng)且僅當(dāng)它同時(shí)含一個(gè)簡單析取式是重言式當(dāng)且僅當(dāng)它同時(shí)含某個(gè)命題變項(xiàng)和它的否定某個(gè)命題變項(xiàng)和它的否定(2) 一個(gè)簡單合取式是矛盾式當(dāng)且僅當(dāng)它同時(shí)含某個(gè)命題一個(gè)簡單合取式是矛盾式當(dāng)且僅當(dāng)它同時(shí)含某個(gè)命題變項(xiàng)和它的否定變項(xiàng)和它的否定19析取范式與合取范式析取范式析取范式(disjunctive(disjunctive) ): :由有限個(gè)簡單合取式組成的析取式由有限個(gè)簡單合取式組成的析取式 A1 A2Ar, 其中其中A1,A2,Ar是是簡單合取式簡單

14、合取式合取范式合取范式(conjunctive (conjunctive ) ): :由有限個(gè)簡單析取式組成的合取式由有限個(gè)簡單析取式組成的合取式 A1 A2Ar , 其中其中A1,A2,Ar是是簡單析取式簡單析取式范式范式(normal form)(normal form): :析取范式與合取范式的統(tǒng)稱析取范式與合取范式的統(tǒng)稱 定理定理2.4 (1) 一個(gè)析取范式是矛盾式當(dāng)且僅當(dāng)它的每一個(gè)一個(gè)析取范式是矛盾式當(dāng)且僅當(dāng)它的每一個(gè)簡單合取式都是矛盾式簡單合取式都是矛盾式(2) 一個(gè)合取范式是重言式當(dāng)且僅當(dāng)它的每一個(gè)簡單析取一個(gè)合取范式是重言式當(dāng)且僅當(dāng)它的每一個(gè)簡單析取式都是重言式式都是重言式20

15、范式存在定理定理定理2.5 任何命題公式都存在著與之等值的析取范式與合任何命題公式都存在著與之等值的析取范式與合 取范式取范式. .證證 求公求公式式A的范式的步驟：的范式的步驟：(1) 消去消去A中的中的, ABA B AB( A B) (AB)(2) 否定聯(lián)結(jié)詞否定聯(lián)結(jié)詞 的內(nèi)移或消去的內(nèi)移或消去 A A (A B)AB (A B)AB21范式存在定理(續(xù))(3) 使用分配律使用分配律 A (B C)(A B) (A C) 求合取范式求合取范式 A (B C)(A B) (A C) 求析取范式求析取范式例例1 1 求求 (pq)r 的析取范式與合取范式的析取范式與合取范式解解 (pq)r

16、( p q)r (pq)r 析取范式析取范式 (pr) ( qr) 合取范式合取范式注意注意: (1)公式的析取范式與合取范式不惟一。公式的析取范式與合取范式不惟一。 (2) 按字典序排列命題變元。按字典序排列命題變元。22極小項(xiàng)與極大項(xiàng)定義定義2.17 在含有在含有n個(gè)命題變項(xiàng)的簡單合取式個(gè)命題變項(xiàng)的簡單合取式( (簡單析取式簡單析取式) )中中, , 若每個(gè)命題變項(xiàng)均以文字的形式出現(xiàn)且僅出現(xiàn)一次；若每個(gè)命題變項(xiàng)均以文字的形式出現(xiàn)且僅出現(xiàn)一次； 第第i( (1 i n) )個(gè)文字個(gè)文字( (按下標(biāo)或字母順序排列按下標(biāo)或字母順序排列) )出現(xiàn)在左出現(xiàn)在左 起第起第i位上位上, ,稱這樣的簡單合

17、取式稱這樣的簡單合取式( (簡單析取式簡單析取式) )為為極小項(xiàng)極小項(xiàng)( (極大項(xiàng)極大項(xiàng)) )說明說明: :(1) n個(gè)命題變項(xiàng)產(chǎn)生個(gè)命題變項(xiàng)產(chǎn)生2n個(gè)極小項(xiàng)和個(gè)極小項(xiàng)和2n個(gè)極大項(xiàng)個(gè)極大項(xiàng) (2) 2n個(gè)極小項(xiàng)個(gè)極小項(xiàng)( (極大項(xiàng)極大項(xiàng)) )均互不等值均互不等值 (3) 用用mi表示第表示第i個(gè)極小項(xiàng)個(gè)極小項(xiàng), ,其中其中i是該極小項(xiàng)成真賦值的十是該極小項(xiàng)成真賦值的十進(jìn)制表示進(jìn)制表示. 用用Mi表示第表示第i個(gè)極大項(xiàng)個(gè)極大項(xiàng), ,其中其中i是該極大項(xiàng)成假賦值的十是該極大項(xiàng)成假賦值的十進(jìn)制表示進(jìn)制表示, mi( (Mi) )稱為極小項(xiàng)稱為極小項(xiàng)( (極大項(xiàng)極大項(xiàng)) )的名稱的名稱. 23極小項(xiàng)

18、與極大項(xiàng)(續(xù))定理定理2.6 設(shè)設(shè)mi 與與Mi是由同一組命題變項(xiàng)形成的極小項(xiàng)和極大項(xiàng)是由同一組命題變項(xiàng)形成的極小項(xiàng)和極大項(xiàng), 則則 mi Mi , Mi mi 極小項(xiàng)極小項(xiàng) 極大項(xiàng)極大項(xiàng) 公式公式 成真賦值成真賦值 名稱名稱 公式公式 成假賦值成假賦值 名稱名稱 pq 0 0 m0 p q 0 0 M0 p q 0 1 m1 pq 0 1 M1 pq 1 0 m2 p q 1 0 M2 p q 1 1 m3 pq 1 1 M3 p,q形成的極小項(xiàng)與極大項(xiàng)形成的極小項(xiàng)與極大項(xiàng)24主析取范式與主合取范式主析取范式主析取范式: :由極小項(xiàng)構(gòu)成的析取范式由極小項(xiàng)構(gòu)成的析取范式主合取范式主合取范式:

19、:由極大項(xiàng)構(gòu)成的合取范式由極大項(xiàng)構(gòu)成的合取范式例如，例如，n=3, 命題變項(xiàng)為命題變項(xiàng)為p, q, r時(shí)，時(shí)， ( pq r) ( p q r) m1 m3 是是主析取范式主析取范式 (p qr) ( p qr) M1 M5 是是主合取范式主合取范式定理定理2.7 任何命題公式都存在著與之等值的主析取范任何命題公式都存在著與之等值的主析取范 式和主合取范式式和主合取范式, 并且是惟一的并且是惟一的. .25求主析取范式的步驟設(shè)公式設(shè)公式A含命題變項(xiàng)含命題變項(xiàng)p1,p2,pn(1) 求求A的析取范式的析取范式A =B1 B2 Bs, 其中其中Bj是簡單是簡單合取式合取式 j=1,2, ,s (2

20、) 若某個(gè)若某個(gè)Bj既不含既不含pi, 又不含又不含 pi, 則將則將Bj展開成展開成 Bj Bj (pi pi) (Bj pi) (Bj pi) 重復(fù)這個(gè)過程重復(fù)這個(gè)過程, 直到所有簡單合取式都是長度為直到所有簡單合取式都是長度為n的的 極小項(xiàng)為止極小項(xiàng)為止(3) 消去重復(fù)出現(xiàn)的極小項(xiàng)消去重復(fù)出現(xiàn)的極小項(xiàng), 即用即用mi代替代替mi mi(4) 將極小項(xiàng)按下標(biāo)從小到大排列將極小項(xiàng)按下標(biāo)從小到大排列26求主合取范式的步驟設(shè)公式設(shè)公式A含命題變項(xiàng)含命題變項(xiàng)p1,p2,pn(1) 求求A的合取范式的合取范式A =B1 B2 Bs, 其中其中Bj是簡單析是簡單析 取式取式 j=1,2, ,s (2)

21、 若某個(gè)若某個(gè)Bj既不含既不含pi, 又不含又不含 pi, 則將則將Bj展開成展開成 Bj Bj (pi pi) (Bj pi) (Bj pi) 重復(fù)這個(gè)過程重復(fù)這個(gè)過程, 直到所有簡單析取式都是長度為直到所有簡單析取式都是長度為n的極的極大項(xiàng)為止大項(xiàng)為止(3) 消去重復(fù)出現(xiàn)的極大項(xiàng)消去重復(fù)出現(xiàn)的極大項(xiàng), 即用即用Mi代替代替Mi Mi(4) 將極大項(xiàng)按下標(biāo)從小到大排列將極大項(xiàng)按下標(biāo)從小到大排列27實(shí)例例例1(1(續(xù)續(xù)) ) 求求 (pq)r 的主析取范式與主合取范式的主析取范式與主合取范式解解 (1) (1) (pq)r (pq)r pq (pq) 1 同一律同一律 (pq) ( r r)

22、排中律排中律 (pqr) (pq r) 分配律分配律 m4 m5 r ( p p) ( q q)r 同一律同一律, 排中律排中律 ( pqr) ( p qr) (pqr) (p qr) m0 m2 m4 m6 分配律分配律得得 (pq)r m0 m2 m4 m5 m6可記作可記作 (0,2,4,5,6)28實(shí)例(續(xù))(2) (pq)r (pr) ( qr) pr p 0r 同一律同一律 p (qq)r 矛盾律矛盾律 (p qr) (pqr) 分配律分配律 M1 M3 qr (pp)qr 同一律同一律, 矛盾律矛盾律 (pqr) ( pqr) 分配律分配律 M3 M7得得 (pq)r M1 M3

23、 M7可記作可記作 (1,3,7)29快速求法設(shè)公式含有設(shè)公式含有n個(gè)命題變項(xiàng)個(gè)命題變項(xiàng), 則則長度為長度為k的簡單合取式可展開成的簡單合取式可展開成2n k個(gè)極小項(xiàng)的析取個(gè)極小項(xiàng)的析取例如例如 公式含公式含p,q,r q ( p qr) ( p q r) (p qr) (p q r) m2 m3 m6 m7長度為長度為k的簡單析取式可展開成的簡單析取式可展開成2n k個(gè)極大項(xiàng)的合取個(gè)極大項(xiàng)的合取例如例如 pr (p qr) (pqr) M1 M330實(shí)例例例2 (1) 求求 A ( p q) ( pq r) r 的主析取范式的主析取范式解解 用快速求法用快速求法(1) p q ( p qr)

24、 ( p q r) m2 m3 pq r m1 r ( pq r) ( p q r) (pq r) (p q r) m1 m3 m5 m7得得 A m1 m2 m3 m5 m7 (1,2,3,5,7)31實(shí)例(續(xù))(2) 求求 Bp (p qr)的主合取范式的主合取范式解解 p ( p q r) ( p qr) ( pq r) ( pqr) M4 M5 M6 M7 p qr M1得得 B M1 M4 M5 M6 M7 (1,4,5,6,7)32主析取范式的用途(1) 求公式的成真賦值和成假賦值求公式的成真賦值和成假賦值設(shè)公式設(shè)公式A含含n個(gè)命題變項(xiàng)個(gè)命題變項(xiàng), A的主析取范式有的主析取范式有s

25、個(gè)極小項(xiàng)個(gè)極小項(xiàng), 則則A有有s個(gè)成真賦值個(gè)成真賦值, 它們是極小項(xiàng)下標(biāo)的二進(jìn)制表示它們是極小項(xiàng)下標(biāo)的二進(jìn)制表示, 其余其余2n s個(gè)賦值都是成假賦值個(gè)賦值都是成假賦值 例如例如 (pq)r m0 m2 m4 m5 m6 成真賦值成真賦值: 000,010,100,101,110; 成假賦值成假賦值: 001,011,11133主析取范式的用途(續(xù))(2) 判斷公式的類型判斷公式的類型 設(shè)設(shè)A含含n個(gè)命題變項(xiàng)，則個(gè)命題變項(xiàng)，則 A為重言式當(dāng)且僅當(dāng)為重言式當(dāng)且僅當(dāng)A的主析取范式含的主析取范式含2n個(gè)極小項(xiàng)個(gè)極小項(xiàng)A為矛盾式當(dāng)且僅當(dāng)為矛盾式當(dāng)且僅當(dāng) A的主析取范式不含任何極小項(xiàng)的主析取范式不含任何

26、極小項(xiàng), ,記作記作0 A為可滿足式當(dāng)且僅當(dāng)為可滿足式當(dāng)且僅當(dāng)A的主析取范式中至少含一個(gè)的主析取范式中至少含一個(gè)極小項(xiàng)極小項(xiàng)34實(shí)例例例3 用主析取范式判斷公式的類型用主析取范式判斷公式的類型:(1) A(pq) q (2) Bp(p q) (3) C(p q)r解解 (1) A ( p q) q ( pq) q 0 矛盾式矛盾式(2) B p (p q) 1 m0 m1 m2 m3 重言式重言式(3) C (p q) r ( pq) r ( pq r) ( pqr) ( pq r) ( p q r) (pq r) (p q r) m0 m1 m3 m5 m7 非重言式的可滿足非重言式的可滿足式式35主析取范式的用途(續(xù))(3) 判斷兩個(gè)公式是否等值判斷兩個(gè)公式是否等值例例4 用主析取范式判斷下面用主析取范式判斷下面2組公式是否等值組公式是否等值:(1) p與與( p q)(p q)解解 p p ( q q) (pq) (p q) m2 m3 ( p q)(p q) ( p q) (p q) (pq) (p q) m2 m3故故 p ( p q)(p q)36實(shí)例(續(xù))(2) (p q) r 與與 p (q r)解解 (p q) r (p qr) (p q r) ( pq r) ( p q r) (pq r) (p q r) m1 m