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

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.

Practical/Practical3/3classroom.md · 5.3 KB · updated 2026-07-31 21:14