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)

    “It is the logic of our times,
    No subject for immortal verse—
    That we who lived by honest dreams
    Defend the bad against the worse.”
    —Cecil Day Lewis (1904–1972)