Richard Suchenwirth 2002-12-04 - "NAND is not AND." By popular demand, here's some codelets to demonstrate how all Boolean operations can be expressed in terms of the single NAND operator, which returns true if not both his two inputs are true (NOR would have done equally well). We have Boolean operators in expr, so here goes:}
proc nand {A B} {expr {!($A && $B)}}# The only unary operator NOT can be written in terms of nand:
proc not {A} {nand $A $A}
proc and {A B} {not [nand $A $B]}
proc or {A B} {nand [not $A] [not $B]}
proc nor {A B} {not [or $A $B]}
proc eq {A B} {or [and $A $B] [nor $A $B]}
proc ne {A B} {nor [and $A $B] [nor $A $B]}if 0 {Here's some testing tools - to see whether an implementation is correct, look at its truth table, here done as the four results for A,B combinations 0,0 0,1 1,0 1,1 - side note how easily procs can be passed in:}
proc truthtable f {
set res {}
foreach A {0 1} {
foreach B {0 1} {
lappend res [$f $A $B]
}
}
set res
}if 0 {
% truthtable and 0 0 0 1 % truthtable nand 1 1 1 0 % truthtable or 0 1 1 1 % truthtable nor 1 0 0 0 % truthtable eq 1 0 0 1
To see how efficient the implementation is (in terms of NAND units used), try this which relies on the fact that Boolean functions contain no lowercase letters apart from the operator names:}
proc nandcount f {
regsub -all {[^a-z]} [info body $f] " " list
set nums [string map {nand 1 not 1 and 2 nor 4 or 3 eq 6} $list]
expr [join $nums +]
}See also: A little proving engine - Parsing Polish notation