# Practical Work 3 — Boolean Functions: Truth Tables and Normal Forms (DNF, CNF)

> Third practical class of **Computer Discrete Mathematics**. Working **by hand**,
> you build the truth table of a Boolean function from its formula, and reduce
> propositional formulas to the two standard shapes — **disjunctive normal form
> (DNF)** and **conjunctive normal form (CNF)** — using the laws of Boolean
> algebra.

## At a glance

| | |
|---|---|
| **Topic** | Boolean formulas: truth tables, the algebra of logic, DNF and CNF |
| **Prerequisite lectures** | [L04 — Boolean algebra basics](../../Lectures/CDM-L04.md), [L06 — Propositional logic](../../Lectures/CDM-L06.md) |
| **Mode** | In-class problem solving — pen and paper, no computer |
| **Deliverable** | Worked solutions to the tasks in [3classroom.md](3classroom.md) |

## Contents

| # | Part | File |
|:--:|---|---|
| 1 | Objective | [1purpose.md](1purpose.md) |
| 2 | Methodical guidelines (self-contained theory) | [2method.md](2method.md) |
| 3 | Classroom tasks **with solutions** | [3classroom.md](3classroom.md) |
| 6 | Control questions | [6questions.md](6questions.md) |

## Conventions

- **Language** — all work is written in **English**.
- **By hand, from the definitions and laws.** Evaluate formulas and transform
  them using the connective definitions and the laws of Boolean algebra, showing
  **one law per step** in a reduction.
- **Notation is fixed and self-contained.** The connectives $\neg,\wedge,\vee,\to,
  \leftrightarrow$, the constants $0,1$, precedence, and the terms *literal*,
  *DNF*, *CNF* are defined in [2method.md](2method.md); no outside reference is
  needed. An overline $\overline{x}$ is a shorthand for $\neg x$, and writing two
  factors side by side (juxtaposition) means $\wedge$.
- **Every task has a full solution.** [3classroom.md](3classroom.md) gives each
  task together with a complete worked answer, including the full truth table
  where one is required.

## Summary

A Boolean formula and its **truth table** are two views of the same function: the
formula is compact, the table is explicit. This practical drills moving between
them and rewriting a formula into a **standard shape**. First we build the truth
table of a four-variable function directly from its formula; then we reduce one
formula to **DNF** (an OR of AND-terms) and another to **CNF** (an AND of
OR-clauses), eliminating implications, driving negations inward with **De
Morgan's laws**, and distributing. Normal forms are the input format for SAT
solvers and the bridge between logic, set algebra, and digital circuits.