Disjunctive and Conjunctive Normal Forms

A literal is an atom $p$ or its negation $\neg p$. The two standard normal forms package any propositional formula into a fixed, layered shape built only from literals.

Definitions

• Disjunctive Normal Form (DNF): a disjunction of conjunctions of literals, $\bigvee_{i}\Big(\bigwedge_{j}\ell_{ij}\Big).$ Each inner conjunction (a term / minterm-style clause) is an AND of literals; the whole formula ORs them together. Think "OR of ANDs."

• Conjunctive Normal Form (CNF): a conjunction of disjunctions of literals, $\bigwedge_{i}\Big(\bigvee_{j}\ell_{ij}\Big).$ Each inner disjunction (a clause) is an OR of literals; the whole formula ANDs them together. Think "AND of ORs."

The defining rule for both forms: negations sit directly on atoms only, and the connectives are layered — in DNF no $\wedge$ may stand above a $\vee$, in CNF no $\vee$ may stand above a $\wedge$.

Existence theorem

Every propositional formula is logically equivalent to a formula in DNF and to one in CNF. Read a formula's truth table to build them directly:

• DNF: OR together one term per row where the formula is true (each term ANDs the literals making that row, using $\neg p$ where $p$ is false).
• CNF: AND together one clause per row where the formula is false (each clause ORs the complemented literals of that row).

Degenerate cases count

This is the exam's favorite trap. A single literal, a single term, or a single clause still qualifies:

Mini-example

Convert $p \to q$ to both forms. Its truth table is false only when $p=\text{T}, q=\text{F}$.

• DNF (OR of true rows $\neg p\neg q,\ \neg p\,q,\ p\,q$): $(\neg p \wedge \neg q) \vee (\neg p \wedge q) \vee (p \wedge q)$, which simplifies to $\neg p \vee q$.
• CNF (one clause for the single false row): $\neg p \vee q$ — already an AND of one clause.

Here $\neg p \vee q$ is simultaneously a valid DNF (two 1-literal terms) and a valid CNF (one clause), illustrating that the same formula can satisfy both templates.

Exam trick: A formula can be in DNF and CNF at once. Never reject a formula just because it lacks a top-level $\vee$ (for DNF) or top-level $\wedge$ (for CNF) — flatten with associativity, treat single literals/clauses as degenerate, and only disqualify it if some connective is layered the wrong way or a negation does not sit directly on an atom.