九九热最新网址,777奇米四色米奇影院在线播放,国产精品18久久久久久久久久,中文有码视频,亚洲一区在线免费观看,国产91精品在线,婷婷丁香六月天

2-2 命題邏輯的等值和推理演算

上傳人:hjk****65 文檔編號:253198147 上傳時間:2024-11-30 格式:PPT 頁數(shù):34 大?。?29.50KB
收藏 版權(quán)申訴 舉報 下載
2-2 命題邏輯的等值和推理演算_第1頁
第1頁 / 共34頁
2-2 命題邏輯的等值和推理演算_第2頁
第2頁 / 共34頁
2-2 命題邏輯的等值和推理演算_第3頁
第3頁 / 共34頁

下載文檔到電腦,查找使用更方便

15 積分

下載資源

還剩頁未讀,繼續(xù)閱讀

資源描述:

《2-2 命題邏輯的等值和推理演算》由會員分享,可在線閱讀,更多相關(guān)《2-2 命題邏輯的等值和推理演算(34頁珍藏版)》請在裝配圖網(wǎng)上搜索。

1、單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,第,2,章 命題邏輯的等值和推理演算,2.1,等值定理,2.2,等值公式,2.3,命題公式與真值表的關(guān)系,2.4,聯(lián)結(jié)詞的完備集,2.5,對偶式,2.6,范式,2.7,推理形式,2.8,基本的推理公式,2.9,推理演算,2.10,歸結(jié)推理法,討論,等值演算,討論,推理演算,2.4,聯(lián)結(jié)詞的完備集,定義,在一個聯(lián)結(jié)詞的集合中,如果一個聯(lián)結(jié)詞可由集合中的其他聯(lián)結(jié)詞定義,則稱此聯(lián)結(jié)詞為,冗余的聯(lián)結(jié)詞,,否則稱為,獨立的聯(lián)結(jié)詞,。,如:,P,Q,=,P,Q,P,Q,=(,P,Q,)(,P,Q,),在,,,中、是冗余的。

2、,在,,,中,,P,Q,=,(,P,Q,),所以是冗余的。,在,,,中無冗余的聯(lián)結(jié)詞。,同理,,在,,,中無冗余的聯(lián)結(jié)詞。,聯(lián)結(jié)詞的完備集,定義,設(shè),C,是聯(lián)結(jié)詞的集合,若對任一命題公式都由,C,中的聯(lián)結(jié)詞表示出來的公式與之等值,就說,C,是,完備的聯(lián)結(jié)詞集合。,顯然,全體聯(lián)結(jié)詞的無限集合是完備的。,,,,,,,,,,,,,,,,,等也是完備的,。,是完備的,2.5,對偶式,定義,在僅含聯(lián)結(jié)詞,,的命題公式,A,中,將聯(lián)結(jié)詞,,,F,,,T,分別換成,,,T,,,F,所得的公式稱為公式,A,的,對偶式,,記為,A,*,如:,P,Q,與,P,Q,是對偶式,(,P,Q,),R,與,(,P,Q,),

3、R,是對偶式,推廣,在僅含有聯(lián)結(jié)詞,,的命題公式中,將聯(lián)結(jié)詞,,,F,,,T,分別換成,,,T,,,F,,就得到了它的對偶式。,與對偶式有關(guān)的定理,設(shè),A,和,A,*,互為對偶式,,P,1,P,2,P,n,是出現(xiàn)在,A,和,A,*,中的全部命題變項,,令,A,=,A,(,P,1,P,2,P,n,),A,=A,(,P,1,P,2,P,n,),定理,2.5.1,:,(,A,*)=(,A,)*,(,A,)=(,A,),如:,A,=,P,(,Q,R,),則:,A*=,P,(,Q,R,),,,A,=,P,(,Q,R,),A=,P,(,Q,R,),所以:,(,A,)*=,P,(,Q,R,),(,A,*)=

4、,P,(,Q,R,),所以:,(,A,),=,P,(,Q,R,),(,A,)=,P,(,Q,R,),(A*)=(,A)*,(,A,)=(,A),與對偶式有關(guān)的定理,定理,2.5.2,:,(,A,*)*=,A,(,A,),=,A,定理,2.5.3,:,A,=,A,*,如:,A,=,P,(,Q,R,),則,:,A,=,P,(,Q,R,),A,*=,P,(,Q,R,),所以:,A,*,=,P,(,Q,R,),=,A,此定理為摩根律:,(,A,B,)=,A,B,(,A,B,)=,A,B,的另一種形式,,,與對偶式有關(guān)的定理,定理,2.5.4,若,A,=,B,,必有,A,*=,B,*,證:,A,=,B,

5、A,B,永真,A,B,永真,A,*,B,*,永真,A,*,B,*,永真,A,*=,B,*,定理,2.5.5,若,A,B,永真,必有,B,*,A,*,永真,(作業(yè)),定理,2.5.6,A,與,A,同永真,同可滿足,A,與,A,*,同,永真,同可滿足,對偶性是邏輯規(guī)律,給證明公式的等值和求否定帶來方便,依定理,2.5.3,有,,A=A*,,,B,=B*,2.6,范 式,簡單析取式,它是僅由有限個命題變項或其否定構(gòu)成的析取式。,如,:,P,,,Q,,,P,,,Q,,,P,Q,,,P,Q,,,P,Q,它是,重言式,當(dāng)且僅當(dāng)它同時含一個命題變項及其否定;,如:,P,Q,P,是重言式,簡單合取式,它是僅由

6、有限個命題變項或其否定構(gòu)成的合取式。,如,:,P,,,Q,,,P,,,Q,,,P,Q,,,P,Q,它是,矛盾式,當(dāng)且僅當(dāng)它同時含一個命題變項及其否定。,如:,P,P,Q,是矛盾式,析取范式,析取范式,由有限個簡單合取式組成的析取式,A,1,A,2,.,A,n,(,n,1,,,A,i,都是,簡單合取式,),如:,(P,Q R),(P Q)Q,一個析取范式是,矛盾式,,當(dāng)且僅當(dāng)其每個簡單合取式都是,矛盾式,合取范式,由有限個簡單析取式組成的合取式,A,1,A,2,.,A,n,(,n,1,A,i,都,是,簡單析取式,),如:,(P,Q R),(P Q)Q,一個合取范式是,重言式,,當(dāng)且僅當(dāng)其每個簡單

7、析取式都是,重言式,范式,析取范式與合取范式的總稱,命題公式的范式,范式存在定理,任何命題公式都存在著與之等值的析取范式與合取范式,求公式,A,的范式的步驟,:,(1),消去,A,中的,(若存在),A,B,=,A,B,A,B=,(,A,B,),(,A,B,)(,求析取范式時,),=,(,A,B,),(,A,B,),(,求合取范式時,),(2),否定聯(lián)結(jié)詞,的內(nèi)移或消去(摩根定律),(3),使用分配律,對,分配(析取范式),對,分配(合取范式),注意:,公式的范式存在,但,不惟一,,這是它的局限性,求公式的范式舉例,例,:,求下列公式的析取范式與合取范式,(,1),A,=(,P,Q,),R,解,

8、(,P,Q,),R,=,(,P,Q,),R,(消去,),=,P,Q,R,(結(jié)合律),這既是,A,的,析取范式,(由,3,個簡單合取式組成的析取式),又是,A,的,合取范式,(由一個簡單析取式組成的合取式),求公式的范式舉例,(,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,),(,對,分配律),這一步得到,合取范式,(由兩個簡單析取式構(gòu)成,),極小項,定

9、義,n,個命題變項的,簡單合取式,,其中每個命題變項與其否定不同時出現(xiàn),,而二者之一必出現(xiàn)且僅出現(xiàn)一次,,這樣的簡單合取式稱為,極小項,。,如:兩個命題變元,P,和,Q,,其極小項為:,P,Q,,,P,Q,,,P,Q,,,P,Q,說明,n,個命題變項產(chǎn)生,2,n,個極小項,它們互不等值,用,m,i,表示第,i,個極小項,,每個小項的,n,個變元排序相同。(按下標(biāo)或字典順序),分別記為,其中,i,是該極小項,成真賦值,的十進制表示,.,m,11,m,10,m,01,m,00,極小項,由,P,Q,R,三個命題變項形成的極小項,極小項,成真賦值,名稱,P,Q,R,000,m,0,P,Q,R,001,

10、m,1,P,Q,R,010,m,2,P,Q,R,011,m,3,P,Q,R,100,m,4,P,Q,R,101,m,5,P,Q,R,110,m,6,P,Q,R,111,m,7,主析取范式,主析取范式,設(shè)命題公式,A,中含,n,個命題變項,如果,A,的析取范式中的簡單合取式全是,極小項,,則稱該析取范式為,A,的,主析取范式,如:,n,=3,命題變項為,P,Q,R,時,主析取范式,:,(,P,Q,R,),(,P,Q,R,)=,m,1,m,3,定理,任何命題公式都存在與之等值的主析取范式,并且是惟一的,.,求主析取范式的方法,等值演算法和真值表法,用等價演算法求主析取范式的步驟,1.,求,A,的析

11、取范式,A,;,2.,若,A,的某簡單合取式,B,中不含某命題變項或其否 定,則將,B,展成如下形式:,B,=,B,1,=,B,(,P,i,P,i,),=,(,B,P,i,),(,B,B,i,),3.,將重復(fù)出現(xiàn)的命題變項、矛盾式及重復(fù)出現(xiàn)的極小項都“消去”。,4.,將極小項按由小到大的順序排列,并用,表示之,如,m,1,m,2,m,6,用,(1,2,6),表示,。,求公式,A,=(,P,Q,),R,的主析取范式,解法,1,:,(,P,Q,),R,=,(,P,Q,),R,=,(,P,Q,),R,(析取范式),(,P,Q,),=(,P,Q,),(,R,R,),=,(,P,Q,R,),(,P,Q,

12、R,),=,m,6,m,7,R,=,(,P,P,),(,Q,Q,),R,=,(,P,Q,R,),(,P,Q,R,),(,P,Q,R,),(,P,Q,R,),=,m,1,m,3,m,5,m,7,代入并合并相同式,得主析取范式:,(,P,Q,),R,=,m,1,m,3,m,5,m,6,m,7,=,(1,3,5,6,7),解法,2,:,(,P,Q,),R,=,(,P,Q,),R,=,(,P,Q,),R,(析取范式),=,m,11x,m,xx1,=,(,m,11,0,m,11,1,),(,m,00,1,m,01,1,m,10,1,m,11,1,),=,(1,3,5,6,7),求公式,A,=(,P,Q,

13、),R,的主析取范式,主析取范式的用途,(,1),求公式的成真賦值和成假賦值,如前面例子中得到,(,P,Q,),R,=,m,1,m,3,m,5,m,6,m,7,其成真賦值為:,001,011,101,110,111,則其余的賦值為成假賦值,000,010,100,主析取范式的用途,(,2),判斷公式的類型,設(shè),A,含,n,個命題變項,則,A,為重言式,A,的主析取范式含,2,n,個極小項,如命題變項為,P,Q,時,,A=,(0,1,2,3),A,為矛盾式,A,的主析取范式為,0,如,A=,0,A,為可滿足式,A,的主析取范式中至少含一個極小項,如,A=,(2,3),(,P,Q,),Q,=(,P

14、,Q,),Q,=,P,Q,Q,=,F,(,矛盾式,),用主析取范式判斷公式的類型,如前面例子中得到,(,P,Q,),R,=,m,1,m,3,m,5,m,6,m,7,=,(1,3,5,6,7),(,可滿足式),(,P,Q,),P,),Q,=(,P,Q,),P,),Q,=(,P,Q,),P,Q,=,m,10,m,0 x,m,x1,=,m,10,m,00,m,01,m,01,m,11,=,m,0,m,1,m,2,m,3,=(0,1,2,3)=,T,(,重言式,),用主析取范式判斷公式的類型,主析取范式的用途,(,3),判斷兩個公式是否等值,如,P,Q,=,P,Q,=,m,0 x,m,x1,=,m,0

15、0,m,01,m,01,m,11,=,m,0,m,1,m,3,=,(0,1,3),P,(,P,Q,),=,m,0 x,m,11,=,m,00,m,01,m,11,=,m,0,m,1,m,3,=,(0,1,3),所以,P,Q =,P,(,P,Q,),定理,任何命題公式都存在與之等值的主析取范式,并且是惟一的,.,主析取范式的應(yīng)用,(4),舉例,例:甲、乙、丙、丁四人參加考試,有人問他們,誰的成績最好,,甲說:,“,不是我,”,乙說:,“,是丁,”,丙說:,“,是乙,”,丁說:,“,不是我,”,四人的回答只有一人符合實際,,問是誰的成績最好,若只有一人成績最好,他是誰?,解此類問題的步驟為:,將簡

16、單命題符號化,寫出各復(fù)合命題,寫出由中復(fù)合命題組成的合取式,求,中所得公式的主析取范式,主析取范式的應(yīng)用舉例,解,設(shè),A,:甲的成績最好,B,:乙的成績最好,,C,:丙的成績最好,D,:丁的成績最好,,(1)(,A,D,B,D,),(2)(,A,D,B,D,),(3)(,A,D,B,D,),(4)(,A,D,B,D,),例:甲、乙、丙、丁四人參加考試,有人問他們,誰的成績最好,,甲說:,“,不是我,”,乙說:,“,是丁,”,丙說:,“,是乙,”,丁說:,“,不是我,”,四人的回答只有一人符合實際,,問是誰的成績最好,若只有一人成績最好,他是誰?,主析取范式的應(yīng)用舉例,(1)(,A,D,B,D,),(2)(,A,D,B,D,),(3)(,A,D,B,D,),(4)(,A,D,B,D,),(1)(4),構(gòu)成的析取式為,(,A,D,B,D,),(,A,D,B,D,),(,A,D,B,D,),(,A,D,B,D,),主析取范式的應(yīng)用舉例,求,中所得公式的主析取范式,(,A,D,B,D,),(,A,D,B,D,),(,A,D,B,D,),(,A,D,B,D,),=(,A,D,B,D,),(,A,

展開閱讀全文
溫馨提示:
1: 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

相關(guān)資源

更多
正為您匹配相似的精品文檔
關(guān)于我們 - 網(wǎng)站聲明 - 網(wǎng)站地圖 - 資源地圖 - 友情鏈接 - 網(wǎng)站客服 - 聯(lián)系我們

copyright@ 2023-2025  zhuangpeitu.com 裝配圖網(wǎng)版權(quán)所有   聯(lián)系電話:18123376007

備案號:ICP2024067431-1 川公網(wǎng)安備51140202000466號


本站為文檔C2C交易模式,即用戶上傳的文檔直接被用戶下載,本站只是中間服務(wù)平臺,本站所有文檔下載所得的收益歸上傳人(含作者)所有。裝配圖網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對上載內(nèi)容本身不做任何修改或編輯。若文檔所含內(nèi)容侵犯了您的版權(quán)或隱私,請立即通知裝配圖網(wǎng),我們立即給予刪除!