Canonical Forms

There are two types of canonical forms:

1. Disjunctive Normal Forms or Sum of Products or (SOP).
2. Conjunctive Normal Forms or Products of Sums or (POS).

Disjunctive Normal Forms or Sum of Products or (SOP):

A Boolean expression over ({0, 1}, ∨,∧,') is said to be in disjunctive normal form if it is a join of minterms

Example: (x₁'∧x₂'∧x₃')∨( x₁'∧x₂∧x₃' )∨(x₁∧x₂∧x₃) is a Boolean expression in disjunctive normal form.

Since there are three min-terms x₁'∧x₂'∧x₃',x₁'∧x₂∧x₃ and x₁∧x₂∧x₃.

Max-term: A Boolean Expression of n variables x₁,x₂,....x_nis said to be a max-term if it is of the form x₁∨x₂∨..........∨x_n

where x_i is used to denote x_i or x_i'.

Conjunctive Normal Forms or Products of Sums or (POS):

A Boolean expression over ({0, 1}, ∨,∧,') is said to be in a disjunctive normal form if it is a meet of max-terms

Example:

        (x₁∨x₂∨x₃)∧( x₁∨x₂∨x₃ )∧(x₁∨x₂∨x₃ )∧(x₁'∨x₂∨x₃' )∧(x₁'∧x₂'∧x₃)

is a Boolean expression in conjunctive normal form consisting of five max-terms.

Obtaining A Disjunctive Normal Form:

Consider a function from {0, 1}ⁿ to {0, 1}. A Boolean expression can be obtained in disjunctive normal forms corresponding to this function by having a min-term corresponding to each ordered n-tuples of 0's and 1's for which the value of the function is 1.

Obtaining A Conjunctive Normal Form:

Consider a function from {0, 1}ⁿ to {0, 1}. A Boolean expression can be obtained in conjunctive normal forms corresponding to this function by having a max-term corresponding to each ordered n-tuples of 0's and 1's for which the value of function is0.

Example: Express the following function in

1. Disjunctive Normal Form
2. Conjunctive Normal Form

	f		f
(0, 0, 0)	1	(1, 0, 0)	0
(0, 0, 1)	0	(1, 0, 1)	1
(0, 1, 0)	1	(1, 1, 0)	0
(0, 1, 1)	0	(1, 1, 1)	1

Solution:

1. (x₁'∧ x₂' ∧ x₃') ∨(x₁'∧x₂∧ x₃' )∨(x₁∧x₂'∧x₃ )∨(x₁∧x₂∧x₃)
2. (x₁'∨x₂'∨x₃')∧( x₁'∨x₂∨x₃ )∧(x₁∨x₂'∨x₃' )∧(x₁∨x₂∨x₃')

Principle of Duality:

The dual of any expression E is obtained by interchanging the operation + and * and also interchanging the corresponding identity elements 0 and 1, in original expression E.

Example: Write the dual of following Boolean expressions:

1. (x₁*x₂) + (x₁*x₃')         2. (1+x₂)*( x₁+1)
3. (a ∧(b∧c))

Solution:

1. ( x₁+x₂)*( x₁+x₃')         2. (0*x₂)+( x₁*0)
3. (a ∨(b∧c))

Note: The dual of any theorem in a Boolean algebra is also a theorem.