ch命題邏輯等值演算實(shí)用PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1ch命題邏輯等值演算實(shí)用命題邏輯等值演算實(shí)用2l值n請(qǐng)驗(yàn)證：np(qr) (pq) r np(qr) 不與 (pq) r 等值第1頁(yè)/共62頁(yè)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頁(yè)/共62頁(yè)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頁(yè)/共62頁(yè)5A(BC)(AB)(AC)n德摩根律(AB)ABn(AB)ABn吸收律A(AB)A, A(AB)A第4頁(yè)/共62頁(yè)6n假言易位ABBAn等價(jià)否定等值式ABABn歸謬論(AB)(AB) An特別提示：必須牢記這16組等值式，這是繼續(xù)學(xué)習(xí)的基礎(chǔ)第5頁(yè)/共62頁(yè)7式，(B) 是用公式 B 置換n(A) 中所有的 A 后得到的命題公式n若 BA，則 (B)(A)第6頁(yè)/共62頁(yè)8n (pq)r（蘊(yùn)涵等值式，置換規(guī)則）n今后在注明中省去置換規(guī)則n注意：用等值演算不能直接證明兩個(gè)公式不等值第7頁(yè)/共62頁(yè)9npq r (p

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

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

5、19ln個(gè)命題變項(xiàng)有2n個(gè)極小項(xiàng)和2n個(gè)極大項(xiàng)l2n個(gè)極小項(xiàng)（極大項(xiàng)）均互不等值l用mi表示第i個(gè)極小項(xiàng)，其中i是該極小項(xiàng)成真賦值的十進(jìn)制表示. 用Mi表示第i個(gè)極大項(xiàng)，其中i是該極大項(xiàng)成假賦值的十進(jìn)制表示. mi（Mi）稱(chēng)為極小項(xiàng)（極大項(xiàng)）的名稱(chēng). 第18頁(yè)/共62頁(yè)20極小項(xiàng)極小項(xiàng)極大項(xiàng)極大項(xiàng)公式公式成真賦值成真賦值名稱(chēng)名稱(chēng)公式公式成假賦值成假賦值名稱(chēng)名稱(chēng) 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頁(yè)/共62頁(yè)21極小項(xiàng)極小項(xiàng)極大項(xiàng)極大項(xiàng)公式公式成真賦值成真賦值名稱(chēng)名稱(chēng)公式公式成

6、假賦值成假賦值名稱(chēng)名稱(chē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 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由三個(gè)命題變項(xiàng)由三個(gè)命題變項(xiàng) p, q, r 形成的極小項(xiàng)與極大項(xiàng)形成的極小項(xiàng)與極大項(xiàng). mi與與Mi的關(guān)系：的關(guān)系： mi Mi, Mi mi 第20頁(yè)/共62頁(yè)2

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

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

9、/共62頁(yè)26n (pqr)(pqr) n M0M4n, 代入 并排序，得n(pq)r M0M2M4（主合取范式）第25頁(yè)/共62頁(yè)27111，n成假賦值為 000, 010, 100. n類(lèi)似地，由主合取范式也立即求出成假賦值和成真賦值. 第26頁(yè)/共62頁(yè)28n A為矛盾式 A的主合析取范式含全部2n個(gè)極大項(xiàng)nA的主析取范式不含任何極小項(xiàng), 記為0.n A為非重言式的可滿(mǎn)足式nA的主析取范式中至少含一個(gè)、但不是全n部極小項(xiàng)nA的主合取范式中至少含一個(gè)、但不是全n部極大項(xiàng).第27頁(yè)/共62頁(yè)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非重言式的可滿(mǎn)足式第28頁(yè)/共62頁(yè)30n (pq)r = m1m3 m4m5m7n顯見(jiàn)，中的兩公式等值，而的不等值.第29頁(yè)/共62頁(yè)31n解 記 p:派A去, q:派B去, r:派C去n(1) pr, (2) qr, (3) (pq)(pq)n求下式的成真賦值nA=(pr)(qr)(pq)(pq)第30頁(yè)/共62頁(yè)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頁(yè)/共62頁(yè)33, nA M0M2M4M5M6由主合取范式確定主析取范式由主合取范式確定主析取范式用真值表確定主范式用真值表確定主范式 第32頁(yè)/共62頁(yè)34定義定義2.6 稱(chēng)稱(chēng)F:0,1n 0,1 為為n元真值函數(shù)元真值函數(shù). 0,1n=000, 001, , 111，包含，包含 個(gè)長(zhǎng)為個(gè)長(zhǎng)為n的的0,1符號(hào)串符號(hào)串. 共有共有 個(gè)個(gè)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頁(yè)/共62頁(yè)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頁(yè)/共62頁(yè)36)2(13F任何一個(gè)含任何一個(gè)含n個(gè)命題變項(xiàng)的命題公式個(gè)命題變項(xiàng)的命題公式A都對(duì)應(yīng)惟一的一個(gè)都對(duì)應(yīng)惟一的一個(gè)n元元真值函數(shù)真值函數(shù)

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

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

15、)有相同的可滿(mǎn)足性, 但不一定等值.第40頁(yè)/共62頁(yè)42.n例11 用消解規(guī)則證明S=(pq)(pqs)(qs)q是不可n滿(mǎ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頁(yè)/共62頁(yè)43n5. CRes(C1,C2)n6. If C= thenn7. 輸出“No”, 計(jì)算結(jié)束n8. If CS0且C S1 thenn9. S2S2C第42頁(yè)/共62頁(yè)44n18. 輸出“Yes”, 計(jì)算結(jié)束n19. Else S0S0S1, S1S2, S2,

16、goto 3第43頁(yè)/共62頁(yè)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頁(yè)/共62頁(yè)46第45頁(yè)/共62頁(yè)47l消解法第46頁(yè)/共62頁(yè)48第47頁(yè)/共62頁(yè)49說(shuō)明說(shuō)明:(2) 重言式的主合取范式不含任何極大項(xiàng)，為重言式的主合取范式不含任何極大項(xiàng)，為1. (3) 矛盾式的主合析范式不含任何極小項(xiàng)矛盾式的主合析范式不含任何極小項(xiàng), 為為0. (4) , 不是完備集，如矛盾式不能寫(xiě)成不是完備集，如矛盾式不

17、能寫(xiě)成 , 中的公式中的公式. (5) , 是完備集是完備集. 真真假假假假假假真真第48頁(yè)/共62頁(yè)50n m0 m1 m2 m3 主析取范式n 1 主合取范式2. 判斷下列公式的類(lèi)型判斷下列公式的類(lèi)型: (1) (pq)( qp)重言式重言式第49頁(yè)/共62頁(yè)51主合取范式(2) (pq) q矛盾式矛盾式第50頁(yè)/共62頁(yè)52n M2 M3 主合取范式(3) (pq)p非重言式的可滿(mǎn)足式非重言式的可滿(mǎn)足式第51頁(yè)/共62頁(yè)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頁(yè)/共62頁(yè)54解解 (1) (pq) r ( pq) r (2) (pq) r (p q) r (3) (pq) r ( pq) r ( ( pq)r)第53頁(yè)/共62頁(yè)55n(6) (pq)r (pq)rn(pq)r)n (pq)r n(pp)(qq)(rr) n說(shuō)明：答案不惟一第54頁(yè)/共62頁(yè)56.n(5) 若周去，則趙、錢(qián)也去. n用等值演算法分析該公司如何選派他們出國(guó)？第55頁(yè)/共62頁(yè)57第56頁(yè)/共62頁(yè)58去sun(3) 錢(qián)、孫兩人中去且僅去一人(qr)(qr)n(4) 孫、李兩人同去或同不去(rs)(rs)n(5) 若周去，則趙、錢(qián)也去u(pq) 第57頁(yè)/共62頁(yè)