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

math artificial-intelligence boolean-logic
lana picture lana · Mar 17, 2009 · Viewed 49k times · Source

How can I convert this equation to CNF?

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

Answer

ziggystar picture ziggystar · Mar 2, 2012

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

Related questions

How to update the bias in neural network backpropagation?

Could someone please explain to me how to update the bias throughout backpropagation? I've read quite a few books, but can't find bias updating! I understand that bias is an extra input of 1 with a weight attached to it (for …

Read More
Unsupervised clustering with unknown number of clusters

I have a large set of vectors in 3 dimensions. I need to cluster these based on Euclidean distance such that all the vectors in any particular cluster have a Euclidean distance between each other less than a threshold "T". I …

Read More
Derivative of sigmoid

I'm creating a neural network using the backpropagation technique for learning. I understand we need to find the derivative of the activation function used. I'm using the standard sigmoid function f(x) = 1 / (1 + e^(-x)) and I've seen that its derivative …

Read More