版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
1、多媒體中心 莊伯金 bjzhuang@bupt.edu.cn,1,第二章,謂詞邏輯,多媒體中心 莊伯金 bjzhuang@bupt.edu.cn,2,主要內(nèi)容,謂詞邏輯的基本概念謂詞公式謂詞邏輯等值式謂詞邏輯推理,多媒體中心 莊伯金 bjzhuang@bupt.edu.cn,3,命題邏輯的不足之處,命題邏輯研究的對象為命題(為一個(gè)完整的陳述句),對于原子命題不可分。例魚兒離不開水。鯽魚是魚。所以鯽魚離不開水。簡單命題之間
2、的內(nèi)在聯(lián)系需要通過進(jìn)一步分析原子命題中主、謂等之間的關(guān)系。個(gè)體謂詞量詞,多媒體中心 莊伯金 bjzhuang@bupt.edu.cn,4,個(gè)體,定義:可以獨(dú)立存在的客觀實(shí)體稱為個(gè)體。具體事物抽象概念例小王和小明是同學(xué)。a能被2整除。x是有理數(shù)。個(gè)體常項(xiàng):表示具體或特定的個(gè)體,常用字母a,b,c...表示;個(gè)體變項(xiàng):表示抽象或泛指的個(gè)體,常用字母x,y,z...表示;個(gè)體域:個(gè)體變項(xiàng)的取值范圍,也稱論域。全總個(gè)體
3、域:宇宙間一切事物組成的個(gè)體域。,多媒體中心 莊伯金 bjzhuang@bupt.edu.cn,5,謂詞,定義:刻畫個(gè)體具有的性質(zhì)或個(gè)體之間關(guān)系的詞。謂詞常項(xiàng):表示具體性質(zhì)或關(guān)系的謂詞。謂詞變項(xiàng):表示抽象的或泛指的謂詞。謂詞符號(hào)通常用大寫字母表示。例:F:...和...是同學(xué)。G:...能被...整除。H:...是有理數(shù)。,多媒體中心 莊伯金 bjzhuang@bupt.edu.cn,6,謂詞,元數(shù):謂詞中包含的個(gè)體變項(xiàng)數(shù)
4、。含n個(gè)個(gè)體變項(xiàng)的謂詞稱為n元謂詞。0元謂詞:不帶個(gè)體變項(xiàng)的謂詞。命題均可以表示成0元謂詞。例:4=3+1如果2是素?cái)?shù),則3是素?cái)?shù)。,多媒體中心 莊伯金 bjzhuang@bupt.edu.cn,7,量詞,定義:表示個(gè)體常項(xiàng)或變項(xiàng)之間數(shù)量關(guān)系的詞。全稱量詞:一切的、所有的、每一個(gè)、任意的、都...。符號(hào)化為“?”。表示個(gè)體域里的所有個(gè)體關(guān)系。存在量詞:存在、有一個(gè)、有的、至少有一個(gè)...。符號(hào)化為“?”。表示個(gè)體域里有的個(gè)
5、體關(guān)系。例所有人都需要呼吸空氣。有的人沒來上課。,多媒體中心 莊伯金 bjzhuang@bupt.edu.cn,8,量詞,量詞需要注意個(gè)體域的問題。在不同的個(gè)體域內(nèi),命題的真值可能不同。例:存在x,使得x+3=2。個(gè)體域?yàn)樽匀粩?shù)個(gè)體域?yàn)檎麛?shù)特性謂詞:將某類個(gè)體從個(gè)體域中區(qū)分出來的謂詞。M(x):x是人;F(x):x是魚;Z(x):x是整數(shù)。,多媒體中心 莊伯金 bjzhuang@bupt.edu.cn,9,命題符號(hào)化
6、,明確命題個(gè)體域,分別找出個(gè)體常項(xiàng)、個(gè)體變項(xiàng)、量詞和謂詞;按照命題的意思用邏輯聯(lián)結(jié)詞將其組合;注意:引入特性謂詞時(shí),全稱量詞的特性謂詞作為命題的前提引入,而存在量詞的特性謂詞作為命題的合取項(xiàng)引入;多個(gè)量詞同時(shí)出現(xiàn),需要注意量詞的順序不能隨意顛倒。例:并非所有的人都愛看電視。,多媒體中心 莊伯金 bjzhuang@bupt.edu.cn,10,一階謂詞的例,火車比汽車跑得快。有理數(shù)可以表示成分?jǐn)?shù)。有的女孩不喜歡穿裙子。,多
7、媒體中心 莊伯金 bjzhuang@bupt.edu.cn,11,謂詞公式,謂詞公式的符號(hào)集個(gè)體常項(xiàng):a,b,c,...個(gè)體變項(xiàng):x,y,z,...函數(shù)符號(hào):f,g,h,...謂詞符號(hào):F,G,H,...量詞:?, ?;聯(lián)結(jié)詞符號(hào):¬,∧,∨,→,?;括號(hào):),(,多媒體中心 莊伯金 bjzhuang@bupt.edu.cn,12,謂詞公式,謂詞公式的項(xiàng)的遞歸定義個(gè)體常項(xiàng)和個(gè)體變項(xiàng)是項(xiàng);若f(x1,x2,..
8、.,xn)是任意的n元函數(shù),t1,t2,...,tn是任意n個(gè)項(xiàng),則f(t1,t2,...,tn)是項(xiàng);所有的項(xiàng)都由有限次使用上述兩條規(guī)定得到。原子公式:設(shè)R(x1,x2,...,xn)是符號(hào)集上任意n元謂詞,t1,t2,...,tn是符號(hào)集的任意n個(gè)項(xiàng),則稱R(t1,t2,...,tn)為原子公式。,多媒體中心 莊伯金 bjzhuang@bupt.edu.cn,13,合式公式,定義(1)原子公式是合式公式;(2)若A是合式公式
9、,則(¬A)也是合式公式(3)若A,B是合式公式,則(A∧B),(A∨B),(A→B),(A?B)也是合式公式;(4)若A是合式公式,則?xA,?xA也是合式公式;(5)只有有限次的應(yīng)用(1)-(4)得到的符號(hào)串才是合式公式。,多媒體中心 莊伯金 bjzhuang@bupt.edu.cn,14,約束變項(xiàng)及自由變項(xiàng),定義: ?xF,?xF中,x稱為指導(dǎo)變項(xiàng),F(xiàn)稱為相應(yīng)量詞的轄域。轄域中x的所有出現(xiàn)稱為約束出現(xiàn),x稱為約束變
10、項(xiàng),F(xiàn)中不是約束出現(xiàn)的其他變項(xiàng)稱為自由變項(xiàng)。例?x F(x)→?y G(x,y)?x(F(x,y)∧?y(G(x,y))?x?y(F(x,y)∧G(y,z))∨H(x,y)閉式:若合式公式中無自由出現(xiàn)的個(gè)體變項(xiàng),則稱A為封閉的公式,簡稱閉式。,多媒體中心 莊伯金 bjzhuang@bupt.edu.cn,15,變項(xiàng)替換規(guī)則,變項(xiàng)替換的目的:為了避免個(gè)體變項(xiàng)的混淆。規(guī)則約束變項(xiàng)換名規(guī)則:將量詞轄域中出現(xiàn)的某個(gè)約束變項(xiàng)及其對應(yīng)
11、的指導(dǎo)變項(xiàng)改成公式中未出現(xiàn)的個(gè)體變項(xiàng)符號(hào),其余部分不變。自由變項(xiàng)代替規(guī)則:將公式中某自由變項(xiàng)用原公式中未出現(xiàn)過的某個(gè)個(gè)體變項(xiàng)符號(hào)代替,且處處代替。,多媒體中心 莊伯金 bjzhuang@bupt.edu.cn,16,謂詞公式的解釋,定義:為使公式成為真值確定的命題而指定的有關(guān)規(guī)定,稱為謂詞公式的一個(gè)解釋。解釋I的組成特定的個(gè)體域DD中一部分特定元素D上每個(gè)函數(shù)變項(xiàng)所取得的具體函數(shù)D上每個(gè)謂詞變項(xiàng)所取的具體謂詞例: ?x(F
12、(f(x))→G(x)),多媒體中心 莊伯金 bjzhuang@bupt.edu.cn,17,謂詞公式的分類,謂詞公式的分類:如果A在任何解釋下都為真,則稱A為永真式(邏輯有效式)。如果A在任何解釋下都為假,則稱A為永假式(矛盾式)。若至少存在一組A的解釋使A為真,則稱A為可滿足式。代換實(shí)例:設(shè)A0是含命題變項(xiàng)p1,p2,...,pn的命題公式,A1,A2,...,An是n個(gè)謂詞公式。用Ai代換A0中的每一個(gè)pi,所得的公式A稱
13、為A0的代換實(shí)例。,多媒體中心 莊伯金 bjzhuang@bupt.edu.cn,18,謂詞公式的定理,定理:命題公式中的重言式的代換實(shí)例在謂詞公式中為邏輯有效式;命題公式中的矛盾式的代換實(shí)例是謂詞公式中仍為矛盾式。,多媒體中心 莊伯金 bjzhuang@bupt.edu.cn,19,謂詞邏輯等值式,等值式的定義:設(shè)謂詞邏輯中任意兩個(gè)公式A和B,若A?B是是邏輯有效式,則稱A與B為等值式。記作A?B。原命題等值式的代換實(shí)例都是等值
14、式。消去量詞等值式:設(shè)個(gè)體域D={a1,a2,...,an}?xA(x)?A(a1)∧A(a2)∧...∧A(an)?xA(x)?A(a1)∨A(a2)∨...∨A(an)量詞否定等值式¬?xA(x) ??x¬A(x) ¬?xA(x) ??x¬A(x),多媒體中心 莊伯金 bjzhuang@bupt.edu.cn,20,謂詞邏輯等值式,量詞轄域擴(kuò)張和伸縮等值式?x(A(x)∨B)??
15、xA(x)∨B ?x(A(x)∨B)??xA(x)∨B?x(A(x)∧B)??xA(x)∧B?x(A(x)∧B)??xA(x)∧B?x(A(x)→B)??xA(x)→B?x(A(x)→B)??xA(x)→B?x(B→A(x))?B→?xA(x)?x(B→A(x))?B→?xA(x),多媒體中心 莊伯金 bjzhuang@bupt.edu.cn,21,謂詞邏輯等值式,量詞分配等值式?x(A(x)∧B(x))??xA(x)∧
16、?xB(x)?x(A(x)∨B(x))??xA(x)∨?xB(x)量詞交換等值式?x?yA(x,y) ??y?xA(x,y) ? x?yA(x,y) ??y?xA(x,y),多媒體中心 莊伯金 bjzhuang@bupt.edu.cn,22,前束范式,定義:設(shè)A為謂詞邏輯公式,若A具有形式Q1x1Q2x2...QnxnB,其中Qi 為?或? ,B為不含量詞的公式。存在定理:任何謂詞邏輯公式都存在與之等值的前束范式。,前束范式,
17、例:?xF(x)→?xG(x)(?xF(x,y)→?yG(y))→?xH(x,y),多媒體中心 莊伯金 bjzhuang@bupt.edu.cn,23,多媒體中心 莊伯金 bjzhuang@bupt.edu.cn,24,作業(yè)(1),P53 2.1 (2)(3)(4) P53 2.2 (2)(3)P53 2.3 (3)(4)P54 2.5 (1),多媒體中心 莊伯金 bjzhuang@bupt.edu.cn,25,作業(yè)(
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫僅提供信息存儲(chǔ)空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 《離散數(shù)學(xué)課件》謂詞邏輯2
- 離散數(shù)學(xué)-謂詞邏輯
- 離散數(shù)學(xué)第10章-謂詞邏輯
- 離散數(shù)學(xué)謂詞
- 《離散數(shù)學(xué)課件》命題邏輯2
- 離散數(shù)學(xué) 2
- 北大離散數(shù)學(xué)chap5
- 離散數(shù)學(xué)課件2
- 離散數(shù)學(xué)第2講
- 離散數(shù)學(xué)ch2
- 離散數(shù)學(xué)答案命題邏輯
- 離散數(shù)學(xué) ( 第2次 ).doc
- 2015離散數(shù)學(xué)謂詞量詞、變元的約束、翻譯
- 《離散數(shù)學(xué)x》在線平時(shí)作業(yè)2
- 離散數(shù)學(xué)課件第2章
- 《離散數(shù)學(xué)課件》謂詞演算的推理理論
- 《離散數(shù)學(xué)課件》命題邏輯1
- 《離散數(shù)學(xué)課件》命題邏輯3
- 2017離散數(shù)學(xué)答案1--5)(2)
- 離散數(shù)學(xué)第2章第1節(jié)
評(píng)論
0/150
提交評(píng)論