# 1. Objective / Мета роботи

**Gain fluency with Boolean formulas — building a function's truth table from its
formula, and reducing formulas to disjunctive and conjunctive normal form by the
laws of Boolean algebra.**

By the end of the class the student should be able to:

- **evaluate** a Boolean formula on every interpretation of its variables and so
  **construct its truth table**, numbering the $2^n$ rows in the standard order
  and computing the value in each;
- apply **operator precedence** ($\neg > \wedge > \vee > \to > \leftrightarrow$)
  and the **laws of Boolean algebra** — double negation, De Morgan,
  distributivity, absorption, idempotence, the complement laws — to rewrite a
  formula while preserving its meaning;
- **eliminate** implications and equivalences in favour of $\neg,\wedge,\vee$, and
  **push negations inward** to the variables using De Morgan's laws;
- reduce a formula to **disjunctive normal form (DNF)** — an OR of AND-terms — and
  to **conjunctive normal form (CNF)** — an AND of OR-clauses;
- recognise when a reduction collapses to a **constant** ($0$ for a contradiction,
  $1$ for a tautology).

The class consolidates
[Lecture 4 — Boolean algebra basics](../../Lectures/CDM-L04.md) and the
normal forms of
[Lecture 6 — Propositional logic](../../Lectures/CDM-L06.md). All
theory needed is restated, self-contained, in [2method.md](2method.md).