**BOOLEAN EXPRESSION SIMPLIFICATION**

*SIMPLIFICATION METHODS*

1.USING BOOLEAN THEOREMS

2. KARNAUGH MAP METHOD

3.QUINE Mc CLUSKY METHOD

NEED FOR SIMPLIFICATION

F = x’y’z +x’yz +xy’ ------- Eqn 1

= x’z (y + y’) + xy’

= x’z +xy’ ------- Eqn 2

Compare Eqn 1 and Eqn 2

Eqn 1 requires two 3 input AND gates, one 2 input AND gate and an OR gate with 3 inputs

Eqn 2 requires two 2 input AND gates and an OR gate with 2 inputs

Simplified expression requires lesser number of gates and lesser number of inputs. It is preferable since it requires less wires and less components

**SIMPLIFICATION USING BOOLEAN THEOREMS**

*DISADVANTAGES*

1.Time consuming process

2.Need better understanding of laws and theorems

3.Lack of specific rules to predict each succeeding step in reduction process.

**KARNAUGH MAP METHOD**

• Karnaugh Map, invented by Maurice Karnaugh of Bell Labs in 1953, also known as K-map, is a diagrammatic method for logic minimization

• Pictorial form of truth table showing the relationship between inputs & outputs

• More efficient than Boolean algebra

• K-map is a diagram made up of squares. Each square represents a minterm or maxterm of the logic function

• K-map identifies the group of minterms which contains redundant variables of the form x + x’ = 1 and then it can be eliminated.

**T****WO - VARIABLE K-MAP**

• For a 2-variable function, there are 4 minterms.

Therefore, the K-map for a 2- variable function has 4 squares:

In each square, the minterm is either 0 or 1

depending on the value of the function at that r

**Con****struction of 2-variable K-map**

• To construct a K-map for a 2-variable function, a logic 1 is entered into the square where the corresponding minterm exists. A logic 0 is entered otherwise (or the square is left blank)

• (ex) f = A’B + AB’

• f is true when AB = 01 or 10

• f = Σ(1, 2)

**C****on****struction of K-map from Truth ****T****able**

• A K-map can be created directly from a truth table

• Each square of the K-map corresponds to one row of the truth table

• A logic 1 is entered when the function is 1

• A logic 0 is entered when the function is 0

**For example**

**3-variable K-map**

• A 3-variable logic function has 8 minterms and its truth table has 8 rows

• Hence, a 3-variable K-map has 8 squares

**Log****i****c Minimization with K-Map**

• Consider a logic function with m2 and m6

• i.e. f = Σ(2, 6)

• m2 is a’bc’ and m6 is abc’

• f = m2 + m6 = a’bc’ + abc’ = bc’(a’ + a) = bc’

• The 2 minterms have a common factor bc’ In the K-map, if we group these 2 adjacent minterms, we can reduce 1 variable

TRUTH TABLE TO MAP

Example of looping pairs of adjacent 1s PAIRS

Example of looping pairs of adjacent 1s QUADS

Example of looping pairs of adjacent 1s OCTETS

**PROCEDURE**

• Construct the K map, place 1s as indicated in the truth table.

• Check for octets (group of eight 1s)

• If octets not available check for quads (four adjacent 1s)

• Loop 1s that are adjacent to only one other 1 and encircle such pairs.

• Loop 1s that are not adjacent to any other 1s.

• 1s which are already present in a group can be included in new group to group the other 1s.

• Form the sum of all product terms generated by each loop.