Boolean Algebra
Boolean Algebra
by Charles W. Brewer, July 2000
Revised Aug 2004
Based upon material developed by
Sally Bellacqua, Mary Johnson, and Janet Mulloy
Fairfax County Public Schools
Fairfax, Virginia
INTRODUCTION
Mathematician George Boole introduced his early ideas on symbolic logic to the world in “The Mathematical Analysis of Logic.” The publication demonstrated that logic could be rendered as algebraic equations and that that mathematics and logic should be associated as opposed to logic and metaphysics. His work on logic is used today in mathematics, information theory, switching theory, graph theory, computer science, and artificial intelligence.
BOOLEAN STATEMENTS
In JAVA, we have Boolean statements that evaluated as either true or false. How does the computer circuitry do this? Some elemental ideas of electricity are all that we need to understand the computer, an electrical device. Although our computers today use chips for transporting electrical impulses, we can think of these as consisting of wires that at one time may be carrying a current and at other times may not.
We can consider a true Boolean statement as current flowing through a switch in a
wire and a false Boolean statement as current not flowing though. Thus, a
true condition could be represented by a closed switch and a false statement by an open switch.
We can represent a Boolean AND statement with switches in series. The only way that current can flow through the circuit (true) is when both switches are closed (true). An example is a car radio – it normally requires that the ignition switch be closed as well as radio being turned on to operate.
The Boolean OR statement can be represented with switches in parallel. Current would flow (true) when one, the other, or both switches are closed. An example is the interior light of a car – it comes on when any of the doors are opened thus closing the switch for that door.
The Boolean NOT statement can be represented with a switch that is normally closed, and open when the input value is true.
In JAVA, AND is represented by &, OR by ||, and NOT by !.
When combined in expressions, the order of precedence is NOT, AND, and OR.
EXAMPLES: A, B, X, and Y are Boolean expressions that may be evaluated as true or false. When combined in expressions, the order of precedence is !, &, and ||.
ANOTHER FORM OF NOTATION - THE LOGIC CIRCUIT
In order for human beings to communicate with the machines, we can represent signals flowing through a wire as binary numbers, such as 10101010, where 1 represents current flowing and 0 represents no current. Similarly, 00000011 would represent six off values followed by two on values.
If two input signals are received, then timing is important. Each input pair must be received simultaneously and must have time to produce the correct output before the next input pair appears.
The AND and OR circuits receive information at two inputs and present the result at one output.
In logic circuit notation we represent the AND circuit as:
and the OR circuit as:
We also have a NOT circuit which has one input and one output. The two contacts always have opposite values. In logic circuit notation we represent the NOT circuit as:
EXAMPLE
The Boolean expression for this circuit is:
(A || B) & (A || !B)
And the corresponding wiring diagram:
EXERCISES
If A, B, C, and D represent Boolean expressions, draw a logic circuit for the following.
1. (A || B) & C
2. A || !B & C
3. A & !(B & C) || D
4. A & B || C & D
5. How would this pair of sequences be processed by an AND gate?
6. How would a NOT gate process this sequence?
7. How would this pair of sequences be processed by an OR gate?
8. Write a Boolean expression for each of these logic circuits.
Venn Diagrams
If we use 1 to represent the Universal set and 0 to represent the null or EMPTY set, then we can illustrate the following with VENN diagrams. Note that AND (&) corresponds to the intersection of sets while OR (||) corresponds to the union of the sets.
EXERCISES
Match each of
the following
sets to the Venn
diagram to the
right.
D 1. Vertical lines A. A || B
C 2. Horizontal lines B. A & B
E 3. Shaded area C. !A
B 4. The unshaded area D. !B
F 5. Crosshatched area E. !A || !B
A 6. The uncrosshatched area F. !A & !B
SHADE VENN DIAGRAMS TO REPRESENT EACH OF THE FOLLOWING
A & A A & !A (A & B) & C
! ( A || B) !(A & B) A & (B || C)
!A & !B !A || !B A & (A || B)
(A || B) & (B || C) A || (!A & B) !A & !B & !C
DRAW A VENN
DIAGRAM TO
ILLUSTRATE THE
LOGIC CIRCUIT
TO THE RIGHT
TRUTH TABLES
There are four possible combinations for two switches that are either open or closed. Using a 0 for open (no current flowing or FALSE) and a 1 for closed (current flowing or TRUE), we can represent all of these combinations with a truth table.
A
/ B / A & B / A || B / !A / With three elements we would have eight possibilities. Could you list them?0 / 0 / 0 / 0 / 1
0 / 1 / 0 / 1 / 1
1 / 0 / 0 / 1 / 0
1 / 1 / 1 / 1 / 0
A & (A || B) = A / A / B / A || B / A & (A || B)
We could illustrate this identity with a truth table. / 0 / 0 / 0 / 0
0 / 1 / 1 / 0
1 / 0 / 1 / 1
1 / 1 / 1 / 1
Notice that we have demonstrated that this identity is true, since the last column has the same truth as column A.
We could also illustrate this
with a wiring diagram
a logic diagram,
or with a VENN diagram
EXERCISES
A & (!A || B) = A & B
ILLUSTRATE WITH A
VENN DIAGRAM: PROVE WITH A TRUTH TABLE
A / B / !A / ! A || B / A & (!A || B) / A & B0 / 0 / 1 / 1 / 0 / 0
0 / 1 / 1 / 1 / 0 / 0
1 / 0 / 0 / 0 / 0 / 0
1 / 1 / 0 / 1 / 1 / 1
A || A & B = A
ILLUSTRATE WITH A
VENN DIAGRAM: PROVE WITH A TRUTH TABLE
A / B / A & B / A || A & B0 / 0 / 0 / 0
0 / 1 / 0 / 0
1 / 0 / 0 / 1
1 / 1 / 1 / 1
USE A TRUTH TABLE TO PROVE: (A || B) & (!A || C) = (A & C) || (!A & B)
A / B / C / !A / A || B / !A || C / (A || B) & (!A || C) / A&C / !A&B / (A & C) || (!A & B)0 / 0 / 0 / 1 / 0 / 1 / 0 / 0 / 0 / 0
0 / 0 / 1 / 1 / 0 / 1 / 0 / 0 / 0 / 0
0 / 1 / 0 / 1 / 1 / 1 / 1 / 0 / 1 / 1
0 / 1 / 1 / 1 / 1 / 1 / 1 / 0 / 1 / 1
1 / 0 / 0 / 0 / 1 / 0 / 0 / 0 / 0 / 0
1 / 0 / 1 / 0 / 1 / 1 / 1 / 1 / 0 / 1
1 / 1 / 0 / 0 / 1 / 0 / 0 / 0 / 0 / 0
1 / 1 / 1 / 0 / 1 / 1 / 1 / 1 / 0 / 1
BASIC LAWS OF BOOLEAN ALGEBRA
Each law contains two parts which may be obtained from one another by interchanging the 0 and 1 and at the same time interchanging & and ||.
Since the DUAL of each is also a law, it follows that if a theorem is proved from these laws, then the dual of the theorem is also proved.
1. / COMMUTATIVE2. / DISTRIBUTIVE
3. / IDENTITY
4. / INVERSE
5. / IDEMPOTENT
6. / BOUNDEDNESS
7. / ABSORPTION
8. / ASSOCIATIVE
9. / INVOLUTION
10. / DERIVED
11. / DeMORGAN’S
ILLUSTRATE SIMPLIFICATION USING THE LAWS
b. Simplify the expression using Boolean identities.
Distributive
Distributive
Inverse
Identity
Distributive
c. Draw the simplified logic circuit.
EXERCISES
PART I. Match each expression to the law that can be used to simplify it, then simplify each expression.
_F__ 1. / A. Commutative_J__ 2. / B. Distributive
_E__ 3. / C. Identity
_K__ 4. / D. Inverse
_F__ 5. / E. Idempotent
_C__ 6. / F. Boundedness
_J__ 7. / G. Absorption
_B__ 8. / H. Associative
_G__ 9. / I. Involution
_D_ 10. / J. Derived
_K_ 11. / K. DeMorgan’s
_K_ 12.
PART II. Simplify the following using the Laws of Boolean Algebra. Show the steps and the law used for each step.
EXERCISES
Part III. Draw an appropriate Venn diagram for each of the following. Shade the area indicated by the expression. Using the Venn diagram and/or the Boolean laws, write the expression in its simplest form.
)
BA -7
Boolean Algebra
EXERCISES
PART IV.
1. Prove the following with a truth table.
A / B / !A / !B / A&B / !(A&B) / !A||!B0 / 0 / 1 / 1 / 0 / 1 / 1
0 / 1 / 1 / 0 / 0 / 1 / 1
1 / 0 / 0 / 1 / 0 / 1 / 1
1 / 1 / 0 / 0 / 1 / 0 / 0
2. Prove the following with a truth table.
A / B / !A / !A&B / A||(!A&B) / A||B0 / 0 / 1 / 0 / 0 / 0
0 / 1 / 1 / 1 / 1 / 1
1 / 0 / 0 / 0 / 1 / 1
1 / 1 / 0 / 0 / 1 / 1
3. Label the numbered parts of the Venn
diagram, using the sets X, Y, and Z.
a.
b. ______X & Y & !Z______
c. ______X & !Y & !Z_____
d. ______X & Z & !Y______
e. ______Z & !Y & !X______
f. ______X & Y & Z______
g. ______!X & !Y & !Z___
h. ______Y & !X & !Z _____
4. Draw a logic circuit of
5. a. Write the Boolean expression of the
circuit below.
b. Construct a truth table to prove that your answer =
A / B / !A / B || !A0 / 0 / 1 / 1
0 / 1 / 1 / 1
1 / 0 / 0 / 0
1 / 1 / 0 / 1
6. Draw a logic circuit for
BA -7
Boolean Algebra
USING BOOLEAN ALGEBRA TO DESIGN TEST CONDITIONS AND CIRCUITS.
Suppose we were asked to design a circuit that was only on (True) when the two inputs A and B are both off (False) or only A is on (True).
The truth table would look like this: The corresponding logic circuit is:
0 / 0 / 1 / 1 / 1 / 0 / 10 / 1 / 1 / 0 / 0 / 0 / 0
1 / 0 / 0 / 1 / 0 / 1 / 1
1 / 1 / 0 / 0 / 0 / 0 / 0
Can this expression be simplified?
Thus we can see that the output only depends upon the state of input B. The simplified logic circuit would be:B
EXERCISE
Using the steps described above, design a logic circuit that inputs the values of two variables and outputs TRUE whenever both variables have the same value.
A / B
REVIEW EXERCISES
1. Determine the output of each gate in the following logic diagram.
______00010100______
______11100010______
______10111111______
2. Given the indicated input values for X, Y, and Z, determine the value of each of the following Boolean expressions.
X = 11100100 / ____11111110______Y = 00111110 / ____00000000______
Z = 00110010 / ____00110010______
____00110011______
____00000001______
3. Write the Boolean expression for this WIRING DIAGRAM.
4. Draw the LOGIC CIRCUIT for
5. Write the Boolean expression that describes
the LOGIC CIRCUIT to the right.
6. Complete the truth table to prove
A
/B
/ !A / !B / A & !B / !A || A & !B / !A || !B0 / 0 / 1 / 1 / 0 / 1 / 1
0 / 1 / 1 / 0 / 0 / 1 / 1
1 / 0 / 0 / 1 / 1 / 1 / 1
1 / 1 / 0 / 0 / 0 / 0 / 0
7. Given:
a. Draw the equivalent logic circuit. / b. Simplify the expression using Boolean algebra.
B
b. Shade the Venn diagram to illustrate
8. GIVEN:
a. Draw a wiring diagram to illustrate / b. Simplify the expression using Boolean algebra.
c. Shade the Venn diagram to illustrate / d. Draw the logic circuit.
9. GIVEN:
a. Draw the logic circuit / b. Simplify using Boolean algebra
BA -7