0
8.3kviews
Explain the steps involved in conveying the propositional logic statement into CNF with a suitable example.
1 Answer
0
547views

CNF in first order logic

  1. Eliminate implications $\Leftrightarrow$, ⇒
  2. Reduce the scope of $\neg$

    » de Morgan’s laws

    ¬(w1 $\vee$ w2) $\equiv$ ¬w1 $\wedge$ ¬w2

    ¬(w1 $\wedge$ w2) $\equiv$ ¬w1 $\vee$ ¬w2

    » Elimination of repeated negations (¬ ¬w $\equiv$ w)

    » Combination of ¬ with quantifiers.

    ¬($\forall$ x) w(x) $\equiv$ ($\exists$ x) ¬w(x)

    ¬($\exists$ x) w(x) $\equiv$ ($\forall$ x) ¬w(x)

  3. Standardize variables: Rename variables so that each different variable in the set of wffs has a different symbol :$(\forall x)[P(x)⇒R(x)]]\vee[(\exists x)P(x)]\vee[(\forall x)[P(x)⇒R(x)]]\vee[(\exists y)P(y)]$

  4. Skolemization: Eliminate existential quantifiers and replace existentially quantized variables by Skolem consants or Skolem functions as appropriate.

  5. Convert to prenex form by moving all universal quantifiers to the beginning of the wff.

    wff in prenex form = Prefix (string of quantifiers) + Matrix (quantifier-free formula)

  6. Drop universal quantifiers.

  7. Use distributive laws and equivalence rules of propositional logic to transform the matrix to CNF.

    Example Conversion to CNF

    $[(\forall x) Q(x)]⇒ (\forall x)(\forall y) [(\exists z) [P(x,y,z) ⇒ (\forall u) R(x,y,u,z)]$

    1. Eliminate implications $\Leftrightarrow$, ⇒

      $¬[(\forall x) Q(x)]\vee$

      $(\forall x)(\forall y) [(\exists z) [¬P(x,y,z) \vee (\forall u) R(x,y,u,z)]$

    2. Reduce scope of negations:

      $[(\exists x) ¬Q(x)] \vee \\ (\forall x)(\forall y) [(\exists z) [¬P(x,y,z) \vee (\forall u) R(x,y,u,z)]$

    3. Standardize variables

      $[(\exists w) ¬Q(w)] \vee \\ (\forall x)(\forall y) [(\exists z) [¬P(x,y,z) \vee (\forall u) R(x,y,u,z)]$

    4. Skolemization:

      $¬Q(A)\vee(\forall x,y)[¬P(x,y,f(x,y))\vee(\forall u)R(x,y,u,f(x,y))]$

    5. Prenex form:

      $(\forall x,y,u)[¬Q(A)\vee ¬P(x,y,f(x,y))\vee R(x,y,u,f(x,y))]$

    6. Drop universal quantifiers

      $¬Q(A)\vee ¬P(x,y,f(x,y)) \vee R(x,y,u,f(x,y))$

    7. Convert to CNF:

      wff already in CNF.

Please log in to add an answer.