Conjunctive Normal Form - Converting From First-order Logic

Converting From First-order Logic

To convert first-order logic to CNF:

  1. Convert to negation normal form.
    1. Eliminate implications: convert to
    2. Move NOTs inwards by repeatedly applying DeMorgan's Law. Specifically, replace with ; replace with ; and replace with .
  2. Standardize variables
    1. For sentences like (∀x P(x)) ∨ (∃x Q(x)) which use the same variable name twice, change the name of one of the variables. This avoids confusion later when we drop the quantifiers. For example, from ∀x ∨ . we obtain: ∀x ∨ .
  3. Skolemize the statement
    1. ∃x P(x) into P(A), where A is a new constant (consult linked article for more details)
  4. Drop universal quantifiers
  5. Distribute ORs over ANDs.

Read more about this topic:  Conjunctive Normal Form

Famous quotes containing the words converting and/or logic:

    “A way of certifying experience, taking photographs is also a way of refusing it—by limiting experience to a search for the photogenic, by converting experience into an image, a souvenir. Travel becomes a strategy for accumulating photographs.”
    —Susan Sontag (b. 1933)

    “The logic of the world is prior to all truth and falsehood.”
    —Ludwig Wittgenstein (1889–1951)