Introduction to Artificial Intelligence - Old Questions

A sentence that is expressed as a conjunction of disjunction of literals is said to be in conjunctive normal form (CNF). E.g. (P∨Q)∧(P∨R)

CNF conversion steps

1. Eliminate ↔ rewriting P↔Q as (P→Q)∧(Q→P)

2. Eliminate → rewriting P→Q as ¬P∨Q

3. Use De Morgan‘s laws to push ¬ inwards:

        - rewrite ¬(P∧Q) as ¬P∨¬Q

        - rewrite ¬(P∨Q) as ¬P∧¬Q

4. Eliminate double negations: rewrite ¬¬P as P

5. Use the distributive laws to get CNF:

        - rewrite P∨(Q∧R) as(P∨Q)∧(P∨R)

6. Use:

        - (P∧Q) ∧ R as P∧Q ∧ R

        - (P∨Q)∨R as P∨Q∨R

E.g. Converting to CNF