is a tautology.

Conversely, a DNF formula is satisfiable if, and only if, one of its conjunctions is satisfiable. This can be decided in polynomial time simply by checking that at least one conjunction does not contain conflicting literals.

Variants

An important variation used in the study of computational complexity is k-DNF. A formula is in k-DNF if it is in DNF and each conjunction

1.Previous
3.Next