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 American Constitution, one of the few modern political documents drawn up by men who were forced by the sternest circumstances to think out what they really had to face instead of chopping logic in a university classroom.”
    —George Bernard Shaw (1856–1950)