Recipe

Read a normal form off a truth table

Use when: you have (or can build) a sentence's truth table and need an equivalent sentence in disjunctive or conjunctive normal form

Goal: a DNF built from the true rows, or a CNF built from the false rows, equivalent to the sentence

Taught in Normal forms

1. 1

   Build the sentence's truth table in standard order, and mark its true rows and its false rows.

   Why: the table lists every situation, so describing its rows describes the sentence completely.

2. 2

   Decide which form you need, then pick the matching set of rows.

   • you want DNF — use the rows where the sentence is true.
   • you want CNF — use the rows where the sentence is false.

   Why: DNF lists the cases the sentence allows; CNF lists the cases it forbids.

3. 3

   For DNF, write an "and" of literals true on that row alone: the letter where it's T, its negation where it's F. For CNF, write an "or" of literals false on that row and no other: the letter where it's F, its negation where it's T.

   Example

   For the row P = T, Q = F: the DNF term is P \wedge \neg Q, and the CNF clause is \neg P \vee Q.

   Why: each term is true on just its own row, and each clause is false on just its own row.

4. 4

   Join DNF terms with \vee, or CNF clauses with \wedge. If there are no rows to use, write P \wedge \neg P for a DNF or P \vee \neg P for a CNF.

   ⚡ Shortcut

   Pick the form with fewer rows to write. A sentence with one false row has a one-clause CNF, even if its DNF needs many terms.

   Why: an "or" of the true-row terms is true on those rows and no others, and an "and" of the false-row clauses is false on those rows and no others.