# Minimisation and Canonical Forms

Computer Science I · Basic Digital Design · https://tryals.app/learn/computer-science-i/minimisation-and-canonical-forms

## Minimisation & Canonical Forms

A simpler boolean expression means a cheaper, faster circuit with fewer gates, less delay, and less power. **Minimisation** is finding an equivalent expression with as few terms and literals as possible.

Two **canonical forms** name functions unambiguously:

| Form | Definition | Example |
| --- | --- | --- |
| **Sum-of-products (SOP)** | OR of AND terms | $A\overline{B} + \overline{A}B$ |
| **Product-of-sums (POS)** | AND of OR terms | $(A+\bar{B})(\bar{A}+B)$ |

Canonical forms provide a clear starting point, but they are rarely minimal.

## Simplifying Logic & Pitfalls

Two primary tools perform logic simplification:

* **Boolean algebra**: Applies identities directly. Example: $AB + A\overline{B} = A(B + \overline{B}) = A$, collapsing two terms because $B$ is redundant.
* **Karnaugh map (K-map)**: A visual grid where adjacent cells differ in one variable. Circle groups of 1s in powers of two ($1, 2, 4, 8$) to eliminate variables.

> **Common Pitfall:** Circling group sizes that are **not** a power of two, or missing the **wrap-around** adjacency where left/right and top/bottom edges are neighbors. Both errors yield non-minimal or incorrect circuits.

## Practice questions

3 of this lesson's 10 practice questions, with answers. The full set is in the app.

### 1. Order the steps of minimising a boolean function with a Karnaugh map.

**Answer:**

1. Write the truth table of the function
2. Plot each 1-row of the table into its cell of the map
3. Circle groups of adjacent 1s, making every group as large as possible and a power of two in size
4. Write one product term for each group, keeping only the variables that stay constant across it
5. OR the terms together to get the minimised expression

**Why:** The map is only a re-arrangement of the truth table, so the table comes first. Grouping before writing terms matters: the variables that vary within a group are exactly the ones dropped, so a different circling gives a different, possibly larger expression. Writing terms cell by cell and grouping afterwards defeats the whole method.

Page: https://tryals.app/practice/computer-science-i/minimisation-and-canonical-forms/order-the-steps-of-minimising-a-boolean-function-with-a-karnaugh-map

### 2. A Karnaugh map is being simplified. Select every group size below that is a legal group in a K-map.

A. A group of 1 cell
B. A group of 6 cells
C. A group of 2 cells
D. A group of 4 cells
E. A group of 8 cells
F. A group of 3 cells

**Answer:** A. A group of 1 cell; C. A group of 2 cells; D. A group of 4 cells; E. A group of 8 cells

**Why:** Legal groups contain 1, 2, 4, 8, ... cells, powers of two, because each doubling removes exactly one variable from the term. A group of 3 or 6 does not correspond to any product term at all, so circling one produces an expression that is simply wrong; that is the most common K-map error, along with missing the wrap-around adjacency between opposite edges.

Page: https://tryals.app/practice/computer-science-i/minimisation-and-canonical-forms/a-karnaugh-map-is-being-simplified-select-every-group-size-below

### 3. Karnaugh maps are taught by hand for four variables and are useless at forty. What replaced them, and what is still worth learning from the map?

A. Nothing is worth learning from them, as the technique does not generalise
B. Algorithmic minimisation replaced them, on the same principle
C. Nothing replaced them; forty-variable functions are minimised by hand in practice
D. Truth tables replaced them, being exact rather than visual

**Answer:** B. Algorithmic minimisation replaced them, on the same principle

**Why:** 2⁴⁰ cells is beyond any visualisation, so Quine-McCluskey and Espresso do the work, but the map makes the underlying fact visible: terms differing in one variable combine and the variable drops out. The tool scales the principle; the map is where you see why it holds.

Page: https://tryals.app/practice/computer-science-i/minimisation-and-canonical-forms/karnaugh-maps-are-taught-by-hand-for-four-variables-and-are-useless