The purpose of this section is to develop a Prolog program for calculating and displaying truth tables for Boolean expressions involving 'and', 'or', and 'not'. We seek the following kind of program behavior:
?- tt(x or (not y and z)). [x,y,z] x or (not y and z) ----------------------------------- [0,0,0] 0 [0,0,1] 1 [0,1,0] 0 [0,1,1] 0 [1,0,0] 1 [1,0,1] 1 [1,1,0] 1 [1,1,1] 1 -----------------------------------
So, the program will be required to do the following things:
- recognize infix Boolean expressions involving Boolean operations 'and', 'or', and 'not'
- find the variables in a Boolean expression
- generate an initial truth assignment for as many variables as there is in the expression
- evaluate the expression at a particular truth assignment
- generate the next truth assignment in binary count-up order
In order to use 'and' and 'or' as infix operators, declarations such as the following will suffice
:- op(1000,xfy,'and'). :- op(1000,xfy,'or').
The 'not' operator may already be recognized by Prolog (as negation as failure), but if not, then the declaration
:- op(900,fy,'not').
will make 'not' bind more tightly than 'and' and 'or'. Generally, it will probably be better to use parentheses in the Boolean expressions, rather than trying to figure out a fool-proof precedence scheme that the program user needs to know about.
To find the variables in a Boolean expression, we propose a Prolog definition whose profile is
find_vars(+The_Expression,+Previously_Found_Variables,-Answer)
indicating that the expression and the previously found variables are supplied on a call, and that the answer gets "bound" by the program.
find_vars(N,V,V) :- member(N,[0,1]),!. /* Boolean constants in expression */
find_vars(X,Vin,Vout) :- atom(X),
(member(X,Vin) -> Vout = Vin ; /* already have */
Vout = [X|Vin]). /* include */
find_vars(X and Y,Vin,Vout) :- find_vars(X,Vin,Vtemp),
find_vars(Y,Vtemp,Vout).
find_vars(X or Y,Vin,Vout) :- find_vars(X,Vin,Vtemp),
find_vars(Y,Vtemp,Vout).
find_vars(not X,Vin,Vout) :- find_vars(X,Vin,Vout).
For example,
?- find_vars(x and (y or x), [], V). V = [y,x]
Notice that find_vars will produce a list of variables in their right-to-left occurrence order in the original expression. Why? We will reverse this list of variables in the main program.
To generate the initial truth assignment, use the list of variables as a guide:
initial_assign([],[]). initial_assign([X|R],[0|S]) :- initial_assign(R,S).
For example,
?- initial_assign([w,x,y,z],A). A = [0,0,0,0]
The program to generate the successor truth assignment is as follows:
successor(A,S) :- reverse(A,R),
next(R,N),
reverse(N,S).
For example, what is proposed should work like this
[0,1,0,1] == reverse ==> [1,0,1,0] ==next==> [0,1,1,0] ==reverse==>[0,1,1,0]
where the point of reversing is that it would be easier to describe binary addition to the front of a list, rather than to the end of a list. The predicate 'next' will be a recursive N-bit binary adder, where N is the number of variables in the Boolean expression.
next([0|R],[1|R]). next([1|R],[0|S]) :- next(R,S).
Now, to evaluate the Boolean expression, a recursive-descent evaluator should be easy to define. We propose the following profile:
truth_value(+Expression,+Variable_List,+Assign_List,-Truth_Value)
so that we can expect to be able to use this in the following way.
?- truth_value(not x or y, [x,y],[1,0],V. V = 0
Here is a definition for 'truth_value'.
truth_value(N,_,_,N) :- member(N,[0,1]).
truth_value(X,Vars,A,Val) :- atom(X),
lookup(X,Vars,A,Val).
truth_value(X and Y,Vars,A,Val) :- truth_value(X,Vars,A,VX),
truth_value(Y,Vars,A,VY),
boole_and(VX,VY,Val).
truth_value(X or Y,Vars,A,Val) :- truth_value(X,Vars,A,VX),
truth_value(Y,Vars,A,VY),
boole_or(VX,VY,Val).
truth_value(not X,Vars,A,Val) :- truth_value(X,Vars,A,VX),
boole_not(VX,Val).
The 'lookup' predicate uses positional association.
lookup(X,[X|_],[V|_],V). lookup(X,[_|Vars],[_|A],V) :- lookup(X,Vars,A,V).
Now we need the driver to force the generation of the entire truth table. The intention is to construct the truth table by means of first finding the variables (already discussed), calculating an initial truth assignment (also already discussed), and then filling out the table row-by-row, or, in a picture
tt(E) :- find_vars(E,[],V),
reverse(V,Vars),
initial_assign(Vars,A),
write(' '), write(Vars), write(' '), write(E), nl,
write('-----------------------------------------'), nl,
write_row(E,Vars,A),
write('-----------------------------------------'), nl.
where write-row will call itself to write the next row of the truth table (if there should be a next row in the table).
write_row(E,Vars,A) :- write(' '), write(A), write(' '),
truth_value(E,Vars,A,V), write(V), nl,
(successor(A,N) -> write_row(E,Vars,N) ; true).
The 'write_row' definition relies of the failure of successor when A == [1,1,1,...,1]. Lastly, we supply the truth tables.
boole_and(0,0,0). boole_or(0,0,0). boole_not(0,1). boole_and(0,1,0). boole_or(0,1,1). boole_not(1,0). boole_and(1,0,0). boole_or(1,0,1). boole_and(1,1,1). boole_or(1,1,1).
Exercise 2.13.1 Add the Boolean operations 'nand', 'nor', and 'xor' to the program.
Exercise 2.13.2 Modify the truth table program so that it writes the table out to a file with the filename supplied by the user.