謂詞邏輯基礎(chǔ)(文件)
【正文】 ? 定義：設(shè)有公式集 F＝ {F1， F2， … ， Fn}， 若存在一個置換 ?，可使 F1?＝ F2?＝ … = Fn?， 則稱 ?是 F的一個合一 。 謂詞邏輯歸結(jié)原理 謂詞邏輯歸結(jié)原理 謂詞邏輯歸結(jié)原理 謂詞邏輯歸結(jié)原理 歸結(jié)原理 ? 歸結(jié)的注意事項： 1. 謂詞的一致性 ， P()與 Q()， 不可以 2. 常量的一致性， P(a, … )與 P(b,… .)， 不可以 變量， P(a, … .)與 P(x, … )， 可以 3. 變量與函數(shù)， P(a, x, … .)與 P(x, f(x), … )，不可以； 4. 是不能同時消去兩個互補對， P∨Q 與 ～ P∨ ～ Q的空，不可以 5. 先進行內(nèi)部簡化（置換、合并） 謂詞邏輯歸結(jié)原理 ? 歸結(jié)的過程 寫出謂詞關(guān)系公式 → 用反演法寫出謂詞表達式 → SKOLEM標準形 → 子句集 S → 對 S中可歸結(jié)的子句做歸結(jié) → 歸結(jié)式仍放入 S中 ， 反復(fù)歸結(jié)過程 → 得到空子句 ?得證 謂詞邏輯歸結(jié)原理 例題 “快樂學生”問題 ? 假設(shè)任何通過計算機考試并獲獎的人都是快樂的 ， 任何肯學習或幸運的人都可以通過所有的考試 ， 張不肯學習但他是幸運的 ， 任何幸運的人都能獲獎 。 ? 歸結(jié)法的問題 ? 子句中有等號或不等號時，完備性不成立。 避免多余的 、 不必要的歸結(jié)式出現(xiàn) 。 ? 若對 S使用歸結(jié)推理過程中 ， 當歸結(jié)式 Cj是重言式（ 永真式 ） 和 Cj被 S中子句和子句集的歸結(jié)式 Ci(ij)所歸類時 ， 便將 Cj刪除 。 刪除策略對阻止不必要的歸結(jié)式的產(chǎn)生來縮短歸結(jié)過程是有效的 。 采用支撐集策略時 ， 從開始到得到 ?的整個歸結(jié)過程中 ， 只選取不同時屬于 ST的子句 ，在其間進行歸結(jié) 。 ? 支撐集策略的歸結(jié)是完備的，同樣，所有可歸結(jié)的謂詞公式都可以用采用支撐集策略達到加快歸結(jié)速度的目的。 同時還引入了文字次序 ， 約定歸結(jié)時其中的一個子句的被歸結(jié)文字只能是該子句中 “ 最大 ” 的文字 。歸結(jié)過程中所得到的歸結(jié)式 Ci立即同另一子句 Bi進行歸結(jié)得歸結(jié)式 Ci+1。如果能搞找到一個較好的頂子句，可以式歸結(jié)順利進行。 初始子句集中沒有單元子句時，單元歸結(jié)策略無效。 可以減少不必要的歸結(jié)次數(shù) 。 謂詞邏輯歸結(jié)原理 。簡單的例子，歸結(jié)結(jié)束時，即最后一個歸結(jié)式為空子句的條件是，參加歸結(jié)的雙方必須是兩個單元子句。 謂詞邏輯歸結(jié)原理 輸入歸結(jié) = 完備 與單元歸結(jié)策略相似 ， 輸入歸結(jié)策略要求在歸結(jié)過程中 ， 每一次歸結(jié)的兩個子句中必須有一個是 S的原始子句 。 謂詞邏輯歸結(jié)原理 C0 C1 C2 C3 C4 C5 空 線性歸結(jié)策略示意圖 謂詞邏輯歸結(jié)原理 單元歸結(jié) = 完備 單元歸結(jié)策略要求在歸結(jié)過程中 ， 每次歸結(jié)都有一個子句是單元子句 （ 只含一個文字的子句 ）或單元因子 。即，如下圖所示歸結(jié)得到的新子句立即參加歸結(jié)。問題是如何尋找合適的語義分類方法，并根據(jù)其含義將子句集兩個部分中的子句進行排序。一個最容易找到的支撐集是目標子句的非，即 S～ B。 謂詞邏輯歸結(jié)原理 例如： A1ΛA 2ΛA 3Λ ～ B中的～ B可以作為支撐集使用 。 盡管使用刪除策略的歸結(jié) ，少做了歸結(jié)但不影響產(chǎn)生空子句 ， 就是說刪除策略的歸結(jié)推理是完備的 。 謂詞邏輯歸結(jié)原理 ? 主要思想：歸結(jié)過程在尋找可歸結(jié)子句時 ， 子句集中的子句越多 ， 需要付出的代價就會越大 。 謂詞邏輯歸結(jié)原理 刪除策略 = 完備 ? 名詞解釋：歸類：設(shè)有兩個子句 C和 D， 若有置換 ?使得 C? ? D成立 ， 則稱子句 C把子句 D歸類 。 謂詞邏輯歸結(jié)原理 歸結(jié)過程的控制策略 ? 要解決的問題： ? 歸結(jié)方法的知識爆炸。 ? 解：先將問題用謂詞表示如下： ? R1:“任何通過計算機考試并獲獎
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1