Two-Variable Sum of Minterms and Minimization Notes

Overview

  • Topic: Minimizing a two-variable Boolean function using sum of minterms and the combining theorem; contrast with product of sums (POS).
  • Practical goal: Find the minimum sum of products for a given truth table; see how minterms can be combined to simplify expressions.

Key concepts and definitions

  • Minterm (two-variable case): a product term that evaluates to 1 for exactly one input combination.
    • For variables A and B, the four minterms are:
    • m_0 = A'B' \ (A=0, B=0)
    • m_1 = A'B \ (A=0, B=1)
    • m_2 = AB' \ (A=1, B=0)
    • m_3 = AB \ (A=1, B=1)
  • Sum of minterms (SOP): a Boolean function expressed as the sum (OR) of the minterms corresponding to input combinations that yield 1.
    • Notation: Y = igvee m_i =
      \sum m(i) for the i values where Y=1.
  • Product of sums (POS): the Boolean function expressed as the product (AND) of maxterms corresponding to input combinations that yield 0.
    • Not used here, but for reference: Y = \prod M(i) where M(i) are maxterms.
  • Complement and De Morgan's laws (briefly):
    • (XY)' = X' + Y' \ (X+Y)' = X'Y'
    • Complement of a minterm like A'B' is (A'B')' = A + B .

Reading the two-variable truth table (case in the transcript)

  • The discussion identifies two input combinations where Y = 1:
    • When both A and B are 0: corresponds to the minterm A'B' (m0).
    • When A = 1 and B = 0: corresponds to the minterm AB' (m2).
  • Therefore, for this case the set of minterms is: Y = m0 + m2 = A'B' + AB'.
  • The other two input combinations (A=0,B=1) and (A=1,B=1) yield Y = 0 (these are m1 and m3).

From sum of minterms to a simplified expression (example)

  • Start with the sum of the identified minterms:
    • Y = A'B' + AB'
  • Factor the common literal B':
    • Y = B'(A' + A)
  • Use the complement law A' + A = 1:
    • Y = B' \cdot 1 = B'
  • Final simplified SOP form: Y = B' (a single literal in a product is allowed as a trivial SOP).
  • Interpretation: The function is simply NOT B; for all input combinations with B=0, Y=1; for B=1, Y=0.

How this connects to De Morgan’s law and complements

  • If you take the complement of the minterm expression, you should get the maxterms for the zeros.
    • Example: (A'B')' = A + B (consistent with De Morgan's law).
  • The transcript emphasizes that the complement of a prime pair is not simply the product unless you apply De Morgan’s correctly.

The combining theorem (Boolean algebra minimization technique)

  • Idea: If two minterms differ in exactly one variable, you can combine them to drop that differing literal, producing a simpler product term.
  • Examples (two-variable pairings):
    • m0 + m1 = A'B' + A'B = A'(B' + B) = A'
    • m2 + m3 = AB' + AB = A(B' + B) = A
    • m0 + m2 = A'B' + AB' = B'(A' + A) = B'
  • This is the essence of the combining theorem: combine adjacent minterms to reduce the expression by canceling the differing literal.
  • In the transcript, the key reduction occurs when combining m0 and m2 to obtain B'.
  • Important caveat discussed: the technique is especially straightforward when the minterms are adjacent in the truth table or K-map; if there are too few 1s or they are not adjacent, you may not be able to combine as desired, which is why you sometimes rely on the “one-zero” pattern to identify possible pairings.

Step-by-step practice example (based on the transcript)

  • Given the truth table where Y=1 for the combinations corresponding to m0 and m2 (i.e., A'B' and AB'), find the minimum sum of products.
    • Step 1: Write the sum of the minterms for Y=1:
    • Y = m0 + m2 = A'B' + AB'
    • Step 2: Apply the combining theorem by factoring the common literal B':
    • Y = B'(A' + A)
    • Step 3: Use tautology A' + A = 1:
    • Y = B'\cdot 1 = B'
    • Step 4: Result: The minimum sum of products is simply Y = B' (a single literal in a product).
  • Note: If you instead attempted to form the POS, you’d identify the maxterms for the zeros (the rows where Y=0) and multiply them, but the SOP minimization often yields a simpler circuit.

Practical implications and takeaways

  • Why minimize to SOP? Fewer literals and terms generally mean fewer gates and simpler hardware.
  • For two-variable functions, many cases reduce quickly via the combining theorem; recognizing common factors (like B' in the example) can turn several terms into a single literal.
  • The process mirrors working with Karnaugh maps (adjacent cells differ by only one variable), which is a visual way to apply the combining principle on larger scales.
  • The same principle extends to more variables: look for pairs, quads, etc., that differ by a small number of literals and combine step by step.

Quick recap (key takeaways)

  • Sum of minterms approach identifies where the output is 1 and builds Y as a sum of corresponding minterms.
  • For the two-variable case with Y = m0 + m2, the simplification is Y = A'B' + AB' = B'(A' + A) = B'.
  • The complement of a product of literals follows De Morgan’s law, e.g., (A'B')' = A + B.
  • The combining theorem helps to minimize SOP by combining minterms that differ in exactly one literal to drop that literal.
  • In practice, this leads to simpler Boolean expressions and, consequently, simpler, cheaper digital circuits.