DSTL Quantum PDF by Motivation Bank
DSTL Quantum PDF by Motivation Bank
DSTL Quantum PDF by Motivation Bank
in
1 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
QUANTUM SERIES
For
B.Tech Students of Second Year
of All Engineering Colleges Affiliated to
Dr. A.P.J. Abdul Kalam Technical University,
Uttar Pradesh, Lucknow
(Formerly Uttar Pradesh Technical University)
By
Dr. Anuj Bhardwaj Dr. Parul Tiwari
M.Sc., Ph.D M.Sc., Ph.D
TM
CO 1 Write an argument using logical notation and determine if the argument is or is not valid. K3, K4
CO 2 Understand the basic principles of sets and operations in sets. K1, K2
Demonstrate an understanding of relations and functions and be able to determine their
CO 3 K3
properties.
CO 4 Demonstrate different traversal methods for trees and graphs. K1, K4
CO 5 Model problems in Computer Science using graphs and trees. K2, K6
CONTENTS
Part-1 : Set Theory : Introduction, ........................ 1–2C to 1–5C
Combination of Sets, Multisets
PART-1
Set Theory : Introduction, Combination of Sets, Multisets.
Questions-Answers
Answer
1. A set is a collection of well defined objects, called elements or members
of the set.
2. These elements may be anything like numbers, letters of alphabets,
points etc.
3. Sets are denoted by capital letters and their elements by lower case
letters.
4. If an object x is an element of set A, we write it as x A and read it as ‘x
belongs to A’ otherwise x A (x does not belong to A).
Types of set :
1. Finite set : A set with finite or countable number of elements is called
finite set.
2. Infinite set : A set with infinite number of elements is called infinite
set.
3. Null set : A set which contains no element at all is called a null set. It is
denoted by or { }. It is also called empty or void set.
4. Singleton set : A set which has only one element is called singleton set.
5. Subset : Let A and B be two sets, if every elements of A also belongs to
B i.e., if every element of set A is also an element of set B, then A is
called subset of B and it is denoted by A B.
Symbolically, A B if x A x B.
6. Superset : If A is subset of a set B, then B is called superset of A.
7. Proper subset : Any subset A is said to be proper subset of another set
B, if there is at least one element of B which does not belong to A, i.e., if
A B but A B. It is denoted by A B.
8. Universal set : In many applications of sets, all the sets under
consideration are considered as subsets of one particular set. This set is
called universal set and is denoted by U.
9. Equal set : Two set A and B are said to be equal if every element of A
belong to set B and every element of B belong to set A. It is written as
A = B.
Symbolically, A = B if x A and x B.
Discrete Structures & Theory of Logic 1–3 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
10. Disjoint set : Let A and B be two sets, if there is no common element
between A and B, then they are said to be disjoint.
Answer
1. Union : Let A and B be two sets, then the union of sets A and B is a set
that contain those elements that are either in A or B or in both. It is
denoted by A B and is read as ‘A union B’.
Symbolically, A B = {x|x A or x B}
For example : A = {1, 2, 3, 4 }
B = {3, 4, 5, 6 }
A B = {1, 2, 3, 4, 5, 6}
2. Intersection : Let A and B be two sets, then intersection of A and B is
a set that contain those elements which are common to both A and B. It
is denoted by A B and is read as ‘A intersection B’.
Symbolically, A B = {x|x A and x B}
For example : A = {1, 2, 3, 4}
B = {2, 4, 6, 7}
then A B = {2, 4}
3. Complement : Let U be the universal set and A be any subset of U,
then complement of A is a set containing elements of U which do not
belong to A. It is denoted by Ac or A or A .
Symbolically, Ac = {x|x U and x A}
For example : U = {1, 2, 3, 4, 5, 6}
and A = {2, 3, 5}
then Ac = {1, 4, 6}
4. Difference of sets : Let A and B be two sets. Then difference of A and
B is a set of all those elements which belong to A but do not belong to B
and is denoted by A – B.
Symbolically, A – B = {x|x A and x B}
For example : Let A = {2, 3, 4, 5, 6, 7}
and B = {4, 5, 7}
then A – B = {2, 3, 6}
5. Symmetric difference of set : Let A and B be two sets. The symmetric
difference of A and B is a set containing all the elements that belong to
A or B but not both. It is denoted by A B or A B.
Also A B = (A B) – (A B)
For example : Let A = {2, 3, 4, 6}
B = {1, 2, 5, 6}
then A B = {1, 3, 4, 5}
Answer
1. Multisets are sets where an element appear more than once,
More pdf : www.motivationbank.in
1–4 C (CS/IT-Sem-3) Set Theory, Functions & Natural Numbers
Que 1.4. Let P and Q be two multisets {4.a, 3.b, 1.c} and {3.a, 3.b,
2.d} respectively. Find
i. P Q, ii. P Q, iii. P – Q, iv. Q – P, v. P + Q.
Answer
i. P Q = {4.a, 3.b, 1.c, 2.d}
ii. P Q = {3.a, 3.b}
iii. P – Q = {1.a, 1.c}
iv. Q – P = {2.d}
v. P + Q = {7.a, 6.b, 1.c, 2.d}
Answer
i. A = {2}
ii. B = {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60}
iii. C = {1, –1}
iv. D = {1}
v. E = {3, 5, 6, 10, 15 ....}
Answer
i. A = {x|x is an integer and –4 x 3}
ii. B = {x|x = n3, where 1 n 4, n is natural number}
iii. C = {x|x = 3n, where n is natural number}
iv. D = {x|x is the integer and prime number}
PART-2
Ordered Pair, Proof of Some General Identities on Sets.
Questions-Answers
Answer
Let A, B, C be any three sets and U be the universal set, then following are
the laws of algebra of sets :
1. Idempotent laws :
a. A A = A
b. A A = A
2. Commutative laws :
a. A B = B A
b. A B = B A
3. Associative laws :
a. A (B C) = (A B) C
b. A (B C) = (A B) C
4. Distributive laws :
a. A (B C) = (A B) (A C)
b. A (B C) = (A B) (A C)
5. Identity laws :
a. A = A
b. A U = A
c. A U = U
d. A =
6. Involution law :
a. (Ac)c = A
More pdf : www.motivationbank.in
1–6 C (CS/IT-Sem-3) Set Theory, Functions & Natural Numbers
7. Complement laws :
a. A Ac = U
b. A Ac =
c. Uc =
d. c = U
8. De Morgan’s laws :
a. (A B)c = Ac Bc
b. (A B)c = Ac Bc
9. Absorption laws :
a. A (A B) = A
b. A (A B) = A
Que 1.8. Prove for any two sets A and B that, (A B) = A B.
Answer
Let x (A B)
xAB
x A and x B
x A and x B
x A B
(A B) A B ...(1.8.1)
Now, let x A B
x A and x B
x A and x B
x (A B)
x (A B)
(AB) (A B) ...(1.8.2)
From eq. (1.8.1) and (1.8.2), (A B) = A B
Answer
Since U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Let the subset of all odd integers be s1, i.e.,
s1 = {1, 3, 5, 7, 9}
subset of all even integers be s2, i.e.,
s2 = {2, 4, 6, 8, 10}
and the subset of integers not exceeding 5 be s3, i.e.,
s3 = {1, 2, 3, 4, 5}
The bit string by characteristic function is given as follows :
Discrete Structures & Theory of Logic 1–7 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
Bit string for s1 is 1010101010
Bit string for s2 is 0101010101
Bit string for s3 is 1111100000
Que 1.10. If A and B are two subsets of universal set, then prove
the following :
a. (A – B) = (B – A) iff A = B
b. (A – B) = A iff A B =
Answer
a. Let A=B
Consider any element x A – B
x A and x B
x B and x A [ A = B]
x B–A
A–B B–A ...(1.10.1)
Conversely, if xB–A
x B and x A
x A and x B
xA–B
B–A A–B ...(1.10.2)
From eq. (1.10.1) and (1.10.2), we have
If A= BA–B=B–A
Now let A–B= B–A
Let x A – B as A – B = B – A
x B–A
Now x A – B x A and x B ...(1.10.3)
and x B – A x B and x A ...(1.10.4)
Eq. (1.10.3) and (1.10.4), can hold true when A = B
b. Let A–B= A
To show AB=
Let A B and let x A B and x
x A and x B
x (A – B) and x B [ A – B = A]
x A and x B and x B
x
which is a contradiction.
AB=
Now conversely, let A B =
To show A – B = A
Let xA–B
x A and x B
xA [as A B = ]
A–B A ...(1.10.5)
Conversely, let x A
x A and x B [as A B = ]
More pdf : www.motivationbank.in
1–8 C (CS/IT-Sem-3) Set Theory, Functions & Natural Numbers
xA–B
AA–B ...(1.10.6)
From eq. (1.10.5) and (1.10.6),
A=A–B
PART-3
Relations : Definition, Operation on Relations, Properties of
Relation, Composite Relation, Equality of Relation, Recursive
Definition of Relation, Order of Relation.
Questions-Answers
Que 1.11. Describe the term relation along with its types.
Let A and B be two non-empty sets, then R is relation from A to B if R is
subset of A × B and is set of ordered pair (a, b) where a A and b B. It is
denoted by aRb and read as “a is related to b by R”.
Symbolically, R = {(a, b) : a A, b B, a R b }
If (a, b) R then a R b and read as “a is not related to b by R”.
For example :
Let A = {1, 2, 3, 4}, B = {1, 2} and aRb iff a × b = even number
Then R = {(1, 2), (2, 1), (2, 2), (3, 2), (4, 1), (4, 2)}
Types of relation :
1. Universal relation : A relation R is called universal relation on A if
R = A × A. In case where R is defined from A to B, then R is universal
relation if R = A × B.
For example :
If A = {1, 2, 3}
then R = {(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1),
(3, 2), (3, 3)}
is universal relation over A.
2. Identity relation : A relation R is called identity relation on A if
R = {(a, a)|a A}. It is denoted by IA or A or . It is also called diagonal
relation.
For example :
If A = {1, 2, 3}, then IA = {(1, 1), (2, 2), (3, 3)}
is identity relation on A.
3. Void relation : A relation R is called a void relation on A if R = . It is
also called null relation.
For example :
If A = {1, 2, 3} and R is defined as R = {(a + b) |a + b > 5}, a, b A then
R = .
Discrete Structures & Theory of Logic 1–9 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
4. Inverse relation : A relation R defined from B to A is called inverse
relation of R defined from A to B if
R–1 = {(b, a) : b B and a A and (a, b) R}.
For example : Consider relation
R = {(1, 1), (1, 2), (1, 3), (3, 2)}
then R–1 = {(1, 1), (2, 1), (3, 1), (2, 3)}
5. Complement of a relation : Let relation R is defined from A to B, then
complement R is set of ordered pairs {(a, b) : (a, b) R}. It is also called
complementary relation.
For example :
Let A = {1, 2, 3} B = {4, 5}
Then A × B = {(1, 4), (1, 5), (2, 4), (2, 5), (3, 4), (3, 5)}
Let R be defined as R = {(1, 4), (3, 4), (3, 5)}
Then RC = R = {(1, 5), (2, 4), (2, 5)}
Answer
1. Relations are sets of ordered pairs so all set operations can be done on
relations.
2. The resulting sets contain ordered pairs and are, therefore, relations.
3. If R and S denote two relations, then R S, known as intersection of
R and S, defines a relation such that
x(R S) y = x R y x S y
4. Similarly, R S, known as union of R and S, such that
x(R S) y = x R y x S y
Also, x(R – S) y = x R y x $ y where R – S is known as different
of R and S
and x(R) y = x R y where R is the complement of R
For example : A = {x, y, z}, B = {x, y, z}, C = {x, y, z}
D = {Y, z}, R = {(x, X), (x, Y), (y, z)}
S = {(x, Y), (y, z)}
The complement of R consists of all pairs of the Cartesian product
A × B that are not R. Thus A × B = {(x, X), (x, Y), (x, Z), (y, X), (y, Y),
(y, Z), (z, X), (z, Y), (z, Z)}
Hence R = {(x, Z), (y, X), (y, Y), (z, X), (z, Y), (z, Z)}
R S = {(x, X), (x, Y), (y, Z)}
R S = {(x, Y), (y, Z)}
R – S = {(x, Y)}
Que 1.13. Give properties of relation.
Answer
Properties of relation are :
1. Reflexive relation : A binary relation R on set A is said to be reflexive
if every element of set A is related to itself.
More pdf : www.motivationbank.in
1–10 C (CS/IT-Sem-3) Set Theory, Functions & Natural Numbers
Answer
a. Equivalence relation :
1. A relation R on a set A is said to be equivalence relation if it is
reflexive, symmetric and transitive.
2. The two elements a and b related by an equivalence relation are
called equivalent.
3. So, a relation R is called equivalence relation on set A if it satisfies
following three properties :
i. (a, a) R a A (Reflexive)
ii. (a, b) R (b, a) R (Symmetric)
iii. (a, b) R and (b, c) R (a, c) R (Transitive)
b. Composition of relation :
1. Let R be a relation from a set A to B and S be a relation from set B
to C then composition of R and S is a relation consisting or ordered
pair (a, c) where a A and c C provided that there exist b B such
that (a, b) R A × B and (b, c) S B × C. It is denoted by RS.
Discrete Structures & Theory of Logic 1–11 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
2. Symbolically, R S = {(a, c)| b B such that (a, b) R and
(b, c) S}
Answer
1. The characteristic function CR of a relation R Nk is defined as follows :
– CS(X1, ..., Xk) = 1 if <X1, ..., Xk> S
– CS(X1, ..., Xk) = 0 if <X1, ..., Xk> S
2. A relation R is a recursive set iff its characteristic function CR is a
recursive function.
3. Examples of recursive relations : <, >, , =
c<(x, y) = sg(y x)
c>(x, y) = sg(x y)
c(x, y) = sg (x y)
c=(x, y) = sg (x y) ×c(x, y) = sg (y x)
4. Consider relation R(x, y, z) defined as follows :
– R(x, y, z) iff y × z x
5. We see that R is the result of substituting the recursive function × into
recursive relation .
6. Thus, R is recursive.
7. (Technically, R is the result of substituting the functions f1(x, y, z) = y ×
z and f2(x, y, z) = x into , and we need to show that f1(x, y, z) = y × z and
f2(x, y, z) = x are recursive ... but that’s trivial using the identity
functions).
Que 1.16. Define the term partial order relation or partial ordering
relation.
Answer
A binary relation R defined on set A is called Partial Order Relation (POR) if
R satisfies following properties :
i. (a, a) R a A (Reflexive)
ii. If (a, b) R and (b, a) R, the a = b (Antisymmetric)
iii. If (a, b) R and (b, c) R (a, c) R where a, b, c A (Transitive)
A set A together with a partial order relation R is called partial order set or
poset.
Que 1.17. Write short notes on :
a. Closure of relations
b. Total order
c. Compatibility relation
More pdf : www.motivationbank.in
1–12 C (CS/IT-Sem-3) Set Theory, Functions & Natural Numbers
Answer
a. Closure of relations :
i. Reflexive closure : Let R be a relation defined on set A. The
R IA is called reflexive closure of R, where IA = {(a, a)|a A} is
diagonal or identity relation.
ii. Symmetric closure : Let R be a relation defined on set A. Then
R R–1 is called symmetric closure of R, where R–1 is inverse of R
on A.
b. Total order : A binary relation R on a set A is said to be total order iff it
is
i. Partial order
ii. (a, b) R or (b, a) R a, b A
It is also called linear order.
c. Compatibility relation : A binary relation R defined on set A is said to
be compatible relation if it is reflexive and symmetric. It is denoted by ‘’.
Answer
R = {(a, b) | a b (mod m)}
For an equivalence relation it has to be reflexive, symmetric and transitive.
Reflexive : For reflexive a we have (a, a) R i.e.,
a a (mod m)
a – a is divisible by m i.e., 0 is divisible by m
Therefore aRa, a Z, it is reflexive.
Symmetric : Let (a, b) Z and we have
(a, b) R i.e., a b (mod m)
a – b is divisible by m
a – b = km, k is an integer
(b – a) = (– k) m
(b – a) = p m, p is also an integer
b – a is also divisible by m
b a (mod m ) (b, a) R
It is symmetric.
Transitive : Let (a, b) R and (b, c) R then
(a , b) R a – b is divisible by m
a – b = t m, t is an integer ...(1.18.1)
(b, c) R b – c is divisible by m
b – c = s m, s is an integer ...(1.18.2)
From eq. (1.18.1) and (1.18.2)
a – b + b – c = (t + s) m
a – c = lm, l is also an integer
Discrete Structures & Theory of Logic 1–13 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
a – c is divisible by m
a c (mod m), yes it is transitive.
R is an equivalence relation.
To show : (x1 + x2) (y1 + y2) :
It is given x1 y1 and x2 y2
i.e., x1 – y1 divisible by m
x2 – y2 divisible by m
Adding above equation :
(x1 – y1) + (x2 – y2) is divisible by m
(x1 + x2) – (y1 + y2) is divisible by m
i.e., (x1 + x2) (y1 + y2)
Que 1.19. Let R be binary relation on the set of all strings of 0’s
and 1’s such that R = {(a, b)|a and b are strings that have the same
number of 0’s}. Is R is an equivalence relation and a partial ordering
relation ? AKTU 2014-15, Marks 05
Answer
For equivalence relation :
Reflexive : a R a (a, a) R a R
where a is a string of 0’s and 1’s.
Always a is related to a because both a has same number of 0’s.
It is reflexive.
Symmetric : Let (a, b) R
then a and b both have same number of 0’s which indicates that again
both b and a will also have same number of zeros. Hence (b, a) R. It is
symmetric.
Transitive : Let (a, b) R, (b, c) R
(a, b) R a and b have same number of zeros.
(b, c) R b and c have same number of zeros.
Therefore a and c also have same number of zeros, hence (a, c) R.
It is transitive.
R is an equivalence relation.
For partial order, it has to be reflexive, antisymmetric and transitive. Since,
symmetricity and antisymmetricity cannot hold together. Therefore, it is not
partial order relation.
Que 1.20. Let A {1, 2, 3,..........., 13}. Consider the equivalence relation
on A × A defined by (a, b) R (c, d) if a + d = b + c. Find equivalence
classes of (5, 8). AKTU 2014-15, Marks 05
Answer
A = {1, 2, 3, ...., 13}
[(5, 8)] = [(a, b) : (a, b) R (5, 8), (a, b) A × A]
More pdf : www.motivationbank.in
1–14 C (CS/IT-Sem-3) Set Theory, Functions & Natural Numbers
= [(a, b) : a + 8 = b + 5]
= [(a, b) : a + 3 = b]
[5, 8] = {(1, 4), (2, 5), (3, 6), (4, 7)
(5, 8), (6, 9), (7, 10), (8, 11)
(9, 12), (10, 13)}
Answer
a. R = {(1, 3), (3, 1), (1, 1), (1, 2), (3, 3), (4, 4)}
Reflexive : (a, a) R a A
(1, 1) R, (2, 2) R
R is not reflexive.
Symmetric : Let (a, b) R then (b, a) R.
(1, 3) R so (3, 1) R
(1, 2) R but (2, 1) R
R is not symmetric.
Transitive : Let (a, b) R and (b, c) R then (a, c) R
(1, 3) R and (3, 1) R so (1, 1) R
(2, 1) R and (1, 3) R but (2, 3) R
R is not transitive.
Since, R is not reflexive, not symmetric, and not transitive so R is not an
equivalence relation.
b. R=A×A
Since, A × A contains all possible elements of set A. So, R is reflexive,
symmetric and transitive. Hence R is an equivalence relation.
Answer
i. (A, ) is a partially ordered relation if it is reflexive, antisymmetric and
transitive.
Reflexive : Let a A then by definition of relation, aRa a a which
is true.
Hence, the relation R i.e., is reflexive.
Antisymmetric : Let a, b A and
aRb b a
a b
Discrete Structures & Theory of Logic 1–15 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
b R a
aRb and bRa holds only when a = b. Relation is antisymmetric.
Transitive : Let a, b, c A and aRb and bRc
b a, c b
ca
aRc
Hence, relation is transitive.
Therefore, is a partial order relation.
ii. Since all the elements of the given set A are comparable to each other,
we always have a least upper bound and greatest lower bound for each
pair of elements of A and A is also a partial order relation. Hence, (A, )
is a lattice.
Answer
We have to show that the relation Rn is reflexive, symmetric, and transitive.
1. Reflexive : The relation Rn is reflexive because s = s, so that sRns
whenever s is a string in S.
2. Symmetric : If sRn t, then either s = t or s and t are both at least n
characters long that begin with the same n characters. This means that
tRn s. We conclude that Rn is symmetric.
3. Transitive : Now suppose that sRn t and tRn u. Then either s = t or s
and t are at least n characters long and s and t begin with the same n
characters, and either t = u or t and u are at least n characters long and
t and u begin with the same n characters. From this, we can deduce that
either s = u or both s and u are n characters long and s and u begin with
the same n characters, i.e., sRn u. Consequently, Rn is transitive.
Que 1.24. Let X = {1, 2, 3,....., 7} and R = {(x, y)|(x – y) is divisible by 3}.
Is R equivalence relation. Draw the digraph of R.
AKTU 2017-18, Marks 07
Answer
Given that X = {1, 2, 3, 4, 5, 6, 7}
and R = {(x, y) : (x – y) is divisible by 3 }
Then R is an equivalence relation if
More pdf : www.motivationbank.in
1–16 C (CS/IT-Sem-3) Set Theory, Functions & Natural Numbers
i. Reflexive : x X ( x x) is divisible by 3
So, ( x, x) X x X or, R is reflexive.
ii. Symmetric : Let x, y X and (x, y) R
(x – y) is divisible by 3 (x – y) = 3n1, (n1 being an integer)
(y – x) = – 3n2 = 3n2, n2 is also an integer
So, y – x is divisible by 3 or R is symmetric.
iii. Transitive : Let x, y, z X and (x, y) R, (y, z) R
Then x – y = 3n1, y – z = 3n2, n1, n2 being integers
x – z = 3(n1 + n2), n1 + n2 = n3 be any integer
So, (x – z) is also divisible by 3 or (x, z) R
So, R is transitive.
Hence, R is an equivalence relation.
1 3
2
4 7 6
5
PART-4
Function : Definition, Classification of Functions, Operations on
Functions, Recursively Defined Functions, Growth of Functions.
Questions-Answers
Que 1.25. Define the term function. Also, give classification of it.
Answer
1. Let X and Y be any two non-empty sets. A function from X to Y is a rule
that assigns to each element x X a unique element y Y.
2. If f is a function from X to Y we write f : X Y.
3. Functions are denoted by f, g, h, i etc.
4. It is also called mapping or transformation or correspondence.
Domain and co-domain of a function : Let f be a function from X to Y.
Then set X is called domain of function f and Y is called co-domain of function f.
Discrete Structures & Theory of Logic 1–17 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
Range of function : The range of f is set of all images of elements of X.
i.e., Range (f) = {y : y Y and y = f (x) x X }
Also Range (f) Y
Classification of functions :
1. Algebraic functions : Algebraic functions are those functions which
consist of a finite number of terms involving powers and roots of the
independent variable x.
Three particular cases of algebraic functions are :
i. Polynomial functions : A function of the form a0xn + a1xn–1+...
+ an where n is a positive integer and a0, a1, ...., an are real constants
and a0 0 is called a polynomial of x in degree n, for example
f (x) = 2x3 + 5x2 + 7x – 3 is a polynomial of degree 3.
f (x )
ii. Rational functions : A function of the form where f (x) and
g( x )
g(x) are polynomials.
iii. Irrational functions : Functions involving radicals are called
3
irrational functions. f(x) = x + 5 is an example of irrational
function.
2. Transcendental functions : A function which is not algebraic is called
transcendental function.
i. Trigonometric functions : Six functions sin x, cos x, tan x, sec x,
cosec x, cot x where the angle x is measured in radian are called
trigonometric functions.
ii. Inverse trigonometric functions : Six functions sin–1 x, cos–1 x,
tan–1 x, cot–1 x, sec–1 x, cosec–1 x, are called inverse trigonometric
functions.
iii. Exponential functions : A function f (x) = ax (a > 0) satisfying the
law a = a and axay = ax+y is called the exponential function.
iv. Logarithm functions : The inverse of the exponential function is
called logarithm function.
Answer
1. One-to-one function (Injective function or injection) : Let
f : X Y then f is called one-to-one function if for distinct elements of X
there are distinct image in Y i.e., f is one-to-one iff
f(x1) = f(x2) implies x1 = x2 x1, x2, X
A B
f
1 f b
2 c
3 d
Answer
If f: A B and g : B C be one-to-one onto functions, then g f is also one-
onto and (g f)–1 = f–1 g–1
Proof. Since f is one-to-one, f (x1) = f (x2) x1 = x2 for x1, x2 R
Again since g is one-to-one, g (y1) = g (y2) y1 = y2 for y1, y2 R
Now g f is one-to-one, since (g f) (x1) = (g f) (x2) g [f(x1)] = g [f (x2)]
f (x1) = f(x2 ) [g is one-to-one]
x1 = x2 [f is one-to-one]
Since g is onto, for z C, there exists y B such that g (y) = z. Also f being
onto there exists x A such that f (x) = y. Hence z = g (y)
= g [f (x)] = (g f) (x)
More pdf : www.motivationbank.in
1–20 C (CS/IT-Sem-3) Set Theory, Functions & Natural Numbers
This shows that every element z C has pre-image under gof. So, g f is
onto.
Thus, g f is one-to-one onto function and hence (g f)–1 exists.
By the definition of the composite functions, g f : A C. So,
(g f)–1 : C A.
Also g–1 : C B and f–1 : B A.
Then by the definition of composite functions, f–1 g–1 : C A.
Therefore, the domain of (g f)–1 = the domain of f–1 g–1.
Now (g f)–1 (z) = x (g f) (x) = z
g (f (x)) = z
g (y) = z where y = f (x)
y = g–1 (z)
f–1 (y) = f–1 (g–1 (z)) = (f–1 g–1) (z)
x = (f–1 g–1) (z) [f–1 (y) = x]
Thus, (g f)–1 (z) = (f–1 g–1) (z).
So, (g f)–1 = f–1 g–1.
Answer
a. Composition of functions :
If f : X Y and g : Y Z then the composition of f and g is a new function
from X to Z denoted by gof = g(f(x))
X Y Z
x y = f(x) z = g f(x)
f g
gf
fg
Fig. 1.29.1. Many one onto.
1. If f and g are considered to be relations then composition of f and g
was denoted by fog whereas the composition of function f and g is
denoted by gof.
2. Composition of functions is not commutative i.e., fog gof.
3. Composition of functions is associative i.e., fo(goh) = (fog)oh.
where h : X Y, g : Y Z, and f : Z W.
b. Recursive function (Recursively defined function) :
Sometimes it becomes difficult to define a function explicitly then it may
be easy to define this function in terms of itself. This technique is referred
as recursion.
Discrete Structures & Theory of Logic 1–21 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
This concept of recursion can be used to define sets, sequences and
algorithms also.
We will define three functions which are called Basis function or Initial
functions that are used in defining other functions by induction.
1. Zero function : (Z : z(x) = 0)
2. Successor function : (S : s(x) = x + 1)
3. Projection function or generalized identity function :
Uin : Uin ( x1 , x2 ,.... xn ) xi )
where superscripts n indicates a number of argument of the function
and subscripts i indicates the value of the function is equal to ith
argument.
c. Primitive recursion :
A function is called primitive recursion if and only if it can be constructed
from the initial functions and other known primitive recursive functions
by a finite number of operations and recursion only.
For example : Consider the function
f(x, y) = x + y
Now f(x, y + 1) = x + (y + 1)
= (x + y) + 1
= f(x, y) + 1
Also f(x, 0) = x + 0 = x
Now f(x, 0) = x = U11 (x) .....(1.29.1)
Also f(x, y + 1) = f(x, y) + 1
= S{f(x, y)} where S is the successor function
= {U33[x, y, f(x, y)]} ...(1.29.2)
If we consider g(x) = U11(x) and h(x, y, z) = S·U33 (x, y, z)
From eq. (1.29.1) and (1.29.2), we get f (x, 0) = g(x)
and f(x, y + 1) = h{x, y, f(x, y)}
Thus, f is obtained from the initial functions U11, U33 and S by applying
compositions once and recursion once. Hence, f is primitive recursive.
Answer
1. We need to approximate the number of steps required to execute any
algorithm because of the difficulty involved in expression or difficulty in
evaluating an expression. We compare one function with another
function to know their rate of growths.
2. If f and g are two functions we can give the statements like ‘f has same
growth rate as g’ or ‘f has higher growth rate than g’.
3. Growth rate of function can be defined through notation.
a. -Notation (Same order) : This notation bounds a function to
within constant factors. We say f(n) = g(n) if there exist positive
constants n0, c1 and c2 such that to the right of n0 the value of f(n)
always lies between c1g(n) and c2g(n) inclusive.
More pdf : www.motivationbank.in
1–22 C (CS/IT-Sem-3) Set Theory, Functions & Natural Numbers
c2 g(n)
f(n)
c1 g(n)
n
n 0 f(n) = (g(n))
Fig. 1.30.1.
1.37.1.
b. O-Notation (Upper bound) : This notation gives an upper bound
for a function to within a constant factor. We write f(n) = O(g(n)) if
there are positive constants n0 and c such that to the right of n0, the
value of f(n) always lies on or below cg(n).
cg(n)
f(n)
n
n0 f(n) = O(g(n))
Fig. 1.30.2.
cg(n)
n
n0 f(n) = (g(n))
Fig. 1.30.3.
PART-5
Natural Numbers : Introduction, Mathematical Induction,
Variants of Induction, Induction with Non-zero Base Cases.
Discrete Structures & Theory of Logic 1–23 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
Questions-Answers
Answer
Mathematical induction is a technique of proving a proposition over the
positive integers. It is the most basic method of proof used for proving
statements having a general pattern. A formal statement of principle of
mathematical induction can be stated as follows :
Let S(n) be statement that involve positive integer n = 1, 2, ... then
Step 1 : Verify S(1) is true. (Inductive base)
Step 2 : Assume that S(k) is true for some arbitrary k.
(Inductive hypothesis)
Step 3 : Verify S(k + 1) is true using basis of inductive hypothesis.
(Inductive step)
Answer
Let S(n) : n3 + 2n is divisible by 3.
Step I : Inductive base : For n = 1
(1)3 + 2.1 = 3 which is divisible by 3
Thus, S(1) is true.
Step II : Inductive hypothesis : Let S(k) is true i.e., k3 + 2k is divisible by
3 holds true.
or k3 + 2k = 3s for s N
Step III : Inductive step : We have to show that S(k + 1) is true
i.e., (k + 1)3 + 2(k + 1) is divisible by 3
Consider (k + 1)3 + 2(k + 1)
= k3 + 1 + 3k2 + 3k + 2k + 2
= (k3 + 2k) + 3(k2 + k + 1)
= 3s + 3l where l = k2 + k + 1 N
= 3(s + l)
Therefore, S(k + 1) is true
Hence by principle of mathematical induction S(n) is true for all
n N.
More pdf : www.motivationbank.in
1–24 C (CS/IT-Sem-3) Set Theory, Functions & Natural Numbers
1 1 1 n
Que 1.33. Prove by induction : + + ... + = .
1.2 2.3 n ( n + 1) (n + 1)
Answer
Let the given statement be denoted by S(n).
1. Inductive base : For n = 1
1 1 1
=
1.2 11 2
Hence S (1) is true.
2. Inductive hypothesis : Assume that S (k) is true i.e.,
1 1 1 k
..... =
1.2 2.3 k(k 1) k 1
3. Inductive step : We wish to show that the statement is true for
n = k + 1 i.e.,
1 1 1 k1
..... =
1.2 2.3 (k 1)(k 2) k2
1 1 1 1
Now, .....
1.2 2.3 k(k 1) ( k 1)(k 2)
k 1 k2 2k 1
=
k 1 ( k 1)(k 2) ( k 1)(k 2)
k1
=
k2
Thus, S(k + 1) is true whenever S(k) is true. By principle of mathematical
induction, S(n) is true for all positive integer n.
Answer
Basis : True for n = 1 i.e.,
L.H.S = a
a (r 1)
R.H.S = =a
r1
Therefore, L.H.S. = R.H.S.
Induction : Let it be true for n = k i.e.,
Discrete Structures & Theory of Logic 1–25 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
a (r k 1)
a + ar + ar2 + .... + ark–1 = ...(1.34.1)
r 1
Now we will show that it is true for n = k + 1 using eq. (1.34.1)
i.e., a + ar + ar2 +.... + ark-1 + ark
Using eq. (1.34.1), we get
a (r k 1)
+ ark
r 1
ar k a ar k1 ar k a ( r k 1 1)
= =
r 1 r 1
which is R.H.S. for n = k + 1, hence it is true for n = k + 1.
By mathematical induction, it is true for all n.
Answer
We prove this by induction on n.
Base case : For n = 1, 11n+1 + 122n–1 = 112 + 121 = 133 which is divisible by
133.
Inductive step : Assume that the hypothesis holds for n = k, i.e.,
11k+1 + 122k–1 = 133A for some integer A. Then for n = k + 1,
11n+1 + 122n–1 = 11k+1+1 + 122(k+1)–1
= 11k+2 + 122k+1
= 11 * 11k+1 + 144 * 122k–1
= 11 * 11k+1 + 11 * 122k–1 + 133 * 122k–1
= 11[11k+1 + 122k–1] + 133 * 122k–1
= 11* 133A + 133 * 122k–1
= 133[11A + 122k–1]
Thus if the hypothesis holds for n = k it also holds for n = k + 1. Therefore, the
statement given in the equation is true.
Answer
Base case : If n = 0, then n4 – 4n2 = 0, which is divisible by 3.
Inductive hypothesis : For some n 0, n4 – 4n2 is divisible by 3.
Inductive step : Assume the inductive hypothesis is true for n. We need to
show that (n + 1)4 – 4(n + 1)2 is divisible by 3. By the inductive hypothesis, we
know that n4 – 4n2 is divisible by 3.
Hence (n + 1)4 – 4(n + 1)2 is divisible by 3 if
(n + 1)4 – 4(n + 1)2 – (n4 –4n2) is divisible by 3.
More pdf : www.motivationbank.in
1–26 C (CS/IT-Sem-3) Set Theory, Functions & Natural Numbers
Answer
3 + 33 + 333 + ............ + 3333 ... = (10n + 1 – 9n – 10)/27
Let given statement be denoted by S(n)
1. Inductive base : For n = 1
(102 9(1) 10) 100 19 81
3= ,3= =3
27 27 27
3 = 3. Hence S(1) is tree.
2. Inductive hypothesis : Assume that S(k) is true i.e.,
3 + 33 + 333 + ............ + 3333 = (10k + 1 – 9k – 10)/27
3. Inductive steps : We have to show that S(k + 1) is also true i.e.,
3 + 33 + 333 + ............ (10k + 2 – 9(k + 1) – 10)/27
Now, 3 + 33 + ............ + 33 ............ 3
= 3 + 33 + 333 + ............ + 3 ............ 3
= (10k + 1 – 9k – 10)/27 + 3(10k + 1 – 1)/9
= (10k + 1 + 9k – 10 + 9.10k + 1 – 9)/27
= (10k + 1 + 9.10k + 1 – 9k – 8 – 10)/27 = (10k + 2 – 9(k + 1) – 10)/27
Thus S(k + 1) is true whenever S(k) is true. By the principle of
mathematical induction S(n) true for all positive integer n.
PART-6
Proof Methods, Proof by Counter – Example, Proof by Contradiction.
Questions-Answers
Answer
In this method, we will give an example for which given statement is false.
This example is called counter example.
For example : Prove by counter that every positive integer can be written
as sum of square of three integers.
To look for a counter example we will first write successive positive integers
as the sum of square of three integers.
1 = 12 + 02 + 02
2 = 12 + 02 + 12
3 = 12 + 12 + 12
4 = 22 + 02 + 02
5 = 02 + 12 + 22
6 = 12 + 12 + 22
But there is no way to write 7 as a sum of three squares which gives
counter example. Therefore, given statement is false.
Answer
In this method, we assume that q is false i.e., ~ q is true. Then by using rules
of inference and other theorems we will show the given statement is true
as well as false i.e., we will reach at a contradiction. Therefore, q must be
true.
For example : Prove that 3 is irrational.
Let 3 is a rational number. Then positive prime integer p and q such that
p
3 =
q
p2
3= p2 = 3q2 ...(1.40.1)
q2
More pdf : www.motivationbank.in
1–28 C (CS/IT-Sem-3) Set Theory, Functions & Natural Numbers
Answer
i. Proof by contrapositive : In this we can prove p q is true by
showing ~ q ~ p is true. It is also called proof by contraposition.
Example : Using method of contraposition if n is integer and 3n + 2 is
even then n is even.
Let p : 3n + 2 is even
q : n is even
Let ~ q is true i.e., n is odd
n = 2k + 1, where k Z
Now, 3n + 2 = 3(2k + 1) + 2
= 2(3k + 2) + 1
= 2m + 1 where m = 3k + 2 Z
(3n + 2) is odd ~ p is true
Hence ~ q ~ p is true.
By method of contraposition p q is true.
ii. Proof by exhaustive cases : Some proofs proceed by exhausting all
the possibilities. We will examine a relatively small number of examples
to prove the theorem. Such proofs are called exhaustive proofs.
Example : Prove that n2 + 1 2n where n is a positive integer and
1 n 4.
We will verify the given inequality n2 + 1 2n for n = 1, 2, 3, 4.
For n = 1; 1 + 1 = 2 which is true
For n = 2; 4 + 1 > 22 which is true
For n = 3; 9 + 1 > 23 which is true
For n = 4; 16 + 1 > 24 which is true
In each of these four cases n2 + 1 2n holds true. Therefore, by method
of exhaustive cases n2 + 1 2n, where n is the positive integer and
1 n 4 is true.
Discrete Structures & Theory of Logic 1–29 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
iii. Proof by Cases : In this method, we will cover up all the possible
cases that we come across while proving the theorem.
Example : Prove that if x and y are real numbers, then max (x, y)
min (x, y) = x + y.
Case I : If x y, then max (x, y) + min (x, y) = y + x = x + y.
Case II : if x y, then max (x, y) + min (x, y) = x + y.
1 1 1 n
Q. 11. Prove by induction : + + ... + = .
1.2 2.3 n ( n + 1) (n + 1)
Ans. Refer Q. 1.33.
2 Algebraic Structures
CONTENTS
Part-1 : Algebraic Structures : .............................. 2–2C to 2–10C
Definition, Groups,
Subgroups and Order
Questions-Answers
Answer
Algebraic structure : An algebraic structure is a non-empty set G equipped
with one or more binary operations. Suppose * is a binary operation on G.
Then (G, *) is an algebraic structure.
Properties of algebraic system : Let {S, *, +} be an algebraic structure
where * and + binary operation on S :
1. Closure property : (a * b) S a, b, S
2. Associative property : (a * b) * c = a * (b * c) a, b, c S
3. Commutative property : (a * b) = (b * a) a, b S
4. Identity element : e S such that a * e = a (right identity) a S,
e is called identity element of S with respect to operation *.
5. Inverse element : For every a S, a–1 S such that
a * a–1 = e = a– 1 * a
here a–1 is called inverse of ‘a’ under operation *.
6. Cancellation property :
a * b = a * c b = c and b * a = c * a b = c a, b, c S and a 0
7. Distributive property : a, b, c S
a * (b + c) = (a * b) + (a * c) (right distributive)
(b + c) * a = (b * a) + (c * a) (left distributive)
8. Idempotent property : An element a S is called idempotent element
with respect to operation * if a * a = a.
Answer
i. Group : Let (G, *) be an algebraic structure where * is binary operation
then (G, *) is called a group if following properties are satisfied :
Discrete Structures & Theory of Logic 2–3 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
1. a * b G a, b G [closure property]
2. a * (b * c) = (a * b) * c a, b, c G [associative property]
3. There exist an element e G such that for any a G
a * e = e * a = e [existence of identity]
4. For every a G, element a–1 G
such that a * a–1 = a–1 * a = e
For example : (Z, +), (R, +), and (Q, +) are all groups.
ii. Abelian group : A group (G, *) is called abelian group or commutative
group if binary operation * is commutative i.e., a * b = b * a a, b G
For example : (Z, +) is an abelian group.
iii. Finite group : A group {G, *} is called a finite group if number of
elements in G are finite. For example G = {0, 1, 2, 3, 4, 5} under 6 is a
finite group.
Infinite group : A group {G, *} is called infinite group if number of
element in G are infinite.
For example, (Z, +) is infinite group.
iv. Order of group : Order of group G is the number of elements in group
G. It is denoted by o (G) or |G|. A group of order 1 has only the identity
element.
v. Groupoid : Let (S, *) be an algebraic structure in which S is a non-
empty set and * is a binary operation on S. Thus, S is closed with the
operation *. Such a structure consisting of a non-empty set S and a
binary operation defined in S is called a groupoid.
Answer
If (G, *) is a group and H G. The (H, *) is said to subgroup of G if
(H, *) is also a group by itself. i.e.,
(1) a * b H a, b H (Closure property)
(2) e H such that a * e = a = e * a a H
Where e is called identity of G.
(3) a – 1 H such that a * a – 1 = e = a– 1 * a a H
For example : The set Q+ of all non-zero +ve rational number is subgroup
of Q – {0}.
Answer
i. Closure :
Let X = x1 + 2 y1
Y = x2 + 2 y2
where x1, x2, y1, y2 Q and X, Y G
2–4 C (CS/IT-Sem-3) Algebraic Structures
More pdf : www.motivationbank.in
Then X + Y = (x1 + 2 y1) + (x2 + 2 y2)
= (x1 + x2) + (y1 + y2) 2
= X1 + 2Y1 G where X1, Y1 Q
Therefore, G is closed under addition [ Sum of two rational numbers is
rational].
ii. Associativity :
Let X, Y and Z G
X = x1 + 2 y1 Y = x2 + 2 y2 Z = x3 + 2 y3
where x1, x2, x3, y1, y2, y3 Q
Consider (X + Y) + Z = (x1 + 2 y1 + x2 + 2 y2) + (x3 + 2 y 3)
= ((x1 + x2) + (y1 + y2) 2 ) + (x3 + 2 y 1)
= (x1 + x2 + x3) + (y1 + y2 + y3) 2 ...(2.4.1)
Also X + (Y + Z) = (x1 + 2 y1) + ((x2 + 2 y2) + (x3 + 2 y3))
= (x1 + 2 y1) + ((x2 + x3) + (y2 + y3) 2 )
= (x1 + x2 + x3) + (y1 + y2 + y3) 2 ...(2.4.2)
From eq. (2.4.1) and (2.4.2)
(X + Y) + Z = X + (Y + Z)
Therefore, G is associative under addition.
iii. Identity element :
Let e G be identity elements of G under addition then
(x + y 2 ) + (e1 + e2 2 ) = x + y 2
Answer
1. Let H be any sub-group of order m of a finite group G of order n. Let us
consider the left coset decomposition of G relative to H.
2. We will show that each coset aH consists of m different elements.
Let H = {h1, h2, ....., hm}
Discrete Structures & Theory of Logic 2–5 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
3. Then ah1, ah2, ...., ahm, are the members of aH, all distinct.
For, we have
ahi = ahj hi = hj
by cancellation law in G.
4. Since G is a finite group, the number of distinct left cosets will also be
finite, say k. Hence the total number of elements of all cosets is km
which is equal to the total number of elements of G.
Hence
n = mk
This show that m, the order of H, is a divisor of n, the order of the
group G.
We also find that the index k is also a divisor of the order of the group.
Que 2.6. Define identity and zero elements of a set under a binary
operation *. What do you mean by an inverse element ?
Answer
Identity element : An element e in a set S is called an identity element with
respect to the binary operation * if, for any element a in S
a*e= e*a=a
If a * e = a, then e is called the right identity element for the operation * and
if e * a = a, then e is called the left identity element for the operation *.
Zero element : Let R be an abelian group with respect to addition. The
element 0 R will be the additive identity. It is called the zero element of R.
Inverse element : Consider a set S having the identity element e with
respects to the binary operation *. If corresponding to each element
a S there exists an element b S such that
a*b= b*a=e
Then b is said to be the inverse of a and is usually denoted by a – 1. We say a
is invertible.
Que 2.7. Prove that (Z6, (+6)) is an abelian group of order 6, where
Answer
The composition table is :
+6 0 1 2 3 4 5
0 0 1 2 3 4 5
1 1 2 3 4 5 0
2 2 3 4 5 0 1
3 3 4 5 0 1 2
4 4 5 0 1 2 3
5 5 0 1 2 3 4
Since 2 +6 1 = 3
2–6 C (CS/IT-Sem-3) Algebraic Structures
More pdf : www.motivationbank.in
4 +6 5 = 3
From the table we get the following observations :
Closure : Since all the entries in the table belong to the given set Z6. Therefore,
Z6 is closed with respect to addition modulo 6.
Associativity : The composition ‘+6’ is associative. If a, b, c are any three
elements of Z6,
a +6 (b +6 c) = a +6 (b + c) [ b +6 c = b + c (mod 6)]
= least non-negative remainder when a + (b + c) is divided by 6.
= least non-negative remainder when (a + b) + c is divided by 6.
= (a + b) +6 c = (a +6 b) +6 c.
Identity : We have 0 Z6. If a is any element of Z6, then from the composition
table we see that
0 +6 a = a = a +6 0
Therefore, 0 is the identity element.
Inverse : From the table we see that the inverse of 0, 1, 2, 3, 4, 5 are 0, 5, 4,
3, 2, 1 respectively. For example 4 +6 2 = 0 = 2 +6 4 implies 4 is the inverse
of 2.
Commutative : The composition is commutative as the elements are
symmetrically arranged about the main diagonal. The number of elements
in the set Z6 is 6.
(Z6, +6) is a finite abelian group of order 6.
Answer
The composition table of G is
* 1 –1 i –i
1 1 –1 i –i
–1 –1 1 –i i
i i –i –1 1
–i –i i –1 1
1. Closure property : Since all the entries of the composition table are
the elements of the given set, the set G is closed under multiplication.
2. Associativity : The elements of G are complex numbers, and we know
that multiplication of complex numbers is associative.
3. Identity : Here, 1 is the identity element.
4. Inverse : From the composition table, we see that the inverse elements
of 1, – 1, i, – i are 1, – 1, – i, i respectively.
Discrete Structures & Theory of Logic 2–7 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
5. Commutativity : The corresponding rows and columns of the table
are identical. Therefore the binary operation is commutative. Hence,
(G, *) is an abelian group.
Que 2.9. Write the properties of group. Show that the set (1, 2, 3,
4, 5) is not group under addition and multiplication modulo 6.
Answer
Properties of group : Refer Q. 2.2(i), Page 2–2C, Unit-2.
Numerical :
Addition modulo 6 (+6) : Composition table of S = {1, 2, 3, 4, 5} under
operation +6 is given as :
+6 1 2 3 4 5
1 2 3 4 5 0
2 3 4 5 0 1
3 4 5 0 1 2
4 5 0 1 2 3
5 0 1 2 3 4
Since, 1 +6 5 = 0 but 0 S i.e., S is not closed under addition modulo 6.
So, S is not a group.
Multiplication modulo 6 (*6) :
Composition table of S = {1, 2, 3, 4, 5} under operation *6 is given as
*6 1 2 3 4 5
1 1 2 3 4 5
2 2 4 0 2 4
3 3 0 3 0 3
4 4 2 0 4 2
5 5 4 3 2 1
Since, 2 *6 3 = 0 but 0 S i.e., S is not closed under multiplication modulo 6.
So, S is not a group.
Que 2.10. Let G = {a, a2, a3, a4, a5, a6 = e}. Find the order of every
element.
Answer
o(a) : a6 = e o(a) = 6
o(a2) : (a2)3 = a6 = e o (a2) = 3
o(a3) : (a3)2 = a6 = e o(a3) = 2
2–8 C (CS/IT-Sem-3) Algebraic Structures
More pdf : www.motivationbank.in
o(a4) : (a4)3 = a12 = (a6)2 = e2 = e o(a4) = 3
o(a5) : (a5)6 = a30 = (a6)5 = e5 = e o(a5) = 6
o(a6) : (a6)1 = a6 = e o(a6) = 1
Answer
i. Let e be the identity element for * in G.
Then we have a * a – 1 = e, where a – 1 G.
Also (a – 1) – 1 * a – 1 = e
Therefore, (a – 1) – 1 * a – 1 = a * a – 1.
Thus, by right cancellation law, we have (a – 1) – 1 = a.
ii. Let a and b G and G is a group for *, then a * b G (closure)
Therefore, (a * b) – 1 * (a * b) = e. ....(2.11.1)
Let a – 1 and b – 1 be the inverses of a and b respectively, then a – 1,
b – 1 G.
Therefore, (b – 1 * a – 1) * (a * b) = b – 1 * (a – 1 * a) * b (associativity)
= b–1 * e * b = b–1 * b = e ...(2.11.2)
From (2.11.1) and (2.11.2) we have,
(a * b) – 1 * (a * b) = (b – 1 * a – 1)* (a * b)
(a * b) – 1 = b – 1 * a –1 (by right cancellation law)
Answer
Let H1 and H2 be any two subgroups of G. Since at least the identity element
e is common to both H1 and H2.
H1 H2
In order to prove that H1 H2 is a subgroup, it is sufficient to prove that
a H1 H2, b H1 H2 ab–1 H1 H2
Now a H1 H2 a H1 and a H2
b H1 H2 b H1 and b H2
But H1, H2 are subgroups. Therefore,
a H1, b H1 ab–1 H1
a H2 , bH2 ab–1 H2
Finally, ab–1 H1, ab–1 H2 ab–1 H1 H2
Thus, we have shown that
a H1 H2, b H1 H2 ab–1 H1 H2.
Hence, H1 H2 is a subgroup of G.
Discrete Structures & Theory of Logic 2–9 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
Que 2.13. Let G be the set of all non-zero real number and let
a * b = ab/2. Show that (G *) be an abelian group.
AKTU 2015-16, Marks 10
Answer
i. Closure property : Let a, b G.
ab
a*b= G as ab 0
2
* is closure in G.
ii. Associativity : Let a, b, c G
bc a(bc) abc
Consider a * (b * c) = a *
2 4 4
ab (ab) c abc
(a * b) * c = * c =
2 4 4
* is associative in G.
iii. Existence of the identity : Let a G and e such that
ae
a*e= =a
2
ae = 2a
e=2
2 is the identity element in G.
iv. Existence of the inverse : Let a G and b G such that a * b = e = 2
ab
=2
2
ab = 4
4
b=
a
4
The inverse of a is , a G.
a
v. Commutative : Let a, b G
ab
a*b=
2
ba ab
and b*a=
2 2
* is commutative.
Thus, (G, *) is an abelian group.
PART-2
Cyclic Group, Cosets, Lagrange’s Theorem.
Questions-Answers
Answer
Cyclic group : A group G is called a cyclic group if at least one element a
in G such that every element x G is of the form an, where n is some integer.
The element a G is called the generator of G.
For example :
Show that the multiplicative group G = {1, – 1, i, – i} is cyclic. Also find its
generators.
We have, i1 = i, i2 = – 1, i3 = – i, i4 = 1.
and (– i)1 = – i, (– i)2 = – 1, (– i)3 = i, (– i)4 = 1
Thus, every element in G be expressed as in or (– i)n
G is cyclic group and its generators are i and – i.
Que 2.16. Prove that every group of prime order is cyclic.
Answer
1. Let G be a group whose order is a prime p.
2. Since P > 1, there is an element a G such that a e.
Discrete Structures & Theory of Logic 2–11 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
3. The group <a> generated by ‘a’ is a subgroup of G.
4. By Lagrange’s theorem, the order of ‘a’ divides |G|.
5. But the only divisors of |G|= p are 1 and p. Since a e we have |<a>|> 1,
so |<a>| = p.
6. Hence, <a> = G and G is cyclic.
Answer
1. Suppose G is a finite group whose order is a prime number p, then to
prove that G is a cyclic group.
2. An integer p is said to be a prime number if p 0, p 1, and if the only
divisors of p are ± 1, ± p.
3. Some G is a group of prime order, therefore G must contain at least 2
element. Note that 2 is the least positive prime integer.
4. Therefore, there must exist an element a G such that a the identity
element e.
5. Since a is not the identity element, therefore o(a) is definitely 2. Let
o(a) = m. If H is the cyclic subgroup of G generated by a then
o (H = o (a) = m).
6. By Lagrange’s theorem m must be a divisor of p. But p is prime and
m 2. Hence, m = p.
7. H = G. Since H is cyclic therefore G is cyclic and a is a generator of G.
Que 2.18. Show that group (G, +5) is a cyclic group where G = {0, 1,
2, 3, 4}. What are its generators ?
Answer
Composition table of G under operation +5 is shown in Table 2.18.1.
Table 2.18.1.
+5 0 1 2 3 4
0 0 1 2 3 4
1 1 2 3 4 0
2 2 3 4 0 1
3 3 4 0 1 2
4 4 0 1 2 3
0 is the identity element of G under +5.
11 = 1 1 mod 5
12 = 1 + 1 2 mod 5
13 = 1 + 1 + 1 3 mod 5
14 = 1 + 1 + 1 + 1 4 mod 5
15 = 1 = 1 + 1 + 1 + 1 0 mod 5
2–12 C (CS/IT-Sem-3) Algebraic Structures
More pdf : www.motivationbank.in
where 1n means 1 is added n times
Therefore, 1 is generator of G.
Similarly, 2, 3, 4 are also generators of G.
Therefore, G is a cyclic group with generator 1, 2, 3, 4.
Que 2.19. Show that G = [(1, 2, 4, 5, 7, 8), X9] is cyclic. How many
generators are there ? What are they ? AKTU 2015-16, Marks 7.5
Answer
Composition table for X9 is
X9 1 2 4 5 7 8
1 2 3 4 5 7 8
2 2 4 8 1 5 7
4 4 8 7 2 1 5
5 5 1 2 7 8 4
7 7 5 1 8 4 2
8 8 7 5 4 2 1
1 is identity element of group G
21 = 2 2 mod 9
22 = 4 4 mod 9
23 = 8 8 mod 9
24 = 16 7 mod 9
25 = 32 5 mod 9
26 = 64 1 mod 9
Therefore, 2 is generator of G. Hence G is cyclic.
Similarly, 5 is also generator of G.
Hence there are two generators 2 and 5.
Answer
Let H be a subgro up o f gro up G and le t a G the n the se t
Ha = {ha : h H} is called right coset generated by H and a.
Also the set aH = {ah : h H} is called left coset generated by a and H.
Properties of cosets : Let H be a subgroup of G and let a and b belong to
G. Then
1. a a H
Proof : a = a e a H
Since e is identity element of G.
2. aH = H iff a H.
Proof : Let aH = H.
Then a = ae aH = H (e is identity in G and so is in H)
aH
3. aH = bH or aH bH =
Discrete Structures & Theory of Logic 2–13 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
Proof : Let aH = bH or aH bH =
and to prove that aH = bH.
Let aH bH
Then there exists h1, h2 H such that
x = ah1 and x = bh2
a = xh1–1 = bh2 h1–1
Since H is a subgroup, we have h2 h1–1 H
let h2 h1–1 = h H
Now, aH = bh2h1–1 H = (bh) H = b (hH) = bh ( hH = H by property 2)
aH = bH if a H bH
Thus, either a H bH = or aH = bH.
4. aH = bH iff a–1 b H.
Proof : Let aH = bH.
a–1 aH = a–1 bH
eH = a–1 bH (e is identity in G)
H = (a–1 b) H
Therefore by property (2); a–1 b H.
Conversely, now if a–1 b H.
Then consider bH = e (bH) = (a a–1) (bH)
= a (1–1 b) H
= aH
Thus aH = bH iff a–1 b H.
5. aH is a subgroup of G iff a H.
Proof : Let aH is a subgroup of G then it contains the identity e of G.
Thus, aH eH
then by property (3) ; aH = eH = H
aH = a H
Conversely, if a H then by property (2); aH = H.
Que 2.21. State and prove Lagrange’s theorem for group. Is the
Answer
Lagrange’s theorem :
Statement : The order of each subgroup of a finite group is a divisor of the
order of the group.
Proof : Let G be a group of finite order n. Let H be a subgroup of G and let
O(H) = m. Suppose h1, h2.... ..., hm are the m members of H.
Let a G, then Ha is the right coset of H in G and we have
Ha = {h1 a, h2 a,....hm a}
Ha has m distinct members, since = hi a = hj a hi = hj
Therefore, each right coset of H in G has m distinct members. Any two
distinct right cosets of H in G are disjoint i.e., they have no element in
2–14 C (CS/IT-Sem-3) Algebraic Structures
More pdf : www.motivationbank.in
common. Since G is a finite group, the number of distinct right cosets of H in
G will be finite, say, equal to k. The union of these k distinct right cosets of H
in G is equal to G.
Thus, if Ha1, Ha2,...., Hak are the k distinct right cosets of H in G. Then
G = Ha1 Ha2 Ha3 .... Hak
the numbe r of elements in G = the numbe r of e lements in
Ha1 + ...... + the number of elements in Ha2 +......+ the number of elements in
Hak
O(G) = km
n = km
n
k=
m
m is a divisor of n.
O(H) is a divisor of O(G).
Proof of converse : If G be a finite group of order n and n G, then
an = e
Let o (a) = m which implies am = e.
Now, the subset H of G consisting of all the integral power of a is a subgroup
of G and the order of H is m.
Then, by the Lagrange’s theorem, m is divisor of n.
Let n = mk, then
an = amk = (am)k = ek = e
Yes, the converse is true.
Answer
Lagrange’s theorem :
If G is a finite group and H is a subgroup of G then o(H) divides o(G).
Moreover, the number of distinct left (right) cosets of H in G is o(G)/o(H).
Proof : Let H be subgroup of order m of a finite group G of order n.
Let H {h1, h2, ..., hm}
Let a G. Then aH is a left coset of H in G and aH = {ah1, ah2, ..., ahm} has m
distinct elements as ahi = ahj hi = hj by cancellation law in G.
Thus, every left coset of H in G has m distinct elements.
Since G is a finite group, the number of distinct left cosets will also be finite.
Let it be k. Then the union of these k-left cosets of H in G is equal to G.
i.e., if a1H, a2H, ..., akH are right cosets of H in G then
G = a1H a2H ... akH.
o(G) = o(a1H) + o(a2H) + ... + o(akH)
(Since two distinct left cosets are mutually disjoint.)
n = m + m + ... + m (k times)
n
n = mk k =
m
o(G )
k= .
o( H )
Discrete Structures & Theory of Logic 2–15 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
Thus order of each subgroup of a finite group G is a divisor of the order of the
group.
Cor 1 : If H has m different cosets in G then by Lagrange’s theorem :
o(G) = m o(H)
o(G )
m=
o( H )
o(G )
[G : H] =
o( H )
Cor 2 : If |G| = n and a G then an = e
Let |a| = m am = e
Now, the subset H of G consisting of all integral powers of a is a subgroup of
G and the order of H is m.
Then by Lagrange’s theorem, m is divisor of n.
Let n = mk, then
an = amk = (am)k = ek = e
Que 2.23.
a. Prove that every cyclic group is an abelian group.
b. Obtain all distinct left cosets of {(0), (3)} in the group
(Z6, +6) and find their union.
c. Find the left cosets of {[0], [3]} in the group (Z6, +6).
AKTU 2016-17, Marks 10
Answer
a. Let G be a cyclic group and let a be a generator of G so that
G = <a> = {an : n Z}
If g1 and g2 are any two elements of G, there exist integers r and s such
that g1 = ar and g2 = as. Then
g1 g2 = ar as = ar+s = as+r = as . ar = g2g1
So, G is abelian.
b. [0] + H = [3] + H, [1] + [4] + H and [2] + H = [5] + H are the three
distinct left cosets of H in (Z6 , + 6 ).
We would have the following left cosets :
g1H = {g1 h, h H}
g2H = {g2 h, h H}
gnH = {gn h, h H}
The union of all these sets will include all the g s, since for each set
gk = {gk h, h H}
we have ge gk = {gk h, h H}
where e is the identity.
Then if we make the union of all these sets we will have at least all the
elements of g. The other elements are merely gh for some h. But since ghG
they would be repeated elements in the union. So, the union of all left cosets
of H in G is G, i.e.,
Z6 = {[0], [1], [2], [3], [4], [5]}
2–16 C (CS/IT-Sem-3) Algebraic Structures
More pdf : www.motivationbank.in
c. Let Z6 = {[0], [1], [2], [3], [4], [5]} be a group.
H = {[0], [3]} be a subgroup of (Z6, +6).
The left cosets of H are,
[0] + H = {[0], [3]}
[1] + H = {[1], [4]}
[2] + H = {[2], [5]}
[3] + H = {[3], [0]}
[4] + H = {[4], [1]}
[5] + H = {[5], [2]}
Answer
Lagrange’s theorem : Refer Q. 2.22, Page 2–14C, Unit-2.
Numerical :
H = {x2 : x G} = {0, 1, 4, 9, 16, 25 ....}
Left coset of H will be 1 + H = {1, 2, 5, 10, 17, 26, ....}
Answer
Coset : Refer Q. 2.20, Page 2–12C, Unit-2.
Numerical :
i. We have Z = {– 7, – 6, – 5, – 4, – 3, – 2, – 1, 0, 1, 2, 3, 4, 5, 6, ....}
and H = {...., – 10, – 5, 0, 5, 10, ....}
Let 0 Z and the right cosets are given as
H = H + 0 = {...., – 10, – 5, 0, 5, 10, ....}
H + 1 = {...., – 9, – 4, 1, 6, 11, ....}
H + 2 = {...., – 8, – 3, 2, 7, 12, ....}
H + 3 = {...., – 7, – 2, 3, 8, 13, ....}
H + 4 = {....., – 6, – 1, 4, 9, 14, ....}
H + 5 = {...., – 10, – 5, 0, 5, 10, ....] = H
Now, its repetition starts. Now, we see that the right cosets,
H, H + 1, H + 2, H + 3, H + 4 are all distinct and more over they are
disjoint. Similarly the left cosets will be same as right cosets.
ii. Index of H in G is the number of distinct right/left cosets.
Therefore, index is 5.
Discrete Structures & Theory of Logic 2–17 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
PART-3
Normal Subgroups, Permutation and Symmetric of Groups.
Questions-Answers
Answer
a. Normal subgroup : A subgroup H of G is said to be normal subgroup
of G if Ha = aH a G i.e., the right coset and left coset of H is G
generated by a are the same.
i. Clearly, every subgroup H of an abelian group G is a normal
subgroup of G. For a G and h H, ah = ha.
ii. Since a cyclic group is abelian, every subgroup of a cyclic group is
normal.
b. Permutation group : A set G of all permutation on a non-empty
set A under the binary operation * is called permutation group.
If A = {1, 2, 3, ...., n}, the given permutation group formed by A is also
called symmetric group of degree n denoted by Sn. Number of elements
of Sn will be n!.
Cyclic permutation : Let A = {x1, x2, ..., xn}. Then let t1, t2,..., tk be
elements of set A and permutation P : A defined by
P(t1) = t2
P(t2) = t3
...........
...........
P(tk–1) = tk
P(tk) = t1
is called a cyclic permutation of length k.
a b c d e
For example : Consider A = {a, b, c, d, e}. Then let P = .
c b d a e
Then P has a cycle of length 3 given by (a, c, d).
Que 2.27. Define the subgroup of a group. Let (G, ) be a group.
Let H = {a | a G and a b = b a for all b G}. Show that H is a
normal subgroup.
2–18 C (CS/IT-Sem-3) Algebraic Structures
More pdf : www.motivationbank.in
Answer
Subgroup : If (G, *) is a group and H G. Then (H, *) is said to subgroup of
G if (H, *) is also a group by itself.
i.e.,
1. a * b H a, b H (Closure property)
2. e H such that a * e = a = e * a a H
where e is called identity of G.
3. a–1 H such that a * a–1 = e = a–1 * a a H
Numerical : Let (G, x) be a group. A non-empty subset H of a group G is said
to be a subgroup of G if (H, *) itself is a group.
Given that, H = {a|a G and a b = b a; b G}
Let a, b H a x = x a and b x = x b, x G
(b x) – 1 = (x b) – 1
x – 1 b – 1 = b – 1 x1
b – 1H.
Now, (a b – 1) x = a (b – 1 x) [ is associative]
= a (x b – 1) [ use b – 1 H]
= (a x) b – 1 [ a H]
= (x a) b – 1
= x (a b – 1)
ab H – 1
Answer
Questions-Answers
Answer
Homomorphism : Let (G1, •) and (G2, *) be two groups then a mapping
f : G1 G2 is called a homomorphism if f(a • b) = f(a) * f(b) for all a, b G1.
Thus f is homomorphism from G1 to G2 then f preserves the composition in
G1 and G2 i.e., image of composition is equal to composition of images.
The group G2 is said to be homomorphic image of group G1 if there exist a
homomorphism of G1 onto G2.
Isomorphism : Let (G1, •) and (G2, *) be two groups then a mapping
f : G1 G2 is an isomorphism if
i. f is homomorphism.
ii. f is one to one i.e., f(x) = f(y) x = y x, y G1.
iii. f is onto.
Que 2.30. Give the definitions of rings, integral domains and fields.
Answer
Ring : A ring is an algebraic system (R, +, •) where R is a non-empty set and
+ and • are two binary operations (which can be different from addition and
multiplication) and if the following conditions are satisfied :
1. (R, +) is an abelian group.
2. (R, •) is semigroup i.e., (a • b) • c = a • (b • c) a, b, c R.
3. The operation • is distributive over +.
i.e., for any a, b, c R
a • (b + c) = (a • b) + (a • c) or (b + c) • a = (b • a) + (c • a)
Integral domain : A ring is called an integral domain if :
i. It is commutative
ii. It has unit element
iii. It is without zero divisors
2–20 C (CS/IT-Sem-3) Algebraic Structures
More pdf : www.motivationbank.in
Field : A ring R with at least two elements is called a field if it has following
properties :
i. R is commutative
ii. R has unity
iii. R is such that each non-zero element possesses multiplicative inverse.
For example, the rings of real numbers and complex numbers are also fields.
Answer
Let a, b R (a + b)2 = (a + b)
(a + b) (a + b) = (a + b)
(a + b)a + (a + b)b = (a + b)
(a2 + ba) + (ab + b2) = (a + b)
(a + ba) + (ab + b) = (a + b) ( a2 = a and b2 = b)
(a + b) + (ba + ab) = (a + b) + 0
ba + ab = 0
a + b = 0 a + b = a + a [being every element of its own additive inverse]
b=a
ab = ba
R is commutative ring.
Que 2.32. Write out the operation table for [Z2, +2, * 2]. Is Z2 a
ring ? Is an integral domain ? Is a field ? Explain.
Answer
The operation tables are as follows :
we have Z2 = {0, 1}
+2 0 1 *2 0 1
0 0 1 0 0 0
1 1 0 1 0 1
Since (Z2, +2, *2) satisfies the following properties :
i. Closure axiom : All the entries in both the tables belong to Z2. Hence,
closure is satisfied.
ii. Commutative : In both the tables all the entries about the main diagonal
are same therefore commutativity is satisfied.
iii. Associative law : The associative law for addition and multiplication
are also satisfied.
Discrete Structures & Theory of Logic 2–21 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
iv. Here 0 is the additive identity and 1 is the multiplicative identity. Identity
property is satisfied.
v. Inverse exists in both the tables. The additive inverse of 0, 1 are 1, 0
respectively and the multiplicative inverse of non-zero element of Z2
is 1.
vi. Multiplication is distributive over addition.
Hence (Z2, +2, *2) is a ring as well as field. Since, we know that every field is
an integral domain therefore it is also an integral domain.
Answer
ax = b (123) (45) x = (1) (2) (3) (4, 5)
1 2 3 4 5 1 2 3 4 5 1 2 3 4 5
2 3 1 4 5 1 2 3 5 4 x 1 2 3 5 4
1 2 3 4 5 1 2 3 4 5
x=
2 3 1 5 4 1 2 3 5 4
1
1 2 3 4 5 1 2 3 4 5
x=
2 3 1 5 4 1 2 3 5 4
2 3 1 5 4 1 2 3 4 5
=
1 2 3 4 5 1 2 3 5 4
1 2 3 4 5 1 2 3 4 5
=
3 1 2 5 4 1 2 3 5 4
1 2 3 4 5
x=
3 1 2 4 5
4 0 1 2 3 4 0 1 2 3
0 0 1 2 3 0 0 0 0 0
1 1 2 3 0 1 0 1 2 3
2 2 3 0 1 2 0 2 0 2
3 3 0 1 2 3 0 3 2 1
We find from these tables :
i. All the entries in both the tables belong to Z4. Hence, Z4 is closed with
respect to both operations.
2–22 C (CS/IT-Sem-3) Algebraic Structures
More pdf : www.motivationbank.in
ii. Commutative law : The entries of 1st, 2nd, 3rd, 4th rows are identical
with the corresponding elements of the 1 st , 2nd, 3rd, 4th columns
respectively in both the tables. Hence, Z4 is commutative with respect to
both operations.
iii. Associative law : The associative law for addition and multiplication
a +4 (b +4 c) = (a +4 b) +4 c for all a, b, c Z4
a ×4 (b ×4 c) = (a ×4 b) ×4 c, for all a, b, c Z4
can easily be verified.
iv. Existence of identity : 0 is the additive identity and 1 is multiplicative
identity for Z4.
v. Existence of inverse : The additive inverses of 0, 1, 2, 3 are 0, 3, 2, 1
respectively.
Multiplicative inverse of non-zero element 1, 2, 3 are 1, 2, 3 respectively.
vi. Distributive law : Multiplication is distributive over addition i.e.,
a ×4(b +4c) = a ×4b + a ×4c
(b +4c) ×4a = b ×4a + c ×4a
For, a ×4(b +4c) = a ×4(b + c) for b +4 c = b + c (mod 4)
= least positive remainder when a × (b + c) is
divided by 4
= least positive remainder when ab + ac is divided
by 4
= ab +4ac
= a ×4b +4a ×4c
For a ×4b = a × b (mod 4)
Since (Z4, +4) is an abelian group, (Z4, ×4) is a semigroup and the operation is
distributive over addition. The (Z4, +4, ×4) is a ring. Now (Z4, ×4) is commutative
with respect to ×4. Therefore, it is a commutative ring.
Answer
Ring : Refer Q. 2.30, Page 2–19C, Unit-2.
Example of commutative ring : Refer Q. 2.31, Page 2–20C, Unit-2.
Example of non-commutative ring : Consider the set R of 2 × 2 matrix
with real element. For A, B, C R
A * (B + C) = (A * B) + (A * C)
also, (A + B) * C = (A * C) + (B * C)
* is distributive over +.
(R, +, *) is a ring.
We know that AB BA, Hence (R, +, *) is non-commutative ring.
Discrete Structures & Theory of Logic 2–23 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
Q. 13.
a. Prove that every cyclic group is an abelian group.
b. Obtain all distinct left cosets of {(0), (3)} in the group
(Z6, +6) and find their union.
c. Find the left cosets of {[0], [3]} in the group (Z6, +6).
Ans. Refer Q. 2.23.
Discrete Structures & Theory of Logic 3–1 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
3 Lattices and
Boolean Algebra
CONTENTS
Part-1 : Lattices : Definition, ................................. 3–2C to 3–10C
Properties of Lattices–Bounded,
Complemented, Modular
and Complete Lattice
Questions-Answers
Answer
A lattice is a poset (L, ) in which every subset {a, b} consisting of 2 elements
has least upper bound (lub) and greatest lower bound (glb). Least upper
bound of {a, b} is denoted by a b and is known as join of a and b. Greatest
lower bound of {a, b} is denoted by a b and is known as meet of a and b.
Lattice is generally denoted by (L, , ).
Properties :
Let L be a lattice and a, b L then
1. Idempotent property :
i. aa=a ii. a a = a
2. Commutative property :
i. ab=ba ii. a b = b a
3. Associative property :
i. a (b c) = (a b) c ii. a (b c) = (a b) c
4. Absorption property :
i. a (a b) = a ii. a (a b) = a
5. i. a b = b iff a b ii. a b = a iff a b
iii. a b = a iff a b = b
6. Distributive Inequality :
i. a (b c) (a b) (a c) ii. a (b c) (a b) (a c)
7. Isotonicity :
Let a, b, c, L and a b, then
i. acbc ii. a c b c
8. Stability :
Let a, b, c, L, then
i. a b, a c a (b c), a (b c)
ii. a b, a c a (b c), a (b c)
Que 3.2. Explain types of lattice.
Discrete Structures & Theory of Logic 3–3 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
Answer
Types of lattice :
1. Bounded lattice : A lattice L is said to be bounded if it has a greatest
element 1 and a least element 0. In such lattice we have
a 1 = 1, a 1 = a
a 0 = a, a 0 = 0
a L and 0 a I
2. Complemented lattice : Let L be a bounded lattice with greatest
element 1 and least element 0. Let a L then an element a L is
complement of a if,
a a = 1 and a a = 0
A lattice L is called complemented if is bounded and if every element in
L has a complement.
3. Distributive lattice : A lattice L is said to be distributive if for any
element a, b and c of L following properties are satisfied :
i. a (b c) = (a b) (a c)
ii. a (b c) = (a b) (a c)
otherwise L is non-distributive lattice.
4. Complete lattice : A lattice L is called complete if each of its non-
empty subsets has a least upper bound and greatest lower bound.
For example :
i. (Z, ) is not a complete lattice.
ii. Let S be the class of all subsets of some universal set A and a
relation is defined as X Y X is a subset of Y such that
X Y = X Y and X Y. Every subset of S has glb and lub. So, S
is complete.
5. Modular lattice : A lattice (L, ) is called modular lattice if,
a (b c) = (a b) c whenever a c for all a, b, c L.
a c
f d
e
Fig. 3.3.1.
AKTU 2014-15, Marks 10
3–4 C (CS/IT-Sem-3) Lattices and Boolean Algebra
More pdf : www.motivationbank.in
Answer
i. Complements of e are c and d which are as follows :
c e = b , c e = f
de=b , de=f
ii. A lattice is bounded if it has greatest and least elements. Here b is
greatest and f is least element.
Que 3.4. Define a lattice. For any a, b, c, d in a lattice (A, ) if a b
and c d then show that a c b d and a c b d.
AKTU 2018-19, Marks 07
Answer
Lattice : Refer Q. 3.1, Page 3–2C, Unit-3.
Numerical :
As a b and c d, a b b d and c d b d.
By transtivity of , a b d and c b d.
So b d is an upper bound of a and c.
So a c bd.
As a c a and a c c, a c a b and a c c d.
Hence a c is a lower bound of b and d. So a c b d.
So a c b d.
Answer
Let a1 and a2 be two complements of an element a L.
Then by definition of complement
a a1 I
...(3.5.1)
a a1 0
a a2 I
...(3.5.2)
a a2 0
Discrete Structures & Theory of Logic 3–5 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
Consider a1 = a1 0
= a1 (a a2) [from (3.5.2)]
= (a1 a) (a1 a2) [Distributive property]
= (a a1) (a1 a2) [Commutative property]
= I (a1 a2) [from (3.5.1)]
= a1 a2 ...(3.5.3)
Now Consider a2 = a2 0
= a2 (a a1) [from (3.5.2)]
= (a2 a) (a2 a1) [Distributive property]
= (a a2) (a1 a2) [Commutative property]
= I (a1 a2) [from (3.5.1)]
= a1 a2 ...(3.5.4)
Hence, from (3.5.3) and (3.5.4),
a1 = a2
So, for bounded distributive lattice complement is unique.
Hasse diagram of [P(a, b, c), ] or [P(a, b, c), ] is shown in Fig. 3.5.1.
{a, b, c}
Fig. 3.5.1.
Greatest element is {a, b, c} and maximal element is {a, b, c}..
The least element is and minimal element is .
1 2
3 4
Fig. 3.6.1.
3–6 C (CS/IT-Sem-3) Lattices and Boolean Algebra
More pdf : www.motivationbank.in
i. Verify that (A, R) is a poset and find its Hasse diagram.
ii. Is this a lattice ?
iii. How many more edges are needed in the Fig. 3.6.1 to extend
(A, R) to a total order ?
iv. What are the maximal and minimal elements ?
AKTU 2014-15, Marks 10
Answer
i. The relation R corresponding to the given directed graph is,
R = {(1, 1), (2, 2), (3, 3), (4, 4), (3, 1), (3, 4), (1, 4), (3, 2)}
R is a partial order relation if it is reflexive, antisymmetric and transitive.
Reflexive : Since aRa, a A . Hence, it is reflexive.
Antisymmetric : Since aRb and bRa then we get a = b otherwise aRb
or bRa.
Hence, it is antisymmetric.
Transitive: For every aRb and bRc we get aRc. Hence, it is transitive.
Therefore, we can say that (A, R) is poset. Its Hasse diagram is :
1
2
4
3
Fig. 3.6.2.
ii. Since there is no lub of 1 and 2 and same for 2 and 4. The given poset is
not a lattice.
1 2 3 4
1 1 1 1
2 2 2
3 1 2 3 1
4 1 1 4
iii. Only one edge (4, 2) is included to make it total order.
iv. Maximals are {1, 2} and minimals are {3, 4}.
Answer
a. Given : a b c
Discrete Structures & Theory of Logic 3–7 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
Now a b = least upper bound of a, b
= least {all upper bounds of a, b}
= least {b, c, ...} [using a b c]
=b ...(3.7.1)
and b c = greatest lower bound of b, c
= maximum {all lower bounds of b, c}
= maximum {b, a, ...} [using a b c]
=b ...(3.7.2)
Eq. (3.7.1) and (3.7.2) gives, a b = b c
b. (a b) (b c) (a b) (a c) = b
Consider, (a b) (b c)
= b b [using a b c and definition of and ]
=b ...(3.7.3)
and (a b) (a c) = b c
=b ...(3.7.4)
From eq. (3.7.3) and (3.7.4), (a b) (b c) = (a b) (a c) = b.
Que 3.8.
a. Prove that every finite subset of a lattice has an LUB and a
GLB.
b. Give an example of a lattice which is a modular but not a
distributive. AKTU 2016-17, Marks 10
Answer
a.
1. The theorem is true if the subset has 1 element, the element being
its own glb and lub.
2. It is also true if the subset has 2 elements.
3. Suppose the theorem holds for all subsets containing 1, 2, ..., k
elements, so that a subset a1, a2, ..., ak of L has a glb and a lub.
4. If L contains more than k elements, consider the subset
{a1, a2, ..., ak + 1} of L.
5. Let w = lub (a1, a2, ..., ak).
6. Let t = lub (w, ak + 1).
7. If s is any upper bound of a1, a2, ..., ak + 1, then s is each of a1, a2, ...,
ak and therefore s w.
8. Also, s ak + 1 and therefore s is an upper bound of w and ak + 1.
9. Hence s t.
10. That is, since t each a1, t is the lub of a1, a2, ..., ak + 1.
11. The theorem follows for the lub by finite induction.
3–8 C (CS/IT-Sem-3) Lattices and Boolean Algebra
More pdf : www.motivationbank.in
12. If L is finite and contains m elements, the induction process stops
when k + 1 = m.
b.
1. The diamond is modular, but not distributive.
2. Obviously the pentagon cannot be embedded in it.
3. The diamond is not distributive :
y (x z) = y (y x) (y z) = 1
4. The distributive lattices are closed under sublattices and every
sublattice of a distributive lattice is itself a distributive lattice.
5. If the diamond can be embedded in a lattice, then that lattice has a
non-distributive sublattice, hence it is not distributive.
Answer
Show that the inclusion relation () is a partial ordering on the power set of
a set S.
Reflexivity : A A whenever A is a subset of S.
Antisymmetry : If A and B are positive integers with A B and B A, then
A = B.
Transitivity : If A B and B C, then A C.
Hasse diagram :
{a, b, c, d}
{a, b, d} {a, c, d}
{a, b, c} {b, c, d}
Fig. 3.9.1.
Discrete Structures & Theory of Logic 3–9 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
(P(S), ) is not a lattice because ({a, b},{b, d}) has no lub and glb.
Que 3.10. Explain modular lattice, distributive lattice and bounded
Answer
Modular distributive and bounded lattice : Refer Q. 3.2, Page 3–2C,
Unit-3.
Example :
Let consider a Hasse diagram :
1
a b c
0
Fig. 3.10.1.
Modular lattice :
0 a i.e., taking b = 0
b (a c) = 0 0 = 0, a (b c) = a c = 0
Distributive lattice :
For a set S, the lattice P(S) is distributive, since union and intersection each
satisfy the distributive property.
Bounded lattice : Since, the given lattice has 1 as greatest and 0 as least
element so it is bounded lattice.
Answer
Hasse diagram of (A, ) where A = {3, 4, 12, 24, 48, 72}
1
a b c
0
Fig. 3.11.1.
Que 3.12. For any positive integer D36, then find whether (D36, ‘|’)
12 12
6
4 9
2 3
1
Since, 9 4 = {}
So, D36 is not a lattice.
PART-2
Boolean Algebra : Introduction, Axioms and Theorems of
Boolean Algebra.
Questions-Answers
Answer
A Boolean algebra is generally denoted by (B, +, ., 0, 1) where (B, +,.) is a
lattice with binary operations ‘+’ and ‘.’ called the join and meet respectively
and () is unary operation in B. The elements 0 and 1 are zero (least) and unit
(greatest) elements of lattice (B, +, .). B is called a Boolean algebra if the
following axioms are satisfied for all a, b, c in B.
Axioms of Boolean algebra :
If a, b, c B, then
1. Commutative laws :
a. a+b=b+a b. a.b = b.a
2. Distributive laws :
a. a + (b.c) = (a + b).(a + c) b. a.(b + c) = (a.b) = (a.c)
3. Identity laws :
a. a+0=a b. a.1 = a
Discrete Structures & Theory of Logic 3–11 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
4. Complement laws :
a. a + a = 1 b. a.a = 0
Basic theorems :
Let a, b, c B, then
1. Idempotent laws :
a. a+a=a b. a.a = a
2. Boundedness (Dominance) laws :
a. a+1=1 b. a.0 = 0
3. Absorption laws :
a. a + (a.b) = a b. a.(a + b) = a
4. Associative laws :
a. (a + b) + c = a + (b + c) b. (a.b).c = a.(b.c)
5. Uniqueness of complement :
a + x = 1 and a.x = 0, then x = a
6. Involution law : (a) = a
7. a. 0 = 1 b. 1 = 0
8. De-Morgan’s laws :
a. (a + b) = a.b b. (a.b) = a + b
Answer
a. Absorption law :
i. To prove : a.(a + b) = a
Let a.(a + b) = (a + 0).(a + b) by Identity law
= a + 0.b by Distributive law
= a + b.0 by Commutative law
= a+0 by Dominance law
= a by Identity law
ii. To prove : a + a.b = a
Let a + a.b = a.1 + a.b by Identity law
= a.(1 + b) by Distributive law
= a.(b + 1) by Commutative law
= a.1 by Dominance law
= a by Identity law
3–12 C (CS/IT-Sem-3) Lattices and Boolean Algebra
More pdf : www.motivationbank.in
b. Idempotent law :
To prove : a + a = a and a.a = a
Let a= a+0 by Identity law
= a + a. a by Complement law
= (a + a).(a + a) by Distributive law
= (a + a).1 by Complement law
= a+a by Identity law
Now let a = a.1 by Identity law
= a.(a + a) by Complement law
= a.a + a.a by Distributive law
= a.a + 0 by Complement law
= a.a by Identity law
c. De Morgan’s law :
i. To prove : (a + b) = a.b
To prove the theorem we will show that
(a + b) + a.b = 1
Consider (a + b) + a.b = {(a + b) + a}.{(a + b) + b}by Distributive law
= {(b + a) + a}.{(a + b) + b}
by Commutative law
= {b + (a + a)}.{a + (b + b)}
by Associative law
= (b + 1).(a + 1) by Complement law
= 1.1 by Dominance law
=1 ...(3.14.1)
Also consider (a + b).ab = ab.(a + b) by Commutative law
= ab.a + ab.b by Distributive law
= a.(ab) + a.(b b) by Commutative law
= (a. a).b + a(b. b) by Associative law
= 0. b + a.0 by Complement law
= b.0 + a.0 by Commutative law
= 0+0 by Dominance law
=0 ...(3.14.2)
From eq. (3.14.1) and (3.14.2), we get,
ab is complement of (a + b) i.e.(a + b) = a b.
ii. To prove : (a. b) = a + b
Follows from principle of duality, that is, interchange operations + and •
and interchange the elements 0 and 1.
d. To prove : 0 = 1 and 1 = 0.
0 = (a a) by Complement law
= a + (a) by De Morgan’s law
= a + a by Involution law
= a + a by Commutative law
=1 by Complement law
Now (0) = 1
0 = 1
1 = 0.
Discrete Structures & Theory of Logic 3–13 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
Que 3.15. Define Boolean algebra. Show that in a Boolean algebra
meet and join operations are distributive to each other.
Answer
Boolean algebra : Refer Q. 3.10, Page 3–10C, Unit-3.
Meet and join operations are distributive :
1. Let L be a poset under an ordering . Let a, b L.
2. We define :
a b (read “a join b”) as the least upper bound of a and b, and
a b(read “a meet b”) as greatest lower bound of a and b.
3. Since the join and meet operation produce a unique result in all cases
where they exist, we can consider them as binary operations on a set if
they always exist.
4. A lattice is a poset L (under ) in which every pair of elements has a lub
and a glb.
5. Since a lattice L is an algebraic system with binary operations and , it
is denoted by [L, , ].
6. Let us consider,
a. [P(A), , ] is a lattice for any set A and
b. The join operation is the set operation of union and the meet
operation is the operation of intersection; that is, = and = .
7. It can be shown that the commutative laws, associative laws, idempotent
laws, and absorption laws are all true for any lattice.
8. An example of this is clearly [P(A); , ], since these laws hold in the
algebra of sets.
9. This lattice is also distributive such that join is distributive over meet
and meet is distributive over join.
PART-3
Algebraic Manipulation of Boolean Expressions, Simplification
of Boolean Functions, Karnaugh Maps.
Questions-Answers
Que 3.16. Express each Boolean expression as SOP and then in its
complete sum-of-products form.
3–14 C (CS/IT-Sem-3) Lattices and Boolean Algebra
More pdf : www.motivationbank.in
a. E = x(xy + xy + yz)
b. E = z(x+ y) + y.
Answer
a. E = x.x.y + x.x.y + x.y.z = x.y + x.y.z = x.y'
( x.x.y = 0 and x.y is contained in x.y.z)
Complete SOP form = x.y (z + z) ( z is missing)
= x.y.z + x.y. z
b. E = z.(x+ y) + y = x.z + y.z + y
Then E = x.z(y + y) + y.z.(x + x) + y.(x + x) (z + z)
(by Complement law)
= x.y.z + x.y.z + x.y.z + x.y.z + x.y.z + x.z.y
+ x.y.z+ x.y.z
= x.y.z + x.y.z + x.y.z + x.y.z + x.y.z + x.y.z
Que 3.17. Define a Boolean function of degree n. Simplify the
following Boolean expression using Karnaugh maps
xyz + xy'z + x'y'z + x'yz + x'y'z'
Answer
Boolean function of degree n :
1. Let B = {0, 1}. Then Bn = {(x1, x2 ...., xn)|xi B for 1 i n} is the set of all
possible n-tuples of 0s and 1s.
2. The variable x is called a Boolean variable if it assumes values only
from B, that is, if its only possible values are 0 and 1.
3. A function from Bn to B is called a Boolean function of degree n.
4. For example, the function F(x, y) = xy from the set of ordered pairs of
Boolean variables to the set {0, 1}, is a Boolean function of degree z
with F(1, 1) = 1, F(1, 0) = 0, F(0, 1) = 0 and F(0, 0) = 0.
Numerical : The Karnaugh map for the given function is :
xyz + xyz + xyz + xyz + xyz
yz
x yz yz yz yz
x 1 1 1
x 1 1
Fig. 3.17.1.
Then the simplified expression is : z + x'y'.
Answer
a. f(x, y, z) = (0, 1, 5, 7)
z
xy 0 1
00 0 1
01 2 3
11 6 7
f=xy+xz
10 4 5
Fig. 3.18.1.
b. f (x, y, z) = (1, 2, 3, 6, 7)
yz
x 00 01 11 10
0 0 1 3 2
1 4 5 7 6
Fig. 3.18.2.
f= xz+y
Answer
yz
x 00 01 11 10
0 1 1 1
1 1
F = x z yz
Answer
a. Y = ((AB) + A + AB)
= ((AB)) (A + (AB))
= (AB) ((A) (AB))
3–16 C (CS/IT-Sem-3) Lattices and Boolean Algebra
More pdf : www.motivationbank.in
= AB (A (A + B))
= AB (AA + AB)
= AB(0 + AB) = AB AB
= ABB
=0
Here, we find that the expression is not in minterm. For getting minterm,
we simplify and find that its value is already zero. Hence, no need to use
K-map for further simplification.
b. A B C D + A B C D + A B CD + A B CD = A B
= A BCD + ABCD + ABCD + ABCD
CD AB
A B C D 1
A B C D 1
AB CD 1
AB CD 1
Fig. 3.20.1.
On simplification by K-map, we get AB corresponding to all the four
one’s.
Que 3.21. Find the Boolean algebra expression for the following
Fig. 3.21.1.
Answer
A ABC
B
C ABC + A(B + C )
A.(B + C )
B
B + C
C
Fig. 3.21.2.
Discrete Structures & Theory of Logic 3–17 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
Que 3.22. Find the Sum-Of-Products and Product-Of-s um
expansion of the Boolean function F(x, y, z) = (x + y) z.
AKTU 2018-19, Marks 07
Answer
F(x, y, z) = (x + y)z
x y z x+y z (x + y)z
1 1 1 1 0 0
1 1 0 1 1 1
1 0 1 1 0 0
1 0 0 1 1 1
0 1 1 1 0 0
0 1 0 1 1 1
0 0 1 0 0 0
0 0 0 0 1 0
Sum-Of-Product :
F(x, y, z) = xyz + xyz + xyz
Product-Of-Sum :
F(x, y, z) = (x + y + z)(x + y+ z)(x+ y + z)(x+ y+ z)
(x+ y+ z')
PART-4
Logic Gates, Digital Circuits and Boolean Algebra.
Questions-Answers
a. f(x1, x2, x3, x4) = x1 + (x2. (x1 + x4) + x3. (x2 + x4))
i. Simplify f algebraically
ii. Draw the logic circuit of the f and the reduction of the f.
b. Write the expres sions E 1 = (x + x * y) + (x/y) and
E2 = x + ((x * y + y)/y), into
3–18 C (CS/IT-Sem-3) Lattices and Boolean Algebra
More pdf : www.motivationbank.in
i. Prefix notation
Answer
a. i. f(x1, x2, x3, x4) = x1 + (x2.(x1 + x4) + x3.(x2+ x4)
= x1 + x2.x1 + x2.x4 + x3.x2 + x3.x4
= x1 + x2 + x2.x4 + x3.x2 + x3.x4
= x1 + x2.(1 + x4) + x3.x2 + x3.x4
= x1 + x2 + x3.x2 + x3.x4
= x1 + x2 + x3 + x3.x4
= x1 + x2 + x3.(1 + x4)
= x1 + x2 + x3
ii. Logic circuit :
x1 x1 + x2 + x3
x2
x3
Fig. 3.23.1.
Reduction of f :
f (x1, x2, x3, x4) = x1 + (x2.(x1 + x4) + x3.(x2 + x4)
= x1 + (x2.x1 + x2.x4) + (x3.x2 + x3.x4)
= x1 + x2.x1 + x2.x4 + x3.x2 + x3.x4
b. E1 = (x + x * y) + (x/y)
Binary tree is :
+ /
x * x y
x y
Fig. 3.23.2.
Prefix : ++ x * x y / xy
Postfix : xx y * + xy / +
E2 = x + ((x * y + y)/y)
Discrete Structures & Theory of Logic 3–19 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
Binary tree is :
/
x
y
+
* y
y
x
Fig. 3.23.3.
Prefix : + x / + * x y y y
Postfix : x x y * y + y / +
F(X, Y, Z) = (X + Y + Z) ( XYZ )
Answer
The logic network is shown below :
X X+Y+Z
Y
Z
(X + Y + Z) X Y Z
X
X
Y XYZ
Y
Z
Z
Fig. 3.24.1.
y
xy + xy
y xy
y
Fig. 3.25.1.
ii. The logic network shown in Fig. 3.25.2.
X
X
Y XY Z
Y
XY Z + XYZ + XY
Z X YZ
Z
XY
Fig. 3.25.2.
a c
f d
e
Fig. 1.
Discrete Structures & Theory of Logic 3–21 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
Ans. Refer Q. 3.3.
1 2
3 4
Fig. 2.
i. Verify that (A, R) is a poset and find its Hasse diagram.
ii. Is this a lattice ?
iii. How many more edges are needed in the Fig. 2 to extend
(A, R) to a total order ?
iv. What are the maximal and minimal elements ?
Ans. Refer Q. 3.6.
Q. 6.
a. Prove that every finite subset of a lattice has an LUB and a
GLB.
b. Give an example of a lattice which is a modular but not a
distributive.
Ans. Refer Q. 3.8.
Q. 9. Draw the Hasse diagram of (A, ), where A = {3, 4, 12, 24, 48,
72} and relation be such that a b if a divides b.
Ans. Refer Q. 3.11.
Q. 10. For any positive integer D36, then find whether (D36, ‘|’) is
lattice or not ?
Ans. Refer Q. 3.12.
Fig. 3.
Ans. Refer Q. 3.21.
Q. 14. Find the Sum-Of-Products and Product-Of-sum expansion
of the Boolean function F(x, y, z) = (x + y) z.
Ans. Refer Q. 3.22.
Q. 15. Consider the Boolean function.
a. f(x1, x2, x3, x4) = x1 + (x2. (x1 + x4) + x3. (x2 + x4))
i. Simplify f algebraically
ii. Draw the logic circuit of the f and the reduction of the
f.
b. Write the expres sions E 1 = (x + x * y) + (x/y) and
E2 = x + ((x * y + y)/y), into
i. Prefix notation ii. Postfix notation
Ans. Refer Q. 3.23.
More pdf : www.motivationbank.in
4–1 C (CS/IT-Sem-3)
Discrete Structures & Theory of Logic
4 Propositional Logic
and Predicate Logic
CONTENTS
Part-1 : Propositional Logic : .................................. 4–2C to 4–6C
Proposition, Well Formed
Formula, Truth Tables
Questions-Answers
Answer
Proposition : Proposition is a statement which is either true or false but not
both. It is a declarative statement. It is usually denoted by lower case letters
p, q, r, s, t etc. They are called Boolean variable or logic variable.
For example :
1. Dr. A.P.J. Abdul Kalam was Prime Minister of India.
2. Roses are red.
3. Delhi is in India
(1) proposition is false whereas (2) and (3) are true.
Compound proposition : A compound proposition is formed by composition
of two or more propositions called components or sub-propositions.
For example :
1. Risabh is intelligent and he studies hard.
2. Sky is blue and clouds are white.
Here first statement contain two propositions ‘‘Risabh is intelligent’’ and ‘‘he
studies hard’’ whereas second statement contain propositions ‘‘sky is blue’’
and ‘‘clouds are white’’. As both statements are formed using two propositions.
So they are compound propositions.
Answer
1. The words or phrases used to form compound proposition are called
connectives.
2. There are five basic connectives as shown in the Table 4.2.1.
More pdf : www.motivationbank.in
4–3 C (CS/IT-Sem-3)
Discrete Structures & Theory of Logic
Table. 4.2.1.
p q pq
T T T
T F T
F T T
F F F
4–4 C (CS/IT-Sem-3) Propositional Logic & Predicate Logic
More pdf : www.motivationbank.in
Que 4.3. What do you mean by well formed formula ?
Answer
1. Well formed formula is defined as a mathematical expression
represented in well defined form and uses parenthesis, braces and
square brackets to avoid the ambiguity.
2. Logical statements are also represented in well defined form using
parenthesis according to priority of operations. To generate well formed
formula recursively, following rules are used :
i. An atomic statement P is a well formed formula.
ii. If P is well formed formula then ~ P is also a well formed.
iii.
If P and Q are well formed formulae then (P Q), (P Q), (P Q)
and (P Q) are also well formed formulae.
iv. A statement consists of variables, parenthesis and connectives is
recursively a well formed formula iff it can be obtained by applying
the above three rules.
For example :
1. (P (P Q)
2. ((P Q) R)
Answer
i. Truth table : A truth table is a table that shows the truth value of a
compound proposition for all possible cases.
p q (p q) p q (p q) p ~p
T T T T T T T F
T F F T F T F T
F T F F T T
F F F F F F
ii. Logical equivalence : If two propositions P (p, q, .....) and Q (p, q, ...)
where p, q, ..... are propositional variables, have the same truth values
in every possible case, the propositions are called logically equivalent or
simply equivalent, and denoted by
P (p, q, .......) Q (p, q, ........)
Que 4.5. Explain the following terms with suitable example :
i. Conjunction
ii. Disjunction
iii. Conditional
More pdf : www.motivationbank.in
4–5 C (CS/IT-Sem-3)
Discrete Structures & Theory of Logic
iv. Converse
v. Contrapositive AKTU 2014-15, Marks 10
OR
Define inverse.
Answer
i. Conjunction : If p and q are two statements, then conjunction of p and
q is the compound statement denoted by p q and read as
“p and q”. Its truth table is,
p q pq
T T T
T F F
F T F
F F F
Example :
p : Ram is healthy.
q : He has blue eyes.
p q : Ram is healthy and he has blue eyes.
ii. Disjunction : If p and q are two statements, the disjunction of
p and q is the compound statement denoted by p q and it is read as “p
or q”. Its truth table is,
p q pq
T T T
T F T
F T T
F F F
Example :
p : Ram will go to Delhi.
q : Ram will go to Calcutta.
p q : Ram will go to Delhi or Calcutta.
iii. Conditional : If p and q are propositions. The compound proposition if
p then q denoted by p q or p q and is called conditional proposition
or implication. It is read as “If p then q” and its truth table is,
4–6 C (CS/IT-Sem-3) Propositional Logic & Predicate Logic
More pdf : www.motivationbank.in
p q pq
T T T
T F F
F T T
F F T
Example :
p : Ram works hard.
q : He will get good marks.
p q : If Ram works hard then he will get good marks.
For converse and contrapositive :
Let p : It rains.
q : The crops will grow.
iv. Converse : If p q is an implication then its converse is given by q p
states that S : If the crops grow, then there has been rain.
v. Contrapositive : If p q is an implication then its contrapositive is
given by q p states that,
t : If the crops do not grow then there has been no rain.
Inverse :
If p q is implication the inverse of p q is ~ p ~ q.
Consider the statement
p : It rains.
q : The crops will grow
The implication p q states that,
r : If it rains then the crops will grow.
The inverse of the implication p q, namely ~ p ~ q states that.
u : If it does not rain then the crops will not grow.
PART-2
Tautology, Satisfiability, Contradiction, Algebra of Proposition,
Theory of Inference.
Questions-Answers
Answer
1. Tautology : Tautology is defined as a compound proposition that is
always true for all possible truth values of its propositional variables and
it contains T in last column of its truth table.
Propositions like,
i. The doctor is either male or female.
ii. Either it is raining or not.
are always true and are tautologies.
2. Contradiction : Contradiction is defined as a compound proposition
that is always false for all possible truth values of its propositional
variables and it contains F in last column of its truth table.
Propositions like,
i. x is even and x is odd number.
ii. Tom is good boy and Tom is bad boy.
are always false and are contradiction.
3. Contingency : A proposition which is neither tautology nor
contradiction is called contingency.
Here the last column of truth table contains both T and F.
4. Satisfiability :
A compound statement formula A (P1, P2, ... Pn) is said to be satisfiable,
if it has the truth value T for at least one combination of truth value of
P1, P2,.... Pn.
Answer
Proposition satisfies various laws which are useful in simplifying complex
expressions. These laws are listed as :
1. Idempotent laws :
a. p p p
b. p p p
2. Associative laws :
a. (p q) r p (q r)
b. (p q) r p (q r)
3. Commutative laws :
a. p q q p
b. p q q p
4–8 C (CS/IT-Sem-3) Propositional Logic & Predicate Logic
More pdf : www.motivationbank.in
4. Distributive laws :
a. p (q r) (p q) (p r)
b. p (q r) (p q) (p r)
5. Identity laws :
a. p F p
b. p T T
c. p F F
d. p T p
6. Complement laws :
a. p ~P T
b. p ~p F
c. ~T F
d. ~F T
7. Involution law :
a. ~(~p) p
8. De Morgan's laws :
a. ~ (p q) ~p ~q
b. ~ (p q) ~p ~q
9. Absorption laws :
a. p (p q) p
b p (p q) p
These laws can easily be verified using truth table.
Answer
Rules of inference are the laws of logic which are used to reach the given
conclusion without using truth table. Any conclusion which can be derived
using these laws is called valid conclusion and hence the given argument is
valid argument.
1. Modus ponens (Law of detachment) : By this rule if an implication
p q is true and the premise p is true then we can always conclude that
q is also true.
The argument is of the form :
p q
p
q
2. Modus tollens (Law of contraposition) : By this rule if an implication
p q is true and conclusion q is false then the premise p must be false.
The argument is of the form :
More pdf : www.motivationbank.in
4–9 C (CS/IT-Sem-3)
Discrete Structures & Theory of Logic
p q
~q
~p
3. Hypothetical syllogism : By this rule whenever the two implications
p q and q r are true then the implication p r is also true.
The argument is of the form :
p q
q r
p r
4. Disjunctive syllogism : By this rule if the premises p q and ~ q are
true then p is true.
The argument is of the form :
p q
~q
p
5. Addition : By this rule if p is true then p q is true regardless the truth
value of q.
The argument is of the form :
p
p q
6. Simplification : By this rule if p q is true then p is true.
The argument is of form :
p q p q
p or q
7. Conjunction : By this rule if p and q are true then p q is true.
The argument is of the form :
p
q
p q
8. Constructive dilemma : By this rule if (p q) (r s) and p r are
true then q s is true.
The argument is of form :
( p q) ( r s)
p r
q s
9. Destructive dilemma : By this rule if (p q) (r s) and ~ q s
are true.
The argument is of the form :
4–10 C (CS/IT-Sem-3) Propositional Logic & Predicate Logic
More pdf : www.motivationbank.in
( p q) (r s)
~qs
pr
10. Absorption : By this rule if p q is true then p (p q) is true.
The argument is of the form :
p q
p ( p q)
Que 4.9. What do you mean by valid argument ? Are the following
arguments valid ? If valid, construct a formal proof ; if not, explain
why.
For students to do well in discrete structure course, it is necessary
that they study hard. Students who do well in courses do not skip
classes. Student who study hard do well in courses. Therefore
students who do well in discrete structure course do not skip class.
Answer
Valid arguments :
1. An argument P1, P2, ..., Pn Q is said to be valid if Q is true whenever
all the premises P1, P2, ..., Pn are true.
2. For example : Consider the argument : p q, q p.
C P P
p q p q
T T T
T F F
F T T
F F T
where P denotes the premise and C denotes the conclusion.
3. From the truth table we can see in first and third rows both the premises
q and p q are true, but the conclusion p is false in third row. Therefore,
this is not a valid argument.
4. First and third rows are called critical rows.
5. This method to determine whether the conclusion logically follows
from the given premises by constructing the relevant truth table is
called truth table technique.
6. Also, we can say the argument P1, P2, ..., Pn Q is valid if and only if
the propo sitio n P 1 P 2 ... P n is true o r we can say if
P1 P2 ... Pn Q is a tautology.
For example : Consider the argument p q, p q.
More pdf : www.motivationbank.in
4–11 C (CS/IT-Sem-3)
Discrete Structures & Theory of Logic
Que 4.10.
i. Show that ((p q) ~ (~ p (~ q ~ r))) (~ p ~q) (~p r) is a
tautology without using truth table.
ii. Rewrite the following arguments using quantifiers, variables
and predicate symbols :
a. All birds can fly.
b. Some men are genius.
c. Some numbers are not rational.
d. There is a student who likes mathematics but not geography.
AKTU 2014-15, Marks 10
OR
Show that ((p q) ~ (~p (~q ~r))) (~p ~q) (~ p r) is a
tautology without using truth table. AKTU 2018-19, Marks 07
4–12 C (CS/IT-Sem-3) Propositional Logic & Predicate Logic
More pdf : www.motivationbank.in
Answer
i. We have
((p q) ~ (~ p (~ q r))) (~ p ~ q) (~ p r)
((p q) ~ (~ p ~ (q r))) (~ (p q) ~ ( p r))
(Using De Morgan's Law)
[(p q)] (p (q r)) ~ ((p q) (p r))
[(p q) (p q) (p r)] ~ (( p q) (p r))
(Using Distributive Law)
[((p q) (p q)] (p r) ~ ((p q) (p r))
((p q) (p r)) ~ ((p q) (p r))
x ~ x where x = (p q) (p r)
T
ii. a. x [B(x) F(x)] b. x [M(x) G(x)]
c. ~[ (x) (N(x) R(x)] d. x [S(x) M(x) ~ G(x)]
Que 4.11. “If the labour market is perfect then the wages of all
persons in a particular employment will be equal. But it is always
the case that wages for such persons are not equal therefore the
labour market is not perfect”. Test the validity of this argument
using truth table. AKTU 2014-15, Marks 10
Answer
Let p1 : The labour market is perfect.
p2 : Wages of all persons in a particular employment will be equal.
~p2 : Wages for such persons are not equal.
~p1 : The labour market is not perfect.
The premises are p1 p2 , ~ p2 and the conclusion is ~ p1. The argument
p1 p2, ~ p2 ~ p1 is valid if ((p1 p2) ~ p2) ~ p1 is a tautology.
Its truth table is,
p1 p2 ~p1 ~p2 p1 p2 (p1 p2) ~p2 (p1p2 ~ p2) ~p1
T T F F T F T
T F F T F F T
F T T F T F T
F F T T T T T
Since ((p1 p2) ~p2) ~p1 is a tautology. Hence, this is valid argument.
Que 4.12. What is a tautology, contradiction and contingency ?
Show that (p q) ( p r) (q r) is a tautology, contradiction or
contingency. AKTU 2018-19, Marks 07
More pdf : www.motivationbank.in
Discrete Structures & Theory of Logic 4–13 C (CS/IT-Sem-3)
Answer
Tautology, contradiction and contingency : Refer Q. 4.6, Page 4–7C,
Unit-4.
Proof : ((p q) (~ p r)) (q r)
p q r ~P (p q) (~ p r) (A B) (q r) C D
=A =B =C =D
F F F T F T T F F
F F T T F T T T T
F T F T T T T T T
F T T T T T T T T
T F F F T F T F F
T F T F T T T T T
T T F F T F T T T
T T T F T T T T T
So, ((p q) (~ p r)) (q r) is contingency.
Que 4.13.
i. Find a compound proposition involving the propositional
variables p, q, r and s that is true when exactly three
propositional variables are true and is false otherwise.
ii. Show that the hypothesis “It is not sunny this afternoon and it
is colder than yesterday”, “We will go swimming only if it is
sunny”, “If we do not go swimming, then we will take a canoe
trip.” and “If we take a canoe trip, then we will be home by
sunset” lead to the conclusion “We will be home by sunset.”
OR
Show that the premises “It is not sunny this afternoon and it is
colder than yesterday,” “We will go swimming only if it is sunny,”
“If we do not go swimming, then we will take a canoe trip.” and
“If we take a canoe trip, then we will be home by sunset” lead to
the conclusion “We will be home by sunset.”
AKTU 2018-19, Marks 07
Answer
Answer
Following the indirect method, we introduce p as an additional premise and show
that this additional premise leads to a contradiction.
{1} (1) p q Rule P
{2} (2) p Rule P (assumed)
{1, 2} (3) q Rule T, (1), (2) and modus ponens
{4} (4) s q Rule P
{1, 2, 4} (5) s Rule T, (3), (4) and modus tollens
{6} (6) r s Rule P
{1, 2, 4, 6} (7) r Rule T, (5), (6) disjunctive syllogism
{8} (8) r q Rule P
{8} (9) r q Rule T, (8) and EQ16 (p q p q)
{8} (10) r q Rule T, (8) and De Morgan’s law
{1, 2, 4, 6} (11) r q Rule T, (7), (3) and conjunction
{1, 2, 4, 6, 8} (12) r q r q Rule T, (10), (11) and conjunction.
PART-3
Predicate Logic : First Order Predicate, Well Formed Formula of
Predicate, Quantifiers, Inference Theory of Predicate Logic.
Questions-Answers
Answer
1. First order logic :
i. First order logic is the extension of propositional logic by generalizing
and quantifying the propositions over given universe of discourse.
ii. In first order logic every individual has the property p (say).
iii. It is also called first order predicate calculus.
iv. Predicate calculus is generalization of propositional calculus.
Predicate calculus allows us to manipulate statements about all or
something.
v. Universe of Discourse (UD) : It is the set of all possible values that
can be substituted in place of predicate variable.
2. Quantifiers : There are following two types of quantifiers :
i. Universal quantifier : Let p(x) be a propositional function defined
on set A. Consider the expression.
( x A) P(x) or x P(x) ...(4.15.1)
Here the symbol ‘‘’’ is read as ‘‘for all’’ or ‘‘for every’’ and is called
universal quantifier. Then the statement (4.15.1) is read as ‘‘For
every x A, P(x) is true.’’
ii. Existential quantifier : Let Q(x) be a propositional function defined
on set B. Consider the expression
(x B) Q(x) or x Q(x) ...(4.15.2)
Here the symbol ‘‘’’ is read as ‘‘for some’’ or ‘‘for at least one’’ or
‘‘there exists’’ and is called existential quantifier.
Then the statement (4.15.2) is read as ‘‘For some x B, Q(x) is
true’’.
Que 4.17. Write the symbolic form and negate the following
statements :
a. Everyone who is healthy can do all kinds of work.
b. Some people are not admired by everyone.
c. Everyone should help his neighbours, or his neighbours will
not help him. AKTU 2016-17, Marks 10
More pdf : www.motivationbank.in
4–17 C (CS/IT-Sem-3)
Discrete Structures & Theory of Logic
Answer
a. Symbolic form :
Let P(x): x is healthy and Q(x): x do all work
x(P(x) Q(x))
Negation : ( x (P(x) Q(x))
b. Symbolic form :
Let P(x) : x is a person
A(x, y) : x admires y
The given statement can be written as “There is a person who is not
admired by some person” and it is (x) ( y)[P(x) P(y) A(x, y)]
Negation : ( x) ( y) [P (x) P(y) A(x, y)]
c. Symbolic form :
Let N(x, y) : x and y are neighbours
H(x, y) : x should help y
P(x, y) : x will help y
The statement can be written as “For every person x and every person
y, if x and y are neighbours, then either x should help y or y will not help
x” and it is ( x) ( y)[N(x, y) (H(x, y) P(y, x))]
Negation : ( x) ( y) [N(x, y) (H (x, y) P (y, x))]
Que 4.18. Express the following statements using quantifiers and
logical connectives.
a. Mathematics book that is published in India has a blue cover.
b. All animals are mortal. All human being are animal. Therefore,
all human being are mortal.
c. There exists a mathematics book with a cover that is not blue.
d. He eats crackers only if he drinks milk.
e. There are mathematics books that are published outside India.
f. Not all books have bibliographies. AKTU 2015-16, Marks 10
Answer
a. P(x) : x is a mathematic book published in India
Q(x) : x is a mathematic book of blue cover
x P(x) Q(x).
b. P(x) : x is an animal
Q(x) : x is mortal
x P(x) Q(x)
4–18 C (CS/IT-Sem-3) Propositional Logic & Predicate Logic
More pdf : www.motivationbank.in
R(x) : x is a human being
x R(x) P(x).
c. P(x) : x is a mathematics book
Q(x) : x is not a blue color
x, P(x) Q(x).
d. P(x) : x drinks milk
Q(x) : x eats crackers
for x, if P(x) then Q(x).
or x, P(x) Q(x).
e. P(x) : x is a mathematics book
Q(x) : x is published outside India
x P(x) Q(x).
f. P(x) : x is a book having bibliography ~ x, P(x).
Que 4.19.
i. Express this statement using quantifiers : “Every student in
this class has taken some course in every department in the
school of mathematical sciences”.
ii. If x yP( x , y) is true, does it necessarily follow that yP( x , y) is
true ? Justify your answer.
Answer
Answer
i. x [S(x) F(x)]
ii. ~ [(x) (C(x) W(x))]
iii. Sentence is incorrect so cannot be translated into quantified expression.
iv. W(x) : x is water
H(x) : x is hot
S(x) : x is Shyam
P(x) : x will swim in pool
x [((W(x) H(x)) (S(x) P(x))]
v. E(x) : x is even
O(x) : x is odd
x (E(x) O(x))
Q. 3. “If the labour market is perfect then the wages of all persons
in a particular employment will be equal. But it is always
the case that wages for such persons are not equal therefore
the labour market is not perfect”. Test the validity of this
argument using truth table.
Ans. Refer Q. 4.11.
Q. 4. What is a tautology, contradiction and contingency ? Show
that (p q) ( p r) (q r) is a tautology, contradiction
or contingency.
4–20 C (CS/IT-Sem-3) Propositional Logic & Predicate Logic
More pdf : www.motivationbank.in
Ans. Refer Q. 4.12.
Q. 5. Show that the premises “It is not sunny this afternoon and
it is colder than yesterday,” “We will go swimming only if it
is sunny,” “If we do not go swimming, then we will take a
canoe trip.” and “If we take a canoe trip, then we will be
home by sunset” lead to the conclusion “We will be home by
sunset.”
Ans. Refer Q. 4.13.
More pdf : www.motivationbank.in
5–1 C (CS/IT-Sem-3)
Discrete Structures & Theory of Logic
5
UNIT
Trees, Graph and
Combinatorics
CONTENTS
Part-1 : Trees : Definition, ...................................... 5–2C to 5–4C
Binary Tree
Questions-Answers
Answer
i. Tree :
1. A tree is a connected graph that contains no cycle or circuit. It is a
simple graph having no self loop or parallel edges.
2. A tree contains a finite set of elements which are called vertices or
nodes. The vertex can have minimum degree 1 and maximum
degree n.
3. The number of vertices in a tree is called order of tree.
4. A tree with only one vertex is called trivial or degenerate or empty
tree.
Fig. 5.1.1.
ii. Forest : A forest is a collection of disjoint tree. It is an undirected,
disconnected, acyclic graph.
Fig. 5.1.2.
iii. Binary tree : Binary tree is the tree in which the degree of every
node is less than or equal to 2. A tree consisting of no nodes is also a
binary tree.
More pdf : www.motivationbank.in
Discrete Structures & Theory of Logic5–3 C (CS/IT-Sem-3)
b c
d e
h i
f g j
Fig. 5.1.3.
It is represented as Tn where n is number of nodes.
v. Full binary tree : A binary tree is said to be extended or full binary tree
if each node has either 0 or 2 children.
b c
d e
g
f
Fig. 5.1.4.
b c
d j k
e f
l
g h
i
Fig. 5.2.1.
Answer
i. The node a is the root node.
ii. The node g, h, i, j and l are leaves.
PART-2
Binary Tree Traversal.
Questions-Answers
Answer
Tree traversal : A traversal of tree is a process in which each vertex is
visited exactly once in a certain manner. For a binary tree we have three
types of traversal :
1. Preorder traversal : Each vertex is visited in the following order :
a. Visit the root (N).
b. Visit the left child (or subtree) of root (L).
c. Visit the right child (or subtree) of root (R).
2. Postorder traversal :
a. Visit the left child (subtree) of root.
b. Visit the right child (subtree) of root.
c. Visit the root.
3. Inorder traversal :
a. Visit the left child (subtree) of root.
b. Visit the root.
c. Visit the right child (subtree) of root.
A binary tree with 12 vertices :
A
B C
D G
E F
H I
J K L
Fig. 5.3.1.
5–6 C (CS/IT-Sem-3) Trees, Graph and Combinatorics
More pdf : www.motivationbank.in
Preorder (NLR) : A B D H I E J C F K L G
Inorder (LNR) : HDIBJEAKFLCG
Postorder (LRN) : H I D J E B K L F G C A
Answer
Root is G.
Fig. 5.4.1.
Element to left of G in inorder traversal are Q B A and B comes first in
preorder traversal. Therefore tree will be
Q A
Fig. 5.4.2.
Now elements on the right of G in inorder traversal are CPEDR and P comes
first. Therefore tree will be
B P
Q A
Fig. 5.4.3.
Now element to left of P in inorder traversal is C and to the right is EDR
(right subtree) out of DER, D comes first and E and R on its left and right
respectively.
More pdf : www.motivationbank.in
Discrete Structures & Theory of Logic5–7 C (CS/IT-Sem-3)
P
B
C D
Q A
E R
Fig. 5.4.4.
Que 5.5. Define a binary tree. A binary tree has 11 nodes. It’s
inorder and preorder traversals node sequences are :
Preorder : A B D H I E J L C F G
Inorder : H D I B J E K A F C G
Draw the tree. AKTU 2018-19, Marks 07
Answer
Binary tree : Refer Q. 5.1(iii), Page 5–2C, Unit-5.
Numerical :
Step 1 : In preorder sequence, leftmost element is the root of the tree. By
searching A in ‘Inorder Sequence’ we can find out all the elements on the left
and right sides of ‘A’.
A
HDIBJEK FCG
B C
A
B C D E F G
HDI JEK F G H I J K
Now H F E are on left of A in inorder traversal and B comes last of all and
continuing in same manner. We will get final binary tree as
I
G
A
D
F B C
H E
PART-3
Binary Search Tree.
Questions-Answers
Answer
Binary search tree :
1. A binary search tree is a binary tree T in which data is associated with
the vertices.
2. The data are arranged so that, for each vertex v in T, each data item in
the left subtree of v is less than the data item in v and each data item
in the right subtree of v is greater than the data item in v.
3. The binary tree T in Fig. 5.7.1, is a binary search tree since every
vertex in T exceeds every number in its left subtree and is less than
every number in its right subtree.
50
40 70
75
30 45
42 65
warbler
3. Similarly by doing the above steps for rest of words we get the final
binary search tree that is given below :
vireo
egret warbler
grosbeak
nuthatch
kingfisher
5–10 C (CS/IT-Sem-3) Trees, Graph and Combinatorics
More pdf : www.motivationbank.in
Que 5.8. Write algorithm for following :
i. Searching and inserting a node in BST
ii. Deleting a node in BST
Answer
i. Searching and inserting a node in BST :
Consider a binary search tree T and we have to insert or search an ITEM in
the tree.
Step I : Compare ITEM with the root of the tree
a. If ITEM < root, proceed to the left child of N.
b. If ITEM > root, proceed to the right child of N.
Step II : Repeat Step I and if
a. We reach a node N such that ITEM = N then search is successful.
b. We reach an empty subtree, which shows the search is successful.
Insert ITEM in place of empty subtree.
ii. Deleting a node in BST :
Consider a binary search tree T and we have to delete an ITEM from the
tree.
Step I : Find the location of node which contain ITEM and also keep track of
its parent too.
Step II : Find the number of children of the node.
a. If node has no children then simply delete the node.
b. If the node has exactly one child then the node is deleted from tree by
replacing the node from its child.
c. If the node has two children then
i. Find its inorder successor.
ii. Delete the successor from tree using (a) or (b).
iii. Replace node by its successor in tree.
Que 5.9. Draw a binary search tree by inserting following
integers 55, 20, 63, 10, 28, 60, 93, 5, 11, 40, 68, 25.
Answer
1. Insert 55 :
55
2. Insert 20 :
55
20
More pdf : www.motivationbank.in
5–11 C (CS/IT-Sem-3)
Discrete Structures & Theory of Logic
3. Insert 63 :
55
20 63
4. Insert 10 :
55
20 63
10
5. Insert 28 :
55
20 63
10 28
6. Insert 60 :
55
63
20
10 28 60
7. Insert 93 :
55
63
20
10 28 60 93
8. Insert 5 :
55
20 63
10 28 60 93
5
5–12 C (CS/IT-Sem-3) Trees, Graph and Combinatorics
More pdf : www.motivationbank.in
9. Insert 11 :
55
20 63
10 28 60 93
5 11
10. Insert 40 :
55
20 63
10 28 60 93
5 11 40
11. Insert 68 :
55
20 63
10 28 60 93
5 11 40 68
12. Insert 25 :
55
20 63
10 28 60 93
5 11 25 40 68
PART-4
Graphs : Definition and Terminology, Representation of Graph.
More pdf : www.motivationbank.in
5–13 C (CS/IT-Sem-3)
Discrete Structures & Theory of Logic
Questions-Answers
Que 5.10. What do you mean by graph ? Also, explain directed and
undirected graph.
Answer
A graph is a non-linear data structure consisting of nodes and edges. A graph
consists of two sets as follows :
1. Set V of nodes or point or vertices of graph G.
2. Set E of ordered or unordered pairs of distinct edges of G.
We denote such a graph by G(V, E) and set of vertices as V(G) and set of
edges as E(G).
For example :
V4 c V3
d e b
V1 V2
a
Fig. 5.10.1.
Order : If G is finite then number of vertices in G denoted by |V (G)| is
called order of G.
Size : The number of edges denoted by |E(G)|in a finite graph G is called
size of G.
Directed graph : A graph G(V, E) is said to be directed graph or digraph if
each edge e E is associated with an ordered pair of vertices as shown
below :
c
a b
Fig. 5.10.2.
Undirected graph : A graph G(V, E) is said to be undirected if each edge
e E is associated with an unordered pair of vertices as shown below :
a b
c d
Fig. 5.10.3.
5–14 C (CS/IT-Sem-3) Trees, Graph and Combinatorics
More pdf : www.motivationbank.in
Que 5.11. Discuss representation of graph.
Answer
Graph can be represented in following two ways :
1. Matrix representation :
Matrices are commonly used to represent graphs for computer
processing. Advantages of representing the graph in matrix lies in the
fact that many results of matrix algebra can be readily applied to study
the structural properties of graph from an algebraic point of view.
a. Adjacency matrix :
i. Representation of undirected graph :
The adjacency matrix of a graph G with n vertices and no
parallel edges is a n × n matrix A = [aij] whose elements are
given by
aij = 1, if there is an edge between ith and jth vertices
= 0, if there is no edge between them
ii. Representation of directed graph :
The adjacency matrix of a digraph D, with n vertices is the
matrix
A = [aij]n×n in which
aij = 1 if arc (vi, vj) is in D
= 0 otherwise
For example :
V1 V4
V2 V3
Fig. 5.11.1.
v1 v2 v3 v4
v1 0 1 1 1
0 1 0
A = v2 1
v3 1 1 0 1
v4 1 0 1 0
b. Incidence matrix :
i. Representation of undirected graph :
Consider an undirected graph G = (V, E) which has n vertices
and m edges all labelled. The incidence matrix I(G) = [bij], is
then n × m matrix, where
bij = 1 when edge ej is incident with vi
= 0 otherwise
More pdf : www.motivationbank.in
5–15 C (CS/IT-Sem-3)
Discrete Structures & Theory of Logic
e4 e5 e2
v4 e3 v3
Fig. 5.11.2.
The incidence matrix of the digraph of Fig. 5.11.2 is
1 0 0 1 1
1 1 0 0 0
I(D) =
0 1 1 0 1
0 0 1 1 0
2. Linked representation : In this representation, a list of vertices
adjacent to each vertex is maintained. This representation is also called
adjacency structure representation. In case of a directed graph, a care
has to be taken, according to the direction of an edge, while placing a
vertex in the adjacent structure representation of another vertex.
PART-5
Multigraph, Bipartite Graphs, Planar Graph,
Isomorphism and Homomorphism of Graphs.
Questions-Answers
Answer
a. Simple and multigraph :
i. Simple graph : A graph in which there is only one edge between
a pair of vertices is called a simple graph.
e
V1 V2
Fig. 5.12.1.
ii. Multigraph : Any graph which contains some parallel edges is
called a multigraph.
e3
V4 V3
e4 e2
V1 V2
e1
Fig. 5.12.2.
b. Complete graph and regular graph :
i. Complete graph : A simple graph, in which there is exactly one
edge between each pair of distinct vertices is called a complete
graph. The complete graph of n vertices is denoted by Kn. The
graphs K1 to K5 are shown below in Fig. 5.12.3.
K1 K2 K3 K4 K5
Fig. 5.12.3.
n(n – 1) n
Kn has exactly = C2 edges
2
ii. Regular graph (n-regular graph) : If every vertex of a simple
graph has equal edges then it is called regular graph.
If the degree of each vertex is n then the graph is called n-regular
graph.
Fig. 5.12.5.
c. Bipartite graph :
i. Bipartite graph : A graph G = (V, E) is bipartite if the vertex set
V can be partitioned into two subsets (disjoint) V1 and V2 such that
every edge in E connects a vertex in V1 and a vertex V2 (so that no
edge in G connects either two vertices in V1 or two vertices in V2).
(V1, V2) is called a bipartition of G.
x1 x2 x3 x1 x2 x3 x4
which
x4
redrawn
as :
y1 y2 y3 y1 y2 y3
Fig. 5.12.6. Some bipartite graphs.
K3,5 K2,6
Fig. 5.12.7. Some complete bipartite graphs.
d. Planar graph :
A graph G is said to be planar if there exists some geometric
representation of G which can be drawn on a plane such that no two of
its edges intersect except only at the common vertex.
i. A graph is said a planar graph, if it cannot be drawn on a plane
without a crossover between its edges crossing.
ii. The graphs shown in Fig. 5.12.8(a) and (b) are planar graphs.
5–18 C (CS/IT-Sem-3) Trees, Graph and Combinatorics
More pdf : www.motivationbank.in
(a) (b )
Fig. 5.12.8. Some planar graph.
Answer
i. Refer Q. 5.12(c), Page 5–15C, Unit-5.
ii. Refer Q. 5.12(b), Page 5–15C, Unit-5.
iii. Number of edge in K7 : Since, Kn is complete graph with n vertices.
7(7 1) 7 6
Number of edge in K7 = = 21
2 2
Number of edge in K3, 6 :
Since, Kn, m is a complete bipartite graph with n V1 and m V2
Number of edge in K3, 6 = 3 × 6 = 18
iv. Refer Q. 5.15(d), Page 5–18A, Unit-5.
Answer
Isomorphism of graph : Two graphs are isomorphic to each other if :
i. Both have same number of vertices and edges.
ii. Degree sequence of both graphs are same (degree sequence is the
sequence of degrees of the vertices of a graph arranged in non-increasing
order).
Example :
Fig. 5.14.1.
Homomorphism of graph : Two graphs are said to be homomorphic if one
graph can be obtained from the other by the creation of edges in series (i.e.,
by insertion of vertices of degree two) or by the merger of edges in series.
More pdf : www.motivationbank.in
5–19 C (CS/IT-Sem-3)
Discrete Structures & Theory of Logic
(a) (b ) (c )
Fig. 5.14.2.
Que 5.15. Prove that K3 and K4 are planar graphs. Prove that K5 is
non-planar.
Answer
The complete K3 graph has 3 edges and 3 vertices.
For a graph to be planar 3 – e 6
3 – e = 3 × 3 – 3 = 9 – 3 = 6 6
K3 is planar graph
Similarly complete K4 graph has 4 vertices and 6 edges.
3 – e = 3 × 4 – 6 = 12 – 6 = 6 6
K4 is planar graph
The complete K5 graph contains 5 vertices and 10 edges.
Now 3 – e = 3 × 5 – 10 = 15 – 10 = 5 6
Hence K5 is non planar since for a graph to be planar 3v – e 6.
Que 5.16. What are Euler and Hamiltonian graph ?
OR
Explain the following terms with example :
i. Homomorphism and Isomorphism graph
ii. Euler graph and Hamiltonian graph
iii. Planar and Complete bipartite graph
AKTU 2014-15, Marks 10
Answer
i. Refer Q. 5.14, Page 5–18C, Unit-5.
ii. Eulerian path : A path of graph G which includes each edge of G
exactly once is called Eulerian path.
Eulerian circuit : A circuit of graph G which include each edge of G exactly
once.
Eulerain graph : A graph containing an Eulerian circuit is called Eulerian
graph.
For example : Graphs given below are Eulerian graphs.
V1 V3 A B
V2
V5 V4 D C
Fig. 5.16.1.
5–20 C (CS/IT-Sem-3) Trees, Graph and Combinatorics
More pdf : www.motivationbank.in
Hamiltonian graph : A Hamiltonian circuit in a graph G is a closed path
that visit every vertex in G exactly once except the end vertices. A graph G is
called Hamiltonian graph if it contains a Hamiltonian circuit.
For example : Consider graphs given below :
D C D C
F
E
A B A B
(a) (b )
Fig. 5.16.2.
Graph given is Fig. 5.16.2(a) is a Hamiltonian graph since it contains a
Hamiltonian circuit A – B – C – D – A while graph in Fig 5.15.2(b) is not a
Hamiltonian graph.
Hamiltonian path : The path obtained by removing any one edge from a
Hamiltonian circuit is called Hamiltonian path. Hamiltonian path is subgraph
of Hamiltonian circuit. But converse is not true.
The length of Hamiltonian path in a connected graph of n vertices is
n – 1 if it exists.
iii. Refer Q. 5.12, Page 5–15C, Unit-5.
Que 5.17.
a. Prove that a connected graph G is Euler graph if and only if
every vertex of G is of even degree.
b. Which of the following simple graph have a Hamiltonian circuit
or, if not a Hamiltonian path ? AKTU 2016-17, Marks 15
a b a b a b g
c d c f
e d c e
d
G1 G2 G3
Fig. 5.17.1.
Answer
a.
1. First of all we shall prove that if a non-empty connected graph is
Eulerian then it has no vertices of odd degree.
2. Let G be Eulerian.
3. Then G has an Eulerian trail which begins and ends at u.
More pdf : www.motivationbank.in
5–21 C (CS/IT-Sem-3)
Discrete Structures & Theory of Logic
4. If we travel along the trail then each time we visit a vertex. We use
two edges, one in and one out.
5. This is also true for the start vertex because we also end there.
6. Since an Eulerian trail uses every edge once, the degree of each
vertex must be a multiple of two and hence there are no vertices of
odd degree.
7. Now we shall prove that if a non-empty connected graph has no
vertices of odd degree then it is Eulerian.
8. Let every vertex of G have even degree.
9. We will now use a proof by mathematical induction on |E(G)|, the
number of edges of G.
Basis of induction :
Let |E(G)| = 0, then G is the graph K1, and G is Eulerian.
Inductive step :
1. Let P(n) be the statement that all connected graphs on n edges of
even degree are Eulerian.
2. Assume P(n) is true for all n < |E(G)|.
3. Since each vertex has degree at least two, G contains a cycle C.
4. Delete the edges of the cycle C from G.
5. The resulting graph, G say, may not be connected.
6. However, each of its components will be connected, and will have
fewer than |E(G)| edges.
7. Also, all vertices of each component will be of even degree, because
the removal of the cycle either leaves the degree of a vertex
unchanged, or reduces it by two.
8. By the induction assumption, each component of G is therefore
Eulerian.
9. To show that G has an Eulerian trail, we start the trail at a vertex,
u say, of the cycle C and traverse the cycle until we meet a vertex,
c1 say, of one of the components of G .
10. We then traverse that component’s Eulerian trail, finally returning
to the cycle C at the same vertex, c1.
11. We then continue along the cycle C, traversing each component of
G as it meets the cycle.
12. Eventually, this process traverses all the edges of G and arrives
back at u, thus producing an Eulerian trail for G.
13. Thus, G is Eulerian by the principle of mathematical induction.
b. G1 : The graph G1 shown in Fig. 5.17.1 contains Hamiltonian circuit, i.e.,
a – b – c – d – e – a and also a Hamiltonian path, i.e., abcde.
G2 : The graph G2 shown in Fig. 5.17.1 does not contain Hamiltonian
circuit since every cycle containing every vertex must contain the edge
e twice. But the graph does have a Hamiltonian path a – b – c – d.
5–22 C (CS/IT-Sem-3) Trees, Graph and Combinatorics
More pdf : www.motivationbank.in
G3 : The graph G3 shown in Fig. 5.17.1 neither have Hamiltonian circuit
nor have Hamiltonian path because any traversal does not cover all the
vertices.
(n k) ( n k 1)
components can have at most edges.
2
AKTU 2016-17, Marks 10
Answer
Let the number of vertices in each of the k-components of a graph G be n1,
n2, ...., nk, then we get
n1 + n2 + ... + nk = n where ni 1 (i = 1, 2, ..., k)
k k k
Now, (n i 1) = n 1 = n – k
i 1
i
i 1
i 1
k 2
(ni 1) = n + k – 2nk
2 2
i 1
k k
or (n i 1)2 2 (ni 1)(n j 1) = n2 + k2 – 2nk
i 1 i 1 j 1
i j
k
[ ni – 1 0, nj – 1 0]
k
or (n i 1)2 n2 + k2 – 2nk
i 1
k k k
2
or n 1 2 n
i i n2 + k2 – 2nk
i 1 i 1 i 1
k
2
or n i k 2n n2 + k2 – 2nk
i 1
k
2
or n i n n2 + k2 – 2nk – k + n
i 1
= n(n – k + 1) – k (n – k + 1)
= (n – k)(n – k + 1) ...(5.18.1)
We know that the maximum number of edges in the ith component of
ni ni (ni 1)
G= C2 =
2
Therefore, the maximum number of edges in G is :
1 1 1
2
ni (ni 1) = 2 n n
2
i i =
2
n
2
i n
More pdf : www.motivationbank.in
5–23 C (CS/IT-Sem-3)
Discrete Structures & Theory of Logic
1
(n – k)(n – k + 1) by using eq. (5.18.1)
2
Que 5.19. What are different ways to represent a graph ? Define
Euler circuit and Euler graph. Give necessary and sufficient
conditions for Euler circuits and paths. AKTU 2018-19, Marks 07
Answer
Representation of graph : Refer Q. 5.11, Page 5–14C, Unit-5.
Euler circuit and Euler graph : Refer Q. 5.16, Page 5–19C, Unit-5.
Necessary and sufficient condition for Euler circuits and paths :
1. A graph has an Euler circuit if and only if the degree of every vertex is
even.
2. A graph has an Euler path if and only if there are at most two vertices
with odd degree.
Answer
1. Breadth First Search (BFS) : Breadth First Search (BFS) is an
algorithm for traversing or searching tree or graph data structures. It
starts at the tree root and explores the neighbour nodes first, before
moving to the next level neighbours.
Algorithmic steps :
Step 1 : Push the root node in the queue.
Step 2 : Loop until the queue is empty.
Step 3 : Remove the node from the queue.
Step 4 : If the removed node has unvisited child nodes, mark them as
visited and insert the unvisited children in the queue.
Depth First Search (DFS) :
Depth First Search (DFS) is an algorithm for traversing or searching
tree or graph data structures. One starts at the root (selecting some
arbitrary node as the root in the case of a graph) and explores as far as
possible along each branch before backtracking.
Algorithmic steps :
Step 1 : Push the root node in the stack.
Step 2 : Loop until stack is empty.
Step 3 : Pick the node of the stack.
Step 4 : If the node has unvisited child nodes, get the unvisited child
node, mark it as traversed and push it on stack.
5–24 C (CS/IT-Sem-3) Trees, Graph and Combinatorics
More pdf : www.motivationbank.in
Step 5 : If the node does not have any unvisited child nodes, pop the
node from the stack.
2. Refer Q. 5.16, Page 5–19C, Unit-5.
3. Refer Q. 5.11, Page 5–14C, Unit-5.
PART-6
Graph Coloring.
Questions-Answers
Answer
1. Suppose that G (V, E) is a graph with no multiple edges, a vertex colouring
of G is an assignment of colours.
2. A graph G is m-colourable if there exists a colouring of G which uses m
colours.
3. Colouring the vertices such a way such that no two adjacent vertices
have same colour is called proper colouring otherwise it is called
improper colouring.
PART-7
Recurrence Relation and Generating Function : Recursive
Definition of Function, Recursive Algorithms, Method of
Solving Recurrences, Combinatorics : Introduction,
Counting Techniques, Pigeonhole Principle.
Questions-Answers
Answer
For a sequence of numbers or numeric function (a0, a1, a2,... ar, ....) an
equation relating ar, for any r, to one or more of the ais, i < r is called
More pdf : www.motivationbank.in
5–25 C (CS/IT-Sem-3)
Discrete Structures & Theory of Logic
Answer
Generating function : The generating function for the sequence a0, a1, ...
ak, ... of real numbers is infinite series given by
k
G(x) = a0 + a1x + a2x2 + ...... + akxk + ...... = a x
k0
k
Answer
n
Let G(t) = a t
n 0
n be generating function of sequence {an}.
a n2 tn – 5 a n 1 tn 6 a n tn 5 n
tn
n 0 n 0 n 0 n 0
G(t) – a0 – a1 t G (t) – a0 1
– 5 6 G(t) 1 – 5t
t2 t
Put a0 = 0 and a1 = 2
t2
G(t) – 2t – 5t G(t) + 6t2 G(t) =
1 – 5t
t2
G(t) – 5t G(t) + 6t2 G(t) = + 2t
1 – 5t
t2
G(t) (1 – 5t + 6t2) = + 2t
1 – 5t
t2
(6t2 – 5t + 1) G(t) = + 2t
1 – 5t
t2 2t
G(t) =
(1 – 5t)(3t – 1)(2t – 1) (3t – 1)(2t – 1)
t2 2t
=
(1 – 5t)(1 – 3t)(1 – 2t) (1 – 3t)(1 – 2t)
Let
t2 A B C
=
(1 – 5t)(1 – 3t)(1 – 2t) (1 – 5t) (1 – 3t) (1 – 2t)
More pdf : www.motivationbank.in
5–27 C (CS/IT-Sem-3)
Discrete Structures & Theory of Logic
t2
A = (1 – 5t)
(1 – 5t)(1 – 3t)(1 – 2t) t 1/5
t2
=
(1 – 3t)(1 – 2t) t 1/5
1 / 25 1
= =
(1 – 3 / 5)(1 – 2 / 5) 6
t2
B = (1 – 3t)
(1 – 5t)(1 – 3t)(1 – 2t) t 1/3
t2 1/9
= =
(1 – 5t)(1 – 2t) t 1/3 3 – 5 3 – 2
3 3
1
= –
2
t2
C = (1 – 2t)
(1 – 5t)(1 – 3t)(1 – 2t) t 1/2
t2 1/ 4
= =
(1 – 5t)(1 – 3t) t 1/2 (2 – 5) (2 – 3)
2 2
1
=
3
Again,
2t D E
=
(1 – 3t)(1 – 2t) (1 – 3t) (1 – 2t)
2t
D = (1 – 3t)
(1 – 3t)(1 – 2t) t 1/3
2t 2/3
= = 2
(1 – 2t) t 1/3 (3 – 2)
3
2t
E = (1 – 2t)
(1 – 3t)(1 – 2t) t 1/ 2
2t 2/2
= = –2
(1 – 3t) t 1/ 2 2–3
2
1/ 6 1/ 2 1/3 2 2
G(t) = – –
(1 – 5t) (1 – 3t) (1 – 2t) (1 – 3t) (1 – 2t)
5–28 C (CS/IT-Sem-3) Trees, Graph and Combinatorics
More pdf : www.motivationbank.in
1/6 3/2 5/3
= –
1 – 5t (1 – 3t) 1 – 2t
1 3 5
a n tn = (5t) n
(3t) n
– (2t)n
n 0
6 n 0
2 n 0
3 n 0
1 3 5
an = (5)n (3) n – (2)n
6 2 3
Que 5.25. Solve the recurrence relation by the method of
generating function :
ar – 7 ar–1 + 10ar–2 = 0, r 2. Given a0 = 3 and a1 = 3.
AKTU 2014-15, Marks 10
OR
Solve the recurrence relation using generating function :
an – 7an – 1 + 10an – 2 = 0 with a0 = 3, a1 = 3.
AKTU 2015-16, Marks 10
Answer
ar – 7ar–1 + 10 ar–2 = 0, r 2
Multiply by xr and take sum from 2 to .
ar xr 7 ar –1 xr 10 ar 2 xr 0
r2 r2 r2
3 – 18 x = A (2 x – 1) + B (5 x – 1)
1
put x=
2
5 3
3 – 9 = B 1 – 6 = B B = – 4
2 2
1
put x=
5
18 2 3 3
3– = A 1 A 1 A = 1
5 5 5 5
1 4 4 1
G(x) = =
5 x 1 2x 1 1 2x 1 5x
ar = 4.2r – 5r
Answer
ar+2 – 5 ar+1 + 6 ar = (r + 1)2 = r2 + 2r + 1 ...(5.26.1)
Now the characteristic equation is :
x2 – 5 x + 6 = 0
(x – 3) (x – 2) = 0 x = 3, 2
The homogeneous solution is :
ar(h) = C12r + C2 3r
Let the particular solution be :
ar(p) = A0 + A1r + A2r2
From eq. (5.26.1)
A0 + A1 (r + 2) + A2 (r + 2)2 – 5 {A0 + A1 (r + 1)} + A2 (r + 1)2}
+ 6A0 + 6A1r + 6A2 r2
= r2 +2r+1
(A0 + 2A1 + 4A2 –5A0 – 5A1 – 5A2 + 6A0) + r (A1 + 4A2 – 5A1 – 10A2 + 6A1)
+ r2 ( A2 – 5A2 + 6A2) = r2 + 2r + 1
Comparing both sides, we get,
2A0 – 3A1 – A2 = 1 ...(5.26.2)
2A1 – 6A2 = 2 ...(5.26.3)
2A2 = 1 A2 = 1/2
From eq. (5.26.3), 2A1 – 3 = 2
5
A1 =
2
5–30 C (CS/IT-Sem-3) Trees, Graph and Combinatorics
More pdf : www.motivationbank.in
From eq. (5.26.2)
15 1
2A0 – =1
2 2
9
2A0 – 8 = 1 A0 =
2
9 5 r2
ar(p) = r
2 2 2
9 5 r2
The final solution is, ar = ar(h) + ar(p) = C1 2r + C2 3r + + r
2 2 2
Que 5.27. Solve ar – 6ar – 1 + 8ar – 2 = r.4r, given a0 = 8, and a1 = 1.
Answer
ar – 6ar – 1 + 8ar – 2 = r4r
The characteristic equation is, x2 – 6x + 8 = 0, x2 – 2x – 4x + 8 = 0
(x – 2) (x – 4) = 0, x = 2, 4
The solution of the associated non-homogeneous recurrence relation is,
ar(h) = B1(2)r + B2(4)r ...(5.27.1)
Let particular solution of given equation is, ar(p) = r2(A0 + A1r)4r
Substituting in the given equation, we get
r2(A0 + A1r)4r – 6(r – 1)2 (A0 + A1(r – 1))4r – 1
+ 8(r – 2)2 (A0 + A1(r – 2)4r – 2 = r4r
6
r 2A 0 + A 1r 3 – [(A0r2 – 2A0r + A0) + (A1r3 – A1 – 3A1r2 + 3A1r)2]
4
8
+ 2 [(A0r2 – 4rA0 + 4A0) + (A1r3 – 8A1 – 6A1r\2 + 12A1r)] = r
4
3 3 3 3
rA0 + A1r3 – A r2 + 3A0r – A – A r3 + A
2 0 2 0 2 1 2 1
9 9 1
+ A r2 – A r+ A r2 – 2A0r + 2A0
2 1 2 1 2 0
1
A r3 – 4A1 – 3A1r2 – 6A1r = r
2 1
1 5 3 3
2A0r – A0r2 – A – A + A r2 + A r=r
2 0 2 1 2 1 2 1
Comparing both sides, we get
3
2A0 + A =1 ...(5.27.2)
2 1
A0 + 5A1 = 0 ...(5.27.3)
2 10
Solving equation (5.27.2) and (5.27.3), we get A1 = A0 =
17 17
To find the value of B1 and B2 put r = 0 and r = 1 in equation (5.27.1)
More pdf : www.motivationbank.in
5–31 C (CS/IT-Sem-3)
Discrete Structures & Theory of Logic
r = 0 a0 = B1 + B2 B1 + B2 = 8 ...(5.27.4)
r = 1 a1 = 2B1 + 4B2 2B1 + 4B2 = 1 ...(5.27.5)
31 15
Solving equations (5.27.4) and (5.27.5), we get B1 = B2 =
2 2
Complete solution is, ar = ar(h) + ar(p)
31 r 15 r 10 2 r
ar = 2 4 r 2 r 4
2 2 17 17
Answer
ar + 4ar – 1 + 4ar – 2 = r2
The characteristic equation is,
x2 + 4x + 4 = 0
(x + 2)2 = 0
x = –2, – 2
The homogeneous solution is, a(h) = (A0 + A1r) (– 2)r
The particular solution be, a(p) = (A0 + A1r) r2
Put ar, ar – 1 and ar – 2 from a(p) in the given equation, we get
r2A0 + A1r3 + 4A0(r – 1)2 + 4A1(r – 1)3 + 4A0(r – 2)2 + 4A1(r – 2)3 = r2
A0(r2 + 4r2 – 8r + 4 + 4r2 – 16r + 16) +
A1(r3 + 4r3 – 4 – 12r2 + 12r + 4r3 – 32 – 24r2 + 48r) = r2
A0(9r2 – 24r + 20) + A1(9r3 – 48r2 + 60r – 36) = r2
Comparing the coefficient of same power of r, we get
9A0 – 48A1 = 1 ...(5.28.1)
20A0 – 36A1 = 0 ...(5.28.2)
3 5
Solving equation (5.28.1) and (5.28.2) A0 = A1
53 159
The complete solution is,
3 5 2
ar = ar(p) + ar(h) = (A0 + A1r) (– 2)r + r r
53 159
Que 5.29. Suppose that a valid codeword is an n-digit number in
decimal notation containing an even number of 0’s. Let an denote
the number of valid codewords of length n satisfying the recurrence
relation an = 8an – 1 + 10n – 1 and the initial condition a1 = 9. Use
generating functions to find an explicit formula for an.
AKTU 2018-19, Marks 07
5–32 C (CS/IT-Sem-3) Trees, Graph and Combinatorics
More pdf : www.motivationbank.in
Answer
Let G(x) =
n 0
an xn be the generating function of the sequence a0, a1, a2 ....
we sum both sides of the last equations starting with n = 1. To find that
G(x) – 1 = an x n (8a n –1 x
n
10 n–1 x n )
n 1 n 1
n n –1 n
= 8 a
n 1
n –1 x 10
n 1
x
= 8x an–1 x n–1 x 10 n –1 n –1
x
n 1 n 1
n n
= 8x a x n x 10 xn
n 0 n 0
= 8xG(x) + x/(1 – 10x)
Therefore, we have
G(x) – 1 = 8xG(x) + x/(1 – 10x)
Expanding the right hand side of the equation into partial fractions gives
1 1 1
G(x) =
2 1 8 x 1 10 x
This is equivalent to
1 n n n n
G(x) =
8 x
2 n 0 10 x
n 0
1 n
= (8 10n ) x n
n 0
2
1 n
an = (8 10n )
2
Que 5.30. Define permutation and combination. Also, write
difference between them.
Answer
1. Permutation refers to different ways of arranging a set of object in a
sequential order.
2. The number of permutations of n different things taken r ( n) at a
time is denoted by p(n, r) or nPr.
3. Combination refers to several ways of choosing items from a large set
of object.
More pdf : www.motivationbank.in
Discrete Structures & Theory of Logic 5–33 C (CS/IT-Sem-3)
n! n!
4. nP = nC =
r (n r)! r r !(n r )!
Que 5.31. Suppose that a cookie shop has four different kinds of
cookies. How many different ways can six cookies be chosen ?
AKTU 2016-17, Marks 15
Answer
As the order in which each cookie is chosen does not matter and each kind of
cookies can be chosen as many as 6 times, the number of ways these cookies
can be chosen is the number of 6-combination with repetition allowed from
a set with 4 distinct elements.
The number of ways to choose six cookies in the bakery shop is the number
of 6 combinations of a set with four elements.
C(4 + 6 – 1, 6) = C(9, 6)
Since C(9, 6) = C(9, 3) = (9 · 8 · 7) / (1 · 2 · 3) = 84
Therefore, there are 84 different ways to choose the six cookies.
Answer
i. Recursive algorithm :
A function is called recursively defined if the function refers to itself,
and satisfies the following step :
a. There must be certain arguments for which the function does not
refer to itself, these arguments are called initial values (Base values).
5–34 C (CS/IT-Sem-3) Trees, Graph and Combinatorics
More pdf : www.motivationbank.in
b. These base values are used to define the other values of the function
by using the function recursively.
Example : ar = 3 ar–1, r 1, a0 = 1
then a1 = 3a0 = 3
a2 = 3a1 = 3 (3a0) = 32 a0 = 32
and so on.
ar = 3r, r 0
ii. Pigeonhole principle :
The pigeonhole principle is sometime useful in counting methods.
If n pigeons are assigned to m pigeonholes then at least one pigeonhole
contains two or more pigeons (m < n).
Proof :
1. Let m pigeonholes be numbered with the numbers 1 through m.
2. Beginning with the pigeon 1, each pigeon is assigned in order to the
pigeonholes with the same number.
3. Since m < n i.e., the number of pigeonhole is less than the number of
pigeons, n-m pigeons are left without having assigned a pigeonhole.
4. Thus, at least one pigeonhole will be assigned to a more than one pigeon.
5. We note that the pigeonhole principle tells us nothing about how to
locate the pigeonhole that contains two or more pigeons.
6. It only asserts the existence of a pigeon hole containing two or more
pigeons.
7. To apply the principle one has to decide which objects will play the role
of pigeon and which objects will play the role of pigeonholes.
Que 5.33. Find the number of integers between 1 and 250 that are
divisible by any of the integers 2, 3, 5, and 7.
Answer
1, 2, 3, -------------- 250
Number of integers between 1 and 250 that are divisible by 2 :
Quotient of last number 2 – quotient of first number 2
(250 2 ) – (1 2) = 125 – 0 = 125
Number of integers between 1 and 250 that are divisible by 3
(250 3) – (1 3) = 83 – 0 = 83
Number of integers between 1 and 250 that are divisible by 5
(250 5) – (1 5) = 50 – 0 = 50
Number of integers between 1 and 250 that are divisible by 7
(250 7) – (1 7) = 35 – 0 = 5
Total number of integers divisible by only 2, 3, 5, 7, individually are
125 + 83 + 50 + 35 = 293
Number of integers divisible by (2 and 3) = 41
More pdf : www.motivationbank.in
5–35 C (CS/IT-Sem-3)
Discrete Structures & Theory of Logic
Que 5.34. How many different rooms are needed to assign 500
classes, if there are 45 different time periods during in the university
time table that are available ?
Answer
Using pigeonhole principle :
n 1 500 1
Here n = 500, m = 45 = 1 45 1
m
At least 12 rooms are needed.
Answer
Let S be the set of students who have taken a course in Spanish, F be the set
of students who have taken a course in French, and R be the set of students
who have taken a course in Russian. Then, we have
|S| = 1232, |F| = 879, |R| = 114, |S F| = 103, |S R| = 23,
|S R| = 14, and |SF R| = 23.
Using the equation
|SF R| = |S|+ |F|+ |R| – |S F| – |S R| – |S R| + |S
F R|,
5–36 C (CS/IT-Sem-3) Trees, Graph and Combinatorics
More pdf : www.motivationbank.in
2092 = 1232 + 879 + 114 – 103 – 23 – 14 +|SF R|,
|SF R| = 7.
|S F| = 103
|S F R| = ?
|S| = 1232
|F| = 879
|S R| = 23
|F R| = 14
Q. 6.
a. Prove that a connected graph G is Euler graph if and only if
every vertex of G is of even degree.
b. Which of the following simple graph have a Hamiltonian
circuit or, if not a Hamiltonian path ?
a b a b a b g
c d c f
e d c e
d
G1 G2 G3
Fig. 1.
Ans. Refer Q. 5.17.
Discrete Structures & Theory of Logic SQ–1 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
1.11. If the function f : R R defined by f(x) = x2, find f–1 (4) and
f–1(– 4).
Ans. f–1(4) = {x R : f (x) = 4}
= {x R : x2 = 4}
= {x R : x = ± 2} = {–2, 2}
f–1(– 4) = {x R : f (x) = – 4}
= {x R : x2 = – 4}
= {x R : x = 2 1 } = since 2 1
are imaginary numbers
1.14. Define multiset and power set. Determine the power set
A = {1, 2}. AKTU 2015-16, Marks 02
Ans. Multiset : Multisets are sets where an element can occur as a
member more than once.
For example : A = { p, p, p, q, q, q, r, r, r, r}
B = { p, p, q, q, q, r}
are multisets.
Power set : A power set is a set of all subsets of the set.
The power set of A = {1, 2} is {{}, {1}, {2}}.
Discrete Structures & Theory of Logic SQ–7 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
2 Algebraic Structures
(2 Marks Questions)
= b–1 * e * b
= b–1 * b = e
Therefore (a * b) – 1 = b – 1 * a – 1 for any a, b G
2.5. Define ring and give an example of a ring with zero divisors.
AKTU 2016-17, Marks 02
OR
SQ–8 C (CS/IT-Sem-3) 2 Marks Questions
More pdf : www.motivationbank.in
Define ring and field. AKTU 2018-19, Marks 02
OR
Define rings and write its properties.
AKTU 2017-18, Marks 02
Ans. Ring : A non-empty set R is a ring if it is equipped with two binary
operations called addition and multiplication and denoted by '+'
and '.' respectively i.e., for all a, b R we have a + b R and a.b R
and it satisfies the following properties :
i. Addition is associative i.e.,
(a + b) + c = a + (b + c) a, b, c R
ii. Addition is commutative i.e.,
a + b = b + a a, b R
iii. There exists an element 0 R such that
0 + a = a = a + 0, a R
iv. To each element a in R there exists an element – a in R such that
a + (– a) = 0
v. Multiplication is associative i.e.,
a.(b.c) = (a.b).c, a b, c R
vi. Multiplication is distributive with respect to addition i.e., for all
a, b, c R,
Example of ring with zero divisors : R = {a set of 2 × 2
matrices}.
Field : A ring R with at least two elements is called a field if it has
following properties :
i. R is commutative
ii. R has unity
iii. R is such that each non-zero element possesses multiplicative
inverse.
For example : The rings of real numbers and complex numbers
are also fields.
2.10. Prove that left inverse of an element is also its right inverse
i.e., a–1 * a = e = a * a–1
Ans. Now a–1 * (a * a–1) = (a–1 * a)* a–1 (Associativity)
= e* a–1
= a–1 * e
Thus, a * (a * a ) = a–1 * e
–1 –1
a * a–1= e
Thus, the left inverse of an element in a group is also its right
inverse.
SQ–10 C (CS/IT-Sem-3) 2 Marks Questions
More pdf : www.motivationbank.in
3.8. Determine
i. All maximal and minimal elements
ii. Greatest and least element
iii. Upper and lower bounds of ‘a’ and ‘b’, ‘c’ and ‘d’
c d
e
a b
Fig. 3.8.1.
Ans.
i. Maximal elements = c, d, Minimal element = a, b
ii. Greatest and least elements do not exist.
iii. Upper bound for a,b are e, f, c, d.
Upper bound for c,d are does not exist.
Lower bound for a,b are does not exist.
Lower bound for c,d are f, e, a, b.
SQ–14 C (CS/IT-Sem-3) 2 Marks Questions
More pdf : www.motivationbank.in
4 Propositional Logic
and Predicate Logic
(2 Marks Questions)
SQ–18 C (CS/IT-Sem-3) 2 Marks Questions
More pdf : www.motivationbank.in
C
B
D E F
Fig. 5.3.1.
Preorder (NLR) : ABDECF
Postorder (LRN) : DEBFCA
Inorder (LNR) : DBEAFC
5.6. Let G be a graph with ten vertices. If four vertices has degree
four and six vertices has degree five, then find the number
of edges of G. AKTU 2016-17, Marks 02
Ans. We know that
deg (v ) = 2e
i
i
4 + 4 + 4 + 4 + 5 + 5 + 5 + 5 + 5 + 5 = 2e
16 + 30 = 2e
2e = 46
e = 23
5.7. State the applications of binary search tree.
AKTU 2016-17, Marks 02
Ans. One of the most common applications is to efficiently store data in
sorted form in order to access and search stored elements quickly.
For example, std :: map or std :: set in C++ Standard Library.
Binary tree as data structure is useful for various implementations
of expression parsers and expression solvers.
5.8. Define multigraph. Explain with example in brief.
AKTU 2016-17, Marks 02
Ans. A multigraphs G(V, E) consists of a set of vertices V and a set of
edges E such that edge set E may contain multiple edges and self
loops.
Example :
a. Undirected multigraph :
v1 e2 v2
e6
e5
e1
e3
e4
v4 v3
Fig. 5.8.1.
SQ–20 C (CS/IT-Sem-3) 2 Marks Questions
More pdf : www.motivationbank.in
b. Directed multigraph :
e7
v1 e3 v2
e1 e2 e4 e5
v4 e6 v3
Fig. 5.8.2.
v1 v3
Fig. 5.14.1.
5.18. How many bit strings of length eight either start with a ‘1’
bit or end with the two bit ‘00’ ?
AKTU 2018-19, Marks 02
Ans.
1. Number of bit strings of length eight that start with a 1 bit :
27 = 128.
2. Number of bit strings of length eight that end with bits 00 : 26 = 64.
Discrete Structures & Theory of Logic SQ–23 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
3. Number of bit strings of length eight 25 = 32 that start with a 1 bit
and end with bits 00 : 25 = 32
Hence, the number is 128 + 64 – 32 = 160.
Discrete Structures & Theory of Logic SP–1 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
B. Tech.
(SEM. III) ODD SEMESTER
THEORY EXAMINATION, 2014-15
DISCRETE STRUCTURE AND
GRAPH THEORY
Time : 3 Hours Max. Marks : 100
b. Prove for any two sets A and B that, (A B)' = A' B'.
1 2
3 4
Fig. 1.
i. Verify that (A, R) is a poset and find its Hasse diagram.
ii. Is this a lattice ?
iii. How many more edges are needed in the Fig. 1 to extend (A,
R) to a total order ?
iv. What are the maximal and minimal elements ?
a c
f d
e
Fig. 2.
b. “If the labour market is perfect then the wages of all persons
in a particular employment will be equal. But it is always
the case that wages for such persons are not equal
therefore the labour market is not perfect”. Test the validity
of this argument using truth table.
SP–4 C (CS/IT-Sem-3) Solved Paper (2014-15)
More pdf : www.motivationbank.in
SOLUTION OF PAPER (2014-15)
b. Prove for any two sets A and B that, (A B)' = A' B'.
Ans.
Let x (A B)
xAB
Discrete Structures & Theory of Logic SP–5 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
x A and x B
x A and x B
x A B
(A B) A B ...(1)
Now, let x A B
x A and x B
x A and x B
x (A B)
x (A B)
(AB) (A B) ...(2)
From eq. (1) and (2), (A B) = A B
1 2
3 4
Fig. 1.
i. Verify that (A, R) is a poset and find its Hasse diagram.
ii. Is this a lattice ?
iii. How many more edges are needed in the Fig. 1 to extend (A,
R) to a total order ?
iv. What are the maximal and minimal elements ?
Ans.
i. The relation R corresponding to the given directed graph is,
R = {(1, 1), (2, 2), (3, 3), (4, 4), (3, 1), (3, 4), (1, 4), (3, 2)}
R is a partial order relation if it is reflexive, antisymmetric and
transitive.
Reflexive : Since aRa, a A . Hence, it is reflexive.
Antisymmetric : Since aRb and bRa then we get a = b otherwise
aRb or bRa.
Hence, it is antisymmetric.
Transitive: For every aRb and bRc we get aRc. Hence, it is
transitive.
Therefore, we can say that (A, R) is poset. Its Hasse diagram is :
1
2
4
3
Fig. 2.
Discrete Structures & Theory of Logic SP–11 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
ii. Since there is no lub of 1 and 2 and same for 2 and 4. The given
poset is not a lattice.
1 2 3 4
1 1 1 1
2 2 2
3 1 2 3 1
4 1 1 4
iii. Only one edge (4, 2) is included to make it total order.
iv. Maximals are {1, 2} and minimals are {3, 4}.
a c
f d
e
Fig. 3.
Ans.
i. In a given lattice, greatest element is b and least element is e. An
element x in lattice is called a complement of element y if
y x = b and y x = e
For element e,
eb=b , e b=e
So, complement of e is b
ii. Proof :
For bounded complemented lattice, every element in lattice has a
complement and lattice is bounded. Since, given lattice have greatest
and least element. So, the given lattice is bounded.
Now the complement of all elements is given below :
Complement of a = {c, d}
Complement of b = {e}
Complement of c = {a, f}
Complement of d = {a, f}
Complement of e = {b}
Complement of f = {c, d}
Since, complement of every element exists and lattice is bounded.
So, the given lattice is bounded complemented lattice.
Hence proved.
SP–12 C (CS/IT-Sem-3) Solved Paper (2014-15)
More pdf : www.motivationbank.in
c. Consider the Boolean function
a. f(x1, x2, x3, x4) = x1 + (x2. (x'1 + x4) + x3. (x'2 + x'4))
i. Simplify f algebraically.
ii. Draw the logic circuit of the f and the reduction of the f.
b. Write the expressions E1 = (x + xy) + (x/y) and E2 = x +
((xy + y)/y), into
i. Prefix notation ii. Postfix notation
Ans.
a. i. f(x1, x2, x3, x4) = x1 + (x2.(x1 + x4) + x3.(x2+ x4)
= x1 + x2.x1 + x2.x4 + x3.x2 + x3.x4
= x1 + x2 + x2.x4 + x3.x2 + x3.x4
= x1 + x2.(1 + x4) + x3.x2 + x3.x4
= x1 + x2 + x3.x2 + x3.x4
= x1 + x2 + x3 + x3.x4
= x1 + x2 + x3.(1 + x4)
= x1 + x2 + x3
ii. Logic circuit :
x1 x1 + x2 + x3
x2
x3
Fig. 4.
Reduction of f :
f (x1, x2, x3, x4) = x1 + (x2.(x1 + x4) + x3.(x2 + x4)
= x1 + (x2.x1 + x2.x4) + (x3.x2 + x3.x4)
= x1 + x2.x1 + x2.x4 + x3.x2 + x3.x4
b. E1 = (x + x * y) + (x/y)
Binary tree is :
+ /
x * x y
x y
Fig. 5.
Prefix : ++ x * x y / xy
Postfix : xx y * + xy / +
E2 = x + ((x * y + y)/y)
Discrete Structures & Theory of Logic SP–13 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
Binary tree is :
+
/
x
y
+
* y
y
x
Fig. 6.
Prefix : + x / + * x y y y
Postfix : x x y * y + y / +
Example :
p : Ram will go to Delhi.
q : Ram will go to Calcutta.
p q : Ram will go to Delhi or Calcutta.
iii. Conditional : If p and q are propositions. The compound proposition
if p then q denoted by p q or p q and is called conditional
proposition or implication. It is read as “If p then q” and its truth
table is,
p q pq
T T T
T F F
F T T
F F T
Example :
p : Ram works hard.
q : He will get good marks.
p q : If Ram works hard then he will get good marks.
For converse and contrapositive :
Let p : It rains.
q : The crops will grow.
iv. Converse : If p q is an implication then its converse is given by
q p states that S : If the crops grow, then there has been rain.
v. Contrapositive : If p q is an implication then its contrapositive
is given by q p states that,
t : If the crops do not grow then there has been no rain.
Inverse :
If p q is implication the inverse of p q is ~ p ~ q.
Consider the statement
p : It rains.
q : The crops will grow
The implication p q states that,
r : If it rains then the crops will grow.
The inverse of the implication p q, namely ~ p ~ q states that.
u : If it does not rain then the crops will not grow.
SP–16 C (CS/IT-Sem-3) Solved Paper (2014-15)
More pdf : www.motivationbank.in
5. Attempt any two parts : (10 × 2 = 20)
a. Solve the recurrence relation by the method of generating
function
ar – 7 ar – 1 + 10ar – 2 = 0, r 2
Given a0 = 3 and a1 = 3.
Ans. ar – 7ar – 1 + 10 ar – 2 = 0, r 2
Multiply by xr and take sum from 2 to .
ar xr 7 ar –1 xr 10 ar 2 xr 0
r2 r2 r2
(a2 x2 + a3 x3 + a4 x4 + ....) – 7 (a1 x2 + a2 x3 + ....)
+ 10 (a0 x2 + a1 x3 + ....) = 0
We know that
G(x) = ar xr a0 a1 x ....
r0
G(x) – a0 – a1 x – 7 x (G(x) – a0) + 10 x2 G(x) = 0
G(x) [1 – 7 x + 10 x2] = a0 + a1 x – 7 a0 x
= 3 + 3x – 21 x = 3 – 18 x
3 18 x 3 18 x
G(x) =
10 x 2 7 x 1 10 x 2 5 x 2 x 1
3 18 x 3 18 x
=
5 x (2 x 1) 1 (2 x 1) (5 x – 1)(2 x 1)
Now,
3 18 x A B
=
(5 x 1) (2 x 1) 5 x 1 2 x 1
3 – 18 x = A (2 x – 1) + B (5 x – 1)
1
put x=
2
5 3
3 – 9 = B 1 – 6 = B B = – 4
2 2
1
put x=
5
18 2 3 3
3– = A 1 A 1 A = 1
5 5 5 5
1 4 4 1
G(x) = =
5 x 1 2x 1 1 2x 1 5x
ar = 4.2r – 5r
(a) (b ) (c )
Fig. 7.
Isomorphism of graph : Two graphs are isomorphic to each
other if :
i. Both have same number of vertices and edges.
ii. Degree sequence of both graphs are same (degree sequence is the
sequence of degrees of the vertices of a graph arranged in non-
increasing order).
Example :
Fig. 8.
ii. Eulerian path : A path of graph G which includes each edge of G
exactly once is called Eulerian path.
Eulerian circuit : A circuit of graph G which include each edge of
G exactly once.
Eulerain graph : A graph containing an Eulerian circuit is called
Eulerian graph.
For example : Graphs given below are Eulerian graphs.
V1 V3 A B
V2
V5 V4 D C
Fig. 9.
Hamiltonian graph : A Hamiltonian circuit in a graph G is a
closed path that visit every vertex in G exactly once except the end
vertices. A graph G is called Hamiltonian graph if it contains a
Hamiltonian circuit.
For example : Consider graphs given below :
D C D C
F
E
A B A B
(a) (b )
Fig. 10.
Graph given is Fig. 10(a) is a Hamiltonian graph since it contains a
Hamiltonian circuit A – B – C – D – A while graph in Fig 10(b) is not
a Hamiltonian graph.
Hamiltonian path : The path obtained by removing any one edge
from a Hamiltonian circuit is called Hamiltonian path. Hamiltonian
path is subgraph of Hamiltonian circuit. But converse is not true.
Discrete Structures & Theory of Logic SP–19 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
The length of Hamiltonian path in a connected graph of n vertices
is n – 1 if it exists.
iii. Planar graph :
A graph G is said to be planar if there exists some geometric
representation of G which can be drawn on a plane such that no
two of its edges intersect except only at the common vertex.
i. A graph is said a planar graph, if it cannot be drawn on a plane
without a crossover between its edges crossing.
ii. The graphs shown in Fig. 11(a) and (b) are planar graphs.
(a) (b )
Fig. 11. Some planar graph.
Complete bipartite graph : The complete bipartite graph on m
and n vertices, denoted Km, n is the graph, whose vertex set is
partitioned into sets V1 with m vertices and V2 with n vertices in
which there is an edge between each pair of vertices 1 and 2
where 1 is in V1 and 2 is in V2. The complete bipartite graphs
K2,3, K2,4, K 3,3, K3,5, and K2,6
K3,5 K2,6
Fig. 12. Some complete bipartite graphs.
Discrete Structures & Theory of Logic SP–1 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
B.Tech.
(SEM. III) ODD SEMESTER
THEORY EXAMINATION, 2015-16
DISCRETE STRUCTURE AND
GRAPH THEORY
Time : 3 Hours Max. Marks : 100
Note : Attempt all parts. All parts carry equal marks. Write answer of
each part in short. (2 × 10 = 20)
SECTION – A
SP–4 C (CS/IT-Sem-3) Solved Paper (2015-16)
More pdf : www.motivationbank.in
SOLUTION OF PAPER (2015-16)
Note : Attempt all parts. All parts carry equal marks. Write answer of
each part in short. (2 × 10 = 20)
SECTION – A
SECTION – B
Fig. 1.
Greatest element is {a, b, c} and maximal element is {a, b, c}.
The least element is and minimal element is .
CD AB
ABCD 1
ABCD 1
ABCD 1
ABCD 1
Fig. 2.
On simplification by K-map, we get AB corresponding to all the
four one’s.
1
1 2 3 4 5 1 2 3 4 5
x=
2 3 1 5 4 1 2 3 5 4
2 3 1 5 4 1 2 3 4 5
=
1 2 3 4 5 1 2 3 5 4
1 2 3 4 5 1 2 3 4 5
=
3 1 2 5 4 1 2 3 5 4
1 2 3 4 5
x=
3 1 2 4 5
4 0 1 2 3 4 0 1 2 3
0 0 1 2 3 0 0 0 0 0
1 1 2 3 0 1 0 1 2 3
2 2 3 0 1 2 0 2 0 2
3 3 0 1 2 3 0 3 2 1
We find from these tables :
i. All the entries in both the tables belong to Z4. Hence, Z4 is closed
with respect to both operations.
ii. Commutative law : The entries of 1st, 2nd, 3rd, 4th rows are identical
with the corresponding elements of the 1st, 2nd, 3rd, 4th columns
respectively in both the tables. Hence, Z4 is commutative with respect
to both operations.
iii. Associative law : The associative law for addition and multiplication
a +4 (b +4 c) = (a +4 b) +4 c for all a, b, c Z4
a ×4 (b ×4 c) = (a ×4 b) ×4 c, for all a, b, c Z4
can easily be verified.
iv. Existence of identity : 0 is the additive identity and 1 is
multiplicative identity for Z4.
v. Existence of inverse : The additive inverses of 0, 1, 2, 3 are 0, 3, 2,
1 respectively.
Multiplicative inverse of non-zero element 1, 2, 3 are 1, 2, 3
respectively.
vi. Distributive law : Multiplication is distributive over addition i.e.,
a ×4(b +4c) = a ×4b + a ×4c
(b +4c) ×4a = b ×4a + c ×4a
For, a ×4(b +4c) = a ×4(b + c) for b +4 c = b + c (mod 4)
= least positive remainder when a × (b + c) is
divided by 4
Discrete Structures & Theory of Logic SP–13 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
= least positive remainder when ab + ac is divided by 4
= ab +4ac
= a ×4b +4a ×4c
For a ×4b = a × b (mod 4)
Since (Z4, +4) is an abelian group, (Z4, ×4) is a semigroup and the
operation is distributive over addition. The (Z4, +4, ×4) is a ring. Now
(Z4, ×4 ) is commutative with respect to ×4 . Therefore, it is a
commutative ring.
SECTION – C
Fig. 3.
Greatest element is {a, b, c} and maximal element is {a, b, c}.
The least element is and minimal element is .
X9 1 2 4 5 7 8
1 2 3 4 5 7 8
2 2 4 8 1 5 7
4 4 8 7 2 1 5
5 5 1 2 7 8 4
7 7 5 1 8 4 2
8 8 7 5 4 2 1
1 is identity element of group G
21 = 2 2 mod 9
22 = 4 4 mod 9
23 = 8 8 mod 9
24 = 16 7 mod 9
25 = 32 5 mod 9
26 = 64 1 mod 9
Therefore, 2 is generator of G. Hence G is cyclic.
Similarly, 5 is also generator of G.
Hence there are two generators 2 and 5.
Discrete Structures & Theory of Logic SP–1 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
B.Tech.
(SEM. III) ODD SEMESTER
THEORY EXAMINATION, 2016-17
DISCRETE STRUCTURES AND
GRAPH THEORY
Section-A
Note : Attempt all parts. All parts carry equal marks. Write answer of
each part in short. (2 × 10 = 20)
Note : Attempt any five questions from this section. (10 × 5 = 50)
1 1 1 n
6. Prove by induction : + + ... + = .
1.2 2.3 n ( n + 1) (n + 1)
Section-C
Note : Attempt any two questions from this section. (15 × 2 = 30)
10. a. Prove that a connected graph G is Euler graph if and only if
every vertex of G is of even degree.
b. Which of the following simple graph have a Hamiltonian
circuit or, if not a Hamiltonian path ?
Discrete Structures & Theory of Logic SP–3 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
a b a b a b g
e c d c f
d c e
d
G1 G2 G3
Fig. 1.
Fig. 2.
SP–4 C (CS/IT-Sem-3) Solved Paper (2016-17)
More pdf : www.motivationbank.in
SOLUTION OF PAPER (2016-17)
Section-A
Note : Attempt all parts. All parts carry equal marks. Write answer of
each part in short. (2 × 10 = 20)
v1 e2 v2
e6
e5
e1
e3
e4
v4 v3
Fig. 1.
Discrete Structures & Theory of Logic SP–7 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
b. Directed multigraph :
e7
v1 e3 v2
e1 e2 e4 e5
v4 e6 v3
Fig. 2.
k 2
(ni 1) = n + k – 2nk
2 2
i 1
k k
or (n i 1)2 2 (ni 1)(n j 1) = n2 + k2 – 2nk
i 1 i 1 j 1
i j
k
[ ni – 1 0, nj – 1 0]
k
2
or (n i 1) n2 + k2 – 2nk
i 1
k k k
2
or n 1 2 n
i i n2 + k2 – 2nk
i 1 i 1 i 1
k
2
or n i k 2n n2 + k2 – 2nk
i 1
k
2
or n i n n2 + k2 – 2nk – k + n
i 1
SP–10 C (CS/IT-Sem-3) Solved Paper (2016-17)
More pdf : www.motivationbank.in
= n(n – k + 1) – k (n – k + 1)
= (n – k)(n – k + 1) ...(1)
We know that the maximum number of edges in the ith component
of
ni (ni 1)
ni
G= C2 =
2
Therefore, the maximum number of edges in G is :
1 1 1
2
ni (ni 1) = 2 ni2 ni = 2 ni2 n
1
(n – k)(n – k + 1) by using eq. (1)
2
1 1 1 n
6. Prove by induction : + + ... + = .
1.2 2.3 n ( n + 1) (n + 1)
Ans. Let the given statement be denoted by S(n).
1. Inductive base : For n = 1
1 1 1
=
1.2 1 1 2
Hence S (1) is true.
2. Inductive hypothesis : Assume that S (k) is true i.e.,
1 1 1 k
..... =
1.2 2.3 k(k 1) k 1
3. Inductive step : We wish to show that the statement is true for
n = k + 1 i.e.,
1 1 1 k1
..... =
1.2 2.3 (k 1)(k 2) k2
1 1 1 1
Now, .....
1.2 2.3 k(k 1) ( k 1)(k 2)
k 1 k2 2k 1
=
k 1 ( k 1)(k 2) ( k 1)(k 2)
k1
=
k2
Thus, S(k + 1) is true whenever S(k) is true. By principle of
mathematical induction, S(n) is true for all positive integer n.
an 2 t n – 5 an 1 t n 6 an t n 5 n
tn
n 0 n 0 n 0 n 0
G(t) – a0 – a1 t G (t) – a0 1
– 5 6 G(t) 1 – 5t
t2 t
Put a0 = 0 and a1 = 2
t2
G(t) – 2t – 5t G(t) + 6t2 G(t) =
1 – 5t
t2
G(t) – 5t G(t) + 6t2 G(t) = + 2t
1 – 5t
t2
G(t) (1 – 5t + 6t2) = + 2t
1 – 5t
t2
(6t2 – 5t + 1) G(t) = + 2t
1 – 5t
t2 2t
G(t) =
(1 – 5t)(3t – 1)(2t – 1) (3t – 1)(2t – 1)
t2 2t
=
(1 – 5t)(1 – 3t)(1 – 2t) (1 – 3t)(1 – 2t)
Let
t2 A B C
=
(1 – 5t)(1 – 3t)(1 – 2t) (1 – 5t) (1 – 3t) (1 – 2t)
t2
A = (1 – 5t)
(1 – 5t)(1 – 3t)(1 – 2t) t 1/5
t2
=
(1 – 3t)(1 – 2t) t 1/5
1 / 25 1
= =
(1 – 3 / 5)(1 – 2 / 5) 6
t2
B = (1 – 3t)
(1 – 5t)(1 – 3t)(1 – 2t) t 1/3
t2 1/9
= =
(1 – 5t)(1 – 2t) t 1/3 3 – 5 3 – 2
3 3
1
= –
2
SP–12 C (CS/IT-Sem-3) Solved Paper (2016-17)
More pdf : www.motivationbank.in
t2
C = (1 – 2t)
(1 – 5t)(1 – 3t)(1 – 2t) t 1/2
t2 1/ 4
= =
(1 – 5t)(1 – 3t) t 1/2 (2 – 5) (2 – 3)
2 2
1
=
3
Again,
2t D E
=
(1 – 3t)(1 – 2t) (1 – 3t) (1 – 2t)
2t
D = (1 – 3t)
(1 – 3t)(1 – 2t) t 1/3
2t 2/3
= = 2
(1 – 2t) t 1/3 (3 – 2)
3
2t
E = (1 – 2t)
(1 – 3t)(1 – 2t) t 1/ 2
2t 2/2
= = –2
(1 – 3t) t 1/ 2 2–3
2
1/ 6 1/ 2 1/3 2 2
G(t) = – –
(1 – 5t) (1 – 3t) (1 – 2t) (1 – 3t) (1 – 2t)
1/6 3/2 5/3
= –
1 – 5t (1 – 3t) 1 – 2t
1 3 5
an t n = (5t)n (3t) n – (2t)n
n 0
6 n 0
2 n 0
3 n 0
1 n 3 n 5 n
an = (5) (3) – (2)
6 2 3
c d c f
e d c e
d
G1 G2 G3
Fig. 4.
Ans.
a.
1. First of all we shall prove that if a non-empty connected graph is
Eulerian then it has no vertices of odd degree.
2. Let G be Eulerian.
3. Then G has an Eulerian trail which begins and ends at u.
4. If we travel along the trail then each time we visit a vertex. We use
two edges, one in and one out.
5. This is also true for the start vertex because we also end there.
6. Since an Eulerian trail uses every edge once, the degree of each
vertex must be a multiple of two and hence there are no vertices of
odd degree.
7. Now we shall prove that if a non-empty connected graph has no
vertices of odd degree then it is Eulerian.
8. Let every vertex of G have even degree.
9. We will now use a proof by mathematical induction on |E(G)|, the
number of edges of G.
Discrete Structures & Theory of Logic SP–15 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
Basis of induction :
Let |E(G)| = 0, then G is the graph K1, and G is Eulerian.
Inductive step :
1. Let P(n) be the statement that all connected graphs on n edges of
even degree are Eulerian.
2. Assume P(n) is true for all n < |E(G)|.
3. Since each vertex has degree at least two, G contains a cycle C.
4. Delete the edges of the cycle C from G.
5. The resulting graph, G say, may not be connected.
6. However, each of its components will be connected, and will have
fewer than |E(G)| edges.
7. Also, all vertices of each component will be of even degree, because
the removal of the cycle either leaves the degree of a vertex
unchanged, or reduces it by two.
8. By the induction assumption, each component of G is therefore
Eulerian.
9. To show that G has an Eulerian trail, we start the trail at a vertex,
u say, of the cycle C and traverse the cycle until we meet a vertex,
c1 say, of one of the components of G .
10. We then traverse that component’s Eulerian trail, finally returning
to the cycle C at the same vertex, c1.
11. We then continue along the cycle C, traversing each component of
G as it meets the cycle.
12. Eventually, this process traverses all the edges of G and arrives
back at u, thus producing an Eulerian trail for G.
13. Thus, G is Eulerian by the principle of mathematical induction.
b. G1 : The graph G1 shown in Fig. 4 contains Hamiltonian circuit, i.e.,
a – b – c – d – e – a and also a Hamiltonian path, i.e., abcde.
G2 : The graph G2 shown in Fig. 4 does not contain Hamiltonian
circuit since every cycle containing every vertex must contain the
edge e twice. But the graph does have a Hamiltonian path a – b – c
– d.
G3 : The graph G3 shown in Fig. 4 neither have Hamiltonian circuit
nor have Hamiltonian path because any traversal does not cover all
the vertices.
Fig. 5.
SP–16 C (CS/IT-Sem-3) Solved Paper (2016-17)
More pdf : www.motivationbank.in
Ans.
A ABC
B
C ABC + A(B + C)
A.(B + C)
B
B + C
C
Fig. 6.
Discrete Structures & Theory of Logic SP–1 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
B.Tech.
(SEM. III) ODD SEMESTER
THEORY EXAMINATION, 2017-18
DISCRETE STRUCTURES &
THEORY OF LOGIC
Time : 3 Hours Max. Marks : 70
Note : 1. Attempt all Sections. If require any missing data; then choose
suitably.
2. Any special paper specific instructions.
SECTION – A
SECTION-B
c. For any positive integer D36, then find whether (D36, ‘|’) is
lattice or not ?
SP–2 C (CS/IT-Sem-3) Solved Paper (2017-18)
More pdf : www.motivationbank.in
d. Let X = {1, 2, 3 ...... 7} and R = {(x, y)|(x – y) is divisible by 3}. Is
R equivalence relation. Draw the digraph of R.
Note : 1. Attempt all Sections. If require any missing data; then choose
suitably.
2. Any special paper specific instructions.
SECTION – A
SECTION-B
K1 K2 K3 K4 K5
Fig. 2.
n(n – 1) n
Kn has exactly = C2 edges
2
SP–6 C (CS/IT-Sem-3) Solved Paper (2017-18)
More pdf : www.motivationbank.in
iii. Number of edge in K7 : Since, Kn is complete graph with n vertices.
7(7 1) 7 6
Number of edge in K7 = = 21
2 2
Number of edge in K3, 6 :
Since, Kn, m is a complete bipartite graph with n V1 and m V2
Number of edge in K3, 6 = 3 × 6 = 18
iv. Planar graph :
A graph G is said to be planar if there exists some geometric
representation of G which can be drawn on a plane such that no
two of its edges intersect except only at the common vertex.
i. A graph is said a planar graph, if it cannot be drawn on a plane
without a crossover between its edges crossing.
ii. The graphs shown in Fig. 3(a) and (b) are planar graphs.
(a) (b )
Fig. 3. Some planar graph.
c. For any positive integer D36, then find whether (D36, ‘|’) is
lattice or not ?
Ans. D36 = Divisor of 36 = {1, 2, 3, 4, 6, 9, 12, 18, 36}
Hasse diagram :
(1 3) = {3, 6}, (1 2) = {2, 4}, (2 6) = {6, 18}, (9 4) = {}
36
12 12
6
4 9
2 3
1
Since, 9 4 = {}
So, D36 is not a lattice.
1 3
2
4 7 6
5
Fig. 4. Diagraph of R.
1 1
F = x z yz
SECTION-C
1 2 3 4 5 0
2 3 4 5 0 1
3 4 5 0 1 2
4 5 0 1 2 3
5 0 1 2 3 4
Since, 1 +6 5 = 0 but 0 S i.e., S is not closed under addition modulo 6.
So, S is not a group.
Multiplication modulo 6 (*6) :
Composition table of S = {1, 2, 3, 4, 5} under operation *6 is given as
*6 1 2 3 4 5
1 1 2 3 4 5
2 2 4 0 2 4
3 3 0 3 0 3
4 4 2 0 4 2
5 5 4 3 2 1
Since, 2 *6 3 = 0 but 0 S i.e., S is not closed under multiplication
modulo 6.
So, S is not a group.
a b c
0
Fig. 5.
Modular lattice :
0 a i.e., taking b = 0
b (a c) = 0 0 = 0, a (b c) = a c = 0
Distributive lattice :
For a set S, the lattice P(S) is distributive, since union and intersection
each satisfy the distributive property.
Discrete Structures & Theory of Logic SP–11 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
Bounded lattice : Since, the given lattice has 1 as greatest and 0
as least element so it is bounded lattice.
a b c
0
Fig. 6.
H E
V5 V4 D C
Fig. 7.
Eulerian path : A path of graph G which includes each edge of G
exactly once is called Eulerian path.
Eulerian circuit : A circuit of graph G which include each edge of
G exactly once.
The existence of Eulerian paths or Eulerian circuits in a graph is
related to the degree of vertices.
a. Adjacency matrix :
i. Representation of undirected graph :
The adjacency matrix of a graph G with n vertices and no parallel
edges is a n × n matrix A = [aij] whose elements are given by
aij = 1, if there is an edge between ith and jth vertices
= 0, if there is no edge between them
ii. Representation of directed graph :
The adjacency matrix of a digraph D, with n vertices is the matrix
A = [aij]n×n in which
aij = 1 if arc (vi, vj) is in D
= 0 otherwise
For example :
V1 V4
V2 V3
Fig. 8.
SP–14 C (CS/IT-Sem-3) Solved Paper (2017-18)
More pdf : www.motivationbank.in
v1 v2 v3 v4
v1 0 1 1 1
0 1 0
A = v2 1
v3 1 1 0 1
v4 1 0 1 0
Discrete Structures & Theory of Logic SP–1 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
B.Tech.
(SEM. III) ODD SEMESTER
THEORY EXAMINATION, 2018-19
DISCRETE STRUCTURES AND
THEORY OF LOGIC
Time : 3 Hours Max. Marks : 70
Note : 1. Attempt all Sections. If require any missing data; then choose
suitably.
2. Any special paper specific instructions.
SECTION – A
e. How many bit strings of length eight either start with a ‘1’
bit or end with the two bit ‘00’ ?
SECTION-B
b. Show that the premises “It is not sunny this afternoon and
it is colder than yesterday,” “We will go swimming only if it
is sunny,” “If we do not go swimming, then we will take a
canoe trip.” and “If we take a canoe trip, then we will be
home by sunset” lead to the conclusion “We will be home by
sunset.”
SP–4 C (CS/IT-Sem-3) Solved Paper (2018-19)
More pdf : www.motivationbank.in
SOLUTION OF PAPER (2018-19)
Note : 1. Attempt all Sections. If require any missing data; then choose
suitably.
2. Any special paper specific instructions.
SECTION – A
e. How many bit strings of length eight either start with a ‘1’
bit or end with the two bit ‘00’ ?
Ans.
1. Number of bit strings of length eight that start with a 1 bit :
27 = 128.
2. Number of bit strings of length eight that end with bits 00 : 26 = 64.
3. Number of bit strings of length eight 25 = 32 that start with a 1 bit
and end with bits 00 : 25 = 32
Hence, the number is 128 + 64 – 32 = 160.
A B
f
Fig. 2. One-to-one.
SP–6 C (CS/IT-Sem-3) Solved Paper (2018-19)
More pdf : www.motivationbank.in
2. Onto function (Surjection or surjective function) : Let
f : X Y then f is called onto function iff for every element y Y
there is an element x X with f(x) = y or f is onto if Range (f) = Y.
X Y
Fig. 3. Onto.
3. One-to-one onto function (Bijective function or bijection) :
A function which is both one-to-one and onto is called one-to-one
onto function or bijective function.
X Y
f
1 a
2 b
3 c
|S F R| = ? |S F| = 103
|S| = 1232
|F| = 879
|S R| = 23
|F R| = 14
|R| = 114 |S F R| = 2092
Fig. 5.
HDIBJEK FCG
B C
A
B C D E F G
HDI JEK F G H I J K
* 1 –1 i –i
1 1 –1 i –i
–1 –1 1 –i i
i i –i –1 1
–i –i i –1 1
Discrete Structures & Theory of Logic SP–11 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
1. Closure property : Since all the entries of the composition table
are the elements of the given set, the set G is closed under
multiplication.
2. Associativity : The elements of G are complex numbers, and we
know that multiplication of complex numbers is associative.
3. Identity : Here, 1 is the identity element.
4. Inverse : From the composition table, we see that the inverse
elements of 1, – 1, i, – i are 1, – 1, – i, i respectively.
5. Commutativity : The corresponding rows and columns of the
table are identical. Therefore the binary operation is commutative.
Hence, (G, *) is an abelian group.
{a, b, d} {a, c, d}
{a, b, c} {b, c, d}
Fig. 6.
(P(S), ) is not a lattice because ({a, b},{b, d}) has no lub and glb.
V5 V4 D C
Fig. 7.
Necessary and sufficient condition for Euler circuits and
paths :
1. A graph has an Euler circuit if and only if the degree of every
vertex is even.
2. A graph has an Euler path if and only if there are at most two
vertices with odd degree.
a1, a2 .... we sum both sides of the last equations starting with n = 1.
To find that
n n
G(x) – 1 = a x (8a
n n –1 x 10 n–1 x n )
n 1 n 1
n n –1 n
= 8 a
n 1
n –1 x 10
n 1
x
SP–16 C (CS/IT-Sem-3) Solved Paper (2018-19)
More pdf : www.motivationbank.in
n –1 n –1 n –1
= 8x a
n 1
n –1 x x 10
n 1
x
n n
= 8x a x n x 10 xn
n 0 n 0
= 8xG(x) + x/(1 – 10x)
Therefore, we have
G(x) – 1 = 8xG(x) + x/(1 – 10x)
Expanding the right hand side of the equation into partial fractions
gives
1 1 1
G(x) =
2 1 8 x 1 10 x
This is equivalent to
1 n n n n
G(x) =
8 x
2 n 0 10 x
n 0
1 n
= (8 10n ) x n
n 0
2
1 n
an = (8 10n )
2
Discrete Structures & Theory of Logic SP–1 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
B.Tech.
(SEM. III) ODD SEMESTER
THEORY EXAMINATION, 2019-20
DISCRETE STRUCTURES & THEORY
OF LOGIC
Time : 3 Hours Max. Marks : 100
Section-A
Section-C
SP–4 C (CS/IT-Sem-3) Solved Paper (2019-20)
More pdf : www.motivationbank.in
SOLUTION OF PAPER (2019-20)
Section-A
Section-B
(a) (b )
Fig. 1. Some planar graph.
Proof : We will use induction to prove this theorem.
Step I : Inductive base :
Assume that e = 1 Then we have two cases given in figure below :
(a) (b)
Fig. 2.
In Fig. 1 (a) we have v = 2 and r = 1 v + r – e = 2 + 1 – 1 = 2
In Fig. 1 (b) we have v = 1 and r = 2 v + r – e = 1 + 2 – 1 = 2
Hence vertified
Step II : Inductive hypothesis :
Let us assume that given theorem is true for e = k
i.e., for k edges
Step III : Inductive step :
We have to show that theorem is true for k + 1 edges.
Let graph G has k + 1 edges.
Case I : We suppose that g contain no circuits. Now take a vertex
v and find a path starting at v. Since g has no circuit so whenever
we find an edge we have a new vertex atleast we will reach a
vertex with degree one as shown in Fig. 3.
x
v
Fig. 3.
Discrete Structures & Theory of Logic SP–9 C (CS/IT-Sem-3)
More pdf : www.motivationbank.in
Now remove vertex x and edge incident on v.
Then we will left with graph G* given as
Fig. 4.
Therefore Euler’s formula holds for graphs in Fig. 4, since it has k
edges [By inductive hypothesis]
Since G has one more edge than G* and one more vertices than G*.
So, let v = v1 + 1 and e = e1 + 1 where G* = (v1, e1)
v + r – e = v1 + 1 + r – e1 – 1
= v1 + r – e1 = 2 [By inductive hypothesis]
Hence Euler’s formula holds true.
Case II : We assume that G has a circuit and e is edge in circuit.
Let G be given in Fig. 5.
v1 v4
v2 v3
Fig. 5.
Now e is the part of boundary for 2 region so after removing edge
we are left with graph G* as shown in Fig. 6.
v1 v4
v2 v3
Fig. 6.
Now number of edges in G* are k so by inductive hypothesis,
Euler formula holds for G*.
Now since G has one more edges and region than G* with same vertices.
So v + r – e = v + r1 + 1 – e1 – 1 = v + r1 – e1 = 2
Hence Euler’s formula also holds for G.
Hence by Principle of mathematical induction Euler’s Theorem
holds true.
Section-C