ch命題邏輯等值演算實用PPT學習教案

1、會計學1ch命題邏輯等值演算實用命題邏輯等值演算實用2l值n請驗證：np(qr) (pq) r np(qr) 不與 (pq) r 等值第1頁/共62頁311111101 11111101 11011101 0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 (p q)rp(qr)qr p q rp q00000011 結(jié)論結(jié)論: : p(qr) (p q) r 第2頁/共62頁401011101 11111101 11011101 0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 (pq)rp(qr)qr p q rpq111100

2、11 結(jié)論結(jié)論: : p(qr) 與與 (pq) r 不等值不等值第3頁/共62頁5A(BC)(AB)(AC)n德摩根律(AB)ABn(AB)ABn吸收律A(AB)A, A(AB)A第4頁/共62頁6n假言易位ABBAn等價否定等值式ABABn歸謬論(AB)(AB) An特別提示：必須牢記這16組等值式，這是繼續(xù)學習的基礎第5頁/共62頁7式，(B) 是用公式 B 置換n(A) 中所有的 A 后得到的命題公式n若 BA，則 (B)(A)第6頁/共62頁8n (pq)r（蘊涵等值式，置換規(guī)則）n今后在注明中省去置換規(guī)則n注意：用等值演算不能直接證明兩個公式不等值第7頁/共62頁9npq r (p

3、q)r(pq)rn更容易看出前面的兩個賦值分別是左邊的成真賦n值和右邊的成假賦值第8頁/共62頁10解解 (1) q(pq) q( p q) （蘊涵等值式）（蘊涵等值式） q (pq) （德摩根律）（德摩根律） p (qq) （交換律，結(jié)合律）（交換律，結(jié)合律） p 0 （矛盾律）（矛盾律） 0 （零律）（零律）矛盾式矛盾式第9頁/共62頁11(3) (p q) (pq) r) (p (qq) r （分配律）（分配律） p 1 r （排中律）（排中律） p r （同一律）（同一律）可滿足式，可滿足式，101和和111是成真賦值，是成真賦值，000和和010等是成假賦值等是成假賦值. 第10頁/

4、共62頁12n(4) 單合取式組成的析取式np, pq, pq, (pq)(pqr)(qr)n(5) 合取范式由有限個簡單析取式組成的合取式np, pq, pq, (pq)p(pqr)n(6) 范式析取范式與合取范式的總稱第11頁/共62頁13第12頁/共62頁14n.n(2) 一個合取范式是重言式當且僅當它的每個簡單析取式都n是重言式.第13頁/共62頁15n (2) 否定聯(lián)結(jié)詞的內(nèi)移或消去n A An(AB)ABn(AB)AB第14頁/共62頁16第15頁/共62頁17n(由3簡單合取式組成的析取式)，又n是合取范式(由一個簡單析取式組成的合取式) 第16頁/共62頁18第17頁/共62頁

5、19ln個命題變項有2n個極小項和2n個極大項l2n個極小項（極大項）均互不等值l用mi表示第i個極小項，其中i是該極小項成真賦值的十進制表示. 用Mi表示第i個極大項，其中i是該極大項成假賦值的十進制表示. mi（Mi）稱為極小項（極大項）的名稱. 第18頁/共62頁20極小項極小項極大項極大項公式公式成真賦值成真賦值名稱名稱公式公式成假賦值成假賦值名稱名稱 pq p qpqp q 0 0 0 1 1 0 1 1 m0m1m2m3 p q pq p q pq 0 0 0 1 1 0 1 1M0M1M2M3第19頁/共62頁21極小項極小項極大項極大項公式公式成真賦值成真賦值名稱名稱公式公式成

6、假賦值成假賦值名稱名稱 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 1 m0m1m2m3m4m5m6m7 p q r p q r p q r p q r p q r p q r p q r p q r0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 M0M1M2M3M4M5M6M7由三個命題變項由三個命題變項 p, q, r 形成的極小項與極大項形成的極小項與極大項. mi與與Mi的關(guān)系：的關(guān)系： mi Mi, Mi mi 第20頁/共62頁2

7、2n公式A的主析取(合取)范式與A 等值的主析取(合取)范式n定理2.5 (主范式的存在惟一定理)n任何命題公式都存在與之等值的主析取范式和主合取范式,n并且是惟一的第21頁/共62頁23求公式主析取范式的步驟求公式主析取范式的步驟:設公式設公式A含命題變項含命題變項p1,p2,pn(1) 求求A的析取范式的析取范式A =B1 B2 Bs , 其中其中Bj是簡單合取是簡單合取 式式 j=1,2, ,s (2) 若某個若某個Bj既不含既不含pi, 又不含又不含 pi, 則將則將Bj展開成展開成 Bj Bj (pi pi) (Bj pi) (Bj pi) 重復這個過程重復這個過程, 直到所有簡單合

8、取式都是長度為直到所有簡單合取式都是長度為n的極的極 小項為止小項為止(3) 消去重復出現(xiàn)的極小項消去重復出現(xiàn)的極小項, 即用即用mi代替代替mi mi(4) 將極小項按下標從小到大排列將極小項按下標從小到大排列第22頁/共62頁24(Bjpi)(Bjpi)n重復這個過程, 直到所有簡單析取式都是長度為n的極n大項為止n(3) 消去重復出現(xiàn)的極大項, 即用Mi代替MiMin(4) 將極大項按下標從小到大排列第23頁/共62頁25n rn (pp)(qq)rn(pqr)(pqr)(pqr)(pqr)n m1m3m5m7 n, 代入并排序，得n(pq)r m1m3m5m6m7（主析取范式）第24頁

9、/共62頁26n (pqr)(pqr) n M0M4n, 代入 并排序，得n(pq)r M0M2M4（主合取范式）第25頁/共62頁27111，n成假賦值為 000, 010, 100. n類似地，由主合取范式也立即求出成假賦值和成真賦值. 第26頁/共62頁28n A為矛盾式 A的主合析取范式含全部2n個極大項nA的主析取范式不含任何極小項, 記為0.n A為非重言式的可滿足式nA的主析取范式中至少含一個、但不是全n部極小項nA的主合取范式中至少含一個、但不是全n部極大項.第27頁/共62頁29矛盾式n(2) B p(pq) 1 m0m1m2m3重言式n(3) C (pq)r (pq)r n

10、(pqr)(pqr)(pqr)n(pqr)(pqr)(pqr)nm0m1m3 m5m7非重言式的可滿足式第28頁/共62頁30n (pq)r = m1m3 m4m5m7n顯見，中的兩公式等值，而的不等值.第29頁/共62頁31n解 記 p:派A去, q:派B去, r:派C去n(1) pr, (2) qr, (3) (pq)(pq)n求下式的成真賦值nA=(pr)(qr)(pq)(pq)第30頁/共62頁32n(pq)(pq)n(pq)(pq)(pr)(pq)n(rq)(pq)(pq)(pq)n(pr)(pq)(rq)(pq)n (pqr)(pqr)n成真賦值:101,010n結(jié)論: 方案1 派

11、A與C去, 方案2 派B去第31頁/共62頁33, nA M0M2M4M5M6由主合取范式確定主析取范式由主合取范式確定主析取范式用真值表確定主范式用真值表確定主范式 第32頁/共62頁34定義定義2.6 稱稱F:0,1n 0,1 為為n元真值函數(shù)元真值函數(shù). 0,1n=000, 001, , 111，包含，包含 個長為個長為n的的0,1符號串符號串. 共有共有 個個n元真值函數(shù)元真值函數(shù). n22n221元真值函數(shù)元真值函數(shù) p 0 0 0 1 1 1 0 1 0 1 )1(3)1(2)1(1)1(0FFFF第33頁/共62頁35p q0 00 11 01 1 0 0 0 0 0 0 0 0

12、 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1p 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(7)2(6)2(5)2(4)2(3)2(2)2(1)2(0FFFFFFFF)2(15)2(14)2(13)2(12)2(11)2(10)2(9)2(8FFFFFFFF2元真值函數(shù)元真值函數(shù)第34頁/共62頁36)2(13F任何一個含任何一個含n個命題變項的命題公式個命題變項的命題公式A都對應惟一的一個都對應惟一的一個n元元真值函數(shù)真值函數(shù)

13、 F , F 恰好為恰好為A的真值表的真值表. 等值的公式對應的真值函數(shù)相同等值的公式對應的真值函數(shù)相同. 例如：例如：pq, p q 都對應都對應第35頁/共62頁37n定理2.6 S = , , 是聯(lián)結(jié)詞完備集n證明 由范式存在定理可證第36頁/共62頁38n(3) AB (AB)n(4) AB (AB)n(5) ABAB , ,不是聯(lián)結(jié)詞完備集不是聯(lián)結(jié)詞完備集, 0不能用它表示不能用它表示它的子集它的子集 , , , , , ,等都不是等都不是第37頁/共62頁39. n證明 , , 為完備集np pp (pp) ppn pq (pq) pq (pp)(qq) n pq (pq) (pq

14、) (pq)(pq) n得證為聯(lián)結(jié)詞完備集. 對類似可證第38頁/共62頁40nSS:S是可滿足的當且僅當S是可滿足的n定義2.9 設C1=lC1, C2=lcC2, C1和C2不含l和lc, 稱C1C2為nC1和C2(以l和lc為消解文字)的消解式或消解結(jié)果, 記作nRes(C1,C2)n例如, Res(pqr, pqs)= qrs第39頁/共62頁41. n(l)=1, 不妨設C1含l, 于是滿足C1. 把擴張到l(和lc)上:n若l=p, 則令(p)=0; 若lc=p, 則令(p)=1. 恒有(lc)=1, 從而n滿足C2. 得證C1C2是可滿足的.n注意: C1C2與Res(C1,C2

15、)有相同的可滿足性, 但不一定等值.第40頁/共62頁42.n例11 用消解規(guī)則證明S=(pq)(pqs)(qs)q是不可n滿足的.n證 C1=pq, C2= pqs, C3=Res(C1,C2)=qs, C4=qs, n C5=Res(C3,C4)=q, C6=q, C7=Res(C5,C6)=, 這是S的否證.第41頁/共62頁43n5. CRes(C1,C2)n6. If C= thenn7. 輸出“No”, 計算結(jié)束n8. If CS0且C S1 thenn9. S2S2C第42頁/共62頁44n18. 輸出“Yes”, 計算結(jié)束n19. Else S0S0S1, S1S2, S2,

16、goto 3第43頁/共62頁45npq, qrprn Res(pq, qr)= prn Res(qr, qr)=qn S2=pr, pr, qn循環(huán)2 S0=p, pq, pq, qr, qr, S1=pr, pr, q, S2=n Res(pq, q)=p第44頁/共62頁46第45頁/共62頁47l消解法第46頁/共62頁48第47頁/共62頁49說明說明:(2) 重言式的主合取范式不含任何極大項，為重言式的主合取范式不含任何極大項，為1. (3) 矛盾式的主合析范式不含任何極小項矛盾式的主合析范式不含任何極小項, 為為0. (4) , 不是完備集，如矛盾式不能寫成不是完備集，如矛盾式不

17、能寫成 , 中的公式中的公式. (5) , 是完備集是完備集. 真真假假假假假假真真第48頁/共62頁50n m0 m1 m2 m3 主析取范式n 1 主合取范式2. 判斷下列公式的類型判斷下列公式的類型: (1) (pq)( qp)重言式重言式第49頁/共62頁51主合取范式(2) (pq) q矛盾式矛盾式第50頁/共62頁52n M2 M3 主合取范式(3) (pq)p非重言式的可滿足式非重言式的可滿足式第51頁/共62頁53 A的主析取范式為的主析取范式為m1 m2 m7A的主合取范式為的主合取范式為M0 M3 M4 M5 M6 p q r F p q r F0 0 0 0 1 0 0

18、00 0 1 1 1 0 1 00 1 0 1 1 1 0 00 1 1 0 1 1 1 1第52頁/共62頁54解解 (1) (pq) r ( pq) r (2) (pq) r (p q) r (3) (pq) r ( pq) r ( ( pq)r)第53頁/共62頁55n(6) (pq)r (pq)rn(pq)r)n (pq)r n(pp)(qq)(rr) n說明：答案不惟一第54頁/共62頁56.n(5) 若周去，則趙、錢也去. n用等值演算法分析該公司如何選派他們出國？第55頁/共62頁57第56頁/共62頁58去sun(3) 錢、孫兩人中去且僅去一人(qr)(qr)n(4) 孫、李兩人同去或同不去(rs)(rs)n(5) 若周去，則趙、錢也去u(pq) 第57頁/共62頁