Any proposition is equivalent to a formula in CNF.

120 Views Asked by At

A proposition is said to be in conjunctive normal form (CNF) if it is $\land_{i=1}^{k}\lor_{j=1}^{n} \psi_{ij}$ where each $\psi_{ij}$ is either an atom or is the negation of an atom.

Show that any proposition is equivalent to a formula in CNF.

I'm totally lost. I don't know how to start proof. I need an idea, not full answer.

1

There are 1 best solutions below

1
On

You may use an inductive proof. Start by showing that for every literal (atom or a negation of one) you have an equivalent formulation in CNF (trivial). Then, assume that $\phi$ and $\psi$ are arbitrary formulae connected by some connective of your language, show that there is an equivalent formulation in CNF. Show this for every connective of your language. You also need to formulate a suitable conclusion.

I hope it is sufficiently clear for an idea.