Chapter 8: Boolean Algebra

Introduction
Digital circuits perform the binary arithmetic operations with binary digits 1 and 0. These
operations are called logic functions or logical operations. The algebra used to symbolically
describe logic functions is called Boolean algebra.

Boolean Algebra

Boolean algebra is a set of rules and theorems by which logical operations can be expressed
symbolically in equation form and be manipulated mathematically. As with ordinary algebra,
the letters of the alphabet (e.g. A, B, C etc.) can be used to represent the variables. Boolean
algebra differs from ordinary algebra in that Boolean constants and variables can have only
two values, 0 and 1. There are four connecting symbols used in Boolean algebra, these are:

Equals sign (=)

The equals sign in Boolean algebra refers to the standard mathematical equality. In other
words, the logical value on one side of the sign is identical to the logical value on the other side
of the sign. Suppose we are given two logical variables such that A = B. Then if A = 1, then B
= 1 and if A = 0, then B = 0.

Plus sign (+)

The plus sign in Boolean algebra refers to the logical OR operation. Thus, when the statement
A + B = 1 appears in Boolean algebra, it means A ORed with B equals 1. Consequently, either
A = 1 or B = 1 or both equal 1.

Multiply sign (·)

The multiply sign in Boolean algebra refers to AND operation. Thus, when the statement A ·
B = 1 appears in Boolean algebra, it means A ANDed with B equals 1. Consequently, A = 1
and B = 1. The function A · B is often written as AB, omitting the dot for convenience.

Bar sign (–)

The bar sign in Boolean algebra refers to NOT operation. The NOT has the effect of inverting
(complementing) the logical value. Thus, if A = 1, then 𝐴̅ = 0.

Variables, Literals and Terms in Boolean Expressions

Variables are the different symbols in a Boolean expression. They may take on the value ‘0’
or ‘1’. For instance, in the expression below, A, B and C are the three variables. In expression
(2), P, Q, R and S are the variables:
The complement of a variable is not considered as a separate variable. Each occurrence of a
variable or its complement is called a literal. In expressions (1) and (2) there are eight and
seven literals respectively. A term is an expression formed by literals and operations at one
level. Expression (1) has four terms including four AND terms and the OR term that combines
the first-level AND terms.

Theorems of Boolean Algebra

The theorems of Boolean algebra can be used to simplify many a complex Boolean expression
and also to transform the given expression into a more useful and meaningful equivalent
expression. The theorems are presented as pairs, with the two theorems in a given pair being
dual of each other. These theorems can be very easily verified by the method of ‘perfect
induction’. According to this method, the validity of the expression is tested for all possible
combinations of values of the variables involved.
Questions

Simplify the following Boolean expressions to a minimum number of literals:

Boolean expression for a logic circuit

To derive a logic expression from a logic circuit, begin from the leftmost inputs and work
toward the final output by writing the expression for the logic gate.
Sum-of-Products Boolean Expressions (SOP)

A sum-of-products expression contains the sum of different terms, with each term being either
a single literal or a product of more than one literal. It can be obtained from the truth table
directly by considering those input combinations that produce a logic ‘1’ at the output. Each
such input combination produces a term. Different terms are given by the product of the
corresponding literals.
The sum of all terms gives the expression. For example, the truth table (TT 1) can be
represented
by the Boolean expression
 TT 1

Domain of a Boolean expression

It is the set of variables contained in the expression either in the complemented or

Canonical Form of Boolean Expressions

An expanded form of Boolean expression, where each term contains all Boolean variables in
their true or complemented form, is also known as the canonical form of the expression or the
standard form.

A standard SOP expression is one where all the variables of the domain appear in each product
term in the expression. Standard SOP expressions are important in the construction of truth
tables and the Karnaugh map.
Convert the following Boolean expressions to standard SOP:

1. A𝐵̅𝐶 + 𝐴̅𝐵̅ + AB𝐶̅ 𝐷

∑ and ∏ nomenclature
Simplification Techniques

There exist techniques other than the application of laws and theorems of Boolean algebra for
minimizing a given complex Boolean expression. The primary objective of all simplification
procedures is to obtain an expression that has the minimum number of terms. Obtaining an
expression with the minimum number of literal is usually the secondary objective.
If there is more than one possible solution with the same number of terms, the one having the
minimum number of literals is the choice. Some of the techniques are:
(a) the Quine–McCluskey tabular method;
(b) the Karnaugh map method.

The Karnaugh Map

A Karnaugh map is a graphical representation of the logic system. It can be drawn directly
from either minterm (sum-of-products) or maxterm (product-of-sums) Boolean expressions.
In general, a Boolean expression with n variables can be represented by a Kmap of
2𝑛 squares where each square represents a row of an equivalent truth table. Drawing a
Karnaugh map from the truth table involves an additional step of writing the minterm or
maxterm expression depending upon whether it is desired to have a minimized sum-of-
products or a minimized product-of-sums expression.

Construction of a Karnaugh Map

An n-variable Karnaugh map has 2𝑛 squares, and each possible input is allotted a square. In
the case of a minterm Karnaugh map, ‘1’ is placed in all those squares for which the output is
‘1’, and ‘0’ is placed in all those squares for which the output is ‘0’. 0s are omitted for
simplicity. An ‘X’ is placed in squares corresponding to ‘don’t care’ conditions. In the case of
a maxterm Karnaugh map, a ‘1’ is placed in all those squares for which the output is ‘0’, and a
‘0’ is placed for input entries corresponding to a ‘1’ output. Again, 0s are omitted for simplicity,
and an ‘X’ is placed in squares corresponding to ‘don’t care’ conditions.
Questions

1.

2.
Don’t Care Conditions

Sometimes we do not care what value is assumed by a Boolean expression for certain
combinations of variables. For example, in BCD the combination 1010 is invalid and should
not occur when designing or using BCD numbers. Quite often, however, the logic designer
finds it more convenient to treat such a combination as a don’t care condition. The letter X is
often used as a don’t care condition. The following example illustrates the procedure.

Question

NB:
All the 1s have been covered, and so the remaining Xs are disregarded since they neither
reduce the number of the terms nor reduce the number of variables in the expression for E.

Exercise

1. Use proof by perfect induction to show the validity of DeMorgan’s theorems.

2. Simplify the Boolean expression: C = AB’ + A’ + B’