17 Nov 2012

CANONICAL FORMS FOR BOOLEAN FUNCTION


CANONICAL FORMS FOR BOOLEAN FUNCTION

A Boolean function specified by a truth table can be expressed algebraically in many different ways. Two ways of forming Boolean expression are canonical and non-canonical forms. Canonical forms express all binary variables in every product (AND) or sum (OR) term of the Boolean function. There are two types of canonical forms of a
Boolean function. The first one is called sum-of product and the second one is called product-of-sum. A’BC+A’BC’+ABC’+AB’C’+A’B’C’+ABC is a canonical sum-of-product form of a Boolean function, the given function has contained three inputs that means three binary variables. In each term of the given function has contained three variables.(X’+Y+Z).(X+Y’+Z).(X’+Y+Z).(X’+Y+Z’) is a canonical product-of-sum form of a Boolean function. A non-canonical form does not express all binary variables in every product or sum term of the Boolean function.   

Minterms and Maxterms

A binary variable may appear either in its normal form (X) OR in its complement form (X’). Now consider two binary variables X and Y combined with an AND operation. Since each variable may appear in either form, these are four possible combinations ( X’.Y’, X’.Y, X.Y’, X.Y). Each of these four AND terms is called a minterm or a standard product.
 In a similar manner, n variables can be combined to form 2n minterm. The 2n different minterms may be determined by a method similar to the one shown below for three variables. The binary numbers from 0 to 2n – 1 are listed under the n variable. Each minterm is obtained from an AND term of the n variables, with each variable being primed if the corresponding bit of the binary number is 0 and unprimed if a 1.
In a similar fashion, n variables forming an OR term, with each variable being primed or unprimed, provide 2n possible combinations called maxterms or standard sums.
The eight maxterms for three variables, together with their symbolic designation, are listed below. Any 2n maxterms for n variables may be determined similarly. Each maxterm is obtained from an OR term of the n variables, with each variable being unprimed if the corresponding bit is 0 and primed if it is a 1.

MINTERMS AND MAXTERMS FOR THREE VARIABLES

VARIABLES
MINTERMS
MAXTERMS
X
Y
Z
    TERM
DESIGNATION
    TERM
DESIGNATION
0
0
0
X’. Y’. Z’
         m0
     X+Y+Z
      M0
0
0
1
X’. Y’. Z
         m1
     X+Y+Z’`
      M1
0
1
0
X’. Y. Z’
         m2
     X+Y’+Z
      M2
0
1
1
X’. Y. Z
         m3
     X+Y’+Z’
      M3
1
0
0
X. Y’. Z’
         m4
     X’+X+Z
      M4
1
0
1
X. Y’. Z
         m5
     X’+Y+Z’
      M5
1
1
0
X. Y. Z’
         m6
     X’+Y’+Z
      M6
1
1
1
X. Y. Z
         m7
     X’+Y’+Z’
      M7
MINTERMS AND MAXTERMS FOR THREE VARIABLES

SUM-OF-PRODUCT

A sum-0f-product expression is a product term (minterm) or several product terms (minterms) logically added (ORed) together.
The following steps are used to express a Boolean function in its sum-of –product form:
1. Construct a truth table for the given Boolean function.
2. Form a minterm for each combination of the variables which produces a 1 in the function.
3. The desired expression is the sum (OR) of all the minterms obtained in step 2.
For example, 011, 100, and 111, there corresponding minterms are X’.Y.Z, X.Y’.Z’, X.Y.Z .
Hence, taking the sum of all these minterms, the given function can be expressed in its sum-of-product form as:
     F1= X’.Y.Z + X.Y’.Z’ + X.Y.Z
Or F1= m3+m4+m7
Similarly, F2 = X’.Y.Z + X.Y’.Z + X.Y.Z’ + X.Y.Z can be easily expressed in its sum-of-product form:
      F2 = X’.Y.Z + X.Y’.Z + X.Y.Z’ + X.Y.Z
Or F2 = m3+m5+m6+m7
X
Y
Z
F1
F2
0
0
0
0
0
0
0
1
0
0
0
1
0
0
0
0
1
1
1
1
1
0
0
1
0
1
0
1
0
1
1
1
0
0
1
1
1
1
1
1
This is the truth table for F1 and F2
It is sometimes convenient to express a Boolean function in its sum-of-product form. If not in this form, it can be made. So by first expanding the expression into a sum of AND terms. 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 of the form (X+X’), where X is one of the missing variable.
 Let us take an example, express the given Boolean function into its sum-of-product form.
      F = A’.(B+C’)
      F = A’.B+A’.C’
 The given function has three variables A, B, and C. The first term of the function A’B is missing one variable, therefore
      A’B = A’.B.(C+C’)
      A’B = A’.B.C+A’B.C’
Similarly, the second term of the function A’C’ is missing one variable, therefore
    A’.C’= A’.C’.(B+B’)
    A’.C’ = A’.C’.B+A’.C’.B’
So by combining all the terms we get
          F = A’.B.C+A’.B.C’+A’.C’.B+A’.B’.C’
    Or F = A’.B.C+A’.B.C’+A’.B.C’+A’.B’.C’
But in the above expression, the term A’.B.C’ appears twice and according to Boolean postulate we have X+X=X. Hence it is possible to remove one of them.
         F = A’.B.C+A’.B.C’+A’.B’.C’
Rearranging the minterms in ascending order, we finally obtain:
         F = A’.B’.C’+A’.B.C’+A’.B.C
         F = m0+m2+m3
        F (A, B, C) = (0, 2, 3)
The summation symbol ‘’ stands for the ORing of terms. The numbers following it are the minterm of the function.

PRODUCT-OF-SUM

A product-of-sum expression is a sum term (maxterm) or several maxterms logically multiplied (ANDed) together. For example, the expression (X’+Y).(X+Y’) is a product-of-sum expression. 
The following steps are used to express a Boolean function in its product-of-sum form:
1. Construct a truth table for the given Boolean function.
2. Form a maxterm for each combination of the variables which produces a 0 in the function.
3. The desired expression is the sum (AND) of all the maxterms obtained in step 2.
For example, 000, 010, 011, 101, 110. The following five combinations of the variable produce a 0.
Their corresponding maxterms are:
 (X+Y+Z), (X+Y’+Z), (X+Y’+Z’), (X’+Y+Z’), and (X’+Y’+Z)
If taking the product (AND) of all these maxterms, we can write them as
      F = (X+Y+Z).(X+Y’+Z).(X+Y’+Z’).(X’+Y+Z’).(X’+Y’+Z)
Or F = M0.M2.M3.M5.M6
 Let us take an example:-Express the Boolean function in the product-of-sum form.
     F = X.Y+X’.Y
At first convert the function into OR term using the distributive law;
     F = X.Y+X’.Z
        = (X.Y+X’).(X.Y+Z)
        = (X+X’).(Y+X’).(X+Z).(Y+Z)
        = (X+Y’).(X+Z).(Y+Z)
The function has three variables X, Y, and Z. Each OR term is missing one variable, therefor:
X’+Y = X’+Y+Z.Z’ = (X’+Y+Z).(X’+Y+Z’) = (X’+Y+Z).(X’+Y+Z’)
 X+Z = X+Z+Y.Y’ = (X+Z+Y).(X+Z+Y’) = (X+Y+Z).(X+Y’+Z)
 Y+Z = Y+Z+X.X’ = (Y+Z+X).(Y+Z+X’) = (X+Y+Z).(X’+Y+Z)
Combining all the terms and removing those that appear more than one, we finally obtain:
    F = (X+Y+Z).(X+Y’+Z).(X’+Y+Z).(X’+Y+Z’)
   F = M0.M2.M4.M5
Or F (X,Y,Z) = π (0,2,4,5)
The product symbol π denotes the ANDing of the maxterms. The numbers following it are the maxterms of the function.
tag: what is canonical form, what is non canonical form, canonical, non canonical, sum of product, product of sum, maxterm, minterm, maxterms, minterms, maxterms and minterms, minterms and maxterms, canonical definition, canonical form, canonical forms, define canonical, definition of canonical form
Post a Comment