Abbott@AEROSPACE@sri-unix.UUCP (07/29/83)
From: Abbott at AEROSPACE (Russ Abbott)
/*
Here is a solution to the truth-tellers and liars problem.
Given the following, p(X) yields X = t(c) and X = l(b),
I.e., that c is a truth-teller and that b is a liar. It
draws no other conclusions about liars and truth-tellers.
Alternatively, one could try p(t(X)) and get c, and p(l(X))
and get b. Also notp(X) (it is not true that X) yields the
key fact: X = says(Y, l(Y), no one, neither liar nor truth-teller,
can validly call himself a liar.
*/
p(l(X)) :- % X is a liar if X says something
p(says(X, Y)), % that isn't true.
notp(Y).
p(t(X)) :- % X is a truth-teller if X says something
p(says(X, Y)), % that is true.
p(Y).
p(( p(t(X)); p(l(X)) )). % It is true that someone must be either a
p(( notp(t(X)); notp(l(X)) )). % truthteller or a liar, but not both.
notp(says(X, Y)) :- % It is not true that X said Y if either
p(( (p(t(X)), notp(Y)); % X is a truth-teller and Y is not true, or
(p(l(X)), p(Y)) )). % X is a liar and Y is true.
/* To be complete we should also define notp(t(X)) and notp(l(X)). */
p(says(b, says(a, l(a)))). % What happened: "b" said that "a" called
p(says(c, l(b))). % himself a liar, and "c" called "b" a liar.
/*
We are forced to write an logical interpreter in prolog (not very neat).
We define truth conditions for p(X). For this problem, and given the way
we have defined everything, we can get away with the following carefully
selected rules.
*/
p(( notp(X); p(X) )). % I.e, ~A or A.
p((X,Y)) :- % A conjunction is true if both of the
p(X), % conjuncts are true.
p(Y).
p(( (A, B); (C, D) )) :- % Distributivity of ';' and ','.
p(( (A; C), (A; D), (B; C), (B; D) )).