Algorithm to Find DNF for a Formula

definitionlogic

Definition

In order to find a DNF for a formula $\phi$,

Step 1

Make a truth table for $\phi$.

Step 2

For each row in which $\phi$ gets value $1$, form a conjunction consisting of each variable in row with value $1$ and the negation of each variable with value $0$.

Note that if there are no rows with $\phi$ getting value $1$ ($\phi$ is a contradiction), then just take $p\wedge \neg p$.

Step 3

Take disjunction of these conjunctions.

Examples