prolog - "Who is the barber"Prolog 中的逻辑谜题

Question

我正在阅读 Raymond Smullyan 的“ mock 一只知更鸟”。书中有一个谜题是这样的:

Any resemblance between the Seville of this story and the famous Seville of Spain (which in fact there isn't) is purely coincidental. In this mythical town of Seville, the male inhabitants wear wigs on those and only those days when they feel like it. No two inhabitants behave alike on all days; that is, given any two male inhabitants, there is at least one day on which one of them wears a wig and the other doesn't. Given any male inhabitants X and Y, inhabitant Y is said to be a follower of X ifY wears a wig on all days that X does. Also, given any inhabitants X, Y, and Z, inhabitant Z is said to be a follower of X and Y if Z wears a wig on all days that X and Y both do.

Five of the inhabitants are named Alfredo, Bernardo, Ben- ito, Roberto, and Ramano. The following facts are known about them:

Fact 1.. Bernardo and Benito are opposite in their wig-wear- ing habits; that is, on any given day, one of them wears a wig and the other one doesn't.

Fact 2: Roberto and Ramano are likewise opposites.

Fact 3: Ramano wears a wig on those and only those days when Alfredo and Benito both wear one.

Seville has exactly one barber, and the following facts are known about him:

Fact 4: Bernardo is a follower of Alfredo and the barber.

Fact 5: Given any male inhabitant X, if Bernardo is a fol- lower of Alfredo and X, then the barber is a follower of X alone.

Alfredo wears only black wigs; Bernardo wears only white wigs; Benito wears only gray wigs; Roberto wears only red wigs; and Ramano wears only brown wigs.

One Easter morning, the barber was seen wearing a wig. What color was he wearing?

我发现在 Prolog 中解决这个问题会很有趣，但我很早就陷入困境:

isOpposite( bernardo, benito   ).
isOpposite( benito  , bernardo ).
isOpposite( roberto , ramano   ).
isOpposite( ramano  , roberto  ).

wears( alfredo , black ).
wears( bernardo, white ).
wears( benito  , gray  ).
wears( roberto , red   ).
wears( ramano  , brown ).

whatWearsTheBarber( WigColor ) :-
  member( Barber, [ alfredo, benito, bernardo, roberto, ramano ] ),
  wears( Barber, WigColor ).

我不知道如何有效地编码某人关注其他人，我不知道如何根据该信息进行推理。我在 Prolog 中遵循了其他一些逻辑谜题的解决方案，但我无法找出这个问题的解决方案。

编辑:这是从 Smulyan 的书中复制的解决方案:

Step 1: First, we prove that Roberto is a follower of the barber.

Well, consider any day on which the barber wears a wig. Either Alfredo wears a wig on that day or he doesn't. Suppose Alfredo does. Then Bernardo also wears a wig on that day, because Bernardo is a follower of Alfredo and the barber. So Benito can't wear a wig on that day, because he is opposite to Bernardo. Then Ramano can't wear a wig on that day, because he wears wigs only on those days when Alfredo and Benito both do, and Benito doesn't have one on this day. Since Ramano doesn't wear a wig on this day, then Roberto must, because Roberto is opposite to Ramano. This proves that on any day on which the barber wears a wig, if Alfredo also does, then so does Roberto.

Now, what about a day on which the barber wears a wig but Alfredo doesn't? Well, since Alfredo doesn't, then it cer- tainly is not the case that Alfredo and Benito both do; hence Ramano doesn't, by Fact 3, and therefore Roberto does, by Fact 2. So Roberto wears a wig on any day that the barber does and Alfredo doesn't-indeed, he wears a wig on all days that Alfredo doesn't, regardless of the barber. This proves that on any day on which the barber wears a wig, Roberto also does, regardless of whether Alfredo does or does not wear a wig on that day. So Roberto is indeed a follower of the barber.

Answer 1

编辑 2:由于@killy9999 发布了书中的部分解决方案，我决定重写我的 Prolog 以反射(reflect) Smullyan 的推理。原始部分解决方案保留在下面。

首先是一些基本结构

 person(alfredo).
 person(benito).
 person(roberto).
 person(ramano).
 person(bernardo).

 day([_Alfredo,_Benito,_Bernardo,_Roberto,_Romano]).

 % barber(alfredo). % Follows from Fact 4.
 barber(benito).
 % barber(bernardo). % Follows from Fact 4.
 barber(roberto).
 barber(romano).

 wearsWig(alfredo,[1,_X,_Y,_Z,_W]). 
 wearsWig(benito,[_X,1,_Y,_Z,_W]).
 wearsWig(bernardo,[_X,_Y,1,_Z,_W]).
 wearsWig(roberto,[_X,_Y,_Z,1,_W]).
 wearsWig(romano,[_X,_Y,_Z,_W,1]).

 noWig(alfredo,[0,_X,_Y,_Z,_W]).
 noWig(benito,[_X,0,_Y,_Z,_W]).
 noWig(bernardo,[_X,_Y,0,_Z,_W]).
 noWig(roberto,[_X,_Y,_Z,0,_W]).
 noWig(romano,[_X,_Y,_Z,_W,0]).

然后我们有两种类型的一致性条件。一个事实是，对方从不同时戴假发。另一个来自事实 3 和事实 4。

 consistent2(_D,[]).
 consistent2(D,[(X,Y)|Os]):-wearsWig(X,D),noWig(Y,D),consistent2(D,Os).
 consistent2(D,[(X,Y)|Os]):-noWig(X,D),wearsWig(Y,D),consistent2(D,Os).

 consistent3(O,G):-consistent3(O,_D,G).

 consistent3(_O,_D,[]).
 consistent3(O,D,[(X,Y,Z)|Gs]):-
     wearsWig(X,D),wearsWig(Y,D),wearsWig(Z,D),
     consistent2(D,O),consistent3(O,D,Gs).
 consistent3(O,D,[(_X,Y,_Z)|Gs]):-
     noWig(Y,D),consistent2(D,O),consistent3(O,D,Gs).
 consistent3(O,D,[(_X,_Y,Z)|Gs]):-
     noWig(Z,D),consistent2(D,O),consistent3(O,D,Gs).

fact3(D):-wearsWig(romano,D),wearsWig(alfredo,D),wearsWig(benito,D).
fact3(D):-noWig(alfredo,D),noWig(romano,D).
fact3(D):-noWig(benito,D),noWig(romano,D).

这足以证明 Roberto 遵循了 Barber(步骤 1):

 ?- person(Barber),barber(Barber),
    O = [(benito,bernardo),(roberto,romano)],
    G = [(bernardo,alfredo,Barber),(romano,alfredo,benito)],
    consistent3(O,D,G),fact3(D),
    wearsWig(Barber,D),noWig(roberto,D).
 false.

因此排除了罗马诺作为理发师的可能性。

我们也已经得到(第 2 步)Bernardo 跟随 Roberto 和 Alfredo:

 ?- person(Barber)barber(Barber),
    O = [(benito,bernardo),(roberto,romano)],
    G = [(bernardo,alfredo,Barber),(romano,alfredo,benito)],
    consistent3(O,D,G),fact3(D),
    wearsWig(alfredo,D),wearsWig(roberto,D),noWig(bernardo,D).
 false.

下一步(第 3 步)需要使用事实 5，这是一个通用陈述(适用于塞维利亚的所有男性居民)并且很难在 Prolog 中进行编码。

 consistent4(_D,_Barber,[]).
 consistent4(D,Barber,[X|Xs]):-
    wearsWig(X,D1),wearsWig(alfredo,D1),
    noWig(bernardo,D1),consistent4(D,Barber,Xs).
 consistent4(D,Barber,[X|Xs]):-
    wearsWig(X,D),wearsWig(alfredo,D),
    wearsWig(bernardo,D),wearsWig(Barber,D),
    consistent4(D,Barber,Xs).

现在定义根谓词和花哨的颜色:

wears(alfredo, black).
wears(bernardo, white).
wears(benito, gray).
wears(roberto, red).
wears(ramano, brown).

whatWearsTheBarber(WigColor):-
   person(Barber),
   day(Easter),
   barber(Barber),
   wearsWig(Barber,Easter),
   fact3(Easter),
   G=[(bernardo,alfredo,Barber),(romano,alfredo,benito)],
   O=[(benito,bernardo),(roberto,romano)],
   consistent2(Easter,O), 
   consistent3(O,D,G),
   X=[alfredo,benito,bernardo,roberto,romano],
   consistent4(D,Barber,X),
   wears(Barber, WigColor).

以下 SWI-Prolog 查询显示 RED 是唯一的答案

 ?- findall(WigColor,whatWearsTheBarber(WigColor),B),list_to_set(B,R).
 B = [red, red, red, red, red, red, red, red, red|...],
 R = [red].

感谢安德鲁·库克。我借鉴了他的回答。

下面的文字是最初发布并产生评论的答案。

编辑:这个谜题实际上非常困难，因为人们必须跟踪许多天，而不仅仅是特定的复活节。以下解决方案仅考虑特定日期塞维利亚的事态，从而大大减少了搜索。

将塞维利亚市的情况视为以列表表示的未知关系可能更容易:

 [ [WearsWig,IsBarber], ... , [WearsWig,IsBarber] ]

以目前的人口，我们可以说

 seville(S) :- 
       S=[Benito,Bernardo,Roberto,Ramano,Alfredo], 
       opposite(Benito,Bernardo),
       opposite(Roberto,Ramano),
       fact3(Ramano,Alfredo,Benito),
       fact4(Bernardo,Alfredo),
       noBarber(Bernardo),noBarber(Alfredo),
       onlyOneBarberWearsWig(S).

相关谓词定义如下:

 noWig([0,_X]).
 wearsWig([1,_X]).

 isBarber([_X,1]).
 noBarber([_X,0]).

 opposite(X,Y):-noWig(X),wearsWig(Y). 
 opposite(X,Y):-noWig(Y),wearsWig(X).


 fact3(X,Y,Z):-wearsWig(X),wearsWig(Y),wearsWig(Z).
 fact3(X,Y,_Z):-noWig(X),noWig(Y).
 fact3(X,_Y,Z):-noWig(X),noWig(Z).

 fact4(X,Y):-wearsWig(X),wearsWig(Y),wearsWig(Z),isBarber(Z).
 fact4(_X,Y):-noWig(Y).

 onlyOneBarberWearsWig([X|Xs]):-isBarber(X),wearsWig(X),noBarbers(Xs).
 onlyOneBarberWearsWig([X|Xs]):-noBarber(X),onlyOneBarberWearsWig(Xs).
 noBarbers([]).
 noBarbers([X|Xs]):-noBarber(X),noBarbers(Xs).

 barbersWigColor([_X,_Y,_Z,_U,Alfredo],black):-isBarber(Alfredo).
 barbersWigColor([_X,Bernardo,_Y,_Z,_U],white):-isBarber(Bernardo).
 barbersWigColor([Benito,_X,_Y,_Z,_U],gray):-isBarber(Benito).
 barbersWigColor([_X,_Y,Roberto,_Z,_U],red):-isBarber(Roberto).
 barbersWigColor([_X,_Y,_Z,Ramano,_U],brown):-isBarber(Ramano).

 whatWearsTheBarber(Color):-seville(X),barbersWigColor(X,Color).

有了上面的定义，SWI 很快就返回了:

 ?- seville(X).
 X = [[0, 0], [1, 0], [1, 1], [0, 0], [0, 0]] ;
 X = [[0, 0], [1, 0], [1, 1], [0, 0], [1, 0]] ;
 X = [[0, 0], [1, 0], [1, 1], [0, 0], [0, 0]] ;
 X = [[1, 1], [0, 0], [1, 0], [0, 0], [0, 0]] ;
 X = [[1, 0], [0, 0], [1, 1], [0, 0], [0, 0]] ;
 false.


 ?- whatWearsTheBarber(Color).
 Color = red ;
 Color = red ;
 Color = red ;
 Color = gray ;
 Color = red ;
 false.

我不太明白 Fact 5 是如何工作的。我不能排除贝尼托是理发师的情况。但我想将此作为答案发布。