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

1、1等值式 定義定義 若等價(jià)式若等價(jià)式AB是重言式，則稱是重言式，則稱A與與B等值等值，記作記作AB，并稱，并稱AB是是等值式等值式說明：定義中，說明：定義中，A,B,均為元語言符號(hào)均為元語言符號(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 第1頁/共35頁2基本等值式 雙重否定律 : AA等冪律： A AA, A AA交換律: A BB A, A BB A結(jié)合律: (

2、A B) CA (B C) (A B) CA (B C)分配律: A (B C)(A B) (A C) A (B C) (A B) (A C)第2頁/共35頁3基本等值式( (續(xù)) )德摩根律: (A B)AB (A B)AB吸收律: A (A B)A, A (A B)A零律: A 11, A 00 同一律: A 0A, A 1A排中律: AA1矛盾律: AA0第3頁/共35頁4基本等值式( (續(xù)) )蘊(yùn)涵等值式: ABA B等價(jià)等值式: AB(AB) (BA)假言易位: ABBA等價(jià)否定等值式: ABAB歸謬論: (AB) (AB) A注意:A,B,C代表任意的命題公式牢記這些等值式是繼續(xù)學(xué)

3、習(xí)的基礎(chǔ)第4頁/共35頁5等值演算與置換規(guī)則 等值演算: 由已知的等值式推演出新的等值式的過程置換規(guī)則：若AB, 則 (B) (A) 等值演算的基礎(chǔ)： (1) 等值關(guān)系的性質(zhì)：自反、對(duì)稱、傳遞 (2) 基本的等值式 (3) 置換規(guī)則 第5頁/共35頁6應(yīng)用舉例證明兩個(gè)公式等值 例1 證明 p(qr) (p q)r證 p(qr) p ( q r) （蘊(yùn)涵等值式，置換規(guī)則） ( pq) r （結(jié)合律，置換規(guī)則） (p q) r （德 摩根律，置換規(guī)則） (p q) r （蘊(yùn)涵等值式，置換規(guī)則） 說明說明: :也可以從右邊開始演算（請(qǐng)做一遍）也可以從右邊開始演算（請(qǐng)做一遍） 因?yàn)槊恳徊蕉加弥脫Q規(guī)則，

4、故可不寫出因?yàn)槊恳徊蕉加弥脫Q規(guī)則，故可不寫出 熟練后，基本等值式也可以不寫出熟練后，基本等值式也可以不寫出 第6頁/共35頁7應(yīng)用舉例證明兩個(gè)公式不等值例例2 證明證明: p(qr) (pq) r 用等值演算不能直接證明兩個(gè)公式不等值用等值演算不能直接證明兩個(gè)公式不等值,證明兩證明兩個(gè)公式不等值的基本思想是找到一個(gè)賦值使一個(gè)成個(gè)公式不等值的基本思想是找到一個(gè)賦值使一個(gè)成真真,另一個(gè)成假另一個(gè)成假. 方法一方法一 真值表法（自己證）真值表法（自己證） 方法二方法二 觀察賦值法觀察賦值法. 容易看出容易看出000, 010等是左邊的等是左邊的的成真賦值，是右邊的成假賦值的成真賦值，是右邊的成假賦值

5、. 方法三方法三 用等值演算先化簡兩個(gè)公式，再觀察用等值演算先化簡兩個(gè)公式，再觀察.第7頁/共35頁8應(yīng)用舉例判斷公式類型 例3 用等值演算法判斷下列公式的類型(1) q(pq) 解 q(pq) q( p q) （蘊(yùn)涵等值式） q (pq) （德 摩根律） p (qq) （交換律，結(jié)合律） p 0 （矛盾律） 0 （零律）由最后一步可知，該式為矛盾式. 第8頁/共35頁9例3 (續(xù))(2) (pq)( qp) 解 (pq)( qp) ( p q)(qp) （蘊(yùn)涵等值式） ( p q)( p q) （交換律） 1由最后一步可知，該式為重言式.問：最后一步為什么等值于1？ 第9頁/共35頁10例3

6、 (續(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)盡量使演算短些第10頁/共35頁111.4 范式 析取范式與合取范式 主析取范式與主合取范式 第11頁/共35頁12析取范式與合取范式 文字: :命題變項(xiàng)及其否定的總稱簡單析取式: :有限個(gè)

7、文字構(gòu)成的析取式如 p, q, pq, p q r, 簡單合取式: :有限個(gè)文字構(gòu)成的合取式如 p, q, pq, p q r, 析取范式: :由有限個(gè)簡單合取式組成的析取式 A1 A2Ar, 其中A1,A2,Ar是簡單合取式合取范式: :由有限個(gè)簡單析取式組成的合取式 A1 A2Ar , 其中A1,A2,Ar是簡單析取式第12頁/共35頁13析取范式與合取范式( (續(xù)) )范式: :析取范式與合取范式的總稱 公式A的析取范式: 與A等值的析取范式公式A的合取范式: 與A等值的合取范式說明： 單個(gè)文字既是簡單析取式，又是簡單合取式pq r, p qr既是析取范式，又是合取范式(為什么?) 第1

8、3頁/共35頁14命題公式的范式 定理 任何命題公式都存在著與之等值的析取范式與合取范式. .求公式A的范式的步驟： (1) 消去A中的, （若存在） (2) 否定聯(lián)結(jié)詞 的內(nèi)移或消去 (3) 使用分配律 對(duì) 分配（析取范式） 對(duì) 分配（合取范式）公式的范式存在，但不惟一第14頁/共35頁15求公式的范式舉例 例 求下列公式的析取范式與合取范式(1) A=(pq)r解 (pq)r ( pq)r （消去） pqr （結(jié)合律）這既是A的析取范式（由3個(gè)簡單合取式組成的析取式），又是A的合取范式（由一個(gè)簡單析取式組成的合取式）第15頁/共35頁16求公式的范式舉例( (續(xù)) )(2) B=(pq)r

9、解 (pq)r ( pq)r （消去第一個(gè)） ( pq) r （消去第二個(gè)） (p q) r （否定號(hào)內(nèi)移德 摩根律）這一步已為析取范式（兩個(gè)簡單合取式構(gòu)成）繼續(xù)： (p q) r (p r) (q r) （ 對(duì) 分配律）這一步得到合取范式（由兩個(gè)簡單析取式構(gòu)成） 第16頁/共35頁172元真值函數(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

10、 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(14)2(13)2(12)2(11)2(10)2(9)2(8FFFFFFFF第17頁/共35頁18極小項(xiàng)與極大項(xiàng) 定義 在含有n個(gè)命題變項(xiàng)的簡單合取式( (簡單析取式) )中，若每個(gè)命題變項(xiàng)均以文字的形式出現(xiàn)且僅出現(xiàn)一次，稱這樣的簡單合取式( (簡單析取式) )為極小項(xiàng)( (極大項(xiàng)）.說明： n個(gè)命題變項(xiàng)產(chǎn)生2n個(gè)極小項(xiàng)和2n個(gè)極大項(xiàng) 2n個(gè)極小項(xiàng)（極大項(xiàng)）均互不等值 在極小項(xiàng)和極大項(xiàng)中文字均按下標(biāo)或字母順序排列 用mi表示第i個(gè)極小項(xiàng)，其中i是

11、該極小項(xiàng)成真賦值的十 進(jìn)制表示. 用Mi表示第i個(gè)極大項(xiàng)，其中i是該極大項(xiàng)成 假賦值的十進(jìn)制表示, mi( (Mi) )稱為極小項(xiàng)( (極大項(xiàng)) )的名稱. mi與Mi的關(guān)系: : mi Mi , Mi mi 第18頁/共35頁19極小項(xiàng)與極大項(xiàng)( (續(xù)) )由p, q兩個(gè)命題變項(xiàng)形成的極小項(xiàng)與極大項(xiàng) 公式公式 成真賦值成真賦值名稱名稱 公式公式 成假賦值成假賦值名稱名稱 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) 第19頁/共35頁20 由p, q

12、, r三個(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 1m0m1m2m3m4m5m6m7p 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 第20頁/共35頁21主析取范式與主合取范式 主析取

13、范式: : 由極小項(xiàng)構(gòu)成的析取范式主合取范式: : 由極大項(xiàng)構(gòu)成的合取范式例如，n=3, 命題變項(xiàng)為p, q, r時(shí)， ( pq r) ( p q r) m1 m3 是主析取范式 (p qr) ( p qr) M1 M5 是主合取范式 A的主析取范式: 與A等值的主析取范式 A的主合取范式: : 與A等值的主合取范式. 第21頁/共35頁22主析取范式與主合取范式( (續(xù)) )定理 任何命題公式都存在著與之等值的主析取范式和主合取范式, 并且是唯一的. . 用等值演算法求公式的主范式的步驟： (1) 先求析取范式（合取范式） (2) 將不是極小項(xiàng)（極大項(xiàng)）的簡單合取式（簡 單析取式）化成與之等

14、值的若干個(gè)極小項(xiàng)的析 ?。O大項(xiàng)的合?。?，需要利用同一律（零 律）、排中律（矛盾律）、分配律、冪等律等. (3) 極小項(xiàng)（極大項(xiàng)）用名稱mi（Mi）表示，并按角標(biāo)從小到大順序排序. 第22頁/共35頁23求公式的主范式例 求公式 A=(pq)r的主析取范式與主合 取范式. . (1) 求主析取范式 (pq)r (p q) r , （析取范式） (p q) (p q) ( r r) (p qr) (p q r) m6 m7 , 第23頁/共35頁24求公式的主范式( (續(xù)) ) r ( p p) ( q q) r ( pq r) ( p q r) (pq r) (p q r) m1 m3 m5

15、m7 , 代入并排序，得 (pq)r m1 m3 m5 m6 m7（主析取范式） 第24頁/共35頁25求公式的主范式( (續(xù)) ) (2) 求A的主合取范式 (pq)r (p r) (q r) , （合取范式） p r p (qq) r (p q r) (pq r) M0 M2, 第25頁/共35頁26求公式的主范式( (續(xù)) ) q r (pp) q r (p q r) ( p q r) M0 M4 , 代入并排序，得 (pq)r M0 M2 M4 （主合取范式） 第26頁/共35頁27主范式的用途與真值表相同 (1) 求公式的成真賦值和成假賦值 例如 (pq)r m1 m3 m5 m6

16、m7， 其成真賦值為001, 011, 101, 110, 111， 其余的賦值 000, 010, 100為成假賦值. 類似地，由主合取范式也可立即求出成 假賦值和成真賦值. 第27頁/共35頁28主范式的用途( (續(xù)) ) (2) 判斷公式的類型 設(shè)A含n個(gè)命題變項(xiàng)，則 A為重言式A的主析取范式含2n個(gè)極小項(xiàng) A的主合取范式為1.A為矛盾式 A的主析取范式為0 A的主合取范式含2n個(gè)極大項(xiàng)A為非重言式的可滿足式A的主析取范式中至少含一個(gè)且不含全部極小項(xiàng)A的主合取范式中至少含一個(gè)且不含全部極大項(xiàng) 第28頁/共35頁29主范式的用途( (續(xù)) )例 用主析取范式判斷下述兩個(gè)公式是否等值： p(

17、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è)公式是否等值說明：說明： 由公式由公式A的主析取范式確定它的主合取范式，反之亦然的主析取范式確定它的主合取范式，反之亦然. 用公式用公式A的真值表求的真值表求A的主范式的主范式.第29頁/共35頁30主范式的用途( (續(xù)) )例 某公司要從趙、錢、孫、李、周五名新畢業(yè)的大學(xué)生中選派一些人出國學(xué)習(xí). 選派必須滿足以

18、下條件： (1)(1)若趙去，錢也去； (2)(2)李、周兩人中至少有一人去； (3)(3)錢、孫兩人中有一人去且僅去一人； (4)(4)孫、李兩人同去或同不去； (5)(5)若周去，則趙、錢也去. 試用主析取范式法分析該公司如何選派他們出國？第30頁/共35頁31例 (續(xù))解此類問題的步驟為： 將簡單命題符號(hào)化 寫出各復(fù)合命題 寫出由中復(fù)合命題組成的合取式 求中所得公式的主析取范式 第31頁/共35頁32例 (續(xù))解 設(shè)p：派趙去，q：派錢去，r：派孫去， s：派李去，u：派周去. . (1) (pq) (2) (s u) (3) (qr) ( q r) (4) (r s) ( rs) (5) (u(p q) (1) (5)構(gòu)成的合取式為 A=(pq) (s u) (qr) ( q r) (r s) ( rs) (u(p q)第32頁/共35頁33例 (續(xù))A的演算過程如下: : A ( p q) (qr) ( q r) (s u) ( u (p q) (r s) ( rs) （交換律) )B1= ( p q) (qr) ( q r) ( p qr) ( pq r) (qr) （分配律）B2= (s