DouKaku?

['and', 'or', 'not', 'and']
のような入力が与えられた場合に、
式 x1 and x2 or not x3 and x4 の値が
Trueとなるような、x1～x4の組み合わせを全て
出力するプログラムを作成してください。
x1～x4には真と偽の2通りの値だけが入るものとします。

Pythonであれば上の入力に対し、
(True, True, True, True)
(True, True, False, True)
(True, False, False, True)
(False, True, False, True)
(False, False, False, True)
と出力します。

andとorの優先順位は同じで左結合性、
つまりa and b or c and dは
(((a and b) or c) and d)
という順番で評価されるものとします。

参考：
d.y.d.

キミならどう書く2.0の小町算問題と似てますが。

このお題はmorchinさんの投稿をもとに作成しました。 ご投稿ありがとうございました。
元ネタの 充足可能性問題 - Wikipedia は、 同じリテラル(x1とかnot x2とか)が複数回出てくることを想定しているので、 今回の問題のようにそれぞれ別の変数でだと乗法標準形 - Wikipediaにした場合に、答えが…と色々悩みどころでした。

?- solve([and, or, not, and]).
[true, true, true, true]
[true, true, fail, true]
[true, fail, fail, true]
[fail, true, fail, true]
[fail, fail, fail, true]

と言う感じです。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

solve(Ps) :-
	forall((tf(Ps, Pt, T, X), solve(Pt, T, Xs)),
	       writeln([X|Xs])).

solve([], T, []) :-
	T, !.
solve([P|Ps], T, [X|Xs]) :-
	tf(Ps, Pt, U, X),
	(   P = and -> solve(Pt, (T,U), Xs)
	;   P = or  -> solve(Pt, (T;U), Xs)
	).

tf([not|Ps], Pt, \+T, X) :-
	!, tf(Ps, Pt, T, X).
tf(Ps, Ps, X, X) :-
	member(X, [true, fail]).