邏輯表示及歸結系統(tǒng)

邏輯表示及歸結系統(tǒng)定義：邏輯學是研究人類思維活動規(guī)律的科學.方法：利用數(shù)學（符號化、公理化、形式化）的方法來研究這些規(guī)律.作用：是表達人類思維和推理的最精確和成功的方法，成為AI的重要基礎.表現(xiàn)方式和人類自然語言非常接近便于計算機做精確處理分類：經(jīng)典邏輯和非經(jīng)典邏輯兩大類，經(jīng)典邏輯中命題邏輯和一階謂詞邏輯是基礎.1一階謂詞邏輯概述第2頁,共46頁，2024年2月25日，星期天命題的定義：表示知識的陳述性形式或具有真假意義的陳述句.例：A：張平是學生；B：樹葉是綠色的；命題的類型：原子命題：表達單一意義、不能再分解.

如P：天在下雨；Q:天晴復合命題：由連接詞、標點和原子命題構成.如，P→~Q可表示：如果天在下雨則天不晴.命題邏輯就是研究命題與命題之間關系的符號邏輯系統(tǒng),包含語法、語義、演算等.1．1命題概念第3頁,共46頁，2024年2月25日，星期天原子命題是命題邏輯中最基本的單元,不能對其進行分解,也不能對其結構進行分析.引發(fā)的問題:限制了它的使用;為了突破這種束縛,發(fā)展了謂詞邏輯.原子命題可分解;以命題中的謂詞為基礎進行分析研究.第4頁,共46頁，2024年2月25日，星期天1.2謂詞概念原子命題分解為謂詞、個體2部分。例：1、3是質(zhì)數(shù)，x是質(zhì)數(shù)，F(xiàn)(x)；2、王二生于武漢市，x生于y，G(x,y)；3、7=2

3，x=y

z，H(x,y,z)；3、王二、武漢市、7等，稱為個體（具體）;代表個體的變元，稱為個體變元（抽象）；刻畫個體性質(zhì)或個體之間關系的詞叫謂詞，如“是質(zhì)數(shù)”、“生于”、“…=…

…”謂詞中包含的個體數(shù)目稱為謂詞的元數(shù).在謂詞P（x1，x2，…，xn）中,若每個xi都是個體常量、變元或函數(shù)，則稱它為一階謂詞，若某個xi本身又是一個一階謂詞，則稱它為二階謂詞…第5頁,共46頁，2024年2月25日，星期天謂詞與命題的區(qū)別——更強的表達能力1、有概括能力例如，

是一個城市，謂詞CITY（X）2、可表示變化著的情況命題值是恒真或恒假，謂詞值可因參數(shù)而異3、可在不同的知識之間建立高級聯(lián)系

HUMAN（X）X是人，LAWED（X）X受法律約束，COMMIT（X）X犯法，PUNISHED（X）X受法律制裁HUMAN（X）→LAWED（X）人人都要受法律約束COMMIT（X）→PUNISHED（X）犯罪，就要受懲罰{[HUMAN（X）→LAWED（X）]→[COMMIT（X）→PUNISHED（X）]}第6頁,共46頁，2024年2月25日，星期天2歸結原理定理證明：已知一公式集F1，F(xiàn)2，…，F(xiàn)n，要證明一個公式W是否成立，即要證明W是公式集的邏輯推論.方法：直接法：F1

F2

…

Fn→W是永真式.間接法（反證法）：F1

F2

…

Fn

~W為永假基本思想：采用反證法將待證明的表達式轉(zhuǎn)換為邏輯公式，然后再進行歸結，歸結能夠順利完成，則證明原定理是正確的.2.1歸結原理概述第7頁,共46頁，2024年2月25日，星期天2.1歸結原理概述(續(xù))理論依據(jù):空子句：一種沒有任何解釋能滿足的子句，其取值總是假，簡記為□或NIL.用歸結法從子句集S導出的擴大子句集S1(S∪歸結式)，其不可滿足性是不變的.(待證)技術思路：設法檢驗原(或擴充的)子句集S是否含有空子句，若S集中存在空子句，則表明S為不可滿足的.過程:S→S1→

S2→

…→Sn

歸結過程可以一直進行下去，也就是要通過歸結過程演繹出S的不可滿足性來，從而使定理得到證明.第8頁,共46頁，2024年2月25日，星期天幾個概念不含有任何連接詞的命題(謂詞)公式稱為原子公式(原子).原子或原子的否定統(tǒng)稱為文字.子句是由一些文字組成的析取式.不包含任何文字的子句稱為空子句.(不能用任何解釋所滿足)子句構成的集合,稱為子句集.第9頁,共46頁，2024年2月25日，星期天2.2命題邏輯的歸結法

1）歸結式的定義及性質(zhì)

歸結：設C1與C2是子句集中的任意兩個子句，如果C1中的文字L1與C2中的文字L2互補，那么從C1和C2中分別消去L1和L2,并將兩個子句中的余下部分析取，構成一個新的子句C，這一過程稱為歸結.C:C1和C2的歸結式;C1和C2:C的親本子句.沒有互補對的兩子句沒有歸結式。第10頁,共46頁，2024年2月25日，星期天[例]設C1=~P

Q

R,C2=~Q

S，

C1中L1=Q與C2中L2=~Q互補.得：C=~P

R

S[例]設C1=P，C2=~P

P與~P互補，可得：C=□.[例]設C1=~P

Q，C2=~Q

R，C3=P，首先對C1，C2進行歸結，得C12=~P

R，再對C12，C3歸結，得C123=R.第11頁,共46頁，2024年2月25日，星期天定理：兩個子句C1和C2的歸結式C是C1和C2的邏輯結論.（即C1

C2

C）證明:設C1=L

C1'，C2=（~L）

C2'，通過歸結可得到C=C1'

C2'因為C1=L

C1'=C1'

L

~C1'

L；

C2=

~L

C2'

L

C2'

C1

C2=(~C1'

L)

(L

C2')由假言三段論得到：

(~C1'

L)

(L

C2')

(~C1'

C2')而~C1'

C2'

C1'

C2'=C

C1

C2

C[證畢]

第12頁,共46頁，2024年2月25日，星期天推論：子句集合S={C1，C2，…，Cn}與S1={C，C1，C2，…，Cn}的不可滿足性是等價的（C是C1和C2的歸結式，即S1是對S應用歸結后得到的）.證明：設S是不可滿足的，則C1

，C2，…，Cn中必有一個為假，因而S1必為不可滿足的.設S1是不可滿足的，則對于不滿足S1的任一解釋I，可能有兩種情況：I使C為真，則C1，C2，…，Cn中必有一子句為假，因而S是不可滿足的。I使C為假，則根據(jù)定理有C1

C2為假，即I或使C1為假，或使C2為假，因而S也是不可滿足的。由此,S和S1的不可滿足性是等價的.

第13頁,共46頁，2024年2月25日，星期天同理可證Si和Si+1（Si導出的擴大的子句集）的不可滿足性也是等價的，其中i=1，2，….第14頁,共46頁，2024年2月25日，星期天總結:

歸結原理就是從子句集S出發(fā)，應用歸結推理規(guī)則導出子句集S1

，再從S1出發(fā)導出S2

，依次類推，直到某一個子句集Sn出現(xiàn)空子句為止.根據(jù)不可滿足性等價原理，若已知Sn為不可滿足的，則可逆向依次推得S必為不可滿足的.用歸結法證明定理，只涉及歸結推理規(guī)則的應用問題，過程比較簡單，因而便于實現(xiàn)機器證明.

第15頁,共46頁，2024年2月25日，星期天2）命題邏輯的歸結過程命題邏輯中，若給定公理集F和命題P，則歸結證明過程可歸納為：把F轉(zhuǎn)化為子句集表示，得子句集S0；把命題P的否定式~P也轉(zhuǎn)化成子句集表示，并將其加到S0中，得S=S0

{~P}；對子句集S反復應用歸結推理規(guī)則，直到導出含有空子句的擴大子句集為止。即出現(xiàn)歸結式為空子句的情況時，表明已找到了矛盾，證明過程結束.第16頁,共46頁，2024年2月25日，星期天[例]、設已知公理集為

P……（1）；（P

Q）

R……（2）；（S

T）

Q……(3）；

T………（4）；求證R.化成子句集表示后得

S={P，~P

~Q

R，~S

Q，~T

Q，T，~R}歸結過程很簡單，如右圖的演繹樹所示，由于根部出現(xiàn)了空子句，因此命題R得到證明.~P

~Q

R~P

~Q~Q~TT~T

QP~R第17頁,共46頁，2024年2月25日，星期天2.3謂詞邏輯中的歸結原理歸結原理對子句集的基本要求(命題級):無量詞約束子句只是文字的析取否定符只作用于單個文字子句間默認為合取在謂詞邏輯中，由于表達式中包含有變元,所以需要考慮變量的約束問題(作用范圍):1.謂詞公式化子句集的方法.2.在應用歸結法時,先對公式作變量置換和合一等處理,得到互補的基本式，然后才能進行歸結.第18頁,共46頁，2024年2月25日，星期天新問題1:量詞問題?謂詞演算中,一般有兩種形式:前束范式和SKOLEM范式.前束范式:若一個謂詞公式P的所有量詞均非否定地出現(xiàn)在P的前部，且量詞轄域是整個公式，稱P為前束范式.如F

(Q1x1)…(Qnxn)M;(Qi:2值,M:析取式)SKOLEM范式:消去前束范式中的所有量詞(方法如下)后所得到的謂詞公式,也稱SKOLEM標準型.:若變量不受全稱量詞的約束(左邊無

),可用任意常量代替該變量;否則,用以其為因變量的函數(shù)代替該存在量詞.,函數(shù)形式(幾元函數(shù))依賴于受幾個全稱量詞約束.:省略.1）謂詞公式的標準化第19頁,共46頁，2024年2月25日，星期天化子句集的方法

xP(x)→{

y[P(y)→P(f(x,y))]

~

y[Q(x,y)→P(y)]}1.消蘊涵符 理論根據(jù)：ab=>~ab~

xP(x)

{

y[~P(y)

P(f(x,y))]

~

y[~Q(x,y)

P(y)]}2.移動否定符理論根據(jù)：~(ab)=>~a~b~(ab)=>~a~b ~(x)P(x)=>(x)~P(x) ~(x)P(x)=>(x)~P(x)

x~P(x)

{

y[~P(y)

P(f(x,y))]

y~[~Q(x,y)

P(y)]}=

x~P(x)

{

y[~P(y)

P(f(x,y))]

y[Q(x,y)

~

P(y)]}第20頁,共46頁，2024年2月25日，星期天化子句集的方法（續(xù)1）3.變量標準化 即：對于不同的量詞約束，對應于不同的變量方法:(x)A(x)(x)B(x)=>(x)A(x)(y)B(y)x~P(x)

{

y[~P(y)

P(f(x,y))]

w[Q(x,w)

~

P(w)]}4.量詞左移

(保序前移到M的前部)

方法:(x)A(x)(y)B(y)=>(x)(y){A(x)B(y)}x

y

w~P(x)

{[~P(y)

P(f(x,y))]

[Q(x,w)

~

P(w)]}第21頁,共46頁，2024年2月25日，星期天化子句集的方法（續(xù)2）5.消存在量詞(skolem化） 原則：對于一個受存在量詞約束的變量，如果它不受全程量詞約束，則該變量用一個常量代替，如果它受全程量詞約束，則該變量用一個函數(shù)代替.

x

y

w~P(x)

{[~P(y)

P(f(x,y))]

[Q(x,w)

~

P(w)]}=>

y~P(a)

{[~P(y)

P(f(a,y))]

[Q(a,g（y）)

~

P(g（y）)]}第22頁,共46頁，2024年2月25日，星期天化子句集的方法（續(xù)3）6.化為合取范式

即(ab)(cd)(ef)的形式方法:

P(x)

[Q(x)

R(x)]

[P(x)

Q(x)]

[P(x)

R(x)]

[P(x)

Q(x)]

R(x)

P(x)

[Q(x)

R(x)]

P(x)

Q(x)

R(x)[P(x)

Q(x)]

R(x)

P(x)

[Q(x)

R(x)]

P(x)

Q(x)

R(x)

y~P(a)

{[~P(y)

P(f(a,y))]

[Q(a,g（y）)

~

P(g（y）)]}

=>

y[~P(a)

~P(y)

P(f(a,y))]

[~P(a)

Q(a,g（y）)]

[~P(a)

~P(g（y）)]第23頁,共46頁，2024年2月25日，星期天化子句集的方法（續(xù)4）7.隱去全程量詞[~P(a)

~P(y)

P(f(a,y))]

[~P(a)

Q(a,g（y）)]

[~P(a)

~P(g（y）)]8.表示為子句集:以逗號替代所有的合取符號~P(a)

~P(y)

P(f(a,y))，~P(a)

Q(a,g（y）)，~P(a)

~P(g（y）)9.變量標準化（變量換名）即：不同的子句，使用不同的變量~P(a)

~P(y1)

P(f(a,y1))，~P(a)

Q(a,g（y2）)，~P(a)

~P(g（y3）)第24頁,共46頁，2024年2月25日，星期天課堂小練習:化下列公式成子句形式1）(x)

(y)[P（x,y）

Q（x,y）]2）(x)

(y)[P（x,y）

Q（x,y）]3)(x)

(y){P（x,y）

[Q（x,y）

R（x,y）]}第25頁,共46頁，2024年2月25日，星期天2)置換和合一問題2:表達式是否相同或匹配?~P(x)

Q(y）與P(a)

R(z）思路:個體變量的替換.

方法:置換和合一置換:在謂詞公式中用項(常,變,函數(shù))替換變量,

形如:s={t1/v1,t2/v2,…,tn/vn}

對公式E實施置換s后得到的公式稱為E的例，記作Es.例：s1={z/x,A/y},則：

P[x,f(y),B]s=P[z,f(A),B]第26頁,共46頁，2024年2月25日，星期天2)置換和合一(續(xù)1)合成置換:有時需對表達式進行多次置換，如用s1、s2依次進行置換（即（Es1）s2），這時可以把兩個置換合成為一個置換（記為s1s2）.合成置換是由兩部分組成的：一部分仍是s1的置換對，只是s1中的項被s2作了置換；另一部分是s2中與s1不同的那些變量對。例如：

s1={g(x,y)/z},s2={A/x,B/y,C/w,D/z}s1s2={g(A,B)/z,A/x,B/y,C/w}性質(zhì):（Es1）s2=E（s1s2），(結合律)但一般情況下置換是不可交換的，即s1s2

s2s1。

s2s1={A/x,B/y,C/w,D/z}

s1s2第27頁,共46頁，2024年2月25日，星期天2)置換和合一(續(xù)2)合一就是通過項對變量的置換,而使表達式(文字)一致.若存在一個置換s使得表達式集{Ei}中每一個元素經(jīng)置換后的例有：E1s=E2s=E3s=

，則稱表達式集{Ei}是可合一的，這個置換s稱作{Ei}的合一者.例.{P（x，f（y），B），P（x,f（B）,B）}s={A/x，B/y}，得{P（A，f（B），B）}.第28頁,共46頁，2024年2月25日，星期天2)置換和合一(續(xù)3)如果g是公式集{Ei}的一個合一者,如果對{Ei}的任意一個合一者s都存在一個置換s

，使得s=gs

，則稱g為表達式{Ei}的最簡單合一者mgu.例.{P（x，f（y），B），P（x，f（B），B）}g={B/y}為該式的mgu.

因為

s={A/x，B/y}，

置換s

={A/x},使s=gs.第29頁,共46頁，2024年2月25日，星期天

求最簡單合一者的算法:1.令W={F1,F2};//輸入2.k=0,W0=W,g0={};//循環(huán)次數(shù),公式集合,置換的初始化3.如果Wk已合一,停止,gk=mgu;//成功退出否則,找不一致集Dk;4.若Dk中存在元素vk和tk,其中vk不出現(xiàn)于tk中,轉(zhuǎn)(5),

否則,不可合一;//失敗退出5.令gk+1=

gk?{tk/vk},Wk+1=Wk{tk/vk},

//置換合成,公式集合變換6.k=k+1轉(zhuǎn)(3)2)置換和合一(續(xù)4)第30頁,共46頁，2024年2月25日，星期天例:S={P(a,x,h(g(z))),P(z,h(y),h(y))}1.g0={};Sg0不是單元素集,故求不一致集D0={a,z};2.g1=g0{a/z};Sg1={P(a,x,h(g(a))),P(a,h(y),h(y))}不是單元素集,故D1={x,h(y)};3.g2=g1{h(y)/x};Sg2=(Sg1){h(y)/x}={P(a,h(y),h(g(a))),P(a,h(y),h(y))}不是單元素集,故D2={g(a),y};4.g3=g2{g(a)/y};Sg3=(Sg2){g(a)/y}={P(a,h(g(a)),h(g(a))),P(a,h(g(a)),h(g(a))}是可合一的.即g3={a/z}{h(y)/x}{g(a)/y}={a/z,h(y)/x}{g(a)/y}={a/z,h(g(a))/x,g(a)/y}是一個mgu.第31頁,共46頁，2024年2月25日，星期天3)謂詞邏輯中的歸結式歸結式:對于子句C1L1和

C2L2，如果L1與~L2可合一，且s是其合一者，則(C1C2)s是其歸結式.例：P(x)Q(y),~P(f(z))R(z) =>Q(y)R(z)(s=f(z)/x)選不同文字對做歸結時,可得不同的歸結式練習:

C1=P(x，f(y))

Q(y)C2=~P(z，f（A）)

~Q(z)第32頁,共46頁，2024年2月25日，星期天3)謂詞邏輯中的歸結式(續(xù))注意點:

被歸結的子句C1,C2應具有不同的變量.

方法:變量換名在求歸結式時,不能同時消去兩個互補文字對,消去兩個互補文字對所得到的結果不是親本子句的邏輯推論.

例.C1=P(..)

Q(..),C2=~P(..)

~Q(..)如在參加歸結的子句內(nèi)含有可合一的文字,則應先對這些文字進行合一,化簡后再歸結.

例.C1=P(x)

P(f(a))

Q(x),C2=~P(y)

R(b)第33頁,共46頁，2024年2月25日，星期天定義謂詞寫出已知條件和結論的謂詞關系公式化為Skolem標準型求子句集合S對S中可歸結的子句做歸結(置換和合一)歸結式仍放入S中,反復歸結過程看能否導出空子句

4)謂詞邏輯中的歸結過程第34頁,共46頁，2024年2月25日，星期天例、已知：1.會朗讀的動物是識字的；2.海豚都是不識字的；3.有些海豚很機靈。證明：有些很機靈的動物不會朗讀。已知：1.(

x)(R(x)

L(x));

2.(

x)(D(x)

~L(x));

3.(

x)(D(x)

I(x))求證：(

x)(I(x)

~R(x))化簡前提條件公式，結論取反，得子句集：（1）~R(x)

L(x)（2）~D(y)

~L(y)（3a）D（A）（3b）I（A）（4）~I(z)

R(z)第35頁,共46頁，2024年2月25日，星期天{A/z}{A/x}{A/y}（1）~R(x)

L(x)（2）~D(y)

~L(y)（3a）D（A）（3b）I（A）（4）~I(z)

R(z)從子句集求歸結式，并將它加進子句集，連續(xù)進行直到產(chǎn)生空子句為止，上圖的歸結過程代表一個可行的證明過程~I(z)

R(z)I（A）NIL~R

(x)L(x)R（A）L（A）~D(y)

~

L(y)D（A）~

D（A）歸結反演樹第36頁,共46頁，2024年2月25日，星期天3歸結反演系統(tǒng)

3.1產(chǎn)生式系統(tǒng)的基本算法綜合數(shù)據(jù)庫：子句集(子句間為合取關系)規(guī)則集合：IFcx（

Si）和cy（

Si）有歸結式rxyTHENSi+1=Si

{rxy}目標條件：Sn中出現(xiàn)空子句過程1Clauses：=S；S為初始的基本子句集。2untilNIL是Clauses的元素，do：3begin4在Clauses中選兩個不同的可歸結的子句ci

、cj5求ci

、cj

的歸結式rij；6Clauses：={rij}

Clauses7end；第37頁,共46頁，2024年2月25日，星期天3.2搜索策略任務:是在算法的第4步中確定選哪兩個子句做歸結，以及在第5步?jīng)Q定這兩個子句中對哪一個文字做歸結主要策略:寬度優(yōu)先:第一級(基本集)→第二級→……支持集:歸結時，至少選一個是與目標公式否定式(本身或后裔)有關的子句.單元子句優(yōu)先:至少有一個是單文字子句線性輸入形:至少有一個是從基本子句集中挑選祖先過濾形:有一個母子句或者從基本集中挑選，或者從該母子句的先輩子句中挑選第38頁,共46頁，2024年2月25日，星期天4基于歸結法的問題解答系統(tǒng)4.1提取回答的方法例、ifFidogoeswhereverJohngoesandifJohnisatschool,whereisFido?分析:兩個已知事實和一個詢問.思路:從事實出發(fā)演繹得到詢問的答案.步驟:1.先用謂詞公式表示問題：前提：(

x)(AT(John,x)

AT(Fido,x));AT(John,School)

目標：(

x)AT(Fido,x)子句集:~AT(John,x1)AT(Fido,x1),AT(John,School),~

AT(Fido,x2)第39頁,共46頁，2024年2月25日，星期天2.證明目標公式是前提公式集的邏輯推論3.找出一個x的例，來回答Fido在何處的詢問.關鍵：把詢問表達為一個有存在量詞約束的目標公式.

歸結反演樹√√~AT(Fido,x2)~AT(John,x1)

AT(Fido,x1){x2/x1}~AT(John,x2)AT(John,School),{School/x2}NIL第40頁,共46頁，2024年2月25日，星期天修改證明樹~AT(John,x1)

AT(Fido,x1){x2/x1}AT(John,School){School/x2}AT(Fido,x2)

~AT(Fido,x2)~AT(John,x2)

AT(Fido,x2)AT(Fido,School)第41頁,共46頁，2024年2月25日，星期天例:在天花板上吊有一串香蕉的房間里，有一個可移動的箱子，問一只猴子如何規(guī)劃自己的行動使得它能摘到香蕉.

cab第42頁,共46頁，2024年2月25日，星期天問題描述:初始狀態(tài)為S0：~ONBOX，AT（box，b），AT（Monkey，a），