2
$\begingroup$

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?

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ Oct 4, 2014 at 19:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.