1、作 業(yè),2.11 p,q:0 r,s:1 (p(q r) (r s) (p r) ( q s) (p q r) (p q r) (p q r s) (p q r s),1,2.2 命題邏輯等值演算,2.2.1 等值式與等值演算 等值式與基本等值式 真值表法與等值演算法 2.2.2 聯(lián)結(jié)詞完備集 真值函數(shù) 聯(lián)結(jié)詞完備集 與非聯(lián)結(jié)詞和或非聯(lián)結(jié)詞,2,等值式,3,定義2.11 若等價(jià)式AB是重言式, 則稱A與B等值, 記作 AB, 并稱AB是等值式 說(shuō)明: (1) 是元語(yǔ)言符號(hào), 不要混同于和= (2) A與B等值當(dāng)且僅當(dāng)A與B在所有可能賦值下的真值都相 同, 即A與B有相同的真值表 (3) n個(gè)命

2、題變項(xiàng)的真值表共有 個(gè), 故每個(gè)命題公式都有 無(wú)窮多個(gè)等值的命題公式 (4) 可能有啞元出現(xiàn). 在B中出現(xiàn), 但不在A中出現(xiàn)的命題變項(xiàng)稱作A的啞元. 同樣,在A中出現(xiàn), 但不在B中出現(xiàn)的命題變項(xiàng)稱作B的啞元. 啞元的值不影響命題公式的真值.,真值表法,例1 判斷 (pq) 與 pq 是否等值 解,4,結(jié)論: (pq) (pq),真值表法(續(xù)),例2 判斷下述3個(gè)公式之間的等值關(guān)系: p(qr), (pq)r, (pq)r 解,5,p(qr)與(pq)r等值, 但與(pq)r不等值,基本等值式,雙重否定律 AA 冪等律 AAA, AAA 交換律 ABBA, ABBA 結(jié)合律 (AB)CA(BC)

3、 (AB)CA(BC) 分配律 A(BC)(AB)(AC) A(BC) (AB)(AC) 德摩根律 (AB)AB (AB)AB 吸收律 A(AB)A, A(AB)A,6,基本等值式(續(xù)),零律 A11, A00 同一律 A0A, A1A 排中律 AA1 矛盾律 AA0 蘊(yùn)涵等值式 ABAB 等價(jià)等值式 AB(AB)(BA) 假言易位 ABBA 等價(jià)否定等值式 ABAB 歸謬論 (AB)(AB) A,7,等值演算,等值演算: 由已知的等值式推演出新的等值式的過(guò)程 置換規(guī)則: 若AB, 則(B)(A) 例3 證明 p(qr) (pq)rp49,例2.12(1) 證 p(qr) p(qr) （蘊(yùn)涵等

4、值式） (pq)r （結(jié)合律） (pq)r （德摩根律） (pq) r （蘊(yùn)涵等值式）,8,實(shí)例,9,等值演算不能直接證明兩個(gè)公式不等值. 證明兩個(gè)公式不 等值的基本思想是找到一個(gè)賦值使一個(gè)成真, 另一個(gè)成假. 例4 證明: p(qr) (pq) r p52 方法一 真值表法（見(jiàn)例2） 方法二 觀察法. 容易看出000使左邊成真, 使右邊成假. 方法三 先用等值演算化簡(jiǎn)公式, 再觀察.,實(shí)例,例5 用等值演算法判斷下列公式的類型 (1) q(pq) 解 q(pq) q(pq) （蘊(yùn)涵等值式） q(pq) （德摩根律） p(qq) （交換律，結(jié)合律） p0 （矛盾律） 0 （零律） 該式為矛盾式

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

6、數(shù)對(duì)應(yīng)無(wú)窮多個(gè)命題公式,14,2元真值函數(shù),聯(lián)結(jié)詞完備集,定義2.13 設(shè)S是一個(gè)聯(lián)結(jié)詞集合, 如果任何n(n1) 元真值 函數(shù)都可以由僅含S中的聯(lián)結(jié)詞構(gòu)成的公式表示,則稱S是 聯(lián)結(jié)詞完備集 定理2.1 下述聯(lián)結(jié)詞集合都是完備集: (1) S1=, , , , (2) S2=, , , (3) S3=, , (4) S4=, (5) S5=, (6) S6=, ,15,AB (AB)(BA),AB AB,AB (AB) (AB),AB (AB),AB (A)B AB,復(fù)合聯(lián)結(jié)詞,與非式: pq(pq), 稱作與非聯(lián)結(jié)詞 或非式: pq(pq), 稱作或非聯(lián)結(jié)詞 pq為真當(dāng)且僅當(dāng)p,q不同時(shí)為真

7、 pq為真當(dāng)且僅當(dāng)p,q同時(shí)為假 定理2.2 ,是聯(lián)結(jié)詞完備集 證 p (pp) pp pq (pq) (pq) (pq)(pq) 得證是聯(lián)結(jié)詞完備集. 對(duì)于可類似證明.,16,2.3 范式,2.3.1 析取范式與合取范式 簡(jiǎn)單析取式與簡(jiǎn)單合取式 析取范式與合取范式 2.3.2 主析取范式與主合取范式 極小項(xiàng)與極大項(xiàng) 主析取范式與主合取范式 主范式的用途,17,簡(jiǎn)單析取式與簡(jiǎn)單合取式,文字:命題變項(xiàng)及其否定的統(tǒng)稱 簡(jiǎn)單析取式:有限個(gè)文字構(gòu)成的析取式 如 p, q, pq, pqr, 簡(jiǎn)單合取式:有限個(gè)文字構(gòu)成的合取式 如 p, q, pq, pqr, 定理2.3 (1) 一個(gè)簡(jiǎn)單析取式是重言式

8、當(dāng)且僅當(dāng)它同時(shí)含 某個(gè)命題變項(xiàng)和它的否定 (2) 一個(gè)簡(jiǎn)單合取式是矛盾式當(dāng)且僅當(dāng)它同時(shí)含某個(gè)命題 變項(xiàng)和它的否定,18,析取范式與合取范式,析取范式:由有限個(gè)簡(jiǎn)單合取式組成的析取式 A1A2Ar, 其中A1,A2,Ar是簡(jiǎn)單合取式 合取范式:由有限個(gè)簡(jiǎn)單析取式組成的合取式 A1A2Ar , 其中A1,A2,Ar是簡(jiǎn)單析取式 范式:析取范式與合取范式的統(tǒng)稱 定理2.4 (1) 一個(gè)析取范式是矛盾式當(dāng)且僅當(dāng)它的每一個(gè) 簡(jiǎn)單合取式都是矛盾式 (2) 一個(gè)合取范式是重言式當(dāng)且僅當(dāng)它的每一個(gè)簡(jiǎn)單析取 式都是重言式,19,范式存在定理,定理2.5 任何命題公式都存在著與之等值的析取范式與合 取范式. 證

9、求公式A的范式的步驟： (1) 消去A中的, ABAB AB(AB)(AB) (2) 否定聯(lián)結(jié)詞的內(nèi)移或消去 A A (AB)AB (AB)AB,20,范式存在定理(續(xù)),(3) 使用分配律 A(BC)(AB)(AC) 求合取范式 A(BC) (AB)(AC) 求析取范式 例1 求(pq)r 的析取范式與合取范式 解 (pq)r (pq)r (pq)r 析取范式 (pr)(qr) 合取范式 注意: 公式的析取范式與合取范式不惟一.,21,極小項(xiàng)與極大項(xiàng),定義2.17 在含有n個(gè)命題變項(xiàng)的簡(jiǎn)單合取式(簡(jiǎn)單析取式) 中,若每個(gè)命題變項(xiàng)均以文字的形式出現(xiàn)且僅出現(xiàn)一次， 而且第i(1in)個(gè)文字(按下

10、標(biāo)或字母順序排列)出現(xiàn)在左 起第i位上,稱這樣的簡(jiǎn)單合取式(簡(jiǎn)單析取式)為極小項(xiàng) (極大項(xiàng)) 說(shuō)明:(1) n個(gè)命題變項(xiàng)產(chǎn)生2n個(gè)極小項(xiàng)和2n個(gè)極大項(xiàng) (2) 2n個(gè)極小項(xiàng)(極大項(xiàng))均互不等值 (3) 用mi表示第i個(gè)極小項(xiàng),其中i是該極小項(xiàng)成真賦值的十進(jìn)制表示. 用Mi表示第i個(gè)極大項(xiàng),其中i是該極大項(xiàng)成假賦值的十進(jìn)制表示, mi(Mi)稱為極小項(xiàng)(極大項(xiàng))的名稱.,22,極小項(xiàng)與極大項(xiàng)(續(xù)),定理2.6 設(shè)mi 與Mi是由同一組命題變項(xiàng)形成的極小項(xiàng)和極大項(xiàng), 則 mi Mi , Mi mi,23,主析取范式與主合取范式,主析取范式:由極小項(xiàng)構(gòu)成的析取范式 主合取范式:由極大項(xiàng)構(gòu)成的合取范式

11、 例如，n=3, 命題變項(xiàng)為p, q, r時(shí)， (pqr)(pqr) m1m3 是主析取范式 (pqr)(pqr) M1M5 是主合取范式 定理2.7 任何命題公式都存在著與之等值的主析取范式和 主合取范式, 并且是惟一的.,24,求主析取范式的步驟,設(shè)公式A含命題變項(xiàng)p1,p2,pn (1) 求A的析取范式A=B1 B2 Bs, 其中Bj是簡(jiǎn)單合取 式 j=1,2, ,s (2) 若某個(gè)Bj既不含pi, 又不含pi, 則將Bj展開(kāi)成 Bj Bj(pipi) (Bjpi)(Bjpi) 重復(fù)這個(gè)過(guò)程, 直到所有簡(jiǎn)單合取式都是長(zhǎng)度為n的極小 項(xiàng)為止 (3) 消去重復(fù)出現(xiàn)的極小項(xiàng), 即用mi代替mi

12、mi (4) 將極小項(xiàng)按下標(biāo)從小到大排列,25,求主合取范式的步驟,設(shè)公式A含命題變項(xiàng)p1,p2,pn (1) 求A的合取范式A=B1B2 Bs, 其中Bj是簡(jiǎn)單析取 式 j=1,2, ,s (2) 若某個(gè)Bj既不含pi, 又不含pi, 則將Bj展開(kāi)成 Bj Bj(pipi) (Bjpi)(Bjpi) 重復(fù)這個(gè)過(guò)程, 直到所有簡(jiǎn)單析取式都是長(zhǎng)度為n的極大 項(xiàng)為止 (3) 消去重復(fù)出現(xiàn)的極大項(xiàng), 即用Mi代替MiMi (4) 將極大項(xiàng)按下標(biāo)從小到大排列,26,實(shí)例,例1(續(xù)) 求(pq)r 的主析取范式與主合取范式 解 (1) (pq)r (pq)r pq (pq)1 同一律 (pq)(rr)

13、排中律 (pqr)(pqr) 分配律 m4m5 r (pp)(qq)r 同一律, 排中律 (pqr)(pqr)(pqr)(pqr) m0 m2 m4 m6 分配律 得 (pq)r m0 m2 m4 m5 m6 可記作 (0,2,4,5,6),27,實(shí)例(續(xù)),(2) (pq)r (pr)(qr) pr p0r 同一律 p(qq)r 矛盾律 (pqr)(pqr) 分配律 M1M3 qr (pp)qr 同一律, 矛盾律 (pqr)(pqr) 分配律 M3M7 得 (pq)r M1M3M7 可記作 (1,3,7),28,快速求法,設(shè)公式含有n個(gè)命題變項(xiàng), 則 長(zhǎng)度為k的簡(jiǎn)單合取式可展開(kāi)成2n-k個(gè)極

14、小項(xiàng)的析取 例如 公式含p,q,r q (pqr)(pqr)(pqr)(pqr) m2 m3 m6 m7 長(zhǎng)度為k的簡(jiǎn)單析取式可展開(kāi)成2n-k個(gè)極大項(xiàng)的合取 例如 pr (pqr)(pqr) M1M3,29,實(shí)例,例2 (1) 求 A (pq)(pqr)r的主析取范式 解 用快速求法 (1) pq (pqr)(pqr) m2 m3 pqr m1 r (pqr)(pqr)(pqr)(pqr) m1 m3 m5 m7 得 A m1 m2 m3 m5 m7 (1,2,3,5,7),30,實(shí)例(續(xù)),(2) 求 B p(pqr)的主合取范式 解 p (pqr)(pqr)(pqr)(pqr) M4M5M

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

16、0 A為可滿足式當(dāng)且僅當(dāng)A的主析取范式中至少含一個(gè)極小項(xiàng),33,實(shí)例,例3 用主析取范式判斷公式的類型: (1) A (pq)q (2) B p(pq) (3) C (pq)r 解 (1) A ( pq)q ( pq)q 0 矛盾式 (2) B p(pq) 1 m0m1m2m3 重言式 (3) C (pq)r (pq)r (pqr)(pqr)(pqr) (pqr)(pqr)(pqr) m0m1m3 m5m7 非重言式的可滿足式,34,主析取范式的用途(續(xù)),(3) 判斷兩個(gè)公式是否等值 例4 用主析取范式判斷下面2組公式是否等值: (1) p與(pq)(pq) 解 p p(qq) (pq)(p

17、q) m2m3 (pq)(pq) (pq)(pq) (pq)(pq) m2m3 故 p (pq)(pq),35,實(shí)例(續(xù)),36,(2) (pq)r 與 p(qr) 解 (pq)r (pqr)(pqr) (pqr)(pqr)(pqr)(pqr) m1m3m5 m6m7 p(qr) (pq)(p r) (pqr)(pqr)(pqr)(pqr) m5 m6m7 故 (pq)r p(qr),實(shí)例,例5 某單位要從A,B,C三人中選派若干人出國(guó)考察, 需滿 足下述條件: (1) 若A去, 則C必須去; (2) 若B去, 則C不能去; (3) A和B必須去一人且只能去一人. 問(wèn)有幾種可能的選派方案? 解 記p:派A去, q:派B去, r:派C去 (1) pr, (2) qr, (3) (pq)(pq) 求下式的成真賦值 A=(pr)(qr)(pq)(pq),37,實(shí)例(續(xù)),求A的主析取范式 A=(pr)(qr)(pq)(pq) (pr)(qr)(pq)(pq) (