Truth table

From Rosetta Code
Revision as of 01:48, 11 January 2016 by Thundergnat (talk | contribs) (→‎{{header|Perl 6}}: Updated to work with latest Rakudo)
Truth table is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.

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

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

D

Translation of: JavaScript

<lang d>import std.stdio, std.string, std.array, std.algorithm, std.typecons;

struct Var { 

   const char name;
   bool val;

} const string expr; Var[] vars;

bool pop(ref bool[] arr) pure nothrow { 

   const last = arr.back;
   arr.popBack;
   return last;

}

enum isOperator = (in char c) pure => "&|!^".canFind(c);

enum varsCountUntil = (in char c) nothrow => 

   .vars.map!(v => v.name).countUntil(c).Nullable!(int, -1);

bool evalExp() { 

   bool[] stack;

   foreach (immutable e; .expr) {
       if (e == 'T')
           stack ~= true;
       else if (e == 'F')
           stack ~= false;
       else if (!e.varsCountUntil.isNull)
           stack ~= .vars[e.varsCountUntil.get].val;
       else switch (e) {
           case '&':
               stack ~= stack.pop & stack.pop;
               break;
           case '|':
               stack ~= stack.pop | stack.pop;
               break;
           case '!':
               stack ~= !stack.pop;
               break;
           case '^':
               stack ~= stack.pop ^ stack.pop;
               break;
           default:
               throw new Exception("Non-conformant character '" ~
                                   e ~ "' in expression.");
       }
   }

   assert(stack.length == 1);
   return stack.back;

}

void setVariables(in size_t pos) in { 

   assert(pos <= .vars.length);

} body { 

   if (pos == .vars.length)
       return writefln("%-(%s %) %s",
                       .vars.map!(v => v.val ? "T" : "F"),
                       evalExp ? "T" : "F");

   .vars[pos].val = false;
   setVariables(pos + 1);
   .vars[pos].val = true;
   setVariables(pos + 1);

}

static this() { "Accepts single-character variables (except for 'T' and 'F', which specify explicit true or false values), postfix, with &|!^ for and, or, not, xor, respectively; optionally seperated by whitespace.".writeln; 

   "Boolean expression: ".write;
   .expr = readln.split.join;

}

void main() { 

   foreach (immutable e; expr)
       if (!e.isOperator && !"TF".canFind(e) &&
           e.varsCountUntil.isNull)
           .vars ~= Var(e);
   if (.vars.empty)
       return;

   writefln("%-(%s %) %s", .vars.map!(v => v.name), .expr);
   setVariables(0);

}</lang>

Output:
Accepts single-character variables (except for 'T' and 'F',
which specify explicit true or false values), postfix, with
&|!^ for and, or, not, xor, respectively; optionally
seperated by whitespace.
Boolean expression: A B ^
A B AB^
F F F
F T T
T F T
T T F

...
Boolean expression: A B C ^ |
A B C ABC^|
F F F F
F F T T
F T F T
F T T F
T F F T
T F T T
T T F T
T T T T

...
Boolean expression: A B C D ^ ^ ^
A B C D ABCD^^^
F F F F F
F F F T T
F F T F T
F F T T F
F T F F T
F T F T F
F T T F F
F T T T T
T F F F T
T F F T F
T F T F F
T F T T T
T T F F F
T T F T T
T T T F T
T T T T F

Déjà Vu

This example is incorrect. Please fix the code and remove this message.

Details: User input is not arbitrary but fixed to the three examples shown

<lang dejavu>print-line lst end: for v in reversed copy lst: print\( v chr 9 ) print end

(print-truth-table) t n func: if n: (print-truth-table) push-through copy t 0 -- n @func (print-truth-table) push-through copy t 1 -- n @func else: print-line t func for in copy t

print-truth-table vars name func: print-line vars name (print-truth-table) [] len vars @func print "" # extra new line

stu s t u: or s /= t u

abcd a b c d: /= a /= b /= c d

print-truth-table [ "A" "B" ] "A ^ B" @/= print-truth-table [ "S" "T" "U" ] "S | (T ^ U)" @stu print-truth-table [ "A" "B" "C" "D" ] "A ^ (B ^ (C ^ D))" @abcd</lang>

Output:
A	B	A ^ B
0	0	0
0	1	1
1	0	1
1	1	0

S	T	U	S | (T ^ U)
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	1

A	B	C	D	A ^ (B ^ (C ^ D))
0	0	0	0	0
0	0	0	1	1
0	0	1	0	1
0	0	1	1	0
0	1	0	0	1
0	1	0	1	0
0	1	1	0	0
0	1	1	1	1
1	0	0	0	1
1	0	0	1	0
1	0	1	0	0
1	0	1	1	1
1	1	0	0	0
1	1	0	1	1
1	1	1	0	1
1	1	1	1	0

Go

Expression parsing and evaluation taken from the Arithmetic evaluation task. Operator precedence and association are that of the Go language, and are determined by the library parser. The unary ^ is first, then &, then | and ^ associating left to right. Note also that the symbols &, |, and ^ operate bitwise on integer types in Go, but here since we implement our own evaluator we can apply them to the type of bool. <lang go>package main

import ( 

   "bufio"
   "errors"
   "fmt"
   "go/ast"
   "go/parser"
   "go/token"
   "os"
   "reflect"

)

func main() { 

   in := bufio.NewScanner(os.Stdin)
   for {
       fmt.Print("Expr:  ")
       in.Scan()
       if err := in.Err(); err != nil {
           fmt.Println(err)
           return
       }
       if !tt(in.Text()) {
           return
       }
   }

}

func tt(expr string) bool { 

   // call library parser
   tree, err := parser.ParseExpr(expr)
   if err != nil {
       fmt.Println(err)
       return false
   }
   // create handy object to pass around
   e := &evaluator{nil, map[string]bool{}, tree}
   // library tree traversal function calls e.Visit for each node.
   // use this to collect variables of the expression.
   ast.Walk(e, tree)
   // print headings for truth table
   for _, n := range e.names {
       fmt.Printf("%-6s", n)
   }
   fmt.Println(" ", expr)
   // start recursive table generation function on first variable
   e.evalVar(0)
   return true

}

type evaluator struct { 

   names []string        // variables, in order of appearance
   val   map[string]bool // map variables to boolean values
   tree  ast.Expr        // parsed expression as ast

}

// visitor function called by library Walk function. // builds a list of unique variable names. func (e *evaluator) Visit(n ast.Node) ast.Visitor { 

   if id, ok := n.(*ast.Ident); ok {
       if !e.val[id.Name] {
           e.names = append(e.names, id.Name)
           e.val[id.Name] = true
       }
   }
   return e

}

// method recurses for each variable of the truth table, assigning it to // false, then true. At bottom of recursion, when all variables are // assigned, it evaluates the expression and outputs one line of the // truth table func (e *evaluator) evalVar(nx int) bool { 

   if nx == len(e.names) {
       // base case
       v, err := evalNode(e.tree, e.val)
       if err != nil {
           fmt.Println(" ", err)
           return false
       }
       // print variable values
       for _, n := range e.names {
           fmt.Printf("%-6t", e.val[n])
       }
       // print expression value
       fmt.Println(" ", v)
       return true
   }
   // recursive case
   for _, v := range []bool{false, true} {
       e.val[e.names[nx]] = v
       if !e.evalVar(nx + 1) {
           return false
       }
   }
   return true

}

// recursively evaluate ast func evalNode(nd ast.Node, val map[string]bool) (bool, error) { 

   switch n := nd.(type) {
   case *ast.Ident:
       return val[n.Name], nil
   case *ast.BinaryExpr:
       x, err := evalNode(n.X, val)
       if err != nil {
           return false, err
       }
       y, err := evalNode(n.Y, val)
       if err != nil {
           return false, err
       }
       switch n.Op {
       case token.AND:
           return x && y, nil
       case token.OR:
           return x || y, nil
       case token.XOR:
           return x != y, nil
       default:
           return unsup(n.Op)
       }
   case *ast.UnaryExpr:
       x, err := evalNode(n.X, val)
       if err != nil {
           return false, err
       }
       switch n.Op {
       case token.XOR:
           return !x, nil
       default:
           return unsup(n.Op)
       }
   case *ast.ParenExpr:
       return evalNode(n.X, val)
   }
   return unsup(reflect.TypeOf(nd))

}

func unsup(i interface{}) (bool, error) { 

   return false, errors.New(fmt.Sprintf("%v unsupported", i))

} </lang> Output: 

Expr:  A ^ B
A     B       A ^ B
false false   false
false true    true
true  false   true
true  true    false
Expr:  S | ( T ^ U )
S     T     U       S | ( T ^ U )
false false false   false
false false true    true
false true  false   true
false true  true    false
true  false false   true
true  false true    true
true  true  false   true
true  true  true    true
Expr:  d^b&(c^d)
d     b     c       d^b&(c^d)
false false false   false
false false true    false
false true  false   false
false true  true    true
true  false false   true
true  false true    true
true  true  false   false
true  true  true    true

J

Implementation:

<lang j>truthTable=:3 :0 

 assert. -. 1 e. 'data expr names table' e.&;: y
 names=. ~. (#~ _1 <: nc) ;:expr=. y
 data=. #:i.2^#names
 (names)=. |:data
 (' ',;:inv names,<expr),(1+#@>names,<expr)":data,.".expr

)</lang>

The argument is expected to be a valid boolean J sentence which, among other things, does not use any of the words used within this implementation (but any single-character name is valid).

Example use:

<lang j> truthTable '-.b' 

b -.b
0   1
1   0
  truthTable 'a*b'
a b a*b
0 0   0
0 1   0
1 0   0
1 1   1
  truthTable 'a+.b'
a b a+.b
0 0    0
0 1    1
1 0    1
1 1    1
  truthTable 'a<:b'
a b a<:b
0 0    1
0 1    1
1 0    0
1 1    1
  truthTable '(a*bc)+.d'
a bc d (a*bc)+.d
0  0 0         0
0  0 1         1
0  1 0         0
0  1 1         1
1  0 0         0
1  0 1         1
1  1 0         1
1  1 1         1</lang>

Java

Works with: Java version 1.5+

This example would require a system of pages that would be moderately complicated to set up and follow (or a really huge page that would also be hard to follow) since there is no eval in Java, so you can find information about it here. There is a link to an executable jar file with the required source files there. The program shows the expression and the truth table in a window. The expression must use prefix notation, single characters for input names (numerals, lowercase letters, and uppercase letters are the easiest to read), and the outputs can be shown as 1/0 or T/F. There is also a "Check" button which will make sure that the operators have enough operands. The window looks something like this:

JavaScript

Actually a HTML document. Save as a .html document and double-click it. You should be fine. <lang javascript><!DOCTYPE html><html><head><title>Truth table</title><script> var elem,expr,vars; function isboolop(chr){return "&|!^".indexOf(chr)!=-1;} function varsindexof(chr){ var i; for(i=0;i<vars.length;i++){if(vars[i][0]==chr)return i;} return -1; } function printtruthtable(){ var i,str; elem=document.createElement("pre"); expr=prompt("Boolean expression:\nAccepts single-character variables (except for \"T\" and \"F\", which specify explicit true or false values), postfix, with \"&|!^\" for and, or, not, xor, respectively; optionally seperated by whitespace.").replace(/\s/g,""); vars=[]; for(i=0;i<expr.length;i++)if(!isboolop(expr[i])&&expr[i]!="T"&&expr[i]!="F"&&varsindexof(expr[i])==-1)vars.push([expr[i],-1]); if(vars.length==0)return; str=""; for(i=0;i<vars.length;i++)str+=vars[i][0]+" "; elem.innerHTML=""+str+expr+"\n"; vars[0][1]=false; truthpartfor(1); vars[0][1]=true; truthpartfor(1); vars[0][1]=-1; document.body.appendChild(elem); } function truthpartfor(index){ if(index==vars.length){ var str,i; str=""; for(i=0;i<index;i++)str+=(vars[i][1]?"T":"F")+" "; elem.innerHTML+=str+(parsebool()?"T":"F")+"\n"; return; } vars[index][1]=false; truthpartfor(index+1); vars[index][1]=true; truthpartfor(index+1); vars[index][1]=-1; } function parsebool(){ var stack,i,idx; console.log(vars); stack=[]; for(i=0;i<expr.length;i++){ if(expr[i]=="T")stack.push(true); else if(expr[i]=="F")stack.push(false); else if((idx=varsindexof(expr[i]))!=-1)stack.push(vars[idx][1]); else if(isboolop(expr[i])){ switch(expr[i]){ case "&":stack.push(stack.pop()&stack.pop());break; case "|":stack.push(stack.pop()|stack.pop());break; case "!":stack.push(!stack.pop());break; case "^":stack.push(stack.pop()^stack.pop());break; } } else alert("Non-conformant character "+expr[i]+" in expression. Should not be possible."); console.log(stack); } return stack[0]; } </script></head><body onload="printtruthtable()"></body></html></lang>

Output in browser window after entering "AB^":
A B AB^
F F F
F T T
T F T
T T F
Output in browser window after entering "ABC^|":
A B C ABC^|
F F F F
F F T T
F T F T
F T T F
T F F T
T F T T
T T F T
T T T T

Liberty BASIC

This at first seems trivial, given our lovely 'eval' function. However it is complicated by LB's use of 'non-zero' for 'true', and by the requirements of accepting different numbers and names of variables. My program assumes all space-separated words in the expression$ are either a logic-operator, bracket delimiter, or variable name. Since a truth table for 8 or more variables is of silly length, I regard that as a practical limit. <lang lb> print 

   print " TRUTH TABLES"
   print
   print " Input a valid Boolean expression for creating the truth table "
   print " Use lowercase 'and', 'or', 'xor', '(', 'not(' and ')'."
   print
   print " Take special care to precede closing bracket with a space."
   print
   print " You can use any alphanumeric variable names, but no spaces."
   print " You can refer again to a variable used already."
   print " Program assumes <8 variables will be used.."
   print
   print " eg 'A xor B and not( C or A )'"
   print " or 'Too_High xor not( Fuel_Out )'"

   print

[start]
   input "        "; expression$
   if expression$ ="" then [start]

   print

   'used$           =""
   numVariables    =0  '   count of detected variable names
   variableNames$  ="" '   filled with detected variable names
   i               =1  '   index to space-delimited word in the expression$

 [parse]
   m$ =word$( expression$, i, " ")
   if m$ ="" then [analyse]
   '   is it a reserved word, or a variable name already met?
   if m$ <>"and" and m$ <>"or" and m$ <>"not(" and m$ <>")" and m$ <>"xor"_
    and not( instr( variableNames$, m$)) then
       variableNames$ =variableNames$ +m$ +" ": numVariables =numVariables +1
   end if

   i =i +1
   goto [parse]

 [analyse]
   for i =1 to numVariables
       ex$          =FindReplace$( expression$, word$( variableNames$, i, " "), chr$( 64 +i), 1)
       expression$  =ex$
   next i

   'print " "; numVariables; " variables, simplifying to "; expression$

   print ,;
   for j =1 to numVariables
       print word$( variableNames$, j, " "),
   next j
   print "Result"
   print

   for i =0 to ( 2^numVariables) -1
       print ,;
       A                         =i mod 2:          print A,
       if numVariables >1 then B =int( i /2) mod 2: print B,
       if numVariables >2 then C =int( i /4) mod 2: print C,
       if numVariables >3 then D =int( i /4) mod 2: print D,
       if numVariables >4 then E =int( i /4) mod 2: print E,
       if numVariables >5 then F =int( i /4) mod 2: print F,
       if numVariables >6 then G =int( i /4) mod 2: print G,
       '   .......................... etc

       'e =eval( expression$)
       if eval( expression$) <>0 then e$ ="1" else e$ ="0"
       print "==>  "; e$
   next i

   print

   goto [start]

   end

function FindReplace$( FindReplace$, find$, replace$, replaceAll) 

   if ( ( FindReplace$ <>"") and ( find$ <>"")) then
       fLen = len( find$)
       rLen = len( replace$)
       do
           fPos            = instr( FindReplace$, find$, fPos)
           if not( fPos) then exit function
           pre$            = left$( FindReplace$, fPos -1)
           post$           =  mid$( FindReplace$, fPos +fLen)
           FindReplace$    = pre$ +replace$ +post$
           fPos            = fPos +(rLen -fLen) +1
       loop while ( replaceAll)
   end if

end function </lang> 

        Too_High and Fuel_Out
              Too_High      Fuel_Out      Result

              0             0             ==>  0
              1             0             ==>  0
              0             1             ==>  0
              1             1             ==>  1

        Fat or Ugly and not( Rich )
              Fat           Ugly          Rich          Result

              0             0             0             ==>  0
              1             0             0             ==>  1
              0             1             0             ==>  1
              1             1             0             ==>  1
              0             0             1             ==>  0
              1             0             1             ==>  0
              0             1             1             ==>  0
              1             1             1             ==>  0

Mathematica

<lang Mathematica>VariableNames[data_] := Module[ {TokenRemoved}, 

TokenRemoved = StringSplit[data,{"~And~","~Or~","~Xor~","!","(",")"}];
Union[Select[Map[StringTrim,TokenRemoved] , Not[StringMatchQ[#,""]]&]]

]

TruthTable[BooleanEquation_] := Module[ {TestDataSet}, 

 TestDataSet = MapThread[Rule,{ToExpression@VariableNames[BooleanEquation],#}]&/@
    Tuples[{False,True}, Length[VariableNames[BooleanEquation]]];

 Join[List[Flatten[{VariableNames[BooleanEquation],BooleanEquation}]],
   Flatten[{#/.Rule[x_,y_] -> y,ReplaceAll[ToExpression[BooleanEquation],#]}]&/@TestDataSet]//Grid

]</lang>

Example usage: 

TruthTable["V ~Xor~ (B ~Xor~ (K ~Xor~ D ) )"]

B	D	K	V	V ~Xor~ (B ~Xor~ (K ~Xor~ D ) )
False	False	False	False	False
False	False	False	True	True
False	False	True	False	True
False	False	True	True	False
False	True	False	False	True
False	True	False	True	False
False	True	True	False	False
False	True	True	True	True
True	False	False	False	True
True	False	False	True	False
True	False	True	False	False
True	False	True	True	True
True	True	False	False	False
True	True	False	True	True
True	True	True	False	True
True	True	True	True	False

Maxima

<lang Maxima>/* Maxima already has the following logical operators 

         =, # (not equal), not, and, or

define some more and set 'binding power' (operator precedence) for them

  • /

infix("xor", 60)$ "xor"(A,B):= (A or B) and not(A and B)$

infix("=>", 59)$ "=>"(A,B):= not A or B$

/* Substitute variables `r' in `e' with values taken from list `l' where `e' is expression, `r' is a list of independent variables, `l' is a list of the values lsubst( '(A + B), ['A, 'B], [1, 2]); 1 + 2;

  • /

lsubst(e, r, l):= ev(e, maplist( lambda([x, y], x=y), r, l), 'simp)$

/* "Cartesian power" `n' of list `b'. Returns a list of lists of the form [<x_1>, ..., <x_n>], were <x_1>, .. <x_n> are elements of list `b' cartesian_power([true, false], 2); [[true, true], [true, false], [false, true], [false, false]]; cartesian_power([true, false], 3); [[true, true, true], [true, true, false], [true, false, true], [true, false, false], [false, true, true], [false, true, false], [false, false, true], [false, false, false]];

  • /

cartesian_power(b, n) := block( 

   [aux_lst: makelist(setify(b), n)],
   listify(apply(cartesian_product, aux_lst))
   )$

gen_table(expr):= block( 

 [var_lst: listofvars(expr), st_lst, res_lst, m],
 st_lst: cartesian_power([true, false], length(var_lst)),
 res_lst: create_list(lsubst(expr, var_lst, val_lst), val_lst, st_lst),
 m      : apply('matrix, cons(var_lst, st_lst)),
 addcol(m, cons(expr, res_lst))
 );

/* examples */ gen_table('(not A)); gen_table('(A xor B)); gen_table('(Jim and (Spock xor Bones) or Scotty)); gen_table('(A => (B and A))); gen_table('(V xor (B xor (K xor D ) )));</lang>

OUtput of the last example: <lang> 

           [   V      B      K      D    V xor (B xor (K xor D)) ]
           [                                                     ]
           [ true   true   true   true            false          ]
           [                                                     ]
           [ true   true   true   false           true           ]
           [                                                     ]
           [ true   true   false  true            true           ]
           [                                                     ]
           [ true   true   false  false           false          ]
           [                                                     ]
           [ true   false  true   true            true           ]
           [                                                     ]
           [ true   false  true   false           false          ]
           [                                                     ]
           [ true   false  false  true            false          ]
           [                                                     ]
           [ true   false  false  false           true           ]
           [                                                     ]
           [ false  true   true   true            true           ]
           [                                                     ]
           [ false  true   true   false           false          ]
           [                                                     ]
           [ false  true   false  true            false          ]
           [                                                     ]
           [ false  true   false  false           true           ]
           [                                                     ]
           [ false  false  true   true            false          ]
           [                                                     ]
           [ false  false  true   false           true           ]
           [                                                     ]
           [ false  false  false  true            true           ]
           [                                                     ]
           [ false  false  false  false           false          ]

</lang>

PARI/GP

Uses infix Boolean expressions with + for OR, * for AND, and the constants 0 and 1 for FALSE and TRUE.

It would be easy to modify the program to take + for XOR instead. <lang parigp>vars(P)={ my(v=List(),x); while(type(P)=="t_POL", x=variable(P); listput(v,x); P=subst(P,x,1) ); Vec(v) }; truthTable(P)={ my(var=vars(P),t,b); for(i=0,2^#var-1, t=eval(P); for(j=1,#var, b=bittest(i,j-1); t=subst(t,var[j],b); print1(b) ); print(!!t) ); }; truthTable("x+y") \\ OR truthTable("x*y") \\ AND</lang>

Output:
000
101
011
111

000
100
010
111

Perl

Note: can't process stuff like "X xor Y"; "xor" would be treated as a variable name here. <lang perl>#!/usr/bin/perl

sub truth_table { my $s = shift; my (%seen, @vars); for ($s =~ /([a-zA-Z_]\w*)/g) { $seen{$_} //= do { push @vars, $_; 1 }; }

print "\n", join("\t", @vars, $s), "\n", '-' x 40, "\n"; @vars = map("\$$_", @vars);

$s =~ s/([a-zA-Z_]\w*)/\$$1/g; $s = "print(".join(',"\t", ', map("($_?'T':'F')", @vars, $s)).",\"\\n\")"; $s = "for my $_ (0, 1) { $s }" for (reverse @vars); eval $s; }

truth_table 'A ^ A_1'; truth_table 'foo & bar | baz';

truth_table 'Jim & (Spock ^ Bones) | Scotty';</lang>

Output:


A       A_1     A ^ A_1
----------------------------------------
F       F       F
F       T       T
T       F       T
T       T       F

foo     bar     baz     foo & bar | baz
----------------------------------------
F       F       F       F
F       F       T       T
F       T       F       F
F       T       T       T
T       F       F       F
T       F       T       T
T       T       F       T
T       T       T       T

Jim     Spock   Bones   Scotty  Jim & (Spock ^ Bones) | Scotty
----------------------------------------
F       F       F       F       F
...<snip for space -- not like you're gonna verify it anyway>...
T       T       T       T       T

Perl 6

Works with: Rakudo version 2016.01

<lang perl6>use MONKEY-SEE-NO-EVAL;

sub truthtable ($x) { 

   my @n = $x.comb(/<ident>/);
   my &fun = EVAL "-> {('\\' «~« @n).join(',')} \{ [{ (|@n,"so $x").join(',') }] \}";

   say (|@n,$x).join("\t");
   .join("\t").say for map &fun, flat map { .fmt("\%0{+@n}b").comb».Int».so }, 0 ..^ 2**@n;
   say ;

}

truthtable 'A ^ B'; truthtable 'foo & bar | baz'; truthtable 'Jim & (Spock ^ Bones) | Scotty';</lang>

Output:
A	B	A ^ B
False	False	False
False	True	True
True	False	True
True	True	False

foo	bar	baz	foo & bar | baz
False	False	False	False
False	False	True	True
False	True	False	False
False	True	True	True
True	False	False	False
True	False	True	True
True	True	False	True
True	True	True	True

Jim	Spock	Bones	Scotty	Jim & (Spock ^ Bones) | Scotty
False	False	False	False	False
False	False	False	True	True
False	False	True	False	False
False	False	True	True	True
False	True	False	False	False
False	True	False	True	True
False	True	True	False	False
False	True	True	True	True
True	False	False	False	False
True	False	False	True	True
True	False	True	False	True
True	False	True	True	True
True	True	False	False	True
True	True	False	True	True
True	True	True	False	False
True	True	True	True	True

PicoLisp

<lang PicoLisp>(de truthTable (Expr) 

  (let Vars
     (uniq
        (make
           (setq Expr
              (recur (Expr)  # Convert infix to prefix notation
                 (cond
                    ((atom Expr) (link Expr))
                    ((== 'not (car Expr))
                       (list 'not (recurse (cadr Expr))) )
                    (T
                       (list
                          (cadr Expr)
                          (recurse (car Expr))
                          (recurse (caddr Expr)) ) ) ) ) ) ) )
     (for V Vars
        (prin (align -7 V)) )
     (prinl)
     (bind (mapcar cons Vars)
        (do (** 2 (length Vars))
           (for "V" Vars
              (space (if (print (val "V")) 6 4)) )
           (println (eval Expr))
           (find '(("V") (set "V" (not (val "V")))) Vars) ) ) ) )</lang>

Test:


<lang PicoLisp>: (truthTable (str "A and (B or C)")) A B C NIL NIL NIL NIL T NIL NIL NIL NIL T NIL NIL T T NIL T NIL NIL T NIL T NIL T T NIL T T NIL T T T T

(truthTable (str "not (Foo and (Bar or Mumble))"))

Foo Bar Mumble NIL NIL NIL T T NIL NIL T NIL T NIL T T T NIL NIL NIL NIL T T T NIL T NIL NIL T T T T T T NIL

(truthTable (str "(A xor B) and (B or C)"))

A B C NIL NIL NIL NIL T NIL NIL NIL NIL T NIL T T T NIL NIL NIL NIL T NIL T NIL T T NIL T T T T T T NIL

(truthTable (str "(A xor B) and ((not B) or C)"))

A B C NIL NIL NIL NIL T NIL NIL T NIL T NIL NIL T T NIL NIL NIL NIL T NIL T NIL T T NIL T T T T T T NIL</lang>

Python

This accepts correctly formatted Python boolean expressions. <lang python>from itertools import product

while True: 

   bexp = input('\nBoolean expression: ')
   bexp = bexp.strip()
   if not bexp:
       print("\nThank you")
       break
   code = compile(bexp, '<string>', 'eval')
   names = code.co_names
   print('\n' + ' '.join(names), ':', bexp)
   for values in product(range(2), repeat=len(names)):
       env = dict(zip(names, values))
       print(' '.join(str(v) for v in values), ':', eval(code, env))

</lang>

Sample output
Boolean expression: A ^ B

A B : A ^ B
0 0 : 0
0 1 : 1
1 0 : 1
1 1 : 0

Boolean expression: S | ( T ^ U )

S T U : S | ( T ^ U )
0 0 0 : 0
0 0 1 : 1
0 1 0 : 1
0 1 1 : 0
1 0 0 : 1
1 0 1 : 1
1 1 0 : 1
1 1 1 : 1

Boolean expression: A ^ (B ^ (C ^ D))

A B C D : A ^ (B ^ (C ^ D))
0 0 0 0 : 0
0 0 0 1 : 1
0 0 1 0 : 1
0 0 1 1 : 0
0 1 0 0 : 1
0 1 0 1 : 0
0 1 1 0 : 0
0 1 1 1 : 1
1 0 0 0 : 1
1 0 0 1 : 0
1 0 1 0 : 0
1 0 1 1 : 1
1 1 0 0 : 0
1 1 0 1 : 1
1 1 1 0 : 1
1 1 1 1 : 0

Boolean expression: 

Thank you

Racket

Since the requirement is to read an expression dynamically, eval is a natural choice. The following isn't trying to protect against bad inputs when doing that.

<lang Racket>

  1. lang racket

(define (collect-vars sexpr) 

 (sort
  (remove-duplicates
   (let loop ([x sexpr])
     (cond [(boolean? x) '()]
           [(symbol? x) (list x)]
           [(list? x) (append-map loop (cdr x))]
           [else (error 'truth-table "Bad expression: ~e" x)])))
  string<? #:key symbol->string))

(define ns (make-base-namespace))

(define (truth-table sexpr) 

 (define vars (collect-vars sexpr))
 (printf "~a => ~s\n" (string-join (map symbol->string vars)) sexpr)
 (for ([i (expt 2 (length vars))])
   (define vals
     (map (λ(x) (eq? #\1 x))
          (reverse (string->list (~r i #:min-width (length vars)
                                       #:pad-string "0"
                                       #:base 2)))))
   (printf "~a => ~a\n" (string-join (map (λ(b) (if b "T" "F")) vals))
           (if (eval `(let (,@(map list vars vals)) ,sexpr) ns) "T" "F"))))

(printf "Enter an expression: ") (truth-table (read)) </lang>

Sample run: 

Enter an expression: (and (or z x) (or y (not z)))
x y z => (and (or z x) (or y (not z)))
F F F => F
T F F => T
F T F => F
T T F => T
F F T => F
T F T => F
F T T => T
T T T => T

REXX

I had the thought that this program would just transform the boolean expression into what REXX approves of, and just step
through the 26 possible propositional constants (which makes a deeply nested DO construct, if nothing else, it looks pretty).
I later added support for all 16 boolean functions --- REXX natively supports three infix operators:

  • &   (and)
  • |   (or)
  • &&   (xor)

and one prefix operator:

  • ¬   (not or negation).

Some REXX intepreters also (or instead) support:

  • \   (backslash)
  • /   (forward slash)
  • ~   (tidle)
  • ^   (carot)

Also included is support for two boolean values: TRUE and FALSE which are part of boolean expressions. <lang rexx>/*REXX program displays a truth table the variables and an expression. */ /*Infix notation is supported with one character propositional constants*/ /*variables (propositional constants) allowed: A──►Z, a──►z except u. */ /*All propositional constants are case insensative (except lowercase v).*/

parse arg expression /*get expression from the C.L. */ if expression\= then do /*Got one? Then show user's stuff*/ 

                       call truthTable expression  /*show and tell T.T.*/
                       exit           /*we're all done with truth table*/
                       end

call truthTable "G ^ H ; XOR" /*txt after ; is shown in output.*/ call truthTable "i | j ; OR" call truthTable "G nxor H ; NXOR" call truthTable "k ! t ; NOR" call truthTable "p & q ; AND" call truthTable "e ¡ f ; NAND" call truthTable "S | (T ^ U )" call truthTable "(p=>q) v (q=>r)" call truthTable "A ^ (B ^ (C ^ D))" exit /*quit while we're ahead, by gum.*/ 

   /* ↓↓↓ no way, Jose. ↓↓↓ */        /*shows a 32,768 line truth table*/

call truthTable "A^(B^(C^(D^(E^(F^(G^(H^(I^(J^(L^(N^(N^(O^P)))))))))))))" exit /*stick a fork in it, we're done.*/

/*─────────────────────────────────────truthTable subroutine────────────*/ truthTable: procedure; parse arg $ ';' comm 1 $o; $o=strip($o) $=translate(strip($),'|',"v"); $u=$; upper $u $u=translate($u,'()()()',"[]{}«»"); $$.=0; PCs=; hdrPCs= @abc='abcdefghijklmnopqrstuvwxyz'; @abcU=@abc; upper @abcU

/* The boxed table below was constructed from an old IBM publication: 

   "PL/I Language Specifications"     ───  March 1968.

       ┌────────────────────────────────────────────────────────────┐
       │                  bool(bitsA, bitsB, BF)                    │
       ├────────────────────────────────────────────────────────────┤
       │ performs the boolean function  BF    ┌──────┬─────────┐    │
       │      on the   A   bitstring          │  BF  │ common  │    │
       │    with the   B   bitstring.         │ value│  name   │    │
       │                                      ├──────┼─────────┤    │
       │ BF  must be a  one to four bit       │ 0000 │boolfalse│    │
       │ value  (from  0000 ──► 1111),        │ 0001 │ and     │    │
       │ leading zeroes can be omitted.       │ 0010 │ NaIMPb  │    │
       │                                      │ 0011 │ boolB   │    │
       │ BF  may have multiple values (one    │ 0100 │ NbIMPa  │    │
       │ for each pair of bitstrings):        │ 0101 │ boolA   │    │
       │                                      │ 0110 │ xor     │    │
       │  ┌──────┬──────┬───────────────┐     │ 0111 │ or      │    │
       │  │ Abit │ Bbit │   returns     │     │ 1000 │ nor     │    │
       │  ├──────┼──────┼───────────────┤     │ 1001 │ nxor    │    │
       │  │   0  │   0  │ 1st bit in BF │     │ 1010 │ notB    │    │
       │  │   0  │   1  │ 2nd bit in BF │     │ 1011 │ bIMPa   │    │
       │  │   1  │   0  │ 3rd bit in BF │     │ 1100 │ notA    │    │
       │  │   1  │   1  │ 4th bit in BF │     │ 1101 │ aIMPb   │    │
       │  └──────┴──────┴───────────────┘     │ 1110 │ nand    │    │
       │                                      │ 1111 │booltrue │    │
       │                                   ┌──┴──────┴─────────┤    │
       │                                   │ A  0101           │    │
       │                                   │ B  0011           │    │
       │                                   └───────────────────┘    │
       └────────────────────────────────────────────────────────────┘  */

?='ff'x /*─────────infix operators───────*/ op.= /*a single quote (') wasn't */ 

                                      /*     implemented for negation. */

op.0 ='false boolFALSE' /*unconditionally FALSE */ op.1 ='& and *' /* AND, conjunction */ op.2 ='naimpb NaIMPb' /*not A implies B */ op.3 ='boolb boolB' /*B (value of) */ op.4 ='nbimpa NbIMPa' /*not B implies A */ op.5 ='boola boolA' /*A (value of) */ op.6 ='&& xor % ^' /* XOR, exclusive OR */ op.7 ='| or + v' /* OR, disjunction */ op.8 ='nor nor ! ↓' /* NOR, not OR, Pierce operator */ op.9 ='xnor xnor nxor' /*NXOR, not exclusive OR, not XOR*/ op.10='notb notB' /*not B (value of) */ op.11='bimpa bIMPa' /* B implies A */ op.12='nota notA' /*not A (value of) */ op.13='aimpb aIMPb' /* A implies B */ op.14='nand nand ¡ ↑' /*NAND, not AND, Sheffer operator*/ op.15='true boolTRUE' /*unconditionally TRUE */ 

                                      /*alphabetic names need changing.*/

op.16='\ NOT ~ ─ . ¬' /* NOT, negation */ op.17='> GT' /*conditional */ op.18='>= GE ─> => ──> ==>' "1a"x /*conditional */ op.19='< LT' /*conditional */ op.20='<= LE <─ <= <── <==' /*conditional */ op.21='\= NE ~= ─= .= ¬=' /*conditional */ op.22='= EQ EQUAL EQUALS =' "1b"x /*biconditional */ op.23='0 boolTRUE' /*TRUEness */ op.24='1 boolFALSE' /*FALSEness */ 

 do jj=0  while  op.jj\== | jj<16   /*change opers──►what REXX likes.*/
 new=word(op.jj,1)
   do kk=2  to words(op.jj)           /*handle each token separately.  */
   _=word(op.jj,kk);     upper _
   if wordpos(_,$u)==0   then iterate /*no such animal in this string. */
   if datatype(new,'m')  then new!=?  /*expresion needs transcribing.  */
                         else new!=new
   $u=changestr(_,$u,new!)            /*transcribe the function (maybe)*/
   if new!==?  then $u=changeFunc($u,?,new)   /*use internal bool name.*/
   end   /*kk*/
 end     /*jj*/

$u=translate($u, '()', "{}") /*finish cleaning up transcribing*/ 

     do jj=1  for length(@abcU)       /*see what variables are used.   */
     _=substr(@abcU,jj,1)             /*use available upercase alphabet*/
     if pos(_,$u)==0  then iterate    /*found one?   No, keep looking. */
     $$.jj=1                          /*found:  set upper bound for it.*/
     PCs=PCs _                        /*also, add to propositional cons*/
     hdrPCs=hdrPCS center(_,length('false'))       /*build a PC header.*/
     end   /*jj*/

$u=PCs '('$u")" /*separate PCs from expression. */ ptr='_────►_' /*a pointer for the truth table. */ hdrPCs=substr(hdrPCs,2) /*create a header for the PCs. */ say hdrPCs left(,length(ptr)-1) $o /*display PC header + expression.*/ say copies('───── ',words(PCs)) left(,length(ptr)-2) copies('─',length($o)) 

                                      /*Note: "true"s:  right─justified*/
do a=0  to $$.1
 do b=0  to $$.2
  do c=0  to $$.3
   do d=0  to $$.4
    do e=0  to $$.5
     do f=0  to $$.6
      do g=0  to $$.7
       do h=0  to $$.8
        do i=0  to $$.9
         do j=0  to $$.10
          do k=0  to $$.11
           do l=0  to $$.12
            do m=0  to $$.13
             do n=0  to $$.14
              do o=0  to $$.15
               do p=0  to $$.16
                do q=0  to $$.17
                 do r=0  to $$.18
                  do s=0  to $$.19
                   do t=0  to $$.20
                    do u=0  to $$.21
                     do !=0  to $$.22
                      do w=0  to $$.23
                       do x=0  to $$.24
                        do y=0  to $$.25
                         do z=0  to $$.26
                         interpret '_=' $u          /*evaluate truth T.*/
                         _=changestr(1,_,'_true')   /*convert 1──►_true*/
                         _=changestr(0,_,'false')   /*convert 0──►false*/
                         _=insert(ptr,_,wordindex(_,words(_))-1)  /*──►*/
                         say translate(_,,'_')      /*display truth tab*/
                         end   /*z*/
                        end    /*y*/
                       end     /*x*/
                      end      /*w*/
                     end       /*v*/
                    end        /*u*/
                   end         /*t*/
                  end          /*s*/
                 end           /*r*/
                end            /*q*/
               end             /*p*/
              end              /*o*/
             end               /*n*/
            end                /*m*/
           end                 /*l*/
          end                  /*k*/
         end                   /*j*/
        end                    /*i*/
       end                     /*h*/
      end                      /*g*/
     end                       /*f*/
    end                        /*e*/
   end                         /*d*/
  end                          /*c*/
 end                           /*b*/
end                            /*a*/

say; return /*─────────────────────────────────────SCAN subroutine──────────────────*/ scan: procedure; parse arg x,at; L=length(x); t=L; lp=0; apost=0; quote=0 if at<0 then do; t=1; x=translate(x,'()',")("); end 

     do j=abs(at)  to t  by sign(at);  _=substr(x,j,1);  __=substr(x,j,2)
     if quote           then do; if _\=='"'  then iterate
                             if __=='""'     then do; j=j+1; iterate; end
                             quote=0;  iterate
                             end
     if apost           then do; if _\=="'"  then iterate
                             if __==""     then do; j=j+1; iterate; end
                             apost=0;  iterate
                             end
     if _=='"'          then do; quote=1; iterate; end
     if _=="'"          then do; apost=1; iterate; end
     if _==' '          then iterate
     if _=='('          then do; lp=lp+1; iterate; end
     if lp\==0          then do; if _==')'  then lp=lp-1; iterate; end
     if datatype(_,'U') then return j-(at<0)
     if at<0            then return j+1
     end   /*j*/

return min(j,L) /*─────────────────────────────────────changeFunc subroutine────────────*/ changeFunc: procedure; parse arg z,fC,newF; funcPos=0 

          do forever
          funcPos=pos(fC,z,funcPos+1);    if funcPos==0  then return z
          origPos=funcPos
          z=changestr(fC,z,",'"newF"',")
          funcPos=funcPos+length(newF)+4
          where=scan(z, funcPos)   ;      z=insert(    '}',  z,  where)
          where=scan(z, 1-origPos) ;      z=insert('bool{',  z,  where)
          end   /*forever*/

/*─────────────────────────────────────BOOL subroutine──────────────────*/ bool: procedure; arg a,$,b 

        select

/*0*/ when $=='FALSE' then return 0 /*1*/ when $=='AND' then return a & b /*2*/ when $=='NAIMPB' then return \ (\a & \b) /*3*/ when $=='BOOLB' then return b /*4*/ when $=='NBIMPA' then return \ (\b & \a) /*5*/ when $=='BOOLA' then return a /*6*/ when $=='XOR' then return a && b /*7*/ when $=='OR' then return a | b /*8*/ when $=='NOR' then return \ (a | b) /*9*/ when $=='XNOR' then return \ (a && b) /*a*/ when $=='NOTB' then return \ b /*c*/ when $=='NOTA' then return \ a /*d*/ when $=='AIMPB' then return \ (a & \b) /*e*/ when $=='NAND' then return \ (a & b) /*f*/ when $=='TRUE' then return 1 

        otherwise             return -13   /*error.*/
        end   /*select*/</lang>

Some older REXXes don't have a   changestr   BIF, so one is included here ──► CHANGESTR.REX.

output when using the default input 

  G     H          G ^ H ; XOR
───── ─────        ───────────
false false  ────► false
false  true  ────►  true
 true false  ────►  true
 true  true  ────► false

  I     J          i | j ; OR
───── ─────        ──────────
false false  ────► false
false  true  ────►  true
 true false  ────►  true
 true  true  ────►  true

  G     H          G nxor H ; NXOR
───── ─────        ───────────────
false false  ────►  true
false  true  ────► false
 true false  ────► false
 true  true  ────►  true

  K     T          k ! t ; NOR
───── ─────        ───────────
false false  ────►  true
false  true  ────► false
 true false  ────► false
 true  true  ────► false

  P     Q          p & q ; AND
───── ─────        ───────────
false false  ────► false
false  true  ────► false
 true false  ────► false
 true  true  ────►  true

  E     F          e ¡ f ; NAND
───── ─────        ────────────
false false  ────►  true
false  true  ────►  true
 true false  ────►  true
 true  true  ────► false

  S     T     U          S | (T ^ U )
───── ───── ─────        ────────────
false false false  ────► false
false false  true  ────►  true
false  true false  ────►  true
false  true  true  ────► false
 true false false  ────►  true
 true false  true  ────►  true
 true  true false  ────►  true
 true  true  true  ────►  true

  P     Q     R          (p=>q) v (q=>r)
───── ───── ─────        ───────────────
false false false  ────►  true
false false  true  ────►  true
false  true false  ────►  true
false  true  true  ────►  true
 true false false  ────►  true
 true false  true  ────►  true
 true  true false  ────►  true
 true  true  true  ────►  true

  A     B     C     D          A ^ (B ^ (C ^ D))
───── ───── ───── ─────        ─────────────────
false false false false  ────► false
false false false  true  ────►  true
false false  true false  ────►  true
false false  true  true  ────► false
false  true false false  ────►  true
false  true false  true  ────► false
false  true  true false  ────► false
false  true  true  true  ────►  true
 true false false false  ────►  true
 true false false  true  ────► false
 true false  true false  ────► false
 true false  true  true  ────►  true
 true  true false false  ────► false
 true  true false  true  ────►  true
 true  true  true false  ────►  true
 true  true  true  true  ────► false

Ruby

Uses eval, so blindly trusts the user's input. The core true and false objects understand the methods & (and), | (or), ! (not) and ^ (xor) -- [1] <lang ruby>loop do 

 print "\ninput a boolean expression (e.g. 'a & b'): "
 expr = gets.strip.downcase 
 break if expr.empty?

 vars = expr.scan(/\p{Alpha}+/)
 if vars.empty?
   puts "no variables detected in your boolean expression"
   next
 end

 vars.each {|v| print "#{v}\t"}
 puts "| #{expr}"

 prefix = []
 suffix = []
 vars.each do |v|
   prefix << "[false, true].each do |#{v}|"
   suffix << "end"
 end

 body = vars.inject("puts ") {|str, v| str + "#{v}.to_s + '\t' + "} 
 body += '"| " + eval(expr).to_s'

 eval (prefix + [body] + suffix).join("\n")

end</lang>

Example 

input a boolean expression (e.g. 'a & b'): !a
a       | !a
false   | true
true    | false

input a boolean expression (e.g. 'a & b'): a|!b
a       b       | a|!b
false   false   | true
false   true    | false
true    false   | true
true    true    | true

input a boolean expression (e.g. 'a & b'): ((a^b)^c)^d
a       b       c       d       | ((a^b)^c)^d
false   false   false   false   | false
false   false   false   true    | true
false   false   true    false   | true
false   false   true    true    | false
false   true    false   false   | true
false   true    false   true    | false
false   true    true    false   | false
false   true    true    true    | true
true    false   false   false   | true
true    false   false   true    | false
true    false   true    false   | false
true    false   true    true    | true
true    true    false   false   | false
true    true    false   true    | true
true    true    true    false   | true
true    true    true    true    | false

Sidef

Translation of: Ruby

A simple solution which accepts arbitrary user-input: <lang ruby>loop { 

 var expr = Sys.readln("\nBoolean expression (e.g. 'a & b'): ").strip.lc
 break if expr.is_empty;

 var vars = expr.scan(/alpha:+/)
 if (vars.is_empty) {
   say "no variables detected in your boolean expression"
   next
 }

 var prefix = [];
 var suffix = [];

 vars.each { |v|
   print "#{v}\t"
   prefix << "[false, true].each { |#{v}|"
   suffix << "}"
 }
 say "| #{expr}"

 var body = ("say (" + vars.map{|v| v+",'\t'," }.join + " '| ', #{expr})")
 eval(prefix + [body] + suffix -> join("\n"))

}</lang>

Output:
Boolean expression (e.g. 'a & b'): (a & b) | c
a	b	c	| (a & b) | c
false	false	false	| false
false	false	true	| true
false	true	false	| false
false	true	true	| true
true	false	false	| false
true	false	true	| true
true	true	false	| true
true	true	true	| true

Tcl

<lang tcl>package require Tcl 8.5

puts -nonewline "Enter a boolean expression: " flush stdout set exp [gets stdin]

  1. Generate the nested loops as the body of a lambda term.

set vars [lsort -unique [regexp -inline -all {\$\w+} $exp]] set cmd [list format [string repeat "%s\t" [llength $vars]]%s] append cmd " {*}\[[list subst $vars]\] \[[list expr $exp]\]" set cmd "puts \[$cmd\]" foreach v [lreverse $vars] { 

   set cmd [list foreach [string range $v 1 end] {0 1} $cmd]

}

puts [join $vars \t]\tResult apply [list {} $cmd]</lang> Sample run: 

Enter a boolean expression: ($a&&$b)||$c
$a	$b	$c	Result
0	0	0	0
0	0	1	1
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1
Retrieved from "https://rosettacode.org/wiki/Truth_table?oldid=204789"