# 2. Methodical guidelines / Методичні вказівки

This section is **self-contained**: it collects all the theory needed for the
theme — Boolean formulas, truth tables, the laws of Boolean algebra, and the two
normal forms — together with the techniques used to solve the tasks in
[3classroom.md](3classroom.md). No outside material is required.

## 2.1 Boolean formulas

A **Boolean (propositional) variable** takes one of two values, $1$ (true) or $0$
(false). **Formulas** are built from variables, the constants $0$ and $1$, and the
**connectives**:

| Connective | Symbol | Value |
|---|:--:|---|
| Negation (NOT) | $\neg A$ (also $\overline{A}$) | $1$ iff $A=0$ |
| Conjunction (AND) | $A \wedge B$ (also $AB$) | $1$ iff both are $1$ |
| Disjunction (OR) | $A \vee B$ | $1$ iff at least one is $1$ |
| Implication | $A \to B$ | $0$ **only** when $A=1,\ B=0$; equals $\neg A \vee B$ |
| Equivalence | $A \leftrightarrow B$ | $1$ iff $A$ and $B$ are equal |

Two shorthands used throughout: an **overline** $\overline{A}$ means $\neg A$, and
**juxtaposition** $AB$ means $A \wedge B$.

**Precedence.** To drop parentheses, connectives bind in the order
$$\neg \;>\; \wedge \;>\; \vee \;>\; \to \;>\; \leftrightarrow.$$
So $x \vee \overline{y}\,z \to t$ reads $\big(x \vee (\overline{y} \wedge z)\big)
\to t$. When in doubt, parenthesise.

## 2.2 From a formula to a truth table

A formula in $n$ variables defines a **Boolean function**; its **truth table**
lists the value on each of the $2^n$ **interpretations** (assignments of $0/1$ to
the variables). To build it:

1. write the $2^n$ rows in the **standard order** — read the variable values as a
   binary number counting up from $0\ldots0$ to $1\ldots1$;
2. for each row, **substitute** the values and evaluate the formula
   **inside-out**, respecting precedence;
3. record the result in the last column.

For example, one row of $f(x,y,z,t)=x \vee \overline{y}(z \vee \overline{x}\,
\overline{y}) \to t$ at $(x,y,z,t)=(0,0,0,0)$ evaluates as
$$0 \vee \overline{0}\,(0 \vee \overline{0}\,\overline{0}) \to 0
= 0 \vee 1(0 \vee 1) \to 0 = 0 \vee 1 \to 0 = 1 \to 0 = 0.$$
The number of the row (its binary value) doubles as the **number of the
interpretation**.

## 2.3 The laws of Boolean algebra

These identities let you transform a formula without changing the function it
computes. They come in **dual pairs** (swap $\wedge\leftrightarrow\vee$ and
$0\leftrightarrow1$).

| Law | For $\wedge$ | For $\vee$ |
|---|---|---|
| Double negation | \(\overline{\overline{A}} = A\) | |
| Complement (excluded middle) | $A \wedge \overline{A} = 0$ | $A \vee \overline{A} = 1$ |
| Constants | $A \wedge 0 = 0,\quad A \wedge 1 = A$ | $A \vee 0 = A,\quad A \vee 1 = 1$ |
| Idempotence | $A \wedge A = A$ | $A \vee A = A$ |
| Absorption | $A \wedge (A \vee B) = A$ | $A \vee (A \wedge B) = A$ |
| Combining | $(A \vee B)(A \vee \overline{B}) = A$ | $AB \vee A\overline{B} = A$ |
| Commutativity | $A \wedge B = B \wedge A$ | $A \vee B = B \vee A$ |
| Associativity | $A(BC) = (AB)C$ | $A \vee (B \vee C) = (A \vee B) \vee C$ |
| Distributivity | $A(B \vee C) = AB \vee AC$ | $A \vee BC = (A \vee B)(A \vee C)$ |
| De Morgan | $\overline{A \wedge B} = \overline{A} \vee \overline{B}$ | $\overline{A \vee B} = \overline{A} \wedge \overline{B}$ |

The two workhorses for normal forms are **De Morgan** (a bar over a group flips
the operation and complements each part) and **distributivity**.

## 2.4 Literals, DNF and CNF

- A **literal** is a variable or its negation: $x$ or $\overline{x}$.
- A **term** (elementary conjunction, "product") is an AND of literals, e.g.
  $x\,\overline{y}\,z$.
- A **clause** (elementary disjunction, "sum") is an OR of literals, e.g.
  $x \vee \overline{y} \vee z$.

The two standard shapes are:

- **Disjunctive normal form (DNF)** — an **OR of terms** (a *sum of products*),
  e.g. $(x\,\overline{y}) \vee (\overline{x}\,z)$;
- **Conjunctive normal form (CNF)** — an **AND of clauses** (a *product of sums*),
  e.g. $(x \vee \overline{y})(\overline{x} \vee z)$.

![CNF is an AND of OR-clauses; DNF is an OR of AND-terms](img/cnf_dnf.png)

Every formula has both forms. DNF makes satisfiability obvious (a term with no
clashing literals is satisfiable); CNF is the input format expected by SAT
solvers.

## 2.5 Reducing a formula to DNF or CNF

Follow the same first two steps, then distribute in the appropriate direction:

1. **Eliminate $\to$ and $\leftrightarrow$.** Replace $A \to B$ by
   $\overline{A} \vee B$, and $A \leftrightarrow B$ by
   $(\overline{A} \vee B)(\overline{B} \vee A)$.
2. **Push negations inward** with De Morgan and double negation until every $\neg$
   sits on a single variable (this is *negation normal form*).
3. **Distribute:**
   - for **DNF**, distribute $\wedge$ over $\vee$ until the formula is an OR of
     AND-terms;
   - for **CNF**, distribute $\vee$ over $\wedge$ until it is an AND of OR-clauses.
4. **Simplify** with idempotence, the complement laws ($x \wedge \overline{x} = 0$,
   $x \vee \overline{x} = 1$), absorption, and the constant laws. A term that
   contains both $x$ and $\overline{x}$ is $0$ (drop it from a DNF); a clause that
   contains both is $1$ (drop it from a CNF). If everything cancels, the formula is
   a **constant**: $0$ (a contradiction) or $1$ (a tautology).

![Algebraic reduction: apply one law per step until the formula reaches its target shape](img/simplify.png)

## 2.6 Working checklist

- For a **truth-table** task, list all $2^n$ rows in binary order and evaluate
  **inside-out**; a final algebraic simplification of the formula is a good
  cross-check (the table and the simplified formula must agree).
- For a **normal-form** task, always start by **removing $\to$ and
  $\leftrightarrow$**, then apply **De Morgan** to reach negation normal form
  *before* distributing.
- **DNF distributes $\wedge$ over $\vee$; CNF distributes $\vee$ over $\wedge$** —
  keep straight which one the task asks for.
- Cite **one law per step**, and finish by simplifying; watch for a term/clause
  collapsing to $0$ or $1$.