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)

    “We want in every man a long logic; we cannot pardon the absence of it, but it must not be spoken. Logic is the procession or proportionate unfolding of the intuition; but its virtue is as silent method; the moment it would appear as propositions and have a separate value, it is worthless.”
    —Ralph Waldo Emerson (1803–1882)