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, L06 — Propositional logic |
| Mode | In-class problem solving — pen and paper, no computer |
| Deliverable | Worked solutions to the tasks in 3classroom.md |
Contents
| # | Part | File |
|---|---|---|
| 1 | Objective | 1purpose.md |
| 2 | Methodical guidelines (self-contained theory) | 2method.md |
| 3 | Classroom tasks with solutions | 3classroom.md |
| 6 | Control questions | 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 , the constants , precedence, and the terms literal, DNF, CNF are defined in 2method.md; no outside reference is needed. An overline is a shorthand for , and writing two factors side by side (juxtaposition) means .
- Every task has a full solution. 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.