Truth table
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
- 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). - 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.
- Either reverse-polish or infix notation expressions are allowed.
- Cf.
- Ref.
- Wolfram mathworld entry on truth tables.
- Some examples from Google.
Go
Variance from statement of task: Runtime evaluation or code generation is not directly supported in Go. The function tt here does however accept functions with any number of arguments and produce the corresponding truth table. <lang go>package main
import (
"fmt" "reflect"
)
func xor(a, b bool) bool {
return a != b
}
func stu(s, t, u bool) bool {
return s || xor(t, u)
}
func abcd(a, b, c, d bool) bool {
return xor(a, xor(b, xor(c, d)))
}
func main() {
tt(xor, "A B A ^ B") tt(stu, "S T U S | ( T ^ U )") tt(abcd, "A B C D A ^ (B ^ (C ^ D))")
}
func tt(f interface{}, label string) {
fmt.Println()
fmt.Println(label)
tv := []bool{false, true}
v := reflect.ValueOf(f)
n := reflect.TypeOf(f).NumIn()
a := make([]reflect.Value, n)
lines := 1 << uint(n)
for l := 0; l < lines; l++ {
s := " "
lBits := l
for i := range a {
ba := tv[lBits & 1]
s = fmt.Sprintf("%-5t %s", ba, s)
a[n-1-i] = reflect.ValueOf(ba)
lBits >>= 1
}
fmt.Println(s, v.Call(a)[0].Bool())
}
}</lang> Output:
A B A ^ B false false false 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 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
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 the 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
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:
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 )'"
[start] input " "; expression$ if expression$ ="" then [start]
'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
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
Perl 6
<lang perl6>sub MAIN ($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, map { .fmt("\%0{+@n}b").comb».so }, 0 ..^ 2**@n;
}</lang>
- Output:
$ truthtable 'A ^ B' A B A ^ B False False False False True True True False True True True False $ truthtable 'foo & bar | baz' 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 $ truthtable 'Jim & (Spock ^ Bones) | Scotty' 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
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
Tcl
<lang tcl>package require Tcl 8.5
puts -nonewline "Enter a boolean expression: " flush stdout set exp [gets stdin]
- 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