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. 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$).

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).

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.)

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).

Practical/Practical4/2method.md · 6.9 KB · updated 2026-08-01 18:44