DSTL compact notes

Notes Unit 2

1 Functions and Properties

A function between two nonempty sets is a rule that associate with each element of one set to a unique
element of the other set. Therefore, sets and functions are important to understand modern mathematics,
and also some aspects of the theory of computation. In particular, the polynomial functions, trigonometric
functions, and exponential functions are the most basic types of functions that hold vast geometric signifi-
cance for applications. We study “properties of functions" to understand how elements of various types of
sets are related to each other. Some simple examples include use of bijective functions to compare the sizes
of sets, study control objects as in control theory, measure computational complexity of an algorithm, and
so on.

1.1 Functions

An abstract definition of a function is as given below.

Definition 2.1. Let X and Y be two nonempty sets (not necessarily distinct). A function f from X to Y is a
relation f ⊆ X ×Y such that, for each x ∈ X, we have

(a) there is some y ∈ Y such that (x, y) ∈ f ;

(b) (x, y1), (x, y2) ∈ f ⇒ y1 = y2.

In this case, we write the function f : X → Y as

f = {(x, y) ∈ X ×Y | y = f (x), for x ∈ X}. (2.1)

The set X is called the domain, and the set Y is called the codomain, of the function f . We usually write
X := Dom f . For x ∈ X, the set of image elements f (x) ∈ Y is called the range of the function f , which is
denoted by Ran( f ). That is, we have
Ran f := y = {f (x) ∈ Y | x ∈ X} (2.2)

We also write y = f (x) as f : x '→ y (read as f maps element x to element y).

Clearly, not every relation is a function. For example, in Fig. 2.1, R violates condition (a), and S violates
condition (b). In general, we can define at least as many functions f : X → Y as there are elements in the
set Y . For, let y0 be any fixed element of the set Y , and define fy0 : X → Y as fy0 (x) = y0, for x ∈ X . This is
called the constant function at y0 given on the set X . Next, we may choose two or more elements in the set
Y , and define functions f : X → Y by mapping elements of X to some of these elements of Y (Fig. 2.2).
DSTL compact notes

A B A B
R S
4 5 4 5

5 6 5 6

6 7 6 7

Figure 2.1: Two relations R, S : A → B that are not functions.

a
X Y
z b
a 1
y
b 2 c
c 3 x d
e
d 4 f

Figure 2.2: Graphs of some simple functions.

Definition 2.2. Two functions f : X → Y and g : U → V are said to be equal if X = U, Y = V, and

f (x) = g(x), for all x ∈ X (= U ). (2.3)

Let f : X → Y be a function. We also call an element x ∈ Dom( f ) an argument of the function f , and the
element y = f (x) ∈ Y is called
} the image of x ∈ X under f . On the other hand, for y ∈ Y , the elements in
the set x ∈ X | f (x) = y are called the pre images of the element y. We write the set of preimages of an
element y ∈ Y as
f −1 y := x ∈ X | f (x) = y (2.4)
More precisely, the notation f −1 is used later to write the inverse of a function f , which correspond to
the case when f −1(y) contains exactly one element of X , for every y ∈ Y . Notice that it is possible that
f −1(y) = ∅, for some y ∈ Y .

1.2 Important Functions

Two related functions given in the next definition use archimedean property of the set R.
DSTL compact notes

Definition 2.3. An integer-valued function ⌊ ⌋ : R → Z given by

⌊x⌋ = n, if x ≥ n, x ∈ R, (2.5)

is called the floor function, and ⌈ ⌉ : R → Z given by

⌈x⌉ = n, where x ≤ n, x ∈ R, (2.6)

is called the ceiling function. The floor function ⌊ ⌋ is also known as the greatest integer function.

Figure 2.3: Graph of the greatest integer function f (x) = ⌊x⌋.

The graph of each one of these two functions is like a stair (see Fig. 2.3). So, such types of functions are
also known as the stair functions. Any assertion concerning the floor functions ⌊ ⌋ is dealt with by taking
x = n + ε, where n = ⌊x⌋ ∈ Z and 0 ≤ ε < 1. Similarly, while dealing with any assertion concerning the
ceiling functions, we take x = n − ε, where n = ⌈x⌉ ∈ Z and 0 ≤ ε < 1. For example, we can apply these
arguments to prove some interesting properties of the stair functions such as given in the next theorem.
These relations are used very extensively in computer science.

Theorem 2.1. For any x ∈ R,

1. ⌊x⌋ = n ⇔ n ≤ x < n + 1; ⌈x⌉ = n ⇔ n − 1 < x ≤ n.

2. ⌊x⌋ = n ⇔ x − 1 < n ≤ x; ⌈x⌉ = n ⇔ x ≤ n < x + 1.

3. x − 1 < ⌊x⌋ ≤ x ≤ ⌈x⌉ < x + 1.

4. ⌊−x⌋ = −⌈x⌉ and ⌈−x⌉ = −⌊x⌋.

5. ⌊x + n⌋ = ⌊x⌋+ n and ⌈x + n⌉ = ⌈x⌉+ n.

Also, sequences and strings are two special type of functions that find numerous applications in computer
science and its allied branches. A sequence over a nonempty set X is an ordered list of elements of X , where
the set of natural numbers N is used to order the terms of the sequence. More precisely, a sequence of
elements of X is a function s : N → X so that if

s(1) = x1, s(2) = x2, s(3) = x3, . . . (2.7)

then we write the sequence s simply as xn , where xn = s(n) is called the n-term of the sequence. As for
functions, two sequences s = xn and t = yn are equal if xn = yn, for all n ∈ N. In particular, when X = R,
DSTL compact notes

we call s a real sequence; when X = R2, we calls a sequence of 2 -dimensional vectors; when X = R3, we
call s a sequence of 3 -dimensional vectors; and, so on.

Example 2.1. The following are some simple real sequences:

Notice that the sequence in (3) gives a listing of elements of the set of integers Z as 0, 1, −1, 2, −2, . . . .
Also, the sequence in (4) lists discrete values of the continuous function f (x) = cos(πx), x ∈ R, at the points
n = 1, 2, 3, Such a process in certain applications is called sampling.

On the other hand, strings over a finite set of alphabets is a special type of finite sequence that find applica-
tions in computer science and also in some other fields such as genomics (see Example 6.4).
Notice that the function in next definition is not formula based.

Definition 2.4 (Characteristic Function). Let X be a nonempty set, and A ⊆ X. The characteristic function7
of the set A, denoted by χA, is a function χA : X → {0, 1} given by

The next theorem proves useful in several interesting situations.

Theorem 2.2. Let X be a nonempty set, and A, B ⊆ X. The following relations hold:

1. χA∩B = χA · χB;

2. χA∪B = χA + χB − χA · χB;
 DSTL compact notes

3. χAc = 1 − χA;

4. χA∨B = χA + χB − 2χA · χB;

5. aχA + bχB = aχA−B + (a + b)χA∪B + bχB−A, for any real numbers a and b.

1.3 Important Properties

Let X and Y be two nonempty sets. The definitions given below are important.

1. A function f : X → Y is called an injective function (or a one-one function) if each pair of distinct
elements in the set X := Dom( f ) has distinct images in the set Y . That is, for any x1, x2 ∈ X ,

(2.9)
p
2. A function f : X → Y is called a surjective function (or an onto function) if every element of the set Y
has a preimage in X . That is, Ran( f ) = Y . We call a function f : X → Y an into function when it is not
an onto function. Notice that, in this case, we have Ran( f ) ⊂ Y .
3. A function f : X → Y is called a bijective function (or simply a bijection) if f is both an injective and
a surjective function.

4. Two sets X and Y are said to be in bijective correspondence if there is a bijection f : X → Y .

In actual practice, while showing that a function is injective , we use the following contrapositive statement
of the implication given in (3.9): For x1, x2 ∈ X ,

f x1 = f x2 ⇒ x1 = x2. (2.10)

For illustration, see the next example, and solution of Q. ??. Also, when both X and Y are finite sets, (4)
implies that |X | = |Y |. In particular, it follows that an injective function f : X → Y can not be an surjective
function if Y has at least one more element than the set X . Therefore, there are many injective functions
that are not surjective, and vice-versa. The function defined in the next example is an important bijective
function.

Q 2.1. Let A and B be two sets such that |A| = |B|. Prove that a function f : A → B is an injective function if
and only if it is a surjective function.

Sol. In general, if f : A → B is injective, we have |A| ≤ |B|. However, since |A| = |B|, we have Ran( f ) = B.
Thus, f is a surjective function. Conversely, if f : A → B is surjective, we have Ran( f ) = B so that |A| ≥ |B|.
However, since |A| = |B|, no element b ∈ B has more than one pre-image. Hence, f is an injective function.
DSTL compact notes

Q 2.2. Let f : A → B and g : B → C be two functions such that the composite function g ◦ f : A → C is a
bijective function. Prove that f is injective, and g is surjective. Give an example to show that converse may
not be true.

Sol. We first prove that f is injective. For, let f (a1) = f (a2), for a1, a2 ∈ A. Then we have

g f (a1) = g f (a2) ⇒ g ◦ f (a1) = g ◦ f (a2) ⇒ a1 = a2,

because g ◦ f is injective. To complete the solution, we show that g is surjective. For, let c ∈ C. Now, as
g ◦ f : A → C is surjective, there is some a ∈ A such that g ◦ f (a) = c. Finally, taking b = f (a), we have
g(b) = c. For a counter-example to disprove the converse, take A = B, f = IA, C = {c}, and g : A → C the
constant function.

Q 2.3. Show that the function f : N → Z given by

Sol. We first show that f is one-one. Clearly, when integers n and m are of opposite parity, we have
f (n) = f (m). Next, let f (n) = f (m), when n and m have the same parity. Now, if both n and m are
even, then we obtain n/2 = m/2, and so n = m. The same conclusion is obtained when both n and m
are odd. To prove f is onto, we have 2m ∈ N when m ∈ Z is positive, and so f (2m) = m. We also have
1 − 2m ∈ N when m ∈ Z is zero or negative, and so f (1 − 2m) = m, because 1 − 2m is odd. Notice that odd
natural numbers 1, 3, 5, 7, . . . are respectively mapped to non-positive integers 0, −1, −2, −3,... , whereas
even natural numbers 2, 4, 6, 8, . . . are respectively mapped to positive integers 1, 2, 3, 4, . . . . Hence, f is
a bijective function.

1.4 Composition & Inverse

We start with the next definition.

Definition 2.5. The composition of two functions f : X → Y and g : Y → Z, denoted by g ◦ f : X → Z (see

Fig. 6), is the function given by

g ◦ f (x) = g f (x) , for all x ∈ X. (2.11)

Example 3.2. The composition of functions f : N → Z and g : Z → Z respectively given by

F(n) = n − 2 and g(n) = n2,

DSTL compact notes

f
X Y

Figure 2.4: Composition of functions.

is given by
g ◦ f (n) = g f (n) = g(n − 2) = (n − 2)2 = n2 − 4n + 4.
On the other hand, though the codomain of the function g is the set Z, yet we can compute the composition
f ◦ g (in reverse order) because we have

Ran(g) = { n2| n ∈ Z} ⊂ N.

In this case, we have

f ◦ g (n) = f(g(n)) = f (n2) = n2 − 2.
Incidently, it is found that f ◦ g = g ◦ f , mainly due to the following two reasons:

(a) their values are different;

(b) the domains of f ◦ g and g ◦ f are not the same set.

In general, while verifying that the composition of two functions is same, we must ensure none of the above
two conditions hold.

Theorem 2.3. Let f : X → Y and g : Y → Z be any two functions.

1. If both f and g are injective then so is the composition g ◦ f .

2. If both f and g are surjective then so is the composition g ◦ f .

3. If both f and g are bijections„ then so is the composition g ◦ f .

We next consider the following general question: Given a function f : X → Y , does there exists a function
g : Y → X that will undo the effect of the function f ?

Definition 2.6. Let X and Y be two nonempty sets, and f : X → Y be a function. We say g : Y → X is an
inverse function of f if
g ◦ f = IX and f ◦ g = IY . (2.12)
In this case, we write g = f −1. We say a function f : X → Y is invertible if it has an inverse.
DSTL compact notes

We remark that if a function f : X → Y is invertible, with g : Y → X as an inverse, then g is necessarily

unique. For, suppose there are two functions g1, g2 : Y → X satisfying the conditions as in (2.12). That is,

f ◦ g1 = IY , g1 ◦ f = IX and f ◦ g2 = IY , g2 ◦ f = IX .

Then, we have
g1 = g1 ◦ IY = g1 ◦ ( f ◦ g2) = (g1 ◦ f ) ◦ g2 = IX ◦ g2 = g2.
This proves our assertion.

Example 2.3. By the reasoning given earlier in Q. 20, it follows that the function g given by

The next theorem proves that, in general, a function is invertible if and only if it is bijective.

Theorem 2.4. Let X and Y be two nonempty sets. A function f : X → Y has an inverse if and only if f is a
bijective function.

Proof. First, let there exists a function g : Y → X such that g ◦ f = IX and f ◦ g = IY . It then follows that
f is bijective (see (a) of Exercise ??). To prove the converse, suppose f is a bijective function. Then, for
every y ∈ Y there is a unique x ∈ X such that f (x) = y. We define g : Y → X by g(y) = x. It follows from the
definition that g satisfies the conditions as in (3.12). Hence, g is the inverse of the function f .
It follows easily that if f : X → Y is a bijective function then so is its inverse f −1 : Y → X (see (b) of
Exercise ??). The next theorem proves that the set operations are more well behaved with respect to inverse
functions.

Theorem 2.5. Let f : X → Y be an invertible function. Then

Q 2.4 Consider the three functions f : R → R, g : R → R, and h : R∗ → R given by (2021)

F(x) = 3x2 + 2, g(x) = 7x − 5, h(x) = 1/x.

Compute the composite functions f ◦ g ◦ h, g ◦ g, g ◦ h, and h ◦ g ◦ f .

DSTL compact notes

Definition 2.7. The Ackermann’s function A(x, y) is the total function given by

A (x+ 1, 0) = A( x, 1)

A( 0, y) = y + 1,

A( x + 1, y + 1) = A( x, A(x + 1, y)) .

The Ackermann function is an example of a recursive function that is not primitive recursive.

Q 2.5. Compute the Ackermann function A(2, 2).

Sol. For, by using the relation A(0, y) = y + 1, we have

A(0, 0) = 1, A(0, 1) = 2, A(0, 2) = 3,

A(0, 3) = 4, A(0, 4) = 5, A(0, 5) = 6.

Next, by using the two relations given by

A(x + 1, 0) = A(x, 1) and A(x + 1, y + 1) = A(x, A(x + 1, y)),

it follows that

A(1, 0) = A(0, 1) = 2;
A(1, 1) = A(0, A(1, 0)) = A(0, 2) = 3;
A(1, 2) = A(0, A(1, 1)) = A(0, 3) = 4;
A(1, 3) = A(0, A(1, 2)) = A(0, 4) = 5;
A(1, 4) = A(0, A(1, 3)) = A(0, 5) = 6;
A(1, 5) = A(0, A(1, 4)) = A(0, 6) = 7.

Finally, by using the relation

A(x + 1, y + 1) = A(x, A(x + 1, y)),
we obtain

A(2, 0) = A(1, 1) = 3;
A(2, 1) = A(1, A(2, 0)) = A(1, 3) = 5;
A(2, 2) = A(1, A(2, 1)) = A(1, 5) = 7.

Hence, we have A(2, 2) = 7

DSTL compact notes

2 Boolean Algebras and Applications

In all that follows, the next definition is important.

Definition 2.8. A Boolean algebra is a set with two special elements 0 and 1; two binary operations denoted
by + (sum) and · (product); and, a unary operation denoted by ′ (complementation) such that, for all
a, b, c ∈ B, the following five axioms hold:

B1. (Identity Laws) a + 0 = a and a · 1 = a;

B2. (Commutative Laws) a + b = b + a and a · b = b · a;

B3. (Associative Laws) a + (b + c) = (a + b) + c and a · (b · c) = (a · b)· c;

B4. (Distributive Laws) a · (b + c) = a · b + a · c and a + (b · c) = (a + b)· (a + c);

B5. (Complement Laws) a + a′ = 1 and a · a′ = 0.

We write a Boolean algebra as (B, +, · , ′ , 0, 1), where 0 is called the zero element and 1 is called the identity
element. Also, for a ∈ B, the element a′ ∈ B is called the complement of a.

2.1 Important Boolean Algebras

The algebra of sets P(X ) defined on a nonempty set X is a Boolean algebra, with respect to binary opera-
tions ∪ and ∩; usual “set complementation” as unary operation; and, by taking 0 ≡ ∅, 1 ≡ X . This is known
as the Boolean algebra of sets10 given by the set X .

Example 8.1 (Lattice Boolean Algebra). Let L, ≤, ∨, ∧ be a complemented distributive lattice, with
bounds denoted by 0 and 1, and a, b ∈ L. Since the join and meet of every pair of elements in L are unique,
it follows that ∨ and ∧ are binary operations on the set L. Since L is complemented distributive lattice, the
mapping a '→ a′ : L → L is well defined, where a′ denotes the complement of the element a. Now, taking ∨
as the sum + and ∧ as the product · , it follows from the problems solved in the previous section that all the
five axioms (B1) – (B5) hold, with the least element 0 of L as the zero element, and the greatest element 1
of L as the identity element. Therefore, every complemented distributive lattice is a Boolean algebra, which
is called the lattice Boolean algebra. For emphasis, we may this Boolean algebra as BL.

Example 8.2. We see here why a 3-point or a 5-point lattice cannot be a Boolean algebra. For, let L,
, ∨, ∧ be a complemented distributive lattice with 3 or 5 elements. We know that a boolean algebra has at
DSTL compact notes

least two elements, 0 and 1, which are respectively the minimum and maximum elements of L. Let x ∈ L be
the third element. Since 0 = x = 1, by unique complement property, we have 0 = x′ = 1. Therefore, x′ is the
fourth element of L. A similar argument applies if L has an additional element y = x.

Q 2.6. Show that the set B = {1, 2, 3, 6} is a Boolean algebra with respect to operations as given
below: a + b = lcm{a, b}, a · b = hcf{a, b}, a′ = 6.
a

Further, show that the set B = {1, 2, 4, 8} is a not a Boolean algebra with respect to + and · as above, and
8
x = .
x
Sol. We first show that the set B = {1, 2, 3, 6} is a Boolean algebra with respect to operations as given below:
a + b = lcm{a, b}, a · b = hcf{a, b}, a′ = 6.
a

The three operations +, · , and ′ , on the set B = {1, 2, 3, 6} are as given in Table 6.

+ 1 2 3 6 · 1 2 3 6 a
1 1 2 3 6 1 1 1 1 1 1 6
2 2 2 6 6 2 1 2 1 2 2 3
3 3 6 3 6 3 1 1 3 3 3 2
6 6 6 6 6 6 1 2 3 6 6 1

Table 6: Tables of operations +, · , and ′ on B = {1, 2, 3, 6}.

It follows from the first two tables that + and · are associative and commutative binary operations. Also,
each operation distributes over the other. Further, for any a ∈ {1, 2, 3, 6}, we have

Lcm{ a, 1} = a and hcf{a, 6}= a.

Therefore, the zero element 0 is given by the element 1, and the identity element 1 is given by the element
6. Further, the third table on the right side shows that the complementation laws hold. Notice that, for
a ∈ {1, 2, 3, 6}, we have

a + a′ = lcm{a, 6/a}= 6 ≡ 1 and a · a′ = hcf{a, 6/a}= 1 ≡ 0

Therefore, the set B = {1, 2, 3, 6} is a Boolean algebra with operations as given in the question.
Finally,we show that the set B = {1, 2, 4, 8} is a not a Boolean algebra with respect to + and · as defined
in the previous case. However, we now have x′ = 8/x. The three tables of operations +, · , and ′ on the
set B = {1, 2, 4, 8} are given in Table 7. As in the previous case, we have that + and · are associative and
commutative binary operations. Also, each operation distributes over the other. Further, the zero element 0
DSTL compact notes

+ 1 2 4 8 · 1 2 4 8 a
1 1 2 4 8 1 1 1 1 1 1 8
2 2 2 4 8 2 1 2 2 2 2 4
4 4 4 4 8 4 1 2 4 4 4 2
8 8 8 8 8 8 1 2 4 8 8 1

Table 7: Tables of operations +, · , and ′ on B = {1, 2, 4, 8}.

is given by the element 1, and the identity element 1 is given by the element 8. However, the third table on
the right side shows that the complementation laws doesn’t hold. For example, with a = 2, we have
a + a′ = lcm{ 2, 8/2}= 4 = 8 ≡ 1 and a · a′ = hcf{2, 8/2} = 2 = 1 ≡ 0.

Therefore, the set B = {1, 2, 4, 8} is not a Boolean algebra.

Q 2.7. Let B, +, ·, ′, 0, 1 be a Boolean algebra, and a, b ∈ B. Show that

(i) a + 1 = 1 and a · 0 = 0.

(ii) a · a + b = a and a + a · b = a.

(iii) a′ ′ = a.

(iv) 0′ = 1 and 1′ = 0.

(v) a + b = b ⇔ a·b = a ⇔ a · b′ = 0 ⇔ a′ + b = 1.

(vi) ab′ + a′b = 0 ⇔ a = b.

Sol. To prove the Idempotent Laws11 given by

a+a = a and a · a = a,

we have

a = a+0 (by B1)

= a + (a · a′) (by B5)
= (a + a)· (a + a′) (by B4)
= (a + a)· 1 (by B5)
= a+a (by B1);
DSTL compact notes

and also

a = a·1 (by B1)

= a · (a + a′) (by B5)
= (a · a) + (a · a′) (by B4)
= (a · a) + 0 (by B5)
= a·a (by B1)

Next, to prove the Absorption Laws given by

a· a+b = a and a + a · b = a,

we have

a · a + b = (a + 0)· a + b (by B1)

= a · (0 + b) (by B4)
= a+0 (by dominance Law)
=a (by B1)

Similarly, we can prove the other equality. Also, to prove the Involution Law given by a′ ′ = a, recall that
we have
a + a′ = 1 and a · a′ = 0,
, by B5, which also says that a is the complement of a′, i. e., a = (a′)′. Further, to prove the 0 - 1 Law given
by 0′ = 1 and 1′ = 0, recall that a · a′ = 0, by B5, so that

0′ = (a · a′)′ (by B5)

= a′ + (a′)′ (by DeMorgan Law)
= a′ + a (by part (iii))
=1 (by B5)

Once again, applying involution law, we obtain 0 = (0′)′ = 1′. We now prove the following equivalences

a+b = b ⇔ a·b = a ⇔ a · b′ = 0 ⇔ a′ + b = 1

First notice that both ways proof of the equivalence given below follows directly from the DeMorgan Laws,
and the previous part:
a · b′ = 0 ⇔ a′ + b = 1.

Now, suppose we have a + b = b. Then, we have

a · b = a · (a + b) = a,
DSTL compact notes

where the second equality is given by absorption law. To prove the reverse implication, suppose we have
a · b = a. Then, we have
a + b = (a · b) + b) = a
where the second equality is given by absorption law. It thus follows that

a+b = b ⇔ a · b = a.

To conclude the solution of part (v), we show that

a+b = b ⇔ a + b′ = 1.

First, suppose a + b = b. Then we have

a′ + b = a′ + (a + b) = (a′ + a) + b = 1 + b = 1,

where the last equality is given by dominance law. To prove other way implication, suppose a′ + b = 1.
Then we have
a + b = (a + b)· 1 = (a + b)· (a′ + b) = (a · a′) + b = 0 + b = b.
Notice that we trivially have
a=b ⇒ a · b′ + a′ · b = 0.

Finally, to conclude the solution, suppose a · b′ + a′ · b = 0. Then we have

a + (a · b′ + a′ · b) = a + 0 = a
⇒ a + a′ · b = a (by absorption Law)
⇒ (a + a′) · (a + b) = a (by B4)
⇒ 1 · (a + b) = a (by B5)
⇒ a+b = a (by B1)

We also have

b + (a · b′ + a′ · b) = b + 0 = b
⇒ b + a · b′ = b (by absorption Law)
⇒ (b + a)· (b + b′) = b (by B4)
⇒ (b + a)· 1 = b (by B5)
⇒ a+b = b (by B1 and B2)

Hence, we have a = b. This completes the solution of the question.

 DSTL compact notes

2.2 Boolean Expressions & Boolean Functions

Let B = {0, 1}, and B, +, ·,′ , 0, 1 be the 2-point Boolean algebra, where the three operations are defined
as in Table 8. Recall that the product set

Bn := (x1, . . . , xn) | each xi ∈ B

Table 8: Tables of operations {+, · }, and ′ on B = {0, 1}.

+ 0 1 + 0 1 a
0 0 1 0 0 0 0 1
1 1 1 1 0 1 1 0

has natural Boolean algebra structure with respect to operations defined pointwise. Also, the identity 1 and
the zero element 0 of Bn are respectively given by

1 := [1, 1 . . . , 1] and 0 := [0, 0, . . . , 0] .

However, we now follow the convention of writing the elements of Bn as strings x1 · · · xn of length n. In
this case, we say xi’s are Boolean variables taking values in the set B = {0, 1}. In all that follows, we take
n ≤ 5. Also, let Fe denotes the function : Bn → B obtained by evaluating a Boolean expression E(x1, . . . , xn)
at 2n values in the Boolean algebra Bn. We call Fe (or simply F) the Boolean function associated with the
expression E.

Q 2.8. Simplify the following Boolean expresions by algebraic manipulation:

(i) x · y + z · xy + xz ′ .

(ii) a + a′ · b · c′ + b + c ′.

Sol. We simplify the following two Boolean expressions by algebraic manipulation:

′
(i) x· y+z· x·y+x·z .

′
(ii) a + a′ · b · c′ + b + c .
DSTL compact notes

For (i), we have

x · y + z · xy + xz ′ = x · y + z · (xy)′ · (xz)′ (by DeMorgan Law)

= x · y + z · (x′ + y′) · (x′ + z′) (by DeMorgan Law)
= x · y + (x′ + y′) · z · (x′ + z′) (by B2 and B3)
= x · y + (x′ + y′) · z · x′ + z · z′ (by B4)

= x · y + (x′ + y′) · z · x′ + 0 (by B5)

= x · y + (x′ + y′) · (z · x′) (by B5)

= x · y + x′ · (z · x′) + y′ · (z · x′) (by B4)

= x · y + x · x′ · (z · x′) + x · y′ · (z · x′) (by B4)
= x · y + 0 · (z · x′) + y′ · z · 0 (by B5 and B2)
= x·y+0+0 = x·y (by Dominance Law and B5)

Next, for (ii), we have

a + a′ · b · c′ + b + c ′ = a + a′ · b · c′ + b′ · c′ (by DeMorgan Law)

= a + (a′ · b + 1)· c′ (by B4)
= a + 1 · c′ (by Dominance Law)
= a + c′ (by B1)

This completes the solution.

Q 2.9. Obtain the DNF associated with the Boolean expressions given by

F( x, y, z) = yz + xz′ xy′ + z′ ′and g( x1, x2, x3) = x1x2′ + x3, by

using truth table method, and also by applying algebraic methods.

Sol. We have to obtain the DNF of the expressions given by

′
F( x, y, z) = y · z + x · z′ · x · y′ + z′ and g( x1, x2, x3) = x1 · x2′ + x3,

by using truth table method, and also by algebraic method. The truth tables of Boolean expressions f and g
are obtained as in Table 9. Now, since only two entries in the last column of the left side table are 1’s, with
associated maxterms x′ · y · z and x · y · z, it thus follows that the DNF of f is given by x′ · y · z + x · y · z. Next,
considering 1 entries in the last column of the right side table, we find that the maxterms are

x1′ · x2′ · x3, x1′ · x2 · x3, x1 · x2′ · x3′ , x1 · x2′ · x3, and x1 · x2 · x3.
DSTL compact notes

Table 9: Truth Tables for Boolean functions of Q.2.9.

x y z (y · z + x · z′) · (x · y′ + z′)′
0 0 0 0 0 0 0 0
0 0 1 0 0 0 1 1
0 1 0 0 0 1 0 0
0 1 1 1 0 1 1 1
1 0 0 0 1 0 0 1
1 0 1 0 1 0 1 1
1 1 0 0 1 1 0 0
1 1 1 1 1 1 1 1

Therefore, the DNF of g is given by

x1′ · x2′ · x3 + x1′ · x2 · x3 + x1 · x2′ · x3′ + x1 · x2′ · x3 + x1 · x2 · x3.

For the second part, recall that the algebraic method involves inserting missing literals using the identity
a · 1 = a. However, we first need to clear complementation (if any involved) by using DeMorgan laws. For
the given f , this is the case. Therefore, by applying the DeMorgan laws, we obtain

′
f x, y, z = y · z + x · z′ · x · y′ + z′

= y · z + x · z′ · (x′ + (y′)′) · z
= y · z + x · z ′ · x′ · z + y · z

= (y · z) · (x′ · z) + (x · z′) · (x′ · z) + (y · z) · (y · z) + (x · z′) · (y · z)

= x′ · y · z + y · z

It thus follows from the identity

y · z = 1 · y · z = (x + x′) · y · z = x · y · z + x′ · y · z

that the DNF of f is given by

x′ · y · z + x · y · z + x′ · y · z = x′ · y · z + x · y · z.
DSTL compact notes

Similarly, the DNF of the expression g by the algebraic method is obtained as follows:

g x1, x2, x3 = x1 · x2′ + x3

= (x1 · x2′ ) · 1 + 1 · x3
= x1 · x2′ · (x3 + x3′ ) + (x1 + x1′ ) · x3
= x1 · x2′ · x3 + x1 · x2′ · x3′ + x1 · x3 + x1′ · x3
= x1 · x2′ · x3 + x1 · x2′ · x3′ + x1 · 1 · x3 + x1′ · 1 · x3
= x1 · x2′ · x3 + x1 · x2′ · x3′ + x1 · (x2 + x2′ ) · x3 + x1′ · (x2 + x2′ ) · x3
= x1 · x2′ · x3 + x1 · x2′ · x3′ + x1 · x2 · x3 + x1 · x2′ · x3 + x1′ · x2 · x3 + x1′ · x2′ · x3
= x1 · x2′ · x3 + x1 · x2′ · x3′ + x1 · x2 · x3 + x1′ · x2 · x3 + x1′ · x2′ · x3,

by using the identity a + a = a to obtain the last equality. This completes the solution.
Q 2.10. Obtain the CNF associated with the Boolean expressions given by

f ( x, y, z) = x + z · y and g(x1, x2, x3) = x2x3 + x1x3′ x1x2′ + x3 ′,

by using truth table method, and also by applying algebraic methods.

Sol. We have to obtain the CNF of the expressions given by

f ( x, y, z) = x + z · y and g(x1, x2, x3) = x2x3 + x1x3′ · x1x2′ + x3 ′,

by using truth table method, and also by algebraic method. The truth tables of Boolean expressions f and
g are obtained as in Table 10. Now, since five entries in the last column of the left side table are 0’s, with
associated minterms x′ + y′ + z′, x′ + y′ + z, x′ + y + z′, x + y′ + z′, and x′ + y′ + z, it thus follows that the CNF
of f is obtained as

Table 10: Truth Tables for Boolean functions of Q.2.10.

x y z (x + z) · y (x2x3 + x1x3′ ) · (x1x2′ + x3)′

0 0 0 0 0 0 0 0
0 0 1 0 0 0 1 0
0 1 0 0 0 1 0 0
0 1 1 1 0 1 1 0
1 0 0 0 1 0 0 0
1 0 1 1 1 0 1 0
1 1 0 0 1 1 0 1
1 1 1 1 1 1 1 0

x′ + y′ + z ′ · x′ + y′ + z · x′ + y + z ′ · x + y′ + z ′ · x ′ + y′ + z .
DSTL compact notes

Next, considering 0 entries in the last column of the right side table, we find that the minterms are

x1′ + x2′ + x3′ , x1′ + x2′ + x3, x1′ + x2 + x3′ , x1′ + x2 + x3,
x1 + x2′ + x3′ , x1 + x2′ + x3, and x1 + x2 + x3

Therefore, the CNF of g is given by the product of the above seven terms. For the second part, recall that
the algebraic method involves inserting missing literals using the identity a + 0 = a. Therefore, in this case,
we have

f x, y, z = x + z · y
= x+0+z · 0+y
= x + y · y′ + z · x · x′ + y
= x + y + z · x + y′ + z · x + y · x′ + y
= x + y + z · x + y′ + z · x + y + 0 · x′ + y + 0
= x + y + z · x + y′ + z · x + y + z · z′ · x′ + y + z · z′
= x + y + z · x + y′ + z · x + y + z · x + y + z′ · x′ + y + z · x′ + y + z′
= x + y + z · x + y′ + z · x + y + z′ · x′ + y + z · x′ + y + z′ ,

by using the identity a · a = a to obtain the last equality. This is the CNF of the expression f . Finally,
to obtain the CNF of the expression g by algebraic method, we first clear the complementation by using
DeMorgan laws. For, we have

g x1, x2, x3 = x2 · x3 + x1 · x3′ · x1 · x2′ + x3 ′

= x2 · x3 + x1 · x3′ · (x1 · x2′ )′ · x3′

= x2 · x3 + x1 · x3′ · x1′ · x3′ + x2 · x3′

= x2 · x3 · x1′ · x3′ + x2 · x3 · x2 · x3′ + x1 · x3′ · x1′ · x3′ + x1 · x3′ · x2 · x3′
= x1 · x2 · x3′ .

Now, by using the identities a + 0 = a and a · a′ = 0 repeatedly, we have

x1 = x1 + x2 · x1 + x2′
= x1 + x2 + x3 · x1 + x2 + x3′ · x1 + x2′ + x3 · x1 + x2′ + x3′ ;
x2 = x1 + x2 · x1′ + x2
= x1 + x2 + x3 · x1 + x2 + x3′ · x1′ + x2 + x3 · x1′ + x2 + x3′ ;
x3′ = x1 + x3′ · x1′ + x3′
= x1 + x2 + x3′ · x1 + x2′ + x3′ · x1′ + x2 + x3′ · x1′ + x2′ + x3′ .
DSTL compact notes

It thus follows that the CNF of g is given by the following product:

x1 + x2 + x3 · x1′ + x2 + x3 · x1 + x2′ + x3 · x1 + x2 + x3′ · x1 + x2′ + x3′ · x1′ + x2 + x3′ · x1′ + x2′ + x3′

This completes the solution.

2.3 Applications: Karnaugh Map

A Karnaugh map is a 2D or a 3D geometric representation of the Boolean function associated with a Boolean
expression representing some logic circuit. The main emphasis here is use this concept to obtain a minimal
SOP or POS form of a Boolean expression.

A minterm term in the case of an SOP or a maxterm term in the case of a POS is called an implicant.
Also, by prime implicants we mean all possible circles that can be formed in the K-Map. And, the prime
implicants that always appear in the final minimal form is known as the essential prime implicants. We
start with the next important definition.

Definition 2.9 The Karnaugh map (or simply a K-map) is a geometric way to visualise the Boolean
function F : Bn → B of a Boolean expression E(x1, . . . , xn), with n ≤ 6. It is a grid of 2n squares such that
each square has two adjacent squares, when n = 2; each square has three adjacent squares, when n = 3;
each square has four adjacent squares, when n = 4; and, so on (see Fig 26). For each of the 2n input values
taken from the product algebra Bn, the corresponding square has 1 or 0 as the F-value of the expression
E. A minterm is represented by a square with F-value 1, and a maxterm is represented by a square with
F-value 0.

cd
00 01 11 10
ab

00 1 1 1 1
y yz
x 0 1 x 00 01 11 10 01 1 1 1 1

0 1 0 0 0 1 0 0 11 0 0 0 0

1 1 0 1 1 1 0 1 10 1 1 1 0

Figure 2.5: K-maps of a Boolean functions in two and three variables.

In more precise geometric terms, , for n = 3, a K-map is a cylinder obtained by identifying the shorter edges
of the 23-grid; and, , for n = 4, a K-map is a torus obtained by identifying opposite edges of the 24-grid.
 DSTL compact notes

To obtain a minimal sum of products (or simply SOP) form of a Boolean expression, we circle together
squares with F-value 1 in powers of 2. Similarly, to obtain a minimal product of sums (or simply POS), we
circle together squares with F-value 0 in powers of 2. Notice that circling (or grouping) two squares elim-
inates one variable; circling four squares eliminates two variables, and so on12. A minterm (or a maxterm)
is said to be covered if it is included in at least one circle of 1’s (or a circle of 0’s). We need to remember
the following five aspect of a K-map while computing a minimal form of a Boolean function, say an SOP:

1. Begin with loneliest squares to ensure adjacencies offer more possible combinations, which must be
combined at a later stage of the process. By adjacencies we mean minterms with multiple adjacent
minterms.

2. Circle together as many squares as possible. Of course, the larger the circle, fewer would be the number
of literals in sought after SOP.

3. Cover all squares making as few circles as possible. Of course, lesser the number of circles, the fewer
would be the number of product terms in minimised SOP.

4. In steps 2 and 3, a minterm can be used any number of times, subject to that it is being used at least
once.

5. Stop when all the minterms are used at least once.

The algorithm given below helps to follow the above guidelines, and to ensure a high likelihood of finding
the minimal SOP of a given Boolean expression. The aim is to find a minimum set of prime implicants that
covers the associated Boolean function. The following algorithm generally finds a minimal solution in an
easy way. However, as random choices are allowed in Step-1 and Step-2, no optimality is claimed in finding
the minimum cover for the associated Boolean function.

1. Count the number of adjacencies for each minterm of the K-map.

2. Select an uncovered minterm with lowest number of adjacencies. Choose randomly when more than
one choices are available.

3. Generate a prime implicant for the chosen minterm and put it in the cover. In case it is covered by more
than one prime implicant, select the one that covers the most uncovered minterms.

4. Keep repeating the previous two steps until all minterms are covered.
DSTL compact notes

x yz
yz 00 01 11 10 x 00 01 11 10

0 1 0 0 1 0 0 1 0 0

1 0 1 0 1 1 1 1 0 1

Figure 2.6: K-maps of a Boolean functions in three variables.

Q 2.11. Use Karnaugh map to find the minimal SOP expression for the function

F(x, y, z) = ∑( 0, 2, 5, 6) .

Also draw the associated digital circuits.

Sol. We need to find a minimal SOP expression for the function

F( x, y, z) = ∑( 0, 2, 5, 6) .

The associated K-map, and circling of 1’s is as shown in the left and right side pictures of Fig. 27. Therefore,
a minimal SOP expression is given by y′z + xz′. It is easy to draw the associated digital circuits.

Q 2.12. Use Karnaugh map to find the minimal SOP expression for the function

F(u, v, w) = uv′w′ + uvw′ + uvw + u′v′w.

Also draw the associated digital circuits.

Sol. We need to find the minimal SOP expression for the function

F(u, v, w) = uv′w′ + uvw′ + uvw + u′v′w.

Notice that we have

F(u, v, w) = uv′w′ + uvw′ + uvw + u′v′w

= 100 + 110 + 111 + 001
= ∑(1, 4, 5,6 )

The associated K-map, and circling of 1’s is as shown in the left and right side pictures of Fig. 28. Therefore,
a minimal SOP expression is given by yz′ + x′y′z′ + xy′z. It is easy to draw the associated digital circuits.
DSTL compact notes

yz yz
x 00 01 11 10 x 00 01 11 10

0 0 1 0 0 0 1 0 0 1

1 1 1 0 1 1 0 1 0 1

Figure 2.7: K-maps of a Boolean functions in three variables.

cd cd
00 01 11 10 00 01 11 10
ab ab

00 1 1 1 1 00 1 1 1 1

01 1 1 1 1 01 1 1 1 1

11 0 0 0 0 11 0 0 0 0

10 1 1 1 0 10 1 1 1 0

Figure 2.8: K-maps and circling for Q.12.

Q 2.13. Use Karnaugh map to find the minimal SOP expression for the function

F(a, b, c, d) = ∑ (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11) .

Also draw the associated digital circuits.

Sol. We need to find the minimal SOP of the Boolean expression given by

F(a, b, c, d) = ∑ (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11) .

For the given Boolean expression, the K-map and circling of 1’s are as shown in the left and right side
pictures of Fig. 29. Therefore, a minimal SOP expression is given by a′ + b′c′ + b′cd. It is easy to draw the
associated digital circuits.

Q 2.14. Use Karnaugh map to find the minimal SOP expression for the function

F(x, y, u, v) = x′y′u′v′ + x′y′u′v + x′y′uv′ + x′yu′v′ + x′yu′v + x′yuv′ + xy′u′v′ + xy′u′v + xyuv.

Also draw the associated digital circuits.

Compact Notes: Comments & Solved Problems 24

uv uv
00 01 11 10 00 01 11 10
xy xy

00 1 1 0 1 00 1 1 0 1

01 1 1 0 1 01 1 1 0 1

11 0 0 1 0 11 0 0 1 0

10 1 1 0 0 10 1 1 0 0

Figure 2.9: K-maps and circling for Q.2.14.

Sol. We need to find the minimal SOP expression for the function

F(x, y, u, v) = x′y′u′v′ + x′y′u′v + x′y′uv′ + x′yu′v′ + x′yu′v + x′yuv′ + xy′u′v′ + xy′u′v + xyuv.

By simple conversion from binary to digits, it follows that we can write

F( x, y, u, v) = ∑(0, 1, 2, 4, 5, 6, 8, 9, 15) .

For the above expression, the K-map and circling of 1’s are as shown in the left and right side pictures of
Fig. 30. Therefore, a minimal SOP expression is given by a′c′ + a′cd′ + ab′c′ + abcd. It is easy to draw the
associated digital circuits.