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