DCG と良い子悪い子普通の子

ありがちな論理パズルを解くことにします。

状況設定

ある島には、良い子、悪い子、普通の子しか住んでいません。

• 良い子はいつも正直です。
• 悪い子はいつも嘘をつきます。
• 普通の子は正直なときもあれば、嘘をつくときもあります。

この島に住む何人かの子供を捕まえて質問をして、その答えを元にどの子が良い子なのか、悪い子なのか、普通の子なのか判定を試みることにしました。

A の子はこう言いました：「B は良い子です」
B の子はこう言いました：「A は良い子ではありません」

まずは解いてみる

島民の属性は、良い子、悪い子、普通の子の三種類です：

属性(良い子).
属性(悪い子).
属性(普通の子).

それぞれの属性の子の言を検証する述語を以下のように書くことにします：

% 良い子の言及は常に真
検証する(良い子, _文章) :- call(_文章).
% 悪い子の言及は常に偽
検証する(悪い子, _文章) :- \+ call(_文章).
% 普通の子の言うことはあてにならない
検証する(普通の子, _).

すると、今回の状況は以下のように書けます：

状況(A, B) :-
    属性(A), 属性(B),
    % A は『B が良い子である』と言う
    検証する(A, B = 良い子),
    % B は『A が良い子でない』と言う
    検証する(B, \+ A = 良い子).

解を表示する :-
    findall([A,B], 状況(A, B), List),
    print(List), nl.
% コンソールで日本語をタイプするのは面倒なので別名として与えておく
solve :- 解を表示する.

これを実行すると、以下のように解が得られます。

?- solve.
[[悪い子,普通の子],[普通の子,良い子],[普通の子,普通の子]]
true.

とりあえず答えらしきものが得られました。

答えらしきものはこれで得られるのですが、果たしてこの結果は正しいのでしょうか。

それぞれの文章にあてはめて正誤を判断するのは意外に面倒です。

このパズルの結果について
「この二人のうち、少なくとも一人は本当のことを言っているけれども良い子ではない者がいる」
などと言われたとしても、それが正しいか否かを判断するのは困難です。

表示を工夫してみる

なので、もっと読みやすい普通の文章として出力させたいと思いました。
Prolog の Definite Clause Grammar(DCG) を使って日本語文を生成してみます。

良い子、悪い子、普通の子の三種類の子がいる、という記述は同じです：

属性(良い子).
属性(悪い子).
属性(普通の子).

先程は、変数 A, B に属性（良い子/悪い子/普通の子）しか入れていなかったのですが、今度はそれぞれの子につけた名前も変数に含めて 人(名前, 属性) の形で表すことにします。これは、結果を表示するときに個々人の名前も付与したいからです。

状況(A, B) -->
    % A の名前は 'A', B の名前は 'B'
    % A, B それぞれ良い子/悪い子/普通の子のいずれかの属性が付いている
    { 属性(_属性A), A = 人('A', _属性A),
      属性(_属性B), B = 人('B', _属性B) },
    % A は『B が良い子である』と言う
    言及する(A, である(B, 良い子)),
    % B は『A が良い子でない』と言う
    言及する(B, でない(A, 良い子)).

それぞれの言及を以下のように検証しつつ、文章化することにします：

言及する(_人, _文)
--> { 検証する(_人, _文, _真偽),
      _人 = 人(_名前, _属性) },
    [_名前, '(', _属性, ')', が, '『'], _文, ['』(', _真偽, ')', と言った, '。'].

ここで、_文に入るのは である/2 あるいは でない/2 の項なので、これも文章に整形します。

である(人(_名前, _実際の属性), _言及された属性)
--> [_名前, '(', _実際の属性, ')', は, _言及された属性, である].
でない(人(_名前, _実際の属性), _言及された属性)
--> [_名前, '(', _実際の属性, ')', は, _言及された属性, でない].

検証手続きは

% 良い子の言及は常に真
検証する(人(_, 良い子), _文章, 真) :- call(_文章).
% 悪い子の言及は常に偽
検証する(人(_, 悪い子), _文章, 偽) :- \+ call(_文章).
% 普通の子の言うことはあてにならない
検証する(人(_, 普通の子), _文章, _真偽) :-
    ( call(_文章) -> _真偽 = 真 ; _真偽 = 偽 ).

% 検証対象となる言
である(人(_, _実際の属性), _言及された属性) :-
    _実際の属性 = _言及された属性.
でない(人(_, _実際の属性), _言及された属性) :-
    \+ _実際の属性 = _言及された属性.

まとめると、全体はこんな感じになりました。

属性(良い子).
属性(悪い子).
属性(普通の子).

状況(A, B) -->
    { 属性(_属性A), A = 人('A', _属性A),
      属性(_属性B), B = 人('B', _属性B) },
    言及する(A, である(B, 良い子)),
    言及する(B, でない(A, 良い子)).

言及する(_人, _文)
--> { 検証する(_人, _文, _真偽),
      _人 = 人(_名前, _属性) },
    [_名前, '(', _属性, ')', が, '『'], _文, ['』(', _真偽, ')', と言った, '。'].
である(人(_名前, _実際の属性), _言及された属性)
--> [_名前, '(', _実際の属性, ')', は, _言及された属性, である].
でない(人(_名前, _実際の属性), _言及された属性)
--> [_名前, '(', _実際の属性, ')', は, _言及された属性, でない].

検証する(人(_, 良い子), _文章, 真) :- call(_文章).
検証する(人(_, 悪い子), _文章, 偽) :- \+ call(_文章).
検証する(人(_, 普通の子), _文章, _真偽) :-
    ( call(_文章) -> _真偽 = 真 ; _真偽 = 偽 ).

である(人(_, _実際の属性), _言及された属性) :-
    _実際の属性 = _言及された属性.
でない(人(_, _実際の属性), _言及された属性) :-
    \+ _実際の属性 = _言及された属性.

解を得る(_一つの文) :- phrase(状況(_, _), _状況を表す文章),
         atomic_list_concat(_状況を表す文章, _一つの文).
解を表示する :-
    解を得る(_一つの文),
    print(_一つの文), nl,
    fail.  % 失敗駆動ループ
% コンソールで日本語をタイプするのは面倒なので別名として与えておく
solve :- 解を表示する.

これを実行すると、以下のような表示が得られます：

?- solve.
'A(悪い子)が『B(普通の子)は良い子である』(偽)と言った。B(普通の子)が『A(悪い子)は良い子でない』(真)と言った。'
'A(普通の子)が『B(良い子)は良い子である』(真)と言った。B(良い子)が『A(普通の子)は良い子でない』(真)と言った。'
'A(普通の子)が『B(普通の子)は良い子である』(偽)と言った。B(普通の子)が『A(普通の子)は良い子でない』(真)と言った。'
false.

まとめ

Prolog でパズルを解いて、その結果を Definite Clause Grammar(DCG) を用いて日本語文として生成しました。