Normal Form
Definition of Normal form:
A normal form is a part of the system which cannot be rewritten any further.
The basic term is rewriting system with reduction rule p: q(x, y) -> x. The term q (q (6, 3), q ((6, 3)) has the following sequence, according to the usual outermost strategy. There are different types of normal forms are used.
Negation normal form: The Negation form is nothing but, if the negation is occurs only immediately above elementary propositions, and {¬, V, ∩} are the only allowed Boolean connectives.
Conjunctive normal form (CNF): The conjunctive normal form is nothing but, if it is a conjunction of clause, where a clause is a disjunction of literals, where a literal and its compliment cannot appear in the same clause.
Disjunctive normal form: The disjunctive normal form is nothing but a normalization of a logical formula and it is a disjunction of conjunctive clauses.
The following is a formal grammar for disjunctive normal form:
1. or → ∨
2. and → ∩
3. not → ¬
4. Disjunction → conjunct
5. Disjunction → disjunction or conjunct
6. Conjunct → literal
7. Conjunct → conjunct and literal
8. Literal → term
9. Literal → not term
Where
Term is any variable.
Algebraic normal form (ANF)
The algebraic normal form is a method of normalizing logical formulas. The general algebraic normal form can be written as:
F(x1, x2 ...xn) = a0+ a1x1+a2x2+………. + anxn +a1,2 x1x2+…….+an-1,nxn-1xn+……. +a1,2…….nx1x2…….xn
Where
a0, a1……. a1,2..........n `in` {0, 1}* fully describes f
The following formulas are in CNF
¬ A ∩ ( B V C )
( A V B ) ∩ (¬ B V C V ¬ D ) ∩ ( D V ¬ E )
A ∩ B.
The last formula for CNF because it can be seen as the conjunction of the two single-literal clauses A and B.
¬ (B V C)
(A ∩ B) V C
A ∩ (B V (D ∩ E)).
¬B∩¬C
(A V C) ∩ (B V C)
A ∩ (B V D) ∩ (B V E).
