資源描述：
《析取范式與合取范式.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。
1、作業(yè)2.11p,q:0r,s:1(p?(q?r))?(r?s)(p?r)?(?q?s)(?p??q?r)?(p?q??r)(?p??q?r?s)?(p?q?r?s)12.2命題邏輯等值演算2.2.1等值式與等值演算等值式與基本等值式真值表法與等值演算法2.2.2聯(lián)結(jié)詞完備集真值函數(shù)聯(lián)結(jié)詞完備集與非聯(lián)結(jié)詞和或非聯(lián)結(jié)詞2等值式3定義2.11若等價(jià)式A?B是重言式,則稱A與B等值,記作A?B,并稱A?B是等值式說明:(1)?是元語言符號(hào),不要混同于?和=(2)A與B等值當(dāng)且僅當(dāng)A與B在所有可能賦值下的真值都相同,即A與B有相同的真
2、值表(3)n個(gè)命題變項(xiàng)的真值表共有個(gè),故每個(gè)命題公式都有無窮多個(gè)等值的命題公式(4)可能有啞元出現(xiàn).在B中出現(xiàn),但不在A中出現(xiàn)的命題變項(xiàng)稱作A的啞元.同樣,在A中出現(xiàn),但不在B中出現(xiàn)的命題變項(xiàng)稱作B的啞元.啞元的值不影響命題公式的真值.真值表法例1判斷?(p?q)與?p??q是否等值解4結(jié)論:?(p?q)?(?p??q)pq?p?qp?q?(p?q)?p??q?(p?q)?(?p??q)00110111011010011001100111001001真值表法(續(xù))例2判斷下述3個(gè)公式之間的等值關(guān)系:p?(q?r),(p?q)
3、?r,(p?q)?r解5pqrp?(q?r)(p?q)?r(p?q)?r000101001111010101011111100111101111110000111111p?(q?r)與(p?q)?r等值,但與(p?q)?r不等值基本等值式雙重否定律??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)A?(B?C)?(A?B)?(A?C)德摩根律?(A?B)??A??B?(A?B)??A??B吸收
4、律A?(A?B)?A,A?(A?B)?A6基本等值式(續(xù))零律A?1?1,A?0?0同一律A?0?A,A?1?A排中律A??A?1矛盾律A??A?0蘊(yùn)涵等值式A?B??A?B等價(jià)等值式A?B?(A?B)?(B?A)假言易位A?B??B??A等價(jià)否定等值式A?B??A??B歸謬論(A?B)?(A??B)??A7等值演算等值演算:由已知的等值式推演出新的等值式的過程置換規(guī)則:若A?B,則?(B)??(A)例3證明p?(q?r)?(p?q)?rp49,例2.12(1)證p?(q?r)??p?(?q?r)（蘊(yùn)涵等值式）?(?p??q
5、)?r（結(jié)合律）??(p?q)?r（德摩根律）?(p?q)?r（蘊(yùn)涵等值式）8實(shí)例9等值演算不能直接證明兩個(gè)公式不等值.證明兩個(gè)公式不等值的基本思想是找到一個(gè)賦值使一個(gè)成真,另一個(gè)成假.例4證明:p?(q?r)(p?q)?rp52方法一真值表法（見例2）方法二觀察法.容易看出000使左邊成真,使右邊成假.方法三先用等值演算化簡公式,再觀察.實(shí)例例5用等值演算法判斷下列公式的類型(1)q??(p?q)解q??(p?q)?q??(?p?q)（蘊(yùn)涵等值式）?q?(p??q)（德摩根律）?p?(q??q)（交換律，結(jié)合律）?p?0（
6、矛盾律）?0（零律）該式為矛盾式.10實(shí)例(續(xù))(2)(p?q)?(?q??p)解(p?q)?(?q??p)?(?p?q)?(q??p)（蘊(yùn)涵等值式）?(?p?q)?(?p?q)（交換律）?1該式為重言式.11實(shí)例(續(xù))(3)((p?q)?(p??q))?r)解((p?q)?(p??q))?r)?(p?(q??q))?r（分配律）?p?1?r（排中律）?p?r（同一律）非重言式的可滿足式.如101是它的成真賦值,000是它的成假賦值.12總結(jié):A為矛盾式當(dāng)且僅當(dāng)A?0;A為重言式當(dāng)且僅當(dāng)A?1說明:演算步驟不惟一,應(yīng)盡量使演
7、算短些真值函數(shù)定義2.12稱F:{0,1}n?{0,1}為n元真值函數(shù)13n元真值函數(shù)共有個(gè)每一個(gè)命題公式對應(yīng)于一個(gè)真值函數(shù)每一個(gè)真值函數(shù)對應(yīng)無窮多個(gè)命題公式1元真值函數(shù)p0001110101142元真值函數(shù)pq0000000000010000111110001100111101010101pq0011111111010000111110001100111101010101聯(lián)結(jié)詞完備集定義2.13設(shè)S是一個(gè)聯(lián)結(jié)詞集合,如果任何n(n?1)元真值函數(shù)都可以由僅含S中的聯(lián)結(jié)詞構(gòu)成的公式表示,則稱S是聯(lián)結(jié)詞完備集定理2.1下述聯(lián)結(jié)
8、詞集合都是完備集:(1)S1={?,?,?,?,?}(2)S2={?,?,?,?}(3)S3={?,?,?}(4)S4={?,?}(5)S5={?,?}(6)S6={?,?}15A?B?(A?B)?(B?A)A?B??A?BA?B???(A?B)??(?A??B)A?B??(?A??B)A
