【人工智能課件】基于謂詞邏輯的機(jī)器推理

第三章 基于謂詞邏輯的機(jī)器推理-3.2 歸結(jié)演繹推理3.2.1子句集定義1 原子謂詞公式及其否定稱為文字；文字的析取式稱為子句；r個文字組成的子句稱為r-文字子句。1-文字子句也稱為單元子句。不含任何文字的子句稱為空子句，記為或NIL。由子句構(gòu)成的集合稱為子句集。任何一個謂詞公式都可以化為子句集，步驟如下：（1）、利用等價式A B A B和 A B (A B)(B A)消去聯(lián)結(jié)詞“”和“”。（2）、縮小否定聯(lián)結(jié)詞的作用范圍，使其僅作用于原子公式?？衫孟铝械葍r式：A A；(AB)A B；(A B)A B；xA(x)x A(x)；xA(x)x A(x)（3）、重新命名變元名，使不同量詞約束的變元有不同的名字。（4）、消去存在量詞。若存在量詞不在全稱量詞的轄域內(nèi)，則用一個常量符號替換該存在量詞轄域中的相應(yīng)約束變元。這樣的常量稱為Skolem常量；若該存在量詞在一個或多個全稱量詞的轄域內(nèi)，則用這些全稱量詞指導(dǎo)變元的一個函數(shù)替換該存在量詞約束的變元。這樣的函數(shù)稱為Skolem函數(shù)。例如x1 x2 xnyP(x1,x2,xn,y)中y可用Skolem函數(shù)f(x1,x2,xn)替換為x1 x2 xnP(x1,x2,xn,f(x1,x2,xn)。（5）、把全稱量詞全部移到公式的左邊。（6）、把全稱量詞后面的公式利用等價關(guān)系A(chǔ)(B C)(AB)(A C)化為子句的合取式，得到的公式稱為Skolem標(biāo)準(zhǔn)形。Skolem標(biāo)準(zhǔn)形的一般形式為x1 x2 xnM，其中M是子句的合取式。（7）、消去全稱量詞。（8）、對變元更名，使子句間無同名變元。（9）、消去合取詞，以子句為元素組成的集合稱為謂詞公式的子句集。例、把謂詞公式xyP(x,y)yQ(x,y)R(x,y)化為子句集。定理1 謂詞公式G 不可滿足當(dāng)且僅當(dāng)其子句集S不可滿足。子句集S是不可滿足的是指其全部子句的合取式是不可滿足的。3.2.2 命題邏輯中的歸結(jié)原理要證明在前提P下結(jié)論Q成立，即是證明P Q永真，這只須證明P Q不可滿足。根據(jù)定理1，只須證明P Q的子句集不可滿足。由于子句之間是合取關(guān)系，只要有一個子句不可滿足，則整個子句集不可滿足。由于空子句是不可滿足的，所以如果子句集中包含空子句，則該子句集是不可滿足的。若子句集中不包含空子句，則可通過Robinson提出的歸結(jié)原理對子句集進(jìn)行歸結(jié)，歸結(jié)過程保證子句集的不可滿足性不變。一旦歸結(jié)出空子句，則證明結(jié)束。因此，歸結(jié)原理把定理的證明化為子句集中歸結(jié)出空子句的過程。定義、設(shè)L是一個文字，則稱L與L為互補(bǔ)文字。定義、設(shè)C1、C2是命題邏輯中的兩個子句，C1 中有文字L1，C 中有文字L，且L1與L互補(bǔ)，從C1，C中分別刪除L1，L，再將剩余部分析取起來，構(gòu)成的新子句C1稱為C1與C2的歸結(jié)式（消解式），C1，C2稱為C1的親本子句。定理、歸結(jié)式C1是其親本子句C1與C2的邏輯結(jié)論。推論、設(shè)C1，C2是子句集S的兩個子句，C1是它們的歸結(jié)式，則（）若用C1代替C1和C2后得到新子句集S1，則由S1的不可滿足性可推出原子句集S的不可滿足性。即S1不可滿足S不可滿足（）若把C1加入到S中，得到新子句集S，則S與S在不可滿足意義上是等價的。即S2不可滿足 S不可滿足例、用歸結(jié)原理證明R是P，（P Q）R，（SU）R，U的邏輯結(jié)果。3.2.3 替換與合一定義、一個替換(Substitution)是形如t1/x1,t2/x2,tn/xn 的有限集合，其中t1,t2 ,tn 是項(xiàng)，x1,x2,xn是互不相同的個體變元。ti/xi表示用ti代換xi。ti與xi不同，xi也不能出現(xiàn)在tj中(j=1,2,n)。例、a/x,g(y)/y,f(g(b)/z是一個替換，g(y)/x,f(x)/y不是一個替換。定義、設(shè)t1/x1,t2/x2,tn/xn 是一個替換，E是一個表達(dá)式（項(xiàng)、原子公式、文字、子句），把E中出現(xiàn)的所有個體變元xi都用ti 替換，得到的結(jié)果記為E，稱為E在下的替換實(shí)例。例、若E=P(x,y,g(z),a/x,f(b)/y,c/z，則E=P(a,f(b),g(c)。定義、設(shè)t1/x1,t2/x2,tn/xn，u1/y1,u2/y2,um/ym 是兩個替換，則將集合t1 /x1,t2 /x2,tn /xn，u1/y1,u2/y2,um/ym 中符合下列條件的兩種情形刪除：）、ti /xi，當(dāng)ti xi。）、ui/yi，當(dāng)yi x1,x2,xn 。得到的集合仍是一個替換，稱為與的復(fù)合，記為。例、見教材p67例3.13。定義、設(shè)S=F1,F2,Fn 是一個原子謂詞公式集，若存在一個替換，使得F1 F2 Fn，則稱為S的一個合一（Unifier），并稱S為可合一的。一個公式集的合一一般不唯一。定義、設(shè)是公式集S的一個合一，如果對S的任何一個合一，都存在一個替換，使得 ，則稱為S的一個最一般合一（Most General Unifier），簡稱MGU。定義、設(shè)S是一個非空的具有相同謂詞名的原子公式集，從S中各公式的左邊第一個項(xiàng)開始，同時向右比較，每一組不都相同的項(xiàng)的差異部分組成的集合稱為S的差異集。例、公式集S=P(a,x,f(g(y),P(z,h(z,u),f(u)的差異集為a,z,x,h(z,u),g(y),u3.2.3 替換與合一設(shè)S為一非空有限具有相同謂詞名的原子謂詞公式集，求S的MGU的算法：（1）、令k=0,Sk=S,k=（表示空替換）。（2）、若Sk只含有一個謂詞公式，則算法停止，k就是要求的最一般合一。（3）、求Sk的差異集Dk。（4）、若Dk中存在元素 xk 和 tk，其中xk是變元，tk是項(xiàng)且xk不在tk中出現(xiàn)，則置Sk+1=Sktk/xk，k+1=k tk/xk，k=k+1，然后轉(zhuǎn)步（2）。（5）、算法停止，S的最一般合一不存在。定理3（合一定理）、如果S是一個非空有限可合一的公式集，則合一算法總是在步（2）停止，且最后的k即是S的最一般合一。3.2.4 謂詞邏輯中的歸結(jié)原理定義12、設(shè)C1，C2是兩個沒有相同變元的子句，L1，L2分別是C1，C2中的兩個文字，如果L1與L2有最一般合一，則子句C12=(C1-L1)(C2-L2)，稱作C1和C2的二元?dú)w結(jié)式（二元消解式）。C1和C2稱為C12的親本子句，L1，L2稱為消解文字。若在參加歸結(jié)的子句內(nèi)部含有可合一文字，則在進(jìn)行歸結(jié)之前，應(yīng)對這些文字進(jìn)行合一。定義13、如果子句C中，兩個或兩個以上的文字有一個最一般合一，則稱C為C的因子。定義14、子句C1，C2的歸結(jié)式，是下列二元?dú)w結(jié)式之一：1）、C1和C2的二元?dú)w結(jié)式；2）、C1和C2的因子的二元?dú)w結(jié)式；3）、C1的因子和C2的二元?dú)w結(jié)式；4）、C1的因子和C2的因子的二元?dú)w結(jié)式。定理4、謂詞邏輯中的歸結(jié)式是它的親本子句的邏輯結(jié)果。類似于命題邏輯中的兩個推論仍成立。歸結(jié)反演：應(yīng)用歸結(jié)原理證明定理的過程稱為歸結(jié)反演。若F為已知前提的公式集，Q為結(jié)論，用歸結(jié)反演證明Q為真的步驟是：（1）、否定Q，得到Q；（2）、把Q并入到公式集F中，得到F,Q；（3）、把公式集F,Q化為子句集S；（4）、應(yīng)用歸結(jié)原理對子句集S中的子句進(jìn)行歸結(jié)，并把每次歸結(jié)得到的歸結(jié)式都并入S中。如此反復(fù)進(jìn)行，直到出現(xiàn)空子句，就證明了Q為真。例、自然數(shù)都是大于零的數(shù)；所有整數(shù)不是偶數(shù)就是奇數(shù)；偶數(shù)除以2是整數(shù)。求證：所有自然數(shù)不是奇數(shù)就是其一半為整數(shù)的數(shù)。證明：前提：F1：x(N(x)GZ(x)I(x)F2：x(I(x)E(x)O(x)F3：x(E(x)I(h(x)結(jié)論：G：x(N(x)O(x)I(h(x)F1、F2、F3 及G 化為子句集：（1）N(x)GZ(x)（2）N(y)I(y)（3）I(z)E(z)O(z)（4）E(u)I(h(u)（5）N(c)（6）O(c)（7）I(h(c)歸結(jié)：（8）I(c)(2),(5),c/y)（9）I(c)E(c)(3),(6),c/z)（10）E(c)(8),(9)（11）I(h(c)(4),(10),c/u)（12）(7),(11)定理5（歸結(jié)原理的完備性）、如果子句集S是不可滿足的，則必存在一個由S推出空子句的歸結(jié)序列。其它例見教材p78,例15，16。課堂練習(xí)：p94，題6。歸結(jié)演繹樹：N(y)I(y)N(c)I(z)E(z)O(z)O(c)I(c)I(c)E(c)E(c)E(u)I(h(u)I(h(c)I(h(c)3.3 應(yīng)用歸結(jié)原理求取問題答案應(yīng)用歸結(jié)原理求取問題答案的步驟：（1）、把已知前提用謂詞公式表示出來，并化為子句集S。（2）、把待求解問題也用謂詞公式表示出來，然后把它的否定與謂詞ANS構(gòu)成析取式。ANS的變元應(yīng)與問題的變元完全一致。（3）、把此析取式化為子句集，并把該子句集并入S中得到子句集S。（4）、對S應(yīng)用歸結(jié)原理進(jìn)行歸結(jié)。（5）、若得到歸結(jié)式ANS，則答案就在ANS中。例、設(shè)A、B、C三人中有人從不說真話，也有人從不說假話，某人向這三人分別提出同一個問題：誰是說謊者？A答：“B和C都是說謊者”；B答：“A和C都是說謊者”；C答：“A和B中至少有一個是說謊者”。求誰是老實(shí)人，誰是說謊者？解、設(shè)T(x)表示x說真話。如果A說的是真話，則有：T(A)T(B)T(C)如果A說的是假話，則有：T(A)T(B)T(C)。同理，對B和C有：T(B)T(A)T(C)T(B)T(A)T(C)T(C)T(A)T(B)T(C)T(A)T(B)化為子句集S：（1）、T(A)T(B)（2）、T(A)T(C)（3）、T(A)T(B)T(C)（）、T(B)T(C)（）、T(A)T(B)T(C)（）、T(C)T(A)（）、T(C)T(B)先求誰是老實(shí)人，把T(x)ANS(x)并入S （）、T(x)ANS(x)（）、T(A)ANS(C)(8),(6),C/x)（）、T(B)ANS(C)(7),(8),C/x)（）、T(B)ANS(C)(9),(1)（）、ANS(C)(10),(11)因此C是老實(shí)人。無論如何歸結(jié)，推不出ANS(A),ANS(B)。下證A是說謊者，即T(A)，其否定為（）T(A)即T(A)（）T(B)(8),(1)（）T(C)（），（）（）T(C)（），（）（）NIL （），（）3.歸結(jié)策略3.4.1 問題的提出歸結(jié)反演的一般過程。步將子句集S置入CLAUSES表；步若空子句NIL在CLAUSES中，則歸結(jié)成功，結(jié)束。步若CLAUSES表中存在可歸結(jié)的子句對，則歸結(jié)之，并將歸結(jié)式并入CLAUSES表，轉(zhuǎn)步；步歸結(jié)失敗，退出。窮舉算法（廣度優(yōu)先策略）第一輪：將原子句集S中的子句兩兩歸結(jié)，產(chǎn)生的歸結(jié)式集合記為S1，再將S1并入CLAUSES表；第二輪：將新的CLAUSES表即SS1中的子句與S1中的子句兩兩歸結(jié)，產(chǎn)生的歸結(jié)式集合記為S2，再將S2并入CLAUSES；第三輪：將新的CLAUSES表即SS1 S2中的子句與S2中的子句兩兩歸結(jié)，。如此下去，直到出現(xiàn)空子句。例1 設(shè)有如下的子句集，用窮舉算法歸結(jié)如下：S：（1）PQ （2）PQ （3）P Q （4）P QS1：（5）Q (1),(2)（6）P (1),(3)（7）Q Q (1),(4)（8）P P (1),(4)（9）Q Q (2),(3)（10）P P (2),(3)（11）P (2),(4)（12）Q (3),(4)S2：（13）P Q (1),(7)（14）P Q (1),(8)（15）P Q (1),(9)（16）P Q (1),(10)（17）Q (1),(11)（18）P (1),(12)（19）Q (2),(6)（20）PQ (2),(7)（21）PQ (2),(8)（22）PQ (2),(9)（23）PQ (2),(10)（24）P (2),(12)（25）P (3),(5)（26）P Q (3),(7)（27）P Q (3),(8)（28）P Q (3),(9)（29）P Q (3),(10)（30）Q (3),(11)（31）P (4),(5)（32）Q (4),(6)（33）P Q (4),(7)（34）P Q (4),(8)（35）P Q (4),(9)（36）P Q (4),(10)（37）Q (5),(7)（38）Q (5),(9)（39）(5),(12)3.4.2 幾種常用的歸結(jié)策略1、刪除策略定義、設(shè)C1，C2是兩個子句，若存在替換，使得C1 C2，則稱子句C1類含C2。例、P(x)類含P(a)Q(y)；P(x)類含P(a)。刪除策略。在歸結(jié)過程中可隨時刪除以下子句：（1）、含有純文字的子句；純文字是指在子句中無補(bǔ)文字的文字。（2）、含有永真式的子句；（3）、被子句集中別的子句類含的子句。使用刪除策略，例1可簡化為：（1）PQ （7）P (2),(4)（2）PQ （8）Q (3),(4)（3）P Q （9）(5),(8)（4）P Q（5）Q (1),(2)（6）P (1),(3)刪除策略的特點(diǎn)：刪除策略的思想是及早刪除無用字句，以避免無效歸結(jié)，縮小搜索空間。刪除策略是完備的。一個歸結(jié)策略是完備的，是指對于不可滿足的子句集，使用該策略進(jìn)行歸結(jié)，最終必導(dǎo)出空子句。2、支持集策略支持集是指目標(biāo)公式的否定的子句集。支持集策略指每次歸結(jié)時，兩個親本子句中至少要有一個是目標(biāo)公式否定的子句或其后裔。例、見教材P84例4.支持集策略的特點(diǎn)：支持集策略實(shí)際是一種目標(biāo)制導(dǎo)的反向推理。支持集策略是完備的。3、線性歸結(jié)策略在歸結(jié)過程中，除第一次歸結(jié)可都用初始子句集S中的子句外，其它的各次歸結(jié)至少要有一個親本子句是前次歸結(jié)的結(jié)果。例、P85例5線性歸結(jié)策略的特點(diǎn)：完備、高效、與別的策略兼容。4、輸入歸結(jié)策略每次參加歸結(jié)的親本子句，必須至少有一個是初始子句集S中的子句。輸入策略的特點(diǎn)：輸入歸結(jié)策略實(shí)際是一種自底向上的推理，它有相當(dāng)高的效率。輸入歸結(jié)策略不完備。例如S=PQ,PQ,P Q,P Q不可滿足，但用輸入歸結(jié)策略導(dǎo)不出空子句?？膳c支持集策略、線性歸結(jié)策略結(jié)合。5、單元?dú)w結(jié)策略（單文字歸結(jié)策略）每次參加歸結(jié)的兩個親本子句中，必須至少有一個是單元子句（單文字子句）。單元?dú)w結(jié)策略的特點(diǎn)：可以盡快逼近空字句；效率高但不完備改進(jìn)型的單元?dú)w結(jié)策略：單元優(yōu)先策略。6、祖先過濾形策略參加歸結(jié)的兩個子句，要么至少有一個是初始子句集中的子句，要么一個是另一個的祖先。例6、P86例6祖先過濾形策略的特點(diǎn)：是輸入策略的改進(jìn)。是完備的3.4.3 歸結(jié)策略的類型簡化性策略。限制性策略。有序性策略。3.5 歸結(jié)反演程序舉例（略）3.6 Horn子句歸結(jié)與邏輯程序3.6.1 子句的蘊(yùn)含表示形式正文字：原子公式稱為正文字。負(fù)文字：原子公式的否定稱為負(fù)文字。把所有正、負(fù)文字分別放在一起，任意子句可寫為：Q1 Qn P1 Pm可近一步化為蘊(yùn)含式：Q1 Q2 Qn P1 P2 Pm如果約定前提文字之間恒為合取關(guān)系，結(jié)論文字之間恒為析取關(guān)系，則上式可簡化為：Q1，Q2，Qn P1，P2，Pm寫成另一種方式：P1，P2，Pm Q1，Q2，Qn兩種特殊情形：當(dāng)m=0時，變?yōu)?Q1，Q2，Qn，相當(dāng)于（Q1 Q2 Qn）。當(dāng)n=0時，變?yōu)镻1，P2，Pm，這相當(dāng)于P1 P2 Pm。對于子句的蘊(yùn)含表示形式，歸結(jié)過程變?yōu)椋簭钠渲幸粋€子句的“”號左（右）側(cè)與另一個子句的“”號右（左）側(cè)的文字中尋找可合一文字對，然后消去它們，并把其余的左部文字合并，作為消解式的左部；其余的右部文字合并，作為消解式的右部。一般地，設(shè)子句C:P1，Pm Q1，Qn和C:P1，P s Q 1，Q t中有Pi與Q j（或 Qi與Pj）可合一，為它們的MGU，則C與C的歸結(jié)式為P1 ，Pi-1 ，Pi+1 ，Pm ，P 1 ，P s Q1 ，Qn，Q 1 ，Qj-1 ，Qj+1 ，Qt 或P1 ，Pm ，P 1 ，Pj-1 ，P j+1 ，P s Q1，Qi-1，Q i+1 ，Qn ，Q1 ，Qt定義1 至多含有一個正文字的子句稱為Horn子句。蘊(yùn)含型Horn子句共有三種：（1）、P Q1，Q2，Qm 稱為條件子句，P稱為頭部或結(jié)論；（2）、P 稱為無條件句；（3）、Q1，Q2，Qm 稱為目標(biāo)子句，Qi稱為子目標(biāo)。例1、證明P(a,c)是下面子句集（1），（2），（3），（4）的邏輯結(jié)論。證：（1）P(x,z)P1(x，y)，P2(y,z)（2）P1(u,v)P11(u，v)（3）P11(a,b)（4）P2(b,c)（5）P(a,c)歸結(jié)（從目標(biāo)子句出發(fā)，采用線性歸結(jié)）（6）P1(a，y)，P2(y,c)(5),(1),a/x,c/z （7）P11(a，y)，P2(y,c)(6),(2),a/u,y/v （8）P2(b，c)(7),(3),b/y (9)(8),(4)第三章 基于謂詞邏輯的機(jī)器推理-3.7 非歸結(jié)演繹推理3.7.1 Bledsoe 自然演繹法3.7.2 基于規(guī)則的演繹推理3.7.3 王浩算法作業(yè)：P85,1.(3),(6);4.(3),(4);7