Prolog/剪枝和否定
本節介紹瞭如何使用剪枝來控制回溯、Prolog 中的否定方式以及兩者結合使用的有效方法。
考慮以下程式。
a :- b.
b :- c.
c :- d.
b.
如果你將此載入到 Prolog 並詢問 Prolog **?- a.**，Prolog 將首先搜尋任何可以使 **a** 為真的規則；它將 **a** 新增到其要證明的目標列表中。第一條規則表明 **a** 為真，如果 **b** 為真，那麼 Prolog 將目標 **b** 新增到其列表中。它找到了 **c** 的規則，現在需要證明 **d**，這失敗了。Prolog 現在從其列表中刪除目標 **d**，因為它無法證明它，並嘗試以不同的方式證明 **c**。這被稱為 **回溯**。Prolog 也無法證明 **c**，再次回溯並嘗試 **b**。它可以使用程式的最後一行來證明這一點，Prolog 終止。
理解 Prolog 如何評估你的查詢對於 Prolog 程式設計至關重要。為了控制 Prolog 評估你的程式的方式，你可以使用 **剪枝** 運算子：**!**。剪枝運算子是一個原子，可以以以下方式使用
a(X) :- b(X), c(X), !, d(X).
如果 Prolog 在規則中發現剪枝，它將不會回溯它所做的選擇。例如，如果它為變數 X 選擇了 frank，並遇到剪枝，那麼 Prolog 將認為 frank 是 X 的唯一選項，即使資料庫中還有其他可能性。這由以下程式說明
a(X, Y) :- b(X), !, c(Y).
b(1).
b(2).
b(3).
c(1).
c(2).
c(3).
如果我們詢問 Prolog **?- a(Q, R).** 它將首先回答
?- a(Q, R).
Q = 1
R = 1 ;
當我們使用 **;** 鍵詢問 Prolog 更多答案時：**
Q = 1
R = 2 ;
Q = 1
R = 3 ;
否
.
正如你所見，Prolog 將 1 視為 Q 的唯一選項，而它返回了 R 的所有備選方案。當 Prolog 開始進行查詢時，它試圖使用程式的第一行來證明 **a(Q, R)**。為了證明這條規則，它首先需要 **證明 b(Q)**，它在 Q = 1 時成功。然後 Prolog 遇到剪枝並將 Q = 1 設定為 Q 的唯一選項。它繼續進行規則的最後一個目標，c(R)。它首先找到 R = 1，並完成了它的目標。當用戶按下 **;** 時，Prolog 首先檢查目標 c(R) 的備選方案。請記住，當 Prolog 遇到剪枝時，它還沒有為 R 選擇例項，所以它仍然可以查詢 R 的備選方案。當它用完 R 的備選方案時，Prolog 無法查詢 Q 的備選方案，並終止。
為了理解剪枝如何改變程式的含義，請考慮以下內容
a(X) :- b(X), !, c(X).
b(1).
b(2).
b(3).
c(2).
如果沒有第一行中的剪枝，Prolog 將返回 **Q = 2** 到查詢 **?- a(Q).**。使用剪枝，Prolog 無法找到答案。為了證明這個目標，它首先使用 Q = 1 來證明 b(Q)。然後它遇到剪枝，被強制設定為 Q=1，並且無法找到 **c(1)** 的證明。如果它可以搜尋備選方案，它會發現 Q=2 使 b(Q) 和 c(Q) 都為真，但剪枝不允許這樣做。但是，如果我們詢問 Prolog **a(2)**，它將返回 yes。現在，Prolog 使用 2 來例項化程式第一行中的 X，因為使用者已經指定了它，並且當 Prolog 達到剪枝時，X 被強制設定為 2，允許 Prolog 證明 c(2)。
剪枝也跨多個規則工作。如果一個程式有兩個關於目標 **a(X)** 的規則，並且 Prolog 在第一個規則中遇到剪枝，那麼它不僅被強制設定為變數的例項，而且還被強制設定為 **a(X)** 的第一個規則。Prolog 不會考慮第二個規則。例如，以下程式
a(X) :- b(X), !, c(X).
a(X) :- d(X).
b(1).
b(4).
c(3).
d(4).
將對查詢 **?- a(X).** 失敗。Prolog 可以使用第二個規則，使用 **X =4** 和程式的最後一行來解決查詢，但 Prolog 首先嚐試第一個規則，當它遇到剪枝時，它被迫忽略 a(Q) 的所有備選方案。這一次，查詢 **?- a(4)** 也會失敗，因為 Prolog 仍然到達剪枝。當它使用第一個規則嘗試 **a(4)** 時，它成功地證明了 **b(4)** 併到達剪枝。然後它嘗試 **c(4)**，這失敗了，Prolog 必須終止。如果將 **b(4).** 和 **b(1).** 行從程式中刪除，那麼 Prolog 在遇到剪枝之前，在第一個規則上失敗，並且被允許使用第二個規則來解決查詢。
not(X) 是在 Prolog 中實現否定的方式；但是 not(X) 不意味著 X 為假，它意味著 X 無法被證明為真。
例如，使用以下資料庫
man('Adam').
woman('Eve').
詢問 not(man('Adam')). 將返回 no。
not(Goal) :- call(Goal),!,fail.
not(Goal).