離散數(shù)學第三節(jié)

1、11.3 命題邏輯等值演算命題邏輯等值演算 等值式等值式基本等值式基本等值式等值演算等值演算置換規(guī)則置換規(guī)則2等值式等值式 定義定義 若等價式若等價式AB是重言式，則稱是重言式，則稱A與與B等值等值，記作記作AB，并稱，并稱AB是是等值式等值式說明：定義中，說明：定義中，A,B,均為元語言符號均為元語言符號, A或或B中中可能有啞元出現(xiàn)可能有啞元出現(xiàn).例如，在例如，在 (pq) ( p q) ( r r)中，中，r為左邊為左邊公式的啞元公式的啞元. 用真值表可驗證兩個公式是否等值用真值表可驗證兩個公式是否等值請驗證：請驗證：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ù)) )蘊涵等值式蘊涵等值式:

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

4、值式 (3) 置換規(guī)則置換規(guī)則 7應用舉例應用舉例證明兩個公式等值證明兩個公式等值 例例1 證明證明 p(qr) (p q)r證證 p(qr) p ( q r) （蘊涵等值式，置換規(guī)則）（蘊涵等值式，置換規(guī)則） ( pq) r （結(jié)合律，置換規(guī)則）（結(jié)合律，置換規(guī)則） (p q) r （德（德 摩根律，置換規(guī)則）摩根律，置換規(guī)則） (p q) r （蘊涵等值式，置換規(guī)則）（蘊涵等值式，置換規(guī)則） 說明說明: :也可以從右邊開始演算（請做一遍）也可以從右邊開始演算（請做一遍） 因為每一步都用置換規(guī)則，故可不寫出因為每一步都用置換規(guī)則，故可不寫出 熟練后，基本等值式也可以不寫出熟練后，基本等值式也

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

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

7、式由最后一步可知，該式為重言式.問：最后一步為什么等值于問：最后一步為什么等值于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為矛盾式當且僅當為矛盾式當且僅當A0 A為重言式當且僅當為重言式當且僅當A1說明：演算步驟不惟一說明：演算步驟不惟一,

8、,應盡量使演算短些應盡量使演算短些作業(yè)n1.8,1.912131.4 范式范式 析取范式與合取范式析取范式與合取范式 主析取范式與主合取范式主析取范式與主合取范式 14析取范式與合取范式析取范式與合取范式 文字文字: :命題變項及其否定的總稱命題變項及其否定的總稱簡單析取式簡單析取式: :有限個文字構(gòu)成的析取式有限個文字構(gòu)成的析取式如如 p, q, pq, p q r, 簡單合取式簡單合取式: :有限個文字構(gòu)成的合取式有限個文字構(gòu)成的合取式如如 p, q, pq, p q r, 析取范式析取范式: :由有限個簡單合取式組成的析取式由有限個簡單合取式組成的析取式 A1 A2Ar, 其中其中A1,

9、A2,Ar是是簡單合取式簡單合取式合取范式合取范式: :由有限個簡單析取式組成的合取式由有限個簡單析取式組成的合取式 A1 A2Ar , 其中其中A1,A2,Ar是是簡單析取式簡單析取式15析取范式與合取范式析取范式與合取范式( (續(xù)續(xù)) )范式范式: :析取范式與合取范式的總稱析取范式與合取范式的總稱 公式公式A的析取范式的析取范式: 與與A等值的析取范式等值的析取范式公式公式A的合取范式的合取范式: 與與A等值的合取范式等值的合取范式說明：說明： 單個文字既是簡單析取式，又是簡單合取式單個文字既是簡單析取式，又是簡單合取式pq r, p qr既是析取范式，又是合取范式既是析取范式，又是合取

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

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

12、繼續(xù)： (p q) r (p r) (q r) （ 對對 分配律）分配律）這一步得到合取范式（由兩個簡單析取式構(gòu)成）這一步得到合取范式（由兩個簡單析取式構(gòu)成） 19極小項與極大項極小項與極大項 定義定義 在含有在含有n個命題變項的簡單合取式個命題變項的簡單合取式( (簡單析取式簡單析取式) )中，中，若每個命題變項均以文字的形式出現(xiàn)且僅出現(xiàn)一次，稱這若每個命題變項均以文字的形式出現(xiàn)且僅出現(xiàn)一次，稱這樣的簡單合取式樣的簡單合取式( (簡單析取式簡單析取式) )為為極小項極小項( (極大項）極大項）.說明：說明：n n個命題變項產(chǎn)生個命題變項產(chǎn)生2n個極小項和個極小項和2n個極大項個極大項n 2n

13、個極小項（極大項）均互不等值個極小項（極大項）均互不等值n 在極小項和極大項中文字均按下標或字母順序排列在極小項和極大項中文字均按下標或字母順序排列n 用用mi表示第表示第i個極小項，其中個極小項，其中i是該極小項成真賦值的十是該極小項成真賦值的十 進制表示進制表示. 用用Mi表示第表示第i個極大項，其中個極大項，其中i是該極大項成是該極大項成 假賦值的十進制表示假賦值的十進制表示, mi( (Mi) )稱為極小項稱為極小項( (極大項極大項) )的名稱的名稱. n mi與與Mi的關(guān)系的關(guān)系: : mi Mi , Mi mi 20極小項與極大項極小項與極大項( (續(xù)續(xù)) )由由p, q兩個命題

14、變項形成的極小項與極大項兩個命題變項形成的極小項與極大項 公式公式 成真賦值成真賦值名稱名稱 公式公式 成假賦值成假賦值名稱名稱 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 極小項極小項 極大項極大項 21 由由p, q, r三個命題變項形成的極小項與極大項三個命題變項形成的極小項與極大項 極小項極小項 極大項極大項 公式公式 成真成真賦值賦值名稱名稱 公式公式 成假成假賦值賦值名稱名稱 p q r p q r p q r p q rp q rp q rp q rp q r0

15、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 22主析取范式與主合取范式主析取范式與主合取范式 主析取范式主析取范式: : 由極小項構(gòu)成的析取范式由極小項構(gòu)成的析取范式主合取范式主合取范式: : 由極大項構(gòu)成的合取范式由極大項構(gòu)成的合取范式例如，例如，n=3, 命題變項為命題變項為p, q, r時，時， ( pq r) ( p

16、 q r) m1 m3 是是主析取范式主析取范式 (p qr) ( p qr) M1 M5 是是主合取范式主合取范式 A的主析取范式的主析取范式: 與與A等值的主析取范式等值的主析取范式 A的主合取范式的主合取范式: : 與與A等值的主合取范式等值的主合取范式. 23主析取范式與主合取范式主析取范式與主合取范式( (續(xù)續(xù)) )定理定理 任何命題公式都存在著與之等值的主析取范任何命題公式都存在著與之等值的主析取范式和主合取范式式和主合取范式, 并且是唯一的并且是唯一的. . 用等值演算法求公式的主范式的步驟：用等值演算法求公式的主范式的步驟： (1) 先求析取范式（合取范式）先求析取范式（合取范

17、式） (2) 將不是極小項（極大項）的簡單合取式（簡將不是極小項（極大項）的簡單合取式（簡 單析取式）化成與之等值的若干個極小項的析單析取式）化成與之等值的若干個極小項的析 ?。O大項的合?。?，需要利用同一律（零?。O大項的合?。枰猛宦桑?律）、排中律（矛盾律）、分配律、冪等律等律）、排中律（矛盾律）、分配律、冪等律等. (3) 極小項（極大項）用名稱極小項（極大項）用名稱mi（Mi）表示，并）表示，并按角標從小到大順序排序按角標從小到大順序排序. 24求公式的主范式求公式的主范式例例 求公式求公式 A=(pq)r的主析取范式與主合的主析取范式與主合 取范式取范式. . (1) 求

18、主析取范式求主析取范式 (pq)r (p q) r , （析取范式）（析取范式） (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

19、 r p (qq) r (p q r) (pq r) M0 M2, 27求公式的主范式求公式的主范式( (續(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為為成假賦值成假賦值.

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

21、極大項的主合取范式中至少含一個且不含全部極大項 30主范式的用途主范式的用途( (續(xù)續(xù)) )例例 用主析取范式判斷下述兩個公式是否等值：用主析取范式判斷下述兩個公式是否等值： 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) 判斷兩個公式是否等值判斷兩個公式是否等值說明：說明： 由公式由公式A的主析取范式確定它的主合取范式，反之亦然的主析取范式確定它的

22、主合取范式，反之亦然. 用公式用公式A的真值表求的真值表求A的主范式的主范式.31主范式的用途主范式的用途( (續(xù)續(xù)) )例例 某公司要從趙、錢、孫、李、周五名新畢業(yè)某公司要從趙、錢、孫、李、周五名新畢業(yè)的大學生中選派一些人出國學習的大學生中選派一些人出國學習. 選派必須滿足選派必須滿足以下條件：以下條件： (1)(1)若趙去，錢也去；若趙去，錢也去； (2)(2)李、周兩人中至少有一人去；李、周兩人中至少有一人去； (3)(3)錢、孫兩人中有一人去且僅去一人；錢、孫兩人中有一人去且僅去一人； (4)(4)孫、李兩人同去或同不去；孫、李兩人同去或同不去； (5)(5)若周去，則趙、錢也去若周去

23、，則趙、錢也去. 試用主析取范式法分析該公司如何選派他們出國？試用主析取范式法分析該公司如何選派他們出國？32例例 (續(xù)續(xù))解此類問題的步驟為：解此類問題的步驟為： 將簡單命題符號化將簡單命題符號化 寫出各復合命題寫出各復合命題 寫出由中復合命題組成的合取式寫出由中復合命題組成的合取式 求求中所得公式的主析取范式中所得公式的主析取范式 33例例 (續(xù)續(xù))解解 設(shè)設(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)成的合取式為構(gòu)成的合取式為 A=(pq) (s u) (qr) ( q r) (r s) ( rs) (u(p q)34例例 (續(xù)續(xù)