# Conjunctive Normal Form

Is a statement of the form $\phi \vee \psi \vee \xi$ considered to be in its conjuntive normal form (CNF), given that $\phi \vee \psi$ is considered to be in CNF?

Example: While converting $\phi \wedge \psi \rightarrow \xi$ to its CNF, we get $\neg(\phi \wedge \psi) \vee \xi$ which gives $(\neg \phi) \vee \neg(\psi) \vee \xi$. Is this statement in its CNF?

Here's a definition of a clause adapted from Merrie Bergmann's An Introduction to Many-Valued and Fuzzy Logic p. 20:

1. A literal (a letter or negation of a letter) is a clause.
2. If P and Q are clauses, then (P $\lor$ Q) is a clause.

Definition of conjunctive normal form.

1. Every clause is in conjunctive normal form.
2. If P and Q are in conjunctive normal form, then (P$\land$Q) is in conjunctive normal form.

So, even though ϕ∨ψ∨ξ is not in conjunctive normal form (note the parentheses),

((ϕ∨ψ)∨ξ) is in conjunctive normal form and

(ϕ∨(ψ∨ξ)) is also in conjunctive normal form.

Demonstration:

Suppose that ϕ, ψ, and ξ are literals. Since ϕ, and ψ are literals, and literals are clauses, by definition of a clause and detachment, (ϕ∨ψ) is a clause. Since ξ is a literal, ξ is a clause. Thus, by definition of a clause and detachment, ((ϕ∨ψ)∨ξ) is a clause. Since every clause is in conjunctive normal, ((ϕ∨ψ)∨ξ) is in conjunctive normal form.

One can similarly show that ((ϕ∨ψ)∨ξ) is a clause by building it up from its literals using part 2. of the above definition of a clause, and invoking the definition of conjunctive normal form to infer that ((ϕ∨ψ)∨ξ) is a clause.

• This is true from a technical point of view - "$A \lor B \lor C$" isn't literally a formula, so it's not in CNF. But the normal linguistic convention is to ignore the lack of parentheses, because of the associativity of $\lor$. So most people would ignore the fact that $A\lor B\lor C$ isn't a formula, and they would say it is in CNF. This sort of convention is present throughout logic - we typically don't write all the parentheses that are formally required, just enough to specify the formula up to tautological equivalence. Oct 4, 2014 at 19:02