第四章 確定性推理方法

第四章確定性推理方法第一頁，共七十一頁，2022年，8月28日單調(diào)推理、非單調(diào)推理按照推理過程中推出的結(jié)論是否越來越接近最終目標來劃分，推理又分為單調(diào)推理和非單調(diào)推理。單調(diào)推理是在推理過程中隨著推理向前推進及新知識的加入，推出的結(jié)論越來越接近最終目標。非單調(diào)推理是在推理過程中有新知識的加入，不僅沒有加強已推出的結(jié)論，反而要否定它，使推理退回到前面的一步，然后重新開始。（知識不完全情況下發(fā)生。）X是鳥，會飛，X是企鵝，不會飛。第二頁，共七十一頁，2022年，8月28日命題邏輯命題：能判斷真假的陳述句為命題。命題公式：單個常量或變量的命題稱作合式公式。合式公式有限次組合所構(gòu)成的字符串稱為命題公式。命題邏輯的基本聯(lián)接詞有：~，，，，等價，當且僅當，雙條件第三頁，共七十一頁，2022年，8月28日命題公式的解釋：設(shè)A為一個命題公式，P1P2P3,…,Pn是出現(xiàn)在A中的全部命題變量，給P1P2P3,…,Pn各指定一個真值（0或1），稱為對A的一個賦值或解釋。第四頁，共七十一頁，2022年，8月28日公式的分類永真式：若A無成假賦值，則稱A為重言式?；蛴勒媸?。永假式可滿足式：若A至少有一個成真賦值，則稱A為可滿足式。非重言式的可滿足式：若A至少有一個成真賦值，又至少有一個成假賦值，則稱A為非重言式的可滿足式。第五頁，共七十一頁，2022年，8月28日范式（公式的標準型式）簡單合取式：僅由有限個命題變量或其否定構(gòu)成的合取式成為簡單合取式。簡單析取式：僅由有限個命題變量或其否定構(gòu)成的析取式稱為簡單析取式。合取范式：僅由有限個簡單析取式構(gòu)成的合取式稱為合取范式。P(PQ)(~PQ)析取范式：僅由有限個簡單合取式構(gòu)成的析取式稱為析取范式。P(PQ)(~PQ)析取范式是矛盾式，每個簡單合取式都是矛盾式。合取范式是重言式，每個簡單析取式都是重言式。第六頁，共七十一頁，2022年，8月28日謂詞邏輯是一種形式語言，具有嚴密的理論體系是一種常用的知識表示方法例：City（北京）City（上海）Age（張三，23）(x)(y)(z)(F(x,y)F(y,z)GF(x,z)第七頁，共七十一頁，2022年，8月28日謂詞邏輯原子謂詞公式：是一個不能再分解的命題。原子謂詞公式及其否定，統(tǒng)稱為文字。P與~P為互補文字。任何文字的析取稱為子句。由子句構(gòu)成的集合成為子句集。不包含任何文字的子句稱為空子句，表示為NIL。由于空子句不包含任何文字，不能被任何解釋滿足，所以，空子句是永假的，不可滿足的。第八頁，共七十一頁，2022年，8月28日4.1歸結(jié)原理歸結(jié)原理是一種定理證明方法，1965年由Robinson提出，從理論上解決了定理證明問題。子句集無量詞約束元素只是文字的析取否定符只作用于單個文字元素間默認為和取例：{~I(z)R(z),I(A),~R(x)L(x),~D(y)}第九頁，共七十一頁，2022年，8月28日謂詞公式化子句集的方法例：(z)(x)(y){[(P(x)Q(x))R(y)]U(z)}1,消蘊涵符 理論根據(jù)：ab=>~abp

Q=>(PQ)(~P~Q) (z)(x)(y){[~(P(x)Q(x))R(y)]U(z)}2,移動否定符（把否定符移動到緊靠謂詞的位置上） 理論根據(jù)：~(ab)=>~a~b ~(ab)=>~a~b ~(x)P(x)=>(x)~P(x) ~(x)P(x)=>(x)~P(x)

(z)(x)(y){[(~P(x)~Q(x))R(y)]U(z)}第十頁，共七十一頁，2022年，8月28日化子句集的方法（續(xù)1）3,變量標準化 即：對于不同的約束，對應(yīng)于不同的變量 (x)A(x)(x)B(x)=>(x)A(x)(y)B(y)4,量詞左移

(x)A(x)(y)B(y)=>(x)(y){A(x)B(y)}5,消存在量詞(skolem化） 原則：對于一個受存在量詞約束的變量，如果他不受全程量詞約束，則該變量用一個常量代替，如果他受全程量詞約束，則該變量用一個函數(shù)代替。

(z)(x)(y){[(~P(x)~Q(x))R(y)]U(z)}=>(x){[(~P(x)~Q(x))R(f(x))]U(a)}第十一頁，共七十一頁，2022年，8月28日化子句集的方法（續(xù)2）6,化為合取范式 即(ab)(cd)(ef)的形式

(x){[(~P(x)~Q(x))R(f(x))]U(a)}=>(x){(~P(x)~Q(x))R(f(x))U(a)}=>(x){[~P(x)R(f(x))U(a)][~Q(x))R(f(x))U(a)]}7,隱去全程量詞 {[~P(x)R(f(x))U(a)][~Q(x))R(f(x))U(a)]}第十二頁，共七十一頁，2022年，8月28日化子句集的方法（續(xù)3）8,表示為子句集{~P(x)R(f(x))U(a),~Q(x))R(f(x))U(a)}9,變量標準化（變量換名）{~P(x1)R(f(x1))U(a),~Q(x2))R(f(x2))U(a)}第十三頁，共七十一頁，2022年，8月28日化下列公式成子句形式：（1）(x)[P（x）→P（x）]（2）{~{(x)P（x）}}→(x)[~P（x）]第十四頁，共七十一頁，2022年，8月28日化下列邏輯表達式為合取范式

化下列邏輯表達式為合取范式:

第十五頁，共七十一頁，2022年，8月28日第十六頁，共七十一頁，2022年，8月28日定理： 若S是合式公式F的子句集，則F永假的充要條件是S不可滿足。S不可滿足：若nilS，則S不可滿足。證明的思路： 目標的否定連同已知條件一起，化為子句集，并給出一種變換的方法，使得S

S1S2...Sn，同時保證當Sn不可滿足時，有S不可滿足。

第十七頁，共七十一頁，2022年，8月28日4.2歸結(jié)方法（命題邏輯）設(shè)子句： C1=LC1’

C2=(~L)C2’ 則歸結(jié)式C為： C=C1’C2’定理： 子句集S={C1,C2,…,Cn}與子句集 S1={C,C1,C2,…,Cn}的不可滿足性是等價的。其中，C是C1和C2的歸結(jié)式。第十八頁，共七十一頁，2022年，8月28日證明歸結(jié)式C是C1和C2的邏輯結(jié)論即C1C2→C(1)也就是要證明使C1和C2為真的解釋I，也必然可以使C為真。C1=LC1’，C2=(~L)C2’(2)設(shè)I是使C1和C2為真的任一解釋，若I下的L為真，從而~L為假。由C2為真的假設(shè)可以推出必有在I下的C2’為真，故在I下，由于C=C1’C2’，所以C也為真。若在解釋I下L為假，從而由于假設(shè)C1為真，必有C1’為真，故在解釋I下C=C1’

C2’也必為真。(3)歸結(jié)式C是其親本子句C1和C2的邏輯結(jié)論。第十九頁，共七十一頁，2022年，8月28日推論：設(shè)C1和C2是子句集S上的子句，C是C1和C2的歸結(jié)式。如果把C加入子句集S后得到新子句集S1，則S1和S在不可滿足的意義下是等價的。S是不可滿足的等價于S1是不可滿足的第二十頁，共七十一頁，2022年，8月28日歸結(jié)推理過程：證明子句集S的不可滿足性過程：（1）對子句集S中的各子句間使用歸結(jié)推理規(guī)則。（2）將歸結(jié)所得到的歸結(jié)式放入子句集S中，得到新子句集S’。（3）檢查子句集S’中是否有空子句(NIL)，若有，則停止推理，否則，轉(zhuǎn)步驟（4）（4）置S=S’，轉(zhuǎn)步驟（1）。第二十一頁，共七十一頁，2022年，8月28日歸結(jié)的例子設(shè)公理集： P, (PQ)R, (ST)Q, T求證：R子句集： (1)P (2)~P~QR (3)~SQ (4)~TQ (5)T (6)~R（目標求反）

化子句集： (PQ)R=>~(PQ)R=>~P~QR (ST)Q=>~(ST)Q=>(~S~T)Q=>(~SQ)(~TQ)=>{~SQ,~TQ}第二十二頁，共七十一頁，2022年，8月28日子句集： (1)P (2)~P~QR (3)~SQ (4)~TQ (5)T (6)~R（目標求反）歸結(jié)： (7)~P~Q(2,6) (8)~Q (1,7)(9)~T(4,8)(10)nil(5,9)第二十三頁，共七十一頁，2022年，8月28日證明子句集S={~PQ,~Q,P}不可滿足第二十四頁，共七十一頁，2022年，8月28日4.3謂詞邏輯的歸結(jié)原理問題：如何找歸結(jié)對 例：P(x)Q(y),~P(f(y))R(y)

P(A)Q(y),~P(f(y))R(y)基本概念置換s={t1/v1,t2/v2,…,tn/vn}(ti項，Vi是變量) 對公式E實施置換s后得到的公式稱為E的例，記作Es。例：s1={z/x,A/y},則： P[x,f(y),B]s=P[z,f(A),B]第二十五頁，共七十一頁，2022年，8月28日合一 如果存在一個S置換，使得{Ei}中 E1s=E2s=E3s=…=Ens，則稱{Ei}是可合一的。S為{Ei}的合一者。例：{P(x,f(y),B),P(z,f(B),B)}置換s={A/x,B/y,A/z}是一個合一者,因為： P(x,f(y),B)s=P(A,f(B),B) P(z,f(B),B)s=P(A,f(B),B) 置換s={z/x,B/y}和置換s={x/z,B/y}也都是合一者。結(jié)論：合一者不唯一。第二十六頁，共七十一頁，2022年，8月28日最一般合一者（mgu） 置換最少，限制最少，產(chǎn)生的例最具一般性。 如前面的例子： {P(x,f(y),B),P(z,f(B),B)} 對于置換{A/x,B/y,A/z}，產(chǎn)生的例是： P(A,f(B),B) 對于置換={z/x,B/y}，產(chǎn)生的例是： P(z,f(B),B)mgu也不是唯一的。第二十七頁，共七十一頁，2022年，8月28日合一算法例：{P(x,x,Z),P(f(y),f(B),y)} 前綴表示： (Pxxz) (P(fy)(fB)y)

置換：{(fy)/x} (P(fy)(fy)z) (P(fy)(fB)y)

置換：{B/y},并使得{(fB)/x} (P(fB)(fB)z) (P(fB)(fB)B)

置換：{B/z} 得到置換：{(fB)/x，B/y，B/z} 置換后的結(jié)果：(P(fB)(fB)B)第二十八頁，共七十一頁，2022年，8月28日謂詞邏輯的歸結(jié)方法對于子句C1L1和C2L2，如果L1與~L2可合一，且s是其合一者，則(C1C2)s是其歸結(jié)式。例：P(x)Q(y),~P(f(z))R(z) =>Q(y)R(z)第二十九頁，共七十一頁，2022年，8月28日歸結(jié)舉例設(shè)公理集： (x)(R(x)L(x)) (x)(D(x)~L(x)) (x)(D(x)I(x))求證：(x)(I(x)~R(x))化子句集：

(x)(R(x)L(x))=>(x)(~R(x)L(x))=>~R(x)L(x)(1)第三十頁，共七十一頁，2022年，8月28日 (x)(D(x)~L(x))=>(x)(~D(x)~L(x))=>~D(x)~L(x)(2) (x)(D(x)I(x))=>D(A)I(A)=>D(A)(3) I(A)(4)第三十一頁，共七十一頁，2022年，8月28日目標求反： ~(x)(I(x)~R(x))=>(x)~(I(x)~R(x))=>(x)(~I(x)R(x))=>~I(x)R(x)(5)換名后得字句集： ~R(x1)L(x1) ~D(x2)~L(x2) D(A)I(A)~I(x5)R(x5)第三十二頁，共七十一頁，2022年，8月28日例題得歸結(jié)樹 ~R(x1)L(x1) ~D(x2)~L(x2) D(A)I(A)~I(x5)R(x5)I(A)

~I(x5)R(x5)

R(A){A/x5}

~R(x1)L(x1)

L(A){A/x1}~D(x2)~L(x2)~D(A){A/x2}D(A)nil第三十三頁，共七十一頁，2022年，8月28日歸結(jié)方法的特點是簡單，易于程序?qū)崿F(xiàn)。其不足是效率低，不直觀，人難于理解其"證明"過程。第三十四頁，共七十一頁，2022年，8月28日1、在命題邏輯下，可以歸結(jié)的子句C1和C2，在某種模型下C1和C2為真。則其歸結(jié)式C在該模型下（）A.必真B.必假

C.真假不能斷言

第三十五頁，共七十一頁，2022年，8月28日2、歸結(jié)證明定理時，若當前歸結(jié)式是（）,則可刪除。A.永假式B.重言式C.空子句D.可滿足式第三十六頁，共七十一頁，2022年，8月28日3、什么是置換？{g(y)/z,f(z)/y}是一個置換么？置換是形如{t1/x1,t1/x2,…,tn/xn}的一個有限集。其中，xi是變量，ti是不同于xi的項（常量、變量、函數(shù)），且xi≠xj（i≠j），i,j=1,2,…,n。{g(y)/z,f(z)/y}不是一個置換，原因是它在x和y之間出現(xiàn)了循環(huán)置換現(xiàn)象。第三十七頁，共七十一頁，2022年，8月28日應(yīng)用歸結(jié)原理進行問題求解（1）把已知前提條件用謂詞公式表示出來，并化成相應(yīng)的子句集，設(shè)該子句集的名字為S1。（2）把待求解的問題也用謂詞公式表示出來，然后將其否定，并與一謂詞ANSWER構(gòu)成析取式。謂詞ANSWER是一個專為求解問題而設(shè)置的謂詞，其變量必須與問題公式的變量完全一致。（3）把問題公式與謂詞ANSWER構(gòu)成的析取式化為子句集，并把該子句集與S1合并構(gòu)成子句集S。（4）對子句集S應(yīng)用謂詞歸結(jié)原理進行歸結(jié)，在歸結(jié)的過程中，通過合一置換，改變ANSWER中的變元。（5）如果得到歸結(jié)式ANSWER，問題的答案即在ANSWER中第三十八頁，共七十一頁，2022年，8月28日例題:某單位招聘工作人員，張三、李四、王五三人應(yīng)試，經(jīng)面試后單位有如下的想法：（1）

如果錄取張三而不錄取李四，則一定錄取王五。（2）

如果錄取李四，則一定錄取王五。（3）

三人中至少要錄取一個人。求證：王五一定會被單位錄取。（提示）定義謂詞和常量：謂詞Matr(x)表示x被錄取。Z表示張三，L表示李四，W表示王五。第三十九頁，共七十一頁，2022年，8月28日第四十頁，共七十一頁，2022年，8月28日例題:任何兄弟都有同一個父親，John和Peter是兄弟，且John的父親是David，問Peter的父親是誰？第一步：將已知條件用謂詞表示出來，并化成字句集。那么，要先定義謂詞。（1）定義謂詞：設(shè)Father(x,y)表示x是y的父親。設(shè)Brother(x,y)表示x和y是兄弟。第四十一頁，共七十一頁，2022年，8月28日（2）將已知事實用謂詞公式表示出來：F1:任何兄弟都有同一個父親。

第四十二頁，共七十一頁，2022年，8月28日第四十三頁，共七十一頁，2022年，8月28日歸結(jié)控制策略盲目歸結(jié)策略，產(chǎn)生了大量的無用的歸結(jié)式。研究以少量的歸結(jié)盡快導出空子句。第四十四頁，共七十一頁，2022年，8月28日歸結(jié)的一般策略S={C1,C2,C3,C4}(1)C1開始，逐個和C2,C3,C4比較，看哪兩個子句可以進行歸結(jié)。C2與C3,C4進行比較，C3與C4比較。得到一組歸結(jié)式，稱為第一級歸結(jié)式。(2)再從C1開始，用S中的子句分別與第一級歸結(jié)式中的子句逐個進行比較、歸結(jié)，得到第二級歸結(jié)式。(3)仍然從C1開始，用S中的子句及第一級歸結(jié)式中的子句逐個地與第二級歸結(jié)式中的子句逐個進行比較，得到第三級歸結(jié)式。如此繼續(xù)下去，知道出現(xiàn)了空子句或者不能再繼續(xù)歸結(jié)時為止。只要子句集是不可滿足的，上述歸結(jié)過程一定會歸結(jié)出空子句而終止。第四十五頁，共七十一頁，2022年，8月28日S={P,~R,~PQ,~QR}S:(1)P(2)~R (3)~PQ (4)~QR(5)Q(1)(3)歸結(jié)(6)~Q(2)(4)歸結(jié)第一級歸結(jié)式(7)~PR(3)(4)歸結(jié)(8)R(1)(7)歸結(jié)(9)~P(2)(7)歸結(jié)第二級歸結(jié)式(10)~P(3)(6)歸結(jié)(11)R(4)(5)歸結(jié)(13)NIL(1)(9)歸結(jié)第三級歸結(jié)式第四十六頁，共七十一頁，2022年，8月28日控制策略的分類刪除策略限制策略第四十七頁，共七十一頁，2022年，8月28日刪除策略刪除某些無用的子句來縮小歸結(jié)的范圍，從而提高歸結(jié)效率。包括：純文字刪除法、重言式刪除法、包孕刪除法。第四十八頁，共七十一頁，2022年，8月28日限制策略主要是對參加歸結(jié)的子句進行種種限制，盡可能地減小歸結(jié)的盲目性。以使其盡快歸結(jié)出空子句?？刂撇呗园ǎ壕€性歸結(jié)策略、單文字歸結(jié)策略、輸入歸結(jié)策略、支撐集策略等。第四十九頁，共七十一頁，2022年，8月28日刪除策略之純文字刪除法如果某文字L在子句集中不存在可與之互補的文字~L，則稱該文字為純文字。純文字不可能被消去，因而用包含它的子句進行歸結(jié)時不可能得到空子句。這樣的子句對歸結(jié)是無意義的，所以可以把它所在的子句從子句集中刪去。S={PQR,

~QR,Q,~R}P是純文字，可將子句PQR從R中刪除。第五十頁，共七十一頁，2022年，8月28日刪除策略之重言式刪除法~P(X)P(X),~P(X)Q(X)P(X)都是重言式。重言式是真值為真的子句。不管P(X)為真還是為假，

~P(X)P(X)和~P(X)Q(X)P(X)結(jié)果都為真。對于一個子句集來說，不管是增加或者刪去一個真值為真的子句都不會影響它的不可滿足性。第五十一頁，共七十一頁，2022年，8月28日刪除策略之包孕刪除法如果子句C1和C2，如果存在一個代換S,使得C1s包含于C2中，則稱C1包孕于C2。P(x)包孕于P(y)Q(z)s={y/x}P(x)包孕于P(a)s={a/x}P(x)包孕于P(a)Q(z)s={a/x}P(x)Q(a)包孕于P(f(a))Q(a)R(y)s={f(a)/x}P(x)Q(y)包孕于P(a)Q(u)R(w)s={a/x,u/y}

把子句集中包孕的子句刪去后，不會影響子句集的不可滿足性，因而可以從子句集中刪去。第五十二頁，共七十一頁，2022年，8月28日支持集策略支撐集：設(shè)有不可滿足子句集S的子集T，如果S-T是可滿足的，則稱T是S的支撐集。采用支撐集策略時，選取不同時屬于S-T的子句對，在其間進行歸結(jié)。至少有一個子句來自于支撐集T或者由T導出的歸結(jié)式。參加歸結(jié)的子句有一個是目標公式的否定所得到的子句或者他們的后裔。思想：盡量避免在可滿足的子句集中進行歸結(jié)。第五十三頁，共七十一頁，2022年，8月28日S={PQ,~PR,~QR,~R}取T={~R}支撐集歸結(jié)過程通常為：PQ~PR~QR~R~P(2)(4)~Q(3)(4)Q(1)(5)P(1)(6)R(3)(7)Nil(4)(9)第五十四頁，共七十一頁，2022年，8月28日線性歸結(jié)策略線性歸結(jié)策略首先從子句集中選取一個稱作頂子句的C0開始進行歸結(jié)。歸結(jié)過程中所得到地歸結(jié)式Ci立即同另一子句Bi進行歸結(jié)，得歸結(jié)式Ci+1，而Bi屬于S或者已經(jīng)出現(xiàn)得歸結(jié)式Cj(j<i)。簡而言之，每次歸結(jié)得到的新子句立即參加歸結(jié)，而后再加入子句集等待再次參加歸結(jié)。第五十五頁，共七十一頁，2022年，8月28日C0B0B1BnC1C2空較好的頂子句,就可以使歸結(jié)順利進行.第五十六頁，共七十一頁，2022年，8月28日輸入歸結(jié)策略對參加歸結(jié)的子句提出了如下限制：參加歸結(jié)的兩個子句中必須至少有一個是初始子句集中的子句。初始子句集就是由已知前提及結(jié)論的否定化來的子句?？梢员苊鈿w結(jié)出不必要的新子句加入歸結(jié)而造成惡性循環(huán)，可以減少不必要地歸結(jié)次數(shù)。原始子句集中沒有單元子句一定不能采用輸入歸結(jié)策略。第五十七頁，共七十一頁，2022年，8月28日~I(x)R(x)I(a)~R(y)~L(y)L(a)R(a)(1)(2)~I(x)~L(x)(1)(3)~R(a)(3)(4)~I(a)(1)(7)~L(a)(2)(6)~L(a)(3)(5)~I(a)(4)(6)NIL(2)(8)第五十八頁，共七十一頁，2022年，8月28日~I(x)R(x)I(a)~R(y)~L(y)L(a)R(a)~I(x)~L(x)~R(a)~I(a)~L(a)~L(a)~I(a)NIL第五十九頁，共七十一頁，2022年，8月28日輸入歸結(jié)策略可限制生成歸結(jié)式的數(shù)量，具有簡單、高效的優(yōu)點。例如：S={P(x)Q(x),~P(y)Q(y),P(u)~Q(u),~P(t)~Q(t)}它是不可滿足的，用輸入歸結(jié)策略卻歸結(jié)不出空子句。第六十頁，共七十一頁，2022年，8月28日單文字子句策略如果一個子句只包含一個文字，則稱它為單文字子句。單文字子句策略要求參加歸結(jié)的兩個子句中必須有一個單文字子句。第六十一頁，共七十一頁，2022年，8月28日S:(1)~I(x)

R(x)(2)I(a)(3)~R(y)~L(y)(4)L(a)S1:(5)R(a)(1)(2)(6)~R(a)(3)(4)S2:(7)~I(a)(1)(6)(8)~L(a)(3)(5)S3:NIL(2)(7)第六十二頁，共七十一頁，2022年，8月28日祖先過濾策略該策略與線性輸入策略比較相似，但放寬了限制。當兩個子句C1和C2進行歸結(jié)時，只要它們滿足下述兩個條件中的任意一個就可以進行歸結(jié)：（1）C1與C2中至少有一個是初始子句集中的子句。（2）如果兩個子句都不是初始子句集中的子句，則一個應(yīng)是另一個祖先（C2是由C1與別的子句歸結(jié)后得到的歸結(jié)式，C1是C2的祖先）第六十三頁，共七十一頁，2022年，8月28日歸結(jié)演繹推理

歸結(jié)演繹推理比較簡單又便于在計算機上實現(xiàn)。但是由于把邏輯公式化成子句集，帶來如下問題：（1）不便于閱讀與理解。(x)(Bird(x)Canfly(x))~Bird(x)Canfly(x)第六十四頁，共七十一頁，2022年，8月28日（2）有可能丟失一些重要的控制信息(~A~B)C(~A~C)B(~B~C)A~A(BC)~B(AC)~C(AB)具有不同的邏輯控制信息，卻得到相同的子句。第六十五頁，共七十一頁，2022年，8月28日對子句集S={P(x)Q(x),~P(x)R(x),~Q(x)R(x),~R(x)}使用單文字歸結(jié)策略對其進行歸結(jié)推理。第六十六頁，共七十一頁，2022年，8月28日解：單文字歸結(jié)過程如下：(1)P(x)Q(x)(2)~P(x)VR(x)(3)~Q(x)VR