Version 6 of Boolean Logic

Updated 2003-04-16 16:08:25

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 ~$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:

 0 0  0
 0 1  1
 1 0  1
 1 1  0

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]]]}

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.