Loudoun County Public Schools



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.

[pic]

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 && B |

| |0 |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 && B |

| |0 |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 |

|2. |DISTRIBUTIVE |[pic] |

|3. |IDENTITY |[pic] |

|4. |INVERSE |[pic] |

|5. |IDEMPOTENT |[pic] |

|6. |BOUNDEDNESS |[pic] |

|7. |ABSORPTION |[pic] |

|8. |ASSOCIATIVE |[pic] |

|9. |INVOLUTION |[pic] |

|10. |DERIVED |[pic] |

|11. |DeMORGAN’S |[pic] |

ILLUSTRATE SIMPLIFICATION USING THE LAWS

[pic]

|Write the Boolean expression for the logic circuit at the right. |

|[pic] | |

| |[pic] |

|Simplify the expression using Boolean identities. |

| | |

|[pic] |Distributive |

|[pic] |Distributive |

|[pic] |Inverse |

|[pic] |Identity |

|[pic] |Distributive |

|Draw the simplified logic circuit. |[pic] |

EXERCISES

PART I. Match each expression to the law that can be used to simplify it, then simplify each expression.

|_F__ 1. |[pic] |Commutative |

|_J__ 2. |[pic] |Distributive |

|_E__ 3. |[pic] |Identity |

|_K__ 4. |[pic] |Inverse |

|_F__ 5. |[pic] |Idempotent |

|_C__ 6. |[pic] |Boundedness |

|_J__ 7. |[pic] |Absorption |

|_B__ 8. |[pic] |Associative |

|_G__ 9. |[pic] |Involution |

|_D_ 10. |[pic] |Derived |

|_K_ 11. |[pic] |DeMorgan’s |

|_K_ 12. |[pic] | |

PART II. Simplify the following using the Laws of Boolean Algebra. Show the steps and the law used for each step.

|[pic] |[pic] |

|[pic] |[pic] |

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.

[pic]

[pic]

[pic]

[pic])

EXERCISES

PART IV.

1. Prove the following with a truth table.

[pic]

|A |B |!A |!B |A&&B |!(A&&B) |

|0 |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. [pic]

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 [pic]

5. a. Write the Boolean expression of the

circuit below.

a. Construct a truth table to prove that your answer = [pic]

|A |B |!A |B || !A |

|0 |0 |1 |1 |

|0 |1 |1 |1 |

|1 |0 |0 |0 |

|1 |1 |0 |1 |

6. Draw a logic circuit for [pic][pic]

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:

|[pic]|[pic]|[pic]|[pic]|[pic] |[pic] |[pic] |[pic] |

|0 |0 |1 |1 |1 |0 |1 | |

|0 |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?

|[pic] |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 |[pic] |____11111110_______ |

|Y = 00111110 |[pic] |____00000000_______ |

|Z = 00110010 |[pic] |____00110010_______ |

| |[pic] |____00110011_______ |

| |[pic] |____00000001_______ |

3. Write the Boolean expression for this WIRING DIAGRAM.

4. Draw the LOGIC CIRCUIT for [pic]

5. Write the Boolean expression that describes

the LOGIC CIRCUIT to the right.

6. Complete the truth table to prove [pic]

|A |B |

| | |

| | |

|Shade the Venn diagram to illustrate | |

| | |

| | |

| | |

| | |

| | |

|GIVEN: [pic] | |

|Draw a wiring diagram to illustrate |b. Simplify the expression using Boolean algebra. |

| | |

| | |

| | |

| | |

| | |

| | |

| | |

|Shade the Venn diagram to illustrate |d. Draw the logic circuit. |

| | |

| | |

| | |

| | |

| | |

| | |

| | |

| | |

| | |

|GIVEN: [pic] | |

| a. Draw the logic circuit |b. Simplify using Boolean algebra |

[pic]

-----------------------

!A: NC Switch

A

A || B: Parallel NO Switches

A

B

A && B: Series of NO Switches

A

B

NO – normally open

NC – normally closed

!A && (B || X) && Y

(A && B || X) && Y

A && B && X || Y

A && B || X && Y

A

B

X

Y

A

B

X

Y

A

B

X

Y

X

A

B

Y

00010101

10110101

01010101

11110101

10110101

01010101

10110010

01001101

A

B

A

A

B

B

10110100

11000110

10110100

11000110

10110100

B

C

A

D

A

C

B

A

!A || A = 1

A

B

!(A || B)

A

B

A || A && B

!A || !B = !(A&&B)

[pic]

A

C

B

A

A

A

C

B

AA

B

A

B

B

B

(A || B) && ( A || !B ) = A

A

A

B

A

C

B

A

B

A

C

B

A

B

A

B

A

A

B

[pic]

A

B

A

B

A

B

A

B

[pic]

A

BA

A

BA

A

BA

CA

A

BA

CA

A

B

B

A

A

a

c

h

b

f

d

e

g

X

Z

Y

[pic]

&

||

A

B

B

Answer Key (partial)

B

A

10000100

01001011

A

C

B

C

11110110

A

(A || B) && C

( B || C || D ) && !A

B

A

A && B && C || !C

(A || B) && !B

( A || !B ) && ( C || !B )

A

B

A || ( B && C)

B

A

B

C

B

C

B

A

[pic]A

C

C

B

[pic]A

B

A

B

C

A

C

A

B

A

B

A

B

A

FCPS

Java

Packets

A

B

C

D

A

B

C

D

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download