UNIT-II 

BOOLEAN EXPRESSIONS AND COMBINATIONAL LOGIC CIRCUITS

2.2 Simplification of Boolean Expressions:

Simplification of Boolean functions is mainly used to reduce the gate count of a design. Less number of gates means less power consumption, sometimes the circuit works faster and also when number of gates is reduced, cost also comes down. There are many ways to simplify a logic design; some of them are given below. We will be looking at each of these in detail in the next few pages.

  • Algebraic Simplification.
  • Simplify symbolically using theorems/postulates.
  • Requires good skills
  • Karnaugh Maps.
  • Diagrammatic technique using 'Venn - diagram'.
  • Limited to not more than 6 variables

Some of the examples are given here:

 

1. Simplify the Boolean expression

XY′Z′+XY′Z′W+XZ′

 

The above expression can be written as

XY′Z′ (1+W) +XZ′

=XY′Z′+XZ′ as 1+W=1

=XZ′ (Y′+1)

=XZ′ as Y′+1=1

 

2. Simplify the Boolean expression

X+X′Y+Y′+(X+Y′) X′Y

 

The above expression can be written as

X+X′Y+Y′+XX′Y+Y′X′Y

=X+X′Y+Y′ as XX′=0, and YY′=0

 

=X+Y+Y′ as X+X′Y=X+Y

=X+1 as Y+Y′=1

=1 as X + 1=1

 

3. Simplify the Boolean expression

Z(Y+Z) (X+Y+Z)

 

The above expression can be written as

(ZY+ZZ)(X+Y+Z)

= (ZY+Z) (X+Y+Z) as ZZ=Z

=Z(X+Y+Z) as Z+ZY=Z

=ZX+ZY+ZZ

=ZX+ZY+Z as ZZ=Z,

=ZX+Z as Z+ZY=Z

=Z as Z+ZX=Z

 

4. Simplify the Boolean expression

(X+Y)(X′+Z)(Y+Z)

 

The above expression can be written as

(XX′+XZ+YX′+YZ)(Y+Z)

=(XZ+YX′+YZ) (Y+Z) as XX′=0

=XZY+YYX′+YYZ+XZZ+YX′Z+YZZ

=XZY+YX′+YZ+XZ+YX′Z+YZ as YY=Y, ZZ=Z

Rearranging the terms we get

XZY+XZ+YX′+YX′Z+YZ as YZ+YZ=YZ

=XZ(Y+1) +YX′+YZ (X′+1) as Y+1=1, X′+1=1

=XZ+YX′+YZ

Now it seems that it cannot be reduced further. But apply the following trick:

The above expression can be written as

XZ+YX′+YZ(X+X′) as X+X′=1

=XZ+YX′+YZX+YZX′

Rearranging the terms we get

XZ+YXZ+Y X′+YX′Z

=XZ (1+Y) +YX′ (1+Z)

=XZ+YX′ as 1+Y=1, 1+Z=1

 

2.2.1 Sum of Products:

A sum of products expression consists of several product terms logically added. A product term is a logical product of several variables. The variables may or may not be complemented. The following are the examples of sum of products expressions.

 

1. XY+X'Y+XY'

2. AB+ABC+BC'

3. A+AB'+B'C

4. ABC+A'B+AB'C+A'BC'

Sometimes a product term may consist of a single variable.

 

 

2.2.2 Products of Sums:

A product of sums expression consists of several sum terms logically multiplied. A sum term is the logical addition of several variables. The variables may or may not be complemented. The following are examples of product of sums expressions:

A) (A+B) (A'+B')

B) A (B'+C') (B+C)

c) (X+Y') (X+Y+Z) (Y+Z)

Sometimes a sum term may consist of a single variable.

 

2.2.3 Canonical SOP and POS Forms:

When each term of a logic expression contains all variables, it’s said to be in the canonical form. When a sum of products form of logic expression is in canonical form, each product term is called minterm. Each minterm contains all variables. The canonical form of a sum of products expression is also called minterm canonical form or standard sum of products. Similarly, when a product of sums form of logic expression is in canonical form, each sum term is called a maxterm. Each maxterm contains all variables. The canonical form of a product of sums expression is also called maxterm canonical form or standard product of sums.

When a logic expression is not in the canonical form, it can be converted into canonical form. In the canonical form there is uniformity in the expression, which facilitates minimization procedure

The following are examples of the canonical form of sum of products expressions (or minterm canonical form):

(i). Z = XY + XY′

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

In case of 2 variables, the maximum possible product terms are 4, for 3 variables, the possible product terms are 8, for 4 variables 16, and for n variables, 2ⁿ.

In the above examples the expression (ii) contains 5 out of 8 possible product terms. When the expression is in the canonical form all terms are mutually exclusive. It means that for a given set of values of the variables, when one of the terms is equal to 1, all others must be 0. Of course, it is possible that all terms may be 0.

The following are examples of canonical form of product of sums expressions (or maxterm canonical form).

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

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

The following table gives the minterms and maxterms for a three variable logical function where the number of minterms as well as maxterms is 2³ = 8. In general, for an n-variable logical function there are 2ⁿ minterms and an equal number of maxterms.

 

Variables

Minterms

Maxterms

A

B

C

m i

M i

0

0

0

A' B' C' = m 0

A + B + C = M 0

0

0

1

A' B' C = m 1

A + B + C' = M 1

0

1

0

A' B C' = m 2

A + B' + C = M 2

0

1

1

A' B C = m 3

A + B' + C' = M 3

1

0

0

A B' C' = m 4

A' + B + C = M 4

1

0

1

A B' C = m 5

A' + B + C' = M 5

1

1

0

A B C' = m 6

A' + B' + C = M 6

1

1

1

A B C = m 7

A' + B' + C' = M 7

 

Minterms and Maxterms for Three variables

 

As shown in the above table each minterm is represented by m iand each maxterm is represented by M i where i is the decimal number equivalent of the natural binary number. With these shorthand notations logical functions can be represented as follows:

  • Y = A' B' C’ + A’ B’ C + A’ B C + A B C’

= m 0 + m 1 + m 3 + m 6

= ∑m( 0, 1, 3, 6 )

  • Y = ( A + B + C’ ) ( A + B’ + C’ ) ( A’ + B’ + C )

= M 1 + M 3 + M 6

= πM( 1, 3, 6 )

Where ∑ denotes sum of product while π denotes product of sum

 

 

 

 

 

Conversion of Sum of Products Expressions into Canonical Form:

 

The following examples will illustrate how logic expressions can be converted into canonical form.

Example 1: Convert the expression X + XY’ into canonical form.

The expression has two variables. The first term has only one variable. So to make it of two variables it can be multiplied by (Y + Y’), as Y + Y’ = 1. After multiplication the given logic expression can be written as

X(Y + Y′) + XY′, as Y + Y′ = 1

or XY + XY′ + XY′

or XY + XY′

 

Conversion of Product of Sums Expression into Canonical Form:

Before we proceed with such a conversion a few identities should be examined.

We can write A = (A + B) (A + B′)

This can be proved as follows:

A = A +A + 0

= A( B + B′ ) + A.A + B.B′, as B + B′ =1, AA=A, BB′=1

= AB + AB′ + AA + BB′

= A (A +B) + B′ (A + B)

= (A + B) (A + B′)

Similarly, we can write A + B = (A + B +C) (A + B + C′).

(A + B + C) (A + B + C′)

= AA + AB + AC′ + AB + BB + BC′ + AC + BC + CC′

Rearranging the terms we get

AA + BB + AC′ + BC′ + AC + BC + AB + AB, as CC′ = 0

= (A + B) + C′ (A + B) + C (A + B) + AB + AB [AA = A; BB = B]

= (A + B) + (A + B) (C + C′) + AB + AB

= (A + B) + (A + B) + AB + AB as C + C′ = 1

= A + B + AB + AB as (A + B) + (A + B) = (A + B)

= A + AB + B + AB

= A (1 + B) + B (1 + A)

= A + B as 1 + B = 1, 1 + A =1

 

This technique can be extended to any number of variables such as

(A + B′ + C) = (A + B′ + C + D) (A + B′ + C + D′)

Example 1: Convert the following expression into canonical form:

(A + B) (B + C)

To convert the above expression into canonical form the following identity can be used:

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

Applying the above identity, the given logic expression can be written as

(A + B + C) (A + B + C′) (A + B + C) (A′ + B + C)

= (A + B + C) (A + B + C′) (A′ + B + C)

 

2.2.4 Karnaugh Maps

Karnaugh maps provide a systematic method to obtain simplified sum-of-products (SOPs) Boolean expressions. This is a compact way of representing a truth table and is a technique that is used to simplify logic expressions. It is ideally suited for four or less variables, becoming cumbersome for five or more variables. Each square represents either a minterm or maxterm. A K-map of n variables will have 2 squares. For a Boolean expression, product terms are denoted by 1's, while sum terms are denoted by 0's.

 

A K-map consists of a grid of squares, each square representing one canonical minterm combination of the variables or their inverse. The map is arranged so that squares representing minterms which differ by only one variable are adjacent both vertically and horizontally. Therefore XY'Z' would be adjacent to X'Y'Z' and would also adjacent to XY'Z and XYZ'.

 

Minimization Technique

  • Based on the Unifying Theorem: X + X' = 1
  • The expression to be minimized should generally be in sum-of-products form (If necessary, the conversion process is applied to create the sum-of-products form).
  • The function is mapped onto the K-map by marking a 1 in those squares corresponding to the terms in the expression to be simplified (The other squares may be filled with 0's).
  • Pairs of 1's on the map which are adjacent are combined using the theorem Y(X+X') = Y where Y is any Boolean expression (If two pairs are also adjacent, then these can also be combined using the same theorem).

The minimization procedure consists of recognizing those pairs and multiple pairs

->These are circled indicating reduced terms.

    • Groups which can be circled are those which have two (2 1) 1's, four (2 2) 1's, and eight (2 3) 1's.

->Note that because squares on one edge of the map are considered adjacent to those on the opposite edge, group can be formed with these squares.

->Groups are allowed to overlap.

The objective is to cover all the 1's on the map in the fewest number of groups and to create the largest groups to do this.

Once all possible groups have been formed, the corresponding terms are identified.

->A group of two 1's eliminates one variable from the original minterm.

->A group of four 1's eliminates two variables from the original minterm.

->A group of eight 1's eliminates three variables from the original minterm, and so on.

->The variables eliminated are those which are different in the original minterms of the group.

 

In any K-Map, each square represents a minterm. Adjacent squares always differ by just one literal (So that the unifying theorem may apply: X + X' = 1). For the 2-variable case (e.g.: variables X, Y), the map can be drawn as in Figure 2.2.4 (a). Two variable map is the one which has got only two variables as input.

Figure 2.2.4 (a)

Equivalent Labeling

 

K-map need not follow the ordering as shown in the Figure 2.2.4(a). What this means is that we can change the positions of m0, m1, m2, m3 of the above figure as shown in the Figure 2.2.4 (b) and Figure 2.2.4(c).

Position assignment is the same as the default k-map positions. This is the one which we will be using throughout this unit.

Figure 2.2.4 (b)

This figure is with changed positions of m0, m1, m2, m3.

Figure 2.2.4(c)

The K-map for a function is specified by putting a '1' in the square corresponding to a minterm, a '0' otherwise.

 

Grouping/Circling K-maps

The power of K-maps is in minimizing the terms, K-maps can be minimized with the help of grouping the terms to form single terms as shown in Figure 2.2.4 (d). When forming groups of squares, observe/consider the following:

  • Every square containing 1 must be considered at least once.
  • A square containing 1 can be included in as many groups as desired

A group must be as large as possible.

Figure 2.2.4 (d)

 

  • If a square that is containing 1 which cannot be placed in a group, then leave it out to include in final expression.
  • The number of squares in a group must be equal to 2(pair), 4(quad), 8(octet).

The map is considered to be folded or spherical; therefore squares at the end of a row or column are treated as adjacent squares.

The simplified logic expression obtained from a K-map is not always unique. Groupings can be made in different ways as shown in Figure 2.2.4(e).

Before drawing a K-map the logic expression must be in canonical form.

Figure 2.2.4 (e)

In the next few pages we will see some examples of grouping.

 

2-­Variable K-Map:

 

Example - F= X'Y+XY

In this example we have the equation as input, and we have one output function. Draw the k-map for function F with marking 1 for X'Y and XY positions. Now combine two 1's as shown in Figure 2.2.4 (f) to form the single term. As you can see X and X' get canceled and only Y remains F = Y

 

 

 

Figure 2.2.4 (f)

Example - X'Y+XY+XY'

In this example we have the equation as input, and we have one output function. Draw the k-map for function F with marking 1 for X'Y, XY and XY positions. Now combine two 1's as shown in Figure 2.2.4(g) to form two single terms.

F = X + Y

Figure 2.2.4(g)

3-Variable K-Map

There are 8 minterms for 3 variables (X, Y, Z). Therefore, there are 8 cells in a 3-variable K-map. One important thing to note is that K-maps follow the gray code sequence, not

the binary one.

Using gray code arrangement ensures that minterms of adjacent cells differ by only one literal.

Each cell in a 3-variable K-map has 3 adjacent neighbours. In general, each cell in an n-variable K-map has n adjacent neighbours as shown in Figure 2.2.4(h)

Figure 2.2.4(h)

There is wrap-around in the K-map

  • X'Y'Z' (m0) is adjacent to X'YZ' (m2)

XY'Z' (m4) is adjacent to XYZ' (m6) as shown in Figure 2.2.4(i)

 

Figure 2.2.4(i)

 

 

 

Example

F = XYZ'+XYZ+X'YZ

F = XY + YZ

Example

F(X, Y, Z) = (1, 3, 4, 5, 6, 7)

 

F = X + Z

4-Variable K-Map

There are 16 cells in a 4-variable (W, X, Y, Z) K-map as shown in the Figure 2.2.4 (j).

Figure 2.2.4(j)

 

 

There are 2 wrap-arounds: a horizontal wrap-around and a vertical wrap-around. Every cell thus has 4 neighbours. For example, the cell corresponding to minterm m0 has neighbours m1, m2, m4 and m8 as shown in Figure 2.2.4(k).

 

Figure 2.2.4(k)

 

Example

F (W, X, Y, Z) = (1, 5, 12, 13)

F=WXY '+W'Y'Z

 

Example

F (W, X, Y, Z) = (4, 5, 10, 11, 14, 15)

F = W'XY' + WY

 

 

Don’t Care:

 

In some digital systems, certain input conditions never occur during normal operations; therefore the corresponding output never appears. Since the output does not appear it is indicated by an X in the truth table.

X is called don’t care condition. So don’t cares can be treated as 0’s and 1’s which ever is more convenient in the process of k-map simplification.

Consider the following truth table in which the output is low for all input entries from 1001 and ‘X’ from 1010 through 1111. The don’t care conditions are denoted by ’X’.

 

 

A

B

C

D

Y

0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

0

0

0

0

1

1

1

1

0

0

0

0

1

1

1

1

 

 

0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1

 

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

 

0

0

0

0

0

0

0

0

0

1

X

X

X

X

X

X

 

 

 

 

Here three don’t cares are treated as 1’s to get a quad which eliminates two variables. The remaining don’t cares are treated as 0’s.

 

Steps to be followed to apply don’t care conditions:

 

1. For the given truth table, draw a K-map with 0’s, 1’s and don’t cares.

2. Encircle the actual 1’s on the K-map in the largest groups, by treating the don’t cares as 1’s.

3. After the actual 1’s have been included in groups discard the remaining don’t cares visualizing them as 0’s.

 

2.2.5 Implementing Boolean Expressions Using NAND Gates:

 

The implementation of a Boolean function with NAND-NAND logic requires that the function be simplified in the sum of product form. The relationship between AND-OR logic and NAND-NAND logic is explained using the following example.

 

Consider the Boolean function: Y = A B C + D E + F

 

 

This Boolean function can be implemented using AND-OR logic as shown in

Figure 2.2.5 (a).

 

Figure 2.2.5 (a) AND-OR

 

Figure 2.2.5 (b) NAND-Bubbled OR

 

 

Figure 2.2.5 (b) shows the AND gates are replaced by NAND gates and the OR gate is replaced by a bubbled OR gate. The implementation shown in Figure 2.2.5(b) is equivalent to implementation in Figure 2.2.5 (a), because two bubbles on the same line represent double inversion (complementation) which is equivalent to having no bubble on the line. In case of single variable, F, the complemented variable is again complemented by bubble to produce the normal value of F.

Figure 2.2.5 (c) NAND-NAND

 

In Figure 2.2.5 (c), the output NAND gate is redrawn with the conventional symbol. The NAND gate with same inputs gives complemented result; therefore F′ is replaced by NAND gate with F input to its both inputs. Thus all the three implementations of the Boolean function are equivalent.

 

From the above example we can summarize the rules for obtaining the NAND-NAND logic diagram from a Boolean function as follows:

 

  • Simplify the given Boolean function and express it in sum of products

form (SOP form).

  • Draw a NAND gate for each product term of the function that has two

or more literals. The inputs to each NAND gate are the literals of the term. This constitutes a group of first-level gates.

  • If Boolean function includes any single literal or literals draw NAND gates for each single literal and connect corresponding literal as an input to the NAND gate.
  • Draw a single NAND gate in the second level, with inputs coming from outputs of first level gates.

 

2.2.6 Implementing Boolean Expressions Using NOR Gates:

 

The NOR function is a dual of the NAND function. For this reason, the implementation procedures and rules for NOR-NOR logic are the duals of the corresponding procedures and rules developed for NAND-NAND logic.

 

The implementation of a Boolean function with NOR-NOR logic requires that the function be simplified in the product of sums form. In product of sums form, we implement all sum terms using OR gates. This constitutes the first level. In the second level all sum terms are logically ANDed using AND gates. The relationship between OR-AND logic and NOR-NOR is explained using following example

 

 

Consider the Boolean function: Y = (A + B +C) (D + E) F

The Boolean function can be implemented using OR-AND logic, as shown in the

Figure 2.2.6 (a)

 

Figure 2.2.6 (a) OR-AND

 

Figure 2.2.6 (b) NOR-Bubbled AND

 

In Figure 2.2.6 (b) the OR gates are replaced by NOR gates and the AND gate is replaced by a bubbled AND gate. The implementation shown in Figure 2.2.6 (b) is equivalent to implementation shown in Figure 2.2.6 (a) because two bubbles on the same line represent double inversion (complementation) which is equivalent to having no bubble on the line. In case of single variable, F, the complemented variable is again complemented by bubble to produce the normal value of F.

Figure 2.2.6(c) NOR-NOR

 

In Figure 2.2.6 (c), the output NOR gate is redrawn with the conventional symbol. The NOR gate with same inputs gives complemented result, therefore, F is replaced by NOR gate with F input to its both inputs. Thus all the three implementations of the Boolean function are equivalent.

 

From the above example, we can summarize the rules for obtaining the NOR-NOR logic diagram from a Boolean function as follows:

 

  • Simplify the given Boolean function and express it in product of sums form(POS form)
  • Draw a NOR gate for each sum term of the function that has two or more literals. The inputs to each NOR gate are the literals of term. This constitute a group of first level gates.
  • If Boolean function includes any single literal or literals, draw NOR gate for each single literal and connect corresponding literal as an input to the NOR gate.
  • Draw a single NOR gate in the second level, with inputs coming from outputs of first level gates

 

 

 

 

 

Check Your Progress 1

1. The simplified form of Boolean expression(X+Y+XY) (X+Z) is

(a) X+Y+Z (b) XY+YZ

(c)X+YZ (d) XZ+Y

2. The simplified form of Boolean expression( X +Y'+Z) (Z+ Y'+Z') is

(a) X' Y+Z' (b) X+Y' +Z

(c) X (d) XY+Z'

3. The canonical form of logical expression A+A' B is

(a)AB+AB'+A'B (b) A'B' +AB+AB'

(c) AB '+A'B+AB' (c) A'B+A B' +A'B'

4. The canonical form of logical expression (A+B') (B'+C) is

(a) (A+B'+C') (A+B'+C) (A'+B'+C)

(b) (A+B'+C') (A+B'+C) (A'+B+C')

(c) (A+B+C') (A+B'+C') (A'+B'+C)

(d) (A+B'+C) (A+B'+C) (A'+B'+C)

Related units

2.0 Objectives

2.1 Introduction

2.3 Combinational Logic Circuits

2.4 Summary

2.5 Glossary

2.6 References

2.7 Answers to Check Your Progress Questions