推理是求解問題的一種重要方法

魯賓遜歸結原理使定理證明能夠在計算機上實現(xiàn)

知識+推理=智能

歸結演繹：謂詞公式化為子句集、魯賓遜歸結原理、歸結反演

推理的基本概念

已知事實（數據庫）+知識 --通過策略à結論

推理方式及其分類：演繹推理、歸納推理、默認推理

1.演繹推理 (deductive reasoning) :??? 一般?? →? 個別

?三段論式（三段論法）

?足球運動員的身體都是強壯的 ；（大前提）

?高波是一名足球運動員；（小前提）

?所以，高波的身體是強壯的。（結論）

2.歸納推理 (inductive reasoning):? 個別 → 一般

完全歸納推理（必然性推理）（普查）、不完全歸納推理（非必然性推理）（抽樣）

3．默認推理（default reasoning，缺省推理）

? 知識不完全的情況下假設某些條件已經具備所進行的推理。

?

確定性推理、不確定性推理

（1）確定性推理：推理時所用的知識與證據都是確定的，推出的結論也是確定的，其真值或者為真或者為假。

（2）不確定性推理：推理時所用的知識與證據不都是確定的，推出的結論也是不確定的。

單調推理、非單調推理

（1）單調推理：隨著推理向前推進及新知識的加入，推出的結論越來越接近最終目標。 （經典邏輯）

（2）非單調推理：由于新知識的加入，不僅沒有加強已推出的結論，反而要否定它，使推理退回到前面的某一步，重新開始。（默認推理）

啟發(fā)式推理、非啟發(fā)式推理

啟發(fā)性知識：與問題有關且能加快推理過程、提高搜索效率的知識。

推理方向：

1. 正向推理（事實驅動推理）:? 已知事實? →?? 結論

（1）從初始已知事實出發(fā)，在知識庫KB中找出當前可適用的知識，構成可適用知識集KS。

（2）按某種沖突消解策略從KS中選出一條知識進行推理，并將推出的新事實加入到數據庫DB中作為下一步推理的已知事實，再在KB中選取可適用知識構成KS 。

（3）重復（2），直到求得問題的解或KB中再無可適用的知識。

實現(xiàn)正向推理需要解決的問題：

?確定匹配（知識與已知事實）的方法。

?按什么策略搜索知識庫。

?沖突消解策略。

?正向推理簡單，易實現(xiàn)，但目的性不強，效率低。

2.逆向推理（目標驅動推理）：以某個假設目標作為出發(fā)點。

? 基本思想：

?選定一個假設目標。

?尋找支持該假設的證據，若所需的證據都能找到，則原假設成立；若無論如何都找不到所需要的證據，說明原假設不成立的；為此需要另作新的假設。

? 主要優(yōu)點：不必使用與目標無關的知識，目的性強，同時它還有利于向用戶提供解釋。

? 主要缺點：起始目標的選擇有盲目性。

正向推理:? 盲目、效率低。

? 逆向推理: 若提出的假設目標不符合實際，會降低效率。

?3.正反向混合推理：

（1）先正向后逆向：先進行正向推理，幫助選擇某個目標，即從已知事實演繹出部分結果，然后再用逆向推理證實該目標或提高其可信度；

（2）先逆向后正向：先假設一個目標進行逆向推理，然后再利用逆向推理中得到的信息進行正向推理，以推出更多的結論。

如下為先正后逆：

4. 雙向推理：正向推理與逆向推理同時進行，且在推理過程中的某一步驟上“碰頭”的一種推理。

沖突消解策略:

已知事實與知識的三種匹配情況：

（1）恰好匹配成功（一對一）；

（2）不能匹配成功；

（3）多種匹配成功（一對多、多對一、多對多）à需要沖突消解

多種沖突消解策略：

（1）按針對性排序

（2）按已知事實的新鮮性排序

（3）按匹配度排序

（4）按條件個數排序（少的更接近充要）

自然演繹推理

自然演繹推理：從一組已知為真的事實出發(fā)，運用經典邏輯的推理規(guī)則推出結論的過程。

推理規(guī)則：P規(guī)則（前提引入）、T規(guī)則(結論引用)、假言推理（P, P→Q=>Q）、拒取式推理(P→Q,﹁Q=>﹁P)

證明：

定義謂詞：

?????? EASY ( x )：x 是容易的

?????? LIKE ( x,? y )：x 喜歡 y

?????? C ( x )：x 是 C 班的一門課程

已知事實和結論用謂詞公式表示：

????? (?x) ( EASY ( x ) → LIKE ( Wang,? x ) )

????? (?x) ( C ( x ) → EASY ( x ))

????? C ( ds )

????? LIKE ( Wang,? ds )

(?x)（EASY ( x )? →LIKE ( Wang,? x ))

?EASY (z) →LIKE ( Wang,? z )?????? 全稱固化

(?x) (C ( x ) → EASY ( x ))

?C ( y )? →EASY ( y ) 全稱固化

所以 C (ds), C (y) →EASY (y)? =>EASY (ds)??????? ????????P規(guī)則及假言推理

所以? EASY (ds), EASY (z)? →LIKE (Wang，z) =>LIKE ( Wang,? ds )?? T規(guī)則及假言推理

缺點：易產生組合爆炸，得到的中間結論一般呈指數形式遞增。

謂詞公式化為子句集的方法

原子（atom）謂詞公式： 一個不能再分解的命題。

? 文字（literal）：原子謂詞公式及其否定。p：正文字，﹁p：負文字。

? 子句（clause）：任何文字的析取式。任何文字本身。

? 空子句（NIL）：不包含任何文字的子句。永假

? 子句集：由子句構成的集合。

將下列謂詞公式化為子句集

1）消去謂詞公式中的“à”和“<-->”符號

（2）把﹁移到緊靠謂詞的位置上

雙重否定：

德摩根：

量詞轉化：

（3）變量標準化（轄域不同，變量名不同）

（4）消去存在量詞

a. 存在量詞不出現(xiàn)在全稱量詞的轄域內。

b. 存在量詞出現(xiàn)在一個或者多個全稱量詞的轄域內。

（5）化為前束形

前束形=（前綴）{母式}

（前綴）：全稱量詞串。

? {母式}：不含量詞的謂詞公式。

(6)化為 Skolem 標準形

（7）略去全稱量詞

（8）消去合取詞

（9）子句變量標準化

謂詞公式不可滿足的充要條件是其子句集不可滿足

魯賓遜歸結原理

子句集中子句之間是合取關系，只要有一個子句不可滿足，? 則子句集就不可滿足。

魯賓遜歸結原理（消解原理）的基本思想：

在 S 中選擇合適的子句進行歸結，一旦歸結出空子句，就說明 S 是不可滿足的。

1. 命題邏輯中的歸結原理（基子句的歸結）

?? 定義3.1（歸結）：設C1與C2是子句集中的任意兩個子句，如果 C1中的文字L1與 C2中的文字L2互補，那么從C1和 C2中分別消去L1和L2，并將二個子句中余下的部分析取，構成一個新子句C12 。

定義：歸結式C12是其親本子句C1與C2的邏輯結論。即如果 C1與C2為真，則C12為真。

推論：設C1與C2是子句集S中的兩個子句，C12是它們的歸結式，若C12 加入原子句集S，得到新子句集S1，則S與S1在不可滿足的意義上是等價的

S永假<=>S1永假

謂詞邏輯中的歸結原理（含有變量的子句的歸結）：

定義 3.2 ：若是L1與﹁L1的最一般合一，則稱

為C1、C2的二元歸結式。

?

對于謂詞邏輯，歸結式是其親本子句的邏輯結論。

對于一階謂詞邏輯，子句集是不可滿足的ó存在一個從該子句集到空子句的歸結演繹

如果沒有歸結出空子句，則既不能說 S 不可滿足，也不能說 S 是可滿足的。(可能是歸結方式錯了)

歸結反演

應用歸結原理證明定理的過程稱為歸結反演。

用歸結反演證明的步驟是：

（1）將已知前提表示為謂詞公式F。

（2）將待證明的結論表示為謂詞公式Q，并否定得到﹁ Q 。

（3）把謂詞公式集{F，﹁Q} 化為子句集S。

（4）應用歸結原理對子句集S中的子句進行歸結，并把每次歸結得到的歸結式都并入到S中。如此反復進行，若出現(xiàn)了空子句（P∨﹁P），則停止歸結，此時就證明了Q為真。

應用歸結原理求解問題

應用歸結原理求解問題的步驟：

（1）已知前提 F 用謂詞公式表示，并化為子句集 S ；

（2）把待求解的問題 Q 用謂詞公式表示，并否定 Q，再與? ANSWER 構成析取式（﹁ Q ∨ ANSWER ）；（也就是QàANSWER）

（3）把（﹁ Q∨ ANSWER） 化為子句集，并入到子句集 S中，得到子句集S’；

（4）對S’應用歸結原理進行歸結；

（5）若得到歸結式 ANSWER ，則答案就在 ANSWER 中。

?

已知：

??????? ：王（Wang）先生是小李（Li）的老師。

??????? ：小李與小張（Zhang）是同班同學。

??????? ：如果x與y是同班同學，則x的老師也是y的老師。

求：小張的老師是誰？

解：

?定義謂詞：

?

把已知前提表示成謂詞公式：

把目標表示成謂詞公式，誰教張T(x,Zhang)，并把它否定后與 ANSWER 析取：

把上述公式化為子句集：

歸結：

?

?

總結

以上是生活随笔為你收集整理的人工智能 3.确定性推理方法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。