人工智能7課題

第三局部學(xué)問和推理

命題規(guī)律

謂詞規(guī)律

學(xué)問表示方法第七章規(guī)律智能體7.1基于學(xué)問的智能體7.2wumpus世界7.3規(guī)律7.4命題規(guī)律7.5命題規(guī)律的推理模式7.6基于命題規(guī)律的智能體基于學(xué)問的智能體學(xué)問庫(Knowledgebase，KB)：語句的集合TELL：將新語句添加到學(xué)問庫，告知學(xué)問庫感知的信息記錄選擇的行動ASK：查詢學(xué)問庫，以獲得應(yīng)當(dāng)執(zhí)行的行動Wumpus世界性能度量：金子+1000，死亡-1000每次行動-1，用掉箭-10環(huán)境：4*4網(wǎng)格，金子、陷阱、wumpus傳感器：Stench,Breeze,Glitter,Bump,Scream執(zhí)行器：向前移動，左、右轉(zhuǎn)90度，Grab，shoot，局部可觀看、確定性的、連續(xù)式的、靜態(tài)的、離散的、單智能體環(huán)境。[None,None,None,None,None][None,Breeze,None,None,None][Stench,None,None,None,None][None,None,None,None,None][Stench,Breeze,Glitter,None,None]規(guī)律規(guī)律的歷史Aristotle：規(guī)律學(xué)Leibnitz：數(shù)理規(guī)律Gottlobfrege:一階謂詞演算系統(tǒng)，《符號論》(19世紀(jì))20世紀(jì)30年月，數(shù)理規(guī)律廣泛進(jìn)展規(guī)律系統(tǒng)一個規(guī)律系統(tǒng)是定義語言和它的含義的方法。規(guī)律符號集合：在全部該規(guī)律的規(guī)律理論中均消失的符號非規(guī)律符號集合：不同的規(guī)律理論中消失的不同的符號語句規(guī)章：定義什么樣的符號串是有意義的語義規(guī)章：定義符號串的語義推理規(guī)章、公理和證明規(guī)律和程序語言的比照邏輯系統(tǒng)程序語言邏輯符號保留字或符號非邏輯符號用戶自定義的符號(變量名，函數(shù)名等)語句規(guī)則構(gòu)造一個程序的語句規(guī)則語義規(guī)則定義程序做什么的規(guī)則推理規(guī)則、公理和證明無語義x+2≥y在x=7,y=1的世界中為真x+2≥y在x=0,y=6的世界中為假可能世界—模型m是α的一個模型，表示語句α在模型m中為真規(guī)律推理--蘊(yùn)含關(guān)系〔entailment〕α╞β，當(dāng)且僅當(dāng)在α為真的模型中，β也為真〔當(dāng)α為真，β必定為真〕 即β的真值包含于α的真值中例如：x+y=4蘊(yùn)含4=x+yKB╞α一個語句規(guī)律上跟隨另一個語句而消失模型檢驗(yàn)3個方格中的每個可能包含或不包含陷阱，則存在8個可能的模型與智能體所知內(nèi)容相沖突的模型中，KB為假。α1：[1,2]無陷阱，α2：[2,2]無陷阱模型檢驗(yàn)依據(jù)[1,1]無微風(fēng)，則在任意[1,2]有陷阱的模型中，KB為假僅3個模型使得KB為真。α1：[1,2]無陷阱KB╞α1模型檢驗(yàn)KB╞α2α2：[2,2]無陷阱模型檢驗(yàn)?zāi)Ｐ蜋z驗(yàn):枚舉出全部可能的模型用于檢驗(yàn)在KB中為真的全部模型中α為真。推理的牢靠性和完備性KB├iα：α通過推理算法i從KB中導(dǎo)出，推理算法i從KB中導(dǎo)出α推理算法i是牢靠的：假設(shè)KB├iα，則KB╞α推理算法i是完備的：假設(shè)KB╞α，則KB├iα命題規(guī)律命題：能夠區(qū)分真假的陳述句。 例如：1+1=2雪是綠色的昆明是云南的省會快點(diǎn)走吧!到哪去？一個原子命題可以用字母表示(命題符號)。命題規(guī)律是由命題符號和規(guī)律連接符組成。原子命題：一個命題，且是不能再進(jìn)一步分解成更簡潔語句。是命題的根本單位。規(guī)律連接符合取式：p與q，記為p∧q析取式：p或q，記為pq蘊(yùn)含式：假設(shè)p則q，記為pq等價式：p當(dāng)且僅當(dāng)q，記為pq否認(rèn)式：非，p優(yōu)先級：，∧，，，命題表示將陳述句轉(zhuǎn)化為命題公式：例如：設(shè)“下雨”為p，“騎車上班”為q1.“只要不下雨，我就騎自行車上班”。p是q的充分條件，可得命題公式：p

q2.“只有不下雨，我才騎自行車上班”。p是q的必要條件，可得命題公式：q

p3.“應(yīng)屆畢業(yè)生，得過國家級競賽一等獎或全班排名第一，保送爭論生”設(shè)：p“應(yīng)屆畢業(yè)生”，q“保送爭論生”，r“得過國家級競賽一等獎”，t“全班排名第一”則有命題公式：p∧〔rt〕qTrue永真命題，F(xiàn)alse永假命題析取范式：僅由有限個簡潔合取式組成的析取式p〔pq〕〔pq〕合取范式：僅由有限個簡潔析取式組成的合取式p〔pq〕〔pq〕語義例如：某模型下，P1,2 P2,2 P3,1

假 真

假語義定義了用于判定關(guān)于特定模型的語句真值的規(guī)章規(guī)律連接符的真值表：指定了復(fù)合句在其組成局部的真值的每種可能賦值狀況下的真值。

P1,2

(P2,2

P3,1)=true

(true

false)=true

true=trueWumpus世界的學(xué)問庫Pi,j

：在[i,j]有陷阱Bi,j

：在[i,j]有微風(fēng)

P1,1

B1,1B2,1陷阱使得其鄰域方格有微風(fēng)B1,1

(P1,2

P2,1)B2,1

(P1,1

P2,2

P3,1)推理的根本概念推理：從事實(shí)動身，運(yùn)用已把握的學(xué)問，推導(dǎo)出其中蘊(yùn)含的事實(shí)性結(jié)論或歸納出某些新的結(jié)論的過程。推理所用的事實(shí)：初始證據(jù)；中間結(jié)論。初始證據(jù)推理機(jī)結(jié)論學(xué)問庫目標(biāo)是推斷某些語句x，kB|=x是否成立。模型檢驗(yàn)：枚舉出模型，驗(yàn)證x在KB為真的每個模型中為真推理真值表α1：

P1,2α2：

P2,2真值表枚舉算法真值表枚舉算法，是牢靠的、完備的n個符號，存在2n個模型，時間簡單度O(2n)用于命題規(guī)律的有效模型檢驗(yàn)推理算法包括回溯(DPLL算法)和局部搜尋方法〔WALKSAT算法〕。推理方法演繹推理：從的一般性學(xué)問動身，推理出適合于某些個別狀況的結(jié)論的過程。歸納推理：從大量的特殊事例動身，歸納出一般性結(jié)論的推理過程。默認(rèn)推理：在學(xué)問不完全的狀況下假設(shè)某些條件已經(jīng)具備所進(jìn)展的推理。推理的不確定性及其單調(diào)性確定性推理：推理所用的證據(jù)、學(xué)問及結(jié)論都是可以準(zhǔn)確表示的，其真值不為真就為假，不會有第三種狀況消失。不確定性推理：推理所用的證據(jù)、學(xué)問及結(jié)論都是不確定的，都是不行以準(zhǔn)確表示的，其真值位于真和假之間。單調(diào)性推理：由于新學(xué)問的參加和使用，使推理所得到的結(jié)論會越來越接近目標(biāo)。非單調(diào)性推理：推理過程中某些新學(xué)問的參加和使用，不但沒有加強(qiáng)已經(jīng)推出的結(jié)論，反而會否認(rèn)原來已推出的結(jié)論。交換律：p∧q≡q∧pp∨q≡q∨p結(jié)合律：(p∨q)∨r≡p∨(q∨r)(p∧q)∧r≡p∧(q∧r)安排率：p∨(q∧r)≡(p∨q)∧(p∨r)p∧(q∨r)≡(p∧q)∨(p∧r)根本等值式：α≡?

，當(dāng)且僅當(dāng)α╞β

且β╞α摩根律：(p∧q)≡p∨q(p∨q)≡p∧q吸取律：p∨(p∧q)≡pp∧(p∨q)≡p同一律：p∨0≡pp∧1≡p蘊(yùn)含等值式：pq≡p∨q〔蘊(yùn)含消去〕假言易位式：pq≡qp〔逆否命題〕雙向蘊(yùn)含消去：pq≡(pq)∧(qp)根本等值式：合法性和可滿足性例如：True，AA, AA, (A(AB))B假設(shè)α至少有一個成真賦值，則稱α為可滿足的e.g.,AB, C假設(shè)α無成真賦值，則稱α為不行滿足的，稱沖突式或永假式，例如：AA假設(shè)語句α無成假賦值，則稱α是合法的，稱重言式或永真式，α是合法的，當(dāng)且僅當(dāng)α是不行滿足的α是可滿足的，當(dāng)且僅當(dāng)α是不合法的反證法〔歸謬〕：KB╞α當(dāng)且僅當(dāng)(KBα)是不行滿足的推理規(guī)章規(guī)律等價分別規(guī)章：αβ,αβ例如，〔WumpusAheadWumpusAlive)shoot和〔WumpusAheadWumpusAlive)，可推導(dǎo)出shoot與消去〔合取式推導(dǎo)出任何合取子句〕：αβα例如：WumpusAheadWumpusAlive可推導(dǎo)出WumpusAlive推理規(guī)章的應(yīng)用序列--證明1.雙向蘊(yùn)含消去：αβ代換為(αβ)(βα).由語句(4)得：(B1,1(P1,2P2,1))((P1,2P2,1)B1,1)--(6)

2.語句〔6〕與消去：((P1,2P2,1)B1,1)--(7)語句(7)再依據(jù)αβ≡βα〔逆否命題〕得：(B1,1((P1,2P2,1))--〔8〕3.由語句〔8〕和〔2〕依據(jù)分別規(guī)章得：((P1,2P2,1))--(9)

4.依據(jù)摩根律：P1,2P2,1---〔10〕〔1〕P1,1〔2〕B1,1〔3〕B2,1〔4〕B1,1(P1,2P2,1)〔5〕B2,1(P1,1P2,2P3,1)歸結(jié)AB反證法：證明AB是沖突式〔永假式〕建立子句集合取范式：命題、命題或的與例如：p〔pq〕〔pq〕子句集S：合取范式形式下得子命題〔元素〕的集合例如：上述命題公式的子句集S={p,pq,pq}合取范式B1,1(P1,2P2,1)1.消去：αβ替換為(αβ)(βα).(B1,1(P1,2P2,1))((P1,2P2,1)B1,1)2.消去：αβ替換為αβ.(B1,1P1,2P2,1)((P1,2P2,1)B1,1)3.依據(jù)摩根律移入：(B1,1P1,2P2,1)((P1,2P2,1)B1,1)4.依據(jù)安排率:(B1,1P1,2P2,1)(P1,2B1,1)(P2,1B1,1)單元?dú)w結(jié)規(guī)章l1…lk, ml1…li-1li+1…lk其中l(wèi)iandm是互補(bǔ)文字(一個文字是另一個文字的否認(rèn)式).全歸結(jié)規(guī)章l1…lk, m1…mnl1…li-1li+1…lkm1…mj-1mj+1...mn其中l(wèi)i和mj是互補(bǔ)文字歸結(jié)規(guī)章：P1,3P2,2, P2,2P1,3歸并：〔AB〕和〔AB〕歸結(jié)得到AA，最終簡化為Ali

真，則mj

假

(m1

…

mj-1

mj+1

...

mn)真li

假，l1

…

li-1

li+1

…

lk真歸結(jié)規(guī)章的完備性：任何完備的搜尋算法，只使用歸結(jié)規(guī)章，就可以生成命題規(guī)律中被任何學(xué)問庫蘊(yùn)涵的任何結(jié)論。l1

…

lk, m1

…

mnl1

…

li-1

li+1

…

lk

m1

…

mj-1

mj+1

...

mn

歸結(jié)規(guī)章的牢靠性：A為真，無法用歸結(jié)自動生成結(jié)論AB，但可以用歸結(jié)推斷AB是否為真。將命題寫成合取范式求出子句集S對子句集使用歸結(jié)推理規(guī)章歸結(jié)式作為新子句參與歸結(jié)歸結(jié)式為空子句，S是不行滿足的〔沖突〕，原命題成立歸結(jié)過程例如：證明公式〔pq〕〔qp〕證：將待證明公式轉(zhuǎn)化為歸結(jié)命題公式：〔pq〕(qp)將該公式轉(zhuǎn)化為合取范式pq≡p∨q(qp)≡(q∨p)≡qp〔pq〕(qp)≡(p∨q)qp則子句集：p∨q，q，p對子句集中的子句進(jìn)展歸結(jié)：〔1〕p∨q〔2〕q〔3〕p〔4〕q〔1,3歸結(jié)〕〔5〕空〔2,4歸結(jié)〕KB=(B1,1

(P1,2

P2,1))

B1,1α=

P1,2Wumpus世界的歸結(jié)推理(B1,1

(P1,2

P2,1))

B1,1

P1,2

≡(

B1,1

P1,2

P2,1)

(

P1,2

B1,1)

(

P2,1

B1,1)

B1,1

P1,2

前向和反向鏈接霍恩子句：至多只有一個正文字的文字析取式(P1,2B1,1)P2,1P1,2P2,1(B1,1P1,2P2,1)每個霍恩子句都可寫成一個蘊(yùn)涵式：(P1,2B1,1)≡P1,2B1,1沒有正文字的霍恩子句：可寫成結(jié)論為False的蘊(yùn)涵式例如：P1,2P2,1≡〔P1,2P2,1)False確定子句：只有一個正文字，例如：P2,1，斷言一個事實(shí)

使用霍恩子句的推理可在前向鏈接和反向鏈接中進(jìn)展使用霍恩子句判定蘊(yùn)涵需要的時間和數(shù)據(jù)庫大小成線性關(guān)系前向鏈接判定單個命題符號q是否被霍恩子句的學(xué)問庫所蘊(yùn)涵：從學(xué)問庫的事實(shí)(正文字)開頭，假設(shè)蘊(yùn)涵的全部前提，則將其結(jié)論添加到事實(shí)集。直到查詢q被添加或無法進(jìn)展更進(jìn)一步的推理前向鏈接前向鏈接前向鏈接前向鏈接前向鏈接前向鏈接前向鏈接前向鏈接牢靠的完備的前向鏈接中每個推理本質(zhì)上是分別規(guī)章的一個應(yīng)用。從查詢q反向進(jìn)展：查詢q是否是事實(shí)，否則查找學(xué)問庫中能以q為結(jié)論的蘊(yùn)涵，假設(shè)其中某個蘊(yùn)涵的全部前提都能證明為真，則q為真。反向鏈接反向鏈接反向鏈接反向鏈接反向鏈接反向鏈接反向鏈