人工智能7課題課件

人工智能——一種現(xiàn)代方法第三部分

知識和推理命題邏輯謂詞邏輯知識表示方法§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法第七章

邏輯智能體7.1基于知識的智能體7.2wumpus世界7.3邏輯7.4命題邏輯7.5命題邏輯的推理模式7.6基于命題邏輯的智能體§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法基于知識的智能體知識庫(Knowledgebase，KB)：語句的集合TELL：將新語句添加到知識庫，告訴知識庫感知的信息記錄選擇的行動ASK：查詢知識庫，以獲得應(yīng)該執(zhí)行的行動§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法Wumpus世界性能度量：金子+1000，死亡-1000每次行動-1，用掉箭-10環(huán)境：4*4網(wǎng)格，金子、陷阱、wumpus傳感器：Stench,Breeze,Glitter,Bump,Scream部分可觀察、確定性的、延續(xù)式的、靜態(tài)的、離散的、單智能體環(huán)境。執(zhí)行器：向前移動，左、右轉(zhuǎn)90度，Grab，shoot，§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法[None,None,None,None,None]§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法[None,Breeze,None,None,None]§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法[Stench,None,None,None,None]§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法[None,None,None,None,None]§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法[Stench,Breeze,Glitter,None,None]§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法邏輯邏輯的歷史Aristotle：邏輯學(xué)Leibnitz：數(shù)理邏輯Gottlob

frege:一階謂詞演算系統(tǒng)，《符號論》(19世紀(jì))20世紀(jì)30年代，數(shù)理邏輯廣泛發(fā)展§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法邏輯系統(tǒng)一個邏輯系統(tǒng)是定義語言和它的含義的方法。邏輯符號集合：在所有該邏輯的邏輯理論中均出現(xiàn)的符號非邏輯符號集合：不同的邏輯理論中出現(xiàn)的不同的符號語句規(guī)則：定義什么樣的符號串是有意義的語義規(guī)則：定義符號串的語義推理規(guī)則、公理和證明§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法邏輯和程序語言的對比邏輯系統(tǒng)邏輯符號非邏輯符號程序語言保留字或符號用戶自定義的符號(變量名，函數(shù)名等)語句規(guī)則構(gòu)造一個程序的語句規(guī)則定義程序做什么的規(guī)則無語義規(guī)則推理規(guī)則、公理和證明§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法語義§

x+2

≥

y

在x

=

7,

y

=

1的世界中為真§

x+2

≥

y

在x

=

0,

y

=

6§

的世界中為假可能世界—

模型m是α的一個模型，表示α在模型m中真§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法邏輯推理--蘊含關(guān)系（entailment）一個語句邏輯上跟隨另一個語句而出現(xiàn)α╞

β

，

當(dāng)且當(dāng)在α真的模型中，

β也真（當(dāng)α真，β必定真）即β的真包含α的真中例如：

x+y

=

4

蘊含

4

=

x+yKB╞

α§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法模型檢驗3個方格中的每個可能包含或不包含陷阱，則存在8個可能的模型§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法模型檢驗與智能體所知內(nèi)容相矛盾的模型中，KB為假。根據(jù)[1,1]無微風(fēng)，則在任意[1,2]有陷阱的模型中，KB為假僅3個模型使得KB為真。α

：[1,2]無陷阱，α

：[2,2]無陷阱12§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法模型檢驗α

：[1,2]無陷阱1KB╞

α1§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法模型檢驗α

：[2,2]無陷阱2KB╞

α2模型檢驗:枚舉出所有可能的模型用于檢驗在KB中為真的所有模型中α為真?！煨?/p>

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法推理的可靠性和完備性KB

├

α：

α通過推理算法i從KB中導(dǎo)出，i推理算法i從KB中導(dǎo)出α推理算法i是可靠的：如果KB

├

α，則KB╞

αi推理算法i是完備的：如果KB╞

α，則KB

├

αi§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法命題邏輯命題：能夠分辨真假的陳述句。例如：1+1=2雪是綠色的昆明是云南的省會快點走吧!到哪去？原子命題：一個命題，且是不能再進(jìn)一步分解成更簡單語句。是命題的基本單位。一個原子命題可以用字母表示(命題符號)。命題邏輯是由命題符號和邏輯連接符組成?！煨?/p>

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法邏輯連接符合取式：p與q，記為p∧q析取式：p或q，記為p

q蘊含式：如果p則q，記為p

q等價式：p當(dāng)且僅當(dāng)q，記為p

q否定式：非，p優(yōu)先級：，

∧，

，

，

§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法命題表示將陳述句轉(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

∧（r

t）

q§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法True永真命題，F(xiàn)alse永假命題析取范式：僅由有限個簡單合取式組成的析取式p

（p

q）

（p

q）合取范式：僅由有限個簡單析取式組成的合取式p（p

q）

（p

q）§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法語義語義定義了用于判定關(guān)于特定模型的語句真值的規(guī)則例如：某模型下，P1,22,2假

真

假3,1PP邏輯連接符的真值表：指定了復(fù)合句在其組成部分的真值的每種可能賦值情況下的真值。P

(P

P

)

=

true

(true

false)

=

true

true

=

true1,22,23,1§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法Wumpus世界的知識庫P

：在[i,

j]有陷阱i,jB

：在[i,

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

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

(P

P

)1,11,22,1B

(P

P

P

)2,11,12,23,1§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法推理的基本概念推理：從已知事實出發(fā)，運用已掌握的知識，推導(dǎo)出其中蘊含的事實性結(jié)論或歸納出某些新的結(jié)論的過程。推理所用的事實：初始證據(jù)；中間結(jié)論。推理機初始證據(jù)結(jié)論知識庫目標(biāo)是判斷某些語句x，kB|=x是否成立。模型檢驗：枚舉出模型，驗證x在KB為真的每個模型中為真§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法推理真值表αα

：

P：

P2,2211,2§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法真值表枚舉算法真值表枚舉算法，是可靠的、完備的n個符號，存在2

個模型，時間復(fù)雜度O(2

)nn用于命題邏輯的有效模型檢驗推理算法包括回溯(DPLL算法)和局部搜索方法（WALKSAT算法）?！煨?/p>

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法推理方法演繹推理：從已知的一般性知識出發(fā)，推理出適合于某些個別情況的結(jié)論的過程。歸納推理：從大量的特殊事例出發(fā)，歸納出一般性結(jié)論的推理過程。默認(rèn)推理：在知識不完全的情況下假設(shè)某些條件已經(jīng)具備所進(jìn)行的推理?！煨?/p>

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法推理的不確定性及其單調(diào)性確定性推理：推理所用的證據(jù)、知識及結(jié)論都是可以精確表示的，其真值不為真就為假，不會有第三種情況出現(xiàn)。不確定性推理：推理所用的證據(jù)、知識及結(jié)論都是不確定的，都是不可以精確表示的，其真值位于真和假之間。單調(diào)性推理：由于新知識的加入和使用，使推理所得到的結(jié)論會越來越接近目標(biāo)。非單調(diào)性推理：推理過程中某些新知識的加入和使用，不但沒有加強已經(jīng)推出的結(jié)論，反而會否定原來已推出的結(jié)論?！煨?/p>

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法基本等值式：α

≡

?

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

β

且β╞

α交換律：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)§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法基本等值式：摩根律：

(p∧q)

≡

p

∨

q

(p∨q)

≡

p

∧

q吸收律：p∨(p∧q)

≡

pp∧(p∨q)

≡

p同一律：p∨

0≡

pp∧1≡

p蘊含等值式：p

q

≡

p

∨

q

（蘊含消去）假言易位式：p

q

≡

q

p（逆否命題）雙向蘊含消去：pq

≡(

p

q)

∧

(q

p)§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法合法性和可滿足性若語句α無成假賦值，則稱α是合法的，稱重言式或永真式，例如：True，A

A,

A

A,

(A

(A

B))

B若α至少有一個成真賦值，則稱α為可滿足的e.g.,

A

B,

C若α無成真賦值，則稱α為不可滿足的，稱矛盾式或永假式，例如：AA§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法α是合法的，當(dāng)且僅當(dāng)α是不可滿足的α是可滿足的，當(dāng)且僅當(dāng)α是不合法的反證法（歸謬）：KB

╞

α當(dāng)且僅當(dāng)(KB

α)是不可滿足的§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法推理規(guī)則§

邏輯等價§分離規(guī)則：α

β,

αβ例如，已知（WumpusAhead

WumpusAlive)

shoot和（WumpusAhead

WumpusAlive)，可推導(dǎo)出shoot§與消去（合取式推導(dǎo)出任何合取子句）：α

βα例如：WumpusAhead

WumpusAlive可推導(dǎo)出WumpusAlive§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法推理規(guī)則的應(yīng)用序列--證明（1）

P

（2）B

（3）B1,11,12,1（4）B

(P

P

)1,11,22,1（5）B

(P

P

P

)2,11,12,23,11.雙向蘊含消去：α

β

代換為(α

β)(β

α).由語句(4)得：(B

(P

P

))

((P

P

)

B

)

--(6)1,11,22,11,22,11,12.語句（6）與消去：((P

P

)

B

)

--(7)1,22,11,1語句(7)再根據(jù)α

β

≡

β

α

（逆否命題）得：(B

((P

P

))

--（8）1,11,22,13.由語句（8）和（2）根據(jù)分離規(guī)則得：((P

P

))

--(9)1,22,14.

根據(jù)摩根律：P

P

---（10）§信

息

學(xué)

院1,22,106

四月

2023人工智能——一種現(xiàn)代方法歸結(jié)A

B反證法：證明A

B是矛盾式（永假式）§

建立子句集合取范式：命題、命題或的與例如：p

（p

q）

（p

q）子句集S：合取范式形式下得子命題（元素）的集合例如：上述命題公式的子句集S={p,

p

q,

p

q}§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法合取范式B

(P

P

)1,11,22,11.

消去：

α

β替換為(α

β)(β

α).(B

(P

P

))

((P

P

)

B

)1,11,22,11,22,11,12.

消去：α

β替換為α

β.(B

P

P

)

((P

P

)

B

)1,11,22,11,22,11,13.

根據(jù)摩根律移入：(B

P

P

)

((P

P

)

B

)1,11,22,11,22,11,1§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法歸結(jié)規(guī)則：單元歸結(jié)規(guī)則l

…

l

,m1kl

…

l

l

…

l1i-1i+1k其中l(wèi)

and

m是互補文字(一個文字是另一個文字的否定式).i全歸結(jié)規(guī)則l

…

l

,1m

…

m1knl

…

l

l

…

l

m

…

m

m

...

m1i-1i+1k1j-1j+1n其中l(wèi)

和

m

是互補文字§信

息

學(xué)

院ij06

四月

2023人工智能——一種現(xiàn)代方法P

P

,

P1,32,22,2P1,3歸并：

（A

B）和（A

B）歸結(jié)得到A

A，最終簡化為A§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法l

…

l

,1m

…

m1knl

…

l

l

…

l

m

…

m

m

...

1i-1i+1k1j-1j+1mn歸結(jié)規(guī)則的可靠性：l

真，則m

假

(m

…

m

m

...

m

)真ij1j-1j+1nl

假，l

…

l

l

…

l

真i1i-1i+1k歸結(jié)規(guī)則的完備性：任何完備的搜索算法，只使用歸結(jié)規(guī)則，就可以生成命題邏輯中被任何知識庫蘊涵的任何結(jié)論。已知A為真，無法用歸結(jié)自動生成結(jié)論A

B，但可以用歸結(jié)判斷A

B是否為真。§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法歸結(jié)過程1.

將命題寫成合取范式2.

求出子句集S3.

對子句集使用歸結(jié)推理規(guī)則4.

歸結(jié)式作為新子句參加歸結(jié)5.

歸結(jié)式為空子句，S是不可滿足的（矛盾），原命題成立§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法例如：證明公式（pq

）

（q

p）證：將待證明公式轉(zhuǎn)化為歸結(jié)命題公式：（

pq

）

(q

p)將該公式轉(zhuǎn)化為合取范式pq

≡

p

∨

q(q

p)

≡

(q

∨p)

≡

q

p（

pq

）

(q

p)

≡(

p

∨

q)

q

p則子句集：

p

∨

q，

q

，p§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法對子句集中的子句進(jìn)行歸結(jié)：（1）

p

∨

q（2）

q（3）p（4）q

（1,

3歸結(jié)）（5）空

（2,

4歸結(jié)）§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法Wumpus世界的歸結(jié)推理KB

=

(B

(P

P

))

B1,11,22,11,1α

=

P1,2(B

(P

P

))

B

P

≡1,11,22,11,11,2(B

P

P

)

(P

B

)

(P

B

)

B

P1,11,22,11,21,12,11,11,11,2§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法前向和反向鏈接霍恩子句：至多只有一個正文字的文字析取式(P

B

)

P

P

P1,21,12,11,22,1(B

P

P

)1,11,22,1§

每個霍恩子句都可寫成一個蘊涵式：(P

B

)

≡

P

B1,21,11,21,1沒有正文字的霍恩子句：可寫成結(jié)論為False的蘊涵式例如：

P

P

≡

（P

P

)

False1,22,11,22,1確定子句：只有一個正文字，

例如：P

，斷言一個事實2,1§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法§

使用霍恩子句的推理可在前向鏈接和反向鏈接中進(jìn)行§

使用霍恩子句判定蘊涵需要的時間和數(shù)據(jù)庫大小成線性關(guān)系§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法前向鏈接判定單個命題符號q是否被霍恩子句的知識庫所蘊涵：從知識庫的已知事實(正文字)開始，如果蘊涵的所有前提已知，則將其結(jié)論添加到已知事實集。直到查詢q被添加或無法進(jìn)行更進(jìn)一步的推理§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法前向鏈接§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法前向鏈接§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法前向鏈接§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法前向鏈接§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法前向鏈接§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法前向鏈接§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法前向鏈接§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法前向鏈接前向鏈接中每個推理本質(zhì)上是分離規(guī)則的一個應(yīng)用。可靠的完備的§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法反向鏈接從查詢q反向進(jìn)行：查詢q是否是已知事實，否則尋找知識庫中能以q為結(jié)論的蘊涵，若其中某個蘊涵的所有前提都能證明為真，則q為真?！煨?/p>

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法反向鏈接§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法反向鏈接§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法反向鏈接§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法反向鏈接§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法反向鏈接§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法反向鏈接§信

息

學(xué)

院06

四月

2023人工智能——一種現(xiàn)代方法反向鏈接§