1 Digital Logic BIT

Unit-3
Simplification of Boolean Functions

For more notes visit:

https://collegenote.pythonanywhere.com/

https://collegenote.pythonanywhere.com/ Prepared By: Jayanta Poudel

2 Digital Logic BIT

Unit-3
Simplification of Boolean Functions

Different forms of Boolean Algebra

1. Sum of Product (SOP)
This is an expression in which each term is a product term and all the product terms are
summed together.
a) Minimal SOP
An expression in which each product term consist of minimum numbers of variables.
E.g. XY+X’Y+XY’

b) Expanded SOP
An expression in which each product term consist of maximum numbers of variables.
E.g. XYZ+X’YZ+WXYZ

2. Product of Sum (POS)

This is an expression in which several sum terms are multiplied together.
a) Minimal POS
In this an expression in which there are minimum number of sum terms.
E.g. (X+Y) (X’+Y) (X+Y’)

b) Expanded POS
In this an expression in which there are maximum number of variables.
E.g. (X+Y+Z)٠(X’+Y’+Z’)٠(W+X+Y+Z)

Minterms or standard product

- Each row of a truth table can be associated with a minterm, which is a product (AND) of
all variables in the function, in direct or complemented form.
- A function with n variables has 2n minterms.
- A minterm has the property that it is equal to 1 on exactly one row of the truth table.

Maxterms or standard sums

- Each row of a truth table is also associated with a maxterm, which is a sum (OR) of all
the variables in the function, in direct or complemented form.
- A function with n variables has 2n maxterms
- A maxterm has the property that it is equal to 0 on exactly one row of the truth table.

https://collegenote.pythonanywhere.com/ Prepared By: Jayanta Poudel

3 Digital Logic BIT

Note: Each maxterm is the complement of its corresponding minterm and vice versa.

Expressing Boolean function by sum of minterms

A boolean function may be expressed algebraically from a given truth table by forming a
minterm for each combination of the variables which produces a 1 in the function and then
taking the OR of all those terms.

Finding Complement of Boolean function by sum of minterms

The complement of a Boolean function can be obtained from the truth table by forming a
minterm of each combination that produces a 0 in the function and then ORing those terms.

https://collegenote.pythonanywhere.com/ Prepared By: Jayanta Poudel

4 Digital Logic BIT

The Complement of f1 is written as:

Expressing Boolean Function by product of maxterms

A boolean function may be expressed algebraically from a given truth table by forming a
maxterm for each combination of the variables which produces a 0 in the function and then
taking the AND of all those terms.

Canonical and Standard forms

- Boolean functions expressed as a sum of minterms or product of maxterms are said to be
in canonical form.
- In an expression in canonical form, every variable appears in every term.
- The two canonical forms of Boolean algebra are basic forms that one obtain from reading
a function from the truth table. These forms are very seldom the ones with least number
of literals, because each minterm or maxterm must contain, by definition, all the
variables either complemented or uncomplemented.

- Another way to express Boolean functions is in standard form. In this configuration, the
terms that form the function may contain one, two or any number of literal.

https://collegenote.pythonanywhere.com/ Prepared By: Jayanta Poudel

5 Digital Logic BIT

- There are two types of standard forms: the sum of products and product of sums.
Sum of products: 𝐹1 = 𝑦 ′ + 𝑥𝑦 + 𝑥′𝑦𝑧′
Product of sums: 𝐹2 = 𝑥(𝑦 ′ + 𝑧)(𝑥 ′ + 𝑦 + 𝑧 ′ + 𝑤)

Expressing Boolean function as a sum of minterms and product of maxterms using

Boolean algebra:
- To express the Boolean function as a sum of minterms, expand the Boolean function into
a sum of products. Each term is then inspected to see if it contains all the variables. If it
misses one or more variables, it is ANDed with an expression such as x + x', where x is
one of the missing variables.

- To express the Boolean function as a product of maxterms , expand the Boolean function
into a product of sums. This may be done by using the distributive law, x + yz = (x + y)(x
+ z). Then any missing variable x in each OR term is ORed with xx'.

Q. Express the Boolean function 𝑭 = 𝑨 + 𝑩′𝑪 in a sum of minterms.

Soln:
The function has three variables, the first term 𝐴 is missing two variables 𝐵 and 𝐶.
Inclusion of variable 𝐵: 𝐴 = 𝐴(𝐵 + 𝐵′ ) = 𝐴𝐵 + 𝐴𝐵′
Inclusion of variable of 𝐶: 𝐴 = 𝐴𝐵(𝐶 + 𝐶 ′ ) + 𝐴𝐵′ (𝐶 + 𝐶 ′ )
= 𝐴𝐵𝐶 + 𝐴𝐵𝐶 ′ + 𝐴𝐵′ 𝐶 + 𝐴𝐵′𝐶′
The second term 𝐵′𝐶 is missing one variable 𝐴.
Inclusion of variable 𝐴: 𝐵′ 𝐶 = 𝐵′ 𝐶 (𝐴 + 𝐴′ ) = 𝐴𝐵′ 𝐶 + 𝐴′𝐵′𝐶
Combining all terms
𝐹 = 𝐴 + 𝐵′𝐶
= 𝐴𝐵𝐶 + 𝐴𝐵𝐶 ′ + 𝑨𝑩′ 𝑪 + 𝐴𝐵′ 𝐶′ + 𝑨𝑩′ 𝑪 + 𝐴′𝐵′𝐶
𝐹 = 𝐴′ 𝐵′ 𝐶 + 𝐴𝐵′ 𝐶 ′ + 𝐴𝐵′ 𝐶 + 𝐴𝐵𝐶 ′ + 𝐴𝐵𝐶
= 𝑚1 + 𝑚4 + 𝑚5 + 𝑚6 + 𝑚7
𝐹(𝐴, 𝐵, 𝐶 ) = ∑(1, 4, 5,6 ,7)

Q. Express the Boolean function 𝑭 = 𝒙𝒚 + 𝒙′𝒛 in a product of maxterm form.

Soln:
Converting the function into OR terms using distributive law:

Including missing with each term:

Combining and avoiding the repeated terms:

https://collegenote.pythonanywhere.com/ Prepared By: Jayanta Poudel

6 Digital Logic BIT

Conversion between canonical forms

𝒎′𝒋 = 𝑴𝒋

Consider a function
𝐹(𝐴, 𝐵, 𝐶 ) = ∑(1, 4, 5, 6,7)
Taking the complement of 𝐹
𝐹 ′ (𝐴, 𝐵, 𝐶 ) = ∑(0, 2, 3) = 𝑚0 + 𝑚2 + 𝑚3
Taking the complement of 𝐹 ′
𝐹 = (𝑚0 + 𝑚2 + 𝑚3 )′ = 𝑚0′ ∙ 𝑚2′ ∙ 𝑚3′ = 𝑀0 𝑀2 𝑀3 = ∏(0, 2, 3)

Similarly,
𝐹(𝑥, 𝑦, 𝑧) = ∑(1, 3, 6,7) ⟷ 𝐹 (𝑥, 𝑦, 𝑧) = ∏(0, 2, 4,5)

Karnaugh Map (K-Map)

- Karnaugh map or K-map is a map of a function used in a technique used for
minimization or simplification of a Boolean expression.
- Booleans expression can be simplified using Boolean algebraic theorems but there are no
specific rules to make the most simplified expression. However, K-map can easily
minimize the terms of a Boolean function.
- Unlike an algebraic method, K-map is a pictorial method and it does not need any Boolean
algebraic theorems.
- K-map is basically a diagram made up of squares. Each of these squares represents a min-
term of the variables. If n = number of variables then the number of squares in its K-map
will be 2n. K-map is made using the truth table.
- Karnaugh map can produce Sum of product (SOP) or product of Sum(POS) expression
considering which of the two (0,1) outputs are being grouped in it. The grouping of 0’s
result in Product of Sum expression & the grouping of 1’s result in Sum of Product
expression.

Rules of minimization in K-Map

1. While grouping, you can make groups of 2n number where n=0, 1, 2, 3…
2. You can either make groups of 1’s or 0’s but not both.
3. Grouping of 1’s lead to Sum of Product form and Grouping of 0’s lead to Product of Sum
form.
4. While grouping, the groups of 1’s should not contain any 0 and the group of 0’s should not
contain any 1.
5. The function output for 0’s grouping should be complemented as 𝐹′.

https://collegenote.pythonanywhere.com/ Prepared By: Jayanta Poudel

7 Digital Logic BIT

Rules for grouping 1’s (Sum of Product form):

 Groups may not include any cell containing a zero.

 Groups may be horizontal or vertical, but not diagonal.

 Groups must contain 1, 2, 4, 8, or in general 2n cells. That is if n = 1, a group will contain

two 1's since 21 = 2. If n = 2, a group will contain four 1's since 22 = 4.

 Each group should be as large as possible.

https://collegenote.pythonanywhere.com/ Prepared By: Jayanta Poudel

8 Digital Logic BIT

 Each cell containing a one must be in at least one group.

 Groups may overlap.

 Groups may wrap around the table. The leftmost cell in a row may be grouped with the
rightmost cell and the top cell in a column may be grouped with the bottom cell.

 There should be as few groups as possible, as long as this does not contradict any of the
previous rules.

https://collegenote.pythonanywhere.com/ Prepared By: Jayanta Poudel

9 Digital Logic BIT

Two Variable Map

There are four minterms for two variables; hence the map consists of fours squares, one of
each minterm.

Fig: Two variable map

Q. Simplify the Boolean function 𝑭 = 𝒙′ 𝒚 + 𝒙𝒚′ + 𝒙𝒚 using K-Map.

Soln:
K-map for given function:

So, after simplification, 𝐹 = 𝑋 + 𝑌

Three Variable Map

- There are eight minterms for three variables, i.e. the map consist of eight squares.
- Minterms are not arranged in binary sequence but in a sequence similar to gray
code/reflected code.

Fig: Three variable map

https://collegenote.pythonanywhere.com/ Prepared By: Jayanta Poudel

10 Digital Logic BIT

Q. Simplify the Boolean function, 𝑭 = 𝑿′ 𝒀𝒁 + 𝑿𝒀′ 𝒁′ + 𝑿𝒀𝒁 + 𝑿𝒀𝒁′ using K-Map.

Soln:
K-map for given function:

After simplification, 𝐹 = 𝑌𝑍 + 𝑋𝑍′

Q. Simplify the Boolean function, 𝑭 = 𝑨′ 𝑪 + 𝑨′ 𝑩 + 𝑨𝑩′ 𝑪 + 𝑩𝑪 using K-Map.

Soln:
𝐹 = 𝐴′ 𝐶 + 𝐴′ 𝐵 + 𝐴𝐵′ 𝐶 + 𝐵𝐶 = 𝑨′ 𝑩𝑪 + 𝐴′ 𝐵′ 𝐶 + 𝑨′ 𝑩𝑪 + 𝐴′ 𝐵𝐶 ′ + 𝐴𝐵′ 𝐶 + 𝐴𝐵𝐶 + 𝑨′𝑩𝑪
K-map for given function:

After simplification, 𝐹 = 𝐶 + 𝐴′𝐵

Q. Simplify the Boolean function: 𝑭(𝑿, 𝒀, 𝒁) = ∑(𝟎, 𝟐, 𝟒, 𝟓, 𝟔) using three variable K-map.
Soln:
K-map for given function:

After simplification, 𝐹 = 𝑍 ′ + 𝑋𝑌′

https://collegenote.pythonanywhere.com/ Prepared By: Jayanta Poudel

11 Digital Logic BIT

Four Variable Map

The map for Boolean function of four binary variables has 16 minterms and the squares
assigned to each.

Fig: Four variable map

- The rows and columns are numbered in a reflected code sequence, with only one digit
changing value between two adjacent rows and columns.
- The minterm corresponding to each square can be obtained from the concatenation of the
row number with the column number.

Q. Simplify the Boolean function 𝑭 = 𝑨′ 𝑩′ 𝑪′ + 𝑩′ 𝑪𝑫′ + 𝑨′ 𝑩𝑪𝑫′ + 𝑨𝑩′ 𝑪′ using K-map.

Soln:
𝐹 = 𝐴′ 𝐵′ 𝐶 ′ + 𝐵′ 𝐶𝐷′ + 𝐴′ 𝐵𝐶𝐷′ + 𝐴𝐵′𝐶
= 𝐴′𝐵′𝐶′(𝐷 + 𝐷′) + 𝐵′𝐶𝐷(𝐴 + 𝐴′) + 𝐴′𝐵𝐶𝐷′ + 𝐴𝐵′𝐶′(𝐷 + 𝐷′)
= 𝐴′𝐵′𝐶′𝐷 + 𝐴′𝐵′𝐶′𝐷′ + 𝐴𝐵′𝐶𝐷 + 𝐴′ 𝐵′𝐶𝐷 + 𝐴′𝐵𝐶𝐷′ + 𝐴𝐵′𝐶′𝐷 + 𝐴𝐵′𝐶′𝐷′
K-map for given function:

After simplification, 𝐹 = 𝐵′ 𝐷′ + 𝐵′ 𝐶 ′ + 𝐴′𝐶𝐷′

https://collegenote.pythonanywhere.com/ Prepared By: Jayanta Poudel

12 Digital Logic BIT

Q. Simplify the Boolean function 𝑭(𝑾, 𝑿, 𝒀, 𝒁) = ∑(𝟎, 𝟏, 𝟐, 𝟒, 𝟓, 𝟔, 𝟖, 𝟗, 𝟏𝟐, 𝟏𝟑, 𝟏𝟒).

Soln:
K-map for given function:

After simplification, 𝐹 = 𝑌 ′ + 𝑊 ′ 𝑍 ′ + 𝑋𝑍′

Product of sum simplification

- All previous examples are in sum-of-products form.
- To obtain the product-of-sum form:
 Simplify 𝐹 ′ in the form of sum of products. [If we mark the empty squares by 0’s
and combine them into valid rectangles, we obtained a simplified expression of
the complement of the function, i.e. of 𝐹 ′ ]
 Apply DeMorgan's theorem 𝐹 = (𝐹 ′ ) ′
 𝑭′ : sum of products ⇒ 𝑭 : product of sums

Q. Simplify the Boolean function: 𝑭 = ∑(𝟎, 𝟏, 𝟐, 𝟓, 𝟖, 𝟗, 𝟏𝟎) in (a) sum of product (SOP)
and (b) product of sum (POS).
Soln:
(a) Sum of products simplification (b) Product of sums simplification

𝐹 = 𝐵′ 𝐷′ + 𝐵′ 𝐶 ′ + 𝐴′𝐶′𝐷 𝐹 ′ = 𝐴𝐵 + 𝐶𝐷 + 𝐵𝐷′
So, 𝐹 = (𝐴′ + 𝐵′ )(𝐶 ′ + 𝐷′ )(𝐵′ + 𝐷)

https://collegenote.pythonanywhere.com/ Prepared By: Jayanta Poudel

13 Digital Logic BIT

Q. Simply the Boolean function 𝑭(𝑨, 𝑩, 𝑪, 𝑫) = ∏(𝟎, 𝟏, 𝟐, 𝟑, 𝟒, 𝟏𝟎, 𝟏𝟏) in POS.

Soln:
K-map for given function:

From Map,
𝐹′ = 𝐴′ 𝐵′ + 𝐵′ 𝐶 + 𝐴′𝐶′𝐷′

So, 𝐹 = (𝐴 + 𝐵)(𝐵 + 𝐶 ′ )(𝐴 + 𝐶 + 𝐷)

Don’t Care Conditions

- There are certain situations where a function may not be completely specified, meaning
there may be some input combination that are undefined for the function.
- Real circuits don’t always need to have an output defined for every possible input.
- The unused combinations is known as don’t care conditions and can be used on the map
to provide further simplification of the boolean expression.
- It should be realized that a don’t care minterm is a combination of variables whose logical
value is not specified. It cannot be marked with a 1 or, 0 in the map as it is not specified
as 0 or 1. To distinguish the don’t care condition from 1’s and 0’s, an X is used. Thus, an
X inside a square in the map indicates that we don’t care whether the value of 0 or 1 is
assigned to 𝐹 for the particular minterms.

Q. Simplify 𝑭(𝒘, 𝒙, 𝒚, 𝒛) = ∑(𝟏, 𝟑, 𝟕, 𝟏𝟏, 𝟏𝟓) which has the don’t care conditions
𝒅(𝒘, 𝒙, 𝒚, 𝒛) = ∑(𝟎, 𝟐, 𝟓).
Soln:

https://collegenote.pythonanywhere.com/ Prepared By: Jayanta Poudel

14 Digital Logic BIT

Q. 𝑭(𝑨, 𝑩, 𝑪, 𝑫) = ∏(𝟎, 𝟏, 𝟑, 𝟕, 𝟖, 𝟏𝟐) and ∏ 𝒅(𝟓, 𝟏𝟎, 𝟏𝟑, 𝟏𝟒). Obtain SOP and POS.
Soln:

For POS: For SOP:

𝐶𝐷 𝐶𝐷
𝐴𝐵 𝐶′𝐷′ 𝐶′𝐷 𝐶𝐷 𝐶𝐷′ 𝐴𝐵 𝐶′𝐷′ 𝐶′𝐷 𝐶𝐷 𝐶𝐷′

𝐴′𝐵′ 0 0 0 𝐴′𝐵′ 1

𝐴′𝐵 X 0 𝐴′𝐵 1 X 1

𝐴𝐵 0 X X 𝐴𝐵 X 1 X

𝐴𝐵′ 0 X 𝐴𝐵′ 1 1 X

𝐹 = (𝐴′ 𝐷 + 𝐴𝐷′ + 𝐵′𝐶′𝐷′)′ 𝐹 = 𝐶𝐷′ + 𝐴𝐷 + 𝐴′𝐵𝐶′

= (𝐴 + 𝐷′ )(𝐴′ + 𝐷)(𝐵 + 𝐶 + 𝐷)

NAND and NOR Implementation

Why NAND and NOR implementation?
- Digital circuits are frequently constructed with NAND/NOR rather than with AND/OR
gates.
- NAND and NOR gates are easier to fabricate with electronic components than AND/OR.
- Cheaper (lower cost) and faster(less delay).
- Any Boolean function can be constructed using only NAND or only NOR gates. That’s
why NAND and NOR are known as universal gates.

Two graphic symbols for NAND gate:

Two graphic symbols for NOR gate:

https://collegenote.pythonanywhere.com/ Prepared By: Jayanta Poudel

15 Digital Logic BIT

NAND Implementation
The implementation of a Boolean function with NAND gates requires that the function be
simplified in the sum of products form.
E.g. Implementation of 𝐹 = 𝐴𝐵 + 𝐶𝐷 + 𝐸 by NAND gate only.

Fig: Three ways to implement 𝑭 = 𝑨𝑩 + 𝑪𝑫 + 𝑬

Rules for obtaining the NAND logic diagram from a Boolean function:
1) Simplify the function and express it in sum of products.
2) Draw a NAND gate for each product term of the function that has at least two literals.
The inputs to each NAND gate are the literals of the term. This constitutes a group of
first-level gates.
3) Draw a single NAND gate (using the AND-invert or invert-OR graphic symbol) in the
second level, with inputs coming from outputs of the 1st level.
4) A term with a single literal requires an inverter in the first level or may be
complemented and applied as an input to the second-level NAND gate.

Note: If we simplify the function combining 0’s in a map, we obtain the simplified
expression of the complement of the function in sum of product. The complement of the
function can then be implemented with two levels of NAND gates using the rules stated
above. If the normal output is desired, it would be necessary to insert a one-input NAND
gate.

https://collegenote.pythonanywhere.com/ Prepared By: Jayanta Poudel

16 Digital Logic BIT

Q. Implement the following function with NAND gates.

𝑭(𝒙, 𝒚, 𝒛) = ∑(𝟎, 𝟔)
Soln:

In Fig(c): If output F is required, it is necessary to add a one input NAND gate to invert the
function. This gives a three-level implementation.

NOR Implementation
The implementation of a Boolean function with NOR gates requires that the function be
simplified in product of sums form.
E.g. Implementation of the function 𝐹 = (𝐴 + 𝐵)(𝐶 + 𝐷)𝐸

Fig: Three ways to implement 𝑭 = (𝑨 + 𝑩)(𝑪 + 𝑫)𝑬

https://collegenote.pythonanywhere.com/ Prepared By: Jayanta Poudel

17 Digital Logic BIT

Rules for obtaining the NAND logic diagram from a Boolean function:
1) Simplify the function and express it in POS.
2) Draw a NOR gate for each sum term of the function that has at least two literals.
3) Draw a single NOR gate (using the OR-invert or invert-AND) in the second level, with
inputs coming from outputs of the 1st level.
4) A term with a single literal requires a one input NOR or inverter gate in the first level
or may be complemented and applied as an input to the second-level NOR gate.

A second way to implement a function with NOR gates would be to use the expression for
the complement of the function of the function in product of sums. This will give a two-level
implementation for 𝐹′ and a three-level implementation if the normal output 𝐹 is required.
To obtain the simplified product of sums from a map, it is necessary to combine the 0’s in the
map and then complement the function. To obtain the simplified product of sums expression
for the complement of the function, it is necessary to combine the 1’s in the map and then
complement the function.

Q. Implement the following function with NOR gates.

𝑭(𝒙, 𝒚, 𝒛) = ∑(𝟎, 𝟔)
n
Sol :

Combine 0’s in map: Combine 1’s in map:

Sum of product: 𝐹 ′ = 𝑥 ′ 𝑦 + 𝑥𝑦 ′ + 𝑧 Sum of product: 𝐹 = 𝑥 ′ 𝑦 ′ 𝑧 ′ + 𝑥𝑦𝑧′
Product of sums: 𝐹 = (𝑥 + 𝑦 ′ )(𝑥 ′ + 𝑦)𝑧′ Product of sums: 𝐹 ′ = (𝑥 + 𝑦 + 𝑧)(𝑥 ′ + 𝑦 ′ + 𝑧)

https://collegenote.pythonanywhere.com/ Prepared By: Jayanta Poudel

18 Digital Logic BIT

Q. Implement the following function with NAND and NOR gates. Use only four gates.
𝑭 = 𝒘′ 𝒙𝒛 + 𝒘′ 𝒚𝒛 + 𝒙′ 𝒚𝒛′ + 𝒘𝒙𝒚′ 𝒛 and 𝒅 = 𝒘𝒚𝒛
Soln:

NAND implementation

NOR implementation

https://collegenote.pythonanywhere.com/ Prepared By: Jayanta Poudel

19 Digital Logic BIT

References:

- M. Morris Mano, “Digital Logic & Computer Design”

https://collegenote.pythonanywhere.com/ Prepared By: Jayanta Poudel