How to convert a propositional formula to conjunctive normal form (CNF)?

Question

How can I convert this equation to CNF?

¬((p ∨ ¬Q) ⊃ R) ⊃ (P ∧ R))

Solution 1

To convert a propositional formula to conjunctive normal form, perform the following two steps:

1. Push negations into the formula, repeatedly applying De Morgan's Law, until all negations only apply to atoms. You obtain a formula in negation normal form.

   • ¬(p ∨ q) to (¬p) ∧ (¬q)

   • ¬(p ∧ q) to (¬p) ∨ (¬q)

2. Repeatedly apply the distributive law where a disjunction occurs over a conjunction. Once this is not possible anymore, the formula is in CNF.

   • p ∨ (q ∧ r) to (p ∨ q) ∧ (p ∨ r)

To obtain a formula in disjunctive normal form, simply apply the distribution of ∧ over ∨ in step 2.

Note about ⊂

The subset symbol (⊂) used in the question is just an alternative notation for the logical implication/entailment, which is usually written as an arrow (⇒).

Solution 2

http://en.wikipedia.org/wiki/Conjunctive_normal_form

To convert first-order logic to CNF:

1. Convert to Negation normal form.
   1. Eliminate implications: convert x → y to ¬ x ∨ y
   2. Move NOTs inwards.
2. Standardize variables
3. Skolemize the statement
4. Drop universal quantifiers
5. Distribute ANDs over ORs.

(Artificial Intelligence: A modern Approach [1995...] Russel and Norvig)