謂詞邏輯與歸結原理

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

p∧～

r→～

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

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

→

蘊含式A：a→b表示，如果a，則b；

?

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

?10第10頁,共180頁，2024年2月25日，星期天3.1命題邏輯將命題從語言表述轉換為命題公式step1、找出簡單命題，并用符號表示step2、分析簡單命題間的邏輯關系，用聯(liá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]中有怪物

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

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

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

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

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

∨

A；結合律:(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*蘊含等值式：A→B<=>~A∨B；*等價等值式：A?B<=>(A→B)∧(B→A)；假言易位式：

A→B<=>~B→~

A

；等價否定等值式：A?B<=>~A?

~

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

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

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

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

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

q→r))→s

的合取范式

(p∧(

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

q∨r))→s;

蘊含等值式

<=>~

(p∧(~

q∨r))∨

s;

蘊含等值式

<=>~

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計算((p∨q)

→r)→p的合取范式

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

(~(p∨q)

∨r)

→p；蘊含等值式

<=>

~

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

蘊含等值式

<=>(

~

~(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命題邏輯課堂練習計算合取范式(p→q)∧~

(~q

→~

p)(~p∨q)∧~

q

∧

p24第24頁,共180頁，2024年2月25日，星期天3.1命題邏輯命題邏輯推理邏輯結論：如果A→B為重言式，則稱B是A的邏輯結論，記作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)等價三段論：((A

B)∧(B

C))=>(A

C)構造型二難：(A

→

B)∧(C

→D)∧(

A

∨C

)

=>(B

∨D

)25第25頁,共180頁，2024年2月25日，星期天3.1命題邏輯命題邏輯推理規(guī)則前提引入規(guī)則任何證明的步驟上，都可以引入前提；結論引入規(guī)則任何證明的步驟上，所得到的結論都可以作為后續(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]中有微風表示房間[i,j]中有陷阱28第28頁,共180頁，2024年2月25日，星期天3.1命題邏輯初始狀態(tài)，在房間[1,1]處沒有感覺到微風，也沒有臭味，則相鄰房間為安全的，既沒有怪物也沒有陷阱。前提：

結論：證明：前提引入

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

其逆命題為：

A∧~B2、求合取范式，得到子句集構成合取范式的有限個簡單析取式構成的集合就是子句集3、對子句集進行歸結，得到空子句

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

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

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

(P→W)∧(~W)

結論為：~P

則，變換形式為：

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

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

→

r)蘊含等值式與雙重否定律

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

<=>p∨r蘊含等值式

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

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

→~

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

(~q

→~

p)為恒假

(p→q)∧~

(~q

→~

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

(q∨~

p)蘊含等值式

<=>(~p∨q)∧~

q

∧

p

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

p∨q2~

q

3

p{~

p∨q,~

q,

p}4~

p1、2歸結

5□3、4歸結由此可得:(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]處沒有感覺到微風，也沒有臭味。2、在房間[1,2]處感覺到微風，但沒有感覺到臭味。3、在房間[2,1]處沒有感覺到微風，但感覺到臭味。求證：房間[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歸結

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

{S0,S1,S2,S3…}

終止條件：

1、生成了空子句，證明結束

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

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

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

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

………例2：用命題邏輯歸結原理證明：“人都是媽生的，張飛是人，所以張飛是媽生的”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基本概念命題是一個陳述句，它一般可分成主語和謂語兩部分。有時還需要用到量詞。主語：指獨立存在的客體，可以是具體事物或抽象概念，也稱為個體謂詞：描述個體詞性質或個體之間關系的詞個體域：表示個體變量的取值范圍，常用D表示常量：表示具體性質或關系的個體或者謂詞變量：表示抽象或泛指的個體或者謂詞。量詞：表示數(shù)量的詞。任意量詞?：表示“任意”，“所有”，也稱為全稱量詞存在量詞?：表示“存在”50第50頁,共180頁，2024年2月25日，星期天3.2.1基本概念例：“關羽是人”，“張飛是人”這是兩個不同的命題，其主語(個體)不同但是謂詞是相同的，“是人”把謂語部分抽出來，假設Human(x)表示x是人這兩個命題都可以用這個謂詞來描述

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

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

Student(I,computer)

方法二：Computer(x)表示X是計算機系的學生

Computer(I)

注意：必須對謂詞進行說明

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

Unlike(x,y)表示

x不喜歡y課2、個體域

x學生的集合，

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

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

Male(x)x：人的集合量詞任意確定邏輯關系與？或？非？蘊含？等價？

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

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

Goodcat(x)表示x是好貓

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

x:貓的集合，y：顏色的集合謂詞間的關系

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

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

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

是n

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

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

A稱為相應量詞的轄域

?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日，星期天對于，指導變量：?的轄域：

x,

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

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

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

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

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

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

D中一部分特定元素；

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

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

給定解釋I如下

個體域:

函數(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)量詞消去等值式，對于有窮個體域量詞否定等值式量詞分配等值式70第70頁,共180頁，2024年2月25日，星期天3.2.3謂詞演算與推理量詞轄域收縮與擴張等值式71第71頁,共180頁，2024年2月25日，星期天3.2.3謂詞演算與推理前束范式—約束在前面的范式將所有的量詞都移到最左邊就得到了前束范式與合取范式類似，所有的謂詞公式都可以改寫成前束范式的形式求前束范式的步驟前束范式中每個量詞的指導變量不同，如果指導變量相同，則需要利用換名規(guī)則進行替換。如果自由變量與指導變量相同，則需利用換名規(guī)則或替代規(guī)則替換其中之一利用量詞轄域收縮擴張等值式替換72第72頁,共180頁，2024年2月25日，星期天3.2.3謂詞演算與推理例P94求前束范式量詞與指導變量：，自由出現(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世紀70年代的漫畫都是日本漫畫家創(chuàng)作的，這幅漫畫是20世紀70年代的作品；因此它是日本漫畫家的作品解：設P(x)：屬于20世紀70年代的漫畫

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

a:一幅漫畫前提:

結論:Q(a)

證明:

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

Play(x,y,z)表示x,y在進行z運動

Play(Li,Zhang,tennis)

2、我在華南師范大學當教師

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

Work(Me,Scnu,teacher)

3、怪物洞穴中某個房間有微風、有臭味、沒有怪物、沒有陷阱、沒有金子

Roomi,j

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

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

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

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

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

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

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

Table(A) 表示A是桌子

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

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

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

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

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

刪除表 At(Robot，Alcove)

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

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

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

EmptyHanded(robot)(機器人手空空)第88頁,共180頁，2024年2月25日，星期天89例(續(xù))先決條件成立與否的驗證可以使用歸結法。如將初始狀態(tài)視作已知條件，而將要驗證的先決條件作為結論，便可使用歸結法了。歸結過程如下：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于是驗證了先決條件的成立。第89頁,共180頁，2024年2月25日，星期天903.2.4謂詞知識表示

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

對于形如的公式求取子句集時，可以分別求各自的子句集，再取并集利用歸結原理消去互補項，直到得到空子句。

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

((P→Q)

→(P→R))

轉化為待歸結命題公式：(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歸結原理歸結：

1、

~P∨~Q∨R

2、~P∨Q

3、P

4、~R

5、~P∨R1、2歸結

6、R3、5歸結

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

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

：1、如果

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

,則用常量替換

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

之前(左邊)有任意量詞

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

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

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

y和

u

：

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

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

x

y

G(x,y)②y

G(x,y)消去x

③G(x,

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

a)成立

①

x

y

G(x,y)②x

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

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