# 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](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.**

| $x$ | $y$ | $z$ | $f=\overline{x}\vee y\vee\overline{z}$ |
|:--:|:--:|:--:|:--:|
| 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | **0** |
| 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 |

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:

| | $xy$ | $\overline{x}y$ | $\overline{x}\,\overline{y}$ | $x\overline{y}$ |
|:--:|:--:|:--:|:--:|:--:|
| $z$ | 1 | 1 | | |
| $\overline{z}$ | 1 | 1 | 1 | |

![Annotated Karnaugh map for Задача 1: the block-of-four group y and the block-of-two group x-bar z-bar cover every 1](img/kmap_z1.png)

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

| $x$ | $y$ | $z$ | $F$ |
|:--:|:--:|:--:|:--:|
| 0 | 0 | 0 | 1 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |

**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:

| | $xy$ | $\overline{x}y$ | $\overline{x}\,\overline{y}$ | $x\overline{y}$ |
|:--:|:--:|:--:|:--:|:--:|
| $z$ | 1 | | | 1 |
| $\overline{z}$ | | 1 | 1 | |

![Annotated Karnaugh map for Задача 2: the wrap-around group xz (first and last columns) and the group x-bar z-bar](img/kmap_z2.png)

- 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:

| | $xy$ | $\overline{x}y$ | $\overline{x}\,\overline{y}$ | $x\overline{y}$ |
|:--:|:--:|:--:|:--:|:--:|
| $z$ | 1 | | | 1 |
| $\overline{z}$ | 1 | 1 | | 1 |

![Annotated Karnaugh map for Задача 3: the wrap-around group x (first and last columns, both rows) and the group y z-bar](img/kmap_z3.png)

- 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

| $xy \backslash zt$ | 00 | 01 | 11 | 10 |
|:--:|:--:|:--:|:--:|:--:|
| **00** | 1 | 0 | 0 | 1 |
| **01** | 1 | 0 | 1 | 1 |
| **11** | 1 | 1 | 0 | 1 |
| **10** | 1 | 1 | 1 | 1 |

![Annotated 4-variable Karnaugh map for Variant 1: four colour-coded groups and the resulting minimal DNF](img/kmap_v1.png)

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

| $xy \backslash zt$ | 00 | 01 | 11 | 10 |
|:--:|:--:|:--:|:--:|:--:|
| **00** | 1 | 0 | 0 | 1 |
| **01** | 1 | 0 | 0 | 1 |
| **11** | 1 | 0 | 0 | 1 |
| **10** | 0 | 1 | 1 | 0 |

![Annotated 4-variable Karnaugh map for Variant 2: three colour-coded groups and the resulting minimal DNF](img/kmap_v2.png)

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

| $xy \backslash zt$ | 00 | 01 | 11 | 10 |
|:--:|:--:|:--:|:--:|:--:|
| **00** | 1 | 0 | 0 | 1 |
| **01** | 1 | 0 | 0 | 1 |
| **11** | 0 | 1 | 1 | 0 |
| **10** | 0 | 1 | 1 | 1 |

![Annotated 4-variable Karnaugh map for Variant 3: three colour-coded groups and the resulting minimal DNF](img/kmap_v3.png)

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

| $xy \backslash zt$ | 00 | 01 | 11 | 10 |
|:--:|:--:|:--:|:--:|:--:|
| **00** | 1 | 1 | 1 | 0 |
| **01** | 1 | 1 | 0 | 0 |
| **11** | 1 | 1 | 1 | 1 |
| **10** | 1 | 1 | 1 | 0 |

![Annotated 4-variable Karnaugh map for Variant 4: three colour-coded groups and the resulting minimal DNF](img/kmap_v4.png)

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

| $xy \backslash zt$ | 00 | 01 | 11 | 10 |
|:--:|:--:|:--:|:--:|:--:|
| **00** | 1 | 1 | 0 | 1 |
| **01** | 1 | 0 | 0 | 1 |
| **11** | 0 | 1 | 1 | 0 |
| **10** | 1 | 0 | 0 | 1 |

![Annotated 4-variable Karnaugh map for Variant 5: four colour-coded groups including the four-corners group, and the resulting minimal DNF](img/kmap_v5.png)

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:

| $wx \backslash yz$ | 00 | 01 | 11 | 10 |
|:--:|:--:|:--:|:--:|:--:|
| **00** | 0 | 0 | 0 | 0 |
| **01** | 0 | 1 | 1 | 1 |
| **11** | $\times$ | $\times$ | $\times$ | $\times$ |
| **10** | 1 | 1 | $\times$ | $\times$ |

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