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

How can I convert this equation to CNF?

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

4 Answers

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 (⇒).

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)

Might I suggest this? There is an algorithm for conversion on the page.

Conjunctive Normal Form

I have implemented a small tool in Java that can do basic transformation from a boolean expression into (C|D)NF. If you are interested, you might want to have a look at . The implementation is based on these lecture notes. A more detailed description can be found here. Any feedback would be greatly appreciated ;-).