Boolean Algebra and Logic Simplification

AIM:
The aim of this chapter is to enable students to apply the laws and rules of Boolean
algebra and the karnaugh map to simplify complex equations and design simplified logic
circuits using logic gates.

Objectives:
 Apply the basic laws and rules of Boolean algebra
 Apply De’Morgan’s theorems to Boolean expressions
 Describe gate combinations with Boolean expressions
 Evaluate Boolean expressions
 Simplify expressions by using the laws and rules of Boolean algebra
 Convert any Boolean expression into a sum of products (SOP) form
 Convert any Boolean expression into a product of sums (POS) form
 Relate a Boolean expression to a truth table
 Use a Karnaugh map to simplify Boolean expressions

The Laws of Boolean

As well as the logic symbols "0" and "1" being used to represent a digital input or output,
we can also use them as constants for a permanently "Open" or "Closed" circuit or
contact respectively. Laws or rules for Boolean Algebra expressions have been invented
to help reduce the number of logic gates needed to perform a particular logic operation
resulting in a list of functions or theorems known commonly as the Laws of Boolean.

Boolean Algebra uses these "Laws of Boolean" to both reduce and simplify a Boolean
expression in an attempt to reduce the number of logic gates required. Boolean Algebra is
therefore a system of mathematics based on logic that has its own set of rules which are
used to define and reduce Boolean expressions. The variables used in Boolean Algebra
only have one of two possible values, a "0" and a "1" but an expression can have an
infinite number of variables all labelled individually to represent inputs to the expression,
For example, variables A, B, C etc, giving us a logical expression of A + B+C or ABC,
but each variable can ONLY be a 0 or a 1.

Examples of these individual Boolean laws, rules and theorems for Boolean algebra are
given in the following table.

Truth Tables for the Laws of Boolean

Boolean Equivalent Boolean Algebra

Description
Expression Switching Circuit Law or Rule

A in parallel with closed =

A+1=1 Annulment
CLOSED
 A+0=A A in parallel with open = A Identity

A.1=A A in series with closed = A Identity

A in series with open =

A.0=0 Annulment
OPEN

A+A=A A in parallel with A = A Indempotent

A.A=A A in series with A = A Indempotent

NOT NOT A (double

NOT A = A   Double Negation
negative) = A

A in parallel with not A =

A+A=1 Complement
CLOSED

A in series with not A =

A.A=0 Complement
OPEN

A+B = A in parallel with B = B in

Commutative
B+A parallel with A

A in series with B = B in
A.B = B.A Commutative
series with A

invert and replace OR with de Morgan's

A+B = A.B  
AND Theorem
invert and replace AND with de Morgan's
A.B = A+B  
OR Theorem

The basic Laws of Boolean Algebra that relate to the Commutative Law allowing a
change in position for addition and multiplication,

A+B=B+A and AB=BA

Associative Law allowing the removal of brackets for addition and multiplication,
A+(B+C) = (A+B)+C and A(BC)=(AB)C

Distributive Law allowing the factoring of an expression, are the same as in ordinary
algebra.A(B+C)=AB+AC

Each of the laws above are given with just a single or two variables, but the number of
variables defined by a single law is not limited to this as there can be an infinite number
of variables as inputs to the expression. The above laws can be used to prove any given
Boolean expression and for simplifying complicated digital circuits. A brief description
of the Laws of Boolean is given below.

Description of the Laws and Theorems

Annulment Law - A term AND´ed with a "0" equals 0 or OR´ed with a "1" will equal 1. 

1. A . 0 = 0,    A variable AND'ed with 0 is always equal to 0.

2. A + 1 = 1,    A variable OR'ed with 1 is always equal to 1.

Identity Law - A term OR´ed with a "0" or AND´ed with a "1" will always equal that
term. 

1. A + 0 = A,   A variable OR'ed with 0 is always equal to the variable.

2. A . 1 = A,    A variable AND'ed with 1 is always equal to the variable. 

Indempotent Law - An input AND´ed with itself or OR´ed with itself is equal to that
input. 

1. A + A = A,    A variable OR'ed with itself is always equal to the variable.

2. A . A = A,    A variable AND'ed with itself is always equal to the variable.

Complement Law - A term AND´ed with its complement equals "0" and a term OR´ed
with its complement equals "1".

1. A . A = 0,    A variable AND'ed with its complement is always equal to 0.

2. A + A = 1,    A variable OR'ed with its complement is always equal to 1.

Commutative Law - The order of application of two separate terms is not important. 

1. A . B = B . A,    The order in which two variables are AND'ed makes no

difference.
2. A + B = B + A,    The order in which two variables are OR'ed makes no
difference. 

Double Negation Law - A term that is inverted twice is equal to the original term.
 1. A = A,     A double complement of a variable is always equal to the
variable. 

De’Morgan´s Theorem - There are two "de Morgan´s" rules or theorems, 

(1) Two separate terms NOR´ed together is the same as the two terms inverted
(Complement) and AND´ed for example, A*+B* = (A. B)*. 

(2) Two separate terms NAND´ed together is the same as the two terms inverted
(Complement) and OR´ed for example, A*.B* = (A +B)*.

Other algebraic laws not detailed above include:

 Distributive Law - This law permits the multiplying or factoring out of an

expression.
  
 Absorptive Law - This law enables a reduction in a complicated expression to a
simpler one by absorbing like terms.
  
 Associative Law - This law allows the removal of brackets from an expression
and regrouping of the variables.

Practice 

Using the above laws, simplify the following expression:  (A + B)(A + C)

Q= (A + B)(A + C)  
  AA + AC + AB + BC - Distributive law
  A + AC + AB + BC - Identity AND law (A.A = A)
  A(1 + C) + AB + BC - Distributive law
  A.1 + AB + BC - Identity OR law (1 + C = 1)
  A(1 + B) + BC - Distributive law
  A.1 + BC - Identity OR law (1 + B = 1)
Q= A + BC - Identity AND law (A.1 = A)

Then the expression:  (A + B)(A + C) can be simplified to A + BC

Truth Tables

As with any standard Boolean Expression, the input and output information of any Logic
Gate or circuit can be plotted into a table to give a visual representation of the switching
function of the system and this is commonly called a Truth Table. Logic gate truth
tables show each possible input to the gate or circuit and the resultant output depending
upon the combination of the input(s).
For example, consider a single 2-input logic circuit with input variables labelled as A
and B. There are "four" possible input combinations or 22 of "OFF" and "ON" for the two
inputs. However, when dealing with Boolean expressions we do not general use ON or
OFF but instead give them values of logic level "1" or logic level "0". The four possible
combinations for a two-input gate are given as:

 Input Combination 1. - "OFF" - "OFF" or ( 0,0 )

  
 Input Combination 2. - "OFF" - "ON" or ( 0,1 )
  
 Input Combination 3. - "ON" - "OFF" or ( 1,0 )
  
 Input Combination 4. - "ON" - "ON" or ( 1,1 )

Therefore, a 3-input logic circuit would have 8 possible input combinations or 23 and a 4-
input logic circuit would have 16 or 24, and so on as the number of inputs increases. Then
a logic circuit with "n" number of inputs would have 2n possible input combinations of
both "OFF" and "ON". In order to keep things simple to understand, we will only deal
with simple 2-input logic gates, but the principals are still the same for gates with more
inputs.

The Truth tables for a 2-input basic, universal and other logic gates we dealt with in the
previous tutorial and is herein summarized

Inputs Truth Table Outputs for each Gate

A B AND NAND OR NOR EX-OR EX-NOR
0 0 0 1 0 1 0 1
0 1 0 1 1 0 1 0
1 0 0 1 1 0 1 0
1 1 1 0 1 0 0 1

The following table gives a list of the common logic functions and their equivalent
Boolean notation.

Logic Function Boolean Notation

AND A.B
OR A+B
NOT A
NAND (A.B)*
NOR (A+B)*
EX-OR (A.B) + (A.B) or A⊕B
 EX-NOR (A.B) +  or A ⊕ B

Here are a few examples of how to use Boolean Algebra to simplify larger logic circuits.

Practice

Construct a Truth Table for the logical functions at points C, D and Q in the following
circuit and identify a single logic gate that can be used to replace the whole circuit.

First observations tell us that the circuit consists of a 2-input NAND gate, a 2-input EX-
OR gate and finally a 2-input EX-NOR gate at the output. As there are only 2 inputs to
the circuit labelled A and B, there can only be 4 possible combinations of the input (22)
and these are: 0-0, 0-1, 1-0 and finally 1-1. Plotting the logical functions from each gate
in tabular form will give us the following truth table for the whole of the logic circuit
below.

Inputs Output at
A B C D Q
0 0 1 0 0
0 1 1 1 1
1 0 1 1 1
1 1 0 0 1

From the truth table above, column C represents the output function from the NAND gate
and column D represents the output function from the Ex-OR gate. Both of these two
output expressions then become the input condition for the Ex-NOR gate at the output. It
can be seen from the truth table that an output at Q is present when any of the two inputs
A or B are at logic 1. The only truth table that satisfies this condition is that of an OR
Gate. Therefore, the whole of the above circuit can be replaced by just one single 2-input
OR Gate.

Practice

Find the Boolean algebra expression for the following system.

The system consists of an AND Gate, a NOR Gate and finally an OR Gate. The
expression for the AND gate is A.B, and the expression for the NOR gate is A+B. Both
these expressions are also separate inputs to the OR gate which is defined as A+B. Thus
the final output expression is given as:

The output of the system is given as Q = (A.B) + (A+B), but the notation A+B is the
same as the De Morgan´s notation A.B, Then substituting A.B into the output expression
gives us a final output notation of Q = (A.B)+(A.B), which is the Boolean notation for an
Exclusive-NOR Gate as seen in the previous section.

Inputs Intermediates Output

B A A.B A+B Q
0 0 0 1 1
0 1 0 0 0
1 0 0 0 0
1 1 1 0 1

Then, the whole circuit above can be replaced by just one single Exclusive-NOR Gate
and indeed an Exclusive-NOR Gate is made up of these individual gates.

Practice

Find the Boolean algebra expression for the following system.

This system may look more complicated than the others to analyse but it also consists of
simple AND, OR and NOT gates. Again as with the previous example we can write the
Boolean notation for each logic function to give us a final expression for the output at Q.

The output from the 3-input AND gate is only a "1" when ALL the inputs are at logic
level "1" (A.B.C). The output from the lower OR gate is only a "1" when one or both
inputs B or C are at logic level "0". The output from the 2-input AND gate is a "1" when
input A is a "1" and inputs B or C are at "0". Then the output at Q is only a "1" when
inputs A.B.C equal "1" or A is equal to "1" and both inputs B or C equal "0", A.(B+C).
Then by using "de Morgan's theorem" inputs B and input C cancel out as to produce an
output at Q they can be either at logic "1" or at logic "0". Then this just leaves input A as
the only input needed to give an output at Q as shown in the table below.
 Inputs Intermediates Output
C B A A.B.C B C B+C A.(B+C) Q
0 0 0 0 1 1 1 0 0
0 0 1 0 1 1 1 1 1
0 1 0 0 0 1 1 0 0
0 1 1 0 0 1 1 1 1
1 0 0 0 1 0 1 0 0
1 0 1 0 1 0 1 1 1
1 1 0 0 0 0 0 0 0
1 1 1 1 0 0 0 0 1

Then, the whole circuit above can be replaced by just one single input labeled A thereby
reducing a circuit of 6 individual logic gates to just one single piece of wire, (or Buffer).
This type of circuit analysis using Boolean Algebra can quickly identify any un-
necessary logic gates thereby reducing the number of gates required, the power
consumption of the circuit and of course the cost.

Logic simplification using Boolean

A logic expression can be reduced to its simplest form or changed to a more convenient
form to implement the expression most efficiently using Boolean algebra. The approach
taken in this section is to use the basic laws, rules, and theorems of Boolean algebra to
manipulate and simplify an expression. This method depends on a thorough knowledge
of Boolean algebra, and considerable practice in its application, not to mention a little
ingenuity and cleverness.
Standard form of Boolean expressions

All Boolean expressions, regardless of their form, can be converted into either of two
standard forms: the sum-of-products form or the product-of-sums form.
Standardization makes the evaluation, simplification, and implementation of Boolean
expressions much more systematic and easier.

The Sum-of-Products (SOP) Form

A product term was defined earlier as a term consisting of the product (Boolean
multiplication) of literals (variables or their complements). When two or more product
terms are summed by Boolean addition, the resulting expression is a sum-of-
products(SOP). Some examples are

AB+ABC,
ABC +C*DE*
A*B+A*BC*+AC

The domain of a general Boolean expression is the set of variables contained in the
expression in either complemented or uncomplemented form. For example, the domain of
the expression AB + ABC is the set of variables A, B, C and the domain of the expression
ABC + CDE + BCD is the set of variables A, B, C, D, E.

Each product term in an SOP expression that does not contain all the variables in the
domain can be expanded to standard form to include all variables in the domain and their
complements. As stated in the following steps, a nonstandard SOP expression is
converted into standard form using Boolean algebra rule 6 (A + A = 1) A variable
added to its complement equals to1.

Step 1: Multiply each nonstandard product term by a term made up of the sum of a
missing variable and its complement. This results in two product terms. As you know,
you can multiply anything by 1 without changing its value.
Step 2: Repeat Step 1 until all resulting product terms contain all variables in the domain
in either complemented or uncomplemented form. In converting a product term to
standard form, the number of product terms is doubled for each missing variable,

A standard product term is equal to 1 for only one combination of variable values. For
example, the product term AB*CD* is equal to 1 when A = 1, B = 0, C = 1, D = 0, as
shown below, and is 0 for all other combinations of values for the variables.
AB*CD* = 1x 0* x 1x 0* = 1 .1 .1 .1 = 1

An SOP expression is equal to 1 only if one or more of the product terms in the
expression is equal to 1.

The Product-of-Sums (POS) Form

A sum term was defined as a term consisting of the sum (Boolean addition) of literals
(variables or their complements). When two or more sum terms are multiplied, the
resulting expression is a product-of-sums (POS).
Some examples are
(A + B)(A + B + C)
(A + B + C)(C + D + E)(B + C + D)
(A + B)(A + B + C)(A + C)

A POS expression can contain a single-variable term, as in A(A + B + C)(B + C + D).

In a POS expression, a single overbar cannot extend over more than one variable;
however, more than one variable in a term can have an overbar. For example, a POS
expression can have the term A* + B* + C* but not (A + B + C)*.

Implementation of a POS Expression

Implementing a POS expression simply requires ANDing the outputs of two or more OR
gates. A sum term is produced by an OR operation, and the product of two or more sum
terms is produced by an AND operation. Therefore, a POS expression can be
implemented by logic in which the outputs of a number (equal to the number of sum
terms in the expression) of OR gates connect to the inputs of an AND gate, as shown by
the expression.
(A + B)(B + C + D)(A + C). The output X of the AND gate equals the POS expression.
The Standard POS Form
So far, you have seen POS expressions in which some of the sum terms do not contain all
of the variables in the domain of the expression. For example, the expression
(A + B + C)(A + B + D)(A + B + C + D) has a domain made up of the variables A, B, C,
and D. Notice that the complete set of variables in the domain is not represented in the
first two terms of the expression; that is, D or D* is missing from the first term and C or
C* is missing from the second term.

A standard POS expression is one in which all the variables in the domain appear in each
sum term in the expression.
For example,
(A + B + C + D)(A + B + C + D)(A + B + C + D) is a standard POS expression. Any
nonstandard POS expression (referred to simply as POS) can be converted to the standard
form using Boolean algebra.

Converting a Sum Term to Standard POS

Each sum term in a POS expression that does not contain all the variables in the domain
can be expanded to standard form to include all variables in the domain and their
complements.
As stated in the following steps, a nonstandard POS expression is converted into standard
form using Boolean algebra rule 8 (AA*) = 0) A variable multiplied by its complement
equals 0.

Step 1: Add to each nonstandard product term a term made up of the product of the
missing variable and its complement. This results in two sum terms. As you know, you
can add 0 to anything without changing its value.
Step 2: Apply rule 12 from Table 4–1: A + BC = (A + B)(A + C)
Step 3: Repeat Step 1 until all resulting sum terms contain all variables in the domain in
either complemented or uncomplemented form.
KARNAUGH MAP METHOD

A Karnaugh map provides a systematic method for simplifying Boolean expressions and,
if properly used, will produce the simplest SOP or POS expression possible, known as the
minimum expression. As you have seen, the effectiveness of algebraic simplification
depends on your familiarity with all the laws, rules, and theorems of Boolean algebra and
on your ability to apply them. The Karnaugh map, on the other hand, provides a
“cookbook” method for simplification.
The Karnaugh map is a variation of the truth table. The technique provides a systematic
method for simplifying and manipulating Boolean expressions. Although the technique
may be used for any number of variables, it is seldom used for more than six, and four
variables will be the maximum number presented here.

Mapping a Standard SOP Expression

Mapping is representing each standard product term of a SOP expression on the array as
will be shown. When an SOP expression is completely mapped, there will be a number of
1s on the Karnaugh map equal to the number of product terms in the standard SOP
expression. The cells that do not have a 1 are the cells for which the expression is 0.
Usually, when working with SOP expressions, the 0s are left off the map.
The following steps and the illustration show the mapping process.

Step 1: Determine the binary value of each product term in the standard SOP expression.
After some practice, you can usually do the evaluation of terms mentally.
Step 2: As each product term is evaluated, place a 1 on the Karnaugh map in the cell
having the same value as the product term.

The cells represent all the unique combinations of the two variables A and B and C.
In a K-map it is usual to indicate only the logic '1' conditions, all other empty cells being
understood to correspond to the Boolean functions being logic '0' which applies to POS
as you will realize later.
*A Boolean expression must first be in standard form before you use a Karnaugh map. If
an expression is not in standard form, then it must be converted to standard form by the
procedure covered of numerical expansion. Since an expression should be evaluated
before mapping anyway, numerical expansion is probably the most efficient approach.

Practice

(i) let F=A B́+ Á B́

K-map of the expression therefore is F= A B́+ Á B́

K-map of the expression M = Á B́+ A B́+ AB

Karnaugh Map Simplification of SOP Expressions

The process that results in an expression containing the fewest possible terms with the
fewest possible variables is called minimization. After an SOP expression has been
mapped, a minimum SOP expression is obtained by grouping the 1s and determining the
minimum SOP expression from the map.

Grouping the 1s
You can group 1s on the Karnaugh map according to the following rules by enclosing
those adjacent cells containing 1s. The goal is to maximize the size of the groups and to
minimize the number of groups.
1. A group must contain either 1, 2, 4, 8, or 16 cells, which are all powers of two. In the
case of a 3-variable map, 23 = 8 cells is the maximum group.
2. Each cell in a group must be adjacent to one or more cells in that same group, but all
cells in the group do not have to be adjacent to each other.
3. Always include the largest possible number of 1s in a group in accordance with rule 1.
4. Each 1 on the map must be included in at least one group. The 1s already in a group
can be included in another group as long as the overlapping groups include noncommon
1s.
Practice:
Group the 1s in the following K-Maps

Solution
When all the 1s representing the standard product terms in an expression are properly
mapped and grouped, the process of determining the resulting minimum SOP expression
begins.

The following rules are applied to find the minimum product terms and the minimum
SOP expression:
1. Group the cells that have 1s. Each group of cells containing 1s creates one product
term composed of all variables that occur in only one form (either uncomplemented or
complemented) within the group. Variables that occur both uncomplemented and
complemented within the group are eliminated. These are called contradictory variables.
2. Determine the minimum product term for each group.
(a) For a 3-variable map:
(1) A 1-cell group yields a 3-variable product term
(2) A 2-cell group yields a 2-variable product term
(3) A 4-cell group yields a 1-variable term
(4) An 8-cell group yields a value of 1 for the expression
(b) For a 4-variable map:
(1) A 1-cell group yields a 4-variable product term
(2) A 2-cell group yields a 3-variable product term
(3) A 4-cell group yields a 2-variable product term
(4) An 8-cell group yields a 1-variable term
(5) A 16-cell group yields a value of 1 for the expression
3. When all the minimum product terms are derived from the Karnaugh map, they are
summed to form the minimum SOP expression.

Practice
From the group generated above develop the simplified expression using the above rules?
  Please note that you can map directly from truth tables by taking all
products with 1s or true

Mapping a Standard POS Expression

For a POS expression in standard form, a 0 is placed on the Karnaugh map for each sum
term in the expression. Each 0 is placed in a cell corresponding to the value of a sum
term.
For example, for the sum term A + B* + C, a 0 goes in the 010 cell on a 3-variable map.
When a POS expression is completely mapped, there will be a number of 0s on the
Karnaugh map equal to the number of sum terms in the standard POS expression. The
cells that do not have a 0 are the cells for which the expression is 1. Usually, when
working with POS expressions, the 1s are left off.

The following steps and the illustration show the mapping process.
Step 1: Determine the binary value of each sum term in the standard POS expression.
This is the binary value that makes the term equal to 0.
Step 2: As each sum term is evaluated, place a 0 on the Karnaugh map in the
corresponding cell.
Karnaugh Map Simplification of POS Expressions
The process for minimizing a POS expression is basically the same as for an SOP
expression except that you group 0s to produce minimum sum terms instead of grouping
1s to produce minimum product terms. The rules for grouping the 0s are the same as
those for grouping the 1s that you learn.
Practice Questions

1. What is the difference in mapping a POS expression and an SOP expression?

2. What is the standard sum term for a 0 in cell 1011?
3. What is the standard product term for a 1 in cell 0010?
4. What are the advantages of Boolean logic K- simplification compared to use of
Boolean rules and laws?
5. How does Boolean logic simplification benefit a circuit design in terms of the target
devices?
6. Simplify the following Boolean functions, using three-variable maps:
(a) F(x, y, z) = 0, 2, 4, 5 (b) F(x, y, z = 1, 2, 3, 7,
7. Give three possible ways to express the following Boolean function with eight or fewer
literals:
F = A*BC*D + AB*CD + A*B*C* + ACD*
8. Implement the following Boolean expression on a k-Map:
F = AB*CD* + A*BCD* + AB*C*D + A*BC*D
9. Implement the above Boolean expression with exclusive-OR and AND gates