Lesson 03: Minterms and Maxterms

Example: Minterms for a 3-variable Function

When specifying a function, we usually start with product terms that contain all of the variables used in the function. In other words, we want the sum-of-midterms, and more specifically, the sum of the one-minterms (i.e., the minterms for which the function is a 1) as opposed to the zero-minterms (i.e., the minterms for which the function is a 0). We use the notion of 1-minterm to denote one-minterm and 0-minterm to denote zero-minterm.

Let us consider a function f(x, y, z) with three variables.

F(x, y, z) = x y z + x y z + y z
           = x y z + x y z + x y z + x y z

and repeated in the following truth table has the 1-minterms: m₃, m₅, m₆, and m₇.

Thus, a shorthand notation for the function is

F(x, y, z) = m₃ + m₅ + m₆ + m₇

We can further simplify the notation by using the standard algebraic symbol Σ for summation and listing out the minterm index numbers. Therefore, we can rewrite the equation as follows:

F(x, y, z) = Σ m(3, 5, 6, 7)

Because a function is obtained from the sum of the 1-minterms, the inverse of the function ( F ) must be the sum of the 0-minterms. This can be obtained easily by replacing the indices with those excluded from the original set. Therefore, the inverse of the above function is:

F(x, y, z) = Σ m(0, 1, 2, 4)

Given the Boolean function F(x, y, z) = y + x z, use Boolean algebra to convert the function to the sum-of-minterms format.

1. Identify the Variables and Number of Minterms:
   • The function has three variables: x, y, and z
   • Therefore, there will be 2³ = 8 possible minterms.
2. Combine Term Using Distributive Law:
   • Apply the distributive law to combine terms when necessary.
3. Express Ecah Minterm with All Variables:
   • In a sum-of-minterms format, all product terms must have all variables.
   • Ensure that each minterm includes all three variables, even if they appear complemented.

F(x, y, z) = y + x z
           = y (x + x)(z + z) + x z (y + y)    # Expand 1st term by ANDing it with (x + x)(z + z),
                                               # and 2nd term with (y + y)
           
           = x y z + x y z + x y z + x y z + x y z + x y z
           = m₇ + m₆ + m₃ + m₂ + m₁
           = Σ m(1, 2, 3, 6, 7)                # Sum of 1-minterms

Given the Boolean function F(x, y, z) = y + x z, use Boolean algebra to convert the function's inverse to the sum-of-minterms format.

F(x, y, z) = y + x z                           # Inverse
           = y (x + z)
           = y x + y z
           = y x (z + z) + y z (x + x)
           = x y z + x y z + x y z + x y z
           = m₅ + m₄ + m₀
           = Σ m(0, 4, 5)                      # Sum of 0-minterms

We have seen that a function can also be specified as a product-of-maxterms, or more specifically, a product of the zero-maxterms (I.e., the maxterms for which the function is a 0). Just like the minterms, we use the notation 1-maxterm to denote one-maxterm and 0-maxterm to denote zero-maxterm.

Let us consider a function f(x, y, z) with three variables:

F(x, y, z) = x y z + x y z + y z
           = (x + y + z)·(x + y + z)·(x + y + z)·(x + y + z)

Which is shown in the following table:

can be specified as the product of the 0-maxterms M₀, M₁, M₂, and M₄. The shorthand notation for the function is:

F(x, y, z) = M₀ · M₁ · M₂ · M₄

By using the standard algebraic symbol ∏ for the product and listing out the maxterm index numbers, the notation is further simplified to

F(x, y, z) = ∏ M(0, 1, 2, 4)

Given the Boolean function F(x, y, z) = y + x z, use Boolean algebra to convert the function to the product-of-maxterms format.

1. Identify the Function's False Outputs
2. Use Distributive Law to change to product-of-sums format
3. Express each maxterm with all variables:
   Remember, each maxterm should include all variables (x, y, and z) even if they are complemented.

F(x, y, z) = y + x z
           = y + (x z)                         # Use Distributive Law
           = (y + x)(y + z)
           = (y + x + z z)(y + z + x x)        # Expand 1st term by ORing it with z z,
                                               # and 2nd term with x x
                                               # Use Distributive Law
           = (x + y + z)(x + y + z)(x + y + z)(x + y + z)
           = M₄ · M₅ · M₀
           = ∏ M(0, 4, 5)                      # Product of 0-maxterms

Given the Boolean function F(x, y, z) = y + x z, use Boolean algebra to convert the function's inverse to the product-of-maxterms format.

F(x, y, z) = y + x z
           = y · (x + z)
           = (y + x x + z z)· (x + z + y y)    # Expand 1st term by ORing it with (x x + z z),
                                               # and 2nd term with y y
           = (x + y + z)(x + y + z)(x + y + z)(x + y + z)(x + y + z)(x + y + z)
           = M₂ · M₃ · M₆ · M₇ · M₁
           = ∏ M(1, 2, 3, 6, 7)                # Product of 1-maxterms

Convert the following Boolean function into Standard SoP form:

F(A, B, C) = A B + B C + A C                                 # SoP
           = A B (C + C) + (A + A) B C + A (B + B) C
           = A B C + A B C + A B C + A B C + A B C + A B C
           = A B C + A B C + A B C + A B C                   # Standard SoP form
           = m₇ + m₆ + m₃ + m₅
           = Σ m(3, 5, 6, 7)

Convert the following Boolean function into Standard PoS form:

F(x, y, z) = x y + x z
           = (x y + x) (x y + z)
           = (x + x) (y + x) (x + z) (y + z)
           = (x + y) (x + z) (y + z)
  Here ⇒ x + y = x + y + z z = (x + y + z)(x + y + z)
       ⇒ x + z = x + z + y y = (x + y + z)(x + y + z)
       ⇒ y + z = y + z + x x = (x + y + z)(x + y + z)
∴ F = (x + y + z)(x + y + z) (x + y + z)(x + y + z) (x + y + z) (x + y + z)   # Standard PoS form
    = M₀· M₂· M₄· M₅
    = ∏ M(0, 2, 4, 5)