Normal forms · Topos Uranos

Summary

One and the same truth function admits infinitely many formulas that represent it, and none of them, taken at random, lets one see what it says. This lesson fixes two moulds into which every formula fits up to equivalence: the disjunctive normal form, a disjunction of conjunctions of literals, and the conjunctive normal form, a conjunction of disjunctions of literals. It defines literals, clauses and elementary conjunctions; it proves that negation turns one form into the other when each literal is changed into its opposite, which is the duality between the two; it builds the canonical forms from the truth table and proves that they are unique. The existence theorem receives two proofs: by the table, as a corollary of functional completeness, and by induction on complexity, with the single case of joint denial and with the double hypothesis that this proof requires. At the end it shows why they are worth the effort: the validity of a conjunctive form and the satisfiability of a disjunctive one are decided at a glance.

Learning objectives

Recognize literals, clauses, elementary conjunctions and formulas in disjunctive or conjunctive normal form, distinguishing form, which is a property of the string, from equivalence, which is a property of the meaning.
Build from the truth table the disjunctive and conjunctive canonical forms of a formula, and prove that the canonical form is unique and that it determines the equivalence class of the formula.
Prove by induction on complexity that every formula is equivalent to a disjunctive normal form and to a conjunctive one, using duality, the generalized De Morgan and distributive laws and semantic replacement.
Decide at a glance the validity of a conjunctive normal form and the satisfiability of a disjunctive one, and apply normal forms to semantic consequence and to measuring the minimum size of a normal form.

In the previous lessons of this unit the formulas were given a meaning: the lesson on the semantics of propositional logic extended each valuation to all formulas; the lesson on semantic consequence and equivalence defined the equivalence $\varphi \eqsem \psi$ and proved semantic replacement; the lesson on the generalized De Morgan and distributive laws extended those laws to conjunctions and disjunctions of $n$ formulas; and the lesson on functional completeness showed that every truth function is represented by some formula. Now, a truth function is represented by infinitely many formulas, which may be very different from one another: $(v_1 \rightarrow v_2)$ , $\neg(v_1 \wedge \neg v_2)$ and $(((v_1 \downarrow v_1) \downarrow v_2) \downarrow ((v_1 \downarrow v_1) \downarrow v_2))$ are three names of the same thing. If this is so, it is convenient to choose in each equivalence class a representative of fixed form, which can be read without effort and with which certain questions are answered by looking. That is what normal forms are.

Literals, clauses and normal forms

Recall, from the lesson on the generalized laws, the notation for the conjunction and the disjunction of $n$ formulas, defined by recursion and associating to the left; that of a single formula is the formula itself.

\bigwedge_{i=1}^{1} \varphi_i = \varphi_1, \qquad \bigwedge_{i=1}^{n + 1} \varphi_i = \left( \bigwedge_{i=1}^{n} \varphi_i \wedge \varphi_{n + 1} \right)

\bigvee_{i=1}^{1} \varphi_i = \varphi_1, \qquad \bigvee_{i=1}^{n + 1} \varphi_i = \left( \bigvee_{i=1}^{n} \varphi_i \vee \varphi_{n + 1} \right)

In the same lesson it was proved that the order and the grouping of the terms do not alter the formula up to equivalence (generalized associativity and independence of order and of repetitions); for that reason we shall also write $\varphi_1 \wedge \varphi_2 \wedge \cdots \wedge \varphi_n$ without parentheses, with the grouping understood to the left.

A literal is a variable $v_n$ , which is called a positive literal, or the negation $\neg v_n$ of a variable, which is called a negative literal. The opposite of a literal $\ell$ , which we write $\ell^{*}$ , is the literal of the same variable and of the other sign:

\ell = v_n \;\Rightarrow\; \ell^{*} = \neg v_n, \qquad \ell = \neg v_n \;\Rightarrow\; \ell^{*} = v_n

It follows from the definition that $(\ell^{*})^{*} = \ell$ . Two literals form a complementary pair if one is the opposite of the other, like $v_3$ and $\neg v_3$ .

A clause is a disjunction of literals, $\bigvee_{j=1}^{k} \ell_j$ , and an elementary conjunction is a conjunction of literals, $\bigwedge_{j=1}^{k} \ell_j$ , with $k \geq 1$ in both cases; a single literal is, therefore, at once a clause and an elementary conjunction. A literal is said to be in a clause or in an elementary conjunction if it is one of its $\ell_j$ .

A formula is in disjunctive normal form if it is a disjunction of elementary conjunctions, and in conjunctive normal form if it is a conjunction of clauses; that is, if it is, respectively, of one of the following two forms, where $m$ and $k_1, \ldots, k_m$ are natural numbers and each $\ell_{i,j}$ is a literal:

\bigvee_{i=1}^{m} \bigwedge_{j=1}^{k_i} \ell_{i,j}, \qquad \bigwedge_{i=1}^{m} \bigvee_{j=1}^{k_i} \ell_{i,j}

We shall say that $\Phi$ is a disjunctive normal form of $\varphi$ if it is in disjunctive normal form and $\varphi \eqsem \Phi$ , and likewise for the conjunctive one. The lengths $k_i$ may vary from one conjunction (or clause) to another: requiring the same number of literals in all of them would force padding with repetitions and would add nothing.

ExampleWhat is and what is not in normal form

The formula $(v_1 \wedge \neg v_2) \vee \neg v_3$ is in disjunctive normal form, with $m = 2$ , $k_1 = 2$ and $k_2 = 1$ ; it is not in conjunctive form, because it is not a conjunction (its two components are distinct, and a conjunction is a double negation), nor is it a clause: read as a disjunction, it has a term, $(v_1 \wedge \neg v_2)$ , which is neither a literal nor a disjunction of literals. The formula $v_1 \wedge \neg v_2 \wedge v_3$ is in both forms: as a disjunction of a single elementary conjunction ( $m = 1$ ) and as a conjunction of three clauses of one literal each. In the same way, $(\neg v_1 \vee v_2)$ is at once a clause, that is, a conjunctive form with $m = 1$ , and a disjunctive form of two conjunctions of one literal.

(v_1 \wedge \neg v_2) \vee \neg v_3, \qquad v_1 \wedge \neg v_2 \wedge v_3, \qquad \neg v_1 \vee v_2

On the other hand, $(v_1 \downarrow v_2)$ and $\neg(v_1 \rightarrow v_2)$ are in neither of the two forms, although the first is equivalent to $(\neg v_1 \wedge \neg v_2)$ and the second to $(v_1 \wedge \neg v_2)$ , which are.

(v_1 \downarrow v_2) \eqsem \neg v_1 \wedge \neg v_2, \qquad \neg(v_1 \rightarrow v_2) \eqsem v_1 \wedge \neg v_2

It is worth pausing on what “being in normal form” means. It is a property of the string of circles and disks, not of its meaning: the lesson on induction on the natural numbers and on formulas proved unique readability, so that asking whether a formula is a disjunction, and of what, has a single answer. Now, the official abbreviations make some formulas be in normal form without looking like it. The implication $(v_1 \rightarrow v_2)$ is defined as $(\neg v_1 \vee v_2)$ : it is not that it is equivalent to that clause, but that it is that very string, and therefore it is already in normal form. More surprising is double negation. By the definitions of $\neg$ and of $\vee$ , the string $(\varphi \vee \varphi)$ is $\neg(\varphi \downarrow \varphi)$ , that is, $\neg\neg\varphi$ ; hence $\neg\neg v_1$ is not a literal, but it is, symbol by symbol, the clause $(v_1 \vee v_1)$ .

(\varphi \vee \varphi) = \neg(\varphi \downarrow \varphi) = \neg\neg\varphi

The value of conjunctions and disjunctions

From the lesson on semantics we take the values of the defined connectives: $v(\neg\varphi) = 1 - v(\varphi)$ ; $v(\varphi \wedge \psi) = v(\varphi)\,v(\psi)$ , which equals $1$ if and only if both equal $1$ ; and $v(\varphi \vee \psi) = 0$ if and only if both equal $0$ . The lesson on the generalized De Morgan and distributive laws extended them to $n$ formulas, by induction on the number of terms, in the value lemma: for every valuation $v$ , the conjunction $\bigwedge_{i=1}^{n} \varphi_i$ takes the value $1$ under $v$ if and only if each $\varphi_i$ takes the value $1$ under $v$ , and the disjunction $\bigvee_{i=1}^{n} \varphi_i$ takes the value $1$ under $v$ if and only if some $\varphi_i$ takes the value $1$ under $v$ . That lemma, which is cited here without repeating its proof, is the instrument with which the value of any normal form is computed.

LemmaNegation of a literal

For every literal $\ell$ , the negation of $\ell$ is equivalent to its opposite, $\neg\ell \eqsem \ell^{*}$ ; in particular, $v(\ell^{*}) = 1 - v(\ell)$ for every valuation $v$ .

Proof

$\ell = v_n \;\Rightarrow\; \neg\ell = \neg v_n = \ell^{*}$
If $\ell$ is a variable $v_n$ , its opposite is $\neg v_n$ , which is exactly the string $\neg\ell$ : there is nothing to prove.
$\ell = \neg v_n \;\Rightarrow\; \neg\ell = \resaltar{\neg\neg v_n} \eqsem v_n = \ell^{*}$
If $\ell$ is $\neg v_n$ , its negation is $\neg\neg v_n$ , which is not a literal; by the law of double negation (lesson on semantic consequence and equivalence), it is equivalent to $v_n$ , which is the opposite of $\ell$ .
$v(\ell^{*}) = v(\neg\ell) = 1 - v(\ell)$
In both cases, $\ell^{*}$ and $\neg\ell$ have the same value under every valuation, and that of $\neg\ell$ is given by the value of negation.

The second case is easy to overlook: when negating a normal form one tends to write $\neg\ell_{i,j}$ instead of a literal, and $\neg\neg v_n$ is not one. Double negation is what brings the result back into the mould.

LemmaElementary conjunctions and clauses

An elementary conjunction is satisfiable if and only if it contains no complementary pair. A clause is valid if and only if it contains some complementary pair.

Proof

$v(\ell)\,v(\ell^{*}) = v(\ell)\,(1 - v(\ell)) = 0$
If an elementary conjunction contains $\ell$ and $\ell^{*}$ , under every valuation one of the two takes the value $0$ , by the previous lemma; by the value lemma, the conjunction takes the value $0$ under every valuation.
$\dato{val}{v_n = \ell_j \;\Rightarrow\; v(v_n) = 1, \qquad \neg v_n = \ell_j \;\Rightarrow\; v(v_n) = 0}$
If it contains no complementary pair, one defines a valuation that gives $1$ to each variable that is in it as a positive literal and $0$ to each variable that is in it as a negative literal (to the others, $0$ ). The definition is not contradictory, because no variable is in it in both ways.
$v\left( \bigwedge_{j=1}^{k} \ell_j \right) = 1$
Under that valuation all its literals take the value $1$ , and by the value lemma the conjunction takes the value $1$ : it is satisfiable.
$v(\ell) + v(\ell^{*}) = 1$
If a clause contains $\ell$ and $\ell^{*}$ , under every valuation one of the two takes the value $1$ , and the clause takes the value $1$ : it is valid.
$v\left( \bigvee_{j=1}^{k} \ell_j \right) = 0$
If it contains no complementary pair, the valuation that gives $0$ to its positive variables and $1$ to its negated variables makes all its literals take the value $0$ ; by the value lemma, the clause takes the value $0$ under it and is not valid.

In the rest of this lesson

The duality between the two forms
The canonical forms, from the table
Existence by induction on complexity
What can be seen at a glance
Solved problems
A variable that goes along with one of the other two
The normal forms of a double joint denial
The hypothetical syllogism, by normal forms
Parity admits no short forms
Monotone formulas
Proposed problems
The canonical form when a variable is added
A consequence at a glance
A valid disjunctive form
Parity in conjunctive form
The variables on which a formula does not depend