Lesson 2Lesson 2
The Properties of Boolean Functions
The basic Boolean operations and the gates that represent them were described in Lesson 1. In this lesson we will begin examining more complex Boolean expressions. As mentioned in the previous lesson, Boolean expressions are written using ordinary algebraic notation, with AND represented as multiplication, and OR represented by addition. As in algebraic notation, multiplication has precedence over addition, so the expression ab+cd represents the Boolean Expression (a AND b) OR (c AND d) . The NOT is represented by placing the prime symbol ' after a variable or an expression. The NOT operation has the highest priority, so ab' represents the expression a AND (NOT b). Parentheses may be used to specify the order of operations. Remember that the variables in an expression can have one of two values, 0 and 1.
As in ordinary algebra, there are several laws that all Boolean Expressions must obey. These laws can be used to rearrange and simplify a Boolean Expression. As a result the equivalent switching circuit is also simplified. The following table lists some of the basic laws of Boolean Algebra.
| Equation | Law |
| 1a=a | And Identity Law |
| a+0=a | Or Identity Law |
| ab = ba | Commutativity of and |
| a+b = b+a | Commutativity of or |
| (ab)c = a(bc) | Associativity of and |
| (a+b)+c = a+(b+c) | Associativity of or |
| a(b+c) = ab+ac | And distributes over or |
| a+bc = (a+b)(a+c) | Or distributes over and |
| aa'=0 | And inverse law |
| a+a'=1 | Or inverse law |
These laws can be proven using a procedure known as Exhaustive Induction. In simple terms this means that we list all input possibilities for each side of an equation, and then reduce both sides to a single Boolean value. We then verify that, for each input value, the resultant values are the same.
In the following example, we will verify the associativity law for AND.
| (a | AND | b) | AND | c | = | a | AND | (b | AND | c) |
| 0 | 0 | 0 | 0 | 0 | 0 | |||||
| 0 | 0 | 1 | 0 | 0 | 1 | |||||
| 0 | 1 | 0 | 0 | 1 | 0 | |||||
| 0 | 1 | 1 | 0 | 1 | 1 | |||||
| 1 | 0 | 0 | 1 | 0 | 0 | |||||
| 1 | 0 | 1 | 1 | 0 | 1 | |||||
| 1 | 1 | 0 | 1 | 1 | 0 | |||||
| 1 | 1 | 1 | 1 | 1 | 1 |
First we apply the parenthesized AND operators.
| (a | AND | b) | AND | c | = | a | AND | (b | AND | c) |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |||
| 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | |||
| 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | |||
| 0 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | |||
| 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | |||
| 1 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | |||
| 1 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | |||
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Next we apply the other two AND operators.
| (a | AND | b) | AND | c | = | a | AND | (b | AND | c) |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | |
| 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | |
| 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | |
| 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | |
| 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | |
| 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | |
| 1 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Finally, we compare the results to verify that they are the same.
| (a | AND | b) | AND | c | = | a | AND | (b | AND | c) |
| 0 | 0 | 0 | 0 | 0 | ok | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 | 1 | ok | 0 | 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 | 0 | ok | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 0 | 1 | ok | 0 | 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 0 | ok | 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 1 | ok | 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 | 0 | ok | 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 | ok | 1 | 1 | 1 | 1 | 1 |
When this procedure is done using pencil and paper, we generally cross out values as they are used to prevent confusion. You should perform this operation for a few laws, just for the practice. However, our main tool for verifying the correctness of these laws will be to create an equivalent circuit for each side of the equation, and then simulate both circuits simultaneously. We will then verify that the simulated outputs for both circuits are the same. (This assumes, of course, that the simulator is correct!)
To verify the commutativity of AND we would use the following FHDL description.
| AndComm: | circuit | |
| inputs | a,b,c | |
| outputs | q1,q2 | |
| g1: | and | (b,c),x1 |
| g2: | and | (a,x1),q1 |
| g3: | and | (a,b),x2 |
| g4: | and | (x2,c),q2 |
| endcircuit |
Use the following window to type this FHDL description.
Once the description is complete, type
your inputs in the box below. In this case there are eight inputs,
0,0,0 0,0,1 0,1,0 0,1,1 1,0,0 1,0,1 1,1,0
and 1,1,1. You must use all eight inputs to verify the correctness of
the associative law.
You should use these two windows to verify the correctess of all of the laws listed above. To verify the correctness of the AND and OR identity laws, you need to know two more things about FHDL, namely how to define constant ones and constant zeros. The following two circuit descriptions show you how to do this. The first circuit demonstrates the one statement that is used to declare constant one signals.
| AndIdent: | circuit | |
| inputs | a | |
| outputs | q | |
| one | c1 | |
| g1: | and | (a,c1),q |
| endcircuit |
The second circuit demonstrates the zero statement that is used to declare constant zero signals.
| OrIdent: | circuit | |
| inputs | a | |
| outputs | q | |
| zero | c0 | |
| g1: | or | (a,c0),q |
| endcircuit |
Use these two circuits to verify the identity laws. Remember that a primed variable requires the use of a NOT gate such as the following.
g1: not a,aprime
Although we have not yet used circuit diagrams for simulation, we could use the following circuit to verify the correctness of the AND identity law. In later lessons we will use circuit diagrams such as the following for simulation exercises. Click the button to display the diagram.
The course continues with Lesson 3.
Text Editor windows are implemented with BenetTec's
AllText 4.5 control.
Drawings are from the Dover Old
Fashioned Clip Art series.
Except as noted above, this
page, its contents and ActiveX controls are Copyright (c) 1999, Peter M.
Maurer
For comments and complaints send mail to Peter_Maurer@Baylor.edu.
Home page http://cs.baylor.edu/~maurer