# 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:**

- 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.
- 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**

- The procedure for obtaining a formula in conjunctive normal form is quite similar to that of disjunctive normal form.
- The conjunctive normal form is not unique.
- A given formula will be identical if every elementary sum presents in its conjunctive normal form are identically true.
- 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.

Related Tutorials

- Set Theory: What It Is, Types, Symbols, and Examples
- Set: Cardinality, Notations, Construction, Operations
- Group Theory and Its Types in Discrete Mathematics
- Discrete Mathematics Functions, Their Types, and Examples
- Algebraic Structure and Properties of Structure
- Permutation Group and Its Types
- Types of Relations in Discrete Mathematics
- Properties of Binary Relation in a Set
- Rings and Types of Rings in Discrete Mathematics
- Operations in Propositional Logic in Discrete Mathematics

Comments and Discussions!