Showing posts with label cannonical forms. Show all posts
Showing posts with label cannonical forms. Show all posts

Logical Expressions & Their Equivalent Forms

Logical Expression and Their Equivalent Forms - Minterms, Maxterms, Canonical Form, Standard Form

 All of the Boolean Expressions can be represented in either canonical form or standard form. In this tutorial, I am going to explain both forms with the help of solved examples.


Learning Objectives:



The canonical forms of a Boolean expression || Standard Form of a Boolean expression

There are two canonical forms: Sum of minterms and product of maxterms.
Similarly, there are two standard forms: Sum of products and product of sums.

Minterms:

There is a method of expressing Boolean expression algebraically from the truth table with the help of the following steps.
  • Draw truth table
  • Assign minterms to all possible combinations of variables. For three variables there are 8 possible combinations (23) and there are 8 minterms as well.
  • Pick only those minterms that produce 1 at the output.
  • spao="font-size: medium;">'OR' all the minterms
ANY BOOLEAN FUNCTION CAN EXPRESS IN THE SUM OF MINTERMS.

Example: Express AND gate expression in the sum of minterms

A

B

Output

Minterms

0

0

0

A’.B’  or  m0

0

1

0

A’.B  or  m1

1

0

0

A.B’  or  m2

1

1

1

A.B  or  m3


F = A.B = m3
F(A,B) = ∑ (3 )

It is a short notation for the sum of minterms.


Example: Express OR gate expression in the sum of minterms

A

B

Output

Minterms

0

0

0

A’.B’  or  m0

0

1

1

A’.B  or  m1

1

0

1

A.B’  or  m2

1

1

1

A.B  or  m3


F = A’.B + A.B’ + A.B = m1 + m2 +  m3
F(A,B) = ∑ ( 1,2,3)

It is a short notation for the sum of minterms.



From the above two examples of AND and OR gates, notice that we only pick those minterms or combinations at which the function produces a "HIGH" output.

Maxterms

There is another method of representing Boolean expressions algebraically from the truth table with the help of the following steps.
  • Draw truth table
  • Assign maxterms to all possible combinations of variables for 3 variables there are 8 possible combinations 
  • Pick only those maxterms that produce 0
  • 'AND' all the maxterms

Example: Express AND gate expression in the product of maxterms

A

B

Output

Maxterms

0

0

0

A + B  or  M0

0

1

0

A + B’  or  M1

1

0

0

A’ + B  or  M2

1

1

1

A’ + B'  or  M3


F = M0 . M1 .  M2 = (A + B)(A + B')(A' + B)


F(A,B) = π (0,1,2)

It is a short notation for the product of maxterms.



Example: Express OR gate expression in the product of maxterms

A

B

Output

Maxterms

0

0

0

A + B  or  M0

0

1

1

A + B’  or  M1

1

0

1

A’ + B  or  M2

1

1

1

A’ + B’  or  M3


F = M= (A + B)

F(A,B) = π (0)

It is a short notation for the product of maxterms.


ANY BOOLEAN FUNCTION CAN EXPRESS IN THE PRODUCT OF MAXTERMS.


Example: The truth table is given. Express the function in the sum of minterms and the product of maxterms. 

F = A + B'C

A

B

C

Output

Minterms

Maxterms

0

0

0

0

A’.B’.C’ (m0)

A+B+C  (M0)

0

0

1

1

A’.B’.C  (m1)

A+B+C’  (M1)

0

1

0

0

A’.B.C’  (m2)

A+B’+C  (M2)

0

1

1

0

A’.B.C  (m3)

A+B’+C’  (M3)

1

0

0

1

A.B’.C’  (m4)

A’+B+C  (M4)

1

0

1

1

A.B’.C  (m5)

A’+B+C’  (M5)

1

1

0

1

A.B.C’  (m6)

A’+B’+C  (M6)

1

1

1

1

A.B.C  (m7)

A’+B’+C’  (M7)


Sum Of Minterms:

F = A’.B’.C + A.B’.C’ + A.B’.C + A.B.C’ + A.B.C


F = m0 + m4 + m5 + m6 + m7


F(A,B,C) = ∑ (1,4,5,6,7 )


Product Of Maxterms:

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


F = M0 M2 M3


F(A,B,C) = π (0,2,3 )




Convert The Boolean Expression In Standard POS | Standard SOP:

Standard SOP:

When two or more product terms are summed by Boolean addition, the resulting sum is a Sum of Products (SOP).

 Examples:

AB + CD

AB' + CD'

A standard SOP expression is one in which all the variables in the domain apear in each product term in the expression.

 

Examples:

An example of a standard SOP expression is given below:

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

Domain: Set of variables A, B, C

Each product term contains all three variables.

ANY BOOLEAN FUNCTION CAN BE EXPRESSED IN THE SUM OF PRODUCTS.

Convert an ordinary SOP into a standard SOP:

To convert an ordinary SOP into a standard SOP, we use the following laws of Boolean algebra:

  1. A variable added to its complement is equal to '1'
  2. Any variable multiplied by 1 remains the same
  3. Distributive law
These points will help in the conversion process
  1. Check out for non-standard terms
  2. Find out the missing variable
  3. Multiply each term by a term containing a variable added to its complement. For example A = A + A' and AB = AB(B + B'). Since B + B' = 1



Examples of standard SOP form:
Similarly, the expression AB' + C is also the Sum Of Product SOP, but it is not in standard form. In standard for each product, the term contains all sets of variables either complimented or uncomplimented in the domain.

Now, let's convert it into standard form.

AB'(C + C') + C Point 1 and Point 2

AB'C + AB'C' + C Point 3

AB'C + AB'C' + C(A + A') Repeat point 1 and point 2

AB'C + AB'C' + AC +AC' Repeat point 3

AB'C + AB'C' + AC(B + B') +AC'(B + B') Repeat point 1 and point 2

AB'C + AB'C' + ACB + ACB' + AC'B + AC'B' Repeat point 3

AB'C + AB'C' + ACB + AC'B + AC'B' term AB;C appears twice

This expression has three variables in its domain (A, B, C), and each product term has all three variables and now it is in standard form.

When two or more sum terms are multiplied, the resulting expression is a product of sum (POS).

 Examples of standard POS form:



(A + B)(C + D)
(X + Y)(Z + X)

An important point to remember is that in the POS expression no two variables are under the same bar. Or you can say, the over-bar is restricted to single or individual variables only.

A' + B'+ C'        allowed 
(A + B + C)'           not allowed  
A standard POS expression is one in which all the variables in the domain appear in each sum term in the expression.

 



 Examples:

 (A + B' + C)(A + B' + C')(A + B + C)(A' + B +C)(A' + B' + C)
It is a standard POS expression.

Convert an ordinary POS into a standard POS:


Any Boolean expression can be expressed in POS form. To convert an ordinary POS into a standard POS, we use these laws:
  1. A variable multiplied by its complement is equal to 0
  2. If '0' is added to any term, the result will remain unchanged (additive identity)
  3. Apply distributive law
These points will help in the conversion process

  1. Check out for non-standard terms
  2. Find out the missing variable
  3. Add a term that is equivalent to '0'. For example, X.X' = 0
  4. Apply this rule (A+B)(A+C) = A + BC. Learn more about these rules in my article laws of Boolean algebra.

Examples:

(X + Y)(Z + X)

This example is in POS form, but not in standard form. Because each product term does not contain all the set of variables either complimented or uncomplimented in the domain. the domain of this expression is the set of variables X, Y, Z. Now, convert it into standard form.

= (X + Y)(Z + X)

The missing variable is Z in the first term and Y in the second term.

= (X + Y + Z.Z')(Y.Y' + Z + X)

Apply the rule stated in point 4.

= (X + Y + Z)(X + Y +Z')(X + Y + Z)(X + Y' + Z)

= (X + Y +Z')(X + Y + Z)(X + Y' + Z)

The term X + Y + Z repeat twice. 


Complement Of a Function Evaluated With The Help Of Canonical Form:

Recall the truth table for the OR gate. in the table below, OR gate is expressed in the sum of minterms and the product of maxterms. From the truth table, we can conclude some important points.


A

B

Output (OR)

Minterms

Maxterms

0

0

0

A’.B’  or  m0

A + B  or  M0

0

1

1

A’.B  or  m1

A + B’  or  M1

1

0

1

A.B’  or  m2

A’ + B  or  M2

1

1

1

A.B  or  m3

A’ + B’  or  M3




F(A,B) = ∑ ( 1,2,3)

F(A,B) = Ï€ (0)   


  1. The complement of a function is evaluated from the truth table. The complement of a function is equal to the sum of minterms missing in the original function
  2. Another important property that is clear from the truth table is  Mj ' = mj. It means any minterm with subscript j is equal to the complement of the maxterm with the same subscript j.
  3. To explain my point, I will proceed with the help of the simplest example of the OR gate. The complement of the OR gate is the NOR gate.
= m1 + m2 +  m3
F' = ( m1 + m2 +  m3)'
Apply DeMorgan's Law
F' = m1'. m2' .  m3'
F' = M1 . M2 . M3 
F'(A,B) = π (1, 2, 3)
F'(A,B) = ∑ (0) = Ï€ (1, 2, 3)

A

B

Output (NOR)

Minterms

Maxterms

0

0

1

A’.B’  or  m0

A + B  or  M0

0

1

0

A’.B  or  m1

A + B’  or  M1

1

0

0

A.B’  or  m2

A’ + B  or  M2

1

1

0

A.B  or  m3

A’ + B’  or  M3




F(A,B) = ∑ (0)

F(A,B) = Ï€ (1, 2, 3)   


The complemented function that is NOR has minterms that are not in the original OR function. In other words NOR function has maxterms that are missing in the original OR function.

Examples:
Evaluate the complement of the following Boolean function/ logic expression with the help of canonical forms. F = XY' + X'Y

F = XY' + X'Y
F' = (XY' + X'Y)'
De Morgan's law
F' = (XY')' (X'Y)'
again apply De Morgan's Law
F' = (X' + Y)(X + Y')
Apply distributive law
F' = XX' + X'Y' + XY + YY'
XX' = 0
F' = X'Y' + XY

The above expression is the complement of the given Boolean function. It is obtained for simplification of laws theorems. For more examples please check out my article here on Boolean expression simplification exercises.

Now our aim is to evaluate with the help of canonical forms.

Step 1: Draw truth tables along with minterms and maxterms



X

Y

Output

Minterms

Maxterms

0

0

0

X’.Y’  or  m0

X + Y  or  M0

0

1

1

X’.Y  or  m1

X + Y’  or  M1

1

0

1

X.Y’  or  m2

X’ + Y  or  M2

1

1

0

X.Y  or  m3

X’ + Y’  or  M3




F(X,Y) = ∑ ( 1,2)

F(X,Y) = Ï€ (0,3)   



F = M0 . M3

F = m1 + m2


F' = (m1 + m2)'
DeMorgan's law
F' = m1' . m2'
F' = M1 . M2
This expression F' = M1. M2 is the maxterm notation for the complement of the given function. now draw its truth table. Recall that maxterms are those where the function produces '0' at the output.

X

Y

Output

Minterms

Maxterms

0

0

1

X’.Y’  or  m0

X + Y  or  M0

0

1

0

X’.Y  or  m1

X + Y’  or  M1

1

0

0

X.Y’  or  m2

X’ + Y  or  M2

1

1

1

X.Y  or  m3

X’ + Y’  or  M3




F(X,Y) = ∑ (0 , 3)

F(X,Y) = Ï€ (1, 2)   


F' = m0 + m3

F' = X'Y' + XY

F'(X , Y) = ∑ (0 , 3 )


Conversion Between Standard Forms: SOP To POS | POS To SOP:

F = AB + CD SOP form
F = (A +B)(C +D) POS form
F = (AB + C)(CD + A) Neither POS nor SOP

I have already discussed conversion from ordinary SOP/POS to standard SOP/POS. For more examples please check out my next article for solved examples.

To convert standard POS to SOP or vice versa please do these simple steps.
  1. Convert the given expression into standard form. If it is given in ordinary SOP, convert it into standard SOP, if it is given in ordinary POS, convert it into standard POS. Standard SOP expression contains all the minterms (combination of variables that produce 1) and standard POS expression contains all the maxterms (combination of variables that produce 0).
  2. Write binary equivalent for each term in standard SOP or POS expression. for example, 1+0+0 is the binary equivalent value for (A'+B+C)
  3. Evaluate the number of possible combinations with the help of several variables (for 2 variables, the number of possible combinations is 22 )
  4. If the POS expression contains 2 product terms (for 2 variable expressions) the rest of the 2 terms are SOP terms. And if the POS expression contains 5 product terms (for 3 variable expressions) the rest of the 3 terms are SOP terms.
  5. Draw the truth table for ease.

Example: (A + B' +C)(A + B +C') (POS To SOP)


Step 1:
The expression is already in standard form.

Step 2:
Write binary equivalent for each combination of variables.
A + B' + C = 0 + 1 + 0
A + B + C' = 0 + 0 + 1

Step 3:
The total number of possible combinations is 23  = 8.

Step 4:
The POS expression contains only 2 combinations of variables. The rest of the 6 terms are SOP.
Step 5:
Have a look at the truth table.

A

B

C

Output

Minterms

Maxterms

0

0

0

0


A+B+C  (M0)

0

0

1

1

A’.B’.C  (m1)


0

1

0

0


A+B’+C  (M2)

0

1

1

1

A’.B.C  (m3)


1

0

0

1

A.B’.C’  (m4)


1

0

1

1

A.B’.C  (m5)


1

1

0

1

A.B.C’  (m6)


1

1

1

1

A.B.C  (m7)



F = A’.B’.C + A’.B.C  + A.B’.C’ + A.B’.C + A.B.C’ + A.B.C


Example: A'B'C + AB'C' +ABC (SOP To POS)

Step 1:
The expression is already in standard form.

Step 2:
Write binary equivalent for each combination of variables.
A'.B'.C = 0.0.1
A.B'.C' = 1.0.0
A.B.C = 1.1.1

Step 3:
The total number of possible combinations is 23  = 8.

Step 4:
The SOP expression contains only 3 combinations of variables. The rest of the 6 terms are POS.
Step 5:
Have a look at the truth table.

A

B

C

Output

Minterms

Maxterms

0

0

0

0


A+B+C  (M0)

0

0

1

1

A’.B’.C  (m1)


0

1

0

0


A+B’+C  (M2)

0

1

1

0


A+B’+C’  (M3)

1

0

0

1

A.B’.C’  (m4)


1

0

1

0


A’+B+C’  (M5)

1

1

0

0


A’+B’+C  (M6)

1

1

1

1

A.B.C  (m7)



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


Check out my next article for solved examples here.

Popular Posts