離散數(shù)學(xué)之等值演算

1、11.3 命題邏輯等值演算命題邏輯等值演算 等值式等值式基本等值式基本等值式等值演算等值演算置換規(guī)則置換規(guī)則2等值式等值式 定義定義 若等價(jià)式若等價(jià)式AB是重言式，則稱是重言式，則稱A與與B等值等值，記作記作AB，并稱，并稱AB是是等值式等值式說(shuō)明：定義中，說(shuō)明：定義中，A,B,均為元語(yǔ)言符號(hào)均為元語(yǔ)言符號(hào), A或或B中中可能有啞元出現(xiàn)可能有啞元出現(xiàn).例如，在例如，在 (pq) ( p q) ( r r)中，中，r為左邊為左邊公式的啞元公式的啞元. 用真值表可驗(yàn)證兩個(gè)公式是否等值用真值表可驗(yàn)證兩個(gè)公式是否等值請(qǐng)驗(yàn)證：請(qǐng)驗(yàn)證：p(qr) (p q) r p(qr) (pq) r 3基本等值式基本

2、等值式 雙重否定律雙重否定律 : AA等冪律等冪律： A AA, A AA交換律交換律: A BB A, A BB A結(jié)合律結(jié)合律: (A B) CA (B C) (A B) CA (B C)分配律分配律: A (B C)(A B) (A C) A (B C) (A B) (A C)4基本等值式基本等值式( (續(xù)續(xù)) )德德摩根律摩根律: (A B)AB (A B)AB吸收律吸收律: A (A B)A, A (A B)A零律零律: A 11, A 00 同一律同一律: A 0A, A 1A排中律排中律: AA1矛盾律矛盾律: AA05基本等值式基本等值式( (續(xù)續(xù)) )蘊(yùn)涵等值式蘊(yùn)涵等值式:

3、ABA B等價(jià)等值式等價(jià)等值式: AB(AB) (BA)假言易位假言易位: ABBA等價(jià)否定等值式等價(jià)否定等值式: ABAB歸謬論歸謬論: (AB) (AB) A注意注意:A,B,C代表任意的命題公式代表任意的命題公式牢記這些等值式是繼續(xù)學(xué)習(xí)的基礎(chǔ)牢記這些等值式是繼續(xù)學(xué)習(xí)的基礎(chǔ)6等值演算與置換規(guī)則等值演算與置換規(guī)則 等值演算等值演算: 由已知的等值式推演出新的等值式的過(guò)程由已知的等值式推演出新的等值式的過(guò)程置換規(guī)則置換規(guī)則：若：若AB, 則則 (B) (A) 等值演算的基礎(chǔ)：等值演算的基礎(chǔ)： (1) 等值關(guān)系的性質(zhì)：自反、對(duì)稱、傳遞等值關(guān)系的性質(zhì)：自反、對(duì)稱、傳遞 (2) 基本的等值式基本的等

4、值式 (3) 置換規(guī)則置換規(guī)則 7應(yīng)用舉例應(yīng)用舉例證明兩個(gè)公式等值證明兩個(gè)公式等值 例例1 證明證明 p(qr) (p q)r證證 p(qr) p ( q r) （蘊(yùn)涵等值式，置換規(guī)則）（蘊(yùn)涵等值式，置換規(guī)則） ( pq) r （結(jié)合律，置換規(guī)則）（結(jié)合律，置換規(guī)則） (p q) r （德（德 摩根律，置換規(guī)則）摩根律，置換規(guī)則） (p q) r （蘊(yùn)涵等值式，置換規(guī)則）（蘊(yùn)涵等值式，置換規(guī)則） 說(shuō)明說(shuō)明: :也可以從右邊開(kāi)始演算（請(qǐng)做一遍）也可以從右邊開(kāi)始演算（請(qǐng)做一遍） 因?yàn)槊恳徊蕉加弥脫Q規(guī)則，故可不寫出因?yàn)槊恳徊蕉加弥脫Q規(guī)則，故可不寫出 熟練后，基本等值式也可以不寫出熟練后，基本等值式也

5、可以不寫出 8應(yīng)用舉例應(yīng)用舉例證明兩個(gè)公式不等值證明兩個(gè)公式不等值例例2 證明證明: p(qr) (pq) r 用等值演算不能直接證明兩個(gè)公式不等值用等值演算不能直接證明兩個(gè)公式不等值,證明兩證明兩個(gè)公式不等值的基本思想是找到一個(gè)賦值使一個(gè)成個(gè)公式不等值的基本思想是找到一個(gè)賦值使一個(gè)成真真,另一個(gè)成假另一個(gè)成假. 方法一方法一 真值表法（自己證）真值表法（自己證） 方法二方法二 觀察賦值法觀察賦值法. 容易看出容易看出000, 010等是左邊的等是左邊的的成真賦值，是右邊的成假賦值的成真賦值，是右邊的成假賦值. 方法三方法三 用等值演算先化簡(jiǎn)兩個(gè)公式，再觀察用等值演算先化簡(jiǎn)兩個(gè)公式，再觀察.9

6、應(yīng)用舉例應(yīng)用舉例判斷公式類型判斷公式類型 例例3 用等值演算法判斷下列公式的類型用等值演算法判斷下列公式的類型(1) q(pq) 解解 q(pq) q( p q) （蘊(yùn)涵等值式）（蘊(yùn)涵等值式） q (pq) （德（德 摩根律）摩根律） p (qq) （交換律，結(jié)合律）（交換律，結(jié)合律） p 0 （矛盾律）（矛盾律） 0 （零律）（零律）由最后一步可知，該式為矛盾式由最后一步可知，該式為矛盾式. 10例例3 (續(xù)續(xù))(2) (pq)( qp) 解解 (pq)( qp) ( p q)(qp) （蘊(yùn)涵等值式）（蘊(yùn)涵等值式） ( p q)( p q) （交換律）（交換律） 1由最后一步可知，該式為重言

7、式由最后一步可知，該式為重言式.問(wèn)：最后一步為什么等值于問(wèn)：最后一步為什么等值于1？ 11例例3 (續(xù)續(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說(shuō)明：演算步驟不惟一說(shuō)明：演算步驟不惟一,

8、,應(yīng)盡量使演算短些應(yīng)盡量使演算短些121.4 范式范式 析取范式與合取范式析取范式與合取范式 主析取范式與主合取范式主析取范式與主合取范式 13析取范式與合取范式析取范式與合取范式 文字文字: :命題變項(xiàng)及其否定的總稱命題變項(xiàng)及其否定的總稱簡(jiǎn)單析取式簡(jiǎn)單析取式: :有限個(gè)文字構(gòu)成的析取式有限個(gè)文字構(gòu)成的析取式如如 p, q, pq, p q r, 簡(jiǎn)單合取式簡(jiǎn)單合取式: :有限個(gè)文字構(gòu)成的合取式有限個(gè)文字構(gòu)成的合取式如如 p, q, pq, p q r, 析取范式析取范式: :由有限個(gè)簡(jiǎn)單合取式組成的析取式由有限個(gè)簡(jiǎn)單合取式組成的析取式 A1 A2Ar, 其中其中A1,A2,Ar是是簡(jiǎn)單合取式

9、簡(jiǎn)單合取式合取范式合取范式: :由有限個(gè)簡(jiǎn)單析取式組成的合取式由有限個(gè)簡(jiǎn)單析取式組成的合取式 A1 A2Ar , 其中其中A1,A2,Ar是是簡(jiǎn)單析取式簡(jiǎn)單析取式14析取范式與合取范式析取范式與合取范式( (續(xù)續(xù)) )范式范式: :析取范式與合取范式的總稱析取范式與合取范式的總稱 公式公式A的析取范式的析取范式: 與與A等值的析取范式等值的析取范式公式公式A的合取范式的合取范式: 與與A等值的合取范式等值的合取范式說(shuō)明：說(shuō)明： 單個(gè)文字既是簡(jiǎn)單析取式，又是簡(jiǎn)單合取式單個(gè)文字既是簡(jiǎn)單析取式，又是簡(jiǎn)單合取式pq r, p qr既是析取范式，又是合取范式既是析取范式，又是合取范式(為什么為什么?)

10、15命題公式的范式命題公式的范式 定理定理 任何命題公式都存在著與之等值的析取范式任何命題公式都存在著與之等值的析取范式與合取范式與合取范式. .求公求公式式A的范式的步驟：的范式的步驟： (1) 消去消去A中的中的, （若存在）（若存在） (2) 否定聯(lián)結(jié)詞否定聯(lián)結(jié)詞 的內(nèi)移或消去的內(nèi)移或消去 (3) 使用分配律使用分配律 對(duì)對(duì) 分配（析取范式）分配（析取范式） 對(duì)對(duì) 分配（合取范式）分配（合取范式）公式的范式存在，但不惟一公式的范式存在，但不惟一16求公式的范式舉例求公式的范式舉例 例例 求下列公式的析取范式與合取范式求下列公式的析取范式與合取范式(1) A=(pq)r解解 (pq)r (

11、 pq)r （消去（消去） pqr （結(jié)合律）（結(jié)合律）這既是這既是A的析取范式（由的析取范式（由3個(gè)簡(jiǎn)單合取式組成的析個(gè)簡(jiǎn)單合取式組成的析取式），又是取式），又是A的合取范式（由一個(gè)簡(jiǎn)單析取式的合取范式（由一個(gè)簡(jiǎn)單析取式組成的合取式）組成的合取式）17求公式的范式舉例求公式的范式舉例( (續(xù)續(xù)) )(2) B=(pq)r解解 (pq)r ( pq)r （消去第一個(gè)（消去第一個(gè)） ( pq) r （消去第二個(gè)（消去第二個(gè)） (p q) r （否定號(hào)內(nèi)移（否定號(hào)內(nèi)移德德 摩根律）摩根律）這一步已為析取范式（兩個(gè)簡(jiǎn)單合取式構(gòu)成）這一步已為析取范式（兩個(gè)簡(jiǎn)單合取式構(gòu)成）繼續(xù)：繼續(xù)： (p q) r

12、(p r) (q r) （ 對(duì)對(duì) 分配律）分配律）這一步得到合取范式（由兩個(gè)簡(jiǎn)單析取式構(gòu)成）這一步得到合取范式（由兩個(gè)簡(jiǎn)單析取式構(gòu)成） 182元真值函數(shù)對(duì)應(yīng)的真值表元真值函數(shù)對(duì)應(yīng)的真值表p q0 00 11 01 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 )2(7)2(6)2(5)2(4)2(3)2(2)2(1)2(0FFFFFFFFp q0 00 11 01 1 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 )2(15)2

13、(14)2(13)2(12)2(11)2(10)2(9)2(8FFFFFFFF19極小項(xiàng)與極大項(xiàng)極小項(xiàng)與極大項(xiàng) 定義定義 在含有在含有n個(gè)命題變項(xiàng)的簡(jiǎn)單合取式個(gè)命題變項(xiàng)的簡(jiǎn)單合取式( (簡(jiǎn)單析取式簡(jiǎn)單析取式) )中，中，若每個(gè)命題變項(xiàng)均以文字的形式出現(xiàn)且僅出現(xiàn)一次，稱這若每個(gè)命題變項(xiàng)均以文字的形式出現(xiàn)且僅出現(xiàn)一次，稱這樣的簡(jiǎn)單合取式樣的簡(jiǎn)單合取式( (簡(jiǎn)單析取式簡(jiǎn)單析取式) )為為極小項(xiàng)極小項(xiàng)( (極大項(xiàng)）極大項(xiàng)）.說(shuō)明：說(shuō)明：n 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)n 2n個(gè)極小項(xiàng)（極大項(xiàng)）均互不等值個(gè)極小項(xiàng)（極大項(xiàng)）均互不等值n 在極小項(xiàng)和極大項(xiàng)中文字

14、均按下標(biāo)或字母順序排列在極小項(xiàng)和極大項(xiàng)中文字均按下標(biāo)或字母順序排列n 用用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)) )的名稱的名稱. n mi與與Mi的關(guān)系的關(guān)系: : mi Mi , Mi mi 20極小項(xiàng)與極大項(xiàng)極小項(xiàng)與極大項(xiàng)( (續(xù)續(xù)) )由由p, q兩個(gè)命題變項(xiàng)形成的極小項(xiàng)與極大項(xiàng)兩個(gè)命題變項(xiàng)形成的極小項(xiàng)與極大項(xiàng) 公式公式 成真賦值成真賦

15、值名稱名稱 公式公式 成假賦值成假賦值名稱名稱 p q p q p q p q0 0 0 1 1 0 1 1 m0m1m2m3 p q p q p q p q 0 0 0 1 1 0 1 1 M0M1M2M3 極小項(xiàng)極小項(xiàng) 極大項(xiàng)極大項(xiàng) 21 由由p, q, r三個(gè)命題變項(xiàng)形成的極小項(xiàng)與極大項(xiàng)三個(gè)命題變項(xiàng)形成的極小項(xiàng)與極大項(xiàng) 極小項(xiàng)極小項(xiàng) 極大項(xiàng)極大項(xiàng) 公式公式 成真成真賦值賦值名稱名稱 公式公式 成假成假賦值賦值名稱名稱 p q r p q r p q r p q rp q rp q rp q rp q r0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1m0m

16、1m2m3m4m5m6m7p q r p q r p q r p q r p q r p q r p q r p q r 0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1M0M1M2M3M4M5M6M7 22主析取范式與主合取范式主析取范式與主合取范式 主析取范式主析取范式: : 由極小項(xiàng)構(gòu)成的析取范式由極小項(xiàng)構(gòu)成的析取范式主合取范式主合取范式: : 由極大項(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) M

17、1 M5 是是主合取范式主合取范式 A的主析取范式的主析取范式: 與與A等值的主析取范式等值的主析取范式 A的主合取范式的主合取范式: : 與與A等值的主合取范式等值的主合取范式. 23主析取范式與主合取范式主析取范式與主合取范式( (續(xù)續(xù)) )定理定理 任何命題公式都存在著與之等值的主析取范任何命題公式都存在著與之等值的主析取范式和主合取范式式和主合取范式, 并且是唯一的并且是唯一的. . 用等值演算法求公式的主范式的步驟：用等值演算法求公式的主范式的步驟： (1) 先求析取范式（合取范式）先求析取范式（合取范式） (2) 將不是極小項(xiàng)（極大項(xiàng)）的簡(jiǎn)單合取式（簡(jiǎn)將不是極小項(xiàng)（極大項(xiàng)）的簡(jiǎn)單合

18、取式（簡(jiǎn) 單析取式）化成與之等值的若干個(gè)極小項(xiàng)的析單析取式）化成與之等值的若干個(gè)極小項(xiàng)的析 ?。O大項(xiàng)的合?。?，需要利用同一律（零取（極大項(xiàng)的合?。?，需要利用同一律（零 律）、排中律（矛盾律）、分配律、冪等律等律）、排中律（矛盾律）、分配律、冪等律等. (3) 極小項(xiàng)（極大項(xiàng)）用名稱極小項(xiàng)（極大項(xiàng)）用名稱mi（Mi）表示，并）表示，并按角標(biāo)從小到大順序排序按角標(biāo)從小到大順序排序. 24求公式的主范式求公式的主范式例例 求公式求公式 A=(pq)r的主析取范式與主合的主析取范式與主合 取范式取范式. . (1) 求主析取范式求主析取范式 (pq)r (p q) r , （析取范式）（析取范式）

19、(p q) (p q) ( r r) (p qr) (p q r) m6 m7 , 25求公式的主范式求公式的主范式( (續(xù)續(xù)) ) r ( p p) ( q q) r ( pq r) ( p q r) (pq r) (p q r) m1 m3 m5 m7 , 代入并排序，得代入并排序，得 (pq)r m1 m3 m5 m6 m7（主析取范式）主析取范式） 26求公式的主范式求公式的主范式( (續(xù)續(xù)) ) (2) 求求A的主合取范式的主合取范式 (pq)r (p r) (q r) , （合取范式）（合取范式） p r p (qq) r (p q r) (pq r) M0 M2, 27求公式的主

20、范式求公式的主范式( (續(xù)續(xù)) ) q r (pp) q r (p q r) ( p q r) M0 M4 , 代入并排序，得代入并排序，得 (pq)r M0 M2 M4 （主合取范式）（主合取范式） 28主范式的用途主范式的用途與真值表相同與真值表相同 (1) 求公式的成真賦值和成假賦值求公式的成真賦值和成假賦值 例如例如 (pq)r m1 m3 m5 m6 m7， 其成真賦值為其成真賦值為001, 011, 101, 110, 111， 其余的賦值其余的賦值 000, 010, 100為為成假賦值成假賦值. 類似地，由主合取范式也可立即求出成類似地，由主合取范式也可立即求出成 假賦值和成真

21、賦值假賦值和成真賦值. 29主范式的用途主范式的用途( (續(xù)續(xù)) ) (2) 判斷公式的類型判斷公式的類型 設(shè)設(shè)A含含n個(gè)命題變項(xiàng)，則個(gè)命題變項(xiàng)，則 A為重言式為重言式A的主析取范式含的主析取范式含2n個(gè)極小項(xiàng)個(gè)極小項(xiàng) A的主合取范式為的主合取范式為1.A為矛盾式為矛盾式 A的主析取范式為的主析取范式為0 A的主合取范式含的主合取范式含2n個(gè)極大項(xiàng)個(gè)極大項(xiàng)A為非重言式的可滿足式為非重言式的可滿足式A的主析取范式中至少含一個(gè)且不含全部極小項(xiàng)的主析取范式中至少含一個(gè)且不含全部極小項(xiàng)A的主合取范式中至少含一個(gè)且不含全部極大項(xiàng)的主合取范式中至少含一個(gè)且不含全部極大項(xiàng) 30主范式的用途主范式的用途( (

22、續(xù)續(xù)) )例例 用主析取范式判斷下述兩個(gè)公式是否等值：用主析取范式判斷下述兩個(gè)公式是否等值： p(qr) 與與 (p q)r p(qr) 與與 (pq)r解解 p(qr) = m0 m1 m2 m3 m4 m5 m7 (p q)r = m0 m1 m2 m3 m4 m5 m7 (pq)r = m1 m3 m4 m5 m7故中的兩公式等值，而的不等值故中的兩公式等值，而的不等值. (3) 判斷兩個(gè)公式是否等值判斷兩個(gè)公式是否等值說(shuō)明：說(shuō)明： 由公式由公式A的主析取范式確定它的主合取范式，反之亦然的主析取范式確定它的主合取范式，反之亦然. 用公式用公式A的真值表求的真值表求A的主范式的主范式.31

23、主范式的用途主范式的用途( (續(xù)續(xù)) )例例 某公司要從趙、錢、孫、李、周五名新畢業(yè)某公司要從趙、錢、孫、李、周五名新畢業(yè)的大學(xué)生中選派一些人出國(guó)學(xué)習(xí)的大學(xué)生中選派一些人出國(guó)學(xué)習(xí). 選派必須滿足選派必須滿足以下條件：以下條件： (1)(1)若趙去，錢也去；若趙去，錢也去； (2)(2)李、周兩人中至少有一人去；李、周兩人中至少有一人去； (3)(3)錢、孫兩人中有一人去且僅去一人；錢、孫兩人中有一人去且僅去一人； (4)(4)孫、李兩人同去或同不去；孫、李兩人同去或同不去； (5)(5)若周去，則趙、錢也去若周去，則趙、錢也去. 試用主析取范式法分析該公司如何選派他們出國(guó)？試用主析取范式法分析該公司如何選派他們出國(guó)？32例例 (續(xù)續(xù))解此類問(wèn)題的步驟為：解此類問(wèn)題的步驟為： 將簡(jiǎn)