UNIT 2

BOOLEAN ALGEBRA AND LOGIC FUNCTIONS

Boolean Algebra is used to analyze and simplify the digital (logic) circuits. It uses only the
binary numbers i.e. 0 and 1. It is also called as Binary Algebra or logical Algebra. Boolean
algebra was invented by George Boole in 1854.

Rule in Boolean Algebra

Following are the important rules used in Boolean algebra.

 Variable used can have only two values. Binary 1 for HIGH and Binary 0 for LOW.
 Complement of a variable is represented by an overbar (-). Thus, complement of
variable B is represented as . Thus if B = 0 then = 1 and B = 1 then = 0.
 ORing of the variables is represented by a plus (+) sign between them. For example
ORing of A, B, C is represented as A + B + C.
 Logical ANDing of the two or more variable is represented by writing a dot between
them such as A.B.C. Sometime the dot may be omitted like ABC.

Boolean Laws

There are six types of Boolean Laws.

Commutative law

Any binary operation which satisfies the following expression is referred to as commutative
operation.

Commutative law states that changing the sequence of the variables does not have any effect
on the output of a logic circuit.

Associative law

This law states that the order in which the logic operations are performed is irrelevant as
their effect is the same.

Distributive law

Distributive law states the following condition.

AND law

These laws use the AND operation. Therefore they are called as AND laws.

OR law

These laws use the OR operation. Therefore they are called as OR laws.

INVERSION law

This law uses the NOT operation. The inversion law states that double inversion of a
variable results in the original variable itself.

Important Boolean Theorems

Following are few important boolean Theorems.

Boolean function/theorems Description

Boolean Functions and Expressions, K-Map and NAND

Boolean Functions
Gates realization

De Morgan's Theorem 1 and Theorem 2

De Morgan's Theorems

Logic gate
Logic gates are the basic building blocks of any digital system. It is an electronic circuit
having one or more than one input and only one output. The relationship between the input
and the output is based on a certain logic. Based on this, logic gates are named as AND
gate, OR gate, NOT gate etc.

AND Gate

A circuit which performs an AND operation is shown in figure. It has n input (n >= 2) and
one output.
Logic diagram

Truth Table

OR Gate

A circuit which performs an OR operation is shown in figure. It has n input (n >= 2) and one
output.

Logic diagram

Truth Table
NOT Gate

NOT gate is also known as Inverter. It has one input A and one output Y.

Logic diagram

Truth Table

NAND Gate

A NOT-AND operation is known as NAND operation. It has n input (n >= 2) and one
output.

Logic diagram
Truth Table

NOR Gate

A NOT-OR operation is known as NOR operation. It has n input (n >= 2) and one output.

Logic diagram

Truth Table

XOR Gate

XOR or Ex-OR gate is a special type of gate. It can be used in the half adder, full adder and
subtractor. The exclusive-OR gate is abbreviated as EX-OR gate or sometime as X-OR gate.
It has n input (n >= 2) and one output.
Logic diagram

Truth Table

XNOR Gate

XNOR gate is a special type of gate. It can be used in the half adder, full adder and
subtractor. The exclusive-NOR gate is abbreviated as EX-NOR gate or sometime as X-NOR
gate. It has n input (n >= 2) and one output.

Logic diagram

Truth Table
Simplification Using Algebraic Functions

In this approach, one Boolean expression is minimized into an equivalent expression by

applying Boolean identities.

Problem 1

Minimize the following Boolean expression using Boolean identities −

F(A,B,C)=A′B+BC′+BC+AB′C′

Solution

Given,F(A,B,C)=A′B+BC′+BC+AB′C′
Or,F(A,B,C)=A′B+(BC′+BC′)+BC+AB′C′
[By idempotent law, BC’ = BC’ + BC’]
Or,F(A,B,C)=A′B+(BC′+BC)+(BC′+AB′C′))
Or,F(A,B,C)=A′B+B(C′+C)+C′(B+AB′)
[By distributive laws]
Or,F(A,B,C)=A′B+B.1+C′(B+A)
[ (C' + C) = 1 and absorption law (B + AB')= (B + A)]
Or,F(A,B,C)=A′B+B+C′(B+A)
[ B.1 = B ]
Or,F(A,B,C)=B(A′+1)+C′(B+A)
Or,F(A,B,C)=B.1+C′(B+A)
[ (A' + 1) = 1 ]
Or,F(A,B,C)=B+C′(B+A)
[ As, B.1 = B ]
Or,F(A,B,C)=B+BC′+AC′
Or,F(A,B,C)=B(1+C′)+AC′
Or,F(A,B,C)=B.1+AC′′
[As, (1 + C') = 1]
Or,F(A,B,C)=B+AC′
[As, B.1 = B]
So,F(A,B,C)=B+AC′is the minimized form.

Problem 2

Minimize the following Boolean expression using Boolean identities −

F(A,B,C)=(A+B)(A+C)

Solution

Given, F(A,B,C)=(A+B)(A+C)
Or, F(A,B,C)=A.A+A.C+B.A+B.C [Applying distributive Rule]
Or, F(A,B,C)=A+A.C+B.A+B.C [Applying Idempotent Law]
Or, F(A,B,C)=A(1+C)+B.A+B.C [Applying distributive Law]
Or, F(A,B,C)=A+B.A+B.C [Applying dominance Law]
Or, F(A,B,C)=(A+1).A+B.C [Applying distributive Law]
Or, F(A,B,C)=1.A+B.C [Applying dominance Law]
Or, F(A,B,C)=A+B.C [Applying dominance Law]
So, F(A,B,C)=A+BC is the minimized form.

Karnaugh Maps

The Karnaugh map (K–map), introduced by Maurice Karnaughin in 1953, is a grid-like

representation of a truth table which is used to simplify boolean algebra expressions. A
Karnaugh map has zero and one entries at different positions. It provides grouping together
Boolean expressions with common factors and eliminates unwanted variables from the
expression. In a K-map, crossing a vertical or horizontal cell boundary is always a change of
only one variable.

Example 1

An arbitrary truth table is taken below −

A B A operation B

0 0 W

0 1 X

1 0 Y
 1 1 Z

Now we will make a k-map for the above truth table −

Example 2

Now we will make a K-map for the expression − AB+ A’B’

Simplification Using K-map

K-map uses some rules for the simplification of Boolean expressions by combining together
adjacent cells into single term. The rules are described below −
Rule 1 − Any cell containing a zero cannot be grouped.

Wrong grouping
Rule 2 − Groups must contain 2n cells (n starting from 1).
 Wrong grouping
Rule 3 − Grouping must be horizontal or vertical, but must not be diagonal.

Wrong diagonal grouping

Proper vertical grouping

Proper horizontal grouping

Rule 4 − Groups must be covered as largely as possible.
 Insufficient grouping

Proper grouping
Rule 5 − If 1 of any cell cannot be grouped with any other cell, it will act as a group itself.

Proper grouping
Rule 6 − Groups may overlap but there should be as few groups as possible.

Proper grouping
Rule 7 − The leftmost cell/cells can be grouped with the rightmost cell/cells and the topmost
cell/cells can be grouped with the bottommost cell/cells.

Proper grouping

Problem

Minimize the following Boolean expression using K-map −

F(A,B,C)=A′BC+A′BC′+AB′C′+AB′C

Solution

Each term is put into k-map and we get the following −

K-map for F (A, B, C)

Now we will group the cells of 1 according to the rules stated above −

K-map for F (A, B, C)

We have got two groups which are termed as A′BA′B and AB′AB′. Hence, F(A,B,C)=A
′B+AB′=A⊕B. It is the minimized form.

Boolean functions can be represented by using NAND gates and also by using K-map
(Karnaugh map) method. We can standardize the Boolean expressions by using by two
standard forms.

SOP form – Sum Of Products form

POS form – Product Of Sums form

Standardization of Boolean equations will make the implementation, evolution and

simplification easier and more systematic.

Sum of Product (SOP) Form

The sum-of-products (SOP) form is a method (or form) of simplifying the Boolean
expressions of logic gates. In this SOP form of Boolean function representation, the variables
are operated by AND (product) to form a product term and all these product terms are ORed
(summed or added) together to get the final function.

A sum-of-products form can be formed by adding (or summing) two or more product terms
using a Boolean addition operation. Here the product terms are defined by using the AND
operation and the sum term is defined by using OR operation.

The sum-of-products form is also called as Disjunctive Normal Form as the product terms are
ORed together and Disjunction operation is logical OR. Sum-of-products form is also called
as Standard SOP.

SOP form representation is most suitable to use them in FPGA (Field Programmable Gate
Arrays).

Examples

AB + ABC + CDE

(AB) ̅ + ABC + CD E ̅

SOP form can be obtained by

  Writing an AND term for each input combination, which produces HIGH output.
 Writing the input variables if the value is 1, and write the complement of the variable if
its value is 0.
 OR the AND terms to obtain the output function.

Ex: Boolean expression for majority function F = A’BC + AB’C + ABC ‘ + ABC

Truth table:

Now write the input variables combination with high output. F = AB + BC + AC.

Checking

By Idempotence law, we know that

([ABC + ABC)] + ABC) = (ABC + ABC) = ABC

Now the function F = A’BC + AB’C + ABC ‘ + ABC

= A’BC + AB’C + ABC’ + ([ABC + ABC)] + ABC)

= (ABC + ABC ‘) + (ABC + AB’C) + (ABC + A’BC)

= AB (C + C ‘) + A (B + B’) C + (A + A’) BC

= AB + BC + AC.

Product of Sums (POS) Form

The product of sums form is a method (or form) of simplifying the Boolean expressions of
logic gates. In this POS form, all the variables are ORed, i.e. written as sums to form sum
terms.

All these sum terms are ANDed (multiplied) together to get the product-of-sum form. This
form is exactly opposite to the SOP form. So this can also be said as “Dual of SOP form”.

Here the sum terms are defined by using the OR operation and the product term is defined by
using AND operation. When two or more sum terms are multiplied by a Boolean OR
operation, the resultant output expression will be in the form of product-of-sums form or POS
form.

The product-of-sums form is also called as Conjunctive Normal Form as the sum terms are
ANDed together and Conjunction operation is logical AND. Product-of-sums form is also
called as Standard POS.

Examples

(A+B) * (A + B + C) * (C +D)

(A+B) ̅ * (C + D + E ̅)

POS form can be obtained by

 Writing an OR term for each input combination, which produces LOW output.
 Writing the input variables if the value is 0, and write the complement of the variable if
its value is 1.
 AND the OR terms to obtain the output function.

Ex: Boolean expression for majority function F = (A + B + C) (A + B + C ‘) (A + B’ + C)

(A’ + B + C)
Now write the input variables combination with high output. F = AB + BC + AC.

Checking

By Idempotence law, we know that

[(A + B + C) (A + B + C)] (A + B + C) = [(A + B + C)] (A + B + C) = (A + B + C)

Now the function

F = (A + B) (B + C) (A + C)

= (A + B + C) (A + B + C ‘) (A + B’ + C) (A’ + B + C)

= [(A + B + C) (A + B + C)] (A + B + C) (A + B + C ‘) (A + B’ + C) (A’ + B + C)

= [(A + B + C) (A + B + C ‘)] [(A + B + C) (A’ + B + C)] [(A + B + C) (A + B’ + C)]

= [(A + B) + (C * C ‘)] [(B + C) + (A * A’)] [(A + C) + (B * B’)]

= [(A + B) + 0] [(B + C) + 0] [(A + C) + 0] = (A + B) (B + C) (A + C)

Canonical Form (Standard SOP and POS Form)

Any Boolean function that is expressed as a sum of minterms or as a product of max terms is
said to be in its “canonical form”.

It mainly involves in two Boolean terms, “minterms” and “maxterms”.

When the SOP form of a Boolean expression is in canonical form, then each of its product
term is called ‘minterm’. So, the canonical form of sum of products function is also known as
“minterm canonical form” or Sum-of-minterms or standard canonical SOP form.

Similarly, when the POS form of a Boolean expression is in canonical form, then each of its
sum term is called ‘maxterm’. So, the canonical form of product of sums function is also
known as “maxterm canonical form or Product-of sum or standard canonical POS form”.

Min terms

A minterm is defined as the product term of n variables, in which each of the n variables will
appear once either in its complemented or un-complemented form. The min term is denoted
as mi where i is in the range of 0 ≤ i < 2ⁿ.

A variable is in complemented form, if its value is assigned to 0, and the variable is un-
complimented form, if its value is assigned to 1.

For a 2-variable (x and y) Boolean function, the possible minterms are:

x’y’, x’y, xy’ and xy.

For a 3-variable (x, y and z) Boolean function, the possible minterms are:

x’y’z’, x’y’z, x’yz’, x’yz, xy’z’, xy’z, xyz’ and xyz.

 1 – Minterms = minterms for which the function F = 1.

 0 – Minterms = minterms for which the function F = 0.

Any Boolean function can be expressed as the sum (OR) of its 1- min terms. The
representation of the equation will be

 F(list of variables) = Σ(list of 1-min term indices)

Ex: F (x, y, z) = Σ (3, 5, 6, 7)

The inverse of the function can be expressed as a sum (OR) of its 0- min terms. The
representation of the equation will be

 F(list of variables) = Σ(list of 0-min term indices)

Ex: F’ (x, y, z) = Σ (0,1, 2, 4)

Examples of canonical form of sum of products expressions (min term canonical form):

i) Z = XY + XZ′

ii) F = XYZ′ + X′YZ + X′YZ′ + XY′Z + XYZ

In standard SOP form, the maximum possible product terms for n number of variables are
given by 2ⁿ. So, for 2 variable equations, the product terms are 22 = 4. Similarly, for 3
variable equations, the product terms are 23 = 8.

Max terms

A max term is defined as the product of n variables, within the range of 0 ≤ i < 2ⁿ. The max
term is denoted as Mi. In max term, each variable is complimented, if its value is assigned to
1, and each variable is un-complimented if its value is assigned to 0.

For a 2-variable (x and y) Boolean function, the possible max terms are:

x + y, x + y’, x’ + y and x’ + y’.

For a 3-variable (x, y and z) Boolean function, the possible maxterms are:

x + y + z, x + y + z’, x + y’ + z, x + y’ + z’, x’ + y + z, x’ + y + z’, x’ + y’ + z and x’ + y’ +

z’.

 1 – Max terms = max terms for which the function F = 1.

 0 – max terms = max terms for which the function F = 0.

Any Boolean function can be expressed the product (AND) of its 0 – max terms. The
representation of the equation will be

 F(list of variables) = Π (list of 0-max term indices)

Ex: F (x, y, z) = Π (0, 1, 2, 4)

The inverse of the function can be expressed as a product (AND) of its 1 – max terms. The
representation of the equation will be

 F(list of variables) = Π (list of 1-max term indices)

Ex: F’ (x, y, z) = Π (3, 5, 6, 7)

Examples of canonical form of product of sums expressions (max term canonical form):

i. Z = (X + Y) (X + Y′)

ii. F = (X′ + Y + Z′) (X′ + Y + Z) (X′ + Y′ + Z′)

In standard POS form, the maximum possible sum terms for n number of variables are given
by 2ⁿ. So, for 2 variable equations, the sum terms are 22 = 4. Similarly, for 3 variable
equations, the sum terms are 23 = 8.

Table for 2n min terms and 2n max terms

The below table will make you understand about the representation of the mean terms and
max terms of 3 variables.

Conversions of Canonical Forms

We can represent the one canonical formed equation in other canonical form i.e. we can
represent the SOP form of equation in POS form and POS form equation in SOP form. To
convert the canonical equations, we interchange the Σ and Π symbols after listing out the
index numbers of the equations, which are excluded from the original form of equation.

The important thing to remember about Boolean functions is that, the SOP and POS forms
are Duals to each other. There are 2 steps to follow to convert the canonical form of the
equations. They are
Step 1: Interchanging the operational symbols, Σ and Π in the equation.

Step 2: Use the De Morgan’s principle of Duality to the index numbers of the Boolean
function or writing the indexes of the terms that are not presented in the given form of
equation.

Conversion of SOP form to POS form

To convert the SOP form into POS form, first we should change the Σ to Π and then write the
numeric indexes of missing variables of the given Boolean function.

Example:

The SOP function

F = ∑ A, B, C (0, 2, 3, 5, 7) = A’ B’ C’ + A B’ C’ + A B’ C + ABC’ + ABC is written in

POS form by

Step 1: changing the operational sign to Π

Step 2: writing the missing indexes of the terms, 001, 100 and 110. Now write the sum form
for these noted terms.

001 = (A + B + C) 100 = (A + B’ + C’) 110 = (A + B’ + C’)

Writing down the new equation in the form of POS form,

F = Π A, B, C (1, 4, 6) = (A + B + C) * (A + B’ + C’) * (A + B’ + C’)

K-Maps for 2 to 5 Variables

K-Map method is most suitable for minimizing Boolean functions of 2 variables to 5

variables. Now, let us discuss about the K-Maps for 2 to 5 variables one by one.

2 Variable K-Map

The number of cells in 2 variable K-map is four, since the number of variables is two. The
following figure shows 2 variable K-Map.
  There is only one possibility of grouping 4 adjacent min terms.
 The possible combinations of grouping 2 adjacent min terms are {(m 0, m1), (m2, m3),
(m0, m2) and (m1, m3)}.

3 Variable K-Map

The number of cells in 3 variable K-map is eight, since the number of variables is three. The
following figure shows 3 variable K-Map.

 There is only one possibility of grouping 8 adjacent min terms.

 The possible combinations of grouping 4 adjacent min terms are {(m 0, m1, m3, m2),
(m4, m5, m7, m6), (m0, m1, m4, m5), (m1, m3, m5, m7), (m3, m2, m7, m6) and (m2, m0, m6,
m4)}.
 The possible combinations of grouping 2 adjacent min terms are {(m 0, m1), (m1, m3),
(m3, m2), (m2, m0), (m4, m5), (m5, m7), (m7, m6), (m6, m4), (m0, m4), (m1, m5), (m3, m7)
and (m2, m6)}.
 If x=0, then 3 variable K-map becomes 2 variable K-map.

4 Variable K-Map

The number of cells in 4 variable K-map is sixteen, since the number of variables is four.
The following figure shows 4 variable K-Map.
  There is only one possibility of grouping 16 adjacent min terms.
 Let R1, R2, R3 and R4 represents the min terms of first row, second row, third row and
fourth row respectively. Similarly, C1, C2, C3 and C4 represents the min terms of first
column, second column, third column and fourth column respectively. The possible
combinations of grouping 8 adjacent min terms are {(R 1, R2), (R2, R3), (R3, R4), (R4,
R1), (C1, C2), (C2, C3), (C3, C4), (C4, C1)}.

 If w=0, then 4 variable K-map becomes 3 variable K-map.

5 Variable K-Map

The number of cells in 5 variable K-map is thirty-two, since the number of variables is 5.
The following figure shows 5 variable K-Map.

 There is only one possibility of grouping 32 adjacent min terms.

 There are two possibilities of grouping 16 adjacent min terms. i.e., grouping of min
terms from m0 to m15 and m16 to m31.
 If v=0, then 5 variable K-map becomes 4 variable K-map.
In the above all K-maps, we used exclusively the min terms notation. Similarly, you can use
exclusively the Max terms notation.
Example

Let us simplify the following Boolean function, fW,X,Y,Z= WX’Y’ + WY + W’YZ’ using
K-map.

The given Boolean function is in sum of products form. It is having 4 variables W, X, Y &
Z. So, we require 4 variable K-map. The 4 variable K-map with ones corresponding to the
given product terms is shown in the following figure.

Here, 1s are placed in the following cells of K-map.

 The cells, which are common to the intersection of Row 4 and columns 1 & 2 are
corresponding to the product term, WX’Y’.

 The cells, which are common to the intersection of Rows 3 & 4 and columns 3 & 4
are corresponding to the product term, WY.

 The cells, which are common to the intersection of Rows 1 & 2 and column 4 are
corresponding to the product term, W’YZ’.

There are no possibilities of grouping either 16 adjacent ones or 8 adjacent ones. There are
three possibilities of grouping 4 adjacent ones. After these three groupings, there is no single
one left as ungrouped. So, we no need to check for grouping of 2 adjacent ones. The 4
variable K-map with these three groupings is shown in the following figure.
Here, we got three prime implicants WX’, WY & YZ’. All these prime implicants
are essential because of following reasons.

 Two ones (m8 & m9) of fourth row grouping are not covered by any other groupings.
Only fourth row grouping covers those two ones.

 Single one (m15) of square shape grouping is not covered by any other groupings.
Only the square shape grouping covers that one.

 Two ones (m2 & m6) of fourth column grouping are not covered by any other
groupings. Only fourth column grouping covers those two ones.

Therefore, the simplified Boolean function is

f = WX’ + WY + YZ’

Follow these rules for simplifying K-maps in order to get standard product of sums form.

 Select the respective K-map based on the number of variables present in the Boolean
function.

 If the Boolean function is given as product of Max terms form, then place the zeroes
at respective Max term cells in the K-map. If the Boolean function is given as
product of sums form, then place the zeroes in all possible cells of K-map for which
the given sum terms are valid.

 Check for the possibilities of grouping maximum number of adjacent zeroes. It

should be powers of two. Start from highest power of two and upto least power of
two. Highest power is equal to the number of variables considered in K-map and
least power is zero.
  Each grouping will give either a literal or one sum term. It is known as prime
implicant. The prime implicant is said to be essential prime implicant, if atleast
single ‘0’ is not covered with any other groupings but only that grouping covers.

 Note down all the prime implicants and essential prime implicants. The simplified
Boolean function contains all essential prime implicants and only the required prime
implicants.

Note − If don’t care terms also present, then place don’t cares ‘x’ in the respective cells of
K-map. Consider only the don’t cares ‘x’ that are helpful for grouping maximum number of
adjacent zeroes. In those cases, treat the don’t care value as ‘0’.

K-map method, which is a convenient method for minimizing Boolean functions up to 5

variables. But, it is difficult to simplify the Boolean functions having more than 5 variables
by using this method.

Quine Mccluskey method

Quine-McCluskey tabular method is a tabular method based on the concept of prime
implicants. We know that prime implicant is a product orsumorsum term, which can’t be
further reduced by combining with any other product orsumorsum terms of the given
Boolean function.

This tabular method is useful to get the prime implicants by repeatedly using the following
Boolean identity.

xy + xy’ = xy+y′ = x.1 = x

Procedure of Quine-McCluskey Tabular Method

Follow these steps for simplifying Boolean functions using Quine-McClukey tabular
method.

Step 1 − Arrange the given min terms in an ascending order and make the groups based on
the number of ones present in their binary representations. So, there will be at most ‘n+1’
groups if there are ‘n’ Boolean variables in a Boolean function or ‘n’ bits in the binary
equivalent of min terms.
Step 2 − Compare the min terms present in successive groups. If there is a change in only
one-bit position, then take the pair of those two min terms. Place this symbol ‘_’ in the
differed bit position and keep the remaining bits as it is.

Step 3 − Repeat step2 with newly formed terms till we get all prime implicants.

Step 4 − Formulate the prime implicant table. It consists of set of rows and columns.
Prime implicants can be placed in row wise and min terms can be placed in column wise.
Place ‘1’ in the cells corresponding to the min terms that are covered in each prime
implicant.

Step 5 − Find the essential prime implicants by observing each column. If the min term is
covered only by one prime implicant, then it is essential prime implicant. Those essential
prime implicants will be part of the simplified Boolean function.

Step 6 − Reduce the prime implicant table by removing the row of each essential prime
implicant and the columns corresponding to the min terms that are covered in that essential
prime implicant. Repeat step 5 for Reduced prime implicant table. Stop this process when all
min terms of given Boolean function are over.

Example

Let us simplify the following Boolean function, f(W,X,Y,Z)=∑m(2,6,8,9,10,11,14,15) using

Quine-McClukey tabular method.

The given Boolean function is in sum of minterms form. It is having 4 variables W, X, Y &
Z. The given min terms are 2, 6, 8, 9, 10, 11, 14 and 15. The ascending order of these min
terms based on the number of ones present in their binary equivalent is 2, 8, 6, 9, 10, 11, 14
and 15. The following table shows these min terms and their equivalent
binary representations.

Group Name Minterms W X Y Z

2 0 0 1 0
GA1
8 1 0 0 0
 6 0 1 1 0

GA2 9 1 0 0 1

10 1 0 1 0

11 1 0 1 1
GA3
14 1 1 1 0

GA4 15 1 1 1 1

The given minterms are arranged into 4 groups based on the number of ones present in their
binary equivalents. The following table shows the possible merging of minterms from
adjacent groups.

Group Name Minterms W X Y Z

2,6 0 - 1 0

2,10 - 0 1 0
GB1
8,9 1 0 0 -

8,10 1 0 - 0

GB2 6,14 - 1 1 0

9,11 1 0 - 1

10,11 1 0 1 -

10,14 1 - 1 0
 11,15 1 - 1 1
GB3
14,15 1 1 1 -

The minterms, which are differed in only one-bit position from adjacent groups are merged.
That differed bit is represented with this symbol, ‘-‘. In this case, there are three groups and
each group contains combinations of two min terms. The following table shows the
possible merging of minterm pairs from adjacent groups.

Group Name Minterms W X Y Z

2,6,10,14 - - 1 0

2,10,6,14 - - 1 0
GB1
8,9,10,11 1 0 - -

8,10,9,11 1 0 - -

10,11,14,15 1 - 1 -
GB2
10,14,11,15 1 - 1 -

The successive groups of min term pairs, which are differed in only one-bit position are
merged. That differed bit is represented with this symbol, ‘-‘. In this case, there are two
groups and each group contains combinations of four min terms. Here, these combinations
of 4 min terms are available in two rows. So, we can remove the repeated rows. The reduced
table after removing the redundant rows is shown below.

Group Name Minterms W X Y Z

GC1 2,6,10,14 - - 1 0
 8,9,10,11 1 0 - -

GC2 10,11,14,15 1 - 1 -

Further merging of the combinations of min terms from adjacent groups is not possible,
since they are differed in more than one-bit position. There are three rows in the above table.
So, each row will give one prime implicant. Therefore, the prime implicants are YZ’, WX’
& WY.

The prime implicant table is shown below.

Minterms / Prime 2 6 8 9 10 11 14 15
Implicants

YZ’ 1 1 1 1

WX’ 1 1 1 1

WY 1 1 1 1

The prime implicants are placed in row wise and min terms are placed in column wise. 1s
are placed in the common cells of prime implicant rows and the corresponding min term
columns.

The min terms 2 and 6 are covered only by one prime implicant YZ’. So, it is an essential
prime implicant. This will be part of simplified Boolean function. Now, remove this prime
implicant row and the corresponding min term columns. The reduced prime implicant table
is shown below.

Minterms / Prime 8 9 11 15
Implicants

WX’ 1 1 1
 WY 1 1

The min terms 8 and 9 are covered only by one prime implicant WX’. So, it is an essential
prime implicant. This will be part of simplified Boolean function. Now, remove this prime
implicant row and the corresponding min term columns. The reduced prime implicant table
is shown below.

Minterms / Prime 15
Implicants

WY 1

The min term 15 is covered only by one prime implicant WY. So, it is an essential prime
implicant. This will be part of simplified Boolean function.

In this example problem, we got three prime implicants and all the three are essential.
Therefore, the simplified Boolean function is

F(W,X,Y,Z)) = YZ’ + WX’ + WY.