Algorithm to Find CNF for a Formula

definitionlogic

Definition

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

Step 1

Make a truth table for $\phi$.

Step 2

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

Note that if there are no rows with $\phi$ getting value $0$, so $\phi$ is a tautology, then we can take $p\vee \neg p$.

Step 3

Take conjunction of these disjunctions.

Examples