1、1,1.3 命題邏輯等值演算,等值式 基本等值式 等值演算 置換規(guī)則,2,等值式,定義 若等價式AB是重言式，則稱A與B等值， 記作AB，并稱AB是等值式 說明：定義中，A,B,均為元語言符號, A或B中 可能有啞元出現(xiàn). 例如，在 (pq) (pq) (rr)中，r為左邊 公式的啞元. 用真值表可驗證兩個公式是否等值 請驗證：p(qr) (pq) r p(qr) (pq) r,3,基本等值式,雙重否定律 : AA 等冪律： AAA, AAA 交換律: ABBA, ABBA 結合律: (AB)CA(BC) (AB)CA(BC) 分配律: A(BC)(AB)(AC) A(BC) (AB)(AC)

2、,4,基本等值式(續(xù)),德摩根律: (AB)AB (AB)AB 吸收律: A(AB)A, A(AB)A 零律: A11, A00 同一律: A0A, A1A 排中律: AA1 矛盾律: AA0,5,基本等值式(續(xù)),蘊涵等值式: ABAB 等價等值式: AB(AB)(BA) 假言易位: ABBA 等價否定等值式: ABAB 歸謬論: (AB)(AB) A 注意: A,B,C代表任意的命題公式 牢記這些等值式是繼續(xù)學習的基礎,6,等值演算與置換規(guī)則,等值演算: 由已知的等值式推演出新的等值式的過程 置換規(guī)則：若AB, 則(B)(A) 等值演算的基礎： (1) 等值關系的性質：自反、對稱、傳遞 (

3、2) 基本的等值式 (3) 置換規(guī)則,7,應用舉例證明兩個公式等值,例1 證明 p(qr) (pq)r 證 p(qr) p(qr) （蘊涵等值式，置換規(guī)則） (pq)r （結合律，置換規(guī)則） (pq)r （德摩根律，置換規(guī)則） (pq) r （蘊涵等值式，置換規(guī)則）,說明:也可以從右邊開始演算（請做一遍） 因為每一步都用置換規(guī)則，故可不寫出 熟練后，基本等值式也可以不寫出,8,應用舉例證明兩個公式不等值,例2 證明: p(qr) (pq) r 用等值演算不能直接證明兩個公式不等值,證明兩 個公式不等值的基本思想是找到一個賦值使一個成 真,另一個成假. 方法一 真值表法（自己證） 方法二 觀察賦

4、值法. 容易看出000, 010等是左邊的 的成真賦值，是右邊的成假賦值. 方法三 用等值演算先化簡兩個公式，再觀察.,9,應用舉例判斷公式類型,例3 用等值演算法判斷下列公式的類型 (1) q(pq) 解 q(pq) q(pq) （蘊涵等值式） q(pq) （德摩根律） p(qq) （交換律，結合律） p0 （矛盾律） 0 （零律） 由最后一步可知，該式為矛盾式.,10,例3 (續(xù)),(2) (pq)(qp) 解 (pq)(qp) (pq)(qp) （蘊涵等值式） (pq)(pq) （交換律） 1 由最后一步可知，該式為重言式. 問：最后一步為什么等值于1？,11,例3 (續(xù)),(3) (p

5、q)(pq)r) 解 (pq)(pq)r) (p(qq)r （分配律） p1r （排中律） pr （同一律） 這不是矛盾式，也不是重言式，而是非重言式的可 滿足式.如101是它的成真賦值,000是它的成假賦值.,總結：A為矛盾式當且僅當A0 A為重言式當且僅當A1 說明：演算步驟不惟一,應盡量使演算短些,12,1.4 范式,析取范式與合取范式 主析取范式與主合取范式,13,析取范式與合取范式,文字:命題變項及其否定的總稱 簡單析取式:有限個文字構成的析取式 如 p, q, pq, pqr, 簡單合取式:有限個文字構成的合取式 如 p, q, pq, pqr, 析取范式:由有限個簡單合取式組成的

6、析取式 A1A2Ar, 其中A1,A2,Ar是簡單合取式 合取范式:由有限個簡單析取式組成的合取式 A1A2Ar , 其中A1,A2,Ar是簡單析取式,14,析取范式與合取范式(續(xù)),范式:析取范式與合取范式的總稱 公式A的析取范式: 與A等值的析取范式 公式A的合取范式: 與A等值的合取范式 說明： 單個文字既是簡單析取式，又是簡單合取式 pqr, pqr既是析取范式，又是合取范式 (為什么?),15,命題公式的范式,定理 任何命題公式都存在著與之等值的析取范式 與合取范式. 求公式A的范式的步驟： (1) 消去A中的, （若存在） (2) 否定聯(lián)結詞的內移或消去 (3) 使用分配律 對分配

7、（析取范式） 對分配（合取范式） 公式的范式存在，但不惟一,16,求公式的范式舉例,例 求下列公式的析取范式與合取范式 (1) A=(pq)r 解 (pq)r (pq)r （消去） pqr （結合律） 這既是A的析取范式（由3個簡單合取式組成的析 取式），又是A的合取范式（由一個簡單析取式 組成的合取式）,17,求公式的范式舉例(續(xù)),(2) B=(pq)r 解 (pq)r (pq)r （消去第一個） (pq)r （消去第二個） (pq)r （否定號內移德摩根律） 這一步已為析取范式（兩個簡單合取式構成） 繼續(xù)： (pq)r (pr)(qr) （對分配律） 這一步得到合取范式（由兩個簡單析取式

8、構成）,18,極小項與極大項,定義 在含有n個命題變項的簡單合取式(簡單析取式)中， 若每個命題變項均以文字的形式出現(xiàn)且僅出現(xiàn)一次，稱這 樣的簡單合取式(簡單析取式)為極小項(極大項）. 說明： n個命題變項產生2n個極小項和2n個極大項 2n個極小項（極大項）均互不等值 在極小項和極大項中文字均按下標或字母順序排列 用mi表示第i個極小項，其中i是該極小項成真賦值的十 進制表示. 用Mi表示第i個極大項，其中i是該極大項成 假賦值的十進制表示, mi(Mi)稱為極小項(極大項)的名稱. mi與Mi的關系: mi Mi , Mi mi,19,極小項與極大項(續(xù)),由p, q兩個命題變項形成的極

9、小項與極大項,20,由p, q, r三個命題變項形成的極小項與極大項,21,主析取范式與主合取范式,主析取范式: 由極小項構成的析取范式 主合取范式: 由極大項構成的合取范式 例如，n=3, 命題變項為p, q, r時， (pqr)(pqr) m1m3 是主析取范式 (pqr)(pqr) M1M5 是主合取范式 A的主析取范式: 與A等值的主析取范式 A的主合取范式: 與A等值的主合取范式.,22,主析取范式與主合取范式(續(xù)),定理 任何命題公式都存在著與之等值的主析取范 式和主合取范式, 并且是唯一的. 用等值演算法求公式的主范式的步驟： (1) 先求析取范式（合取范式） (2) 將不是極小

10、項（極大項）的簡單合取式（簡 單析取式）化成與之等值的若干個極小項的析 取（極大項的合?。?，需要利用同一律（零 律）、排中律（矛盾律）、分配律、冪等律等. (3) 極小項（極大項）用名稱mi（Mi）表示，并 按角標從小到大順序排序.,23,求公式的主范式,例 求公式 A=(pq)r的主析取范式與主合 取范式. (1) 求主析取范式 (pq)r (pq)r , （析取范式） (pq) (pq)(rr) (pqr)(pqr) m6m7 , ,24,求公式的主范式(續(xù)),r (pp)(qq)r (pqr)(pqr)(pqr)(pqr) m1m3m5m7 , 代入并排序，得 (pq)r m1m3m5

11、m6m7（主析取范式）,25,求公式的主范式(續(xù)),(2) 求A的主合取范式 (pq)r (pr)(qr) , （合取范式） pr p(qq)r (pqr)(pqr) M0M2, ,26,求公式的主范式(續(xù)),qr (pp)qr (pqr)(pqr) M0M4 , 代入并排序，得 (pq)r M0M2M4 （主合取范式）,27,主范式的用途與真值表相同,(1) 求公式的成真賦值和成假賦值 例如 (pq)r m1m3m5 m6m7， 其成真賦值為001, 011, 101, 110, 111， 其余的賦值 000, 010, 100為成假賦值. 類似地，由主合取范式也可立即求出成 假賦值和成真賦

12、值.,28,主范式的用途(續(xù)),(2) 判斷公式的類型 設A含n個命題變項，則 A為重言式A的主析取范式含2n個極小項 A的主合取范式為1. A為矛盾式 A的主析取范式為0 A的主合取范式含2n個極大項 A為非重言式的可滿足式 A的主析取范式中至少含一個且不含全部極小項 A的主合取范式中至少含一個且不含全部極大項,29,主范式的用途(續(xù)),例 用主析取范式判斷下述兩個公式是否等值： p(qr) 與 (pq)r p(qr) 與 (pq)r 解 p(qr) = m0m1m2m3 m4m5 m7 (pq)r = m0m1m2m3 m4m5 m7 (pq)r = m1m3 m4m5 m7 故中的兩公式

13、等值，而的不等值.,(3) 判斷兩個公式是否等值,說明： 由公式A的主析取范式確定它的主合取范式，反之亦然. 用公式A的真值表求A的主范式.,30,主范式的用途(續(xù)),例 某公司要從趙、錢、孫、李、周五名新畢業(yè) 的大學生中選派一些人出國學習. 選派必須滿足 以下條件： (1)若趙去，錢也去； (2)李、周兩人中至少有一人去； (3)錢、孫兩人中有一人去且僅去一人； (4)孫、李兩人同去或同不去； (5)若周去，則趙、錢也去. 試用主析取范式法分析該公司如何選派他們出國？,31,例 (續(xù)),解此類問題的步驟為： 將簡單命題符號化 寫出各復合命題 寫出由中復合命題組成的合取式 求中所得公式的主析取范式,32,例 (續(xù)),解 設p：派趙去，q：派錢去，r：派孫去， s：派李去，u：派周去. (1) (pq) (2) (su) (3) (qr)(qr) (4) (rs)(rs) (5) (u(pq) (1) (5)構成的合取式為 A=(pq)(su)(qr)(qr) (rs)(rs)(u(pq),33,例 (續(xù)), A (pqrsu)(pqrsu) 結論：由可知，A的成真賦值為00110與11001， 因而派孫、李去（趙、錢、周不去）或派趙、錢、 周去（孫、李不去）. A的演算過程如下: A (pq)(qr)(q