Boolean Algebra

Boolean Algebra Summary

• We can interpret high or low voltage as representing true or

false.
• A variable whose value can be either 1 or 0 is called a Boolean
variable.
• AND, OR, and NOT are the basic Boolean operations.
• We can express Boolean functions with either an expression or a
truth table.
• Every Boolean expression can be converted to a circuit.
• Now, we’ll look at how Boolean algebra can help simplify
expressions, which in turn will lead to simpler circuits.

2
 Boolean Algebra Summary
• Recall that the two binary values have different names:
– True/False
– On/Off
– Yes/No
– 1/0
• We use 1 and 0 to denote the two values.
• The three basic logical operations are:
– AND
– OR
– NOT
• AND is denoted by a dot (·).
• OR is denoted by a plus (+).
• NOT is denoted by an overbar ( ¯ ), a single quote mark (')
after, or (~) before the variable

3
 Boolean Algebra Summary
• Examples:
– is read “Y is equal to A AND B.”
– is read “z is equal to x OR y.”
– is read “X is equal to NOT A.”

Tabular listing of the values of a function for all possible

combinations of values on its arguments
Example: Truth tables for the basic logic operations:

AND OR NOT
X Y Z = X·Y X Y Z = X+Y X Z= X
0 0 0 0 0 0 0 1
0 1 0 0 1 1 1 0
1 0 0 1 0 1
1 1 1 1 1 1 4
 Boolean Operator Precedence

 The order of evaluation is:

1. Parentheses
2. NOT
3. AND
4. OR
 Consequence: Parentheses appear
around OR expressions
 Example: F = A(B + C)(C + D)
 Boolean Algebra Postulates

• Commutative Law
x•y=y•x x+y=y+x

• Identity Element
x•1=x x+0=x
x’1 = x’ x’+ 0 = x’

• Complement
x • x’ = 0 x + x’ = 1

6 / 28
 Boolean Algebra Theorems

Theorem 1
– x•x=x x+x=x

• Theorem 2
– x•0=0 x+1=1

• Theorem 3: Involution
– ( x’ )’ = x (x)=x

7 / 28
 Boolean Algebra Theorems
• Theorem 4:
– Associative: ( x • y ) • z = x • ( y • z )
(x+y)+z=x+(y+z)
– Distributive :
x•(y+z)=(x•y)+(x•z)
x+(y•z)=(x+y)•(x+z)

• Theorem 5: DeMorgan
– ( x • y )’ = x’ + y’ ( x + y )’ = x’ • y’
–x•y) =x +y (x+y) = x•y

• Theorem 6: Absorption
– x•(x+y)=x x+(x•y)=x
8 / 28
Truth Table to Verify DeMorgan’s

X + Y =X·Y X · Y = X + Y
X Y X·Y X+Y X Y X+Y X · Y X·Y X+Y
0 0 0 0 1 1 1 1 1 1
0 1 0 1 1 0 0 0 1 1
1 0 0 1 0 1 0 0 1 1
1 1 1 1 0 0 0 0 0 0
• Generalized DeMorgan’s Theorem:
X1 + X2 + … + Xn = X1 · X2 · … · Xn
X1 · X2 · … · Xn = X1 + X2 + … + Xn
 Logic Gates

• In the earliest computers, switches were

opened and closed by magnetic fields
produced by energizing coils in relays. The
switches in turn opened and closed the
current paths.

• Later, vacuum tubes that open and close

current paths electronically replaced relays.

• Today, transistors are used as electronic

switches that open and close current paths.
 Logic Gate Symbols

• Logic gates have special symbols:

X X
Z = X ·Y Z= X+ Y X Z= X
Y Y
AND gate OR gate NOT gate or
inverter
 Boolean Functions
• A Boolean function is a function whose arguments, as well as the
function itself, assume values from a two-element set ({0, 1)}).
• Example: F(x, y) = x’y’ + xyz + x’y

• After finding the circuit inputs and outputs, you can come up with
either an expression or a truth table to describe what the circuit does.
• You can easily convert between expressions and truth tables.
Find the circuit’s
inputs and outputs

Find a Boolean
Find a truth table
expression
for the circuit
for the circuit

12
 Boolean Functions

• Boolean Expression/Function x y z F
Example: F (x, y) = x + y’ z
0 0 0 0
• Truth Table 0 0 1 1
All possible combinations 0 1 0 0
of input variables 0 1 1 0
• Logic Circuit 1 0 0 1
1 0 1 1
x F 1 1 0 1
y
z 1 1 1 1

13 / 28
 Logic Diagrams and Expressions
Truth Table Logic Equation/Boolean Function
X Y Z F = X + Y ×Z
0 0 0 0 F = X +Y Z
0 0 1 1
0 1 0 0 Logic Circuit
0 1 1 0 X
1 0 0 1
Y F
1 0 1 1
1 1 0 1 Z
1 1 1 1
• Boolean equations, truth tables and logic diagrams
describe the same function!
• Truth tables are unique, but expressions and logic
diagrams are not. This gives flexibility in
implementing functions.
 Boolean Functions Exercise

• The truth table for the function:

F (X, Y, Z ) = X Y + Y Z is:

X Y Z XY Y YZ F=XY+YZ
0 0 0 0 1 0 0
0 0 1 0 1 1 1
0 1 0 0 0 0 0
0 1 1 0 0 0 0
1 0 0 0 1 0 0
1 0 1 0 1 1 1
1 1 0 1 0 0 1
1 1 1 1 0 0 1
Draw the logic circuit for the boolean function above.
 Converting from Truth Table to Boolean Function

• In designing digital circuits, the designer often begins

with a truth table describing what the circuit should do.

• The design task is largely to determine what type of

circuit will perform the function described in the truth
table.

• While some people seem to have a natural ability to look

at a truth table and immediately envision the necessary
logic gate or relay logic circuitry for the task, there are
procedural techniques available for the rest of us.

• Here, Boolean algebra proves its utility in a most

dramatic way!
 Converting from Truth Table to Boolean Function

• This problem will be solved by showing that any

Boolean function can be represented by a Boolean
sum of Boolean products of the variables and their
complements or the product of sums.

• There are two ways to convert from truth tables

to Boolean functions:
1. Using Sum of Products /Minterms
2. Using Product of Sums /Maxterms
 Converting from Truth Table to Boolean Function

• Minterm
– Product (AND function)
A B C Minterm

– Contains all variables

0 0 0 0 m0 ABC

– Evaluates to ‘1’ for a

1 0 0 1 m1 ABC
specific combination 2 0 1 0 m2 ABC
Example 3 0 1 1 m3 ABC
A=0 A B C 4 1 0 0 m4 ABC
B=0 (0) • (0) • (0)
5 1 0 1 m5 ABC
6 1 1 0 m6
C=0 ABC
1 • 1 • 1=1
7 1 1 1 m7 ABC

18 / 28
 Converting from Truth Table to Boolean Function

• Maxterm
– Sum (OR function)
A B C Maxterm
M0 A + B + C
– Contains all variables
0 0 0 0

– Evaluates to ‘0’ for a

1 0 0 1 M1 A + B + C
M2 A + B + C
specific combination 2 0 1 0
M3 A + B + C
Example 3 0 1 1
M4 A + B + C
A=1 A B C 4 1 0 0
M5 A + B + C
B=1 (1) • (1) • (1)
5 1 0 1
6 1 1 0 M6 A + B + C
C=1
0 • 0 • 0=0
7 1 1 1 M7 A + B + C

19 / 28
 Converting from Truth Table to Boolean Function

• Truth Table to Boolean Function

A B C F F = ABC + A BC + A BC + ABC
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 0
1 1 1 1
Using Minterms
20 / 28
 Converting from Truth Table to Boolean Function

• Truth Table to Boolean Function

F = ( A + B + C)( A + B + C ) ( A + B + C ) ( A + B + C )
A B C F
0 0 0 1
0 0 1 0
0 1 0 1
0 1 1 1
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 0 Using Maxterms
21 / 28
 Converting from Truth Table to Boolean Function

• Sum of Minterms A B C F F
F = ABC + ABC + ABC + ABC 0 0 0 0 0 1
1 0 0 1 1 0
F = m1 + m4 + m5 + m7
2 0 1 0 0 1
F =  (1,4,5,7)
3 0 1 1 0 1
•Product of Maxterms 4 1 0 0 1 0
F = ABC + ABC + ABC + ABC 5 1 0 1 1 0
F = A BC + ABC + ABC + AB C 6 1 1 0 0 1
7 1 1 1 1 0
F = A BC  ABC  ABC  AB C
F = ( A + B + C )( A + B + C )( A + B + C )( A + B + C )
F = M0 M2 M3 M6
F =  (0,2,3,6) 22 / 28