Equivalence and normal forms

A conditional and its contrapositive came out with identical truth table columns in the previous lesson, and that observation is worth far more than the fact itself.

If two formulas are true in exactly the same rows, then no argument, no matter how long, can tell them apart, and either may be swapped for the other anywhere it appears. That licenses doing logic the way algebra is done: by rewriting, in steps, each step justified by a law. This lesson sets out the laws, shows how any formula can be pushed into one of two standard shapes, and finishes with the surprising fact that one connective is enough to express everything the language can say.

Equivalence, and why substitution is safe

Two formulas are logically equivalent, written $φ \equiv ψ$ , when they have the same truth value under every valuation. Equivalently, $φ \leftrightarrow ψ$ is a tautology, since a biconditional is true exactly when its sides agree. The two definitions are the same statement read from the table and from the formula.

Equivalence licenses substitution: replacing any subformula by an equivalent one leaves the value of the whole unchanged, in every row. This follows from truth-functionality and nothing else. A connective sees only the truth values of its parts, so if a part is swapped for something with the same value in every row, no connective above it can notice. Whole chains of rewriting are therefore safe, which is the property that makes calculation possible.

Note carefully what equivalence is not. It is not sameness of meaning: $2 + 2 = 4$ and Fermat's last theorem are both tautologies of arithmetic and nobody would call them the same claim. Within propositional logic, where the only thing visible is a column of Ts and Fs, equivalence is as fine a distinction as the machinery can draw, and the loss is the same one the second lesson noted when "but" became $\land$ .

The laws

Ten laws do nearly all the work. Each can be checked in four or eight rows, and doing that once for each is the best hour available in this subject.

Law	Statement
Double negation	$\neg \neg P \equiv P$
Commutativity	$P \land Q \equiv Q \land P$ , and the same for $\lor$
Associativity	$(P \land Q) \land R \equiv P \land (Q \land R)$ , and the same for $\lor$
Idempotence	$P \land P \equiv P$ , $P \lor P \equiv P$
De Morgan	$\neg (P \land Q) \equiv \neg P \lor \neg Q$ , $\neg (P \lor Q) \equiv \neg P \land \neg Q$
Distribution	$P \land (Q \lor R) \equiv (P \land Q) \lor (P \land R)$ , and with $\land$ and $\lor$ swapped
Absorption	$P \land (P \lor Q) \equiv P$ , $P \lor (P \land Q) \equiv P$
Implication	$P \to Q \equiv \neg P \lor Q$
Contraposition	$P \to Q \equiv \neg Q \to \neg P$
Biconditional	$P \leftrightarrow Q \equiv (P \to Q) \land (Q \to P)$

Two of these deserve a second look. De Morgan is the law behind the second lesson's warning about "neither" and "not both": denying a conjunction gives a disjunction of denials, not a conjunction of them. It generalises the informal rule for negating English, that a negation pushed inward flips "and" to "or" and back.

Distribution is the one where the analogy with school algebra fails. In arithmetic, multiplication distributes over addition and addition does not distribute over multiplication. In logic both directions hold, so $P \lor (Q \land R) \equiv (P \lor Q) \land (P \lor R)$ as well. That symmetry is what makes it possible to convert freely between the two normal forms below.

Two more equivalences follow from the laws and are used constantly: $\neg (P \to Q) \equiv P \land \neg Q$ , which says a conditional is denied by asserting its antecedent and denying its consequent, and $P \to (Q \to R) \equiv (P \land Q) \to R$ , called exportation, which is how a rule with two conditions gets split or joined.

Pushing negations inward

The first thing to do with any formula is tidy it, and there is a standard destination for the tidying. A formula is in negation normal form when negations apply to atoms and to nothing else, so no $\neg$ sits in front of a bracket.

Getting there is a fixed procedure with no choices in it. Replace every $\leftrightarrow$ using the biconditional law, then every $\to$ using the implication law, then push each remaining negation inward with De Morgan, cancelling double negations as they appear. The procedure always terminates, because each De Morgan step moves a negation strictly closer to an atom and there are only finitely many places left to go.

Example. Simplify $\neg (P \land (Q \lor \neg R))$ until no negation applies to anything but an atom.

De Morgan on the outer negation gives $\neg P \lor \neg (Q \lor \neg R)$ . De Morgan again on the second disjunct gives $\neg P \lor (\neg Q \land \neg \neg R)$ , and double negation finishes it as

\neg P \lor (\neg Q \land R)

Three steps, each one law, and the result is in negation normal form.

Now you. Bring $\neg (P \to (Q \land R))$ to negation normal form.

Answer

Implication turns the inside into $\neg P \lor (Q \land R)$ , so the formula is $\neg (\neg P \lor (Q \land R))$ . De Morgan gives $\neg \neg P \land \neg (Q \land R)$ , and a second De Morgan with double negation gives

P \land (\neg Q \lor \neg R)

which says what the English would: the antecedent holds and the consequent fails.

Two standard shapes

Rewriting is more useful when it has a destination. Two shapes are standard.

A formula is in disjunctive normal form, or DNF, when it is a disjunction of conjunctions of literals, a literal being an atom or its negation. $(P \land \neg Q) \lor (Q \land R) \lor \neg P$ is in DNF. It is in conjunctive normal form, or CNF, when it is a conjunction of disjunctions of literals, and each of those disjunctions is called a clause.

The two shapes answer different questions at a glance. A DNF is satisfiable exactly when one of its conjunctions is free of an atom together with that atom's negation, so satisfiability is read off by inspection. A CNF is a tautology exactly when every clause contains some atom alongside its negation, so being a tautology is read off by inspection. Neither shape makes both questions easy, which is a hint about how hard the underlying problems are.

Reading a normal form off the table

Every formula has both forms, and no ingenuity is needed to find them, because the truth table hands them over directly.

For DNF, take each row where the formula is true and write the conjunction of literals describing that row, with an atom that is true appearing plain and one that is false appearing negated. Each such conjunction is true in its own row and false in every other, so their disjunction is true in exactly the rows the formula is. For CNF, work from the false rows instead, writing for each one the clause that rules it out by negating every literal of the row. Each clause is false only in its own row, so the conjunction is false in exactly the rows the formula is.

A formula true in no row has an empty DNF, and one true in every row has an empty CNF, which is the sensible boundary case rather than a defect.

Example. Put $(P \to Q) \land (Q \to R)$ into disjunctive normal form.

Its table has eight rows and the formula is true in four of them: all three atoms false; $P$ and $Q$ false with $R$ true; $P$ false with $Q$ and $R$ true; and all three true. Writing each row as a conjunction gives

(\neg P \land \neg Q \land \neg R) \lor (\neg P \land \neg Q \land R) \lor (\neg P \land Q \land R) \lor (P \land Q \land R)

which is correct and clumsy. The first two rows agree except on $R$ , and $R$ is true in one and false in the other, so together they say $\neg P \land \neg Q$ whatever $R$ does. The last two agree except on $P$ , so together they say $Q \land R$ . The formula reduces to

(\neg P \land \neg Q) \lor (Q \land R)

and that pairing-off of rows that differ in one atom is exactly the simplification that circuit designers do with Karnaugh maps.

Now you. Put $P \leftrightarrow Q$ into disjunctive normal form.

Answer

It is true in two rows, both atoms true and both false, so the DNF is

(P \land Q) \lor (\neg P \land \neg Q)

One connective is enough

A set of connectives is functionally complete when every truth function can be written using only those. Since every formula has a DNF, and a DNF uses only $\neg$ , $\land$ and $\lor$ , that set is complete: the two-line argument is the whole proof, and it also covers every truth function of any number of arguments, because the DNF construction never cared how many atoms there were.

The set shrinks. De Morgan turns $P \lor Q$ into $\neg (\neg P \land \neg Q)$ , so $\lor$ can go and ${\neg, \land}$ is complete. The implication law turns $\neg P \lor Q$ into $P \to Q$ , so ${\neg, \to}$ is complete too.

It shrinks to one. Write $P ↑ Q$ for "not both", the connective now called NAND. Then $\neg P$ is $P ↑ P$ , and $P \land Q$ is $(P ↑ Q) ↑ (P ↑ Q)$ , and with negation and conjunction available everything else follows. Henry Sheffer published this in 1913, and Charles Sanders Peirce had found it in 1880 in work that stayed unpublished until 1933. Its dual, NOR, works the same way, and of the sixteen binary truth functions those two are the only ones that are complete on their own. Emil Post settled the general question in 1921, classifying exactly which sets are complete.

This is not a curiosity. It is why NAND gates are the cheapest way to build hardware: one gate type, repeated, can compute any Boolean function, and integrated circuits are built out of exactly that repetition. It is also why flash memory is called NAND flash, after the gate arrangement of its cells.

Example. Express $P \lor Q$ using only $↑$ .

By De Morgan, $P \lor Q \equiv \neg (\neg P \land \neg Q)$ , and "not both" is what $↑$ already means, so $\neg (\neg P \land \neg Q)$ is $\neg P ↑ \neg Q$ . Substituting the NAND form of each negation gives

(P ↑ P) ↑ (Q ↑ Q)

Three gates, and a check on the row where both are false confirms it: each inner NAND gives true, and true NAND true is false, which is what $P \lor Q$ should be.

Now you. How many of the sixteen binary truth functions are functionally complete on their own?

Answer

Two, NAND and NOR. Every other binary function fails to be complete, most obviously $\land$ , $\lor$ , $\to$ and $\leftrightarrow$ , all of which give true when both inputs are true and so can never produce a formula false everywhere.

Where calculation runs out

Normal forms are the input to real machinery. Satisfiability of a CNF formula, the SAT problem, was the first problem shown NP-complete, by Stephen Cook in 1971 and independently by Leonid Levin, so every problem in NP can be encoded as a CNF and solved by a SAT solver. Modern solvers handle industrial instances with millions of clauses, and they are used to verify processor designs and to plan schedules, all of it downstream of the conversion in this lesson.

The honest limit is that conversion itself can explode. Distributing to turn a DNF into a CNF can square the number of clauses at each step, and formulas exist whose smallest CNF is exponentially larger than the original. The standard fix, Tseytin's transformation of 1970, introduces a new atom for each subformula and produces a CNF of linear size that is satisfiable exactly when the original is, which is enough for a solver even though it is not equivalent to the original.

And the deeper limit is unchanged from the previous lesson. Everything here still rests on columns of a table, whether or not the table is written out. Nothing yet lets you argue from premises to a conclusion in steps that a reader could follow and check. That is what the next lesson builds, and the equivalences here become the justification for its rules.