文章目錄

• • • 量詞的推理規則
    • • 代換（置換，substitution）
      • 全稱量詞實例化（UI規則）
      • 存在量詞的實例化
    • 合一和提升
    • • 一般假言推理規則
      • 合一
    • 歸結
    • • 一階邏輯的合取范式CNF
      • 一階邏輯的歸結推理規則（消解原理）
      • 歸結反駁(Resolution Refutation)
    • 前向鏈接與反向鏈接
    • • 一階限定字句（一階確定子句）
      • 后向鏈接
    • 一階邏輯語句翻譯示例
    • 資源分享

量詞的推理規則

在命題邏輯中，根據歸結原理：
可由P∨R, Q∨￢R 得到 P∨Q
可由P∨R(a), Q∨￢R(a) 得到 P∨Q
那么，可由P∨R(x), Q∨￢R(y) 得到P∨Q嗎？
這里，首先需要了解代換（置換，substitution）。

代換（置換，substitution）

Subst(θ, α), θ is like {x/Michael, y/Bob}，其中θ是substitution，α是centence。

• (?x )( Man ( x ) ? Mortal ( x ))
• Subst({ x / Michael }, (?x)(Man(x) ? Mortal(x)))
• Man(Michael) ? Mortal(Michael)

只能將變元代換成常量，不能將常量代換成常量或者常量代換成變元。

• Subst({Michael/x}, Man(Michael) ? Mortal(Michael))
  = Max(x) ? Mortal(x) no
• Subst({Michael/Bob}, Man(Michael) ? Mortal(Michael))
  = Max(Bob) ? Mortal(Bob) no
• Subst({x/Bob}, Man(x) ? Mortal(x))
  = Max(Bob) ? Mortal(Bob) yes

全稱量詞實例化（UI規則）

UI規則：用基項（沒有變量的項）置換變量得到的語句。
注意：置換是用一個項（語法成分）替代某個變量，產生新語句，而解釋則將變量映射到論域中的某個對象。

存在量詞的實例化

Subst({Michael/x} ,?x AtAI(x)∧Sleep(x)
=AtAI(Michael)∧Sleep(Michael)

上面替換y的不是skolem常量而是關于x的Skolem函詞

例子：
Subst({m(y)/x},?y?xMother(x,y)
=?y Mother(m(y),y)
在邏輯中，這個新的名稱Michael在知識庫中其他地方未出現過，把它稱作Skolem常數。
存在量詞實例化的過程叫做Skolem標準化。
上述的m(y)是一個Skolem函數。

全稱量詞實例化可以應用多次而得到不同的結果，而存在量詞實例化只能應用一次，然后存在量化的語句就可以被拋棄。

一旦進行了去量詞產生新語句的操作，就可能將一階邏輯簡化成為命題邏輯。

合一和提升

一般假言推理規則

對于原子語句$p_i$、$p_i^{\prime }$和$q$,存在置換$\theta$使得對所有的i都有$SUBST(\theta ,p_i^{\prime })$成立，

$$\frac{p_1^{\prime },p_2^{\prime },...,p_i^{\prime },(p_1\wedge p_2\wedge ...\wedge p_n?q)}{SUBST(\theta ,q)}$$
該規則有n+1個前提：n個原子語句$p_i'$和一個蘊含式。結論就是將置換應用于后項q得到的語句。

在邪惡的國王的例子中：
$p_1^{\prime }$是King(John) p1是King(x)
$p_2^{\prime }$是Gredy(y) p2是Gredy(x)
θ是{x/John,y/John} q是Evil(x)
SUBST(θ,q)是Evil(John)

一般化假言推理規則是假言推理規則的升級版本，它將假言推理規則從（沒有變量的命題邏輯）提高到一階邏輯。

合一

合一（Unification）：找到使不同的邏輯表示變得相同的置換的過程。合一是所有一階邏輯推理算法的關鍵。合一算法UNIFY以兩條語句為輸入，如果合一置換存在則返回它們的合一元（unifier）θ：
UNIFY(p,q)=θ where SUBST(θ,p)=SUBST(θ,q)

也有可能有多個合一元，即多種置換方式：

• UNIFY (Knows(John,x), Knows(y,z))
• unifier：{y/John, x/z} or {x/John, y/John, z/John}
• ? Knows (John, z) or Knows (John, John)

上例的最一般合一置換是{y/John, x/z} 。
結果表明，對每對可合一的表達式，存在唯一的最一般合一置換（MGU）。不考慮變量的取名情況它是唯一的（如{x/John}和{y/John}是等價的，{x/John, y/John}和{x/John，y/x}也是等價的）。

歸結

一階邏輯的合取范式CNF

一階邏輯的每個語句都可以轉化成推理等價的CNF語句。特別是，CNF語句只有當原始語句不可滿足時才不可滿足，這是應用CNF語句上的反證法證明的基礎。
轉換成CNF的過程和命題邏輯類似。主要的不同在于一階邏輯要消除存在量詞。
步驟如下：

• Eliminate implications 消除蘊含詞
• Move negation inwards 將￢內移
• Standardize variables 變量標準化
• Skolemize Skolem化
• Drop universal quantifiers 刪除全稱量詞
• Distribute ∧ over ∨ 將∧分配到∨中

try：

$$?x\left\{P(x)?[?y[P(y)?P(f(x,y))]\wedge ??y[Q(x,y)?P(y)]]\right\}$$

一階邏輯的歸結推理規則（消解原理）

一階邏輯的子句的歸結規則簡單而言就是命題邏輯歸結規則的升級版本。
$$\frac{l_1\vee ...\vee l_k,m_1\vee ...\vee m_n}{SUBST(\theta ,l_1\vee ...\vee l_{i?1}\vee l_{i+1}\vee ,...,\vee l_k\vee m_1\vee ...\vee m_{j?1}\vee m_{j+1}\vee ...\vee m_n)}$$
其中$UNIFY(l_i,?m_j)=\theta$

一個二元歸結規則的例子如下，剛好可以對兩個文字進行歸結：
通過合一置換θ={u/G(x),v/x}消除互補文字Loves(G(x),x)和?Loves(u,v)，可以對兩個子句進行歸結：
[Animal(F(x))∨Loves(G(x),x)]和[?Loves(u,v)∨?Kills(u,v)]
產生歸結子句:[Animal(F(x))∨?Kills(G(x),x)]

全歸結規則對每個可合一的子句中的文字子句進行歸結。
另外一種方法是歸并：去除冗余文字。命題邏輯的歸并是指如果兩個文字相同，則將這兩個文字減少到一個；一階邏輯的歸并是指如果這兩個文字可合一，則將這兩個文字減少到一個。合一置換必須應用到整個子句。

歸結反駁(Resolution Refutation)

證明：KB ╞ α
反證法思路：證明KB∧?α不可滿足，即推導出空語句

理發師悖論(Barber Paradox)
在某個城市中有一位理發師，他的廣告詞是這樣寫的：“本人的理發技藝十分高超，譽滿全城。我將為本城所有不給自己刮臉的人刮臉，我也只給這些人刮臉。我對各位表示熱誠歡迎！”來找他刮臉的人絡繹不絕，自然都是那些不給自己刮臉的人。

可是，有一天，這位理發師從鏡子里看見自己的胡子長了，他本能地抓起了剃刀，你們看他能不能給他自己刮臉呢？如果他不給自己刮臉，他就屬于“不給自己刮臉的人”，他就要給自己刮臉，而如果他給自己刮臉呢？他又屬于“給自己刮臉的人”，他就不該給自己刮臉。

證明：不存在這樣的理發師

存在一個人只為每個不給自己刮胡子的人刮胡子。
?p?q S(p,q)?￢S(q,q)

?x Horse(x)? Animal(x)
等于?x(￢ Horse(x)∨Animal(x))
不等于￢ ?x(Horse(x)∨Animal(x))

庸醫問題(quack problem)

前向鏈接與反向鏈接

在命題邏輯中，給出了命題邏輯限定子句的前向鏈接算法：從知識庫中的原子語句出發,在前向推理中應用假言推理規則,增加新的原子語句,直到不能進行任何推理。

下面討論在一階邏輯中，如何應用于一階限定子句,如何高效地實現。

一階限定字句（一階確定子句）

一階限定子句和命題邏輯中的限定子句非常相似：它們是文字的析取，其中正好只有一個正文字。它可以是原子語句;或是蘊含語句,蘊含語句的前提是正文字的合取,結論是單個正文字。
例如：
King(x) ∧ Greedy(x) ?Evil(x)
King(John)
Greedy(y)

和命題邏輯文字不同，一階限定子句中,一階文字可以包含變量，假設變量是全稱量化的,書寫時省略全稱量詞

有些知識庫可寫成限定子句的集合,但并非每個知識庫都可寫為限定子句的集合(單一正文字的限制過于嚴格)。

考慮以下問題:
美國法律規定美國人販賣武器給敵對國家是犯法的。美國的敵對國家Nono有一些導彈,所有這些導彈都是美國人West上校賣給他們的。
證明West是罪犯(criminal)。

用一階限定子句來表示這些事實：

• （1）美國人販賣武器給敵對國家是犯法的：American ( x )∧ Weapon ( y )∧ Sells ( x , y , z )∧ Hostile ( z ) ?Criminal ( x )
• Nono…有導彈：?x Owns ( Nono , x )∧ Missile ( x )
• 消去存在量詞被轉換成兩個限定子句:
• （2）Owns ( Nono , M1 )
• （3）Missile ( M1 )
• （4）所有該國的導彈都購自West上校：Missile ( x )∧ Owns ( Nono , x ) ? Sells ( West , x , Nono )
• （5）還需要知道導彈是武器：Missile ( x ) ? Weapon ( x )
• （6）還需要知道美國的敵人被稱為“敵對的”：Enemy ( x , America ) ? Hostile ( x )
• （7）West,一個美國人：American ( West )
• （8）Nono國,美國的敵人：Enemy ( Nono , America )

后向鏈接

一階邏輯語句翻譯示例

1.使用三個謂詞：HeadOf(h,x)(h是x的頭),Horse(x),Animal(x)
前提：馬是動物
?x Horse(x)? Animal(x)
結論：一匹馬的頭是一只動物的頭
?x,h Horse(x)∧HeadOf(h,x) ? ?yAnimal(y) ∧ HeadOf(h,y)

資源分享

實驗代碼下載：
https://github.com/yyl424525/AI_Homework
人工智能-一種現代方法中文第三版pdf、課件、作業及解答、課后習題答案、實驗代碼和報告、歷年考博題下載：https://download.csdn.net/download/yyl424525/11310392

總結

以上是生活随笔為你收集整理的人工智能 一种现代方法 第9章 一阶逻辑的推理的全部內容，希望文章能夠幫你解決所遇到的問題。

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