A truth table is a display of the inputs to, and the output of a Boolean function organized as a table where each row gives one combination of input values and the corresponding value of the function.



Task

 Input a Boolean function from the user as a string then calculate and print a formatted truth table for the given function.
 (One can assume that the user input is correct).
 Print and show output for Boolean functions of two and three input variables, but any program should not be limited to that many variables in the function. 
 Either reverse-polish or infix notation expressions are allowed.


Related tasks

   Boolean values
   Ternary logic


See also

   Wolfram MathWorld entry on truth tables.
   some "truth table" examples from Google.


/*
    To evaluate the truth table a line of text is inputted and then there are three steps
    Let's say the expression is: 
    'not a and (b or c)'
 
    Step 1: tokenize into atoms and brackets
    eg: Tokenized = [ not, a, and, '(', b, or, c, ')' ].
 
    Step 2: convert to a term that can be evaluated, and get out the variables
    eg: Expression = op(and, op(not, a), op(or, b, c)), Variables = [ a, b, c ]
 
    Step 3: permeate over the variables, substituting the values for each var, and evaluate the expression for each permutation
    eg: [ 0, 0, 0]
        op(and, op(not, 0), op(or, 0, 0))
        op(and, 1, op(or, 0, 0))
        op(and, 1, 0)
        0
 
        [ 0, 0, 1]
        op(and, op(not, 0), op(or, 0, 1))
        op(and, 1, op(or, 0, 0))
        op(and, 1, 1)
        1
*/
truth_table :-
    current_input(In), 
    read_line_to_codes(In, Line),
    atom_codes(A, Line),
    atom_chars(A, Chars),
 
    % parse everything into the form we want
    phrase(tok(Tok), Chars, _),
    phrase(expr(Expr,Vars), Tok, _),
    list_to_set(Vars,VarSet),
 
    % evaluate
    print_expr(Expr, VarSet), !.
 
print_expr(Expr, Vars) :-
    % write the header (once)
    maplist(format('~p '), Vars),
    format('~n'),
 
    % write the results for as many times as there are rows
    eval_expr(Expr, Vars, Tvals, R),
    maplist(format('~p '), Tvals),
    format('~p~n', R),
    fail.   
print_expr(_, _).   
 
 
% Step 1 - tokenize the input into spaces, brackets and atoms
tok([A|As]) --> spaces(_), chars([X|Xs]), {atom_codes(A, [X|Xs])}, spaces(_), tok(As).
tok([A|As]) --> spaces(_), bracket(A), spaces(_), tok(As).
tok([]) --> [].
chars([X|Xs]) --> char(X), { dif(X, ')'), dif(X, '(') }, !, chars(Xs).
chars([]) --> [].
spaces([X|Xs]) --> space(X), !, spaces(Xs).
spaces([]) --> [].
bracket('(') --> ['('].
bracket(')') --> [')'].
 
 
% Step 2 - Parse the expression into an evaluable term
expr(op(I, E, E2), V) --> starter(E, V1), infix(I), expr(E2, V2), { append(V1, V2, V) }. 
expr(E, V) --> starter(E, V).
 
starter(op(not, E),V) --> [not], expr(E, V).
starter(E,V) --> ['('], expr(E,V), [')'].
starter(V,[V]) --> variable(V).
 
infix(or) --> [or].
infix(and) --> [and].
infix(xor) --> [xor].
infix(nand) --> [nand].
 
variable(V) --> [V], \+ infix(V), \+ bracket(V).
space(' ') --> [' ']. 
char(X) --> [X], { dif(X, ' ') }.   
 
 
% Step 3 - evaluate the parsed expression
eval_expr(Expr, Vars, Tvals, R) :-
    length(Vars,Len), 
    length(Tvals, Len), 
    maplist(truth_val, Tvals), 
    eval(Expr, [Tvals,Vars],R).
 
eval(X, [Vals,Vars], R) :- nth1(N,Vars,X), nth1(N,Vals,R).
eval(op(Op,A,B), V, R) :- eval(A,V,Ae), eval(B,V,Be), e(Op,Ae,Be,R).
eval(op(not,A), V, R) :- eval(A,V,Ae), e(not,Ae,R).
 
truth_val(0). truth_val(1).
 
e(or,0,0,0). e(or,0,1,1). e(or,1,0,1). e(or,1,1,1).
e(and,0,0,0). e(and,0,1,0). e(and,1,0,0). e(and,1,1,1).
e(xor,0,0,0). e(xor,0,1,1). e(xor,1,0,1). e(xor,1,1,0).
e(nand,0,0,1). e(nand,0,1,1). e(nand,1,0,1). e(nand,1,1,0).
e(not, 1, 0). e(not, 0, 1).