1. Canonical Forms – Why?

We want a way of writing a Boolean function that:

  • makes it easy to compare expressions (to see if two are equivalent), and
  • maps directly onto the truth table.

Two canonical forms do this: the Sum of Minterms (SoM) and the Product of Maxterms (PoM).


2. Minterms and Maxterms

A variable can appear in normal form () or complement form (). A literal is a variable in either form.

Definition – Minterm

A minterm of variables is a standard product (AND) in which every one of the variables appears once, normal or complemented. There are minterms.

  • 3 variables → 8 minterms: .
  • is not a minterm of — is missing.

Definition – Maxterm

A maxterm of variables is a standard sum (OR) in which every variable appears once, normal or complemented. There are maxterms.

  • 3 variables → 8 maxterms: .
  • is not a maxterm of .

Standard Order and Notation

  • Variables must be written in the same order in every term (usually alphabetical). , , are not in standard order.
  • Minterms: lowercase (e.g. ). Maxterms: uppercase (e.g. ).
  • The index , written as an -bit binary pattern, says how each variable appears:
Bit at position in a minterm in a maxterm
1normal ()complemented ()
0complemented ()normal ()

Memory aid: is the product that equals 1 only on row ; is the sum that equals 0 only on row .

Table – Minterms and Maxterms of 3 Variables

Minterm Maxterm
0000
1001
2010
3011
4100
5101
6110
7111

Theorem – Relation Between and

By the generalized De Morgan laws:

Example

⇒ ✓.


3. Sum of Minterms (SoM)

Theorem – Function from Its 1s

A function equals the OR of the minterms where it is 1.

Example –

00011
01000
10011
11101

4. Product of Maxterms (PoM)

Theorem – Function from Its 0s

A function equals the AND of the maxterms where it is 0.

Example – Same

The only 0 is on row 1 ():

Choosing a Form

The two canonical forms are equivalent. Pick the shorter one:

  • Fewer 1s → Sum of Minterms.
  • Fewer 0s → Product of Maxterms.

For : SoM has three terms, PoM has one () → PoM is simpler.

Exercise – Canonical Forms from a Truth Table

#
00000
10011
20100
30110
41001
51010
61100
71111

The SoM indices and PoM indices are complementary sets — together they cover .

Method – Canonical Forms by Algebra

To expand a term missing variable , multiply it by (for SoM), or add to a sum term (for PoM).

Exercise –

  • SoM:
  • PoM: (T9 simplification)

Exercise –

PoM = the missing indices: .

⚠️ Respect the variable order (alphabetical here) when reading indices: = 001 = , not .


5. Complement of a Function

Theorem – Complement in Canonical Form

Let with the set of 1-rows and the remaining indices.

If is…then is…
— the missing minterms
— the missing maxterms
— maxterms with the same indices

Example

#01234567
01001001
10110110

Method – Converting Between Canonical Forms

SoM → PoM:

  1. Write as a SoM (the missing minterms).
  2. Complement it: becomes a PoM with those same indices.
flowchart LR
    A["F = Σm(1,4,5,6,7)"] -->|"missing indices"| B["F' = Σm(0,2,3)"]
    B -->|"complement:<br/>m_i' = M_i"| C["F = ΠM(0,2,3)"]

Shortcut: swap and replace the index list by the missing indices. PoM → SoM works the same way.


6. Standard Forms: SoP and PoS

In a standard form, terms may contain any number of literals (not necessarily all variables).

Definition – Sum of Products (SoP)

An OR of product terms (AND terms, one or more literals each).
Example: .

Definition – Product of Sums (PoS)

An AND of sum terms (OR terms, one or more literals each).
Example: .

⚠️ Every SoM is an SoP and every PoM is a PoS, but not the reverse. Canonical = every term has every variable; standard = terms can be shorter.

Two-Level Implementation

Inputs are assumed available in both normal and complemented form, so inverters are not drawn.

SoP → AND gates feeding one OR gate. Each product term needs an AND gate, except a single-literal term, which goes straight to the OR.

Example –

y’xyx’yz’F = y’ + xy + x’yz’

PoS → OR gates feeding one AND gate. Each sum term needs an OR gate, except a single literal.

Example –

xy’zx’yzG = x(y’+z)(x’+y+z)

Non-Standard Forms

An expression like is neither SoP nor PoS. It needs two AND and two OR gates in three levels:

ABCDEF = AB + C(D+E)

Boolean algebra can turn it into a standard form: (two levels).


7. Designing a Logic Circuit

flowchart LR
    A["1. Identify inputs"] --> B["2. Identify outputs"]
    B --> C["3. Truth table"]
    C --> D["4. Canonical forms<br/>(SoM / PoM)"]
    D --> E["5. Simplify to<br/>SoP / PoS"]
    E --> F["6. Draw the<br/>2-level circuit"]

Solved Exercise – Canonical and Standard Forms

is 1 when at least two inputs are 1 (rows 3, 5, 6, 7).

#
00000
10010
20100
30111
41000
51011
61101
71111

Canonical forms

x’yzxy’zxyz’xyzFm = Σm(3,5,6,7)

xyzxyz’xy’zx’yzFM = ΠM(0,1,2,4)

Simplification to SoP

xyyzxzF = xy + yz + xz

Simplification to PoS

xyxzyzF = (x+y)(x+z)(y+z)

Both standard forms need 3 two-input gates + 1 three-input gate, versus 4 three-input gates + 1 four-input gate for the canonical forms.

⚠️ Always check a simplification by expanding back: ✓ — the SoP and PoS describe the same function.


Exercises: in the slides — canonical forms from a truth table (); canonical forms of and ; SoM/PoM → SoP/PoS solved exercise (§4, §7).