# 2. Methodical guidelines / Методичні вказівки

This section is **self-contained**: it collects all the theory needed for the
theme — canonical forms, algebraic minimization, and Karnaugh maps — together
with the techniques used to solve the tasks in
[3classroom.md](3classroom.md). No outside material is required.

## 2.1 Boolean functions and truth tables

A **Boolean function** of $n$ variables assigns a value in $\{0,1\}$ to each of the
$2^n$ input combinations (**interpretations**); its **truth table** lists them all.
We build from variables, the constants $0,1$, and the connectives $\neg$ (NOT,
written $\overline{x}$), $\wedge$ (AND, written by juxtaposition $xy$), and $\vee$
(OR). A **literal** is a variable or its negation ($x$ or $\overline{x}$).
Precedence is $\neg > \wedge > \vee$.

## 2.2 Canonical forms: canonical DNF and canonical CNF

Two special forms are read **directly off the truth table**. (Some textbooks call
them the *perfect* or *complete* DNF/CNF; the Russian/Ukrainian abbreviations
СДНФ/СКНФ, sometimes transliterated "SDNF/SKNF", refer to the **same** two forms. More
generally, a DNF is a **sum of products (SOP)** and a CNF a **product of sums (POS)** —
the names used in Lecture 5.)

- A **minterm** of a row is the AND of all $n$ variables, each **uncomplemented if
  its value is $1$** and complemented if $0$; it equals $1$ on **exactly that
  row**. The **canonical DNF** (the *sum of minterms*) is the **OR of the minterms
  of the $1$-rows**.
- A **maxterm** of a row is the OR of all $n$ variables, each **uncomplemented if
  its value is $0$** and complemented if $1$; it equals $0$ on **exactly that
  row**. The **canonical CNF** (the *product of maxterms*) is the **AND of the
  maxterms of the $0$-rows**.

For example, if $f(x,y,z)$ is $1$ only on the rows $(1,1,1)$ and $(0,0,0)$, then
$$\text{canonical DNF: } f = xyz \vee \overline{x}\,\overline{y}\,\overline{z}.$$
Canonical forms are unique but usually **not minimal** — every $1$-row (or
$0$-row) contributes a full term; minimizing removes the redundancy.

## 2.3 The laws of Boolean algebra

Minimization rewrites a formula using these identities (dual pairs — swap
$\wedge\leftrightarrow\vee$, $0\leftrightarrow1$).

| Law | For $\wedge$ | For $\vee$ |
|---|---|---|
| Double negation | \(\overline{\overline{A}} = A\) | |
| Complement | $A\,\overline{A} = 0$ | $A \vee \overline{A} = 1$ |
| Constants | $A\cdot 0 = 0,\ \ A\cdot 1 = A$ | $A \vee 0 = A,\ \ A \vee 1 = 1$ |
| Idempotence | $A A = A$ | $A \vee A = A$ |
| Absorption | $A(A \vee B) = A$ | $A \vee AB = A$ |
| Combining | $(A \vee B)(A \vee \overline{B}) = A$ | $AB \vee A\overline{B} = A$ |
| Commutativity / Associativity | $AB = BA,\ \ A(BC)=(AB)C$ | $A \vee B = B \vee A,\ \ A\vee(B\vee C)=(A\vee B)\vee C$ |
| Distributivity | $A(B \vee C) = AB \vee AC$ | $A \vee BC = (A \vee B)(A \vee C)$ |
| De Morgan | $\overline{AB} = \overline{A} \vee \overline{B}$ | $\overline{A \vee B} = \overline{A}\,\overline{B}$ |

A useful consequence: $A \vee \overline{A}B = A \vee B$ (absorption variant).

## 2.4 Algebraic minimization

To minimise by **equivalent transformations**:

1. **Eliminate** implications/equivalences: $A \to B = \overline{A} \vee B$.
2. **Push negations inward** with De Morgan and double negation, until each $\neg$
   is on a single variable.
3. **Simplify** with distributivity, **combining** ($AB \vee A\overline{B} = A$),
   **absorption** ($A \vee AB = A$), and the complement laws, until no rule
   applies. The result is a **minimal DNF** (or, dually, a minimal CNF).

![Algebraic reduction: apply one law per step until no rule applies](img/simplify.png)

The weakness of the algebraic method is that it is easy to *miss* a simplification;
the Karnaugh map makes the available groupings **visible** instead.

## 2.5 Karnaugh maps

A **Karnaugh map** is the truth table laid on a grid where **physically adjacent
cells differ in exactly one variable** (a Gray-code ordering). For three variables
$x,y,z$ the columns are labelled $xy,\ \overline{x}y,\ \overline{x}\,\overline{y},\
x\overline{y}$ and the rows $z,\ \overline{z}$; fill in a $1$ for every minterm of
the function.

(Lecture 5 draws the same three-variable map with the axes swapped — rows $x$,
columns $yz$ in Gray order. The two layouts are equivalent: a group's constant literals,
and hence its **term**, come out the same either way.)

![A Karnaugh map: adjacent 1s combine into a group that drops a variable](img/kmap3.png)

For **four** variables $x,y,z,t$ the map is a $4\times 4$ grid: the rows are
labelled by $xy$ and the columns by $zt$, **both** in the Gray order
$00,\ 01,\ 11,\ 10$. The wrap-around adjacency now applies to **both** directions
(top/bottom rows and left/right columns are neighbours), so a group may be a block
of $1,2,4,8,$ or $16$ cells, and a group of $2^k$ cells again drops $k$ variables.

**Reading a minimal DNF:**

- **Group** the $1$s into rectangles of size $1,2,4,8,\dots$ (a power of two), each
  as **large** as possible;
- adjacency **wraps around**: the left and right edges are neighbours and the top
  and bottom are too (the map is a **cylinder/torus**), so the first and last
  columns may group together, as may the four corners;
- a group of $2^k$ cells **eliminates $k$ variables**; its **term** is the AND of
  the literals that stay **constant** across the group;
- choose the **fewest, largest** groups that together **cover every $1$**
  (overlaps are allowed); the **minimal DNF** is the OR of the group terms.

**Reading a minimal CNF:** apply the same procedure to the **$0$s**. Grouping the
zeros gives the minimal DNF of $\overline{f}$; complementing it with De Morgan
turns each product into a sum, yielding the **minimal CNF** of $f$. (Equivalently,
each zero-group contributes one OR-clause.)

**Prime and essential implicants.** A group that **cannot be enlarged** (doubled) any
further is a **prime implicant**. If a prime implicant is the **only** group that covers
some particular $1$-cell, it is an **essential** prime implicant and *must* appear in the
answer. The systematic recipe is therefore: take **all essential** prime implicants first,
then cover any $1$s still left with as few further prime implicants as possible. (The
Karnaugh map and the tabular **Quine–McCluskey** method find the *same* prime implicants;
the map is faster by eye up to four variables, Quine–McCluskey scales to more.)

## 2.6 Working checklist

- To get the **canonical DNF/CNF**, list the truth table; OR the **minterms of the
  $1$-rows** (canonical DNF) or AND the **maxterms of the $0$-rows** (canonical
  CNF); mind the polarity rule (minterm: complement where the value is $0$;
  maxterm: complement where it is $1$).
- On a **Karnaugh map**, group in **powers of two**, as **large** as possible, use
  the **wrap-around**, and cover every $1$ with the fewest groups; read the term of
  a group from the literals that stay constant.
- For a **minimal CNF**, group the **$0$s** (or convert the minimal DNF of
  $\overline{f}$ by De Morgan).