# Normal forms and their types | Discrete Mathematics

In this article, we will learn about the **introduction of normal form and the types of normal form and their principle in discrete mathematics**.

Submitted by Prerana Jain, on August 28, 2018

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

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions