Chapter 8: Boolean Logic and Digital Design | The Art of Assembly Language

Boolean logic is the basis of computation in modern computer systems. You can represent any algorithm, or any electronic computer circuit, using a system of Boolean equations. To fully understand how software operates you need to understand basic Boolean logic and digital design.

This material is especially important to those who want to design electronic circuits or write software that controls electronic circuits. Even if you never plan to do this, you can use your knowledge of Boolean logic to optimize your software. However, there is one other reason for studying Boolean functions, even if you never intend to do either of these two things. Many high-level languages process Boolean expressions, such as those that control an if statement or while loop. By optimizing your Boolean expressions, it is often possible to improve the performance of high-level language code. Therefore, studying Boolean functions is important even if you never intend to design an electronic circuit. It can help you write better code in a traditional programming language.

8.1 Boolean Algebra

Boolean algebra is a deductive mathematical system. A binary operator ' °' accepts a pair of Boolean inputs and produces a single Boolean value. For example, the Boolean AND operator accepts two Boolean inputs and produces a single Boolean output (the logical AND of the two inputs).

8.1.1 The Boolean Operators

For our purposes, we will base Boolean algebra on the following set of operators and values:

The two possible values in the Boolean system are zero and one. Often we will call these values false and true , respectively.
The symbol '*' represents the logical AND operation. For example, A*B is the result of logically ANDing the Boolean values A and B . When using single letter variable names , this text will drop the '*' symbol; therefore, AB also represents the logical AND of the variables A and B, which we will also call the product of A and B .
The symbol '+' represents the logical OR operation. For example, A + B is the result of logically ORing the Boolean values A and B . We will also call this the sum of A and B .
Logical complement, logical negation, and NOT, are all names for the same unary operator. This chapter will use the ( ' ) symbol to denote logical negation. For example, A' denotes the logical NOT of A .

8.1.2 Boolean Postulates

Every algebraic system follows a certain set of initial assumptions, or postulates . You can deduce additional rules, theorems, and other properties of the system from this basic set of postulates. Boolean algebra systems are no different, and usually employ the following postulates:

Closure . A Boolean system is closed with respect to a particular binary operator if, for every pair of Boolean values, it only produces a Boolean result.
Commutativity . A binary operator ' °' is said to be commutative if A °B=B °A for all possible Boolean values A and B .
Associativity . A binary operator ' °' is said to be associative if (A °B) °C= A ° (B ° C) for all Boolean values A, B, and C .
Distribution . Two binary operators ' °' and '%' are distributive if A °(B%C) = (A ° B) % (A ° C) for all Boolean values A, B, and C .
Identity . A Boolean value I is said to be the identity element with respect to some binary operator ' °' if A ° I = A for all Boolean values A .
Inverse . A Boolean value I is said to be the inverse element with respect to some binary operator ' °' if A ° I = B and B ‰ A (i.e., B is the opposite value of A in a Boolean system) for all Boolean values A and B.

When applied to the Boolean operators, the preceding postulates produce the following set of Boolean postulates :

P1: Boolean algebra is closed under the AND, OR, and NOT operations.
P2: The identity element of AND (*) is one, and the identity element of OR (+) is zero. There is no identity element with respect to logical NOT ( ' ).
P3: The * and + operators are commutative.
P4: * and + are distributive with respect to one another. That is, A *(B+C) = (A * B) + (A * C) and A + (B * C) = (A + B) * (A + C) .
P5: * and + are both associative. That is, (A * B) * C = A * (B * C) and (A+B) + C = A + (B + C) .
P6: For every value A there exists a value A' such that A * A' = 0 and A+A' = 1. This value is the logical complement (or NOT) of A .

You can prove all other theorems in Boolean algebra using this set of Boolean postulates. This chapter will not go into the formal proofs of the following theorems, but familiarity with some important theorems in Boolean algebra will be useful. Here are some of the important theorems:

Th1:	A + A = A
Th2:	A * A = A
Th3:	A + 0 = A
Th4:	A * 1 = A
Th5:	A * 0 = 0
Th6:	A + 1 = 1
Th7:	( A + B ) ' = A' * B'
Th8:	( A * B ) ' = A' + B'
Th9:	A + A * B = A
Th10:	A * ( A + B ) = A
Th11:	A + A'B = A + B
Th12:	A' * ( A + B' ) = A'B'
Th13:	AB + AB' = A
Th14:	( A' + B' ) * ( A' + B ) = A'
Th15:	A + A' = 1
Th16:	A * A' = 0

Note	Theorems seven and eight are called DeMorgan's Theorems after the mathematician who discovered them.

An important principle in the Boolean algebra system is that of duality . Each pair, theorems 1 and 2, theorems 3 and 4, and so on, forms a dual . Any valid expression you can create using the postulates and theorems of Boolean algebra remains valid if you interchange the operators and constants appearing in the expression. Specifically, if you exchange the * and + operators and swap the 0 and 1 values in an expression, the resulting expression will obey all the rules of Boolean algebra. This does not mean the dual expression computes the same values ; it only means that both expressions are legal in the Boolean algebra system.

8.1.3 Boolean Operator Precedence

If several different Boolean operators appear within a single Boolean expression, the result of the expression depends on the precedence of the operators. The following Boolean operators are ordered from highest precedence to lowest :

parentheses
logical NOT
logical AND
logical OR

The logical AND and OR operators are left associative. This means that if two operators with the same precedence appear between three operands, you must evaluate the expressions from left to right. The logical NOT operation is right associative, although it would produce the same result using either left or right associativity because it is a unary operator having only a single operand.