解决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中的相互递归约束问题

回答

相关问题