Version 6 of NAND

Updated 2003-04-08 14:50:46

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
 }

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, but I like it because it "implements" Boolean functions very intuitively, by just giving their truth table:

 proc booleanFunction {truthtable a b} {lindex $truthtable [expr {$a*2+$b}]}
 interp alias {} and {} booleanFunction {0 0 0 1}
 interp alias {} or {} booleanFunction {0 1 1 1}

TV Always good to have a page on the thing which can be proven to be a basic building block of pretty much the whole universe of computers! For digital designers with some historic perspective (and sense), NANDs are pieces of electronics which have in minimal form 3 pins each, and are represented by 'iron' symbols, where the ouput 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 which do not invert. Otherwise, mathematically one can construct ANY logical function from ANY logical building blocks which has two inputs and inverts and does something like a and or or function.

From Texas Instruments datasheet: http://195.241.128.75/Wiki/nand7400.jpg


See also: A little proving engine - Parsing Polish notation


Category Concept | Arts and crafts of Tcl-Tk programming