Motivation
A logical expression can be presented in several ways without changing what it says. A truth table makes that meaning explicit, while a clause representation makes it possible to search systematically for a satisfying assignment. These representations do not have the same size: a direct table may be exponentially larger than the formula we started with.
We develop two exact normal forms and a resolution procedure with a model-preserving proof. We then introduce auxiliary variables carefully: a compact encoding may preserve the existence of a solution without being the same formula over the same variables.
Assignments and equivalence
Definition 12.1.1
(Assignment, equivalence, satisfiability and validity)
Fix a finite list of distinct Boolean variables. An assignment gives each listed variable one of the values false or true. The connectives , and have their usual truth-functional meanings; constants and denote false and true. Define implication and biconditional by
Two formulas and are equivalent, written , if they have the same value on every assignment to all variables occurring in either formula. A formula is satisfiable if at least one assignment makes it true; it is valid if every assignment does. Thus exactly when is valid.
An equivalent replacement inside a larger formula preserves the larger formula's value: prove this by induction on the surrounding connectives.
Definition 12.1.2
(Literals, clauses, terms and normal forms)
A literal is a variable or its negation. A clause is a finite disjunction of literals; a term is a finite conjunction of literals. Conjunctive normal form (CNF) is a conjunction of clauses, and disjunctive normal form (DNF) is a disjunction of terms. Repeated literals or clauses may be removed. A clause containing both a variable and its negation is true and can be deleted from a conjunction; a term containing both is false and can be deleted from a disjunction.
The empty clause is and the empty term is . An empty conjunction of clauses is ; an empty disjunction of terms is . These conventions make formulas with no variables and elimination boundary cases behave consistently.
Theorem 12.1.3
(Every truth table has two exact normal forms)
Given a formula on a declared list of variables, there are equivalent DNF and CNF formulas over that same list. The canonical DNF has one term for each true row, while the canonical CNF has one clause for each false row. There are rows, including one row when .
Constructing the normal forms
Proof
(Isolating one row at a time)
For each assignment , form a term containing each variable positively when its value under is true and negatively when that value is false. This term is true on exactly the row . Disjoin the terms belonging to the true rows: the result has exactly the same truth table as the original formula. If there are no true rows, use the empty disjunction .
For the CNF, instead form a clause false on exactly : include a variable negatively when it is true on the row and positively when it is false. Conjoin the clauses for all false rows. A different assignment satisfies each such clause, so the conjunction rejects precisely the original false rows. If there are none, use the empty conjunction . When , the unique row yields an empty term or an empty clause as appropriate.
Proof X-ray
One row, one exact test
The only idea is that one row can be isolated by a single test. A term built from a true row is a conjunction of literals that all match , so it is true at and at no other row: any other row differs from in some variable and falsifies the corresponding literal. A clause built from a false row uses the opposite signs, so every literal is false at and the clause is false exactly there; any other row satisfies the literal on a variable where it differs. The signs flip because a conjunction fails as soon as one literal fails, whereas a disjunction fails only when all literals fail. The argument closes because a formula is determined by its truth table: disjoining the terms of all true rows, or conjoining the clauses of all false rows, reproduces every row. Only finiteness of the variable list is used.
The construction proves existence and gives an explicit algorithm, but may write up to literal occurrences. A short original formula can have a much shorter noncanonical normal form; a truth-table construction is an upper bound, not a claim of smallest size. Conversely, an algorithm that writes a large explicit normal form must pay for that output, regardless of how short the input was.
An equivalence claim can be disproved by a single assignment on which the two values differ. Proving it by a truth table requires checking every row, including assignments to variables that appear in only one formula. This distinction turns a proposed algebraic rewrite into a testable semantic statement.
The familiar identities and can also be checked on all rows of their two- or three-input truth tables. Substitution then permits applying them within larger formulas. Such rewriting is useful, but a chosen sequence of distributive steps need not minimize the resulting expression.
Resolution and exact elimination
Definition 12.1.4
(Resolvent)
Let and be clauses, where neither nor contains . Their resolvent is the clause .
The resolvent is implied by its two parents: any assignment satisfying both parent clauses satisfies it, because if both and were false, the parents would require opposite values for .
Concept lensGeometric
Clauses as forbidden subcubes
View the assignments as the corners of the -dimensional cube. A clause with literals on distinct variables forbids exactly the assignments that make all its literals false, and these form a subcube of dimension ; a CNF is satisfied precisely by the corners that avoid every forbidden subcube. In this picture the resolvent of and forbids the corners where and are both false, and each such corner already lies in the region forbidden by the first parent (when is false) or by the second (when is true). Soundness of resolution says that the new forbidden region is covered by the two old ones.
Definition 12.1.5
(Elimination of a variable)
Given a CNF, first discard tautological clauses and duplicate literals. To eliminate , keep every clause not containing and add every resolvent obtained by pairing a clause with a clause . Then discard all clauses that contain or and delete tautological resolvents. If either side has no clauses, no pairs are added. Empty clauses are retained.
Theorem 12.1.6
(Resolution is existential projection)
For every assignment to the remaining variables, the eliminated CNF is true exactly when some choice of makes the original CNF true. Consequently elimination preserves satisfiability, and after all variables are eliminated the original CNF is unsatisfiable exactly when the empty clause remains.
Proof
(Choosing a value for the eliminated variable)
The forward direction is a construction of a value for . Fix an assignment satisfying all retained clauses and resolvents. If some positive parent has false, every negative parent must have true, or its resolvent with that positive parent would be false. Set true: all positive parents hold and all negative parents hold through their parts. If no positive parent has false, set false: all positive parents hold through their parts and all negative parents hold through . This also covers an empty positive or negative family.
Conversely, a satisfying value of makes every retained clause and every resolvent true, since each resolvent is implied by its two parents. This proves the row-by-row projection claim. Inductively eliminating all variables preserves existence of a model. At the end there are no literals: every remaining nonempty clause is impossible, so the result is either an empty conjunction, which is true, or a conjunction containing the empty clause, which is false. Each generated resolvent is a consequence of earlier clauses; if an empty clause is generated, the generation history is a finite refutation certificate.
Proof X-ray
Resolvents are the only obstructions
The non-obvious move is to read the resolvents as the only obstructions to choosing . Setting true works exactly when every negative parent has its true; setting false works exactly when every positive parent has its true. Both choices fail only when some positive parent has false and some negative parent has false, and then their resolvent is false. The hypothesis that and do not contain is used so that their values do not depend on the choice of . Discarded tautological resolvents are true anyway, and an empty family on either side makes the corresponding choice automatic, which is why the proof needs no separate boundary case.
A parent pair can produce a tautological resolvent such as ; discarding it imposes no condition. In the worst case, pairwise generation creates many clauses, so this proof does not make unrestricted SAT a polynomial-time problem. The order of eliminating variables can change intermediate size even though the final satisfiability answer is unchanged.
Counterexample mode
Resolving on two variables at once is unsound
Claim: from and one may cancel both pairs of opposite literals and derive the empty clause. The assignment makes both clauses true, while the empty clause is false under every assignment, so the derivation would be unsound. The definition of resolvent allows one variable at a time; here and contain the second variable, and the resolvent on is the tautology , which carries no information.
Auxiliary variables: a different guarantee
Suppose a formula is represented by an acyclic expression graph with gates, each computing AND, OR or NOT. Introduce one fresh variable for each gate and clauses enforcing that variable's gate value. For example, is equivalent to
Use the analogous constant-size clauses for OR and NOT, then assert the output gate with a unit clause. Constants, a literal output and an empty gate graph can be handled directly. There are clauses and literal occurrences, assuming constant fan-in and counting only gates and used input-variable references.
Theorem 12.1.7
(Gate encoding is exact under existential projection)
Let a formula be given by an acyclic gate graph, and let be the CNF consisting of the clauses defining every gate together with the unit clause asserting the output gate. For every assignment to the original variables, exactly one assignment to the gate variables satisfies all gate-defining clauses, and has a satisfying extension of exactly when the original formula is true at .
Proof
(Evaluating the gates in topological order)
For every assignment to the original variables, topological evaluation supplies exactly one assignment to the gate variables that satisfies all gate definitions. The output unit is then true exactly when the original formula is true. Conversely, any satisfying assignment of the clauses must agree with those gate evaluations. Therefore the original formula is true on an input assignment exactly when there exists an extension satisfying the new CNF.
This is stronger than mere global equisatisfiability, but it is not equivalence under every arbitrary assignment to the new variables.
Counterexample mode
A fresh variable is not a free replacement
The formulas and are equisatisfiable: each has a model. They are not equivalent on the combined variables, since true and false separates them. The existence of a suitable extension is a quantified statement, not permission to assign the new variable arbitrarily.
Worked examples
Worked example 12.1.8
(Exclusive or by rows)
For variables , exclusive or is true on and . Its canonical DNF is . The false rows are and , giving canonical CNF .
Worked example 12.1.9
(Eliminate one variable)
From , eliminating produces the single clause . If both and are false, the original requires both values of ; otherwise choose a value satisfying both clauses. The original and the result are not equivalent as formulas on assignments including : the result records existence of a suitable .
Worked example 12.1.10
(A complete refutation)
The clauses , and resolve on to and . Resolving these on yields the empty clause. Thus no assignment satisfies the original three clauses; the three resolution steps are a checkable derivation, not merely a failed search trace.
Common mistakes and scope
Common mistake
(Elimination is not equivalence)
Eliminating from gives . This is true when and are true and is false, although the original formula is false there. Elimination preserves the existence of a suitable value of , not the formula's value for each fixed value of .
Common mistake
(Stopping before the elimination is finished)
Eliminating from keeps and adds the resolvent . The result contains no empty clause, yet the original clauses are unsatisfiable: only after is eliminated does the empty clause appear. A resolution refutation proves unsatisfiability, but the absence of an empty clause at an intermediate stage proves nothing.
Do not infer validity from the existence of one satisfying row, and do not read a CNF as a single disjunction: a CNF is false as soon as one clause is false.
All constructions concern finite propositional formulas and finite variable lists. They do not by themselves prove a polynomial SAT algorithm, first-order completeness, or a bound on the smallest equivalent CNF. The auxiliary encoding has linear output in the expression graph, but deciding its satisfiability remains a separate task.
Summary
Rows of a truth table construct equivalent DNF and CNF over the original variables. Resolution projects a CNF one variable at a time while preserving exactly the extendable assignments. Fresh gate variables provide a compact CNF whose existential projection is the original formula; their values cannot be ignored when claiming equivalence.
Exercises
Quick check
(Write the canonical CNF for over and state its false row.)
Solution · Answer
Implication is false only when is true and is false. Its canonical CNF is the single clause , false on precisely that row.
Quick check
(Eliminate from . Explain why no new resolvent is needed.)
Solution · Answer
There are no negative parents, so no parent pairs and no resolvents. Delete the two positive parents and retain . Whenever holds, setting true satisfies the original clauses for any values of ; if fails, no value of helps.
Quick check
(What are the canonical DNF and CNF of with an empty variable list? What remains after eliminating from the clauses and ?)
Solution · Answer
There is one assignment to the empty list, and is false there. Its canonical DNF is the empty disjunction ; its canonical CNF is the conjunction of one empty clause, also . Resolving the unit clauses and yields the empty clause, which remains after elimination.
Quick check
(For the three clauses defining , determine the only valid value of when is false. Why is the encoding not equivalent to on arbitrary assignments to ?)
Solution · Answer
If is false, forces false; the other two clauses then hold for either value of . As a formula over all three variables the gate definition is true when are all false, but is false there. The output unit clause is what selects inputs for which the gate's value is true.