Normal Forms

Let A(P₁, P₂, P₃, …, P_n) be a statement formula where P₁, P₂, P₃, …, P_n are the atomic variables. If A has truth value T for all possible assignments of the truth values to the variables P₁, P₂, P₃, …, P_n , then A is said to be a tautology. If A has truth value F, then A is said to be identically false or a contradiction.

1.2.1 Disjunctive Normal Forms

A product of the variables and their negations in a formula is called an elementary product. A sum of the variables and their negations is called an elementary sum. That is, a sum of elementary products is called a disjunctive normal form of the given formula.

Example:

The disjunctive normal form of

1. PÙ (P® Q) Û PÙ (ù PÚ Q) Û (PÙ ù P)Ú (PÙ Q).
2. ù (P Ú Q) (PÙ Q) Û (ù (PÚ Q)Ù (PÙ Q))Ú ((PÚ Q)Ù ù (PÙ Q))
   Û (ù P Ù ù Q Ù P Ù Q) Ú (P Ù ù P) Ú (Q Ù ù P) Ú (P Ù ù Q) Ú (Q Ù ù Q).

Back to top

1.2.2 Conjunctive Normal Forms

A formula which is equivalent to a given formula and which consists of a product of elementary sums is called a conjunctive normal form of a given formula.

Example 1:

The conjunctive normal form of

(a) P Ù (P® Q) Û P Ù (ù P Ú Q).

(b) ù (P Ú Q) Û ù P Ù ù Q.

(c) ù (P Q) Û ù ((P® Q) Ù (Q® P))
Û ù ((ù P Ú Q) Ù (ù Q Ú P))
Û ù (ù P Ú Q) Ú ù (ù Q Ú P)
Û (P Ù ù Q) Ú (Q Ù ù P)
Û (P Ú Q) Ù (Q Ú ù Q) Ù (P Ú ù P) Ù (ù P Ú ù Q).

(d) ù (P Ú Q) (P Ù Q) Û (ù (P Ú Q) ® (P Ù Q)) Ù ((P Ù Q)® ù (P Ú Q))
Û ((P Ú Q) Ú (P Ù Q)) Ù (ù (P Ù Q) Ú (ù P Ù ù Q)
Û (P Ú Q Ú P) Ù (P Ú Q Ú Q) Ù (ù P Ú ù Q Ú ù P) Ù (ù P Ú ù Q Ú ù Q).

Example 2:

(a) Show that the formula ù B Ú (ù A Ù B) Ú (A Ù B) is a tautology.

ù B Ú (ù A Ù B) Ú (A Ù B) Û ù B Ú ((ù A Ú A) Ù B)
Û (ù B Ú ù A Ú A) Ù (ù B Ú B)
Û T Ù T
Û T.
Therefore, it is a tautology.

(b) Show that the formula (ù B Ù A) Ù B is a contradiction.

(ù B Ù A) Ù B Û A Ù (B Ù ù B)
Û A Ù F
Û F.
Therefore, it is a contradiction.

(c) Show that (Q® P) Ù ( ù P Ù Q) is a contradiction.

(Q® P) Ù ( ù P Ù Q) Û (ù Q Ú P) Ù (ù P Ù Q)
Û (ù P Ù Q Ù ù Q) Ú (P Ù ù P Ù Q)
Û F Ú F
Û F.
Therefore, it is a contradiction.

Back to top

1.2.3 Principal Disjunctive Normal Form (PDNF)

Let us assume A and B be two statement variables. All possible formulas by using conjunction are given as follows. The total number of formulas for two variables A and B are 2² formulas. They are A Ù B, A Ù ùB,
ùA Ù B and ù A Ù ù B.

These are called minterms or Boolean conjunctions of A and B. The minterms (2ⁿ terms) are denoted by M₀, M₁, … ,M₂ⁿ_-1.

A formula equivalent to a given formula consisting of the disjunction of minterms only is called PDNF of the given formula.

Example 1:

Obtain the PDNF of (ù P Ú ù Q)® (P ù Q)

P	Q	ù PÚ ù Q	P ù Q	(ù PÚ ù Q) ® (P ù Q)
T	T	F	F	T
T	F	T	T	T
F	T	T	T	T
F	F	T	F	F

From the above table

(ù PÚ ù Q)® (P ù Q) Û (PÙ Q) Ú (PÙ ù Q) Ú (ù PÙ Q)
Û (ù PÙ Q) Ú (PÙ ù Q) Ú (PÙ Q)
Û

Example 2:

Obtain the PDNF of

P	Q	P ® Q
T	T	T
T	F	F
F	T	T
F	F	T

P® Q Û (PÙ Q) Ú (ù PÙ Q) Ú (ù PÙ ù Q)
Û (ù PÙ ù Q) Ú (ù PÙ Q) Ú (PÙ Q)
Û

Procedure for obtaining PDNF

Step1 : Get rid of , ® .
Step2 : Use De Morgan’s law.
Step3 : Use distributive law.
Step4 : Introduce missing factor in the disjunction.
Step5 : If there is elementary product of the form.

(PÙ ù P) Ú ( ) Ú …… , delete P Ù ù P.

For every truth value T in the truth table of the given formula, select minterm which also has the value T for the same combination of the truth values of P and Q. The disjunction of these minterms will be equivalent to the given formula.

To find a particular minterm M_i, the subscript i is expressed in the binary representation and suitable number of 0’s are added to the left.

Example 3:

Obtain PDNF for .

Assign 1 for P and 0 for ù P.

Example 4:

Obtain PDNF for .

Solution:

Example 5:

Obtain PDNF for P® ((P® Q Ù ù (ù Q Ú ù P))).

Solution:

P® ((P® Q Ù ù (ù Q Ú ù P))) Û P® ((P® Q Ù (P Ù Q)))
Û P® ((P® P Ù Q))
Û P® (ù P Ú (P Ù Q))
Û ù P Ú (ù P Ú (P Ù Q))
Û ù P Ú (P Ù Q)
Û (ù P Ù (Q Ú ù Q)) Ú (P Ù Q)
Û (ù P Ù Q) Ú (ù P Ù ù Q) Ú (P Ù Q)
Û (ù P Ù ù Q) Ú (ù P Ù Q) Ú (P Ù Q)
Û .

Back to top

1.2.4 Principal Conjunctive Normal Forms (PCNF)

The duals of minterms are called maxterms. For a given number of variables the maxterm consists of disjunctions in which each variable or its negation, but not both, appears only once.

For a given formula, an equivalent formula consisting of conjunctions of maxterms only is known as its principal conjunctive normal form. This is also called the product of sums canonical form.

Example 1:

Obtain the PCNF of (ù P® R) Ù (Q P).

Solution:

(ù P® R) Ù (Q P) Û (P Ú R) Ù ((Q® P) Ù (P® Q))
Û (P Ú R) Ù ((ù Q Ú P) Ù (ù P Ú Q))
Û (P Ú R Ú (Q Ù ù Q)) Ù ((P Ú ù Q Ú (R Ù ù R)) Ù (ù P Ú Q Ú (R Ù ù R))
Û (P Ú Q Ú R) Ù (P Ú ù Q Ú R) Ù (P Ú ù Q Ú ù R) Ù (ù P Ú Q Ú R) Ù (ù P Ú Q Ú ù R)

S Û p (0,2,3,4,5).

ù S Û consisting of missing maxterms
Û M₁ Ù M₆ Ù M₇
Û (P Ú Q Ú ù R) Ù (ù P Ú ù Q Ú R) Ù (ù P Ú ù Q Ú ù R).


Example2:

Obtain PCNF for A : (ù P® R) Ù ((Q® P) Ù (P® Q)).

Solution:

A Û (PÚ R)Ù ((ù QÚ P)Ù (ù PÚ Q))
Û (PÚ RÚ (QÙ ù Q)) Ù (PÚ ù QÚ (RÙ ù R)) Ù (ù PÚ QÚ (RÙ ù R))
Û (PÚ QÚ R)Ù (PÚ ù QÚ R)Ù (PÚ ù QÚ R)Ù (PÚ ù QÚ ù R)Ù (ù PÚ QÚ R)Ù (ù PÚ QÚ ù R)
Û (PÚ QÚ R) Ù (PÚ ù QÚ R) Ù (PÚ ù QÚ ù R) Ù (ù PÚ QÚ R) Ù (ù PÚ QÚ ù R)
Û p (0,2,3,4,5).

Example 3:

From the given truth table formula S, determine its PDNF and PCNF

Table 1.2.4

A	B	C	S
T	T	T	T
T	T	F	F
T	F	T	F
T	F	F	F
F	T	T	F
F	T	F	F
F	F	T	F
F	F	F	T

By choosing the minterms corresponding to each T value of S,

the PDNF of S .

By choosing the maxterms corresponding to each F value of S,

the PCNF of S Û (ù A Ú ù B Ú C) Ù (ù A Ú B Ú ù C) Ù (ù A Ú B Ú C) Ù (A Ú ù B Ú ù C) Ù (A Ú ù B Ú C)
Ù (A Ú B Ú ù C) .


Example 4:

Form the given truth table formula S, determine its PDNF and PCNF

A	B	C	S
T	T	T	F
T	T	F	F
T	F	T	T
T	F	F	F
F	T	T	T
F	T	F	T
F	F	T	F
F	F	F	T

By choosing minterms corresponding to each T value of S,

the PDNF of S Û (A Ù ù B Ù C) Ú (ù A Ù B Ù C) Ú (ù A Ù B Ù ù C) Ú (ù A Ù ù B Ù ù C)
Û .

By choosing maxterms corresponding to each F value of S,

the PCNF of S Û (ù A Ú ù B Ú ù C) Ù (ù A Ú ù B Ú C) Ù (ù A Ú B Ú C) Ù (A Ú B Ú ù C)
Û p(1,4,6,7).


Example 5:

Obtain the product of sums canonical form of the formula A which is given by
(P Ù Q Ù R) Ú (ù P Ù Q Ù R) Ú (ù P Ù ù Q Ù ù R)

Solution:

ù A Û (ù P Ú ù Q Ú ù R) Ù (P Ú ù Q Ú ù R) Ù (P Ú Q Ú R)
Û p(0,3,7).

ù (ù A) Û consisting of missing maxterms
Û p(1,2,4,5,6)
Û (P Ú Q Ú ù R) Ù (P Ú ù Q Ú R) Ù (ù P Ú Q Ú R) Ù (ù P Ú Q Ú ù R) Ù (ù P Ú ù Q Ú R) .


Example 6:

Obtain the product-of-sums canonical form of the formula A, which is given by
(ù P Ù Q Ù R Ù ù S) Ú (P Ù ù Q Ù ù R Ù S) Ú (P Ù ù Q Ù R Ù ù S) Ú (ù P Ù Q Ù ù R Ù S) Ú (P Ù Q Ù ù R Ù ù S).

Solution:

ù A Û (P Ú ù Q Ú ù R Ú S) Ù (ù P Ú Q Ú R Ú ù S) Ù (ù P Ú Q Ú ù R Ú S) Ù (P Ú ù Q Ú R Ú ù S) Ù
(ù P Ú ù Q Ú R Ú S)
Û (P Ú ù Q Ú R Ú ù S) Ù (P Ú ù Q Ú ù R Ú S) Ù (ù P Ú Q Ú R Ú ù S) Ù (ù P Ú Q Ú ù R Ú S) Ù
(ù P Ú ù Q Ú R Ú S)
Û p(5, 6, 9, 10, 12).

ù (ù A) Û consisting of missing maxterms
Û p(0,1,2,3,4,7,8,11,13,14,15)
Û M₀Ù M₁Ù M₂Ù M₃Ù M₄Ù M₇Ù M₈Ù M₁₁Ù M₁₃Ù M₁₄Ù M₁₅
Û (P Ú Q Ú R Ú S) Ù (P Ú Q Ú R Ú ù S) Ù (P Ú Q Ú ù R Ú S) Ù (P Ú Q Ú ù R Ú ù S) Ù (P Ú ù Q Ú R Ú S)
Ù (P Ú ù Q Ú ù R Ú ù S) Ù (ù P Ú Q Ú R Ú S) Ù (ù P Ú Q Ú ù R Ú ù S) Ù (ù P Ú ù Q Ú R Ú ù S) Ù
(ù P Ú ù Q Ú ù R Ú S) Ù (ù P Ú ù Q Ú ù R Ú ù S).


Example 7:

Obtain the product of sums canonical form of (P Ù Q) Ú (ù P Ù Q) Ú (P Ù ù Q).

Solution:

ù A Û (ù P Ú ù Q) Ù (P Ú ù Q) Ù (ù P Ú Q)
Û (P Ú ù Q) Ù (ù P Ú Q) Ù (ù P Ú ù Q)
Û p(1,2,3).

ù (ù A) Û consisting of missing maxterms
Û p(0)
Û M₀
Û P Ú Q.

Back to top

Exercise:

1. Write the following statements in symbolic form using the statements

P : Sandeep is rich. Q : Sandeep is happy.

1. Sandeep is poor but happy.
2. Sandeep is rich or unhappy.
3. Sandeep is neither rich nor happy.
4. Sandeep is poor or he is both rich and unhappy.

2. Write the negation of each of the following statements as simply as possible.

1. He is tall but handsome.
2. He has blond hair or blue eyes.
3. He is neither rich nor happy.
4. He lost his job or he did not go to work today.
5. Neither Siva nor Sriram is unhappy.
6. Ajay speaks Bengali or Hindi, but not German.
7. If he studies, he will pass the exam.
8. He swims if and only if the water is warm.
9. If it snows, then he does not drive the car.
10. If it is cold, then he wears a coat but no sweater.
11. If he studies then he will go to college or to art school.

3. Write the following statement in symbolic form using the statements

P: It is cold. Q: It rains.

1. It rains only if it is cold.
2. A necessary condition for it to be cold is that it rain.
3. A sufficient condition for it to be cold is that it rain.
4. Whenever it rains it is cold.
5. It never rains when it is cold.

4. Write each statement in symbolic form using

P : He is rich Q : He is happy.

1. If he is rich then he is unhappy.
2. He is neither rich nor happy.
3. It is necessary to be poor in order to be happy.
4. To be poor is to be unhappy.
5. Being rich is a sufficient condition to being happy.
6. Being rich is a necessary condition to being happy.
7. One is never happy when one is rich.
8. He is poor only if he is happy.
9. To be rich means the same as to be happy.
10. He is poor or else he is both rich and happy.

5. Write the negation of each statement in as simple a sentence as possible.

1. If Sindhu is a poet, then she is poor.
2. If Madhu passed the test, then he studied.
3. If x is less than zero, then x is not positive.
4. If it is cold, he wears a hat.
5. If productivity increases, then wages rise.

6. From the formulas given below select those which are well formed and indicate which ones are tautologies
or contradictions.

1. (A ® ( A Ú Q))
2. ((A ® (ù A)) ® ù A)
3. (ù B Ù A) Ù B
4. ((A ® (B ® C)) ® ((A ® B) ® (A ® C)))
5. ((ù A ® B) ® (B ® A))
6. ((A Ù B) A)

7. Obtain the PCNF of the following

1. 
2. 
3. ù (A B)

8. Obtain the product of sums canonical forms of the following.

1. (P Ù Q Ù R) Ú (ù P Ù Q Ù R) Ú (ù P Ù ù Q Ù ù R) Ú (ù P Ù ù Q Ù R).
2. (ù P Ù Q Ù R Ù ù S) Ú (P Ù ù Q Ù ù R Ù S) Ú (P Ù ù Q Ù R Ù ù S) Ú (ù P Ù Q Ù ù RÙ S) Ú
   (P Ù Q Ù R Ù ù S).
3. (ù P Ù ù Q) Ú (ù P Ù Q) Ú (P Ù ù Q).
4. (P Ù Q) Ú (ù P Ù Q Ù R).

9. Obtain the PDNF and PCNF of the following

1. (Q Ù (P Ú ù Q)).
2. P Ú (ù P® (Q Ú (ù Q® R))).
3. (P® (Q Ù R)) Ù (ù P® (ù Q Ù ù R)).
4. P ® (P Ù (Q® P)).
5. (Q® P) Ù (ù P Ù Q).