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

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

2、r) (p?q) ?r,3,基本等值式,雙重否定律 : ??A?A等冪律： A?A?A, A?A?A交換律: A?B?B?A, A?B?B?A結(jié)合律: (A?B)?C?A?(B?C) (A?B)?C?A?(B?C)分配律: A?(B?C)?(A?B)?(A?C)

3、 A?(B?C)? (A?B)?(A?C),4,基本等值式(續(xù)),德·摩根律: ?(A?B)??A??B ?(A?B)??A??B吸收律: A?(A?B)?A, A?(A?B)?A零律: A?1?1, A?0?0 同一律: A?0?A, A?1?A排中律:

4、 A??A?1矛盾律: A??A?0,5,基本等值式(續(xù)),蘊涵等值式: A?B??A?B等價等值式: A?B?(A?B)?(B?A)假言易位: A?B??B??A等價否定等值式: A?B??A??B歸謬論: (A?B)?(A??B) ??A注意:A,B,C代表任意的命題公式牢記這些等值式是繼續(xù)學習的基礎(chǔ),6,

5、等值演算與置換規(guī)則,等值演算: 由已知的等值式推演出新的等值式的過程置換規(guī)則：若A?B, 則?(B)??(A) 等值演算的基礎(chǔ)： (1) 等值關(guān)系的性質(zhì)：自反、對稱、傳遞 (2) 基本的等值式 (3) 置換規(guī)則,7,應用舉例——證明兩個公式等值,例1 證明 p?(q?r) ? (p?q)?r證 p?(q?r) ??p?(?q?r) （蘊涵等值式，置換規(guī)則） ?(?p??q)

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

7、,證明兩個公式不等值的基本思想是找到一個賦值使一個成真,另一個成假. 方法一 真值表法（自己證） 方法二 觀察賦值法. 容易看出000, 010等是左邊的的成真賦值，是右邊的成假賦值. 方法三 用等值演算先化簡兩個公式，再觀察.,9,應用舉例——判斷公式類型,例3 用等值演算法判斷下列公式的類型(1) q??(p?q) 解 q??(p?q) ? q??(?p?q) （蘊涵等值式）

8、 ? q?(p??q) （德?摩根律） ? p?(q??q) （交換律，結(jié)合律） ? p?0 （矛盾律） ? 0 （零律）由最后一步可知，該式為矛盾式.,10,例3 (續(xù)),(2) (p?q)?(?q??p) 解 (p?q)?(?q??p) ? (?p?q)?(q??p) （蘊涵等值式

9、） ? (?p?q)?(?p?q) （交換律） ? 1由最后一步可知，該式為重言式.問：最后一步為什么等值于1？,11,例3 (續(xù)),(3) ((p?q)?(p??q))?r) 解 ((p?q)?(p??q))?r) ? (p?(q??q))?r （分配律） ? p?1?r （排中律） ? p?r

10、 （同一律）這不是矛盾式，也不是重言式，而是非重言式的可滿足式.如101是它的成真賦值,000是它的成假賦值.,總結(jié)：A為矛盾式當且僅當A?0 A為重言式當且僅當A?1說明：演算步驟不惟一,應盡量使演算短些,作業(yè),1.8,1.9,12,13,1.4 范式,析取范式與合取范式 主析取范式與主合取范式,14,析取范式與合取范式,文字:命題變項及其否定的總稱簡單析取式:有限個文字構(gòu)成的析取式

11、如 p, ?q, p??q, p?q?r, …簡單合取式:有限個文字構(gòu)成的合取式如 p, ?q, p??q, p?q?r, …析取范式:由有限個簡單合取式組成的析取式 A1?A2???Ar, 其中A1,A2,?,Ar是簡單合取式合取范式:由有限個簡單析取式組成的合取式 A1?A2???Ar , 其中A1,A2,?,Ar是簡單析取式,15,析取范式與合取范式(續(xù)),范式:析取范式與合取范式的總稱 公式A的析

12、取范式: 與A等值的析取范式公式A的合取范式: 與A等值的合取范式說明： 單個文字既是簡單析取式，又是簡單合取式p??q?r, ?p?q??r既是析取范式，又是合取范式(為什么?),16,命題公式的范式,定理 任何命題公式都存在著與之等值的析取范式與合取范式.求公式A的范式的步驟： (1) 消去A中的?, ?（若存在） (2) 否定聯(lián)結(jié)詞?的內(nèi)移或消去 (3) 使用分配律

13、 ?對?分配（析取范式） ?對?分配（合取范式）公式的范式存在，但不惟一,17,求公式的范式舉例,例 求下列公式的析取范式與合取范式(1) A=(p??q)??r解 (p??q)??r ? (?p??q)??r （消去?） ? ?p??q??r （結(jié)合律）這既是A的析取范式（由3個簡單合取式組成的析取式），又是A的合取范式（由一個簡單析取式組成的合取式）,18,

14、求公式的范式舉例(續(xù)),(2) B=(p??q)?r解 (p??q)?r ? (?p??q)?r （消去第一個?） ? ?(?p??q)?r （消去第二個?） ? (p?q)?r （否定號內(nèi)移——德?摩根律）這一步已為析取范式（兩個簡單合取式構(gòu)成）繼續(xù)： (p?q)?r ? (p?r)?(q?r) （?對?分配律）這一步得到合取范式

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

16、大項，其中i是該極大項成 假賦值的十進制表示, mi(Mi)稱為極小項(極大項)的名稱. mi與Mi的關(guān)系: ?mi ? Mi , ?Mi ? mi,20,極小項與極大項(續(xù)),由p, q兩個命題變項形成的極小項與極大項,21,,由p, q, r三個命題變項形成的極小項與極大項,22,主析取范式與主合取范式,主析取范式: 由極小項構(gòu)成的析取范式主合取范式: 由極大項構(gòu)成的合取范式例如，n=3, 命題變項為p, q

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

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

19、 (p??q)?r ? (p?q)?r , （析取范式） ① (p?q) ? (p?q)?(?r?r) ? (p?q??r)?(p?q?r) ? m6?m7 , ②,25,求公式的主范式(續(xù)),r ?(?p?p)?(?q?q)?r ?(?p??q?r)?(?p?q?r)?(p??q?r)?(p?

20、q?r) ? m1?m3?m5?m7 ③ ②, ③代入①并排序，得 (p??q)?r ? m1?m3?m5? m6?m7（主析取范式）,26,求公式的主范式(續(xù)),(2) 求A的主合取范式 (p??q)?r ? (p?r)?(q?r) , （合取范式） ① p?r ?

21、p?(q??q)?r ? (p?q?r)?(p??q?r) ? M0?M2, ②,27,求公式的主范式(續(xù)),q?r ? (p??p)?q?r ? (p?q?r)?(?p?q?r) ? M0?M4

22、 ③ ②, ③代入①并排序，得 (p??q)?r ? M0?M2?M4 （主合取范式）,28,主范式的用途——與真值表相同,(1) 求公式的成真賦值和成假賦值 例如 (p??q)?r ? m1?m3?m5? m6?m7， 其成真賦值為001, 011, 101, 110, 111， 其余的賦值 000, 010, 100為成假賦值. 類似地，由

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

24、一個且不含全部極大項,30,主范式的用途(續(xù)),例 用主析取范式判斷下述兩個公式是否等值： ⑴ p?(q?r) 與 (p?q)?r ⑵ p?(q?r) 與 (p?q)?r解 p?(q?r) = m0?m1?m2?m3? m4?m5? m7 (p?q)?r = m0?m1?m2?m3? m4?m5? m7 (p?q)?r = m1?m3? m4?m5? m7故⑴中的兩公式等值，而⑵

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

26、周去，則趙、錢也去. 試用主析取范式法分析該公司如何選派他們出國？,32,例 (續(xù)),解此類問題的步驟為：① 將簡單命題符號化② 寫出各復合命題③ 寫出由②中復合命題組成的合取式 ④ 求③中所得公式的主析取范式,33,例 (續(xù)),解 ① 設(shè)p：派趙去，q：派錢去，r：派孫去， s：派李去，u：派周去. ② (1) (p?q) (2) (s?u) (3) ((q??r)?(?q?r)

27、) (4) ((r?s)?(?r??s)) (5) (u?(p?q)) ③ (1) ~ (5)構(gòu)成的合取式為 A=(p?q)?(s?u)?((q??r)?(?q?r))? ((r?s)?(?r??s))?(u?(p?q)),34,例 (續(xù)),④ A ? (?p??q?r?s??u)?(p?q??r??s?u)結(jié)論：由④可知，A的成真賦值為00110與110

28、01，因而派孫、李去（趙、錢、周不去）或派趙、錢、周去（孫、李不去）. A的演算過程如下: A ? (?p?q)?((q??r)?(?q?r))?(s?u)?(?u?(p?q))? ((r?s)?(?r??s)) （交換律)B1= (?p?q)?((q??r)?(?q?r)) ? ((?p?q??r)?(?p??q?r)?(q??r)) （分配律）,35

29、,例 (續(xù)),B2= (s?u)?(?u?(p?q)) ? ((s??u)?(p?q?s)?(p?q?u)) （分配律） B1?B2 ? (?p?q??r?s??u)?(?p??q?r?s??u) ?(q??r?s??u)?(p?q??r?s)?(p?q??r?u)再令 B3 = ((r?s)?(?r??s))得 A ? B1?B2?B3 ? (?p?

30、?q?r?s??u)?(p?q??r??s?u)注意：在以上演算中多次用矛盾律要求：自己演算一遍,作業(yè),1.12P，Q，R，S四個字母，從中取兩個字母，但要滿足下述三個條件，問有幾種取法，如何取？如果取P，則R和S要取一個Q，R不能同時取取R則不能取S,36,可選習題,張先生手中有代號為A、B、C、D、E的五種股票，根據(jù)當前股市情況及張先生本人的經(jīng)濟需求，需要有若干個股票拋出，但又必須滿足如下復雜的要求：（1）若A拋出，則