Introduction to Artificial Intelligence - Old Questions

8.  Why disjunctive normal form is required? Explain all the steps with examples.

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

DNF 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 DNF:

        - 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