人工智能第三章

人工智能第三章第1頁，課件共80頁，創(chuàng)作于2023年2月3.1.1命題命題：能判斷真假（不是既真又假）的陳述句。 簡單陳述句描述事實、事物的狀態(tài)、關(guān)系等性質(zhì)。例如：1．

1+1=22．

雪是黑色的。3．

北京是中國的首都。4．

到冥王星去渡假。命題通常用字母p,q,a,b表示；

判斷一個句子是否是命題，有先要看它是否是陳述句，而后看它的真值是否唯一。以上的例子都是陳述句，第4句的真值現(xiàn)在是假，隨著人類科學的發(fā)展，有可能變成真，但不管怎樣，真值是唯一的。因此，以上4個例子都是命題。而例如：

1．

快點走吧！

2．

到那去？

3．

x+y>10

等等句子，都不是命題。第2頁，課件共80頁，創(chuàng)作于2023年2月3.1.2命題邏輯公式

定義：

原子命題：不能再分解的命題稱為原子命題。合式公式：原子命題是合式公式，連接詞聯(lián)結(jié)的合式公式的組合也是合式公式（命題公式）。常用的聯(lián)結(jié)詞：合取式：p與q，記做pΛ

q析取式：

p或q，記做p∨

q蘊含式：如果p則q，記做p→

q等價式：p當且僅當q，記做p<=>

q否定：～p

、

～最優(yōu)先，其次為Λ、∨，再次為→，<=>第3頁，課件共80頁，創(chuàng)作于2023年2月命題表示公式（1）將陳述句轉(zhuǎn)化成命題公式。如：設(shè)“下雨”為p，“騎車上班”為q，，1．“只要不下雨，我騎自行車上班”。～p

是q的充分條件， 因而，可得命題公式：～p→q2．“只有不下雨，我才騎自行車上班”?！玴

是q的必要條件， 因而，可得命題公式：q→～p第4頁，課件共80頁，創(chuàng)作于2023年2月命題表示公式（2）事件化為命題公式的步驟：（１）分析簡單命題，將其符號化；（２）使用適當?shù)穆?lián)結(jié)詞把簡單命題連接起來。例如：1．

“如果我進城我就去看你，除非我很累。” 設(shè)：p，我進城，q，去看你，r，我很累。 則有命題公式：～r→(p→q)。2．“應(yīng)屆高中生，得過數(shù)學或物理競賽的一等獎， 保送上北京大學?！?設(shè)：p，應(yīng)屆高中生，q，保送上北京大學上學，

r，是得過數(shù)學一等獎。t，是得過物理一等獎。 則有命題公式公式：p

∧(r∨t)→

q。

第5頁，課件共80頁，創(chuàng)作于2023年2月２命題公式的解釋定義：設(shè)Ａ為一個命題公式，p1,p2,…,pn是出現(xiàn)在Ａ中的全部原子命題，給原子命題各指定一個真值（０或者１），稱為對Ａ的一個賦值或解釋。若Ａ的值為真，則稱為成真賦值。若Ａ的值為假，則稱為成假賦值。第6頁，課件共80頁，創(chuàng)作于2023年2月公式邏輯真值表ＰＱ～ＰＰ∨ＱＰ∧ＱＰ→ＱＰＱＴＴＦＴＴＴＴＴＦＦＴＦＦＦＦＴＴＴＦＴＦＦＦＴＦＦＴＴ第7頁，課件共80頁，創(chuàng)作于2023年2月命題邏輯基礎(chǔ)基本等值式交換率：p∨q<=>q

∨p

；

pΛ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)

雙重否定率：～～p<=>p

等冪率：p<=>p∨p

，p<=>pΛp

等價等值式：p

q

<=> (p→

q)Λ(q→

p)等價否定式：p

q

<=> ~p~q

第8頁，課件共80頁，創(chuàng)作于2023年2月命題邏輯基礎(chǔ)摩根率:～

(p∨q)

<=>～

pΛ

～

q

；

～

(pΛq)

<=>～

p∨

～

q

吸收率:p∨(pΛq)<=>p

；

pΛ(p∨q)<=>p

同一律:p∨0

<=>p

；

pΛ1

<=>p

蘊含等值式:p→

q

<=>～

p∨q

假言易位式:p→

q

<=>～p→～

q

歸謬式:(p→

q)Λ(p→~q

)<=>～p排中律：p∨～p

<=>１；矛盾律：pΛ～p

<=>０

零率：p∨１

<=>１；

pΛ０

<=>０

第9頁，課件共80頁，創(chuàng)作于2023年2月范式：公式的標準型式。定義：設(shè)A為一個公式若A無成假賦值，則稱A為重言式或永真式；若A無成真賦值，則稱A為矛盾式或永假式；若A至少有一個成真賦值，則稱A為可滿足的；簡單合取式：有限個原子命題或其否定構(gòu)成合取式。簡單析取式：有限個原子命題或其否定構(gòu)成析取式。析取范式：僅由有限個簡單合取式組成的析取式。合取范式：僅由有限個簡單析取式組成的合取式。范式的性質(zhì)：析取范式是矛盾式，當且僅當每個簡單合取式是矛盾式。合取范式是永真式，當且僅當每個簡單析取式是永真式。第10頁，課件共80頁，創(chuàng)作于2023年2月范式的轉(zhuǎn)化存在定理：任何命題公式都存在著與之等值的析取范式和合取范式。求合取范式的步驟：（１）消去多余的｛∨，∧｝以及→聯(lián)結(jié)詞（２）去掉否定～符號（３）利用分配率例：3.1,3.23.1.3命題邏輯的意義

把自然語言轉(zhuǎn)化為形式語言，以利于計算機能夠處理。第11頁，課件共80頁，創(chuàng)作于2023年2月例3.2：求的（（Ｐ∨Ｑ）→Ｒ）→Ｐ合取范式解：（（Ｐ∨Ｑ）→Ｒ）→Ｐ＝（～（Ｐ∨Ｑ）∨Ｒ）→Ｐ＝～（～（Ｐ∨Ｑ）∨Ｒ）∨Ｐ＝（（Ｐ∨Ｑ）∧～Ｒ）∨Ｐ＝（Ｐ∨Ｑ∨Ｐ）∧（～Ｒ∨Ｐ）＝（Ｐ∨Ｑ）∧（～Ｒ∨Ｐ）第12頁，課件共80頁，創(chuàng)作于2023年2月3.1.4命題邏輯的推理規(guī)則（自然演繹推理）邏輯結(jié)論：對于Ａ→Ｂ，如果永真，則稱Ｂ是Ａ的邏輯結(jié)論，即Ａ推出Ｂ的結(jié)論正確，Ａ為真則Ｂ為真，記為Ａ=>Ｂ。常用的推理定律（永真式）：，∧

附加：Ａ=>（Ａ∨Ｂ）簡化：（Ａ∧Ｂ）=>Ａ

假言推理：（Ａ→Ｂ）∧Ａ）=>Ｂ拒取式：（（Ａ→Ｂ）∧～Ｂ）=>～Ａ析取三段論：（（Ａ∨Ｂ）∧～Ａ）=>Ｂ假言三段論：（（Ａ→Ｂ）∧（Ｂ→Ｃ））=>（Ａ→Ｃ）等價三段論：（（ＡＢ）∧（ＢＣ））=>（ＡＣ）構(gòu)造性二難：（（Ａ→Ｂ）∧（Ｃ→Ｄ）∧（Ａ∨Ｃ））=>（Ｂ∨Ｄ）第13頁，課件共80頁，創(chuàng)作于2023年2月常用的推理規(guī)則：（１）前提引入規(guī)則（２）結(jié)論引入規(guī)則（３）置換規(guī)則：等價的可以置換例３.4：證明：如果今天是下雨天，則要帶傘或帶雨衣。如果走路上班，則不帶雨衣。今天下雨，走路上班，所以帶雨傘。解：把題目用命題公式表示：今天下雨p，帶傘q，帶雨衣r，走路上班s前提：p→（q∨r），s→～r，p，s要證的結(jié)論：q證明：①p→（q∨r）②

p前提引入

③（q∨r）假言推理

④

s

⑤s→～r前提引入

⑥～r假言推理⑦q析取三段論第14頁，課件共80頁，創(chuàng)作于2023年2月3.1.5命題邏輯的歸結(jié)法歸謬法：命題：A1、A2、A3

和B求證：A1ΛA2ΛA3成立，則B成立，即：A1ΛA2ΛA3→B為永真

A1ΛA2ΛA3→B

等價于~(A1ΛA2ΛA3)∨B

等價于~(~~(A1ΛA2ΛA3)∧~B)

等價于~((A1ΛA2ΛA3)∧~B)永真即證明((A1ΛA2ΛA3)∧~B)永假反證法：證明A1ΛA2ΛA3Λ～B是矛盾式（永假式）

第15頁，課件共80頁，創(chuàng)作于2023年2月例：前提：p→（~（r∨s）→q)，p，~s要證的結(jié)論：q證明：①p→（~（r∨s）→q)

②p前提引入

③~（r∨s）→q

假言推理

④

~q引入否定結(jié)論

⑤（r∨s）拒取式

⑥～s前提引入⑦s簡化⑤⑧～s∧s⑥

⑦合取永假矛盾。第16頁，課件共80頁，創(chuàng)作于2023年2月歸結(jié)原理由J.A.Robinson由1965年提出。與演繹法(deductiveinference)完全不同，新的邏輯演算(inductiveinference)算法。一階邏輯中，至今為止的最有效的半可判定的算法。即，一階邏輯中任意恒真公式，使用歸結(jié)原理，總可以在有限步內(nèi)給以判定。語義網(wǎng)絡(luò)、框架表示、產(chǎn)生式規(guī)則等等都是以推理方法為前提的。即，有了規(guī)則已知條件，順藤摸瓜找到結(jié)果。而歸結(jié)方法是自動推理、自動推導證明用的。（“數(shù)學定理機器證明”）第17頁，課件共80頁，創(chuàng)作于2023年2月命題邏輯的歸結(jié)法子句集子句：子句是文字的集合，各個文字之間被析取分隔。文字：原子命題或否定被稱為文字。合取范式：命題、命題或的與，如：

PΛ（P∨Q）Λ（～P∨Q）子句集S：合取范式形式下的子命題（元素）的集合例：命題公式：PΛ（P∨Q）Λ（～P∨Q）子句集S：S={P,P∨Q,～P∨Q}

第18頁，課件共80頁，創(chuàng)作于2023年2月歸結(jié)式設(shè)C1,C2是子句集中的兩個子句，如果C1中的文字L1與C2中文字L2互補，則可以從C1和

C2中分別消去文字L1和文字L2，并將中余下的部分按析取關(guān)系構(gòu)成一個新子句C12，這個過程就叫歸結(jié)。如子句：C1=P∨Q,C2=~P∨W

，歸結(jié)式：C12

=W∨Q

性質(zhì)：歸結(jié)式C12

是親本子句C1和

C2邏輯結(jié)論。

C1ΛC2→C12

，注意：反之不一定成立。第19頁，課件共80頁，創(chuàng)作于2023年2月命題邏輯的歸結(jié)法歸結(jié)過程

將命題寫成合取范式求出子句集對子句集使用歸結(jié)推理規(guī)則歸結(jié)式作為新子句參加歸結(jié)歸結(jié)式為空子句□，S是不可滿足的（矛盾），原命題成立。?（證明完畢）謂詞的歸結(jié)：除了有量詞和函數(shù)以外，其余和命題歸結(jié)過程一樣。第20頁，課件共80頁，創(chuàng)作于2023年2月命題邏輯歸結(jié)例題（1）例題，已知：(P→Q)求證：(～Q→～P)證明：（1）根據(jù)歸結(jié)原理，將待證明公式轉(zhuǎn)化成待歸結(jié)命題公式：

(P→Q)∧～(～Q→～P)（2）分別將公式前項化為合取范式：

P→Q＝～P∨Q

結(jié)論求～后的后項化為合取范式： ～(～Q→～P)＝～(Q∨～P)＝～Q∧P

兩項合并后化為合取范式： （～P∨Q）∧～Q∧P

（3）則子句集為：

{～P∨Q，～Q，P}第21頁，課件共80頁，創(chuàng)作于2023年2月命題邏輯歸結(jié)例題（2）子句集為： {～P∨Q，～Q，P}（4）對子句集中的子句進行歸結(jié)可得：1.

～P∨Q2.

～Q3.

P4.

Q， （1，3歸結(jié)）5.

， （2，4歸結(jié)）

由上可得原公式成立。第22頁，課件共80頁，創(chuàng)作于2023年2月3.2謂詞歸結(jié)原理基礎(chǔ)一階邏輯3.2.1基本概念個體詞：表示主語的詞(客體、具體事物或抽象的概念）謂詞：刻畫個體性質(zhì)或個體之間關(guān)系的詞量詞：表示數(shù)量的詞第23頁，課件共80頁，創(chuàng)作于2023年2月謂詞歸結(jié)原理基礎(chǔ) 小王是個工程師。

8是個自然數(shù)。 我去買花。 小麗和小華是朋友。其中，“小王”、“工程師”、“我”、“花”、“8”、“小麗”、“小華”都是個體詞，而“是個工程師”、“是個自然數(shù)”、“去買”、“是朋友”都是謂詞。顯然前兩個謂詞表示的是事物的性質(zhì)，第三個謂詞“去買”表示的一個動作也表示了主、賓兩個個體詞的關(guān)系，最后一個謂詞“是朋友”表示兩個個體詞之間的關(guān)系。第24頁，課件共80頁，創(chuàng)作于2023年2月謂詞歸結(jié)原理基礎(chǔ)個體常量：a,b,c個體變量：x,y,z謂詞符號：P,Q,R謂詞：由謂詞符號和個體（項）組成。例P(x,y)一階謂詞：謂詞中不含有謂詞。n元謂詞：就是有n個項。量詞符號：

,第25頁，課件共80頁，創(chuàng)作于2023年2月例如：（1）所有的人都是要死的。（2）

有的人活到一百歲以上。在個體域D為人類集合時，可符號化為：（1）xP(x)，其中P(x)表示x是要死的。（2）xQ(x),其中Q(x)表示x活到一百歲以上。在個體域D是全總個體域時，引入特殊謂詞R(x)表示x是人，可符號化為：（1）x（R(x)→P(x)）,

其中，R(x)表示x是人；P(x)表示x是要死的。（2）x（R(x)∧Q(x)）， 其中，R(x)表示x是人；Q(x)表示x活到一百歲以上。

第26頁，課件共80頁，創(chuàng)作于2023年2月3.2.2一階謂詞邏輯1謂詞公式原子公式：單個謂詞就是原子公式。謂詞公式：簡單說就是由原子公式、連接詞、否定符號以及量詞構(gòu)成的式子。指導變量：量詞后面的變量稱為指導變量。x、y轄域：就是量詞管轄的區(qū)域。約束出現(xiàn)：在轄域內(nèi)，受量詞約束的變量是約束出現(xiàn)。自由出現(xiàn)：在轄域內(nèi)，不受量詞約束的變量是約束出現(xiàn)。換名規(guī)則：將量詞轄域中某個約束出現(xiàn)的個體變量改成在此轄域中未出現(xiàn)過的個體變量符號。xP(x,y)∧R(x,y)

第27頁，課件共80頁，創(chuàng)作于2023年2月替換規(guī)則：對某個自由變量用與原公式中所有個體變量符號不同的變量去替代，且處處替代。xP(x,y)∧R(x,y)替換xP(x,z)∧R(x,z)2.謂詞公式的解釋對謂詞公式的各變量常量去替代，就構(gòu)成了一個謂詞公式的解釋。當存在解釋能使謂詞公式為真時，則稱這個解釋滿足謂詞公式。這個解釋就是這個謂詞公式的模型。兩個謂詞公式等價，當且僅當所有的解釋下兩個謂詞公式的值是相同的。永真式不可滿足式歸結(jié)原理就是對謂詞公式的正確性證明轉(zhuǎn)化為不可滿足性證明。第28頁，課件共80頁，創(chuàng)作于2023年2月3.2.3謂詞演算與推理1.謂詞演算公式量詞否定等值式：～(x

）

M（x）<=>（

y

）～

M（y）～(x

）

M（x）<=>（

y

）～

M（y）量詞分配等值式：(x

）(

P（x）ΛQ（x）)<=>(x

）

P（x）Λ(x

）

Q（x）(x

）(

P（x）∨

Q（x）)<=>(x

）

P（x）∨

(x

）

Q（x）消去量詞等值式：設(shè)個體域為有窮集合（a1,a2,…an）(x

）

P（x）<=>P（a1

）ΛP（a2

）Λ…ΛP（an

）(x

）P（x）<=>P（a1

）∨

P（a2

）∨

…

∨

P（an

）第29頁，課件共80頁，創(chuàng)作于2023年2月約束變量換名規(guī)則：

(Qx)P(x)<=>(Qy)P(y)

(Qx)P(x,z)<=>(Qy)P(y,z)量詞轄域收縮與擴張等值式：(x

）(

P（x）∨Q)<=>(x

）

P（x）∨Q(x

）(

P（x）ΛQ)<=>(x

）

P（x）ΛQ

(x

）(

P（x）→Q)<=>(x

）

P（x）→Q

(x

）(Q

→P（x）)<=>Q

→(x

）

P（x）(x

）(

P（x）∨Q)<=>(x

）

P（x）∨Q(x

）(

P（x）ΛQ)<=>(x

）

P（x）ΛQ

(x

）(

P（x）→Q)<=>(x

）

P（x）→Q

(x

）(Q

→P（x）)<=>Q

→(x

）

P（x）第30頁，課件共80頁，創(chuàng)作于2023年2月前束范式

定義：說公式A是一個前束范式，如果A中的一切量詞都位于該公式的最左邊（不含否定詞），且這些量詞的轄域都延伸到公式的末端。第31頁，課件共80頁，創(chuàng)作于2023年2月即：把所有的量詞都提到前面去，然后消掉所有量詞

(Q1x1)(Q2x2)…(Qnxn)M(x1,x2,…,xn)例９第32頁，課件共80頁，創(chuàng)作于2023年2月２謂詞推理要運用與命題邏輯相同的推理規(guī)則和量詞的消去和引入。任意量詞可以消去，用變量或常量表示，存在量詞可以用常量表示。對于任意量詞，ｘ為自由變量，ｙ為不在Ｐ中約束出現(xiàn)的個體變量時：

ｘＰ（ｘ）=>Ｐ（ｙ）ｃ為常量

ｘＰ（ｘ）=>Ｐ（ｃ）對于存在量詞，

ｘＰ（ｘ）=>Ｐ（ｃ）對于變量引入量詞：

Ｐ（ｙ）=>ｘＰ（ｙ）要求ｙ在Ｐ（ｙ）中自由出現(xiàn)，且為真，ｘ不在Ｐ（ｙ）中約束出現(xiàn)。

Ｐ（ｃ）=>ｘＰ（ｘ）要求ｃ是特定常量，取代ｃ的ｘ不能在Ｐ（ｃ）中出現(xiàn)。第33頁，課件共80頁，創(chuàng)作于2023年2月例3.1020世紀７０年代的漫畫都是日本漫畫家創(chuàng)作的，這幅漫畫是２０世紀７０年代的作品，因此這幅漫畫是日本漫畫家的作品。解：設(shè)Ｐ(x)：ｘ是20世紀７０年代的漫畫Q(ｙ):ｙ日本漫畫家的作品a:一幅漫畫前提x(Ｐ(x)

→Q(x)),P(a)結(jié)論Q(a)證明①x(Ｐ(x)

→Q(x))②P(a)③Ｐ(a)

→Q(a)④Q(a)第34頁，課件共80頁，創(chuàng)作于2023年2月3.2.4謂詞知識表示知識：是人們在認識、改造世界中經(jīng)驗的總結(jié)或者實事的描述。使用邏輯法表示知識，將自然語言描述的知識，通過謂詞、函數(shù)加以描述，獲得邏輯謂詞公式，進而利用計算機進行處理。例：校長與小李打網(wǎng)球。可以表示為：定義：Play(x,y,z)表示，ｘ和ｙ打ｚ這種球

Play(zhang,li,tennis)

清華是個大學定義：Univ(x)表示ｘ是大學

Univ(qinghua)第35頁，課件共80頁，創(chuàng)作于2023年2月常用的可以用蘊含代表規(guī)則：人人都受法律管制：

Human(x)→Lawed(x)

如果ｘ犯罪則被懲罰

Commit(x)→Punished(x)（Human(x)→Lawed(x)）→（Commit(x)→Punished(x)）應(yīng)用謂詞表示知識應(yīng)用廣泛：（１）易于用數(shù)據(jù)庫存貯知識（２）謂詞具有完備邏輯推理方法（３）表達的知識具有科學嚴密性（４）邏輯推理具有知識的一致性第36頁，課件共80頁，創(chuàng)作于2023年2月３.3謂詞邏輯歸結(jié)原理3.3.1歸結(jié)原理命題：A1、A2、A3

和B求證：A1ΛA2ΛA3成立，則B成立，反證法：證明A1ΛA2ΛA3Λ～B是矛盾式（永假式）3.3.2Skolem標準形1.前束范式2.Skolem標準形消去前束范式中的所有量詞的公式第37頁，課件共80頁，創(chuàng)作于2023年2月量詞消去原則： 消去存在量詞“”，略去全程量詞“”。 注意：左邊有全程量詞的存在量詞，消去時該變量改寫成為全程量詞的函數(shù)；如沒有，改寫成為常量。第38頁，課件共80頁，創(chuàng)作于2023年2月謂詞歸結(jié)子句形(Skolem標準形)Skolem定理： 謂詞邏輯的任意公式都可以化為與之等價的前束范式，但其前束范式不唯一。SKOLEM標準形定義： 消去量詞后的謂詞公式。注意：謂詞公式G的SKOLEM標準形同G并不等值。第39頁，課件共80頁，創(chuàng)作于2023年2月謂詞歸結(jié)子句形(Skolem標準形)例:將下式化為Skolem標準形： ～(x)(y)P(a,x,y)→(x)(～(y)Q(y,b)→R(x))解：第一步，消去→號，得： ～(～(x)(y)P(a,x,y))∨(x)(～～(y)Q(y,b)∨R(x))第二步，～深入到量詞內(nèi)部，得：

(x)(y)P(a,x,y)∨(x)((y)Q(y,b)∨R(x))第三步，變元易名，得

(x)((y)P(a,x,y)∨(u)(v)(Q(v,b)∨R(u))第四步，存在量詞左移，直至所有的量詞移到前面，得：

(x)(y)(u)(v)P(a,x,y)∨(Q(v,b)∨R(u))由此得到前述范式第40頁，課件共80頁，創(chuàng)作于2023年2月謂詞歸結(jié)子句形(Skolem標準形)

第五步，消去“”（存在量詞），略去“”全稱量詞 消去(y)，因為它左邊只有(x)，所以使用x的函數(shù)f(x)代替之，這樣得到：

(x)(z)(P(a,x,f(x))∧～Q(z,b)∧～R(x))

消去(z)，同理使用g(x)代替之，這樣得到：

(x)(P(a,x,f(x))∧～Q(g(x),b)∧～R(x))

則，略去全稱變量，原式的Skolem標準形為：

P(a,x,f(x))∧～Q(g(x),b)∧～R(x)

第41頁，課件共80頁，創(chuàng)作于2023年2月3.3.3子句集子句與子句集文字：不含任何連接詞的謂詞公式。子句：一些文字的析?。ㄖ^詞的和）。子句集S的求?。?/p>

G→SKOLEM標準形 →消去存在變量 →以“，”取代“Λ”，并表示為集合形式。第42頁，課件共80頁，創(chuàng)作于2023年2月謂詞歸結(jié)子句形

G是不可滿足的<=>S是不可滿足的G與S不等價，但在不可滿足得意義下是一致的。

定理： 若G是給定的公式，而S是相應(yīng)的子句集，則G是不可滿足的<=>S是不可滿足的。

注意：G真不一定S真，而S真必有G真。 即：S=>G第43頁，課件共80頁，創(chuàng)作于2023年2月謂詞歸結(jié)子句形G=G1ΛG2ΛG3Λ…ΛGn

的子句形G的字句集可以分解成幾個單獨處理。

有SG=S1US2US3U…USn

則SG

與S1US2US3U…USn在不可滿足得意義上是一致的。 即SG

不可滿足<=>S1US2US3U…USn不可滿足第44頁，課件共80頁，創(chuàng)作于2023年2月求取子句集例(1)例：對所有的x,y,z來說，如果y是x的父親，z又是y的父親，則z是x的祖父。又知每個人都有父親，試問對某個人來說誰是它的祖父？求：用一階邏輯表示這個問題，并建立子句集。解：這里我們首先引入謂詞：

P(x,y)表示x是y的父親

Q(x,y)表示x是y的祖父

ANS(x)表示問題的解答第45頁，課件共80頁，創(chuàng)作于2023年2月求取子句集例(2)對于第一個條件，“如果x是y的父親，y又是z的父親，則x是z的祖父”，一階邏輯表達式如下：

A1：(x)(y)(z)(P(x,y)∧P(y,z)→Q(x,z)) SA1：～P(x,y)∨～P(y,z)∨Q(x,z)對于第二個條件：“每個人都有父親”，一階邏輯表達式：

A2：(y)(x)P(x,y) SA2：P(f(y),y)對于結(jié)論：某個人是它的祖父

B：(x)(y)Q(x,y)

否定后得到子句：～（(x)(y)Q(x,y)）∨ANS(x) S～B：～Q(x,y)∨ANS(x)則得到的相應(yīng)的子句集為：{SA1，SA2，S～B}第46頁，課件共80頁，創(chuàng)作于2023年2月歸結(jié)原理歸結(jié)原理正確性的根本在于，找到矛盾可以肯定不真。方法：和命題邏輯一樣。但由于有函數(shù)，所以要考慮合一和置換。

第47頁，課件共80頁，創(chuàng)作于2023年2月3.3.4置換與合一置換：可以簡單的理解為是在一個謂詞公式中用置換項去置換變量。定義： 置換是形如{t1/x1,t2/x2,…,tn/xn}的有限集合。其中，x1,x2,…,xn是互不相同的變量，t1,t2,…,tn是不同于xi的項（常量、變量、函數(shù)）；ti/xi表示用ti置換xi，并且要求ti與xi不能相同，而且xi不能循環(huán)地出現(xiàn)在另一個ti中。例如

{a/x，c/y，f(b)/z}是一個置換。

{g(y)/x，f(x)/y}不是一個置換，

第48頁，課件共80頁，創(chuàng)作于2023年2月置換的合成設(shè)＝{t1/x1,t2/x2,…,tn/xn}， ＝{u1/y1,u2/y2,…,un/yn}，是兩個置換。 則與的合成也是一個置換，記作·。它是從集合

{t1·/x1,t2·/x2,…,tn·/xn,u1/y1,u2/y2,…,un/yn}

中刪去以下兩種元素：當ti=xi時，刪去ti/xi(i=1,2,…,n);

當yi{x1,x2,…,xn}時，刪去uj/yj(j=1,2,…,m)

最后剩下的元素所構(gòu)成的集合。合成即是對ti先做置換然后再做置換，置換xi第49頁，課件共80頁，創(chuàng)作于2023年2月置換的合成例：設(shè)：＝{f(y)/x,z/y}，＝{a/x,b/y,y/z}，求與的合成。解：先求出集合

{f(b/y)/x,(y/z)/y,a/x,b/y,y/z}＝{f(b)/x,y/y,a/x,b/y,y/z}

其中，f(b)/x中的f(b)是置換作用于f(y)的結(jié)果；y/y中的y是置換作用于z的結(jié)果。在該集合中，y/y滿足定義中的條件i，需要刪除；a/x，b/y滿足定義中的條件ii，也需要刪除。最后得

·＝{f(b)/x，y/z}第50頁，課件共80頁，創(chuàng)作于2023年2月合一合一可以簡單地理解為“尋找相對變量的置換，使兩個謂詞公式一致”。定義：設(shè)有公式集F＝{F1，F(xiàn)2，…，F(xiàn)n}，若存在一個置換，可使F1＝F2＝…=Fn，則稱是F的一個合一。同時稱F1，F(xiàn)2，...，F(xiàn)n是可合一的。

例： 設(shè)有公式集F＝{P(x,y,f(y)),P(a,g(x),z)}，則＝{a/x,g(a)/y,f(g(a))/z}是它的一個合一。注意：一般說來，一個公式集的合一不是唯一的。

第51頁，課件共80頁，創(chuàng)作于2023年2月最一般合一：設(shè)δ是謂詞公式集F，如果對F的任意一個合一θ都存在一個置換λ使得θ=δ·λ，則稱δ是一個最一般的合一mgu.最一般合一求取方法：逐一比較找出不一致，并做合一置換算法：對于F1和F2①令W={F1,F2}②令k=0，W0=W,δ0=ε③如果Wk已合一，停止,δk=mgu,，否則找不一致集Dk④若Dk中存在元素vk和tk，其中vk不出現(xiàn)于tk中，轉(zhuǎn)⑤，否則不可合一⑤令δk+1=δk·{tk/vk},Wk+1=Wk·{tk/tk}=Wδk+1⑥k=k+1轉(zhuǎn)③。可證明若F1和F2可合一，算法必停于③第52頁，課件共80頁，創(chuàng)作于2023年2月例3.16：W={P(a,x,f(g(y))),P(z,f(a),f(u))},F1=P(a,x,f(g(y))),F2=P(z,f(a),f(u)),求：F1和F2的最一般合一第53頁，課件共80頁，創(chuàng)作于2023年2月3.3.5歸結(jié)式要考慮變量的置換和合一歸結(jié)式：對兩個無公共變量的字句對于子句C1‘∨L1和C2’∨L2，如果L1與～L2可合一，且s是其合一者，則(C1‘∨C2’)s是其歸結(jié)式。其中L1、L2是單文字。事實上L1、L2中有一個含有否定符，所以對另一個加上否定符后，才能判斷它們是否可合一。

例（1）P(x)∨Q(x,y)與~P(a)∨R(b,z)（2）P(x,y)∨Q(x)∨R(x)與~P(a,z)∨~Q(b)第54頁，課件共80頁，創(chuàng)作于2023年2月3.3.5歸結(jié)式歸結(jié)的注意事項：謂詞的一致性，P()與Q()，不可以常量的一致性，P(a,…)與P(b,….)，不可以 變量，P(a,….)與P(x,…)，可以變量與函數(shù)，P(a,x,….)與P(x,f(x),…)，不可以；是不能同時消去兩個互補對，P∨Q與～P∨～Q的空，不可以先進行內(nèi)部簡化（置換、合并）

第55頁，課件共80頁，創(chuàng)作于2023年2月3.3.6歸結(jié)的過程寫出謂詞關(guān)系公式→用反演法寫出謂詞表達式→SKOLEM標準形→子句集S→對S中可歸結(jié)的子句做歸結(jié)→歸結(jié)式仍放入S中，反復歸結(jié)過程→得到空子句

?得證第56頁，課件共80頁，創(chuàng)作于2023年2月

子句集的化簡

在謂詞邏輯中，任何一個謂詞公式都可以通過應(yīng)用等價關(guān)系及推理規(guī)則化成相應(yīng)的子句集。其化簡步驟如下：

(1)消去連接詞“→”和“?”反復使用如下等價公式：

P→Q?﹁P∨QP?Q?(P∧Q)∨(﹁P∧﹁Q)即可消去謂詞公式中的連接詞“→”和“?”。例如公式

(?x)((?y)P(x,y)→﹁(?y)(Q(x,y)→R(x,y)))經(jīng)等價變化后為

(?x)(﹁(?y)P(x,y)∨﹁(?y)(﹁Q(x,y)∨R(x,y)))第57頁，課件共80頁，創(chuàng)作于2023年2月2.子句集的化簡(2)減少否定符號的轄域反復使用雙重否定率

﹁(﹁P)?P摩根定律

﹁(P∧Q)?﹁P∨﹁Q﹁(P∨Q)?﹁P∧﹁Q量詞轉(zhuǎn)換率

﹁(?x)P(x)?(?x)﹁P(x)﹁(?x)P(x)?(?x)￢P(x)將每個否定符號“﹁”移到僅靠謂詞的位置，使得每個否定符號最多只作用于一個謂詞上。例如，上式經(jīng)等價變換后為

(?x)((?y)﹁P(x，y)∨(?y)(Q(x，y)∧﹁R(x，y)))第58頁，課件共80頁，創(chuàng)作于2023年2月子句集的化簡

(3)對變元標準化在一個量詞的轄域內(nèi)，把謂詞公式中受該量詞約束的變元全部用另外一個沒有出現(xiàn)過的任意變元代替，使不同量詞約束的變元有不同的名字。例如，上式經(jīng)變換后為

(?x)((?y)﹁P(x，y)∨(?z)(Q(x，z)∧﹁R(x，z)))(4)化為前束范式化為前束范式的方法:把所有量詞都移到公式的左邊，并且在移動時不能改變其相對順序。由于第(3)步已對變元進行了標準化，每個量詞都有自己的變元，這就消除了任何由變元引起沖突的可能，因此這種移動是可行的。例如，上式化為前束范式后為

(?x)(?y)(?z)(﹁P(x，y)∨(Q(x，z)∧﹁R(x，z)))第59頁，課件共80頁，創(chuàng)作于2023年2月2.子句集的化簡

(5)消去存在量詞消去存在量詞時，需要區(qū)分以下兩種情況：

若存在量詞不出現(xiàn)在全稱量詞的轄域內(nèi)（即它的左邊沒有全稱量詞），只要用一個新的個體常量替換受該存在量詞約束的變元，就可消去該存在量詞。

若存在量詞位于一個或多個全稱量詞的轄域內(nèi)，例如

(?x1)…(?xn)(?y)P(x1，x2,…,xn,y)則需要用Skolem函數(shù)f(x1，x2,…,xn)替換受該存在量詞約束的變元y，然后再消去該存在量詞。例如，上步所得公式中存在量詞(?y)和(?z)都位于(?x)的轄域內(nèi)，因此都需要用Skolem函數(shù)來替換。設(shè)替換y和z的Skolem函數(shù)分別是f(x)和g(x)，則替換后的式子為

(?x)(﹁P(x,f(x))∨(Q(x,g(x))∧﹁R(x,g(x))))第60頁，課件共80頁，創(chuàng)作于2023年2月2.子句集的化簡

(6)化為Skolem標準形

Skolem標準形的一般形式為

(?x1)…(?xn)M(x1,x2,……,xn)其中，M(x1,x2,……,xn)是Skolem標準形的母式，它由子句的合取所構(gòu)成。把謂詞公式化為Skolem標準形需要使用以下等價關(guān)系

P∨(Q∧R)?(P∨Q)∧(P∨R)例如，前面的公式化為Skolem標準形后為

(?x)((﹁P(x,f(x))∨Q(x,g(x))∧(﹁P(x,f(x))∨﹁R(x,g(x))))(7)消去全稱量詞由于母式中的全部變元均受全稱量詞的約束，并且全稱量詞的次序已無關(guān)緊要，因此可以省掉全稱量詞。但剩下的母式，仍假設(shè)其變元是被全稱量詞量化的。例如，上式消去全稱量詞后為

(﹁P(x,f(x))∨Q(x,g(x))∧(﹁P(x,f(x))∨﹁R(x,g(x)))第61頁，課件共80頁，創(chuàng)作于2023年2月2.子句集的化簡

(8)消去合取詞在母式中消去所有合取詞，把母式用子句集的形式表示出來。其中，子句集中的每一個元素都是一個子句。例如，上式的子句集中包含以下兩個子句

﹁P(x,f(x))∨Q(x,g(x))﹁P(x,f(x))∨﹁R(x,g(x))(9)更換變量名稱對子句集中的某些變量重新命名，使任意兩個子句中不出現(xiàn)相同的變量名。由于每一個子句都對應(yīng)著母式中的一個合取元，并且所有變元都是由全稱量詞量化的，因此任意兩個不同子句的變量之間實際上不存在任何關(guān)系。這樣，更換變量名是不會影響公式的真值的。例如，對前面的公式，可把第二個子句集中的變元名x更換為y，得到如下子句集

﹁P(x,f(x))∨Q(x,g(x))﹁P(y,f(y))∨﹁R(y,g(y))第62頁，課件共80頁，創(chuàng)作于2023年2月對于證明問題設(shè)F為前提的公式集，Q為目標公式集，用歸結(jié)反演證明的步驟：（1）否定Q，得到~Q

（2）把~Q加入到公式集F，得到{F，~Q}稱為S

（3）對S進行歸結(jié)，歸結(jié)到空子句為止。第63頁，課件共80頁，創(chuàng)作于2023年2月例：求證:G是F1和F2的邏輯推論

F1：F2:

G:

證明：化為子句集{P(a)(1)~R(y)∨L(a,y)(2)~P(x)∨~Q(y)∨~L(x,y)(3)R(b)(4)Q(b)(5)(2)(4)歸結(jié)L(a,b)(6)(1)(3)歸結(jié)~Q(y)∨~L(a,y)(7)(5)(7)~L(a,b)(8)(6)(8)NIL證畢。第64頁，課件共80頁，創(chuàng)作于2023年2月例題“快樂學生”問題假設(shè)任何通過計算機考試并獲獎的人都是快樂的，任何肯學習或幸運的人都可以通過所有的考試，張不肯學習但他是幸運的，任何幸運的人都能獲獎。求證：張是快樂的。

解：先將問題用謂詞表示如下：R1:“任何通過計算機考試并獲獎的人都是快樂的”

(x)((Pass(x,computer)∧Win(x,prize))→Happy(x))R2:“任何肯學習或幸運的人都可以通過所有考試”

(x)(y)(Study(x)∨Lucky(x)→Pass(x,y))R3:“張不肯學習但他是幸運的” ～Study(zhang)∧Lucky(zhang)R4:“任何幸運的人都能獲獎”

(x)(Luck(x)→Win(x,prize))結(jié)論：“張是快樂的”的否定～Happy(zhang)第65頁，課件共80頁，創(chuàng)作于2023年2月例題“快樂學生”問題由R1及邏輯轉(zhuǎn)換公式:P∧W→H=～（P∧W）∨H，可得

(1)～Pass(x,computer)∨～Win(x,prize)∨Happy(x)由R2：(2)～Study(y)∨Pass(y,z)(3)～Lucky(u)∨Pass(u,v)由R3：(4)～Study(zhang)(5)Lucky(zhang)由R4：(6)～Lucky(w)∨Win(w，prize)由結(jié)論：(7)～Happy(zhang) （結(jié)論的否定）(8)～Pass(w,computer)∨Happy(w)∨～Luck(w)(1)(6)，{w/x}(9)～Pass(zhang,computer)∨～Lucky(zhang)(8)(7)，{zhang/w}(10)

～Pass(zhang,computer) (9)(5)(11)

～Lucky(zhang) (10)(3)，{zhang/u,computer/v}(12)

?

(11)(5)

第66頁，課件共80頁，創(chuàng)作于2023年2月對于用歸結(jié)原理求取問題答案步驟：（1）把已知化為謂詞公式并轉(zhuǎn)化成子句集S(2)把待求解的問題用謂詞公式表示，并否定之，然后和謂詞ANSWER(x)構(gòu)成析取式，x代表問題的答案。（3）把第二步的析取式和S合并，構(gòu)成S’(4)對S’進行歸結(jié)（5）若歸結(jié)出ANSWER(x)，并且在x已經(jīng)被替代，被替代就是答案。第67頁，課件共80頁，創(chuàng)作于2023年2月已知：F1:李(li)先生是小趙(zhao)的老師；

F2:小趙(zhao)與小劉(liu)是同班同學；

F3:如果x與y是同班同學，則x的老師也是y的老師。定義的謂詞如下：

T(x，y)：表示x是y的老師；

C(x，y)：表示x與y是同班同學；求：小劉的老師是誰？解：把已知前提及待求解的問題表示成謂詞公式：

第68頁，課件共80頁，創(chuàng)作于2023年2月把上述公式化為子句集：（1）（2）（3）（4）應(yīng)用歸結(jié)原理進行歸結(jié)：（5）（1）和（3）歸結(jié)（4）和（5）歸結(jié)（2）和（6）歸結(jié)得知小劉的老師是李老師。第69頁，課件共80頁，創(chuàng)作于2023年2月第70頁，課件共80頁，創(chuàng)作于2023年2月歸結(jié)原理歸結(jié)法的實質(zhì)：歸結(jié)法是僅有一條推理規(guī)則的推理方法