Logical Connectives and Normal Forms

Propositional logic gives you a small toolbox of connectives — \neg (not), \wedge (and), \vee (or) — and lets you bolt them together into formulas of any size. A single formula can be written in a bewildering number of equivalent ways, so logicians agreed on two tidy normal forms that any formula can be squeezed into. Once you can put a formula into one of these shapes, machines can reason about it, chips can compute it, and truth tables read off almost by themselves.

This matters far beyond the whiteboard. Every silicon chip in your phone is a sea of NAND gates — one humble connective, repeated a billion times, is enough to build every logical function. And a SAT solver — the workhorse behind chip verification, timetabling, and AI planning — insists on being fed its input in one specific normal form, CNF. This page is about those normal forms and the surprising fact that so little machinery goes such a long way.

Literals, clauses, and terms

Three small words unlock everything that follows.

A literal is a variable or its negation: P and \neg P are both literals. Nothing more complicated than that.
A clause is an OR of literals, e.g. (P \vee \neg Q \vee R). A clause is true as soon as any one of its literals is true.
A term (or minterm) is an AND of literals, e.g. (P \wedge \neg Q \wedge R). A term is true only when every literal in it is true.

Clauses and terms are mirror images: OR of literals versus AND of literals. Stack one kind on top of the other and you get exactly the two normal forms.

CNF and DNF

A formula is in Conjunctive Normal Form (CNF) when it is an AND of clauses — an AND of ORs:

(P \vee \neg Q) \wedge (\neg P \vee Q \vee R) \wedge (\neg R)

A formula is in Disjunctive Normal Form (DNF) when it is an OR of terms — an OR of ANDs:

(P \wedge \neg Q) \vee (\neg P \wedge Q \wedge R) \vee (\neg R)

The names describe the outermost operator: CNF is one big conjunction (AND) at the top, DNF is one big disjunction (OR) at the top. A handy mnemonic: CNF = AND of ORs, DNF = OR of ANDs. Every formula is equivalent to some CNF and to some DNF — and the truth table hands them to you for free.

For every propositional formula there is:

an equivalent formula in CNF (an AND of clauses), and
an equivalent formula in DNF (an OR of terms).

Both can be read straight off the formula's truth table, so no formula is beyond reach.

Reading DNF off the true rows, CNF off the false rows

Here is the trick that makes normal forms feel like magic. Take any formula's truth table:

For DNF, walk the TRUE rows. Each true row becomes one term: write P where the variable is 1 and \neg P where it is 0, AND them together, then OR all those terms. That formula is true on exactly those rows — so it equals your formula.
For CNF, walk the FALSE rows. Each false row becomes one clause, but with every literal flipped: write \neg P where the variable is 1 and P where it is 0, OR them together, then AND all those clauses.

The figure works the first recipe on the exclusive-or table F = P \oplus Q, which is true in exactly two rows. Step through it to watch each true row turn into a term and the terms join into a DNF.

The resulting DNF is

P \oplus Q \;\equiv\; (\neg P \wedge Q) \vee (P \wedge \neg Q).

Two true rows, two terms. Had the table been true in five rows, the DNF would have five terms — the recipe never fails, it just gets longer.

Worked example: build a DNF, then simplify

Consider the formula F = P \vee (\neg P \wedge Q). Its truth table is:

\begin{array}{cc|c} P & Q & F \\ \hline 0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 1 \end{array}

Read the DNF off the three true rows. Rows (0,1), (1,0) and (1,1) give the terms (\neg P \wedge Q), (P \wedge \neg Q) and (P \wedge Q), so the "full" DNF is

(\neg P \wedge Q) \vee (P \wedge \neg Q) \vee (P \wedge Q).

Now simplify. The last two terms share the factor P: (P \wedge \neg Q) \vee (P \wedge Q) = P \wedge (\neg Q \vee Q) = P. That collapses the whole thing to

(\neg P \wedge Q) \vee P \;\equiv\; P \vee Q.

The truth table for P \vee Q is indeed exactly those same three true rows — so P \vee (\neg P \wedge Q) was just a dressed-up P \vee Q all along. Reading a normal form off the table is mechanical; shrinking it back down is where the cleverness lives.

Functional completeness: how little you actually need

A set of connectives is functionally complete if every truth function can be built from it. Because the DNF recipe writes any formula using only \neg, \wedge and \vee, that set is complete straight away:

\{\neg, \wedge, \vee\} \text{ is functionally complete.}

But we can trim it. De Morgan's laws let you rewrite an OR using AND and NOT, or an AND using OR and NOT:

P \vee Q \equiv \neg(\neg P \wedge \neg Q), \qquad P \wedge Q \equiv \neg(\neg P \vee \neg Q).

So you can throw away \vee (keeping \{\neg, \wedge\}) or throw away \wedge (keeping \{\neg, \vee\}) — each of those two-element sets is still complete. What you may not drop is \neg: \{\wedge, \vee\} alone can never make the constant-false function, because with all inputs true it can only ever output true.

The showstopper: a single connective can be complete on its own. The NAND (\uparrow, "not-and") and NOR (\downarrow, "not-or") each do it:

P \uparrow Q \;\equiv\; \neg(P \wedge Q), \qquad P \downarrow Q \;\equiv\; \neg(P \vee Q).

From NAND alone you rebuild the whole toolkit: \neg P \equiv P \uparrow P, P \wedge Q \equiv (P \uparrow Q) \uparrow (P \uparrow Q), and P \vee Q \equiv (P \uparrow P) \uparrow (Q \uparrow Q). That is why a chip fab can build any circuit from one gate design — and why NAND is called the Sheffer stroke.

\{\neg, \wedge, \vee\} is functionally complete (the DNF recipe uses only these).
So are \{\neg, \wedge\} and \{\neg, \vee\}, via De Morgan.
\uparrow (NAND) alone and \downarrow (NOR) alone are each complete.
\{\wedge, \vee\} — with no negation — is not complete.

Every gate from one gate

Here is the Sheffer stroke earning its keep. Starting from a single \mathrm{nand} function (using 1 for true and 0 for false, so AND is just multiplication), we reconstruct NOT, AND, and OR — and check them against every input.

// NAND is the only primitive. For a,b in {0,1}, (a AND b) = a*b, so NAND = 1 - a*b. const nand = (a: number, b: number): number => 1 - a * b; // Rebuild the whole toolkit from NAND alone. const not = (a: number): number => nand(a, a); const and = (a: number, b: number): number => not(nand(a, b)); const or = (a: number, b: number): number => nand(not(a), not(b)); for (const a of [0, 1]) { for (const b of [0, 1]) { console.log(`a=${a} b=${b} not(a)=${not(a)} and=${and(a, b)} or=${or(a, b)}`); } }

Every output matches the ordinary truth tables — all conjured from one connective.

The classic mix-up: reading DNF off the false rows, or CNF off the true ones. Keep the pairing straight:

DNF ← TRUE rows, literals written as-is (variable 1 gives P, variable 0 gives \neg P), joined by AND, then OR-ed.
CNF ← FALSE rows, literals flipped (variable 1 gives \neg P, variable 0 gives P), joined by OR, then AND-ed.

The reason for the flip: a DNF term should be true on its own row, while a CNF clause should be false only on its own row (so its negation matches the row). Sanity-check by counting: if the table has 3 true and 1 false row, the DNF has 3 terms and the CNF has 1 clause.

You can turn any formula into CNF by pushing negations inward and distributing \vee over \wedge — but beware, the result can explode. Distributing (P_1 \wedge Q_1) \vee (P_2 \wedge Q_2) \vee \dots \vee (P_n \wedge Q_n) into CNF produces on the order of 2^{n} clauses — the formula's size can grow exponentially.

This is not a quirk of clumsy algebra; it is genuinely unavoidable for naive conversion. Real tools dodge it with the Tseitin transformation, which introduces fresh helper variables to produce an equisatisfiable CNF (same yes/no answer to "is it satisfiable?") that is only linearly bigger. So when a SAT solver wants CNF, it does not blindly distribute — and neither should you on anything larger than a toy formula.