




版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
第二章命題邏輯等值演算第二章命題邏輯等值演算1本章內(nèi)容等值式基本等值式等值演算置換規(guī)則析取范式和合取范式析取范式與合取范式主析取范式與主合取范式本章內(nèi)容等值式22.1等值式兩公式什么時(shí)候代表了同一個(gè)命題呢?抽象地看,它們的真假取值完全相同時(shí)即代表了相同的命題。設(shè)公式A,B共同含有n個(gè)命題變項(xiàng),可能A或B有啞元,若A與B有相同的真值表,則說(shuō)明在2n個(gè)賦值的每個(gè)賦值下,A與B的真值都相同。于是等價(jià)式A?B應(yīng)為重言式。2.1等值式兩公式什么時(shí)候代表了同一個(gè)命題呢?32.1等值式2.1等值式42.1等值式(p∨q)?(┐p∧┐q)的真值表2.1等值式(p∨q)?(┐p∧┐q)的真值表52.1等值式例、判斷下列各組公式是否等值:(1)p→(q→r)與(p∧q)→r(2)(p→q)→r與(p∧q)→r2.1等值式例、判斷下列各組公式是否等值:62.1等值式基本等值式2.1等值式基本等值式72.1等值式基本等值式(續(xù))2.1等值式基本等值式(續(xù))82.1等值式基本等值式(續(xù))2.1等值式基本等值式(續(xù))92.1等值式等值演算與置換規(guī)則2.1等值式等值演算與置換規(guī)則102.1等值式應(yīng)用舉例——證明兩個(gè)公式等值2.1等值式應(yīng)用舉例——證明兩個(gè)公式等值112.1等值式例、證明兩個(gè)公式不等值2.1等值式例、證明兩個(gè)公式不等值122.1等值式應(yīng)用舉例---判斷公式類型2.1等值式應(yīng)用舉例---判斷公式類型132.1等值式應(yīng)用舉例---判斷公式類型2.1等值式應(yīng)用舉例---判斷公式類型142.1等值式應(yīng)用舉例---判斷公式類型2.1等值式應(yīng)用舉例---判斷公式類型152.2析取范式與合取范式2.2析取范式與合取范式162.2析取范式與合取范式2.2析取范式與合取范式172.2析取范式與合取范式2.2析取范式與合取范式182.2析取范式與合取范式2.2析取范式與合取范式192.2析取范式與合取范式命題公式的方式2.2析取范式與合取范式命題公式的方式202.2析取范式與合取范式求公式的范式舉例2.2析取范式與合取范式求公式的范式舉例212.2析取范式與合取范式求公式的范式舉例2.2析取范式與合取范式求公式的范式舉例222.2析取范式與合取范式極大項(xiàng)與極小項(xiàng)2.2析取范式與合取范式極大項(xiàng)與極小項(xiàng)232.2析取范式與合取范式極大項(xiàng)與極小項(xiàng)2.2析取范式與合取范式極大項(xiàng)與極小項(xiàng)242.2析取范式與合取范式2.2析取范式與合取范式252.2析取范式與合取范式主析取范式與主合取范式2.2析取范式與合取范式主析取范式與主合取范式262.2析取范式與合取范式主析取范式與主合取范式2.2析取范式與合取范式主析取范式與主合取范式272.2析取范式與合取范式主析取范式與主合取范式求公式的主范式2.2析取范式與合取范式主析取范式與主合取范式282.2析取范式與合取范式主析取范式與主合取范式求公式的主范式2.2析取范式與合取范式主析取范式與主合取范式292.2析取范式與合取范式主析取范式與主合取范式求公式的主范式2.2析取范式與合取范式主析取范式與主合取范式302.2析取范式與合取范式主析取范式與主合取范式求公式的主范式2.2析取范式與合取范式主析取范式與主合取范式312.2析取范式與合取范式主范式的用途——與真值表相同2.2析取范式與合取范式主范式的用途——與真值表相同322.2析取范式與合取范式主范式的用途2.2析取范式與合取范式主范式的用途332.2析取范式與合取范式主范式的用途2.2析取范式與合取范式主范式的用途342.3聯(lián)接詞的完備集N元真值函數(shù)定義:就是有n個(gè)自變量的函數(shù),其自變量和函數(shù)值都是真值為0或者1。一元真值函數(shù)有4個(gè)2.3聯(lián)接詞的完備集N元真值函數(shù)352.3聯(lián)接詞的完備集N元真值函數(shù)二元真值函數(shù)有16個(gè)2.3聯(lián)接詞的完備集N元真值函數(shù)362.3聯(lián)接詞的完備集N元真值函數(shù)一般地,n元真值函數(shù)共有多少個(gè)呢?每個(gè)自變量有2個(gè)取值方式,n個(gè)自變量共有2n個(gè)不同取值方式。對(duì)n個(gè)自變量的每個(gè)取值方式,函數(shù)值有2個(gè)取值方式,即為0或1,故n元真值函數(shù)共有個(gè)。例如,3元真值函數(shù)共有=256個(gè)。
一般地,函數(shù)F:{0,1}n→{0,1}稱為n元真值函數(shù),其中:{0,1}n為{0,1}的卡氏積。
2.3聯(lián)接詞的完備集N元真值函數(shù)372.3聯(lián)接詞的完備集真值函數(shù)與命題公式的關(guān)系對(duì)于每個(gè)真值函數(shù),都可以找到許多與之等值的命題公式。以2元真值函數(shù)為例,所有矛盾式都與F0等值,所有的重言式都與F15等值。又如F13?(p→q)?(┐p∨q)?┐(p∧┐q)?(┐p∧┐q)∨(┐p∧q)∨(p∧q)。更重要的是,每個(gè)真值函數(shù)與唯一的一個(gè)主析取范式(主合取范式)等值。還以2元真值函數(shù)為例,0(矛盾式),(p∧q)m1,(p∧┐q)m2,(p∧┐q)∨(p∧q)m2∨m3,…反過(guò)來(lái),每個(gè)主析取范式對(duì)應(yīng)無(wú)窮多個(gè)與之等值的公式,所以每個(gè)真值函數(shù)對(duì)應(yīng)無(wú)窮多個(gè)與之等值的命題公式。由定理2.5可知,每個(gè)命題公式對(duì)應(yīng)唯一的與之等值的真值函數(shù)。2.3聯(lián)接詞的完備集真值函數(shù)與命題公式的關(guān)系382.3聯(lián)接詞的完備集聯(lián)結(jié)詞完備集定義:設(shè)S是一個(gè)聯(lián)結(jié)詞集合,如果任何n(n≥1)元真值函數(shù)都可以由僅含S中的聯(lián)結(jié)詞構(gòu)成的公式表示,則稱S是聯(lián)結(jié)詞完備集。定理:S={┐,∧,∨}是聯(lián)結(jié)詞完備集。因?yàn)槿魏蝞(n≥1)元真值函數(shù)都與唯一的一個(gè)主析取范式等值,而在主析取范式中僅含聯(lián)結(jié)詞┐,∧,∨,所以S={┐,∧,∨}是聯(lián)結(jié)詞完備集。2.3聯(lián)接詞的完備集聯(lián)結(jié)詞完備集392.3聯(lián)接詞的完備集聯(lián)結(jié)詞完備集以下聯(lián)結(jié)詞集都是完備集:(1)S1={┐,∧,∨,→}(2)S2={┐,∧,∨,→,}(3)S3={┐,∧}(4)S4={┐,∨}(5)S5={┐,→}解答:(1),(2)的成立是顯然的。(3)由于S={┐,∧,∨}是聯(lián)結(jié)詞完備集,因而任何真值函數(shù)都可以由僅含S中的聯(lián)結(jié)詞的公式表示。同時(shí)對(duì)于任意公式A,B,A∨B┐┐(A∨B)┐(┐A∧┐B),因而任意真值函數(shù)都可以由僅含S3={┐,∧}中的聯(lián)結(jié)詞的公式表示,所以S3是聯(lián)結(jié)詞完備集。(4)A∧B┐(┐A∨┐B)。(5)A∨B┐A→B。2.3聯(lián)接詞的完備集聯(lián)結(jié)詞完備集402.3聯(lián)接詞的完備集單元素聯(lián)結(jié)詞構(gòu)成的聯(lián)結(jié)詞完備集設(shè)p、q為兩個(gè)命題,復(fù)合命題“p與q的否定式”(“p或q的否定式”)稱作p,q的與非式(或非式),記作p↑q(p↓q)。符號(hào)↑(↓)稱作與非聯(lián)結(jié)詞(或非聯(lián)結(jié)詞)。p↑q為真當(dāng)且僅當(dāng)p與q不同時(shí)為真(p↓q為真當(dāng)且僅當(dāng)p與q同時(shí)為假)。
p↑q?┐(p∧q)p↓q?┐(p∨q)2.3聯(lián)接詞的完備集單元素聯(lián)結(jié)詞構(gòu)成的聯(lián)結(jié)詞完備集412.3聯(lián)接詞的完備集單元素聯(lián)結(jié)詞構(gòu)成的聯(lián)結(jié)詞完備集{↑},{↓}都是聯(lián)結(jié)詞完備集。證已知{┐,∧,∨}為聯(lián)結(jié)詞完備集,因而只需證明其中的每個(gè)聯(lián)結(jié)詞都可以由↑定義即可。而
┐p?┐(p∧p)?p↑p;p∧q?┐┐(p∧q)?┐(p↑q)?(p↑q
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 廉政風(fēng)險(xiǎn)防范管理工作實(shí)施方案(醫(yī)院版)
- 明廚亮灶視頻聯(lián)網(wǎng)監(jiān)管系統(tǒng)解決方案
- 老年友善管理工作制度(14篇)
- 海洋特色農(nóng)產(chǎn)品開(kāi)發(fā)
- 2025年石首市市直初中小學(xué)選調(diào)教師考試筆試試題(含答案)
- 2025年山東奇瑞汽車多崗招聘考試筆試試題(含答案)
- 老年護(hù)理課件視頻下載
- 老年護(hù)理課件-衣著護(hù)理
- 老年醫(yī)學(xué)專業(yè)技能課件
- 老年人睡眠健康教育課件
- 醫(yī)療急救車調(diào)度制度
- 門診停電應(yīng)急預(yù)案
- 《新能源材料與器件導(dǎo)論》課程教學(xué)大綱(新能源材料與器件專業(yè))
- 重慶市森林資源二類調(diào)查操作細(xì)則2012年
- 民航危險(xiǎn)品運(yùn)輸學(xué)習(xí)通超星期末考試答案章節(jié)答案2024年
- IEC31010-2019風(fēng)險(xiǎn)管理 風(fēng)險(xiǎn)評(píng)估技術(shù)(雷澤佳譯-2024)
- 人民法院司法警察執(zhí)法資格考試題庫(kù)(500題)
- 新生兒黃疸的護(hù)理常規(guī)
- (人教2024版)英語(yǔ)七年級(jí)上冊(cè) Unit 1單元復(fù)習(xí)課件(新教材)
- ISOIEC38507-2022信息技術(shù)-IT治理-組織使用人工智能的治理影響(中文版-雷澤佳譯2024)
- 國(guó)家開(kāi)放大學(xué)本科《西方行政學(xué)說(shuō)》期末紙質(zhì)考試總題庫(kù)珍藏版
評(píng)論
0/150
提交評(píng)論