Boolean Algebra

ShareIn this tutorial we will learning about Sum of Products and Product of Sums.

A boolean expression consisting entirely either of minterm or maxterm is called canonical expression.

Example

if we have two variables X and Y then,

Following is a canonical expression consisting of minterms XY + X’Y’

and

Following is a canonical expression consisting of maxterm (X+Y) . (X’ + Y’)

There are two forms of canonical expression.

- Sum of Products (SOP)
- Product of Sums (POS)

A boolean expression consisting purely of Minterms (product terms) is said to be in canonical sum of products form.

Example

lets say, we have a boolean function F defined on two variables A and B. So, A and B are the inputs for F and lets say, output of F is true i.e., F = 1 when any one of the input is true or 1. Now we draw the truth table for F.

A | B | F |
---|---|---|

0 | 0 | 0 |

0 | 1 | 1 |

1 | 0 | 1 |

1 | 1 | 1 |

Now we will create a column for the minterm using the variables A and B. If input is 0 we take the complement of the variable and if input is 1 we take the variable as is.

A | B | F | Minterm |
---|---|---|---|

0 | 0 | 0 | A'B' |

0 | 1 | 1 | A'B |

1 | 0 | 1 | AB' |

1 | 1 | 1 | AB |

To get the desired canonical SOP expression we will add the **minterms** (product terms) for which the **output is 1**.

F = A’B + AB’ + AB

From the previous example we have

F = A’B + AB’ + AB

Now, lets say we want to express the SOP using shorthand notation.

we have F = A’B + AB’ + AB

First we need to denote the minterms in shorthand notation.

A’B = (01)_{2} = m_{1}

AB’ = (10)_{2} = m_{2}

AB = (11)_{2} = m_{3}

We saw the conversion of SOP to shorthand notation. Lets check the conversion of shorthand notation to SOP.

Lets say, we have a boolean function F defined on two variables A and B. So, A and B are the inputs for F and lets say, the minterms are expressed as shorthand notation given below.

F = ∑(1, 2, 3)

our task is to get the SOP.

F has two input variables A and B and output of F = 1 for m_{1}, m_{2} and m_{3} i.e., 2nd, 3rd and 4th combination.

we have,

F = ∑(1, 2, 3)

= m_{1} + m_{2} + m_{3}

= 01 + 10 + 11

To convert from shorthand notation to SOP we follow the given rules. If the variable is 1 then it is taken "as is" and if the variable is 0 then we take its "complement".

F = ∑(1, 2, 3)

= A’B + AB’ + AB

And we have the required SOP

A boolean expression consisting purely of Maxterms (sum terms) is said to be in canonical product of sums form.

Example

Lets say, we have a boolean function F defined on two variables A and B. So, A and B are the inputs for F and lets say, output of F is true i.e., F = 1 when only one of the input is true or 1.

now we draw the truth table for F

A | B | F |
---|---|---|

0 | 0 | 0 |

0 | 1 | 1 |

1 | 0 | 1 |

1 | 1 | 0 |

Now we will create a column for the maxterm using the variables A and B. If input is 1 we take the complement of the variable and if input is 0 we take the variable as is.

A | B | F | Maxterm |
---|---|---|---|

0 | 0 | 0 | A + B |

0 | 1 | 1 | A + B' |

1 | 0 | 1 | A' + B |

1 | 1 | 0 | A' + B' |

To get the desired canonical POS expression we will multiply the maxterms (sum terms) for which the output is 0.

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

From the previous example we have

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

Now, lets say we want to express the POS using shorthand notation.

we have F = (A+B) . (A’+B’)

First we need to denote the maxterms in shorthand notation.

A+B = (00)_{2} = M_{0}

A’+B’ = (11)_{2} = M_{3}

Now we express F using shorthand notation.

F = M_{0} . M_{3}

This can also be written as F = ∏(0, 3)

We saw the conversion of POS to shorthand notation. Lets check the conversion of shorthand notation to POS.

Lets say, we have a boolean function F defined on two variables A and B so, A and B are the inputs for F and lets say, the maxterm are expressed as shorthand notation given below.

F = ∏(1, 2, 3)

Our task is to get the POS.

F has two input variables A and B and output of F = 0 for M_{1}, M_{2} and M_{3} i.e., 2nd, 3rd and 4th combination.

we have, F = ∏(1, 2, 3)

= M_{1} . M_{2} . M_{3}

= 01 . 10 . 11

To convert from shorthand notation to POS we follow the given rules. If the variable is 0 then it is taken as is and if the variable is 1 then we take its complement.

we have, F = ∏(1, 2, 3)

= (A+B’) . (A’+B) . (A’+B’)

And we have the required POS.

- Maximum subarray problem - Kadane's Algorithm Programming
- Maximum subarray problem Programming
- Find median of an array Programming
- Find the minimum and maximum number in an array using Tournament Method Programming
- Find the minimum and maximum number in an array Programming
- Reverse a string Programming
- Design Patterns - Strategy Pattern Design Patterns
- PostgreSQL - SELECT FROM Table PostgreSQL
- PostgreSQL - INSERT INTO Table PostgreSQL
- PostgreSQL - CREATE Table PostgreSQL