解決Prolog中的相互遞歸約束問題

我試圖用SWI-Prolog解決一些相互遞歸的約束。這些限制都比較簡單，但在查詢任何這些謂詞導致無限遞歸：解決Prolog中的相互遞歸約束問題

%If X is an animal, then X is a bird or a mammal, and vice-versa. 
animal(X) :- 
    (mammal(X);bird(X)), 
    (male(X);female(X)). 

male(X) :- animal(X). 
female(X) :- animal(X). 

bird(X) :- (X='parrot';X='pigeon'),animal(X). 

mammal(X) :- (X='cat';X='dog'),animal(X).

是否有可能解決的Prolog這些約束而沒有讓他們非遞歸？

我寫了一個類似的方案有幾個基本的情況，但查詢mammal(X),bird(X)仍然會導致無限遞歸，而不是返回false：

%If X is an animal, then X is a bird or a mammal, and vice-versa. 
animal(X) :- 
    (mammal(X);bird(X)). 

bird('parrot'). 
bird('pigeon'). 
bird(X) :- (X='parrot';X='pigeon'),animal(X). 

mammal('cat'). 
mammal('dog'). 
mammal(X) :- (X='cat';X='dog'),animal(X).

來源

2016-07-22 Anderson Green

你意識到序言謂詞不返回像函數這樣的值，對嗎？所以'dif（哺乳動物（X），鳥（X））'不會做你認爲它可以做的事情。事實上，它總是會成功的，因爲對於任何'X'，哺乳動物（X）和鳥（X）都必然不同。正如斯科特在他的「答案」中指出的，你沒有任何事實或基本情況。 – lurker

@lurker是的，在這種情況下，「dif/2」謂詞是多餘的。我編輯了程序來糾正這個問題。 –

他們不僅僅是多餘的。他們被錯誤地使用。：除了斯科特指出的遺漏基礎案例外，你現有的邏輯是循環的。「動物/ 1」用「男/ 1」，「女/ 1」和「哺乳動物/ 1」來定義。而'男/ 1'，'女/ 1'和'哺乳動物/ 1'則按照「動物/ 1」來定義。 – lurker

使用constraint handling rules可以找到相互遞歸約束的解。

這是一組相互遞歸限制：

%If X is an animal, then X is a bird or a mammal, and vice-versa. 
:- use_module(library(chr)). 

:- chr_constraint mammal/2,bird/2,animal/1,male/1,female/1,species/2. 

animal(X) <=> 
    (mammal(X,Species);bird(X,Species)), 
    (male(X);female(X)). 

male(X),female(X) ==> false. 

bird(X,Species) <=> member(Species,[parrot,pigeon,crow]),species(X,Species). 
bird(X,Species) ==> animal(X). 

mammal(X,Species) <=> member(Species,[cat,dog,bull]),species(X,Species). 
mammal(X,Species) ==> animal(X). 

species(X,bull) ==> male(X).

...這是一個查詢的這個程序的輸出：

?- male(X),mammal(X,Species). 
male(_G67406) 
species(_G67406,cat) 
Species = cat

來源

2016-07-24 09:36:59

解決遞歸約束需要一個或多個基本情況;你還沒有提供任何。問題不在於Prolog;它與問題的定義。

來源

2016-07-22 20:17:40

當然，將這些互斥遞歸約束重寫爲非遞歸約束是可能的，但我的目標是解決相互遞歸的約束，而無需手動重寫它們。對於Prolog來說，有一個[SMT解決方案]（https://www.cs.kent.ac.uk/pubs/2012/3136/content.pdf），可能會使這更簡單。 –

有* no *求解器可以「解決」沒有任何基本情況的遞歸問題。添加基本案例不會使其不具有遞歸性;基本情況是遞歸定義的*部分*。 –

問：「有可能在Prolog中解決這些約束而不使它們不能遞歸？」;我解釋了爲什麼這個問題不健全，因此無法解決。 –

我想你想要的是你有鳥，你有哺乳動物。而且，如果它是鳥類或哺乳動物，你還試圖證明一個生物是一種動物。

該代碼目前超過規定，並具有循環邏輯。

遍歷代碼...

animal(X) :- 
    (mammal(X); bird(X)).

這就是說X是animal如果X是mammal或X是bird。到現在爲止還挺好。

的bird說明上寫着：

bird('parrot'). 
bird('pigeon').

這些事實表明，一個parrot是bird和pigeon是bird。但後來有這樣的規則：

bird(X) :- (X='parrot';X='pigeon'),animal(X).

這表示，X是bird如果X或者是一個parrot或pigeon，如果X是animal。前兩個事實已經確定parrot和pigeon是鳥類。爲什麼這個規則是必要的？而且它進一步增加了條件：X是animal，而這又是根據bird和mammal定義的，所以是循環的。

對於mammal的定義類似。它有哺乳動物所需要的事實：

mammal('cat'). 
mammal('dog').

然後overspecifies與循環邏輯：

mammal(X) :- (X='cat';X='dog'), animal(X).

你需要什麼本質很簡單：

bird('parrot'). 
bird('pigeon'). 

mammal('cat'). 
mammal('dog'). 

animal(X) :- 
    mammal(X); bird(X).

此邏輯定義什麼生物是鳥類或哺乳動物使用事實，然後提供一個規則，說如果一個生物被認爲是鳥類或哺乳動物，那麼它就是一種動物。

來源

2016-07-24 02:08:03 lurker

該解決方案適用於這種情況，但我的目標是解決相互遞歸的約束，而無需以非遞歸形式手動重寫它們。爲了做到這一點，我可能需要使用[向前鏈接]（https://en.wikipedia.org/wiki/Forward_chaining）推理引擎，如[CHR]（https://en.wikipedia.org/wiki/Constraint_Handling_Rules）。 –

這種問題的一個解決方案是簡單地啓用您的Prolog系統的製表機制。

例如，在SWI-Prolog的（最新開發版本），如果我只是在程序的開頭添加下列指令：

:- use_module(library(tabling)). 

:- table animal/1.

然後我得到例如：

 
?- animal(X). 
false. 

?- male(X). 
false. 

?- bird(X). 
false.

因此，在這些情況下，我們仍然沒有找到任何解決方案，但至少我們可以得到答案。

來源

2016-07-24 09:17:49 mat

解決Prolog中的相互遞歸約束問題

回答

相關問題