Normal forms of logical formulas

Propositional Logic: Logical consequence and consistency

Normal forms of logical formulas

Functional completeness A set \(\mathcal{C}\) of connectives is called functionally complete if any formula from propositional logic is equivalent to a formula using only connectives from \(\mathcal{C}\).

The set \(\{\neg, \land, \lor\}\) is functionally complete.

The formulas \(\varphi\rightarrow\psi\) and \(\neg\,\varphi\lor \psi\) are logically equivalent. The formulas \(\varphi\leftrightarrow\psi\) and \((\varphi\rightarrow\psi)\land(\psi\rightarrow\varphi)\) are logically equivalent. So in propositional logic we can do without the implication and equivalence connectives, as long a we keep the connectives \(\neg\), \(\land\), and \(\lor\).

The set \(\{\neg,\rightarrow\}\) is functionally complete.

The formulas \(\varphi\lor \psi\) and \(\neg\,\varphi\rightarrow \psi\) are logically equivalent. The formulas \(\varphi\land \psi \) and \(\neg(\varphi\rightarrow \neg\,\psi)\) are logically equivalent. So in propositional logic we can do without the disjunction, conjunction and equivalence connective, as long as we keep the connectives \(\neg\) and \(\rightarrow\).

We denote the exclusive disjunction connective with the symbol \(\oplus\) (or \(\veebar\)); the truth table of this connective is: \[\begin{array}{cc|c} \varphi & \psi & \varphi\oplus \psi \\ \hline 0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1\\ 1 & 1 & 0 \end{array}\] If we include in the alphabet of propositional logic the symbol \(\top\) for an always true statement (verum, a connective with no arguments), then the set \(\{\top, \oplus, \land\}\) is functionally complete.

The logical formulas \(\neg\,\varphi\) and \(\top \oplus \varphi\) are logically equivalent. The logical formulas \(\varphi\lor \psi\) and \((\varphi\oplus \psi)\oplus(\varphi\land \psi)\) are logically equivalent. are logically equivalent. So in propositional logic we can do without the disjunction, implication and equivalence connectives, as long as we keep the connectives \(\top\), \(\oplus\), and \(\land\).

Note that \(\top\oplus\top\) in this propositional logic is an always false statement. This is called falsum and usually notated with \(\bot\).

We define the neither connective with symbol \(\star\) via the truth table below \[\begin{array}{cc|c} \varphi & \psi & \varphi\star \psi \\ \hline 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0\\ 1 & 1 & 0 \end{array}\] For formulas \(\varphi\) and \(\psi\) we have that \(\varphi\star \psi\) and \(\neg\varphi\land\neg\psi\) are equivalent.

The collection \(\{\star\}\) is functionally complete.

The logical formulas \(\neg\,\varphi\) and \(\varphi\ast \varphi\) are logically equivalent. The logical formulas \(\varphi\lor \psi\) and \((\varphi\star \psi)\star(\varphi\star \psi)\) are logically equivalent. The logical formulas \(\varphi\land \psi\) and \(\bigl((\varphi\star \varphi)\star(\psi\star \psi)\bigr)\star\bigl((\varphi\star \varphi)\star(\psi\star \psi)\bigr)\) are logically equivalent. So we can do without the usual connectives in propositional logic if we introduce the neither connective \(\star\).

Normal forms A literal is a propositional letter or a negation of a propositional letter. We define the following normal forms of logical formulas.

Disjunctive normal form

A logic formula \(\varphi\) is in disjunctive normal form if \(\varphi\) is a disjunction of conjunctions of literals, i.e., has the following form \[\varphi=D_1\lor\ldots\land D_{n}\] where every disjunction part \[D_i=l_{i1}\land \ldots\land L_{im_i}\] is a conjunction of literals \(l_{i1},\ldots, L_{im_i}\).

A disjunctive normal form is full if each propositional variable occurs exactly once in each disjunction part.

Examples of formulas in normal form: \[p,\;\; \neg\,p,\;\; p\lor\neg\,q,\;\; \neg\,p\land q\text{ and }\] \[ (p\land r)\lor(\neg\,p\land r)\lor(\neg\,p\land\neg\, r)\] Examples of formulas that are not
are in disjunctive normal form: \[\neg\neg\,p\text{ and }\neg\,p\land(p\lor q)\] They are equivalent to the normal forms \[p\text{ and }\neg\,p\land q\] \(p\lor q\) is not complete, but is equivalent to the complete normal form \((p\land q)\lor (\neg\,p\land q)\lor (p\land\neg\,q)\).

Conjunctive normal form

A logical formula \(\varphi\) is in conjunctive normal form if \(\varphi\) is a conjunction of disjunctions of literals, i.e., has the following form \[\varphi=C_1\land\ldots\land C_{n}\] where every conjunction part \[C_i=l_{i1}\lor \ldots\lor L_{im_i}\] is a disjunction of literals \(l_{i1},\ldots, L_{im_i}\).

Examples of formulas in normal form: \[p,\;\; \neg\,p,\;\; p\land\neg\,q,\;\; \neg\,p\lor q\text{ and }\] \[ (p\lor r)\land(\neg\,p\lor r)\land(\neg\,p\lor\neg\, r)\] Examples of formulas that are not
are in cconjunctive normal form: \[\neg\neg\,p\text{ and }\neg\,p\lor(p\land q)\] They are equivalent to the normal forms \[p\text{ and }\neg\,p\lor q\]

Algebraic normal form

A logical formula \(\varphi\) is in algebraic normal form if \(\varphi\) is an exclusive disjunction of conjunctions of propositional variables or an exclusive disjunction of verum with such a formula, i.e., has the following form \[\varphi=C_1\oplus\ldots\oplus C_{n}\text{ or } \varphi=\top\oplus C_1\oplus\ldots\oplus C_{n}\] where each conjunction part \[C_i=P_{i1}\land \ldots\land P_{im_i}\] is a conjunction of propositional variables \(l_{i1},\ldots, L_{im_i}\).

Examples of formulas in algebraic normal form: \[p,\;\; \top\oplus\,p,\;\; p\land q,\;\; \top\oplus p\land q,\text{ and }\] \[ \top\oplus (p\land r)\oplus( p\land r)\] Examples of formulas that are not
are in algebraic normal form: \[\top\oplus (\top\oplus p)\text{ and }(\top\oplus p)\land(p\oplus q)\] They are equivalent to the normal forms \[p\text{ and }q\oplus(p\land q)\]

Transformations of logical formulas into normal form usually proceed through a series of applications of well-known tautologies such as De Morgan's rules, distributivity rules, and double negation. Every logical formula is logically equivalent with exactly one complete disjunctive normal form (except for associative and distributive rules)

The algebraic normal form is the simplest normal form because it is not necessary to work with literals, but only with propositional variables and the verum connective. Also, logically equivalent formulas have the same algebraic normal form. This makes it easier to check logical equivalence in an 'automatic theorem prover' than with the full disjunctive normal form.