CNF,DNF and NNF

As we know the set { ,⋀,⋁, →} of connectives is functionally complete. We can eliminate → connective and the result set remain functionally complete, because → Boolean function can be written in form of p⋁q (p→q), it easy to see when we write down the truth tables. But the remain system has more properties than just the completeness, we can write any propositional formula in some normal forms, which we define now.

NNF(Negation Normal Form)
A formula is in NNF when it consists only ,⋀,⋁ connectives and connective used only on propositions(sometimes called atomic formulas). For example ((p⋀q)⋁(r⋀t)) formula is in NNF, but ((p⋀q)⋁(r⋀t)) formula is not in NNF. We can also define an algorithm which transfer a propositional formula into NNF.
Algorithm

1. Write formula using only ,⋀,⋁ connectives.
2. Push negations in until they apply only to propositions or negation of propositions(called literals), repeatedly replacing by equivalences

p=p
(A⋀B)=A⋁B
(A⋁B)=A⋀B

We can simplify the NNF formula again.
CNF(Conjunctive Normal Form)
A formula is in CNF when it is in form of A1⋀A2⋀A3⋀...An where each Ai is in form B1⋁B2⋁B3⋁...⋁Bn where each Bi is proposition or negation of proposition.
It easy to understand that CNF formula is in NNF . And for transforming propositional formula into CNF we can at first transform it into NNF then

• Push disjunctions in until they apply only to literals, repeatedly replacing by equivalences

A ⋁ (B ⋀ C)= (A ⋁ B) ⋀ (A ⋁ C)
(B ⋀ C) ⋁ A= (B ⋁ A) ⋀ (C ⋁ A)

DNF(Disjunctive Normal Form)
A formula is in DNF when it is in form of A1⋁A2⋁A3⋁...An where each Ai is in form B1⋀B2⋀B3⋀...⋁Bn where each Bi is literal. If formula is in DNF then it is in the NNF also.The same transformation method work for DNF when we swap ⋁,⋀ connectives.

Later we see that CNF is useful when proofing theorems and DNF for refuting.