Simplification of Boolean Equations and Karnaugh Map

Boolean Equations

 Ø Study of mathematical operations performed on certain binary variables.

 Ø Have only 2 values : 1 (true) or 0 (false).

 Ø Operators involve : AND , OR and NOT. 

 Ø Represented in 2 standard forms :

	Sum-of-products (SOP)	Product-of-sums (POS)
Output	1	0
Boolean algebra expressions	ANDed terms ORed together	ORed terms ANDed together
Example	F = A’B’ + A’B’C	F = (A’+B’)(A’+B’+C)
Both are reversible method. You can find both SOP/POS expression from the truth table or build truth table from the expression.

Build truth table from given expression,

Example of (SOP):  F = A’BC’ + AB’C

    a.     Determine the number of variables. Given variables are 3(A,B,C) , there will                   
         be 2³ = 8 possible combinations. (combinations = 2^inputs).

    b.    Prepare the truth table for the variables and the output. The value of             
         variables are in increasing binary value. (start from minimum, 0 0 0 and end   
         with maximum, 1 1 1).

    c.     Find the output value by substituting the variables with value written just now          
         into the equation given.

e.g. for the 1^st row, A = 0, A’ = 1, B = 0, B’ = 1, C = 0, C’ = 1

F = (1 x 0 x 1) + (1 x 0 x 1) = 0.

    d.    After substituting all the values, following truth table obtained :

A	B	C	F
0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	0
1	0	1	1
1	1	0	0
1	1	1	0

    e.     For minimizing error, u may divide the column into another smaller part for 
          easier identify the output value.

A	B	C	A’BC’	AB’C	F
0	0	0	0	0	0
0	0	1	0	0	0
0	1	0	1	0	1
0	1	1	0	0	0
1	0	0	0	0	0
1	0	1	0	1	1
1	1	0	0	0	0
1	1	1	0	0	0

    f.    Determine the row with output 1.

  

   g.    Identify the product term and add them together. For SOP, variable with 
        value 0 will be complement while for value 1, variable will remain  
        unchanged. The product term will be ANDed then ORed. 

    Product term : A’BC’ + AB’C

A	B	C	F
0	1	0	1
1	0	1	1

    SOP expression : F = A’BC’ + AB’C

There is another easy way of determining the output rather than substituting the variable one by one into the given equation.

    Example of (SOP):  F = A’BC’ + AB’C

                                         0 1 0     1 0 1

The following value are the variable which will result in output 1, while the others variable result in output 0. Therefore , it obtained the same truth table as the above.

    Example of (POS) : F = (A+B’+C).(A+B+C’).(A’+B’+C’)

                                                         0  1   0      0   0   1     1    1    1

    

The following value are the variable which will result in output 0, while others variable result in output 1. 

A	B	C	F
0	0	0	1
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	0

    Finding SOP and POS expression from given truth table :

    For SOP :

     For POS :

A	B	C	X	Product Term
0	0	0	0	(A+B+C)
0	0	1	0	(A+B+C’)
0	1	0	0	(A+B’+C)
1	0	1	0	(A’+B+C’)

    POS expression : X = (A+B+C).(A+B+C’).(A+B’+C).(A’+B+C’)

Simplification of Boolean Equation.

      1.    Algebraic Simplification

          ·       by applying Laws of Boolean Algebra.

Example :

     
       I.             

   II. AB + A(B + C) + B(B + C)

Step 1 : Apply Distributive Law to the 2^nd and 3^rd term. [A. (B + C)] =  (A.B) +  
             (A.C)

AB + AB + AC + BB + BC

Step 2 : Apply rule 7 to the 4^th term. (B.B = B).

 AB + AB + AC + B + BC

Step 3 : Apply rule 5 to 1^st and 2^nd terms. (A+B + A+B = A+B).

AB + AC + B + BC

Step 4 : Apply rule 10 to the last 2 terms. (B + BC = B)

AB + AC + B

Step 5 : Apply rule 10 to the 1^st and 3^rd terms. (AB + B = B)

Answer : B + AC

  III.

   

     2.    Karnaugh Map

     ·       A method of mapping truth tables onto a matrix.

     ·       Produce the simplest SOP or POS expression possible.

     ·       Number of cells = total number of input variable combinations.

     ·       Mostly up to 4 variables only, combination = 2⁴ = 16.

Example of K-map :

                           

Mapping of K-map in a given expression.

Example : Given following SOP expression. X = A’BC + AB’C + AB’C’.