Home » Discrete Mathematics

Normal Forms and Their Types | Discrete Mathematics

In this tutorial, we will learn about the introduction of normal form and the types of normal form and their principle in discrete mathematics. By Prerana Jain Last updated : May 09, 2023

Normal Form

Suppose, A (P1, P2, ... , Pn) is a statements formula where P1, P2, ..., P6 are the atomic variables if we consider all possible assignments of the truth value to P1, P2, ..., Pn and obtain the resulting truth values of the formula A then we get the truth table for A, such a truth table contains 2^6 rows. The formula may have the truth value T for all possible assignments of the truth values to the variables P1, P2, ..., Pn. In this case, A is called identically true or tautology. If A has the truth value T for at least one combinations of truth values assigned to P1, P2, ..., Pn then A is called satisfiable.

The problem of determining in a finite number of steps, whether a given statement formula is a tautology or a contradiction or least satisfiable is known as a decision problem.

Types of Normal form

1. Disjunctive Normal form

We may use the word "product" in place of "conjunction" and "sum" in place of "disjunction".

A product of the variable and their negations in a formula is called an elementary product. Similarly, a sum of the variables and their negations is called as an elementary sum.

Some statements hold for elementary sums and product:

1. For any elementary product, the necessary condition is false is when it contains at least one pair of a factor in which one is the negation of the other.
2. For any elementary sum, the necessary condition is true when it contains at least one pair of factors in which one is the negations of the other.

2. Conjunctive normal form

The conjunctive normal form of a given formula is the one which contains the product of elementary sums (that formula is equivalent in the given formula).

Observations

1. The procedure for obtaining a formula in conjunctive normal form is quite similar to that of disjunctive normal form.
2. The conjunctive normal form is not unique.
3. A given formula will be identical if every elementary sum presents in its conjunctive normal form are identically true.
4. The 3 hold if every elementary sum present in the formula has at least two factors in which one is the negation of the other.

3. Principle Disjunctive normal form

Suppose, P and Q are two variables. We construct all possible formulas which consist of a conjunction of P or in negation and conjunction of Q or its negation. Now of the formulas should contains both a variable and its negation. For two variables P and Q there is 2^2 such formula.

These formulas are called minterms or Boolean conjunction of p and Q from the truth tables of theses minterms, it is clear that no two minterms are equivalent. Each minterm has the truth value T for exactly one combination of the truth value of the variables P and Q.

For a given formula an equivalent formula consisting of a disjunction of minterms only is known as its principle disjunction normal form. Such a normal form is also said to be the sum-product canonical form.

4. Principle conjunctive normal form

Given a number of variables maxterm of these variables is a formula which consists of disjunction in which each variable or its negations but not both appear only once. Observe that the maxterm are the duals of minterms. Therefore each of the maxterm has the truth value F for exactly one combination of the truth values of the variables.

The principle of conjunctive normal form or the product-sum canonical form, the equivalent formula consists of only the conjunction of the maxterms only.

---