Version 9 of Boolean Logic

page by Theo Verelst (TV apr 16 03) Boolean logic is the formal mathematical foundation of the most fundamental computer circuits, as well as a major component in the design of complex digital circuits, and as such is important for every serious programmer to at least have some knowledge about, unless one wants to be bereft of fundamental, relevant and fun concepts, and not be aware of the reason for the efficiency of certain and inefficiency of other programming constructs.

In tcl, it is fun to interactively play around with these fundamantals, to begin with in basic form, later I'll do a page where these principles are applied and shown graphically.

As almost everybody (here) will know, booleans are two valued numbers, meaning they are 1 or 0, or in electronical circuits which carry them, a high or a low signal, for instance 5 Volts or 0 Volts. Like with decimal numbers, we can combine 1's and 0's in a list, like decimal numbers, and define operations on them. Parallel operations as with decimal numbers can be defined, which can like in the decimal case be carried out using distributive and associative and substituation operations and factoring.

The basic operations are invert, and and or, which can be defined in tcl as:

 proc inv a {return [expr !$a]}
 proc and {a b} {return [expr $a && $b]}
 proc or {a b} {return [expr $a || $b]}

We can list the domain and corresponding logical functions values easily in short lists:

 # truth table format:
 #  inputs   --> output
 # msb  lsb
    for {set i 0} {$i < 2} {incr i} {puts "$i [inv $i]"}
 0 1
 1 0

    for {set j 0} {$j < 2} {inc j} { for {set i 0} {$i < 2} {incr i} {puts "$j$i [and $j $i]"}}
 00 0
 01 0
 10 0
 11 1

    for {set j 0} {$j < 2} {inc j} { for {set i 0} {$i < 2} {incr i} {puts "$j$i [or $j $i]"}}
 00 0
 01 1
 10 1
 11 1

We can define a nand as the combination of an inverter and a AND circuit as a nand:

 proc nand {a b} {return [inv [and $a $b]]}

With as truth table:

    for {set j 0} {$j < 2} {inc j} { for {set i 0} {$i < 2} {incr i} {puts "$j$i [nand $j $i]"}}
 00 1
 01 1
 10 1
 11 0

Combining more than one bit in a conceptual 'word' we can distinguish the weight of the bits, and like with decimal numbers place the highest valued bit left, and the one valued bit at the right. Because every bit contributes a doubling of the set of possible numbers the word can take on, we can say the corresponding weight of each bit is pow(2,n), where n is the bit number starting from zero at the right. The highest number thus formed 11111...1 is pow(2,n)-1, taking the lowest to have corresponding decimal value zero, and represented as 0000...0.

A seperate page of course could be about the conversions possible between numbers in various representations, here we take it that all we need to know is that numbers exist, and that pow(2,n) distinquishable numbers exist for a word of n bits.

Now an important logical circuit and theory concept is the combination of logical circuits, and possibilities to select and combine. We've seen the nand function as combination of and and invert, but we can also combine two variable / input functions. Before succoming to wieldy and large ranges of possibilities which would come from all possible combinations of logical functions, we can stand on the shoulders of generations of digital designers, and limit ourselves to sets of functions and their combinations which can be proven to span the range of all possible digital function mappings of any number of input and output bits.

The main though is that we can start with a 'select' function, which is capable of having an active, we currently define as one for exactly one input combination, such as for a and function, we have only a 1 at the output when both inputs are 1. We can extend that to a and with more than two inputs:

 and_ninputs = and_1(i1, and_2(i2, and_3(i3, and_n-1(in-1, in))))

Intuitively we can understand that the only way to make all ands give out a 1 is to feed all inputs with a 1, otherwise one or more will spoil the overall 1 for certain. Logical designers would never built this circuit with longest path of n-1, because that would have corresponding electronical signal delay, but built it like a tree, which is logically equivalent, as long as the truth table is 1 only for all inputs 1.

Now for a set of digital values corresponding to the full set of possible numbers corresponding to n bits of information, we can define n functions such that for each combination there is exactly one function which evaluates to a 1, and all others zero. Assuming a andn function and a invert-or-not (lets call it exor) function which can take any number of inputs, such function set can be generated as follows:

 select = andn( inv(exor (i1,select1)), inv(exor (i2,select2)), inv(exor (in,selectn)),  )     (non-tcl notation)

Where the select1 ... selectn bits are set to the value the function is supposed to return 1 for. The exor is exclusive or, which has truth table:

So the combined function nexor outputs a one whenever its two inputs are equal, and a zero when they are not equal. The exor function can be made in the same way as the above construction, filling in the not exor part for all 4 possibilites and simplifing the logical function result:

 proc exor {a b} {return [or [and [inv $a] $b] [and $a [inv $b]]]}

When we apply the whole set of select functions to a chosen domain of binary numbers as inputs to a 'combination' function, which generates an output word for each possible combination of inputs, which are combined into the m bits spanning the output co-domain of any logical function from n to m bits. The or combination combines the outputs of all select functions which make the overall function output bit the 'or' is associated with, which correspond to a logical output of 1. So in fact we take the ouput range of the logical function at hand, and for each bit we determine which inputs combinations make that output bit a 1, and 'or' the corresponding select intermedeate outputs together. We repeat that for each bit pf the output range, and reuse the set of intermedeate select functions, not implementing those eventually which aren't or-tied at any point.

That is regular digital designer practice, at least those who know what they are doing, and is sometimes called the and or planes solution. Mathematically, it offers a clean and overseeable construction proof for any binary function from any binary number domain to range.

Finally, we can proof that we can construct ANY logical functions by using just NAND gates, by observing that:

 inv = nand(1,in)
 and = not(nand(..))
 or = nand(inv(i1),(inv(i2))

RS comments: It is debatable which operations are basic (e.g. NAND or NOR suffice to build all others), but inv above is frequently called not, and should in parallel to and and or be implemented with !, i.e.

 proc inv a {return [expr {!$a}]}

Also, expr arguments should be braced, for performance and robustness against double substitution. And the use of for above makes my fingers itch - in such a small domain, I'd much rather KISS and write

 foreach j {0 1} {foreach i {0 1} {...}}

than

 for {set j 0} {$j < 2} {inc j} { for {set i 0} {$i < 2} {incr i} {...}}

TV Fine, fine, I was making a point, not doing efficient boolean tcl... Basic operations follow from the number of possible function mapping from m to n bits, one could chose various basis functions to span that functions space, these are the historic ones, for decent and acceptable reasons, and as I'll write further, on can mathematically proof that the ones I present can form the basis for ANY digital functions.

I just corrected the inv, which is inv because that is what the equivalent hardware unit is called, a 'not' unit doesn't have the same ring to it.

And example of a 2 bit decoder followed by an encoder which codes back to binary, is shown in bwise (bottom part of the image):

The generators for the various logical blocks are:

 newproc "newproc \"set or\${genor.n}.q \\\[expr (\\\${or\${genor.n}.a} || \\\${or\${genor.n}.b})\\\]\" or\${genor.n} {a b} q  ;set genor.nlast \${genor.n}" genor n nlast
 ewproc "newproc \"set inv\${geninv.n}.q \\\[expr !(\\\${inv\${geninv.n}.b})\\\]\" inv\${geninv.n} {a} q  ;set geninv.nlast \${geninv.n}" geninv n nlast
 newproc "newproc \"set and\${genand.n}.q \\\[expr (\\\${and\${genand.n}.a} && \\\${and\${genand.n}.b})\\\]\" and\${genand.n} {a b} q  ;set genand.nlast \${genand.n}" genand n nlast

As shown in the image, these are blocks which can be 'eval'-ed using the popup menu, or the button in the 'data' window, to generate blocks of and, or and inv kind. As shown with genor, we can initialize the input to count 0 or 1, and wrap back the ouput to the input after changing the block function code to increment the counter with one. Then we can call 'funprop' on the single blocks with feedback, and we get incrementing indices when generating logical blocks.

The generated and or and invert blocks can be dragged in place on the canvas and connected.

Some special blocks with general applicability

 newproc {binary scan [binary format S ${tobin4.i}] B* ba ; set tobin4.bin [lrange [split $ba {}] end-3 end]} tobin4  i bin
  newproc {for {set i 0} {$i <4} {incr i} {set bits4.o$i [lindex ${bits4.in} $i]}} bits4 in {o1 o2 o3 o4}

The connections can be taken from

 netlistout
 {Entry1 out Proc1 in} {Proc1 out Mon1 in} {genor nlast genor n} {or2 q list4 i1} {or3 q or2 a} {inv1 q and1 a} {inv1 q and3 a} {inv2 q and1 b} {inv2 q and2 b} {and1 q Text1 in} {and2 q Text2 in} {and2 q or3 a} {and2 q or3 b} {bits4 o1 inv1 a} {bits4 o1 and2 a} {bits4 o1 and4 a} {bits4 o1 list4 i3} {bits4 o2 inv2 a} {bits4 o2 and3 b} {bits4 o2 and4 b} {bits4 o2 list4 i4} {and3 q Text3 in} {and3 q or4 a} {and3 q or4 b} {and4 q Text4 in} {and4 q or2 b} {and4 q or5 b} {tobin4 bin bits4 in} {Entry2 out tobin4 i} {or4 q or5 a} {or5 q list4 i2} {list4 l Mon2 in}

The idea in bwise is that the variables in a block are available in the 'data' window, and the names are subpaths of the block names, and that apart from input and output pins there is limited state and other dependence outside the obvious for such a block.

The funprop popup menu makes the data riple through the blocks as if they are functions, which in this example works fine.