Two Level Logic

Any logic function can be implemented with only

• AND, OR, and NOT functions
• Every input is either true or a complemented variable
• There are only two levels of gates and a possible inversion on the final output

Canonical Forms

• Literal = Boolean variable or complement of a boolean variable
  • Positive literal $A$
  • Negative literal $\overline{B}$
• Product term: AND operation on $\ge 1$ literals
• Sum term: OR operation on $\ge 1$ literals
• Minterm: Product term where all variables appear exactly once
• Maxterm: Sum term in which all variables appear exactly once
• Normal Forms
  • Canonical Disjunctive Normal Form (Sum of Products)
    • Sum of minterms
    • Unique for every truth table
  • Canonical Conjunctive Normal Form (Product of Sums)
    • Product of maxterms
    • Not unique
  • Different from normal two level logic because every inner term has to contain every variable

Sum of Products

• Inner level AND, outer level OR
• Easy to construct from the truth table of a function
  • AND the variables (inverted if their input is false) of each true row and then OR them together
  • Used more often because of that
• Example
  • $SOP=(A\cdot B\cdot \overline{C})+(A\cdot C\cdot \overline{B})+(B\cdot C\cdot \overline{A})$

Product of Sums

• Inner level OR, outer level AND
• Derive by negating the sum of all products that are false and then applying DeMorgan’s theorem twice to get product of sums
• Example
  • $POS=\overline{(\overline{A}+\overline{B}+C)\cdot (\overline{A}+\overline{C}+B)\cdot (\overline{B}+C+A)}$