Prolog/邏輯入門

由於 Prolog 很大程度上基於形式邏輯，因此在開始學習這門語言之前，瞭解一些邏輯知識非常有用。這是一篇針對想要學習 Prolog 的人的簡短邏輯入門。它將討論兩種邏輯語言：命題邏輯和一階邏輯。

命題邏輯

命題邏輯有兩個基本元素：**項**和**聯結詞**。項由字母表示（通常是大寫字母），代表**真**和**假**的值，即項可以是真或假，但並不總是必須明確說明它們代表哪個。從某種意義上說，它們就像數學中的變數一樣，代表未知值。

聯結詞，顧名思義，將兩個項連線起來。這種連線的結果將取真或假值，具體取決於兩個項的值。例如，考慮聯結詞 AND。它可以連線項 A 和 B 以形成邏輯句子 "A AND B"。（任何可以取真或假值的東西都被稱為句子。）句子 "A AND B" 在 A 和 B 都為真時為真。如果其中一個或兩個都為假，那麼該句子為假。聯結詞通常用符號而不是單詞表示。下表顯示了最常用的聯結詞、它們的含義以及通常用來表示它們的符號。

名稱	用法	翻譯	意義	符號
合取	$A\land B$	A 且 B	當且僅當兩個項都為真時，該句子才為真	$\land \quad ,$
析取	$A\lor B$	A 或 B	當一個或兩個項都為真時，該句子為真	$\lor \quad ;$
異或	$A\oplus B$	A xor B	當其中一個項為真，但不是兩個都為真時，該句子為真	$\oplus \quad {\underline {\lor }}\quad$
否定	$\lnot A$	非 A	當該項為假時，該句子為真；當該項為真時，該句子為假	$\sim \quad \lnot \quad {\bar {q}}$
蘊涵	$A\rightarrow B$	A 邏輯蘊涵 B	如果 A 為真，則該句子僅當 B 為真時才為真；如果 A 為假，則該句子為真	$\rightarrow \quad \Rightarrow \quad \models$
等價	$A\leftrightarrow B$	A 邏輯等價於 B	當兩個項都為真或兩個項都為假時，該句子為真	$\leftrightarrow \quad \Leftrightarrow \quad =$

要注意蘊涵的含義，因為它可能違反直覺。 $A\rightarrow \;B$ 基本上表示，如果 A 為真，那麼 B 也為真，否則 B 可以為真或假。

由於每個項只能取兩個值，因此所有可能性都可以很容易地在所謂的真值表中枚舉出來。

$A$	$B$		$A\land B$	$A\lor B$	$A\oplus B$	$\neg A$	$A\Rightarrow \;B$	$A\Leftrightarrow \;B$
F	F		F	F	F	T	T	T
F	T		F	T	T	T	T	F
T	F		F	T	T	F	F	F
T	T		T	T	F	F	T	T

下一步是使用連線詞將這些句子連線起來，以構成更復雜的句子，例如 $(A\land B)\Rightarrow \;(B\Leftrightarrow \;A)$ 或 $(A\lor B)\lor (A\lor C)$。在最後一句話中，括號可以省略，因為 $A\lor (B\lor C)$ 與 $(A\lor B)\lor C$ 相同。但是，如果存在疑問，最好使用括號來使句子的含義完全清晰。

您也可以使用真值表分析複雜的句子。

$A$	$B$		$A\land B$	$A\lor B$	$(A\land B)\lor (A\lor B)$
F	F		F	F	F
F	T		F	T	T
T	F		F	T	T
T	T		T	T	T

現在我們可以將句子分為三類：有效、不可滿足和可滿足。

• 有效句子（又稱重言式）始終為真，無論它們的項取何值。
  有效句子的例子包括
  1. $A\lor (\lnot A)$
  2. $A\Rightarrow A$
  3. $(A\Rightarrow B)\lor (A\land (\lnot B))$
• 不可滿足句子（又稱矛盾）始終為假，無論它們的項取何值。
  不可滿足句子的例子包括
  1. $A\land (\lnot A)$
  2. $(A\Rightarrow B)\land (A\land (\lnot B))$
• 可滿足句子（又稱偶然式）是指可以為真或假的句子，具體取決於其項的取值。
  可滿足句子的例子包括
  1. $A$
  2. $A\lor B$
  3. $A\land B$

意義和意圖

在邏輯語言中，要意識到這些句子可以以不同的方式使用，這一點非常重要。例如，$A\wedge B$ 本身沒有隱含任何意義。它只是一種建立邏輯結構的形式化方法。有人可以 **宣告** $A\wedge B$ 為真，這將賦予句子意義（即 A 和 B 都為真），可以用來推匯出進一步的真理，如果已知關於 A 和 B 的其他資訊。有人也可能 **詢問** $A\wedge B$ 是否為真，被問到這個問題的人必須根據已經知道的關於 A 和 B 的東西找到答案。換句話說，一個邏輯句子本身沒有意義。讀者需要知道句子的意圖（通常是問題或陳述）才能對其進行操作。邏輯中常見的結構是知識庫，它是一組被宣告為真的句子，以及一個作為問題提出的單個句子。問題是，鑑於知識庫，該問題是否為真。例如，考慮以下知識庫

$A\wedge B$
$~B$

以及問題

$A$

也就是說，鑑於知識庫，A 是否為真。很明顯，這個問題確實是真，因為 $A\wedge B$ 為真，B 也為真。這種知識庫/問題結構實際上是 Prolog 的工作方式。你編寫一個知識庫（你的程式）並向 Prolog 提出一個問題。與傳統的程式語言相比，知識庫是你的程式，問題是它的輸入，Prolog 解決你的問題就是執行程式。

一階邏輯

一階邏輯（也稱為謂詞邏輯）擴充套件了命題邏輯，使用謂詞、變數和物件。在命題邏輯中，原子句子（可以取真/假值的最小元素）是項，由字母表示的符號。在一階邏輯中，原子句子是 **謂詞**。謂詞有一個名稱（以大寫字母開頭），後面跟著幾個 **變數**（以小寫字母開頭）。以下是謂詞的示例

• Predicate(variable1, variable2)
• BrotherOf(sibling, brother)
• MotherOf(child, mother)
• HasWheels(thing)

這些變數可以用 **物件** 來例項化。物件是以大寫字母開頭的詞語表示的元素。例如，在謂詞 $HasWheels(thing)$ 中，變數 thing 可以用物件 Car、Bike 或 Banana 來例項化。根據變數的例項化，謂詞為真或假（$HasWheels(Car)$ 為真，而 $HasWheels(Banana)$ 為假）。但是，請注意，這些名稱僅是為了可讀性，它們本身實際上沒有任何意義。 $HasWheels(Banana)$ 與 $X(A)$ 或 $WrUlS(OvqPv)$ 在功能上沒有區別。是否 $HasWheels(Banana)$ 為真或假需要以某種形式化方式定義（例如知識庫，將在下面描述）。

這些謂詞可以用連線詞（連線詞與命題邏輯中的連線詞相同）連線在句子中，就像命題邏輯中的項一樣。通常，有一組被假定為真的句子，用於建立謂詞的邏輯定義。這樣一組被假定為真的句子被稱為 **知識庫**。例如，這樣一個知識庫可能包含以下句子

HasWheels(Car)
MotherOf(Charles, Elizabeth)

這些句子告訴我們，如果第一個元素是汽車，則 HasWheels 謂詞為真；如果第一個元素是 Charles，第二個是 Elizabeth，則 MotherOf 謂詞為真。為了構建這種包含變數的句子，我們需要說明在使用變數時我們究竟指的是什麼。如果 HasWheels(x) 為真，我們指的是它對 x 的例項化都為真，還是說存在 x 的一個例項化使得 HasWheels(x) 為真？為了定義這一點，我們使用 **量詞**，即它們確定變數的數量。一階邏輯有兩個量詞：**全稱量詞** $\forall$ 和 **存在量詞** $\exists$。這些量詞放在變數之前，以表明變數在量詞之後的句子中所代表的含義。例如，句子 $\forall xHasWheels(x)$ 表示對 x 的所有可能例項化，HasWheels(x) 都為真，也就是說，所有可能的物體都有輪子。句子 $\exists xHasWheels(x)$ 表示存在至少一個物體 x 使得 HasWheels(x) 為真，換句話說，至少存在一個東西有輪子。為了理解量詞的使用，請考慮以下示例

• 如果 x 是陸地車輛，那麼 x 擁有輪子。（如果 x 不是陸地車輛，則該句子對 x 沒有任何說法）

$\forall {x}LandVehicle(x)\Rightarrow HasWheels(x)$

• 如果 x 有一個孩子 y 且 x 是男性，則 x 是 y 的父親。

$\forall {x,y}HasChild(x,y)\wedge Man(x)\Rightarrow FatherOf(y,x)$

• 存在至少一個物體既有輪子，又不是汽車

$\exists {x}HasWheels(x)\wedge \sim Car(x)$

• 所有的母親都有一個孩子

$\forall {x}Mother(x)\Rightarrow \exists {y}Child(y)\wedge HasChild(x,y)$

Prolog 中的邏輯

Prolog 中使用的邏輯是一階邏輯的一種版本，使用大寫字母反轉（謂詞和物件以小寫字母開頭，變數以大寫字母開頭）。Prolog 程式由一個知識庫組成，其中每個句子都是謂詞的合取，連線到一個具有蘊涵關係的最終謂詞。例如

$\forall a,b,c,dPred1(a,b)\wedge Pred2(b,c)\wedge Pred3(c,d)\Rightarrow Pred4(a)$

這樣的句子稱為霍恩子句。在 Prolog 中，上面的句子將如下所示

pred4(A) :- pred1(A, B), pred2(B, C), pred3(C, D).

請注意，蘊涵符號被反轉，逗號用於合取，句號用於結束句子，並且所有變數都被假定為是全稱量詞。

示例

對所有 x：貓(x) 或 狗(x) 蘊涵 寵物(x)

練習

(x) 為以下命題邏輯中的句子寫出真值表。
a) $(A\wedge B)VC$
b) $A$
c) $A$
d) $A$
e) $A$

(x) 連線兩個項的連線詞有多少種？為什麼？

(x) 嘗試找到一個公式來擬合以下真值表
a)
b)
c)
d)

(x) 真值表是證明命題公式為真的一個好方法。你能對一階邏輯做同樣的事情嗎？解釋如何或為什麼不能。

(x) 將以下句子轉換為一階邏輯。嘗試密切遵循句子的邏輯結構（使用物件表示個體，使用變量表示人組，使用連線詞表示邏輯結構，使用謂詞表示其餘部分）。
a) 所有的孩子都很矮。
b) 一些孩子擁有鞋子。
c) 如果一個人是孩子且是男孩，那麼他喜歡汽車。
d) 所有擁有鞋子的孩子都穿鞋子。
e) 所有的孩子都有母親。
f) 如果一個女人是母親，那麼她有一個孩子。
g) 如果蔬菜煮過頭了，那麼沒有孩子喜歡蔬菜。
h) 如果老師懲罰了她的孩子，那麼沒有母親喜歡老師。

(x) (高階) 以下問題與 = 符號有關。它接受兩個變數，如果它們繫結到相同的東西，則為真，換句話說，如果 x 和 y 代表同一個物件，則 x = y 為真。
(a) = 符號是函式、謂詞還是連線詞？為什麼？
(b) = 符號不應該與等式連線詞混淆。它們有什麼不同？
(c) 你能想到一個一階邏輯中的句子，當它被新增到知識庫中（因此被認為始終為真）時，它與 = 符號做同樣的事情嗎？也就是說，透過它在知識庫中的定義，這個句子，以 'inputs' x 和 y 為輸入，如果 x 和 y 相等，則為真。
(d) 存在量詞 $\exists x$ 定義了一個句子，如果它對 x 的至少一個可能的例項化都為真，則為真。你能想到一種量化變數 x 用於句子的方法，這樣如果句子僅對 x 的一個例項化為真，但不再多，則句子為真？你可能需要為此使用 = 符號。