[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} # .. and everything else can be built from them too: 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 } # Test: catch {console show} puts "nand: [truthtable nand]" 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 +] } ---- A very different idea, having nothing to do with NAND as elementary function, but I like it because it "implements" Boolean functions very intuitively, by just giving their truth table for look-up at runtime: proc booleanFunction {truthtable a b} {lindex $truthtable [expr {!!$a+!!$a+!!$b}]} interp alias {} and {} booleanFunction {0 0 0 1} interp alias {} or {} booleanFunction {0 1 1 1} interp alias {} nand {} booleanFunction {1 1 1 0} !! is a cute little Booleanizer (thanks [KPV] on [Toggling a Boolean variable]!) ---- [TV] Always good to have a page on the thing that can be proven to be a basic building block of pretty much the whole universe of computers! For digital designers with some historical perspective (and sense), NANDs are pieces of electronics that have in minimal form 3 pins each, and are represented by 'iron' symbols, where the output has an extra circle, which indicates it is not an AND but a NAND (with inverted output). Inverters are more fun, because one cannot construct something inverting with gates that do not invert. Otherwise, mathematically one can construct ANY logical function from ANY logical building blocks that has two inputs and inverts and does something like an ''and'' or ''or'' function. From Texas Instruments datasheet: [http://82.168.209.239/Wiki/nand7400.jpg] For a course proof on how any logical function can be constructed, also from NANDs, see [Boolean Logic] ---- [Laws of Form] shows a model of Boolean arithmetics with two operators, one of them being the empty string "", however... ---- See also: [A little proving engine] - [Parsing Polish notation] ---- A Little Bit O' History : http://planetmath.org/encyclopedia/Ampheck.html ---- [Arts and Crafts of Tcl-Tk Programming] ---- !!!!!! %|[Category Concept]|% !!!!!!