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 |
|---|---|---|
| 1 | normal () | complemented () |
| 0 | complemented () | 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 | ||
|---|---|---|---|
| 0 | 000 | ||
| 1 | 001 | ||
| 2 | 010 | ||
| 3 | 011 | ||
| 4 | 100 | ||
| 5 | 101 | ||
| 6 | 110 | ||
| 7 | 111 |
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 –
| 0 | 0 | 0 | 1 | 1 | |
| 0 | 1 | 0 | 0 | 0 | |
| 1 | 0 | 0 | 1 | 1 | |
| 1 | 1 | 1 | 0 | 1 |
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
| # | ||||
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 |
| 2 | 0 | 1 | 0 | 0 |
| 3 | 0 | 1 | 1 | 0 |
| 4 | 1 | 0 | 0 | 1 |
| 5 | 1 | 0 | 1 | 0 |
| 6 | 1 | 1 | 0 | 0 |
| 7 | 1 | 1 | 1 | 1 |
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
| # | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | |
| 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 |
Method – Converting Between Canonical Forms
SoM → PoM:
- Write as a SoM (the missing minterms).
- 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 –
PoS → OR gates feeding one AND gate. Each sum term needs an OR gate, except a single literal.
Example –
Non-Standard Forms
An expression like is neither SoP nor PoS. It needs two AND and two OR gates in three levels:
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).
| # | ||||
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 |
| 2 | 0 | 1 | 0 | 0 |
| 3 | 0 | 1 | 1 | 1 |
| 4 | 1 | 0 | 0 | 0 |
| 5 | 1 | 0 | 1 | 1 |
| 6 | 1 | 1 | 0 | 1 |
| 7 | 1 | 1 | 1 | 1 |
Canonical forms
Simplification to SoP
Simplification to PoS
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).