哈工大人工智能課件chpt3124

1、 13.1 命題邏輯和一階謂詞邏輯3.2 邏輯系統(tǒng)的語法和語義3.3 邏輯推理舉例3.4 邏輯智能體的推理策略參考書目附錄 形式系統(tǒng)簡介第3章 邏輯系統(tǒng)2 AI研究內(nèi)容之一是推理，即研究怎樣使計算機獲得自動推理的能力 數(shù)理邏輯用數(shù)學(xué)方法研究各種推理中的邏輯問題，以推理本身作為研究對象 AI要使用邏輯推理，就必然涉及數(shù)理邏輯 / 數(shù)理邏輯的經(jīng)典部分經(jīng)典的命題邏輯和一階謂詞邏輯，同時作為人工智能的知識表示方法和推理方法而存在；因此數(shù)理邏輯是人工智能的一個基礎(chǔ)第3章 邏輯系統(tǒng)3 基于知識的智能體的核心部件是知識庫，當(dāng)這些知識以邏輯形式表示并進行相應(yīng)的推理時，就是邏輯智能體 知識表示：命題邏輯、一階謂

2、詞邏輯 推理(一階謂詞邏輯)主要有3類推理算法：前向鏈接和演繹系統(tǒng)、反向鏈接和邏輯程序設(shè)計(本章)、歸結(jié)反演和定理證明系統(tǒng)(第4章) 采用命題和謂詞演算進行推理的系統(tǒng)(如演繹系統(tǒng))是一種典型的邏輯智能體第3章 邏輯系統(tǒng)43.1 命題邏輯和一階謂詞邏輯命題、真值、原子公式、合式公式謂詞、論域、個體量詞、變量、函數(shù)一階語言、一階語言的項第3章 邏輯系統(tǒng)5 命題：描述客觀世界的可區(qū)分真假的陳述句, 即一個判斷（經(jīng)典二值邏輯：非真即假） 是命題的例子： 2+2=4 / 二月份有30天 / 2002年威海有地震 / 北京是中國首都 不是命題的例子： 快點走吧 / 張三比李四聰明 / 公共汽車內(nèi)非常擁擠（

3、各人認識不同）第3章 邏輯系統(tǒng)6 命題變量（變元）：一個命題用符號表示，稱為命題符號 當(dāng)命題符號代表任一個命題時，即為命題變量 真值：真或假 一個命題或命題變量具有真值 真值連接詞（5個）：否定/合取/析取/蘊涵/等價 真值函數(shù)：真值聯(lián)結(jié)詞可以視為一元或二元映射(真值函數(shù))，是從T,F到T,F，其余是T,F2到T,F的映射 / 其函數(shù)定義由真值表確定第3章 邏輯系統(tǒng)7 簡單命題：一個被視為整體的、具有真或假的命題是簡單命題 復(fù)合命題：使用聯(lián)結(jié)詞將簡單命題聯(lián)結(jié)起來的命題是復(fù)合命題第3章 邏輯系統(tǒng)8 定義： 合取式：p與q，記做p q 析取式：p或q，記做p q 蘊含式：如果p則q，記做p q 等

4、價式：p當(dāng)且僅當(dāng)q，記做pq第3章 邏輯系統(tǒng)9 定義： 若A無成假賦值，則稱A為重言式或永真式； 若A無成真賦值，則稱A為矛盾式或永假式； 若A至少有一個成真賦值，則稱A為可滿足的； 析取范式：僅由有限個簡單合取式組成的析取式 合取范式：僅由有限個簡單析取式組成的合取式 第3章 邏輯系統(tǒng)10 基本等值式（24個） 交換律：pq q p p q q p 結(jié)合律： (pq) r p(q r); (p q) r p (q r) 分配律： p(q r) (pq)(p r) ； p (q r) (p q) (p r)第3章 邏輯系統(tǒng)11 基本等值式（24個） 摩根律: (pq) p q ； (p q)

5、p q 吸收律: p(pq ) p ； p (pq ) p 同一律: p0 p ； p1 p 蘊含等值式：p q pq 假言易位式: p q p q 第3章 邏輯系統(tǒng)12 命題邏輯：研究復(fù)合命題之間的推導(dǎo)關(guān)系 命題語言：是命題邏輯使用的形式語言，是符號的集合,用Lp表示 包括：命題符號、連接詞、左右括號 原子公式：命題語言中的一個表達式是原子公式，當(dāng)且僅當(dāng)它是一個命題符號 / 原子公式也稱為文字(包括正文字和負文字)第3章 邏輯系統(tǒng)13 合式公式(well-formed formula)，簡稱公式，記作wff：一個表達式是一個公式，當(dāng)且僅當(dāng)它能通過有限次地使用下述步驟生成：(1)原子公式是公式

6、；(2)如果A是公式，則(A)是公式；(3)如果A、B均為公式，則A*B是公式，其中*表示中的任意一個 公式的形成規(guī)則 命題邏輯的主要研究對象是公式第3章 邏輯系統(tǒng)14例子 將陳述句轉(zhuǎn)化成命題公式。 如：設(shè)“下雨”為p，“騎車上班”為q 1 “只要不下雨，我就騎車上班”。 p是q的充分條件，因而可得命題公式：pq 2 “只有不下雨，我才騎車上班”。 p是q的必要條件，因而可得命題公式： q p15例子 1 “如果我進城我就去看你，除非我很累” 設(shè)：p, 我進城，q，去看你，r，我很累，則有命題公式：r(pq) 2”應(yīng)屆高中生，得過數(shù)學(xué)或物理競賽的一等獎，保送上大學(xué)“ 設(shè)：p，應(yīng)屆高中生；q,保

7、送上大學(xué)；r,得過數(shù)學(xué)競賽的一等獎；t,得過物理競賽的一等獎。則有命題公式：p (rt)q 16 命題邏輯：使用陳述性、上下文無關(guān)、無歧義性、合成性的形式語言 陳述性使用符號描述(語句形式)顯式地表示知識 ( 相對于過程性將需要的知識直接編寫為程序代碼 ) 上下文無關(guān)其含義不因環(huán)境而改變 無歧義性含義唯一 合成性語句的含義是其各部分含義的一個函數(shù)(也是一種唯一性)第3章 邏輯系統(tǒng)17 從命題到一階謂詞：命題內(nèi)部邏輯結(jié)構(gòu)的分解 對判斷的分解，把判斷中的具體內(nèi)容抽出，稱為個體；剩下的判斷即為謂詞 謂詞可看作是從個體域或個體域的笛卡兒乘積到真值集合T/F的映射 典型的推理例子：(1)凡人皆有死；(2

8、)蘇格拉底是人；(3)蘇格拉底有死。（三段論式）M(x)D(x), M(s) D(s)第3章 邏輯系統(tǒng)18例子 小王是個工程師 8是個自然數(shù) 我去買花 小麗和小華是朋友 其中，“小王”、“工程師”、“8”、“我”、“花”、“小麗”、“小華”都是個體，而“是個工程師”、“是個自然數(shù)”、“去買花”、“是朋友”都是謂詞。顯然前兩個謂詞表示的是事物的性質(zhì)，第三個謂詞表示的是一個動作，也表示了主、賓兩個個體的關(guān)系，最后一個謂詞“是朋友”表示兩個個體之間的關(guān)系。19 論域和個體：在一階邏輯中，被研究對象構(gòu)成的非空集稱為論域；論域中的每個元素稱為個體 論域例子：前面例子中的論域是“人” / 所有的有理數(shù)都是

9、實數(shù)：其論域為有理數(shù) 一階邏輯還研究個體之間的關(guān)系（或個體的性質(zhì)）及作用于個體的函數(shù) 論域/個體/個體間關(guān)系/作用于個體函數(shù) 這4個成分構(gòu)成了一階邏輯的結(jié)構(gòu)第3章 邏輯系統(tǒng)20 謂詞（關(guān)系）：一階形式語言中用于指稱論域中個體的性質(zhì)或者個體之間關(guān)系的形式符號（大寫字母表示） 給定了論域，就確定了謂詞的真假值 一元謂詞：個體的性質(zhì)；二元謂詞(多元謂詞)：個體的關(guān)系 個體的位置空位，具體化構(gòu)成意義完整的語句 空位的數(shù)目謂詞的元數(shù)幾元謂詞第3章 邏輯系統(tǒng)21 變量(變元)：表示論域內(nèi)的任意一個個體 / 常量(常元)，表示確定的個體 量詞與變量：量詞用來表示謂詞的判斷特性 全稱量詞：對所有的x x P(

10、x) 存在量詞：存在x x P(x) 約束變量：、中x的變量，量詞所管轄的公式如P(x)稱為量詞轄域 自由變量：不在量詞轄域內(nèi)的變量為自由變量第3章 邏輯系統(tǒng)22 區(qū)別：自由變量可代入常量，約束變量不行，因為a P(a)無意義 ；約束變量可改名，自由變量不行 帶有全稱變量x的命題表示為一階公式時，其表示形式為 x(P(x)，帶有存在變量x的命題則表示形式為x(P(x) 例子：所有有理數(shù)都是實數(shù) x(P(x)R(x)，有些人身高超過2米x(M(x)G(x) 上述使用方式不可改變，否則造成邏輯錯誤第3章 邏輯系統(tǒng)23 函數(shù)：表示個體之間的運算，可作用于一個或數(shù)個個體（用小寫字母） 給定一個或若干個

11、體（對象），產(chǎn)生一個新的個體（對象）/ 函數(shù)的元數(shù) 例子：x的父親 father(張三) 兩數(shù)之和仍是一個數(shù) add(e1, e2)第3章 邏輯系統(tǒng)24 謂詞和函數(shù)的區(qū)別：謂詞代表語句，結(jié)果是關(guān)系（具有真假值）；函數(shù)代表關(guān)系運算，結(jié)果是一個新個體 例子：謂詞SUM(e1, e2, e3) 說明e1、e2、e3之間的關(guān)系是e1與e2的和是e3 ， 函數(shù)add(e1, e2)說明e1與e2相加的結(jié)果仍是一個數(shù)第3章 邏輯系統(tǒng)25 一階語言L：是一階邏輯使用的形式語言，可以和任何結(jié)構(gòu)（論域）沒有聯(lián)系，也可以與某個結(jié)構(gòu)有聯(lián)系 與結(jié)構(gòu)沒有聯(lián)系的一階語言由8類符號組成：(1)無限序列的個體符號（個體常量）

12、(2)無限序列的謂詞符號，有確定的元數(shù)n1有一個特殊的謂詞符號稱為相等符號（等式），記為=。 L可含或不含=，如果含有，即稱為含=的一階邏輯第3章 邏輯系統(tǒng)26(3)無限序列的函數(shù)符號，有確定的元數(shù)m1(4)無限序列的自由變量：用u/v/w等表示自由變量(5)無限序列的約束變量：用x/y/z等表示約束變量(6)聯(lián)結(jié)詞：(7)量詞： 、(8)標(biāo)點：左右括號、逗號 ( ) , 一階邏輯：描述對象和關(guān)系的陳述性、合成性的形式語言第3章 邏輯系統(tǒng)27 L的項：一階語言中的一個符號是項t，當(dāng)且僅當(dāng)它能通過有限次使用下述步驟生成：(1)個體常量、自由變量是項；(2)如果t1tn是項，且f是n元函數(shù)，則f(

13、t1tn)是項 L的原子公式：一階語言中的一個表達式是一個原子公式，當(dāng)且僅當(dāng)它有如下2種形式：(1)F(t1tn)，F(xiàn)是n元謂詞，t1tn是項；(2)=(t1,t2)或t1=t2， t1、t2是項第3章 邏輯系統(tǒng)28 L的公式：一階語言中的一個表達式是一個公式，當(dāng)且僅當(dāng)它能通過有限次使用下述步驟生成：(1)原子公式是公式；(2)如果A是公式，則(A)是公式；(3)如果A、B均為公式，則A*B是公式，其中*表示中的任意一個(4)如果A(u)是公式，且x不在A(u)中出現(xiàn)，則x A(x)、x A(x)都是公式第3章 邏輯系統(tǒng)29 一階謂詞公式的例子 數(shù)學(xué)命題的表示：5只被1和5整除 設(shè)Q(x,y)

14、表示x被y整除，N(x)表示x是自然數(shù) x(Q(5,x)N(5)N(1) 自然語言語句的表示：他不能在所有時刻欺騙所有人 設(shè)F(x)表示“x是人”/G(x)“x是一個時刻”/H(x,y)“他能在y時刻欺騙x” x y (F(x)G(y) H(x,y) 或者 xy(H(x,y)F(x)G(y) 第3章 邏輯系統(tǒng)30 一階謂詞公式的例子 1 所有人都是要死的 2 有的人活到一百歲以上 在個體域D為人類集合時，可符號化為：1 x P(x), 其中P(x)表示x是要死的2 xQ(x), 其中Q(x)表示x活到一百歲以上 在個體域D是全總個體域時，引入特殊謂詞R(x)表示x是人，可符號化為1 x （R(

15、x)P(x)2 x (R(x) Q(x) 第3章 邏輯系統(tǒng)313.3 邏輯推理舉例 wumpus世界第3章 邏輯系統(tǒng)32 Wumpus是一個早期電腦游戲中的怪物 Agent感知： 陷阱旁邊有微風(fēng)breeze 怪獸旁邊有惡臭stench 金子閃閃發(fā)光glitter 感覺墻的反彈 陷阱和怪物的位置隨機生成第3章 邏輯系統(tǒng)stenchBreezePitWumpus(Monster)BreezeStenchGoldPitBreezestenchBreezeAgentBreezePitBreeze33 Wumpus世界搜索圖示感知用5元組表示感知wumpus, 感知微風(fēng), 感知金光, 感知墻, 感知wu

16、mpus被殺死A=AgentB=BreezeG=Glitter,GoldOK=safe squareP=PitS=StenchV=visitedW=wumpusN=None1,42,43,44,41,32,33,34,31,2 OK2,23,24,21,1 A OK2,1 OK3,14,1第3章 邏輯系統(tǒng)1,42,43,44,41,32,33,34,31,2OK2,2P?3,24,21,1VOK2,1 ABOK3,1P?4,1 (a) N,N,N,N,N(b) N,B,N,N,N341,42,43,44,41,3W!2,33,34,31,2 ASOK2,2OK3,24,21,1VOK2,1 B

17、VOK3,1P!4,1第3章 邏輯系統(tǒng)1,42,4P？3,44,41,3W!2,3 AB S G3,3P？4,31,2 S VOK2,2VOK3,24,21,1VOK2,1 BVOK3,1P!4,1A=AgentB=BreezeG=Glitter,GoldOK=safe squareP=PitS=StenchV=visitedW=wumpusN=None (c) S,N,N,N,N (d) S,B,G,N,N35 一個簡單的知識庫：只考慮陷阱的情況 Pi,j=T i,j中有陷阱，記為Pi,j Bi,j=T i,j中有微風(fēng)，記為Bi,j 規(guī)則如下： R1P1,1 R2B1,1P1,2P2,1 R

18、3B2,1P1,1P2,2P3,1 R4B1,1 R5B2,1第3章 邏輯系統(tǒng)36 分離規(guī)則 與消去 邏輯等價(雙向蘊涵消去), 第3章 邏輯系統(tǒng)()()()()37 用R1R5規(guī)則和推理模式證明：1,2和2,1中沒有陷阱，即P1,2和P2,1 證明： 從R2開始 R6(B1,1(P1,2P2,1)(P1,2P2,1)B1,1)R2雙向蘊涵消去 R7(P1,2P2,1)B1,1R6與消去 R8B1,1(P1,2P2,1)逆否命題邏輯等價 R9(P1,2P2,1)R4/R8分離規(guī)則 R10(結(jié)果) P1,2P2,1迪摩根定律第3章 邏輯系統(tǒng)383.4 邏輯智能體的推理策略邏輯智能體構(gòu)造Horn子

19、句置換與合一前向鏈接算法 / 后向鏈接算法第3章 邏輯系統(tǒng)39 以一階謂詞演算為核心的邏輯系統(tǒng)是典型的邏輯智能體 系統(tǒng)的基礎(chǔ)是一階語言，由此構(gòu)造知識庫 一般構(gòu)造知識庫(知識工程)的過程包括： 確定任務(wù) 收集相關(guān)知識 確定謂詞、函數(shù)和常量詞匯表第3章 邏輯系統(tǒng)40 對領(lǐng)域(論域)的通用知識進行編碼 對特定問題實例的描述進行編碼 查詢提交、推理、給出答案 調(diào)試知識庫 如果采用一階語言的特殊形式確定子句Horn子句，可獲得高效推理第3章 邏輯系統(tǒng)41 Horn子句(Horn Clause)：是一類至多只有一個正文字的子句(子句=文字的析取式) 例子: ABC (注意：這是一般公式ABC的變形) Ho

20、rn子句稱為確定子句, 其中正文字稱為子句的頭, 負文字構(gòu)成子句的體第3章 邏輯系統(tǒng)42 只有一個正文字的約束具有重要意義: 每個Horn子句實際上都是一個蘊涵式的變形, 實際知識庫中常常使用這樣易懂的形式 Horn子句的推理可以使用前向鏈接和后向鏈接算法 用Horn子句判定蘊涵所需時間與數(shù)據(jù)庫成線性關(guān)系 最重要的是最后一個性質(zhì)第3章 邏輯系統(tǒng)43 簡要介紹2種推理算法簡單的前向鏈接算法和簡單的后向鏈接算法,結(jié)合一個例子說明算法的應(yīng)用 一階推理規(guī)則一般化分離規(guī)則(Generalized Modus Ponens) 對于原子語句pi, pi, q, 存在置換,使得(pi)= (pi), 對所有i

21、都成立, 則第3章 邏輯系統(tǒng))().( , .11qqppppnn44 置換(或代換)：設(shè)x1xn是n個變量，且各不相同，t1tn是n個項(常量、變量、函數(shù))，tixi，則有限序列t1/x1, t2/x2 tn/xn稱為一個置換 置換乘積(合成)：設(shè)和是2個置換，則先后作用于公式或項，稱為置換乘積，用表示。 通過相關(guān)的置換,使不同的一階公式成為一樣的，這個過程稱為合一第3章 邏輯系統(tǒng)45 合一置換：設(shè)有一組謂詞公式E1Ek和置換，使E1=E2=Ek,則稱為合一置換，E1Ek稱為可合一的 / 合一置換也叫通代 最一般合一置換(最廣通代)：如果和都是公式組E1Ek的合一置換，且有置換存在，使得=，

22、則稱為公式組E1Ek的最一般合一置換，記為mgu (most general unification)第3章 邏輯系統(tǒng)46 有子句 x King(x) Greedy(x) Evil(x) King(John) Greedy(John) 則做置換 =x/John, 用一般化分離規(guī)則可得: q=Evil(John)第3章 邏輯系統(tǒng)47 對于合一UNIFY, 合一的結(jié)果是一個置換, 如: UNIFY(Know(John, x), Know(John, Jane) =x/Jane UNIFY(Know(John, x), Know(y, Mary) =x/Mary, y/John 但是UNIFY(K(

23、John, x), K(x, Jane)=FAIL, 原因是x不能同時選取2個值 詳細的合一算法將在第4章介紹第3章 邏輯系統(tǒng)48 問題描述: 美國法律規(guī)定：美國人(American)賣武器(weapon)給敵對國家(hostile)是犯罪的(criminal). 美國的敵國Nono有一些導(dǎo)彈(missile)，所有這些導(dǎo)彈是West上校賣給他們的，而West上校是一個美國人 證明：West是犯罪的第3章 邏輯系統(tǒng)49 用確定子句表示上述內(nèi)容 美國人賣武器給敵對國家是犯罪的American(x) Weapon(y) Sell(x,y,z) Hostile(z) Criminal(x)1 Non

24、o有一些導(dǎo)彈x Own(Nono, x) Missile(x) 消去其中的存在量詞，引入新常量，得到2個原子公式(正文字)Own(Nono, M1) 4Missile(M1) 5第3章 邏輯系統(tǒng)50 所有該國導(dǎo)彈都是West上校出售的Missile(y) Own(Nono, y)Sell(West, y, Nono) 2 導(dǎo)彈是武器Missile(y) Weapon(y)3 其它陳述：美國人West American(West)6敵國 Nono Hostile(Nono)7 上述描述放入知識庫：13為確定子句(上述原始形式均可以化為原子的析取且只有一個正文字)， 47為正文字第3章 邏輯系統(tǒng)5

25、1 前向鏈接算法的推理過程： 從已知事實(知識庫中的原子公式)開始，依次對知識庫中的規(guī)則(以確定子句的形式出現(xiàn))進行置換，檢查規(guī)則前提部分的文字是否全部與知識庫中的事實相匹配 如果是匹配的，則把該條規(guī)則已經(jīng)做過置換的結(jié)論部分添加到知識庫中，如果這個結(jié)論和查詢(既需要推導(dǎo)出的結(jié)論)一致，則推理結(jié)束，獲得證明第3章 邏輯系統(tǒng)52 重復(fù)上述過程，直到獲得證明；或者再沒有新的事實(推出的結(jié)論)加入，則此時推理以證明失敗結(jié)束 約束：要求每次加入知識庫的結(jié)論都是全新的，而不是已知事實的重命名(即謂詞相同只是變量名不同)第3章 邏輯系統(tǒng)53Function FC(KB,) Return a substitu

26、tion or FALSEInputs: KB , a set of first-order definite clauses / , the query = an atomlocal variables : new, the new rules inferred on each iterationrepeat until new is empty newfor each rule r (in the form of define clause) in KB do for each such that (p1pn)= (p1pn)get (q)=q if q is new (satisfied

27、 the constraint) then do add q to new UNIFY(q, ) If is not fail then return add new to KBreturn false 第3章 邏輯系統(tǒng)54第3章 邏輯系統(tǒng) 使用前向鏈接算法對前面的例子進行推理 用知識庫中的事實(即47)依次對知識庫中的各個子句進行置換操作并用推理規(guī)則獲得新的文字 第一次循環(huán)體執(zhí)行： 子句1前提部分未獲滿足(為什么？) 子句2使用置換x/M1, 則可得Sell(West, M1, Nono)8 子句3使用置換x/M1，則可得Weapon(M1)9American(x) Weapon(y) Se

28、ll(x,y,z) Hostile(z) Criminal(x) 1Missile(y) Own(Nono, y)Sell(West, y, Nono) 2Missile(y) Weapon(y)3Own(Nono, M1) 4Missile(M1) 5American(West)6Hostile(Nono) 755第3章 邏輯系統(tǒng) 此時new中為89，為原知識庫所未有，將它們添加到知識庫中 第二次循環(huán)體執(zhí)行： 再次循環(huán)時new首先清空 子句1置換x/West, y/M1, z/Nono得到Criminal(West)10 添加到new中，與查詢進行合一測試，一致則返回 / 算法結(jié)束56第3章

29、 邏輯系統(tǒng)Criminal(West)Weapon(M1)Sells(West,M1,Nono)Hostile(Nono)American(West)Missile(M1)Owns(Nono,M1)Enemy(Nono,America)57 算法的推理過程是： 選取棧當(dāng)中的第一個目標(biāo)，在知識庫中尋找子句的頭(即結(jié)論部分)能與目標(biāo)合一的每個子句 每個這樣的子句創(chuàng)建了一個遞歸調(diào)用過程，在這個遞歸調(diào)用過程中子句的前提(子句的體)被加入到目標(biāo)棧當(dāng)中 當(dāng)棧中所有目標(biāo)都得到匹配，則當(dāng)前的證明分支是成功的 注意：事實是指有頭沒有體的子句(正文字)第3章 邏輯系統(tǒng)58 原始查詢(既要證明的結(jié)論)以目標(biāo)列表的形

30、式出現(xiàn)，開始時列表中只有一個元素 列表的操作相當(dāng)于棧，是一個遞歸過程(如下)即深度優(yōu)先的搜索過程 推理過程是從結(jié)論(子句的頭)開始，找到匹配的頭就擴展這個頭所在的規(guī)則體；擴展部分又作為頭繼續(xù)擴展，直到全部原子均與事實相匹配 比較：正向=事實結(jié)論/反向=結(jié)論事實第3章 邏輯系統(tǒng)59Function BC(KB, goals, ) returns a set of substitutionsInputs: KB, goals=a list of conjuncts forming a query ( already applied), =the current substitution (init

31、ial=)local variables: answers=a set of substitutions (initial=)if goals is empty then return q=(FIRST(goals)(初始為空，遞歸以后不空)for each rule r (in the form of define clause) in KB and =UNIFY(q, q) succeeds new_goal=p1, , pn as REST(goals) answers=BC(KB, new_goal, )answersreturn answers第3章 邏輯系統(tǒng)60 在算法中answe

32、rs作為存放置換的數(shù)據(jù)結(jié)構(gòu)，返回一系列置換操作，這些操作說明了反向鏈接算法獲取證明的過程 在算法中包括了置換的合成(或者寫為Compose(,)，其效果就是依次進行每個置換第3章 邏輯系統(tǒng)61 第一次應(yīng)用算法，對于待證明的目標(biāo)來說，本身就是一個正文字，此時要用這個文字中的常量對合適的規(guī)則(子句的頭與該文字匹配)進行置換 這個置換通過遞歸調(diào)用帶入下一次置換，就得到了合成置換 在本例中有：初始x/West 遞歸x/West, y/M1遞歸x/West, y/M1, z/Nono第3章 邏輯系統(tǒng)62 反向鏈接算法推理過程 目標(biāo)Criminal(West)分解為公式1前提部分的4個文字，即Americ

33、an(West), Weapon(y), Sell(West, y, z), Hostile(z)置換=x/West American(West)和事實相匹配 需要遞歸匹配：Weapon(y), Sell(West, y, z), Hostile(z) Weapon(y)遞歸調(diào)用前=x/West，進入第一次遞歸產(chǎn)生Missile(M1)，此時置換y/M1匹配，遞歸返回復(fù)合=x/West, y/M1第3章 邏輯系統(tǒng)63 再次遞歸調(diào)用Sell(West, M1, z)得到置換=z/Nono，遞歸返回復(fù)合置換x/West, y/ M1, z/Nono 在置換過程中每個變量只能置換一個常量作為約束，減

34、少置換的不定性 此時子目標(biāo)全部匹配，再無新的子目標(biāo)生成，返回置換集合結(jié)束第3章 邏輯系統(tǒng)64第3章 邏輯系統(tǒng)Criminal(West)American(West)Weapon(y)Sells(West,M1,z)Hostile(Nono)Missile(y)Missile(M1)Owns(Nono ,M1)Enemy(Nono,Amerca)z/Nonoy/M165 前向鏈接算法特點：數(shù)據(jù)驅(qū)動 / 是可靠的和完備的 后向鏈接算法特點：目標(biāo)驅(qū)動 / 是可靠的但不是完備的(書中p220/p224) 可以從“是否能找到問題的解”角度考慮不完備性 后向鏈接算法根據(jù)目標(biāo)來進行相關(guān)事實的匹配，對于大規(guī)模

35、的知識庫來說有助于減小搜索空間第3章 邏輯系統(tǒng)663.2 邏輯系統(tǒng)的語法和語義邏輯系統(tǒng)的語法邏輯系統(tǒng)的語義語法和語義之間的關(guān)系第3章 邏輯系統(tǒng)67 邏輯系統(tǒng)(亦稱形式系統(tǒng)Formal System)由5個部分組成： 符號表非空集合，即邏輯(形式)語言如一階語言 項和變量 上全體符號的集合*的子集 公式FORMULA*的子集| 公式和項的交集為空 公理AXIOM 公式FORMULA上的子集 推理規(guī)則RULE 公式上的n元關(guān)系集合 、項TERM、FORMULA稱為FS的組成部分 / AXIOM、RULE稱為FS的推演部分第3章 邏輯系統(tǒng)68 邏輯系統(tǒng)除符號表以外的部分構(gòu)成了邏輯系統(tǒng)的語法 形式推演

36、：定義了公式之間的形式可推演性關(guān)系，它涉及公式的語法結(jié)構(gòu)，其正確性能夠機械地證明 用記號 表示形式可推演關(guān)系，讀作“推出” 用 A表示A是由形式可推演的（或形式可證明的），其中是前提，A是結(jié)論第3章 邏輯系統(tǒng)69 研究命題邏輯的語義，即研究公式(公式集)的真假賦值問題 真假賦值：真假賦值是以所有命題符號的集合為定義域、以真假值1,0為值域的函數(shù)。真假賦值v給公式A指派的值記作Av 可滿足性：是可滿足的，當(dāng)且僅當(dāng)有真假賦值v，使得v=1。此時稱v滿足。第3章 邏輯系統(tǒng)70 的可滿足性蘊涵了中所有公式的可滿足性，但反過來不成立。因為這要求同一個真假賦值滿足所有的公式(并非所有可滿足的公式使用同一個

37、賦值) 重言式和矛盾式 A是重言式(永真式)，當(dāng)且僅當(dāng)對于任意的真假賦值v，Av=1 A是矛盾式(永假式)，當(dāng)且僅當(dāng)對于任意的真假賦值v，Av=0第3章 邏輯系統(tǒng)71 可推導(dǎo)關(guān)系：研究前提的真是否蘊涵結(jié)論的真 引入語義以后對公式進行真假賦值；如果對任意的真假賦值，都有上述關(guān)系，則說明前提和結(jié)論之間存在一種邏輯推論關(guān)系(或稱邏輯蘊涵)第3章 邏輯系統(tǒng)72 邏輯推論：設(shè)、A分別是命題邏輯中的公式集合和公式,A是的邏輯推論，記為 |=A，當(dāng)且僅當(dāng)對于任意真假賦值v，v=1蘊涵Av=1。 |=可讀作“邏輯地蘊涵”，|=是前提和結(jié)論A之間的關(guān)系 邏輯推論的證明 要證明|=A時，即要證明對于任何真假賦值v

38、，如果v=1則Av=1 (通常使用反證法)第3章 邏輯系統(tǒng)73 一階語言的語義：一階語言的解釋包括一個論域和一個函數(shù) 函數(shù)把一階語言中的個體符號映射到論域中的個體 n元關(guān)系符號(即謂詞)映射到論域上的n元關(guān)系 m元函數(shù)符號映射到論域上的m元全函數(shù) 以上組成了該論域中對一階語言的解釋第3章 邏輯系統(tǒng)74 賦值：一階語言L的賦值v包括一個論域D和一個函數(shù)(記作v) L中所有個體符號a為定義域，其賦值v(a)或av 關(guān)系符號F的賦值v(F)或Fv 函數(shù)符號f的賦值v(f)或fv 自由變量符號u的賦值v(u)或uv 則有(1)av, uvD(2)FvDn(3)fv: DmD第3章 邏輯系統(tǒng)75 公式的

39、真假值：一階語言的公式在以D為論域的賦值之下，其真假值可以遞歸定義 一階邏輯的邏輯推論：設(shè)、A分別是一階語言的公式集和公式，A是的邏輯推論，記作|=A，當(dāng)且僅當(dāng)對于任何賦值v，v=1蘊涵Av=1 一階邏輯的邏輯推論證明方法類似于命題邏輯，常用反證法。但對于否證邏輯推論，則需要構(gòu)造賦值所需的論域。確定論域時，關(guān)鍵在于論域的大小第3章 邏輯系統(tǒng)76 在經(jīng)典邏輯的形式系統(tǒng)中，形式推演是語法概念，邏輯推論是語義概念 形式系統(tǒng)的整體特征：是在形式系統(tǒng)引入語義以后，研究對于任何一階語言的公式集和公式A在何種賦值的條件下，其結(jié)果是否為真即研究形式推演與邏輯推論之間的關(guān)系即語法和語義之間的關(guān)系 賦值的條件：

40、給定某個賦值可滿足性 給定任意賦值有效性第3章 邏輯系統(tǒng)77 不加證明地給出有關(guān)定義和定理 可滿足性一階邏輯公式集合是可滿足的，當(dāng)且僅當(dāng)有(以某個不空集為論域)賦值v，使得v=1 / 當(dāng)v=1時，稱v滿足 反過來，不可滿足性就是對任意論域上的任意賦值都有v=0 第3章 邏輯系統(tǒng)78 有效性：一階邏輯公式A是有效的，當(dāng)且僅當(dāng)對于(以任何不空集為論域)任何賦值v，Av=1 / 有效性也稱為普遍有效性 / 教科書中稱為合法性第3章 邏輯系統(tǒng)79 (關(guān)于命題的)定理: (1)A是可滿足的，當(dāng)且僅當(dāng)A是不有效的；(2)A是有效的，當(dāng)且僅當(dāng)A是不可滿足的。 (關(guān)于一階的)定理: (1)A(u1,un)是可

41、滿足的，當(dāng)且僅當(dāng)x1. xn A(x1,xn)是可滿足的 (2)A(u1,un)是有效的，當(dāng)且僅當(dāng)x1. xn A(x1,xn)是有效的第3章 邏輯系統(tǒng)80 對于任何一階語言的公式集和公式A， A|=A表示：凡是形式可推演性所反映的前提和結(jié)論之間的關(guān)系，在非形式的推理中都是成立的，即形式可推演性對于反映非形式的推理是可靠的，此即可靠性定理(或者稱合理性) |=A A表示：凡是在非形式推理中成立的前提和結(jié)論之間的關(guān)系，形式可推演性都是能夠反映的，即形式可推演性在反映非形式推理時沒有遺漏，此即完備性定理第3章 邏輯系統(tǒng)81作業(yè)1 掃雷游戲，和wumpus世界有著密切的聯(lián)系，N個方格的矩形網(wǎng)絡(luò)，M個

42、隨機分布的地雷。通過在每個已經(jīng)探尋過的方格內(nèi)顯示直接以及對交相鄰的地雷數(shù)量來指示地雷的存在，目標(biāo)是探尋每個沒有地雷的方格。 （1） Xi,j為真當(dāng)且僅當(dāng)方格i,j中包含地雷，用一個包括Xi,j命題的一些邏輯組合的語句表示i,j周圍恰好有1顆地雷的斷言。 （2） 如何構(gòu)造一個合取范式語句，并根據(jù)（1）把你的斷言推廣為：n個相鄰的方格中有k個方格包含地雷。82 Stuart Russell / Peter Norvig: AIMA 第7章 /第8章 /第9章 陸汝鈐 編著: 人工智能(上冊) 第1章 陸鐘萬，面向計算機科學(xué)的數(shù)理邏輯，科學(xué)出版社，1998年1月第1版 朱梧木賈、肖奚安，數(shù)理邏輯引論

43、，南京大學(xué)出版社，1995年5月第1版 王元元，計算機科學(xué)中的邏輯學(xué)，科學(xué)出版社，1989年9月第1版第3章 邏輯系統(tǒng)83附錄 形式系統(tǒng)簡介F1 形式系統(tǒng)和形式推演F2 形式系統(tǒng)的語義F3 形式系統(tǒng)的整體特征第3章 邏輯系統(tǒng)84F1 形式系統(tǒng)定義和形式推演第3章 邏輯系統(tǒng)85 邏輯的形式系統(tǒng)的定義 一個形式系統(tǒng)Formal System由5個部分組成：(1)符號表，非空集合，即形式語言(如Lp和L)；(2)上全體符號的集合*的一個子集TERM，其 元 素 稱 為 F S 的 項 ； T E R M 有 子 集VARIABLE，其元素稱為變量；(3)*的一個子集FORMULA，其元素稱為FS的公

44、式；FORMULA有子集ATOM，其元素稱為原子公式；TERMFORMULA=；第3章 邏輯系統(tǒng)86(4)FORMULA的一個子集AXIOM，其元素稱為FS的公理；(5)FORMULA上的n元關(guān)系集合RULE，其元素稱為FS的推理規(guī)則。 其中、TERM、FORMULA稱為FS的組成部分，AXIOM、RULE稱為FS的推演部分 公理推演系統(tǒng)包括AXIOM，而自然推演系統(tǒng)只包括推理規(guī)則第3章 邏輯系統(tǒng)87 對象語言和元語言：作為被研究對象的語言稱為對象語言，用以研究對象語言的語言稱為元語言 例子：用漢語研究英語語法，則英語是對象語言，漢語是元語言 數(shù)理邏輯中的形式系統(tǒng)各有其自身的形式語言如Lp和L

45、，這些是被研究的對象，因而是對象語言；但為了研究這些形式系統(tǒng)，又必須使用某種語言，那么這種語言便是元語言第3章 邏輯系統(tǒng)88 如：“鳥正在飛翔”描述對象語言；“命題鳥正在飛翔真”對上句的評論元語言。 形式系統(tǒng)的對象語言，其中的符號既是對客觀對象的抽象，用于研究客觀對象;同時又是一種符號客體，是被研究的對象第3章 邏輯系統(tǒng)89 形式系統(tǒng)的元語言包括： 對形式系統(tǒng)中組成成分的稱謂項、公式、公理等 邏輯術(shù)語如果-那么、當(dāng)且僅當(dāng)、存在、所有等 對形式系統(tǒng)性質(zhì)（整體特征）的描述如一致性、完備性、可判定性等，該部分最重要 元語言中使用的符號：自然語言（如漢語）和一些被引進的符號，如：、|= 等 未經(jīng)解釋的

46、形式語言可以沒有含義，但元語言必須有其具體含義。第3章 邏輯系統(tǒng)90 元理論是關(guān)于形式系統(tǒng)的理論，包括三部分內(nèi)容： 關(guān)于形式系統(tǒng)語法(syntax)的研究，不涉及具體意義的符號體系，研究符號串的推演，即形式推演； 關(guān)于形式系統(tǒng)語義(semantics)的研究，研究形式系統(tǒng)在被作出各種解釋時的性質(zhì)； 關(guān)于形式系統(tǒng)語法和語義關(guān)系的研究，特別是形式系統(tǒng)的性質(zhì)，如：合理性、完備性等。第3章 邏輯系統(tǒng)91 形式推演：定義了公式之間的形式可推演性關(guān)系，它涉及公式的語法結(jié)構(gòu)，其正確性能夠機械地證明 用記號 表示形式可推演關(guān)系，讀作“推出” 用 A表示A是由形式可推演的（或形式可證明的），其中是前提，A是結(jié)論

47、 記號不是形式語言中的符號， A也不是形式語言中的公式，而是元語言中的命題第3章 邏輯系統(tǒng)92 形式推演由形式推演的規(guī)則定義 命題邏輯中有一些常用的推演規(guī)則(規(guī)則模式) 肯定前提if A then A () 增加前提if A then , A (+) 自反A A (Ref) 傳遞if A then A ()第3章 邏輯系統(tǒng)93 消去(反證律)if , A B & , AB then A(-) 引入(歸謬律) if , A B & , A B then A(+) 消去if AB, Athen B(-) 引入if , A B then AB(+)第3章 邏輯系統(tǒng)94 消去if AB

48、 then A, B(-) 引入if A, B then AB(+) 消去if , A C & ,B C then ,AB C (-) 引入if A then AB, BA(+)第3章 邏輯系統(tǒng)95 消去if AB, A then Bif AB, B then A() 引入if , A B & , B A then AB (+) 通過連接詞的增減或變形，實現(xiàn)公式的變換 常用AB AB第3章 邏輯系統(tǒng)96 (命題邏輯)形式可推演性：在命題邏輯中，A是由可形式推演的(或形式可證明的)，記為A，當(dāng)且僅當(dāng)A能通過有限次應(yīng)用命題邏輯的形式推演規(guī)則生成 即A成立，當(dāng)且僅當(dāng)存在有限序列使得

49、1A1，2A2，nAn 中的每一項均由某個形式推導(dǎo)規(guī)則生成,且nAn 就是A即n=,An=A第3章 邏輯系統(tǒng)97 用 A表示A不成立 用A|-|B表示左右兩邊的公式可以互相推出，稱其為語法等值公式或等值公式 建立在上述形式推演規(guī)則基礎(chǔ)上的形式推演系統(tǒng)稱為自然推演(演繹)系統(tǒng)第3章 邏輯系統(tǒng)98 命題邏輯中的形式推演規(guī)則都包括在一階邏輯當(dāng)中，但是其中出現(xiàn)的公式是一階語言中的公式，另外增加了關(guān)于量詞的規(guī)則 (一階邏輯)形式可推演性：在一階邏輯中，A是由可形式推演的(或形式可證明的)，記為A，當(dāng)且僅當(dāng)A能通過有限次應(yīng)用一階邏輯的形式推演規(guī)則生成 形式推演的例子可以參考本章后面列出的3本關(guān)于邏輯的教科

50、書第3章 邏輯系統(tǒng)99F2 形式系統(tǒng)的語義第3章 邏輯系統(tǒng)100 語義即對形式語言進行解釋 研究可推導(dǎo)性即形式推演()時不考慮作為前提和結(jié)論的命題的內(nèi)容，只考慮命題真假并由此確定前提的真是否蘊涵結(jié)論的真，即前提和結(jié)論之間是否有可推導(dǎo)關(guān)系(語法) 研究形式系統(tǒng)的語義時，對形式系統(tǒng)賦予研究對象的集合即論域；用論域中的個體對象、對象之上的運算(函數(shù))、對象之間的關(guān)系(謂詞)去解釋形式系統(tǒng)中的符號，稱作指稱denote 指稱語義學(xué)第3章 邏輯系統(tǒng)101 賦予形式系統(tǒng)的論域及解釋稱為形式系統(tǒng)的語義結(jié)構(gòu)，簡稱結(jié)構(gòu)(structure)/ 結(jié)構(gòu)及其在該結(jié)構(gòu)下公式所取真值的規(guī)定，稱為形式系統(tǒng)的指稱語義(den

51、otational semantics)第3章 邏輯系統(tǒng)102 研究命題邏輯的語義，即研究公式(公式集)的真假賦值問題 真假賦值：真假賦值是以所有命題符號的集合為定義域，以真假值1,0為值域的函數(shù)。真假賦值v給公式A指派的值記作Av 可滿足性：是可滿足的，當(dāng)且僅當(dāng)有真假賦值v，使得v=1。此時稱v滿足。第3章 邏輯系統(tǒng)103 的可滿足性蘊涵了中所有公式的可滿足性，但反過來不成立。因為這要求同一個真假賦值滿足所有的公式(并非所有可滿足的公式使用同一個賦值) 重言式和矛盾式 A是重言式(永真式)，當(dāng)且僅當(dāng)對于任意的真假賦值v，Av=1 A是矛盾式(永假式)，當(dāng)且僅當(dāng)對于任意的真假賦值v，Av=0第

52、3章 邏輯系統(tǒng)104 一個命題公式是重言式或者是矛盾式或者兩者都不是，需要進行判定。判定方法可通過構(gòu)造真假值表方法或采用樹形分支的方法來判定 可推導(dǎo)關(guān)系研究前提的真是否蘊涵結(jié)論的真，引入語義以后對公式進行真假賦值；如果對任意的真假賦值，都有上述關(guān)系，則說明前提和結(jié)論之間存在一種邏輯推論關(guān)系(或稱邏輯蘊涵)。此時對關(guān)系陳述得也更精確第3章 邏輯系統(tǒng)105 邏輯推論：設(shè)、A分別是命題邏輯中的公式集合和公式,A是的邏輯推論，記為 A，當(dāng)且僅當(dāng)對于任意真假賦值v，v=1蘊涵Av=1。 |=可讀作“邏輯地蘊涵”，|=是前提和結(jié)論A之間的關(guān)系,但不是命題語言中的符號，|=A是元語言中的命題第3章 邏輯系統(tǒng)

53、106 邏輯推論的證明 要證明|=A時，即要證明對于任何真假賦值v，如果v=1則Av=1 但任意的真假賦值難于驗證 故使用反證法，假設(shè)|A，即存在一個真假賦值v，使得v=1且Av=0，由此而產(chǎn)生矛盾，即肯定了 |=A第3章 邏輯系統(tǒng)107 一階語言的語義：一階語言的解釋包括一個論域和一個函數(shù)，函數(shù)把一階語言中的個體符號、n元關(guān)系符號(即謂詞)、m元函數(shù)符號分別映射到論域中的個體、論域上的n元關(guān)系和m元全函數(shù)，是在這個論域中對一階語言的解釋第3章 邏輯系統(tǒng)108 如果n元關(guān)系符號和m元函數(shù)中不含自由變量，其項為論域中的個體ai，則原子公式F(t1,tn)被解釋為：a1,an有R關(guān)系；項f(t1,tn)被解釋為論域中的個體f(a1,an) 對于含有自由變量的函數(shù)(項)和公式，則分別被解釋為論域上的m元函數(shù)和n元命題函數(shù)，它們經(jīng)過解釋，再給其中的自由變量符號指派論域中的某些個體，就得到論域中個體作為其值、真或假的命題作為其真假值第3章 邏輯系統(tǒng)109 賦值：一階語言L的賦值v包括一個論域和一個函數(shù)，記作v，以L中所有個體符號a、關(guān)系符號F、函數(shù)符號f和自由變量符號u構(gòu)成的集合為定義域，且分別把v(a)、v(F)、v(f)、v(u)寫作av、Fv、f