Boolean function

A Boolean function is a Boolean algebraic equation derived generally from the word statement of the given problem or from the truth table. Such a function has two or more input variables. The function will produce a LOW or HIGH output when certain combinations of the input signal (binary value) is applied to the input variables.

Two forms of Boolean functions

1. 1. Sum of Product
   2. Product of Sum

Sum of Product:

A sum of product (or SOP) equation is obtained by ORing the product or the minterms

Minterm :

A Minterm is also called as product term is one that produces a HIGH output when the values of the input variables are ANDed together. It is written for a ‘1’ or HIGH values in the output column. Note carefully how the Minterms are formed for HIGH outputs in the truth table given below.

 

Table-1 above has only four minterms represented by the index m0, m3,m4 and m7 each minterm gives a ‘1’ of “HIGH” value for just one combination of literal only. . Minterm m4 gives a true value (i.e., 1) for just one combination of the input variables xy’z’ where x=1, y=0, z=0, similarily minterm m7 gives a true value (i.e., 1) for just one combination of the input variables xyz where x=1, y=1, and z=1,

Formation of SOP  equation:

A SOP equation is formed by :

• Writing the Minterms (or product terms) against a HIGH output in the truth table.
• Minterms can also be written with its index values as m₀, m₁, m₂, m₃, m₄, m₅, ……
• SOP is obtained by ORing the minterms (or product terms obtained in step-i)

Referring the truth table given above, we can now write the SOP equation in the following different ways  as:

•               F = X’.Y’.Z’ + X’.Y.Z  + X.Y’.Z’ + X.Y.Z                                                        eqn-1
• or          F=  m₀,    +     m₃,   +   m₄,      +   m₇
• or          F =  ∑m(0 , 3 , 4, 7)

Implementation of SOP function using basic gates:

Referring the Boolean function or Boolean Equation (1) , it can easily be put that the equation consist of AND operation on the input variables (asserted or complented ) and OR operation on the AND (or minterms) terms.

To implement the above Boolean SOP function we require :

Three input AND gates…………  04

Four input OR gate ……………..  01

Inverters (NOT gates) ……….    06

The SOP function implementation using basic gates is shown in figure-1

Product of Sum Equation:

A product of sum equation can be formed by ANDing all the Maxterms.

Maxterm:

A Maxterm also known as the sum terms is one that produces a LOW ‘0’ output when all the variables are ORed together. It should be remembered that if binary value of the input variable is ‘1’ then the variable is written in complemented form.  Example:

 

Maxterms are written for ‘0’ output terms as shown in the following truth table.

Formation of POS equation

1. Form the Maxterms (Sum terms)for ‘0’ output of truth table
2. Maxterms can also be written using the index as M0, M1, M2, M3, M4………..

• AND all Maxterms to form the POS equation.The AND (or product ) can also be written as ∏(M0, M1……)

From the truth table we see that there are four Maxterms. ANDing all these terms forms the POS equation as given below:

• F = (X+Y’+Z).(X’+Y+Z).(X’+Y+Z’).(X’+Y’+Z’) eqn-2
• Or F = ∏(M2, M4, M5, M7)
• Or F = ∏M( 2, 4, 5, 7)

Implementation of the logic circuit fro POS equation

Implementation of the logic circuit from POS equation – The first level of gating is OR gates and the 2^nd level gate used is AND gate. To implement the eqn-2 using basic gates would require:

• OR gates 04
• AND Gate 01
• NOT(inverts) 07

The logic circuit of eqn-2 is shown below

Practice Problem:

1. Write the truth table for the logic function F = X’YZ  +  X’Y’Z  + XYZ’ + XYZ
2. Write the Minterms and Maxterms in a single the truth table when a three input variable produces high outputs for the binary input equivalents of 0,1,2,4,7

Canonical or Standard vs Minimal form of equation

Canonical ( or standard) Form of SOP or POS equation

Canonical form of a SOP or POS equation is also called as a standard form of SOP or standard POS  equation. It is a unique form of equation in which each minterm or Maxterm  contains all the literals ( with a ‘ or without a ‘ i.e. complemented or un-complemented form). A canonical form can be written directly using the minterms or Maxterms from the truth table of the given function or a minimal form can be converted to the standard (Canonical) form

Minimal Form of SOP or POS equation

Minimal form of SOP equation

A minimal form of equation (either SOP or POS) is obtained on simplification of the standard or canonical form of equation. It may not include all the literal in its minterm or Maxterm. A minimal for of SOP equation looks like:

F = A’B + BC

We  observe that the first term uses two literals A and B and the 2^nd minterm uses B and C literals. In all there are total of three literals, literal C is missing in 1^st minterm whereas literal A is missing in 2^nd minterm.

Minimal form of POS equation:

Minimal form of POS equation is one that is obtained by simplifying the standard or canonical form of the POS equation. An example of the minimal POS equation is:

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

Converting a minimal form of equation to standard or canonical form

Converting minimal SOP to canonical(standard) SOP form

1. Find the missing literals in each minterm
2. Expand each minimal term by including missing literl in complemented and un-complemented for one at a time.

Example: Convert AB + BC in canonical (or standard) form of SOP

Solution

We observe literal C is missing in 1^st minterm and literal A missing in 2^nd minterm. Include them as:

F = AB(C+C’) + BC (A + A’)    solving we get

F= ABC + ABC’ + ABC + A’BC  next write the duplicate terms only once

F = ABC + ABC’ + A’BC

Converting minimal POS to canonical(standard) POS form

A minimal POS equation can be converted to standard or Canonical POS in a similar way by including the missing literals. See the examples.

Example: Convert (A+B)(a+C) to a canonical or the standard POS equation

Solution:

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

= [(A+B) + CC’][(A+C) + B.B’]

= [ (A+B+C)(A+B+C’)][(A+C+B)(A+C+B’)]

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

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

The above POS equation contains all the literals in each of the three Maxterm.

Practice Problems:

1. Convert AB + ACD to a canonical or the standard form of SOP equation

Options:

1. A’B’CD + ABC’D + AB’CD’ + A’BCD
2. ABC’D’ + ABC’D + ABCD’ + ABCD + AB’CD
3. AB’CD + ABC’D + ABCD’ + A’BCD + AB’CD’
4. ABC’D + AB’CD + A’BCD + ABCD’ A’B’CD

Answer : (b) solve and check your answer

2. Write the truth table from the following POS equation

F(ABCD) = ∏M(0, 1, 2, 4, 5, 6, 8, 9, 10)