Disjunctive Normal Form and satisfiable is in P (DNFSAT)

Question

I am reading that a language that is in Disjunctive Normal Form and is satisfiable is a language in P, but there is no explanation, could anyone tell me why?

Answer 1

To make an expression that is in DNF be true, you just need to make a single disjunctive clause of it true. A typical clause would be something like A ^ B ^ ~C or something like that, and so you set A and B to true and C to false.

So the algorithm would be:

1. Find some disjunctive clause that is not self-contradictory. (I.e. it contains both X and ~X).
2. If all the disjunctive clauses contain some self-contradiction, then the entire expression cannot be satisfied.
3. If there is even one clause that doesn't self-contradict, then there is an obvious assignment of variables that makes that clause be true. In that case the entire expression is true.