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

> **Source of tasks.** The problems below are taken **exactly** from the
> practical-class assignment for this topic (Boolean functions and normal forms);
> only the wording has been translated to English. **Task 1** is the truth-table
> construction worked through in the source material; **Tasks 2–3** are the
> DNF/CNF reductions. Each task is followed by a **complete worked solution**. The
> theory and the laws of Boolean algebra used here are in [2method.md](2method.md);
> recall the precedence $\neg > \wedge > \vee > \to$, the overline shorthand
> $\overline{A}=\neg A$, and juxtaposition $AB = A\wedge B$.

## Task 1 — Build the truth table of a Boolean function

**Construct the truth table of the function**
$$f(x,y,z,t) = x \vee \overline{y}\,(z \vee \overline{x}\,\overline{y}) \to t.$$

**Solution.** The function has four variables, so the table has $2^4 = 16$
interpretations. By precedence the formula is
$\big(x \vee \overline{y}(z \vee \overline{x}\,\overline{y})\big) \to t$: everything
left of $\to$ forms the antecedent $A$, and $f = A \to t = \overline{A} \vee t$.
Evaluate $A$ **inside-out** on each interpretation; for example,

$$
\begin{aligned}
(0,0,0,0):&\ \ 0 \vee 1(0 \vee 1\cdot 1) \to 0 = 0 \vee 1 \to 0 = 1 \to 0 = 0,\\
(0,0,0,1):&\ \ 0 \vee 1(0 \vee 1\cdot 1) \to 1 = 1 \to 1 = 1,\\
(0,1,0,0):&\ \ 0 \vee 0(\cdots) \to 0 = 0 \to 0 = 1,\\
(1,0,1,0):&\ \ 1 \vee \cdots \to 0 = 1 \to 0 = 0.
\end{aligned}
$$

Filling in all sixteen rows (in binary order, where the row number is the
interpretation number):

| # | $x$ | $y$ | $z$ | $t$ | $f$ |
|:--:|:--:|:--:|:--:|:--:|:--:|
| 0 | 0 | 0 | 0 | 0 | **0** |
| 1 | 0 | 0 | 0 | 1 | 1 |
| 2 | 0 | 0 | 1 | 0 | **0** |
| 3 | 0 | 0 | 1 | 1 | 1 |
| 4 | 0 | 1 | 0 | 0 | 1 |
| 5 | 0 | 1 | 0 | 1 | 1 |
| 6 | 0 | 1 | 1 | 0 | 1 |
| 7 | 0 | 1 | 1 | 1 | 1 |
| 8 | 1 | 0 | 0 | 0 | **0** |
| 9 | 1 | 0 | 0 | 1 | 1 |
| 10 | 1 | 0 | 1 | 0 | **0** |
| 11 | 1 | 0 | 1 | 1 | 1 |
| 12 | 1 | 1 | 0 | 0 | **0** |
| 13 | 1 | 1 | 0 | 1 | 1 |
| 14 | 1 | 1 | 1 | 0 | **0** |
| 15 | 1 | 1 | 1 | 1 | 1 |

So $f = 0$ on exactly the six interpretations $0,2,8,10,12,14$ and $f=1$ on the
other ten.

**Cross-check (simplify the formula).** The antecedent simplifies:
$$
\begin{aligned}
A &= x \vee \overline{y}\,(z \vee \overline{x}\,\overline{y})
   = x \vee \overline{y}\,z \vee \overline{x}\,\overline{y} && \text{(distribute; } \overline{y}\,\overline{y}=\overline{y}\text{)}\\
  &= x \vee \overline{y} \vee \overline{y}\,z && \text{(}x \vee \overline{x}\,\overline{y} = x \vee \overline{y}\text{)}\\
  &= x \vee \overline{y}. && \text{(absorption: }\overline{y}\vee\overline{y}z=\overline{y}\text{)}
\end{aligned}
$$
Hence $f = (x \vee \overline{y}) \to t = \overline{(x \vee \overline{y})} \vee t =
\overline{x}\,y \vee t$ (De Morgan). The compact function $f = \overline{x}\,y \vee
t$ is $1$ exactly when $x=0,y=1$ or $t=1$ — which agrees with the table row for
row.

## Task 2 — Reduce to DNF

**Reduce the formula to disjunctive normal form:**
$$\varphi = \overline{\,\overline{(x \to y)} \vee \overline{(y \to z)}\,}.$$

**Solution.** Push the outer negation inward, then eliminate the implications and
distribute.

$$
\begin{aligned}
\varphi &= \overline{\,\overline{(x \to y)} \vee \overline{(y \to z)}\,} \\
  &= \overline{\overline{(x \to y)}} \wedge \overline{\overline{(y \to z)}} && \text{(De Morgan)}\\
  &= (x \to y) \wedge (y \to z) && \text{(double negation)}\\
  &= (\overline{x} \vee y) \wedge (\overline{y} \vee z) && \text{(} A\to B = \overline{A}\vee B\text{)}\\
  &= (\overline{x}\,\overline{y}) \vee (\overline{x}\,z) \vee (y\,\overline{y}) \vee (y\,z) && \text{(distribute } \wedge \text{ over } \vee\text{)}\\
  &= (\overline{x}\,\overline{y}) \vee (\overline{x}\,z) \vee (y\,z). && \text{(} y\,\overline{y}=0 \text{, drop it)}
\end{aligned}
$$

The DNF is
$$\boxed{\ \varphi = \overline{x}\,\overline{y} \ \vee\ \overline{x}\,z \ \vee\ y\,z\ }$$
— an OR of three AND-terms. (Note $\varphi$ is exactly $(x\to y)\wedge(y\to z)$, the
transitivity of implication.)

## Task 3 — Reduce to CNF

**Reduce the formula to conjunctive normal form:**
$$\varphi = \overline{(x \to y)} \wedge \overline{\,\overline{(y \to z)} \to x\,}.$$

**Solution.** Simplify the two conjuncts by eliminating each implication and
applying De Morgan.

$$
\begin{aligned}
\overline{(x \to y)} &= \overline{\overline{x} \vee y} = x \wedge \overline{y}, \\
\overline{\,\overline{(y \to z)} \to x\,}
  &= \overline{\,(y\,\overline{z}) \to x\,} && \text{(}\overline{y\to z}=y\,\overline{z}\text{)}\\
  &= \overline{\,\overline{(y\,\overline{z})} \vee x\,}
   = (y\,\overline{z}) \wedge \overline{x}. && \text{(} P\to x=\overline P\vee x\text{, then De Morgan)}
\end{aligned}
$$

Therefore
$$
\varphi = (x \wedge \overline{y}) \wedge (y \wedge \overline{z} \wedge \overline{x})
        = x \wedge \overline{x} \wedge y \wedge \overline{y} \wedge \overline{z}.
$$

This is already a **conjunction of one-literal clauses** — a CNF — but it contains
the complementary pair $x$ and $\overline{x}$ (and $y$, $\overline{y}$), and
$x \wedge \overline{x} = 0$. Hence
$$\boxed{\ \varphi = x\,\overline{x}\,y\,\overline{y}\,\overline{z} \equiv 0\ }$$
— the formula is a **contradiction** (unsatisfiable): it is false under every
interpretation, so its truth table is all $0$s.