3. Classroom tasks and solutions / Аудиторні задачі та розв’язання #

Source of tasks. The problems below are taken exactly from the practical-class assignment for this topic (minimization of Boolean functions); only the wording has been translated to English. The worked example below demonstrates the full method (algebraic minimization → truth table → canonical CNF); Задача 1–4 are the tasks to solve, each minimized with a Karnaugh map. Every task is followed by a complete solution. Theory and the laws of Boolean algebra are in 2method.md; recall the overline $\overline{x}=\neg x$ and juxtaposition $xy = x\wedge y$.

Throughout, a three-variable Karnaugh map has columns $xy,\ \overline{x}\,y,\ \overline{x}\,\overline{y},\ x\overline{y}$ and rows $z,\ \overline{z}$; remember that the first and last columns are adjacent (wrap-around).

Worked example — algebraic minimization and the canonical CNF #

For $f(x,y,z) = (\overline{x} \vee \overline{y})(\overline{y} \vee \overline{z}) \to (\overline{x} \vee \overline{z})$: (a) find a minimal DNF by transformation; (b) build the truth table and write the canonical CNF.

(a) Minimal DNF. First simplify the antecedent by distributivity, then eliminate the implication and push the negation inward:

$$\begin{aligned} (\overline{x} \vee \overline{y})(\overline{y} \vee \overline{z}) &= \overline{y} \vee \overline{x}\,\overline{z} && \text{(distributivity)}\\ f &= (\overline{y} \vee \overline{x}\,\overline{z}) \to (\overline{x} \vee \overline{z}) = \overline{(\overline{y} \vee \overline{x}\,\overline{z})} \vee \overline{x} \vee \overline{z} && \text{(} A\to B=\overline A\vee B\text{)}\\ &= \big(y\,(x \vee z)\big) \vee \overline{x} \vee \overline{z} && \text{(De Morgan)}\\ &= xy \vee yz \vee \overline{x} \vee \overline{z} && \text{(distributivity)}\\ &= \overline{x} \vee y \vee \overline{z}. && \text{(} \overline{x}\vee xy=\overline{x}\vee y;\ \overline{z}\vee yz=\overline{z}\vee y\text{)} \end{aligned}$$

So the minimal DNF is $\ f = \overline{x} \vee y \vee \overline{z}$.

(b) Truth table and canonical CNF.

The function is $0$ on the single row $(x,y,z)=(1,0,1)$. Its maxterm complements each variable that is $1$ there ($x$ and $z$), giving

$$\text{canonical CNF: } f = (\overline{x} \vee y \vee \overline{z}).$$

(With only one zero, the canonical CNF is a single maxterm — here identical to the minimal DNF.)

Задача 1 — minimize with a Karnaugh map #

Simplify $\ f = xyz \vee \overline{x}\,\overline{y}\,\overline{z} \vee \overline{x}yz \vee xy\overline{z} \vee \overline{x}y\overline{z}.$

Solution. Place the five minterms on the map:

Two groups cover every $1$:

• a block of four — the two $y$-columns ($xy$ and $\overline{x}y$), both rows; only $y$ stays constant, so the term is $y$;
• a block of two — row $\overline{z}$, columns $\overline{x}y$ and $\overline{x}\,\overline{y}$; here $\overline{x}$ and $\overline{z}$ stay constant, giving $\overline{x}\,\overline{z}$.

$$\boxed{\ f = y \vee \overline{x}\,\overline{z}\ }$$

Задача 2 — canonical DNF from a truth table, then minimize #

For the function given by the truth table, write the canonical DNF, draw the Karnaugh map, and simplify.

Solution. $F=1$ on the rows $(1,1,1),(1,0,1),(0,1,0),(0,0,0)$, so the canonical DNF is

$$F = xyz \vee x\overline{y}z \vee \overline{x}y\overline{z} \vee \overline{x}\,\overline{y}\,\overline{z}.$$

On the map:

• row $z$, columns $xy$ and $x\overline{y}$ (the first and last, adjacent by wrap): only $x$ and $z$ stay constant $\Rightarrow xz$;
• row $\overline{z}$, columns $\overline{x}y$ and $\overline{x}\,\overline{y}$: $\overline{x}$ and $\overline{z}$ stay constant $\Rightarrow \overline{x}\,\overline{z}$.

$$\boxed{\ F = xz \vee \overline{x}\,\overline{z}\ }$$

(As a check, $xz\vee\overline{x}\,\overline{z}$ is exactly “$x$ and $z$ are equal”, which matches every row of the table.)

Задача 3 — minimize with a Karnaugh map (wrap-around) #

Simplify $\ f = xyz \vee x\overline{y}z \vee xy\overline{z} \vee x\overline{y}\,\overline{z} \vee \overline{x}y\overline{z}.$

Solution. Place the five minterms on the map:

• a block of four — the two $x$-columns ($xy$ and $x\overline{y}$, the first and last, adjacent by wrap), both rows; only $x$ stays constant $\Rightarrow x$;
• a block of two — row $\overline{z}$, columns $xy$ and $\overline{x}y$; here $y$ and $\overline{z}$ stay constant $\Rightarrow y\overline{z}$.

Every $1$ is covered, so (the smaller groups merge by absorption, $A \vee AB = A$)

$$\boxed{\ f = x \vee y\overline{z}\ }$$

Задача 4 — Four-variable Karnaugh maps (variants) #

Each map below defines a function $f(x,y,z,t)$: the rows are labelled by $xy$ and the columns by $zt$, both in the Gray order $00,01,11,10$. Minimise each function to a DNF by grouping the $1$s; the minimal CNF (from grouping the $0$s) is given as well. Wrap-around adjacency applies to both rows and columns.

Variant 1 #

Grouping the twelve $1$s:

• $\overline{t}$ — the two $t=0$ columns ($00,10$), all rows (a block of $8$);
• $x\overline{y}$ — row $10$, all columns (a block of $4$);
• $x\overline{z}$ — rows $11,10$, columns $00,01$ (a block of $4$);
• $\overline{x}yz$ — row $01$, columns $11,10$ (a block of $2$).

$$\boxed{\ f = \overline{t} \vee x\overline{y} \vee x\overline{z} \vee \overline{x}yz\ }$$

$$\text{CNF: } f = (x \vee y \vee \overline{t})(x \vee z \vee \overline{t})(\overline{x} \vee \overline{y} \vee \overline{z} \vee \overline{t}).$$

Variant 2 #

Groups: $y\overline{t}$ (rows $01,11$, columns $00,10$), $\overline{x}\,\overline{t}$ (rows $00,01$, columns $00,10$), and $x\overline{y}t$ (row $10$, columns $01,11$).

$$\boxed{\ f = y\overline{t} \vee \overline{x}\,\overline{t} \vee x\overline{y}t\ }$$

$$\text{CNF: } f = (x \vee \overline{t})(\overline{y} \vee \overline{t})(\overline{x} \vee y \vee t).$$

Variant 3 #

Groups: $xt$ (rows $11,10$, columns $01,11$), $\overline{x}\,\overline{t}$ (rows $00,01$, columns $00,10$), and $\overline{y}z\overline{t}$ (rows $00,10$, column $10$).

$$\boxed{\ f = xt \vee \overline{x}\,\overline{t} \vee \overline{y}z\overline{t}\ }$$

$$\text{CNF: } f = (x \vee \overline{t})(\overline{x} \vee z \vee t)(\overline{x} \vee \overline{y} \vee t).$$

Variant 4 #

Groups: $\overline{z}$ (the two $z=0$ columns $00,01$, all rows — a block of $8$), $xy$ (row $11$, all columns), and $\overline{y}t$ (rows $00,10$, columns $01,11$).

$$\boxed{\ f = \overline{z} \vee xy \vee \overline{y}t\ }$$

$$\text{CNF: } f = (y \vee \overline{z} \vee t)(x \vee \overline{y} \vee \overline{z}).$$

Variant 5 #

Groups: $\overline{x}\,\overline{t}$ (rows $00,01$, columns $00,10$), $\overline{y}\,\overline{t}$ (rows $00,10$, columns $00,10$), $xyt$ (row $11$, columns $01,11$), and $\overline{x}\,\overline{y}\,\overline{z}$ (row $00$, columns $00,01$).

$$\boxed{\ f = \overline{x}\,\overline{t} \vee \overline{y}\,\overline{t} \vee xyt \vee \overline{x}\,\overline{y}\,\overline{z}\ }$$

$$\text{CNF: } f = (\overline{x} \vee \overline{y} \vee t)(x \vee \overline{y} \vee \overline{t})(x \vee \overline{z} \vee \overline{t})(\overline{x} \vee y \vee \overline{t}).$$

Задача 5 — a map with don’t-care conditions #

A circuit reads a decimal digit as a 4-bit BCD code $wxyz$ (value $8w+4x+2y+z$) and must output $1$ when the digit is $\ge 5$. Codes $1010$–$1111$ (values $10$–$15$) never occur, so their output is a “don’t-care” $\times$ — free to be $0$ or $1$, whichever minimises the result. Find the minimal DNF.

Rows $wx$, columns $yz$ (Gray order); $\times$ marks a don’t-care:

Solution. Treat each $\times$ as a $1$ only when it enlarges a group. Three groups then cover every required $1$:

• $w$ — the two $w=1$ rows ($11,10$), all columns (a block of $8$): the $\times$-row $11$ and the $\times$-cells of row $10$ let $w\overline{x}\,\overline{y}$ (just $8,9$) grow to the single literal $w$;
• $xy$ — rows $01,11$, columns $11,10$ (covers $6,7$);
• $xz$ — rows $01,11$, columns $01,11$ (covers $5,7$).

$$\boxed{\ f = w \vee xy \vee xz\ }$$

Every genuine $1$ ($5,6,7,8,9$) is covered and no genuine $0$ ($0$–$4$) is; the unused don’t-cares are simply left at $0$. (Ignoring the don’t-cares — forcing $10$–$15$ to $0$ — would block the $w$ group and force the longer $w\overline{x}\,\overline{y}\vee xy\vee xz$; this is the practical payoff of don’t-cares.)

Practical/Practical4/3classroom.md · 11.4 KB · updated 2026-08-01 18:44