

CS302 
Digital Logic & Design
Lesson
No. 08
BOOLEAN
ALGEBRA AND LOGIC
SIMPLIFICATION
Any digital
circuit no matter how
complex can be described by
Boolean Expressions.
Boolean
algebra is the mathematics of
Digital Systems. Knowledge of
Boolean algebra is
indispensable to
the study and analysis of
logic gates. AND, OR,
NOT, NAND and NOR
gates
perform
simple Boolean operations
and Boolean expressions
represent the Boolean
operations
performed by the logic
gates.
· AND
gate
F =
A.B
· OR
gate
F=A+B
F=A
· NOT
gate
F = A.B
· NAND
gate
F=A+B
·
NOR
gate
Boolean
expressions which represent
Boolean functions help in
two ways. The
function
and
operation of a Logic Circuit
can be determined by Boolean
expressions without
implementing
the Logic Circuit. Secondly,
Logic circuits can be very
large and complex.
Such
large
circuits having many gates
can be simplified and
implemented using fewer
gates.
Determining a
simpler Logic circuit having
fewer gates which is
identical to the original
logic
circuit in
terms of the function it
performs can be easily done
by evaluating and
simplifying
Boolean
expressions.
Boolean
Algebra expressions are
written in terms of variables
and literals using
laws,
rules
and theorems of Boolean
Algebra. Simplification of Boolean
expressions is also
based
on the
Boolean laws, rules and
theiorems.
Boolean
Algebra Definitions
1.
Variable
A variable is a
symbol usually an uppercase
letter used to represent a
logical quantity.
A variable
can have a 0 or 1
value.
2.
Complement
A complement is
the inverse of a variable
and is indicated by a bar
over the variable.
Complement of
variable X is X . If X = 0 then
X = 1 and if X = 1
then X = 0.
3.
Literal
A Literal is a
variable or the complement of a
variable.
Boolean
Addition
Boolean
Addition operation is performed by an OR
gate. In Boolean algebra
the
expression
defining Boolean Addition is a
sum term which is the
sum of literals.
A + B, A + B, A + B + C
·
A sum
term is 1 when any one
literal is a 1
·
A sum
term is 0 when all literals
are a 0.
71
CS302 
Digital Logic & Design
Boolean
Multiplication
Boolean
Multiplication operation is performed by
an AND gate. In Boolean algebra
the
expression
defining Boolean Multiplication is a
product term which is the
product of literals.
A.B , A.B , A.B.C
·
A product
term is 1 when all literal
terms are a 1
·
A product
term is 0 when any one
literal is a 0.
Laws of
Boolean Algebra
The
basic laws of Boolean
Algebra are the same as
ordinary algebra and hold
true for
any
number of variables.
1. Commutative
Law for addition and
multiplication
2. Associative
Law for addition and
multiplication
3. Distributive
Law
1. Commutative
Law for Addition and
Multiplication
· Commutative
Law for Addition
A+B=B+A
· Commutative
Law for
Multiplication
A.B =
B.A
Figure
8.1
Implementation
of Commutative Laws
In terms of
implementation, the Boolean
Addition and Multiplication of
two or more
literals is
the same no matter how
they are ordered at the
input of an OR and AND
Gates
respectively.
Commutative law for Addition
and Multiplication holds
true for n number of
literals.
2. Associative
Law for Addition and
Multiplication
· Associative
Law for Addition
A + (B + C) = (A + B) +
C
· Associative
Law for MultiplicationA.(B.C) =
(A.B).C
72
CS302 
Digital Logic & Design
A
A
A.(B.C)
A.B
B
B
(A.B).C
B.C
C
C
Figure
8.2
Implementation
of Associative Laws
In terms of
implementation, the Associative
ordering of literals for
Boolean Addition and
Multiplication
is the same at the input of
an OR and AND gates. Commutative
law for Addition
and
Multiplication holds true
for n number of literals.
The addition of literals B
and C followed
by the
addition of literal A with
the result of B+C is the
same as adding literals A
and B
followed by
the addition of literal
C.
The
multiplication of literals B and C
followed by the multiplication of
the result of B.C
with
literal A is the same as
multiplying literals A and B
followed by the multiplication of
literal
C.
3. Distributive
Law
· Distributive
Law
A.(B + C) =
A.B + A.C
Figure
8.3
Implementation
of Distributive Law
Distributive
law holds true for
any number of literals.
Adding literals B and C
followed
by multiplying
the result with literal A is
the same as multiplying
literal A with literal B
and
adding
the result to the product of
literals A and C.
Rules of
Boolean Algebra
Rules of
Boolean Algebra can be
proved by replacing the
literals with Boolean values
0
and
1.
1.
A+0=A
2.
A+1=1
3.
A.0 =
0
4.
A.1 =
A
5.
A+A=A
A+ A=1
6.
7.
A.A = A
A. A = 0
8.
73
CS302 
Digital Logic & Design
9. A = A
10. A +
A.B = A
= A.(1 +
B)
where
(1+B) according to Rule 2 is
equal to 1
=A
11. A +
A.B = A + B
= A(B+1) +
A.B
according to
Rule 2 (B+1) = 1
= AB +A + A.B
= B(A+
A ) +A
according to
Rule 6 A + A = 1
=B+A
12.
(A+B).(A+C) = A+B.C
= AA+AC+AB+BC
applying the Distributive
Law
= A(1+C+B)
+BC
according to
Rule 2 (1+B+C) = 1
=
A+BC
Demorgan's
Theorems
Demorgan's
First Theorem states: The
complement of a product of variables is
equal
to the
sum of the complements of
the variables.
A.B = A + B
Demorgan;s
Second Theorem states: The
complement of sum of variables is
equal to
the
product of the complements of
the variables.
A + B = A.B
Demorgan's
two theorems prove the
equivalency of the NAND and
negativeOR gates
and
the NOR and negativeAND
gates respectively. Figure
8.4
A +B
A.B
A +B
A.B
Figure
8.4
Implementation
of Demorgan's Theorems
Demorgan's
Theorems can be applied to
expressions having any
number of variables
· X.Y.Z = X + Y + Z
X + Y + Z = X.Y.Z
·
74
CS302 
Digital Logic & Design
Demorgan's
Theorem can be applied to a
combination of other
variables
(A + B.C).(A.C
+
B)
=
(A
+
B.C)
+
(A.C
+
B)
·
= A.(B.C) + (A.C).B
·
= A.(B + C) + (A + C).B
·
= A.B + A.C + A.B + B.C
·
= A.B + A.C + B.C
·
Boolean
Analysis of Logic
Circuits
Boolean
algebra provides a concise
way to represent the
operation of a logic
circuit.
The
complete function of the
logic circuit can be
determined by evaluating the
Boolean
expression
using different input
combinations.
AB + C
C
(AB + C)D
Figure
8.5
Boolean
expression representing a Logic
Circuit
The
expression (AB + C)D can be derived
from the circuit by starting
from the left
hand,
input side of the Logic
Circuit. The AND gate
provides the output AB.
The OR gate adds
the
product term AB and the
complement C to result in (AB + C) term.
The AND gate on the
right
hand side of the circuit
performs a multiplication operation
between the term
(AB + C) and
the literal D resulting in (AB + C)D .
There
are four variables,
therefore the function table
or truth table for the
logic circuit
has 16
possible input combinations.
The expression can be
evaluated by trying out the
16
combinations.
Alternately, the input
combinations A, B, C and D that
set the output of
the
expression
(AB + C)D to 1 can be easily
determined.
From
the expression, the output
is a 1 if both variable D = 1 and
term (AB + C) =1.
The
term (AB + C) =1 only if
AB=1 or C=0.
Thus
expression (AB + C)D =1
if D=1 AND
(C=0 OR AB=1)
75
CS302 
Digital Logic & Design
Inputs
Output
A
B
C
D
F
0
0
0
0
0
0
0
1
0
1
0
0
1
0
0
0
0
1
1
0
0
1
0
0
0
0
1
1
0
1
0
1
1
0
0
0
1
1
1
0
1
0
0
0
0
1
0
1
0
1
1
0
1
0
0
1
0
1
1
0
1
1
0
0
0
1
1
1
0
1
1
1
1
0
0
1
1
1
1
1
Function
table for expression (AB + C)D
Table
8.1
In the
function table the input
conditions for variables A, B, C
and D that satisfy
the
condition
D=1 AND C=0 are 0001,
0101, 1001. The condition
D=1 AND AB=1 are satisfied
by
input
combination 1111. The
condition D=1 AND (C=0 OR
AB=1) is satisfied by the
input
combination
1101.
Simplification
using Boolean
Algebra
Many times a
Boolean expression has to be
simplified using laws, rules
and theorems
of Boolean
Algebra. The simplified
expression results in fewer
variables and a simpler
circuit.
Consider
the Boolean expression AB +
A(B+C) + B(B+C) and the
Logic Circuit represented
by
the
expression. Figure 8.6. The
simplification of the expression
results in an expression B +
AC represented
by a simpler circuit having
fewer gates. Figure
8.7
= AB + A(B+C) +
B(B+C)
= AB + AB + AC + BB
+BC
using
Distributive Law
= AB + AC + B +
BC
BB = B using
rule 7
= AB + AC +
B
(B+BC) = B
using rule 10
= B + AC
(B+AB) = B
using rule 10
Figure
8.6
Logic
Circuit represented by Boolean
expression AB + A(B+C) +
B(B+C)
76
CS302 
Digital Logic & Design
Figure
8.7
Simplified
Logic Circuit represented by
Boolean expression
B+AC
Standard
Form of Boolean
Expressions
All
Boolean expressions can be
converted into and
represented in one of the
two
standard
forms
·
SumofProducts
form
·
ProductofSums
form
1. Sum of Product
form
When
two or more product terms
are summed by Boolean
addition, the result is
a
SumofProduct
or SOP expression.
·
AB +
ABC
·
ABC +
CDE + BCD
AB + ABC + AC
·
The
Domain of an SOP expression is
the set of variables
contained in the
expression,
both
complemented and uncomplemented. A
SOP expression can have a
single variable term
such as A. A
SOP expression can not
have a term of more than
one variable having an
over
bar
extending over the entire
term, such as AB + C .
2. Product of
Sums form
When
two or more sum terms
are multiplied by Boolean
multiplication, the result is
a
ProductofSum
or POS expression.
(A + B)(A + B + C)
·
(A + B + C)(C + D + E)(B + C + D)
·
(A + B)(A + B + C)(A + C)
·
The
Domain of a POS expression is
the set of variables
contained in the
expression,
both
complemented and uncomplemented. A
POS expression can have a
single variable term
such as A. A
POS expression can not
have a term of more than
one variable having an
over
bar
extending over the entire
term such as (A + B)(A + B + C) .
77
CS302 
Digital Logic & Design
Implementation of
an SOP and POS
expression
A SOP
expression can be implemented by an
ANDOR combination of gates.
The
product
terms are implemented by an AND
gate and the SOP
expression is implemented by
OR gate
connected to the outputs of
the AND gates. Figure
8.8
Figure
8.8
SOP
Implementation of Boolean expression
B+AC+AD
A POS
expression can be implemented by an
ORAND combination of gates.
The sum
terms
are implemented by OR gates
and the POS expression is
implemented by AND gate
connected to
the outputs of the OR
gates.
Figure
8.9
POS
Implementation of Boolean expression
(A+B)(B+C+D)(A+C)
Conversion of a
general expression to SOP
form
Any logical
expression can be converted
into SOP form by applying
techniques of
Boolean
Algebra
AB + B(CD + EF) = AB + BCD
+
BEF
·
(A + B)(B + C + D) = AB + AC + AD + B + BC + BD = AC + AD + B
·
(A + B) + C = (A + B)C = (A + B)C = AC + BC
·
78
Table of Contents:

