謂詞邏輯與歸結(jié)原理

謂詞邏輯與歸結(jié)原理概述本章的內(nèi)容與目標(biāo)智能體如何認(rèn)識事物并且進(jìn)行推理用形式化的語言描述推理過程機(jī)器證明的一般方法—?dú)w結(jié)原理2第2頁,共180頁，2024年2月25日，星期天概述語言自然語言：人們在日常生活中所使用的語言文字半形式化語言：自然語言加特定的符號，如數(shù)學(xué)語言(定義、定理等)形式化語言：用精確的數(shù)學(xué)或機(jī)器可處理的公式定義的語言。(邏輯學(xué)語言，弗雷格Frege，1879)(p→q)∧(p→r)∧～

p∧～

r→～

p3第3頁,共180頁，2024年2月25日，星期天怪物洞穴人工智能的經(jīng)典實(shí)驗(yàn)環(huán)境—怪物洞穴(wumpus世界)洞穴有多個(gè)房間組成某個(gè)房間中藏著一只怪物wumpus，它會吃掉進(jìn)入這個(gè)房間的人，相鄰房間中能夠感覺到臭味某些房間中有陷阱，進(jìn)入房間會被陷阱吞噬，相鄰房間中能夠感覺到微風(fēng)游戲的主角是一個(gè)智能體，可以進(jìn)入相鄰的房間(對角線不可以)智能體有且僅有一支箭，用這支箭可以射殺怪物某個(gè)房間中有金子，游戲的目標(biāo)是智能體找到金子4第4頁,共180頁，2024年2月25日，星期天怪物洞穴智能體行動的關(guān)鍵是要根據(jù)獲得的信息推理，從而判斷哪個(gè)房間有怪物？哪個(gè)房間有陷阱？哪個(gè)房間是安全的？房間[4,2]和[2,3]有陷阱，房間[3,4]有怪物，房間[4,3]有金子5第5頁,共180頁，2024年2月25日，星期天3.1命題邏輯6第6頁,共180頁，2024年2月25日，星期天3.1命題邏輯命題—能夠判斷真假的陳述句陳述句真值唯一，可用二進(jìn)制表示用小寫字母進(jìn)行標(biāo)識例1、北京是中國的首都。2、華南師范大學(xué)位于崗頂附近。3、1+1=24、計(jì)算機(jī)系的學(xué)生必修C或JAVA。5、坐著花生過黃河5、x+1=26、吃飯了嗎？7、南無阿彌陀佛8、我正在說假話7第7頁,共180頁，2024年2月25日，星期天3.1命題邏輯簡單命題與復(fù)合命題簡單命題：(原子命題)一個(gè)命題無法分解為更簡單的子命題復(fù)合命題：由簡單命題用聯(lián)結(jié)詞聯(lián)結(jié)而成的命題

1、由若干簡單命題組成；2：由聯(lián)結(jié)詞聯(lián)結(jié)例：1、北京是中國的首都。2、華南師范大學(xué)位于崗頂附近。3、計(jì)算機(jī)系的學(xué)生必修C或JAVA。4、這家的報(bào)價(jià)單配置合理并且價(jià)格低廉。5、“李四是犯罪嫌疑人”“李四有犯罪動機(jī)”8第8頁,共180頁，2024年2月25日，星期天3.1命題邏輯合式公式：單個(gè)常量或者變量的命題構(gòu)成合式公式聯(lián)結(jié)詞聯(lián)結(jié)的合式公式的組合也是合式公式合式公式的有限次組合稱為命題公式命題公式：有限次合式公式組合的形式化描述，本書中以大寫字母標(biāo)識。9第9頁,共180頁，2024年2月25日，星期天3.1命題邏輯基本聯(lián)結(jié)(連接)符號～非，否定,﹁；∧與，合取，AND的首字母；∨或，析取，vel

→

蘊(yùn)含式A：a→b表示，如果a，則b；

?

等價(jià)聯(lián)結(jié)符號的優(yōu)先級～∧∨→

?10第10頁,共180頁，2024年2月25日，星期天3.1命題邏輯將命題從語言表述轉(zhuǎn)換為命題公式step1、找出簡單命題，并用符號表示step2、分析簡單命題間的邏輯關(guān)系，用聯(lián)結(jié)符號進(jìn)行描述例1、3不是偶數(shù)令：p表示“3是偶數(shù)”，~p2、教室里有30名男生和10名女生令：p表示“教室里有30名男生”，

q表示“教室里有10名女生”

p∧q3、如果天下雨，出門帶傘令p表示“天下雨”，q表示“出門帶傘”p→q4、只要不下雨，我就騎自行車上班令p表示“天下雨”，q表示“騎自行車上班”

~p→q5、只有不下雨，我才騎自行車上班令p表示“天下雨”，q表示“騎自行車上班”

q→~p11第11頁,共180頁，2024年2月25日，星期天3.1命題邏輯例：怪物洞穴如果房間[1,1]中有臭味，則房間[1,2]或[2,1]中有怪物表示房間[i,j]中有臭味表示房間[i,j]中有怪物

練習(xí)：如果房間[1,1]中沒有臭味，則房間[1,2]和[2,1]中沒有怪物12第12頁,共180頁，2024年2月25日，星期天3.1命題邏輯練習(xí)：掃雷游戲設(shè)Xi,j表示方格[i,j]中有一個(gè)地雷。寫出方格[1,1]周圍恰好有2顆地雷的命題公式12345……5432113第13頁,共180頁，2024年2月25日，星期天3.1命題邏輯命題公式的賦值對命題公式中的所有的命題變量各賦給一個(gè)值0，1。真值表pq~pp∧qp∨qp→qp?q0001101114第14頁,共180頁，2024年2月25日，星期天3.1命題邏輯復(fù)合命題的真值例：p:周杰倫是一個(gè)流行歌手q:人工智能是計(jì)算機(jī)科學(xué)的一個(gè)分支

r:牛在天上飛求下列復(fù)合命題的真值~p∧qp∧~q((~p∧q)∨(p∧~q))→r(q∨r)→(p→~r)p→~r(~p∨r)

(p∧~r)我們關(guān)心的是復(fù)合命題中命題之間的真值關(guān)系，而不關(guān)心命題的內(nèi)容。15第15頁,共180頁，2024年2月25日，星期天3.1命題邏輯命題公式的分類重言式或永真式tautology，設(shè)A為任一命題公式，若A在它的各種賦值下取值均為真，則稱A是重言式例：P∨~P矛盾式或永假式contradictory設(shè)A為任一命題公式，若A在它的各種賦值下取值均為假，則稱A是永假式。例：P∧~P16第16頁,共180頁，2024年2月25日，星期天3.1命題邏輯可滿足式satisfiable設(shè)A為任一命題公式，如果存在一組取值使A為真，則A為可滿足式。即：對于命題公式A，若A不是矛盾式，則稱A是可滿足式。例：P∧Q

非重言式的可滿足式既是可滿足式，又不是重言式17第17頁,共180頁，2024年2月25日，星期天3.1命題邏輯等值邏輯運(yùn)算<=>邏輯等值，等號連接的命題公式等價(jià)，≡基本等值算式P80交換律:

A∧B<=>B∧A；A∨B<=>B

∨

A；結(jié)合律:(A∧B)∧C<=>A∧(B∧C)；

(A∨B)∨C<=>A∨(B∨C)；*分配律:A∨(B∧C)<=>(A∨B)∧(A∨C)；

A∧(B∨C)<=>(A

∧

B)∨(A∧C)；雙重否定律：~~A<=>A；等冪律：A<=>A∧A；

A<=>A∨

A；*摩根律：~(A∨

B)<=>~A∧~B；

~(A∧B)<=>~A∨~B；18第18頁,共180頁，2024年2月25日，星期天3.1命題邏輯吸收律:

A∨(A∧B)<=>A；

A∧(A∨B)<=>A；同一律:A∨0<=>A；

A∧

1

<=>A；

零律:A∨1<=>1；

A∧

0

<=>0；

排中律：A∨~A

<=>1矛盾律：A∧~A

<=>0*蘊(yùn)含等值式：A→B<=>~A∨B；*等價(jià)等值式：A?B<=>(A→B)∧(B→A)；假言易位式：

A→B<=>~B→~

A

；等價(jià)否定等值式：A?B<=>~A?

~

B；歸謬論：(A→B)∧(A→~B)<=>~A；19第19頁,共180頁，2024年2月25日，星期天3.1命題邏輯合取范式與析取范式簡單析取式：有限個(gè)命題變元或其否定，析取聯(lián)結(jié)符

p∨q;~p∨q;p;q合取范式：有限個(gè)簡單析取式，合取

p∧(p∨q)∧(~p∨q)簡單合取式：有限個(gè)命題變元或其否定，合取

p∧q;~p∧q;p;q析取范式：有限個(gè)簡單合取式，析取

p∨(p∧q)∨(~p∧q)20第20頁,共180頁，2024年2月25日，星期天3.1命題邏輯任意命題公式都存在等值的析取范式和合取范式求取合取范式的步驟1、利用蘊(yùn)含等值式和等價(jià)等值式消去命題公式中除{~，∨，∧}以外的聯(lián)結(jié)詞2、利用摩根律、雙重否定律等進(jìn)行置換，將~移到括號里面3、利用分配律得到合取范式21第21頁,共180頁，2024年2月25日，星期天3.1命題邏輯例P82計(jì)算(p∧(

q→r))→s

的合取范式

(p∧(

q→r))→s<=>(p∧(~

q∨r))→s;

蘊(yùn)含等值式

<=>~

(p∧(~

q∨r))∨

s;

蘊(yùn)含等值式

<=>~

p∨~

(~

q∨r)∨

s;

摩根律

<=>~

p∨(~

~

q∧~r)∨

s;

摩根律

<=>~

p∨(

q∧~r)∨

s;

雙重否定律

<=>(~

p∨

s)

∨(

q∧~r);

交換律

<=>(

~

p∨

s∨q)∧(~

p∨

s∨~r);

分配律22第22頁,共180頁，2024年2月25日，星期天3.1命題邏輯例P82計(jì)算((p∨q)

→r)→p的合取范式

((p∨q)→r)→p<=>

(~(p∨q)

∨r)

→p；蘊(yùn)含等值式

<=>

~

(~(p∨q)∨r)∨p;

蘊(yùn)含等值式

<=>(

~

~(p∨q)∧~

r)∨p;

摩根律

<=>(

(p∨q)∧~

r)∨

p;雙重否定律

<=>(

p

∨q∨p)∧(~

r∨p)

;分配律

<=>(

p∨q)∧(~

r∨p)

;等冪律23第23頁,共180頁，2024年2月25日，星期天3.1命題邏輯課堂練習(xí)計(jì)算合取范式(p→q)∧~

(~q

→~

p)(~p∨q)∧~

q

∧

p24第24頁,共180頁，2024年2月25日，星期天3.1命題邏輯命題邏輯推理邏輯結(jié)論：如果A→B為重言式，則稱B是A的邏輯結(jié)論，記作A=>B。常用推理定律：附加：A=>(A

∨B)簡化：(A

∧

B)=>A假言推理：((A

→

B)∧A)=>B拒取式:((A

→

B)∧~B)=>~A析取三段論：((A

∨

B)∧~A)=>B假言三段論：((A

→

B)∧(B

→C))=>(A

→

C)等價(jià)三段論：((A

B)∧(B

C))=>(A

C)構(gòu)造型二難：(A

→

B)∧(C

→D)∧(

A

∨C

)

=>(B

∨D

)25第25頁,共180頁，2024年2月25日，星期天3.1命題邏輯命題邏輯推理規(guī)則前提引入規(guī)則任何證明的步驟上，都可以引入前提；結(jié)論引入規(guī)則任何證明的步驟上，所得到的結(jié)論都可以作為后續(xù)證明的前提；置換規(guī)則任何證明的步驟上，命題公式中任何子命題都可以用與之等值的命題公式置換；26第26頁,共180頁，2024年2月25日，星期天3.1命題邏輯例：P84

如果今天下雨，則要帶雨傘或雨衣。如果走路上班；則不帶雨衣。今天下雨，走路上班，證明要帶傘。解：

p:

今天下雨；q:帶雨傘；r:帶雨衣；s:走路上班

前提：p→(q∨r)；s→~r；p；s求證：q證明：1、p→(q∨r)，p

前提引入：

2、((p→(q∨r))∧

p)=>

q∨r假言推理：

3、s→~r，

s前提引入：

4、((s→~r)∧

s)=>~r假言推理：

5、((q∨r)∧

~r)=>

q析取三段論：27第27頁,共180頁，2024年2月25日，星期天3.1命題邏輯例怪物洞穴表示房間[i,j]中有臭味表示房間[i,j]中有怪物表示房間[i,j]中有微風(fēng)表示房間[i,j]中有陷阱28第28頁,共180頁，2024年2月25日，星期天3.1命題邏輯初始狀態(tài)，在房間[1,1]處沒有感覺到微風(fēng)，也沒有臭味，則相鄰房間為安全的，既沒有怪物也沒有陷阱。前提：

結(jié)論：證明：前提引入

等價(jià)等值式簡化前提引入拒取式摩根律29第29頁,共180頁，2024年2月25日，星期天3.1命題邏輯歸結(jié)原理證明的一般方法由已知條件正向推導(dǎo)結(jié)論，演繹推理假定結(jié)論不成立，逆向推導(dǎo)與已知條件矛盾，反證法命題邏輯證明的歸謬思想P85歸結(jié)原理的思想：如果證明A∧~B為永假式，則得證30第30頁,共180頁，2024年2月25日，星期天歸結(jié)推理命題邏輯謂詞邏輯Skolem標(biāo)準(zhǔn)形、子句集基本概念謂詞邏輯歸結(jié)原理合一和置換、控制策略數(shù)理邏輯命題邏輯歸結(jié)Herbrand定理31第31頁,共180頁，2024年2月25日，星期天3.1命題邏輯歸結(jié)方法的思想1、將待證明問題轉(zhuǎn)化為其逆命題例：條件A，求證B.即A→B

其逆命題為：

A∧~B2、求合取范式，得到子句集構(gòu)成合取范式的有限個(gè)簡單析取式構(gòu)成的集合就是子句集3、對子句集進(jìn)行歸結(jié)，得到空子句

32第32頁,共180頁，2024年2月25日，星期天3.1命題邏輯將待證明問題轉(zhuǎn)化為另一種形式證明問題的一般形式：已知：A成立求證：B成立即：證明A→BA→B<=>~A∨B蘊(yùn)含等值式

<=>~(A∧~B)摩根律

A∧~B如果退出矛盾，則結(jié)論成立33第33頁,共180頁，2024年2月25日，星期天3.1命題邏輯例：證明G是F的邏輯結(jié)論F1：P→WF2：~WG：~P分析：已知條件為：

(P→W)∧(~W)

結(jié)論為：~P

則，變換形式為：

(P→W)∧(~W)∧P34第34頁,共180頁，2024年2月25日，星期天3.1命題邏輯子句與子句集P86對問題的變換形式，求其合取范式對于一個(gè)合取范式，該范式中的每一條簡單析取式都是一個(gè)子句。子句集：合取范式下的所有子句構(gòu)成其子句集。例：p∧(p∨q)∧(~p∨q)子句集為

{p,p∨q,~p∨q}35第35頁,共180頁，2024年2月25日，星期天3.1命題邏輯歸結(jié)方法如果p∨q與~q∨r都為真，則p∨r為真證明1真值表pp∨qq~q~q∨rrp∨r1-----10110111證明2前提：(p∨q)∧(~q∨r)結(jié)論：p∨r證明:(p∨q)∧(~q∨r)<=>(~p→q)∧(q

→

r)蘊(yùn)含等值式與雙重否定律

=>(~p→r)假言三段論

<=>p∨r蘊(yùn)含等值式

36第36頁,共180頁，2024年2月25日，星期天3.1命題邏輯歸結(jié)式例{p∨q,~p∨q}歸結(jié)后為:{q}歸結(jié)的目標(biāo)—空子句對于一個(gè)合取范式，如果有一個(gè)子句不可滿足，則子句集就不可滿足，該合取范式為永假式若一個(gè)子句集中包含空子句，則這個(gè)子句集一定是不可滿足的例：{p,~p}歸結(jié)后為

{□}37第37頁,共180頁，2024年2月25日，星期天3.1命題邏輯歸結(jié)法步驟建立待歸結(jié)命題公式。將證明A→B為真轉(zhuǎn)化為證明A∧~B為矛盾式求合取范式，得到子句集對子句集進(jìn)行歸結(jié)歸結(jié)式作為新子句加入子句集進(jìn)行歸結(jié)當(dāng)歸結(jié)式為空子句□時(shí)停止，證明結(jié)束。出現(xiàn)空子句□，表示該子句集不可滿足歸結(jié)法的完備性：如果A→B成立，則利用歸結(jié)法一定可以得到證明38第38頁,共180頁，2024年2月25日，星期天3.1命題邏輯例：證明(p→q)→(~q

→~

p)證明：要證明原命題為真，只需證明(p→q)∧~

(~q

→~

p)為恒假

(p→q)∧~

(~q

→~

p)<=>(~p∨q)∧~

(q∨~

p)蘊(yùn)含等值式

<=>(~p∨q)∧~

q

∧

p

摩根律于是，子句集為:1~

p∨q2~

q

3

p{~

p∨q,~

q,

p}4~

p1、2歸結(jié)

5□3、4歸結(jié)由此可得:(p→q)∧~

(~q

→~

p)為恒假，原命題為真

{□,~p,

p,~p∨q,~q}{~p,

p,~p∨q,~q}39第39頁,共180頁，2024年2月25日，星期天3.1命題邏輯例：怪獸洞穴1、在房間[1,1]處沒有感覺到微風(fēng)，也沒有臭味。2、在房間[1,2]處感覺到微風(fēng)，但沒有感覺到臭味。3、在房間[2,1]處沒有感覺到微風(fēng)，但感覺到臭味。求證：房間[3,1]處有怪物*；房間[1,3]處有洞穴；房間[2,2]是安全的。40第40頁,共180頁，2024年2月25日，星期天3.1命題邏輯前提：求證：證明：要證明原命題為真，只需證明以下命題為恒假

41第41頁,共180頁，2024年2月25日，星期天3.1命題邏輯于是，得到子句集為：42第42頁,共180頁，2024年2月25日，星期天3.1命題邏輯1~s1,22~w1,13s2,14~s2,1∨w1,1∨w2,2∨w3,1

5s1,2∨~

w1,1

6s1,2∨~

w2,27~

w3,18

w1,1∨w2,2∨w3,1

3,4歸結(jié)

9w2,2∨w3,18,2歸結(jié)10w2,29,7歸結(jié)11s1,210,6歸結(jié)12□11,1歸結(jié)43第43頁,共180頁，2024年2月25日，星期天3.1命題邏輯思考：歸結(jié)算法的計(jì)算機(jī)實(shí)現(xiàn)？

{S0,S1,S2,S3…}

終止條件：

1、生成了空子句，證明結(jié)束

2、循環(huán)結(jié)束，沒有可以添加的新語句，待證明的定理不成立

44第44頁,共180頁，2024年2月25日，星期天3.1命題邏輯好的歸結(jié)控制策略初始狀態(tài)優(yōu)先選擇包含結(jié)論的子句進(jìn)行歸結(jié)，之后每次都選擇上一次歸結(jié)得到的歸結(jié)式與其他子句歸結(jié)容易犯的錯(cuò)誤字句集

1、P∨Q2、~P∨~Q3、□1、

2歸結(jié)3、Q∨~Q1、2歸結(jié)不允許同時(shí)歸結(jié)兩個(gè)項(xiàng)45第45頁,共180頁，2024年2月25日，星期天3.1命題邏輯歸結(jié)方法是一種機(jī)械化的,可在計(jì)算機(jī)上加以實(shí)現(xiàn)的推理方法歸結(jié)方法是一種反向推理形式提供了一種自動定理證明的方法歸結(jié)的半完備性當(dāng)定理可以證明時(shí)，歸結(jié)方法是完備的當(dāng)定理不可證明時(shí)，歸結(jié)方法得不到任何結(jié)論，算法不一定會停止46第46頁,共180頁，2024年2月25日，星期天3.2謂詞邏輯47第47頁,共180頁，2024年2月25日，星期天3.2.1基本概念命題邏輯描述簡單的陳述性命題，但表示量化和謂詞過于繁瑣，也難以表示個(gè)體間的關(guān)系例：現(xiàn)在課堂上的所有學(xué)生都在上人工智能課命題邏輯s1:張三在上人工智能課s2:李四在上人工智能課s3:王五在上人工智能課

………例2：用命題邏輯歸結(jié)原理證明：“人都是媽生的，張飛是人，所以張飛是媽生的”p:人都是媽生的q:張飛是人r:張飛是媽生的(p∧q)→r

p∧q∧~r48第48頁,共180頁，2024年2月25日，星期天3.2.1基本概念謂詞邏輯Class(x)表示x在上人工智能課

x=張三，就得到了s1；

x=李四，就得到了s2；

x=王五，就得到了s3；

Class(x,y)表示x在上y課x=張三，y=人工智能，表示張三在上人工智能課x=李四，y=線性代數(shù)，表示李四在上線性代數(shù)課x=王五，y=睡覺，表示王五在上睡覺課49第49頁,共180頁，2024年2月25日，星期天3.2.1基本概念命題是一個(gè)陳述句，它一般可分成主語和謂語兩部分。有時(shí)還需要用到量詞。主語：指獨(dú)立存在的客體，可以是具體事物或抽象概念，也稱為個(gè)體謂詞：描述個(gè)體詞性質(zhì)或個(gè)體之間關(guān)系的詞個(gè)體域：表示個(gè)體變量的取值范圍，常用D表示常量：表示具體性質(zhì)或關(guān)系的個(gè)體或者謂詞變量：表示抽象或泛指的個(gè)體或者謂詞。量詞：表示數(shù)量的詞。任意量詞?：表示“任意”，“所有”，也稱為全稱量詞存在量詞?：表示“存在”50第50頁,共180頁，2024年2月25日，星期天3.2.1基本概念例：“關(guān)羽是人”，“張飛是人”這是兩個(gè)不同的命題，其主語(個(gè)體)不同但是謂詞是相同的，“是人”把謂語部分抽出來，假設(shè)Human(x)表示x是人這兩個(gè)命題都可以用這個(gè)謂詞來描述

Human(guanyu)Human(zhangfei)其中x屬于個(gè)體變量，guanyu和zhangfei屬于個(gè)體常量51第51頁,共180頁，2024年2月25日，星期天3.2.1基本概念例：1、所有的人都是要死的2、有的人能夠活到100歲

P(x)表示x是要死的，Q(x)表示x活到100歲個(gè)體域D為人類集合個(gè)體域D為總個(gè)體域集合引入特殊謂詞R(x)表示x是人52第52頁,共180頁，2024年2月25日，星期天3.2.1基本概念語言描述轉(zhuǎn)換為謂詞公式1、確定并說明謂詞2、確定個(gè)體和個(gè)體域3、確定量詞4、判斷謂詞間的邏輯關(guān)系53第53頁,共180頁，2024年2月25日，星期天3.2.1基本概念例：我是計(jì)算機(jī)系的學(xué)生1、確定并說明謂詞：方法一：Student(x,y)表示X是Y系的學(xué)生2、個(gè)體域：X：學(xué)生的集合，y：系的集合

Student(I,computer)

方法二：Computer(x)表示X是計(jì)算機(jī)系的學(xué)生

Computer(I)

注意：必須對謂詞進(jìn)行說明

P(I,computer)54第54頁,共180頁，2024年2月25日，星期天3.2.1基本概念1、定義并說明謂詞

Unlike(x,y)表示

x不喜歡y課2、個(gè)體域

x學(xué)生的集合，

y課程的集合3、量詞存在例：有學(xué)生不喜歡上人工智能課Like(x,y)表示x喜歡y課Student(x)表示x是學(xué)生Like(x,y)表示x喜歡y課個(gè)體域x：人的集合邏輯關(guān)系：與55第55頁,共180頁，2024年2月25日，星期天3.2.1基本概念例：任何人的兄弟都是男性確定并說明謂詞Brother(x,y)表示x是y的兄弟Male(x)表示x是男性個(gè)體域

Brother(x,y)x、y：人的集合

Male(x)x：人的集合量詞任意確定邏輯關(guān)系與？或？非？蘊(yùn)含？等價(jià)？

56第56頁,共180頁，2024年2月25日，星期天3.2.1基本概念例：不管黑貓白貓，抓住老鼠就是好貓定義并說明謂詞

Cat(x,y)表示是x是y顏色的貓

Goodcat(x)表示x是好貓

Catch(x,Mouse)表示x能抓住老鼠個(gè)體域

x:貓的集合，y：顏色的集合謂詞間的關(guān)系

Cat(x,y)與Catch(x,Mouse)蘊(yùn)含Goodcat(x)量詞：任意57第57頁,共180頁，2024年2月25日，星期天3.2.1基本概念量詞使用中的注意事項(xiàng)不同的個(gè)體域中，命題符號化的形式可能不同沒有給定個(gè)體域的情況下，應(yīng)考慮全總個(gè)體域如果個(gè)體域?yàn)橛邢藜?，對任意謂詞P(x)有：多個(gè)量詞同時(shí)出現(xiàn)時(shí)，不能顛倒其先后順利，否則會改變公式的含義。58第58頁,共180頁，2024年2月25日，星期天3.2.1基本概念例：love(x,y)表示x喜愛y

表示對任意的x，都存在喜愛的對象y，即“每一個(gè)人都會喜愛某人”表示存在都一個(gè)y，任意的人x都喜愛他，即“上帝”O(jiān)R“大眾……”

59第59頁,共180頁，2024年2月25日，星期天3.2.2一階謂詞邏輯原子公式：設(shè)是任意n元謂詞，是項(xiàng)，則稱為原子公式。項(xiàng)：任何常量是項(xiàng)。任何變量是項(xiàng)。n≥1個(gè)參數(shù)的任何表達(dá)式(其中，是項(xiàng)，而f

是n

階的函數(shù))是項(xiàng)。閉包條款：其他東西都不是項(xiàng)。

60第60頁,共180頁，2024年2月25日，星期天3.2.2一階謂詞邏輯謂詞公式原子公式是謂詞公式。若A為謂詞公式，則～A也是一個(gè)謂詞公式。若A和B都是謂詞公式，則(A∧B)，(A∨B)，(A→B)和(AB)也都是謂詞公式。若A是謂詞公式，和也都是謂詞公式。只有有限次應(yīng)用上述規(guī)則得到的公式，才是謂詞公式。61第61頁,共180頁，2024年2月25日，星期天3.2.2一階謂詞邏輯對于，x稱為指導(dǎo)變量

A稱為相應(yīng)量詞的轄域

?x(p(x))x在轄域A中的出現(xiàn)稱為約束出現(xiàn)x以外的變量在轄域A中的出現(xiàn)稱為自由出現(xiàn)?x(p(x,y))62第62頁,共180頁，2024年2月25日，星期天對于，指導(dǎo)變量：?的轄域：

x,

y都是約束出現(xiàn)3.2.2一階謂詞邏輯例對于，指導(dǎo)變量:?的轄域:

x、y是約束出現(xiàn)還是自由出現(xiàn)

y是約束出現(xiàn)，

x是自由出現(xiàn)63第63頁,共180頁，2024年2月25日，星期天3.2.2一階謂詞邏輯不同量詞如果采用相同的指導(dǎo)變量名，易引起混淆一般要求不同的量詞使用不同的指導(dǎo)變量名稱64第64頁,共180頁，2024年2月25日，星期天3.2.2一階謂詞邏輯當(dāng)在一個(gè)公式中，一個(gè)變量符號既是約束出現(xiàn)的變量，又是自由出現(xiàn)的變量時(shí)，需要作變量符號更換。換名規(guī)則：將量詞轄域中某個(gè)約束出現(xiàn)的變量及其指導(dǎo)變量替換為此轄域中未出現(xiàn)過的個(gè)體變量符號

x既作為指導(dǎo)變量約束出現(xiàn)又自由出現(xiàn)，因此要換掉其中之一換名規(guī)則更換的是指導(dǎo)變量可替換為65第65頁,共180頁，2024年2月25日，星期天3.2.2一階謂詞邏輯替代規(guī)則：對某自由出現(xiàn)的個(gè)體變量用與原公式中未出現(xiàn)過的變量符號去替代，且處處替代。

x既作為指導(dǎo)變量約束出現(xiàn)又自由出現(xiàn)，且多處自由出現(xiàn)替代規(guī)則更換的是自由出現(xiàn)的變量，且處處替代替換為66第66頁,共180頁，2024年2月25日，星期天3.2.2一階謂詞邏輯謂詞公式的解釋對謂詞公式中的各種變量制定具體的常量去替代一個(gè)解釋包括非空個(gè)體域D

D中一部分特定元素；

D上一些特定的函數(shù)；

D上一些特定的謂詞。如果謂詞公式在特定解釋下為真，稱這個(gè)解釋滿足這個(gè)謂詞公式，是這個(gè)謂詞公式的一個(gè)模型永真與不可滿足67第67頁,共180頁，2024年2月25日，星期天3.2.2一階謂詞邏輯例：P92

給定解釋I如下

個(gè)體域:

函數(shù)f(x):f(2)=3,f(3)=2

謂詞：P(x)為P(2)=0,P(3)=1

Q(x,y)為Q(i,j)=1,i,j=2,3

R(x,y)為R(2,2)=R(3,3)=1，R(2,3)=R(3,2)=0

求解釋I下，下列謂詞公式的真值

1、

2、68第68頁,共180頁，2024年2月25日，星期天3.2.2一階謂詞邏輯解1、

=>

(P(f(2))∧Q(2,f(2)))∨(P(f(3))∧Q(3,f(3)))=>(P()∧Q(2,

))∨(P(

)∧Q(3,

))=>(1∧1)∨(0∧1)=>12、

=>

=>(R(2,2)∨R(2,3))∧(R(3,2)∨R(3,3))=>(1∨0)∧(0∨1)=>169第69頁,共180頁，2024年2月25日，星期天3.2.3謂詞演算與推理謂詞演算公式約束變量換名規(guī)則，Q為任意量詞

(Qx)P(x)<=>(Qy)P(y)(Qx)P(x,z)<=>(Qy)P(y,z)量詞消去等值式，對于有窮個(gè)體域量詞否定等值式量詞分配等值式70第70頁,共180頁，2024年2月25日，星期天3.2.3謂詞演算與推理量詞轄域收縮與擴(kuò)張等值式71第71頁,共180頁，2024年2月25日，星期天3.2.3謂詞演算與推理前束范式—約束在前面的范式將所有的量詞都移到最左邊就得到了前束范式與合取范式類似，所有的謂詞公式都可以改寫成前束范式的形式求前束范式的步驟前束范式中每個(gè)量詞的指導(dǎo)變量不同，如果指導(dǎo)變量相同，則需要利用換名規(guī)則進(jìn)行替換。如果自由變量與指導(dǎo)變量相同，則需利用換名規(guī)則或替代規(guī)則替換其中之一利用量詞轄域收縮擴(kuò)張等值式替換72第72頁,共180頁，2024年2月25日，星期天3.2.3謂詞演算與推理例P94求前束范式量詞與指導(dǎo)變量：，自由出現(xiàn)的變量：，

換名規(guī)則替代規(guī)則

P933-7

73第73頁,共180頁，2024年2月25日，星期天3.2.3謂詞演算與推理

P933-8

P933-3

P933-474第74頁,共180頁，2024年2月25日，星期天3.2.3謂詞演算與推理謂詞推理例：20世紀(jì)70年代的漫畫都是日本漫畫家創(chuàng)作的，這幅漫畫是20世紀(jì)70年代的作品；因此它是日本漫畫家的作品解：設(shè)P(x)：屬于20世紀(jì)70年代的漫畫

Q(y)：屬于日本漫畫家的作品

a:一幅漫畫前提:

結(jié)論:Q(a)

證明:

前提引入量詞消去前提引入假言推理75第75頁,共180頁，2024年2月25日，星期天3.2.4謂詞知識表示謂詞邏輯表達(dá)的規(guī)范形式P是謂詞，而表示個(gè)體(主體或者客體)知識庫：表達(dá)知識的一組謂詞公式的集合。語句的集合對環(huán)境、規(guī)則等信息的結(jié)構(gòu)化描述基于知識的智能體的核心構(gòu)件76第76頁,共180頁，2024年2月25日，星期天3.2.4謂詞知識表示定義謂詞例1、小李與小張打網(wǎng)球

Play(x,y,z)表示x,y在進(jìn)行z運(yùn)動

Play(Li,Zhang,tennis)

2、我在華南師范大學(xué)當(dāng)教師

Work(x,y,z)表示x在y單位從事z工作

Work(Me,Scnu,teacher)

3、怪物洞穴中某個(gè)房間有微風(fēng)、有臭味、沒有怪物、沒有陷阱、沒有金子

Roomi,j

(x,y,z,m,n)參數(shù)分別對應(yīng)有沒有微風(fēng)、臭味、怪物、陷阱、金子

Roomi,j(1,1,0,0,0)77第77頁,共180頁，2024年2月25日，星期天783.2.4謂詞知識表示謂詞比命題更加細(xì)致地刻畫知識：表達(dá)能力強(qiáng)如：北京是個(gè)城市，City(x)

把城市這個(gè)概念分割出來。把“城市”與“北京”兩個(gè)概念連接在一起，而且說明“北京”是“城市”的子概念。(有層)謂詞可以代表變化的情況如：City(北京),真。City(煤球)，假在不同的知識之間建立聯(lián)系……….第78頁,共180頁，2024年2月25日，星期天793.2.4謂詞知識表示在不同的知識之間建立聯(lián)系如：Human(x)→Lawed(x)，人人都受法律管制，x是同一個(gè)人。

Commit(x)→Punished(x)，x不一定是人也可以是動物。 而，{[Human(x)→Lawed(x)]→[commit(x)→Punished(x)]}， 意為如果由于某個(gè)x是人而受法律管制，則這個(gè)人犯了罪就一定要受到懲罰。第79頁,共180頁，2024年2月25日，星期天803.2.4謂詞知識表示謂詞邏輯法是應(yīng)用最廣的方法之一，其原因是：謂詞邏輯與數(shù)據(jù)庫，特別是關(guān)系數(shù)據(jù)庫就有密切的關(guān)系。在關(guān)系數(shù)據(jù)庫中，邏輯代數(shù)表達(dá)式是謂詞表達(dá)式之一。因此，如果采用謂詞邏輯作為系統(tǒng)的理論背景，則可將數(shù)據(jù)庫系統(tǒng)擴(kuò)展改造成知識庫。一階謂詞邏輯具有完備的邏輯推理算法。如果對邏輯的某些外延擴(kuò)展后，則可把大部分的知識表達(dá)成一階謂詞邏輯的形式。(知識易表達(dá))………..第80頁,共180頁，2024年2月25日，星期天813.2.4謂詞知識表示謂詞邏輯法是應(yīng)用最廣的方法之一，其原因是：謂詞邏輯本身具有比較扎實(shí)的數(shù)學(xué)基礎(chǔ)，知識的表達(dá)方式?jīng)Q定了系統(tǒng)的主要結(jié)構(gòu)。因此，對知識表達(dá)方式的嚴(yán)密科學(xué)性要求就比較容易得到滿足。這樣對形式理論的擴(kuò)展導(dǎo)致了整個(gè)系統(tǒng)框架的發(fā)展。邏輯推理是公理集合中演繹而得出結(jié)論的過程。由于邏輯及形式系統(tǒng)具有的重要性質(zhì)，可以保證知識庫中新舊知識在邏輯上的一致性(或通過相應(yīng)的一套處理過程檢驗(yàn))、和所演繹出來的結(jié)論的正確性。而其它的表示方法在這點(diǎn)上還不能與其相比。第81頁,共180頁，2024年2月25日，星期天823.2.4謂詞知識表示

用邏輯(謂詞)表示知識實(shí)質(zhì)上是把人類關(guān)于世界的認(rèn)識變成一個(gè)包含個(gè)體、函數(shù)和謂詞的概念化形式。基本步驟：給出有關(guān)世界的個(gè)體、函數(shù)和謂詞構(gòu)造一階謂詞公式(集)對公式(集)給出解釋，使該解釋是相應(yīng)公式(集)的一個(gè)模型。第82頁,共180頁，2024年2月25日，星期天833.2.4謂詞知識表示

為此邏輯表示法在實(shí)際人工智能系統(tǒng)上得到應(yīng)用。

第83頁,共180頁，2024年2月25日，星期天3.2.4謂詞知識表示例：準(zhǔn)前女友雙眼皮,大眼睛doublefold(x)∧bigeyes(x)一頭烏黑的頭發(fā)blackhair(x)∧thickhair(x)一身漂亮的呢子大衣beautifuldress(x)走路的姿態(tài)賽過模特graceful(x)84第84頁,共180頁，2024年2月25日，星期天853.2.4謂詞知識表示例：一個(gè)房間里，有一機(jī)器人Robot，一個(gè)積木塊Box，兩個(gè)桌子A和B， 怎樣用邏輯法描述從初始狀態(tài)到目標(biāo)狀態(tài)的機(jī)器人操作過程？先引入謂詞：

Table(A) 表示A是桌子

EmptyHanded(Robot)機(jī)器人Robot雙手空空

At(Robot,A) 表示機(jī)器人Robot在A旁

Holds(Robot,Box) 機(jī)器人Robot拿著Box On(Box,A) 積木塊Box在A上第85頁,共180頁，2024年2月25日，星期天863.2.4謂詞知識表示設(shè)定初始狀態(tài)：

EmptyHanded(Robot) On(Box,A) Table(A) Table(B)目標(biāo)狀態(tài)是：

EmptyHanded(Robot) On(Box,B) Table(A) Table(B)第86頁,共180頁，2024年2月25日，星期天87例(續(xù))機(jī)器人的每個(gè)操作的結(jié)果所引起的狀態(tài)變化，可用對原狀態(tài)的增添表和刪除表來表示。如機(jī)器人有初始狀態(tài)是把Box從A桌移到B桌上，然后仍回到Alcove，這時(shí)同初始狀態(tài)相比有： 增添表 On(Box，B) 刪除表 On(Box，A)又如機(jī)器人從初始狀態(tài)，走近A桌，然后拿起B(yǎng)ox。這時(shí)同初始狀態(tài)相比有： 增添表 At(Robot，A) Holds(Robot，Box)

刪除表 At(Robot，Alcove)

EmptyHanded(Robot) On(Box，A)第87頁,共180頁，2024年2月25日，星期天88例(續(xù))進(jìn)一步說，機(jī)器人的每一操作還需要先決條件。如機(jī)器人拿起A桌上的Box這一操作，先決條件：

On(Box，A)(Box在A上)

At(Robot，A)(機(jī)器人在A旁邊)

EmptyHanded(robot)(機(jī)器人手空空)第88頁,共180頁，2024年2月25日，星期天89例(續(xù))先決條件成立與否的驗(yàn)證可以使用歸結(jié)法。如將初始狀態(tài)視作已知條件，而將要驗(yàn)證的先決條件作為結(jié)論，便可使用歸結(jié)法了。歸結(jié)過程如下：1)At(Robot,A)2)EmptyHanded(Robot)3)On(Box,A)4)Table(A)5)Table(B)6)～On(Box,A)∨～At(Robot,A)∨～EmptyHanded(Robot)(先決條件之否定)7)～At(Robot,A)∨～EmptyHanded(Robot) 3，68)～EmptyHanded(Robot) 1，79)NULL 2，8于是驗(yàn)證了先決條件的成立。第89頁,共180頁，2024年2月25日，星期天903.2.4謂詞知識表示

存在問題： 謂詞表示越細(xì)，推力越慢、效率越低，但表示清楚。實(shí)際中是要折衷的。第90頁,共180頁，2024年2月25日，星期天3.3謂詞邏輯歸結(jié)原理91第91頁,共180頁，2024年2月25日，星期天3.3.1歸結(jié)原理命題邏輯歸結(jié)原理：將由前提A得到結(jié)論B的證明過程轉(zhuǎn)化為證明A∧~B為矛盾式將其轉(zhuǎn)化為合取范式，得到子句集

對于形如的公式求取子句集時(shí)，可以分別求各自的子句集，再取并集利用歸結(jié)原理消去互補(bǔ)項(xiàng)，直到得到空子句。

92第92頁,共180頁，2024年2月25日，星期天3.3.1歸結(jié)原理例(P→(Q→R))→

((P→Q)

→(P→R))

轉(zhuǎn)化為待歸結(jié)命題公式：(P→(Q→R))∧~((P→Q)

→(P→R))求子句集:分別對(P→(Q→R))和~((P→Q)→(P→R))兩部分求取子句集，再取并集1、(P→(Q→R))<=>(~P∨(~Q∨R))<=>(~P∨~Q∨R)

2、~((P→Q)

→(P→R))<=>~(~(~P∨Q)∨(~P∨R))<=>~((P∧~Q)∨(~P∨R))<=>(~(P∧~Q)∧~(~P∨R))<=>((~P∨Q)∧(P∧

~R))子句集為：{~P∨~Q∨R,~P∨Q,P,~R}93第93頁,共180頁，2024年2月25日，星期天3.3.1歸結(jié)原理歸結(jié)：

1、

~P∨~Q∨R

2、~P∨Q

3、P

4、~R

5、~P∨R1、2歸結(jié)

6、R3、5歸結(jié)

7、□4、6歸結(jié)因此得證94子句集為：{~P∨~Q∨R,~P∨Q,P,~R}第94頁,共180頁，2024年2月25日，星期天3.3.1歸結(jié)原理步驟命題邏輯歸結(jié)原理謂詞邏輯歸結(jié)原理1、建立A∧~B命題邏輯公式謂詞邏輯公式2、求子句集求合取范式求前束合取范式消去量詞3、歸結(jié)直接消去互補(bǔ)項(xiàng)利用置換與合一消去互補(bǔ)項(xiàng)歸結(jié)式加入子句集歸結(jié)式加入子句集95第95頁,共180頁，2024年2月25日，星期天3.3.1歸結(jié)原理謂詞邏輯歸結(jié)原理的重點(diǎn)如何對前束合取范式消去量詞命題邏輯謂詞邏輯如何利用置換與合一對不同變量的子句進(jìn)行置換命題邏輯謂詞邏輯96第96頁,共180頁，2024年2月25日，星期天3.3.1歸結(jié)原理求前束合取范式：方法一：先轉(zhuǎn)化為前束范式，再將轄域中的謂詞公式轉(zhuǎn)化為合取范式方法二：(1)消去聯(lián)結(jié)詞→和?。(2)將聯(lián)結(jié)詞~向內(nèi)深入，使之只作用于原子公式。(3)利用換名或替代規(guī)則使所有約束變元的符號都不同，并且自由變元與約束變元的符號也不同。(4)利用量詞轄域的擴(kuò)張和收縮，擴(kuò)大量詞至整個(gè)公式。(5)再將轄域中的謂詞公式轉(zhuǎn)化為合取范式。97第97頁,共180頁，2024年2月25日，星期天3.2.3謂詞演算與推理量詞轄域收縮與擴(kuò)張等值式98第98頁,共180頁，2024年2月25日，星期天3.2.3謂詞演算與推理求前束合取范式

(x)P(x)→

Q(x)

~(x)P(x)∨

Q

(x)

(x)(~P(x))∨

Q(x)

(x)(~P(x))

∨

Q(y)

(x)(~P(x)∨

Q(y))

(x)(~P(x)∨

Q(y))1、消去→和?2、~向內(nèi)深入3、換名或替代4、量詞前束5、轄域中的公式化為合取范式99第99頁,共180頁，2024年2月25日，星期天3.3.2Skolem標(biāo)準(zhǔn)型例求前束合取范式

100第100頁,共180頁，2024年2月25日，星期天3.3.2Skolem標(biāo)準(zhǔn)型Skolem標(biāo)準(zhǔn)型：對前束合取范式消去所有的量詞。P100第一步：消去存在量詞

：1、如果

之前(左邊)沒有任意量詞

,則用常量替換

的指導(dǎo)變量可用常量b替換x消去存在量詞，得P(b,a)2、如果

之前(左邊)有任意量詞

，則用任意量詞的函數(shù)替換

的指導(dǎo)變量可用f(x)替換y消去存在量詞，第二步消去任意量詞

：簡單的省略即可101第101頁,共180頁，2024年2月25日，星期天3.3.2Skolem標(biāo)準(zhǔn)型例：1、消去存在量詞

y和

u

：

y前面有任意量詞，指導(dǎo)變量為x，因此用f(x)替換y，

u前面有任意量詞，指導(dǎo)變量為x，因此用g(x)替換u2、消去任意量詞：102第102頁,共180頁，2024年2月25日，星期天3.3.2Skolem標(biāo)準(zhǔn)型例判斷下列的消去量詞的過程是否正確。證明：①

x

y

G(x,y)②y

G(x,y)消去x

③G(x,

a)消去y對任意x，都存在一個(gè)恒定常量a，使G(x,

a)成立

①

x

y

G(x,y)②x

G(x,f(x))消去y③G(x,f(x))消去x對任意x，都存在一個(gè)與之對應(yīng)的f(x)，使G(x,

f(x))成立103第103頁,共180頁，2024年2月25日，星期天3.3.3子句集定義文字：不含任何聯(lián)結(jié)詞的謂詞公式子句：一些文字或其非的析取子句集：所有子句的集合計(jì)算過程將謂詞公式轉(zhuǎn)化為前束合取范式消去存在量詞，略去任意量詞，得Skolem標(biāo)準(zhǔn)型將各子句提出，得到子句集謂詞公式不可滿足，當(dāng)且僅當(dāng)其子句集不可滿足的形如的謂詞公式在求子句集時(shí)可以分別對求子句，再取其并集104第104頁,共