4

我正在阅读 Raymond Smullyan 的“To mock a Mockingbird”。书中有一个谜题是这样的：

这个故事中的塞维利亚与西班牙著名的塞维利亚（实际上没有）之间的任何相似之处纯属巧合。在这个神秘的塞维利亚小镇，男性居民在那些而且只有在他们喜欢的时候才会戴假发。没有两个居民在所有日子里都表现得一样；也就是说，给定任何两个男性居民，至少有一天其中一个戴假发而另一个不戴。给定任何男性居民 X 和 Y，如果 Y 在 X 所做的所有日子里都戴着假发，则据说居民 Y 是 X 的追随者。此外，给定任何居民 X、Y 和 Z，如果 Z 在 X 和 Y 都做的所有日子里都戴着假发，则说居民 Z 是 X 和 Y 的追随者。

其中五个居民被命名为 Alfredo、Bernardo、Benito、Roberto 和 Ramano。关于它们的已知事实如下：

事实 1.. Bernardo 和 Benito 在戴假发的习惯上是截然相反的；也就是说，在任何一天，其中一个戴假发，另一个不戴。

事实 2：罗伯托和拉马诺同样是对立的。

事实 3：拉马诺戴假发，而且只有在阿尔弗雷多和贝尼托都戴假发的日子里。

塞维利亚只有一位理发师，关于他的已知事实如下：

事实 4：贝尔纳多是阿尔弗雷多和理发师的追随者。

事实 5：给定任何男性居民 X，如果 Bernardo 是 Alfredo 和 X 的追随者，那么理发师只是 X 的追随者。

阿尔弗雷多只戴黑色假发；贝尔纳多只戴白色假发；Benito 只戴灰色假发；罗伯托只戴红色假发；拉马诺只戴棕色假发。

一个复活节的早晨，有人看到理发师戴着假发。他穿的是什么颜色的？

我发现在 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 的书中复制的解决方案：

步骤 1：首先，我们证明 Roberto 是理发师的追随者。

好吧，考虑一下理发师戴假发的任何一天。阿尔弗雷多那天要么戴假发，要么不戴。假设阿尔弗雷多这样做。然后贝尔纳多那天也戴着假发，因为贝尔纳多是阿尔弗雷多和理发师的追随者。所以贝尼托那天不能戴假发，因为他是贝尔纳多的对面。然后拉马诺那天不能戴假发，因为他只在阿尔弗雷多和贝尼托都戴假发的日子里戴假发，而贝尼托这一天没有戴假发。既然拉马诺这一天不戴假发，那么罗伯托就必须戴，因为罗伯托是拉马诺的对面。这证明了在理发师戴假发的任何一天，如果阿尔弗雷多也戴假发，那么罗伯托也戴假发。

现在，理发师戴假发但阿尔弗雷多不戴假发的那一天呢？好吧，既然阿尔弗雷多不这样做，那么阿尔弗雷多和贝尼托当然也不会这样做；因此，根据事实 3，拉马诺没有，因此根据事实 2，罗伯托也这样做。所以罗伯托在理发师戴假发而阿尔弗雷多不戴的任何一天都戴假发——事实上，他在阿尔弗雷多不戴的所有日子里都戴假发。 t，不管理发师。这证明了在理发师戴假发的任何一天，罗伯托也戴假发，不管那天阿尔弗雷多戴假发还是不戴假发。所以罗伯托确实是理发师的追随者。

4

2 回答 2

5

Edit2：由于@killy9999 发布了书中的部分解决方案，我决定重写我的 Prolog 以反映 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).

这足以证明罗伯托遵循理发师（步骤 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 步）需要使用 Fact 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 是如何工作的。我不能排除贝尼托是理发师的情况。然而，我想将此作为答案发布。

于 2012-04-22T15:35:07.827 回答
1

发布为“答案”只是因为它需要评论。这是我第一次用 prolog 尝试这样的事情。我不确定我对 not/1 的使用是否正确。给出白色和棕色作为两个（！）答案（尽管我认为棕色会被排除在外，如果事实 4 意味着伯纳德不能成为理发师）。注释掉的部分导致无限递归。

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

opposite(bernardo, benito). % fact 1
opposite(benito, bernardo). % fact 1
opposite(roberto, ramano). % fact 2
opposite(ramano, roberto). % fact 2
opposite(X, Y):- dif(X, Y). % cannot be opposite to yourself
%opposite(X, Y):- opposite(Y, X). % symmetric

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

follower(A, A).
follower(bernardo, alfredo). % fact 4
follower(ramano, alfredo):- % fact 3
  follower(alfredo, benito); follower(benito, alfredo).
follower(ramano, benito):- % fact 3
  follower(alfredo, benito); follower(benito, alfredo).
follower(X, ramano):- % fact 3
  follower(X, alfredo); follower(X, benito).
%follower(A, B):-
%  dif(A, B),
%  person(X),
%  follower(A, X),
%  follower(X, B).

follower(A, B):- not(opposite(A, B)).
follower(B, A):- not(opposite(A, B)).

fact5(Barber):-                                                                 
  not(follower(bernardo, X));                                                   
  not(follower(bernardo, alfredo));                                             
  person(X),                                                                    
  person(Y),                                                                    
  follower(Barber, X),                                                          
  dif(Y, X),                                                                    
  not(follower(Barber, Y)).                                                     

whatWearsTheBarber(WigColor):-                                                  
  person(Barber), % implicit in question?                                       
  dif(alfredo, Barber), % fact 4                                                
  follower(bernardo, Barber), % fact 4                                          
  fact5(Barber),                                                                
  wears(Barber, WigColor).
于 2012-04-22T14:37:20.810 回答