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: Parsing formulas and then evaluating them 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("A ^ B", xor) tt("S | ( T ^ U )", stu) tt("A ^ (B ^ (C ^ D))", abcd)
}
func tt(label string, f interface{}) {
fmt.Printf("\n%s:\n", 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[i] = reflect.ValueOf(ba) lBits >>= 1 } fmt.Println(s, v.Call(a)[0].Bool()) }
}</lang> Output:
A ^ B: false false false false true true true false true true true false S | ( T ^ U ): false false false false false false true true false true false true false true true true true false false true true false true true true true false false true true true true 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:
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] 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