Truth table: Difference between revisions
m (→{{header|REXX}}: reformated a few clauses. -- ~~~~) |
m (→{{header|REXX}}: changed/added comments, added DO-END comment labels, added w hitespace, changes some output glyphs. -- ~~~~) |
||
Line 542: | Line 542: | ||
<br>through the 26 possible propositional constants (which makes a deeply nested DO construct, if nothing else, it looks pretty). |
<br>through the 26 possible propositional constants (which makes a deeply nested DO construct, if nothing else, it looks pretty). |
||
<br>I later added support for all 16 boolean functions --- REXX natively supports three infix operators: |
<br>I later added support for all 16 boolean functions --- REXX natively supports three infix operators: |
||
* & (and) |
* '''&''' (and) |
||
* | (or) |
* '''|''' (or) |
||
* && (xor) |
* '''&&''' (xor) |
||
and one prefix operator: |
and one prefix operator: |
||
* ¬ (not or negation). |
* '''¬''' (not or negation). |
||
Some REXX intepreters also (or instead) support: |
|||
* backslash (\) |
|||
* forward slash (/) |
|||
* tidle (~) |
|||
* carot (^) |
|||
Also included is support for two boolean values: <tt>TRUE</tt> and <tt>FALSE</tt> which are part of boolean expressions. |
Also included is support for two boolean values: <tt>TRUE</tt> and <tt>FALSE</tt> which are part of boolean expressions. |
||
<br><br>Some older REXXes don't have a '''changestr''' bif, so one is included here. |
<br><br>Some older REXXes don't have a '''changestr''' bif, so one is included here. |
||
<lang rexx>/*REXX program displays a truth table the variables and an expression. */ |
<lang rexx>/*REXX program displays a truth table the variables and an expression. */ |
||
/*Infix notation is supported with one character propositional constants*/ |
/*Infix notation is supported with one character propositional constants*/ |
||
/*variables (propositional constants) allowed: |
/*variables (propositional constants) allowed: A──►Z, a──►z except u. */ |
||
/*All propositional constants are case insensative (except lowercase v).*/ |
/*All propositional constants are case insensative (except lowercase v).*/ |
||
parse arg expression /*get expression from command line.*/ |
parse arg expression /*get expression from command line.*/ |
||
if expression\='' then do /*got one? Then show user's stuff.*/ |
if expression\='' then do /*got one? Then show user's stuff.*/ |
||
call truthTable expression /*show and tell time*/ |
call truthTable expression /*show and tell time*/ |
||
exit |
exit /*we're all done with truth table. */ |
||
end |
end |
||
call truthTable "G ^ H ; XOR" /* |
call truthTable "G ^ H ; XOR" /*txt after ; is shown in output*/ |
||
call truthTable "i | j ; OR" |
call truthTable "i | j ; OR" |
||
call truthTable "G nxor H ; NXOR" |
call truthTable "G nxor H ; NXOR" |
||
Line 569: | Line 574: | ||
call truthTable "(p=>q) v (q=>r)" |
call truthTable "(p=>q) v (q=>r)" |
||
call truthTable "A ^ (B ^ (C ^ D))" |
call truthTable "A ^ (B ^ (C ^ D))" |
||
exit /*quit while we're ahead*/ |
|||
exit /*quit while we're ahead, by gum.*/ |
|||
/*shows a 32,768 line truth table*/ |
|||
call truthTable "A^(B^(C^(D^(E^(F^(G^(H^(I^(J^(L^(N^(N^(O^P)))))))))))))" |
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.*/ |
|||
exit |
|||
/*─────────────────────────────────────truthTable subroutine────────────*/ |
/*─────────────────────────────────────truthTable subroutine────────────*/ |
||
truthTable: procedure; parse arg $ ';' comm 1 $o; $o=strip($o) |
truthTable: procedure; parse arg $ ';' comm 1 $o; $o=strip($o) |
||
$=translate(strip($),'|',"v"); $u=$; upper $u |
$=translate(strip($),'|',"v"); $u=$; upper $u |
||
$u=translate($u,'()()()',"[]{}«»"); $$.=0; PCs=; hdrPCs= |
$u=translate($u,'()()()',"[]{}«»"); $$.=0; PCs=; hdrPCs= |
||
@abc='abcdefghijklmnopqrstuvwxyz'; @abcU=@abc; upper @abcU |
@abc='abcdefghijklmnopqrstuvwxyz'; @abcU=@abc; upper @abcU |
||
/* The boxed table below was constructed from an old IBM publication: |
/* The boxed table below was constructed from an old IBM publication: |
||
Line 589: | Line 596: | ||
│ ├──────┼─────────┤ │ |
│ ├──────┼─────────┤ │ |
||
│ BF must be a one to four bit │ 0000 │boolfalse│ │ |
│ BF must be a one to four bit │ 0000 │boolfalse│ │ |
||
│ value (from 0000 |
│ value (from 0000 ──► 1111), │ 0001 │ and │ │ |
||
│ leading zeroes can be omitted. │ 0010 │ NaIMPb │ │ |
│ leading zeroes can be omitted. │ 0010 │ NaIMPb │ │ |
||
│ │ 0011 │ boolB │ │ |
│ │ 0011 │ boolB │ │ |
||
Line 640: | Line 647: | ||
op.24='1 boolFALSE' /*falseness */ |
op.24='1 boolFALSE' /*falseness */ |
||
do jj=0 while op.jj\=='' | jj<16 |
do jj=0 while op.jj\=='' | jj<16 /*change opers──►what REXX likes.*/ |
||
new=word(op.jj,1) |
new=word(op.jj,1) |
||
do kk=2 to words(op.jj) |
do kk=2 to words(op.jj) /*handle each token separately. */ |
||
_=word(op.jj,kk); upper _ |
_=word(op.jj,kk); upper _ |
||
if wordpos(_,$u)==0 |
if wordpos(_,$u)==0 then iterate /*no such animal in this string. */ |
||
if datatype(new,'m') then new!=? |
if datatype(new,'m') then new!=? /*expresion needs transcribing. */ |
||
else new!=new |
else new!=new |
||
$u=changestr(_,$u,new!) /*transcribe the function (maybe)*/ |
$u=changestr(_,$u,new!) /*transcribe the function (maybe)*/ |
||
if new!==? then $u=changeFunc($u,?,new) |
if new!==? then $u=changeFunc($u,?,new) /*use internal bool name.*/ |
||
end /*kk*/ |
end /*kk*/ |
||
end /*jj*/ |
end /*jj*/ |
||
$u=translate($u,'()',"{}") /*finish cleaning up transcribing*/ |
$u=translate($u,'()',"{}") /*finish cleaning up transcribing*/ |
||
do |
do jj=1 for length(@abcU) /*see what variables are used. */ |
||
_=substr(@abcU, |
_=substr(@abcU,jj,1) /*use available upercase alphabet*/ |
||
if pos(_,$u)==0 then iterate /*found one? No, keep looking. */ |
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*/ |
PCs=PCs _ /*also, add to propositional cons*/ |
||
hdrPCs=hdrPCS center(_,length('false')) /*build a PC header.*/ |
hdrPCs=hdrPCS center(_,length('false')) /*build a PC header.*/ |
||
end |
end |
||
$u=PCs '('$u")" /* |
$u=PCs '('$u")" /*separate PCs from expression. */ |
||
ptr=' |
ptr='_────►+_' /*a pointer for the truth table. */ |
||
hdrPCs=substr(hdrPCs,2) /*create a header for the PCs. */ |
hdrPCs=substr(hdrPCs,2) /*create a header for the PCs. */ |
||
say hdrPCs left('',length(ptr)-1) $o /*display PC header + expression.*/ |
say hdrPCs left('',length(ptr)-1) $o /*display PC header + expression.*/ |
||
Line 693: | Line 700: | ||
do z=0 to $$.26 |
do z=0 to $$.26 |
||
interpret '_=' $u /*evaluate truth T.*/ |
interpret '_=' $u /*evaluate truth T.*/ |
||
_=changestr(1,_,'_true') /*convert |
_=changestr(1,_,'_true') /*convert 1──►_true*/ |
||
_=changestr(0,_,'false') /*convert |
_=changestr(0,_,'false') /*convert 0──►false*/ |
||
_=insert(ptr,_,wordindex(_,words(_))-1) /* |
_=insert(ptr,_,wordindex(_,words(_))-1) /*──►*/ |
||
say translate(_,,'_') /*display truth tab*/ |
say translate(_,,'_') /*display truth tab*/ |
||
end |
end |
||
Line 726: | Line 733: | ||
return |
return |
||
/*─────────────────────────────────────SCAN subroutine──────────────────*/ |
/*─────────────────────────────────────SCAN subroutine──────────────────*/ |
||
scan: procedure; parse arg x,at; L=length(x); t=L; lp=0; apost=0; quote=0 |
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 |
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) |
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 quote then do; if _\=='"' then iterate |
||
if __=='""' then do; j=j+1; iterate; end |
if __=='""' then do; j=j+1; iterate; end |
||
quote=0; iterate |
quote=0; iterate |
||
end |
end |
||
if apost then do; if _\=="'" then iterate |
if apost then do; if _\=="'" then iterate |
||
if __=="''" then do; j=j+1; iterate; end |
if __=="''" then do; j=j+1; iterate; end |
||
apost=0; iterate |
apost=0; iterate |
||
end |
end |
||
if _=='"' then do; quote=1; iterate; end |
if _=='"' then do; quote=1; iterate; end |
||
if _=="'" then do; apost=1; iterate; end |
if _=="'" then do; apost=1; iterate; end |
||
if _==' ' then iterate |
if _==' ' then iterate |
||
if _=='(' then do; lp=lp+1; iterate; end |
if _=='(' then do; lp=lp+1; iterate; end |
||
if lp\==0 then do; if _==')' then 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 datatype(_,'U') then return j-(at<0) |
||
if at<0 then return j+1 |
if at<0 then return j+1 |
||
end |
end |
||
return min(j,L) |
return min(j,L) |
||
/*─────────────────────────────────────changeFunc subroutine────────────*/ |
/*─────────────────────────────────────changeFunc subroutine────────────*/ |
||
changeFunc: procedure; parse arg z,fC,newF |
changeFunc: procedure; parse arg z,fC,newF |
||
funcPos=0 |
|||
do forever |
do forever |
||
funcPos=pos(fC,z,funcPos+1) |
funcPos=pos(fC,z,funcPos+1); if funcPos==0 then return z |
||
origPos=funcPos |
origPos=funcPos |
||
if funcPos==0 then leave |
|||
z=changestr(fC,z,",'"newF"',") |
z=changestr(fC,z,",'"newF"',") |
||
funcPos=funcPos+length(newF)+4 |
funcPos=funcPos+length(newF)+4 |
||
where=scan(z,funcPos) |
where=scan(z, funcPos) ; z=insert( '}', z, where) |
||
z=insert(' |
where=scan(z, 1-origPos) ; z=insert('bool{', z, where) |
||
end |
|||
z=insert('bool{',z,where) |
|||
end /*forever*/ |
|||
return z |
|||
/*───────────────────────────CHANGESTR subroutine───────────────────────*/ |
|||
changestr: procedure; parse arg o,h,n; r=; w=length(o); if w==0 then return n||h |
|||
do forever; parse var h y (o) _ +(w) h; if _=='' then return r||y; r=r||y||n; end |
|||
/*─────────────────────────────────────BOOL subroutine──────────────────*/ |
/*─────────────────────────────────────BOOL subroutine──────────────────*/ |
||
bool: procedure; |
bool: procedure; arg a,$,b |
||
select |
select |
||
/*0*/ when $=='FALSE' then return 0 |
/*0*/ when $=='FALSE' then return 0 |
||
/*1*/ when $=='AND' then return a&b |
/*1*/ when $=='AND' then return a & b |
||
/*2*/ when $=='NAIMPB' then return \(\a&\b) |
/*2*/ when $=='NAIMPB' then return \ (\a & \b) |
||
/*3*/ when $=='BOOLB' then return b |
/*3*/ when $=='BOOLB' then return b |
||
/*4*/ when $=='NBIMPA' then return \(\b&\a) |
/*4*/ when $=='NBIMPA' then return \ (\b & \a) |
||
/*5*/ when $=='BOOLA' then return a |
/*5*/ when $=='BOOLA' then return a |
||
/*6*/ when $=='XOR' then return a&&b |
/*6*/ when $=='XOR' then return a && b |
||
/*7*/ when $=='OR' then return a|b |
/*7*/ when $=='OR' then return a | b |
||
/*8*/ when $=='NOR' then return \(a|b) |
/*8*/ when $=='NOR' then return \ (a | b) |
||
/*9*/ when $=='XNOR' then return \(a&& b) |
/*9*/ when $=='XNOR' then return \ (a && b) |
||
/*a*/ when $=='NOTB' then return \b |
/*a*/ when $=='NOTB' then return \ b |
||
/*c*/ when $=='NOTA' then return \a |
/*c*/ when $=='NOTA' then return \ a |
||
/*d*/ when $=='AIMPB' then return \(a&\b) |
/*d*/ when $=='AIMPB' then return \ (a & \b) |
||
/*e*/ when $=='NAND' then return \(a&b) |
/*e*/ when $=='NAND' then return \ (a & b) |
||
/*f*/ when $=='TRUE' then return 1 |
/*f*/ when $=='TRUE' then return 1 |
||
otherwise |
otherwise return -13 /*error.*/ |
||
end /*select*/</lang> |
|||
'''output''' when using the default input |
'''output''' when using the default input |
||
<pre style="height:50ex;overflow:scroll"> |
<pre style="height:50ex;overflow:scroll"> |
||
G H G ^ H ; XOR |
G H G ^ H ; XOR |
||
───── ───── ─────────── |
───── ───── ─────────── |
||
false false |
false false ────► false |
||
false true |
false true ────► true |
||
true false |
true false ────► true |
||
true true |
true true ────► false |
||
I J i | j ; OR |
I J i | j ; OR |
||
───── ───── ────────── |
───── ───── ────────── |
||
false false |
false false ────► false |
||
false true |
false true ────► true |
||
true false |
true false ────► true |
||
true true |
true true ────► true |
||
G H G nxor H ; NXOR |
G H G nxor H ; NXOR |
||
───── ───── ─────────────── |
───── ───── ─────────────── |
||
false false |
false false ────► true |
||
false true |
false true ────► false |
||
true false |
true false ────► false |
||
true true |
true true ────► true |
||
K T k ! t ; NOR |
K T k ! t ; NOR |
||
───── ───── ─────────── |
───── ───── ─────────── |
||
false false |
false false ────► true |
||
false true |
false true ────► false |
||
true false |
true false ────► false |
||
true true |
true true ────► false |
||
P Q p & q ; AND |
P Q p & q ; AND |
||
───── ───── ─────────── |
───── ───── ─────────── |
||
false false |
false false ────► false |
||
false true |
false true ────► false |
||
true false |
true false ────► false |
||
true true |
true true ────► true |
||
E F e ¡ f ; NAND |
E F e ¡ f ; NAND |
||
───── ───── ──────────── |
───── ───── ──────────── |
||
false false |
false false ────► true |
||
false true |
false true ────► true |
||
true false |
true false ────► true |
||
true true |
true true ────► false |
||
S T U S | (T ^ U ) |
S T U S | (T ^ U ) |
||
───── ───── ───── ──────────── |
───── ───── ───── ──────────── |
||
false false false |
false false false ────► false |
||
false false true |
false false true ────► true |
||
false true false |
false true false ────► true |
||
false true true |
false true true ────► false |
||
true false false |
true false false ────► true |
||
true false true |
true false true ────► true |
||
true true false |
true true false ────► true |
||
true true true |
true true true ────► true |
||
P Q R (p=>q) v (q=>r) |
P Q R (p=>q) v (q=>r) |
||
───── ───── ───── ─────────────── |
───── ───── ───── ─────────────── |
||
false false false |
false false false ────► true |
||
false false true |
false false true ────► true |
||
false true false |
false true false ────► true |
||
false true true |
false true true ────► true |
||
true false false |
true false false ────► true |
||
true false true |
true false true ────► true |
||
true true false |
true true false ────► true |
||
true true true |
true true true ────► true |
||
A B C D A ^ (B ^ (C ^ D)) |
A B C D A ^ (B ^ (C ^ D)) |
||
───── ───── ───── ───── ───────────────── |
───── ───── ───── ───── ───────────────── |
||
false false false false |
false false false false ────► false |
||
false false false true |
false false false true ────► true |
||
false false true false |
false false true false ────► true |
||
false false true true |
false false true true ────► false |
||
false true false false |
false true false false ────► true |
||
false true false true |
false true false true ────► false |
||
false true true false |
false true true false ────► false |
||
false true true true |
false true true true ────► true |
||
true false false false |
true false false false ────► true |
||
true false false true |
true false false true ────► false |
||
true false true false |
true false true false ────► false |
||
true false true true |
true false true true ────► true |
||
true true false false |
true true false false ────► false |
||
true true false true |
true true false true ────► true |
||
true true true false |
true true true false ────► true |
||
true true true true |
true true true true ────► false |
||
</pre> |
</pre> |
||
Revision as of 23:15, 26 November 2012
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
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
<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
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.
Some older REXXes don't have a changestr bif, so one is included here.
<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 command line.*/ if expression\= then do /*got one? Then show user's stuff.*/
call truthTable expression /*show and tell time*/ 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.*/
/*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 (') wan'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
$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 end end end end end end end end end end end end end end end end end end end end end end end end end
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
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
/*─────────────────────────────────────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>
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
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