2015年6月10日 星期三

AI - Ch11 邏輯(4), 謂詞邏輯與一階邏輯 Predicate logic and First-order logic

 

謂詞邏輯簡介
在數理邏輯中,謂詞邏輯(Predicate logic)是符號形式系統的通用術語,比如一階邏輯,二階邏輯,多類邏輯或無窮邏輯等等。

最簡單的命題邏輯只有用來代表真假值的簡單變數,像是 A, B, C, X, Y, Z .... 等,所以邏輯算式看來通常如下:
  • P & (P=>Q) => Q
  • A & B & C => D | E
  • -(A & B) <=> -A | -B

這種命題邏輯裏沒有函數的概念,只有簡單的命題 (Proposition),因此才稱為命題邏輯。而謂詞邏輯多了「布林函數」的概念,因此其表達能力較強,以下是一些謂詞邏輯的範例。
  • Parent(x,y) <= Father(x,y).
  • Parent(John, Johnson).
  • Ancestor(x,y) <= Parent(x,y).
  • Ancestor(x,y) <= Ancestor(x,z) & Parent(z,y).



[補充1]  謂詞是什麼?
謂詞,用來描述或判定客體性質、特徵或者客體之間關係的詞項。計算領域中,謂詞是指條件表達式的求值返回真或假的過程。例如:"貓是動物"一句中的"是"就是一個謂詞,而"貓"是客體。"3 大於 2"中"大於"是一個謂詞。
  • 謂詞常項 : 表示某個確定判定的謂詞稱為謂詞常項。如上述兩個謂詞"是"、"大於"。
  • 謂詞變項 : 尚未確定的謂詞稱為謂詞變項。例如用P(3,2)記一個謂詞變項,可以表示 "3大於2"、"3小於2"等等。


[補充2]  邏輯系統的層級
  • 命題邏輯 : 命題邏輯包含邏輯連詞。
  • 一階邏輯 : 命題邏輯加上個項變元(particular variable)與量詞(quantifiers,如「所有的」、「有些」等)就成為一階邏輯(first-order logic, FOL)。
  • 二階邏輯 : 一階邏輯再加上函值變元(function variable)或關係變元(relation variable),量詞作用的範圍包括這些變元,則成為二階邏輯(second-order logic)。




一階邏輯 First-order logic
命題邏輯只處理「事實」,如:現在正在下雨,而一階邏輯可以用變數處理「東西」,可將世界上的東西轉成變量量化,表達力比命題邏輯要強。如:「所有的」書, 「一些」書 (不用特地指哪一本書)



一階邏輯的組成
  • 項目(term)
    • 布林常數 (如 Fred, Japan, Virus-H1N1)
    • 布林變數 (如 x, y, z ...)
    • 函數 (如 Parent(), Father(), Ancestor() ...)
  • 語句(sentence)
    • 謂詞(predicate):
      • 一個謂詞符號可接受一至多項,例如 : on(a,b), sister(Jane, Joan), mother(Sister-of(John), Jane), its-raining()
      • 一個謂詞返回一個布林值 {T/F}
    • 等於號 (Equality)「=」:$s_1 = s_2$
    • 量詞 (Quantifier):所有 $\forall$ 、存在 $\exists$  
    • 連接詞 (Connectives) : ∧∨ ¬ ⇒ ⇔


[例題] 一階邏輯
For each English sentence on the left below, write the logic sentence on the right that best expresses it, or N (= None). note : "¬" means "not"
  • Let P(x) mean "x is a person"
  • let F(x) mean "x is a fact"
  • let K(x,y) mean "x knows y" 
  • let PKF(x,y)=[(P(x) and F(y)) → K(x,y)]. 

基礎問題
  • Every person knows every fact. : ∀x∀y PKF(x,y)
  • Every person knows some fact.  : ∀x∃y PKF(x,y)
  • Some person knows some fact.   : ∃x∃y PKF(x,y)
  • Some person knows every fact.  : ∃x∀y PKF(x,y)

進階問題(有not、被動語態)
  • No person knows every fact.    : ¬∃x∀y PKF(x,y)
  • Some person knows no fact.     : ∃x∀y ¬PKF(x,y)
  • No person knows any fact.      : ∀x∀y ¬PKF(x,y)
  • Some fact is knows by every person.  : ∃y∀x  PKF(x,y)
  • There is a fact that no person knows.: ∃y¬∃x PKF(x,y)

[用心去感覺]
轉換1:「No」可以翻譯成「不存在」,也就是 $¬ \exists$。
轉換2:$\exists$ 和 $\forall$左側的負號可以提到謂詞(predicate)旁,然後$\exists$ ($\forall$)反轉。

例如 : Some person knows no fact. 
= ∃x¬∃xPKF(x,y)     (轉換1:因為「No」翻譯成「不存在」)
= ∃x∀y ¬PKF(x,y)    (轉換2:提出負號,$\exists$ ($\forall$) 反轉)





References

交大胡毓志教授人工智慧講義

百度百科 - 謂詞
http://baike.baidu.com/view/1026648.htm

程式人雜誌 -- 2014 年 3 月號 (開放公益出版品)
http://programmermagazine.github.io/201403/htm/focus3.html






技術提供:Blogger.