next up previous
Next: Abstract switching circuits Up: No Title Previous: No Title

Boolean Arithmetic and Switching

Boolean Arithmetic

Boolean values

Boolean arithemetic is also called ``Boolean algebra,'' ``propositional logic,'' ``mod 2 arithmetic.'' The Boolean domain has only two values, which we call 0 and 1. In other books and articles, they are often called T and F. Electronically, they correspond to two distinguishable electrical values, usually voltages. When a wire or other electrical component carries a 1 voltage, our textbook says that the wire is ``asserted.''

Boolean operations

Boolean operations may be defined by tables of all their values. There are only 4 possible unary operations: constant 0, constant 1, identity and inverse. Constants and identity are trivial, and inverse has the table


We write the inverse of a as tex2html_wrap_inline193 . In other places, it may be written as tex2html_wrap_inline195 , tex2html_wrap_inline197 , or -a. Inverse is also called, ``negation,'' or ``not.''

There are 16 possible binary operations. The two most important to us are and and or, with the following tables



We write a and b as tex2html_wrap_inline101 ; other places it may be ab, tex2html_wrap_inline105 , tex2html_wrap_inline107 . Similarly, we write a or b as a+b; other places it may be a|b, tex2html_wrap_inline117 .

Boolean expressions, other operations

Every Boolean operation, no matter how many arguments it takes, may be defined by an expression using inverse and either one of the binary operations and, or. It is particularly convenient to use all three operations in expressions, and unless we say otherwise in a special case, a ``Boolean expression'' will involve these three operations, and occasionally the constants 0 and 1. In fact a single binary operation is sufficient to define all Boolean operations: the nor operation defined by tex2html_wrap_inline259 is sufficient, and so is the nand operation defined by tex2html_wrap_inline261 . You should convince yourself of this fact by defining inverse, and, or in terms of nor and in terms of nand.

Another binary operation that you are likely to see is exclusive or, given by the table


We write the exclusive or of a and b as tex2html_wrap_inline283 . Exclusive or is also called mod 2 sum. Both or and xor are analogues to addition: the or treats 1 as infinity, and the xor works modulo 2. and agrees with multiplication under both the 1-as-infinity and the modulo 2 interpretations. Notice that tex2html_wrap_inline291

Boolean identities

Important properties of the Boolean operations include


These properties resemble the algebraic properties of real number addition and multiplication, but they are more symmetric. In particular, the distributive property works both ways in Boolean arithmetic. Because of the Associative law, we can skip parentheses in long sequences of + or tex2html_wrap_inline295 . To save further parentheses, we give tex2html_wrap_inline295 precedence over +.

Normal forms

The Boolean identities above can be used to simplify Boolean expressions. In particular, every Boolean expression can be simplified into a 3-level form where the bottom level has variables and their inverses, the middle level has ands, the top level has ors--alternatively we can have a middle level of ors and a top level of ands. These forms are called ``sum of products'' and ``product of sums,'' or ``conjunctive normal form'' and ``disjunctive normal form.'' Convince yourself that the Commutative, Associative, Distributive, DeMorgan, and Inverse identities are sufficient to produce normal forms. The Idempotent, Identity, and Annihilate identities can often be used to reduce the size of the normal form.

For a quick silly example, tex2html_wrap_inline301 simplifies to sum of products as follows:


Skipping unneccesary parentheses, this is tex2html_wrap_inline303 . Notice that we have sum of products form already in line 5, then we simplify one of the terms. You should derive the product of sums form, tex2html_wrap_inline305 , for yourself.

The normal forms for Boolean expressions are important to digital circuit design, because they lead to a technique called Programmable Logic Array for implementing an arbitrary Boolean function in a disciplined uniform way. The speed of a circuit depends mostly on the depth of the Boolean expression that it implements, so PLAs are pretty fast. But, the size of an expression may increase exponentially when it is ``simplified'' to sum of products or product of sums, so the PLA technique is used sparingly.

Mathematically, there is a perfect symmetry between sum of products and product of sums, but intuitively the sum of products is often easier to understand, because it corresponds directly to a table of the operation. PLAs in current VLSI technology use sum of products.

next up previous
Next: Abstract switching circuits Up: No Title Previous: No Title

Mike O'Donnell
Fri Jan 22 10:15:39 CST 1999