DSTLCST Notes Aktu
DSTLCST Notes Aktu
DSTLCST Notes Aktu
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
CONTENTS
Part-1 : Set Theory : Introduction, ........................ 1–2C to 1–5C
Combination of Sets, Multisets
10. Disjoint set : Let A and B be two sets, if there is no common element
PART-1 between A and B, then they are said to be disjoint.
Set Theory : Introduction, Combination of Sets, Multisets. Que 1.2. Describe the different types of operation on sets.
Answer
Questions-Answers
1. Union : Let A and B be two sets, then the union of sets A and B is a set
Long Answer Type and Medium Answer Type Questions 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 }
Que 1.1. What do you understand by set ? Explain different types B = {3, 4, 5, 6 }
of set. A B = {1, 2, 3, 4, 5, 6}
2. Intersection : Let A and B be two sets, then intersection of A and B is
Answer a set that contain those elements which are common to both A and B. It
1. A set is a collection of well defined objects, called elements or members is denoted by A B and is read as ‘A intersection B’.
of the set. Symbolically, A B = {x|x A and x B}
2. These elements may be anything like numbers, letters of alphabets, For example : A = {1, 2, 3, 4}
points etc. B = {2, 4, 6, 7}
3. Sets are denoted by capital letters and their elements by lower case then A B = {2, 4}
letters. 3. Complement : Let U be the universal set and A be any subset of U,
4. If an object x is an element of set A, we write it as x A and read it as ‘x then complement of A is a set containing elements of U which do not
belongs to A’ otherwise x A (x does not belong to A). belong to A. It is denoted by Ac or A or A .
Types of set : Symbolically, Ac = {x|x U and x A}
1. Finite set : A set with finite or countable number of elements is called For example : U = {1, 2, 3, 4, 5, 6}
finite set. and A = {2, 3, 5}
2. Infinite set : A set with infinite number of elements is called infinite then Ac = {1, 4, 6}
set. 4. Difference of sets : Let A and B be two sets. Then difference of A and
3. Null set : A set which contains no element at all is called a null set. It is B is a set of all those elements which belong to A but do not belong to B
denoted by or { }. It is also called empty or void set. and is denoted by A – B.
4. Singleton set : A set which has only one element is called singleton set. Symbolically, A – B = {x|x A and x B}
5. Subset : Let A and B be two sets, if every elements of A also belongs to For example : Let A = {2, 3, 4, 5, 6, 7}
B i.e., if every element of set A is also an element of set B, then A is and B = {4, 5, 7}
called subset of B and it is denoted by A B. then A – B = {2, 3, 6}
Symbolically, A B if x A x B. 5. Symmetric difference of set : Let A and B be two sets. The symmetric
6. Superset : If A is subset of a set B, then B is called superset of A. difference of A and B is a set containing all the elements that belong to
7. Proper subset : Any subset A is said to be proper subset of another set A or B but not both. It is denoted by A B or A B.
B, if there is at least one element of B which does not belong to A, i.e., if Also A B = (A B) – (A B)
A B but A B. It is denoted by A B. For example : Let A = {2, 3, 4, 6}
8. Universal set : In many applications of sets, all the sets under B = {1, 2, 5, 6}
consideration are considered as subsets of one particular set. This set is then A B = {1, 3, 4, 5}
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 Que 1.3. What do you mean by multisets ?
belong to set B and every element of B belong to set A. It is written as
A = B. Answer
Symbolically, A = B if x A and x B.
1. Multisets are sets where an element appear more than once,
1–4 C (CS/IT-Sem-3) Set Theory, Functions & Natural Numbers Discrete Structures & Theory of Logic 1–5 C (CS/IT-Sem-3)
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 Que 1.7. List down laws of algebra of sets.
i. P Q, ii. P Q, iii. P – Q, iv. Q – P, v. P + Q. OR
Write down the general identities on sets.
Answer
i. P Q = {4.a, 3.b, 1.c, 2.d} Answer
ii. P Q = {3.a, 3.b} Let A, B, C be any three sets and U be the universal set, then following are
iii. P – Q = {1.a, 1.c} the laws of algebra of sets :
iv. Q – P = {2.d} 1. Idempotent laws :
v. P + Q = {7.a, 6.b, 1.c, 2.d} a. A A = A
Que 1.5. Describe each of following in roster form : b. A A = A
2. Commutative laws :
i. A = {x : x is an even prime} a. A B = B A
ii. B = {x : x is a positive integral divisor of 60} b. A B = B A
iii. C = {x R : x2 – 1 = 0} 3. Associative laws :
iv. D = {x : x2 – 2x + 1 = 0} a. A (B C) = (A B) C
v. E = {x : x is multiple of 3 or 5} b. A (B C) = (A B) C
4. Distributive laws :
Answer
a. A (B C) = (A B) (A C)
i. A = {2} b. A (B C) = (A B) (A C)
ii. B = {1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60} 5. Identity laws :
iii. C = {1, –1} a. A = A
iv. D = {1} b. A U = A
v. E = {3, 5, 6, 10, 15 ....} c. A U = U
d. A =
Que 1.6. Describe the following in set builder form : 6. Involution law :
i. A = {–4, –3, –2, –1, 0, 1, 2, 3} a. (Ac)c = A
1–6 C (CS/IT-Sem-3) Set Theory, Functions & Natural Numbers Discrete Structures & Theory of Logic 1–7 C (CS/IT-Sem-3)
Que 1.11. Describe the term relation along with its types. Answer
Let A and B be two non-empty sets, then R is relation from A to B if R is 1. Relations are sets of ordered pairs so all set operations can be done on
subset of A × B and is set of ordered pair (a, b) where a A and b B. It is relations.
denoted by aRb and read as “a is related to b by R”. 2. The resulting sets contain ordered pairs and are, therefore, relations.
Symbolically, R = {(a, b) : a A, b B, a R b } 3. If R and S denote two relations, then R S, known as intersection of
If (a, b) R then a R b and read as “a is not related to b by R”. R and S, defines a relation such that
x(R S) y = x R y x S y
For example :
4. Similarly, R S, known as union of R and S, such that
Let A = {1, 2, 3, 4}, B = {1, 2} and aRb iff a × b = even number
x(R S) y = x R y x S y
Then R = {(1, 2), (2, 1), (2, 2), (3, 2), (4, 1), (4, 2)}
Also, x(R – S) y = x R y x $ y where R – S is known as different
Types of relation :
of R and S
1. Universal relation : A relation R is called universal relation on A if
and x(R) y = x R y where R is the complement of R
R = A × A. In case where R is defined from A to B, then R is universal
For example : A = {x, y, z}, B = {x, y, z}, C = {x, y, z}
relation if R = A × B.
D = {Y, z}, R = {(x, X), (x, Y), (y, z)}
For example :
S = {(x, Y), (y, z)}
If A = {1, 2, 3}
The complement of R consists of all pairs of the Cartesian product
then R = {(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1),
A × B that are not R. Thus A × B = {(x, X), (x, Y), (x, Z), (y, X), (y, Y),
(3, 2), (3, 3)}
(y, Z), (z, X), (z, Y), (z, Z)}
is universal relation over A.
Hence R = {(x, Z), (y, X), (y, Y), (z, X), (z, Y), (z, Z)}
2. Identity relation : A relation R is called identity relation on A if
R S = {(x, X), (x, Y), (y, Z)}
R = {(a, a)|a A}. It is denoted by IA or A or . It is also called diagonal
R S = {(x, Y), (y, Z)}
relation.
R – S = {(x, Y)}
For example :
If A = {1, 2, 3}, then IA = {(1, 1), (2, 2), (3, 3)} Que 1.13. Give properties of relation.
is identity relation on A.
3. Void relation : A relation R is called a void relation on A if R = . It is Answer
also called null relation.
For example : Properties of relation are :
If A = {1, 2, 3} and R is defined as R = {(a + b) |a + b > 5}, a, b A then 1. Reflexive relation : A binary relation R on set A is said to be reflexive
R = . if every element of set A is related to itself.
1–10 C (CS/IT-Sem-3) Set Theory, Functions & Natural Numbers Discrete Structures & Theory of Logic 1–11 C (CS/IT-Sem-3)
i.e., a A, (a, a) R or aRa. 2. Symbolically, R S = {(a, c)| b B such that (a, b) R and
For example : Let R = {(1, 1), (1, 2), (2, 2), (2, 3), (3, 3)} be a relation (b, c) S}
defined on set A = {1, 2, 3}. As (1, 1) R, (2, 2) R and (3, 3) R.
Que 1.15. Describe recursive definition of relation.
Therefore, R is reflexive relation.
2. Irreflexive relation : A binary relation R defined on set A is said to
irreflexive if there is no element in A which is related to itself i.e., Answer
a A such that (a, a) R. 1. The characteristic function CR of a relation R Nk is defined as follows :
For example : Let R = {(1, 2), (2, 1), (3, 1)} be a relation defined on set – CS(X1, ..., Xk) = 1 if <X1, ..., Xk> S
A = {1, 2, 3}. As (1, 1) R, (2, 2) R and (3, 3) R. Therefore, R is – CS(X1, ..., Xk) = 0 if <X1, ..., Xk> S
irreflexive relation. 2. A relation R is a recursive set iff its characteristic function CR is a
3. Non-reflexive relation : A relation R defined on set A is said to be non- recursive function.
reflexive if it is neither reflexive nor irreflexive i.e., some elements are 3. Examples of recursive relations : <, >, , =
related to itself but there exist at least one element not related to itself. c<(x, y) = sg(y x)
4. Symmetric relation : A binary relation on a set A is said to be c>(x, y) = sg(x y)
symmetric if (a, b) R (b, a) R. c(x, y) = sg (x y)
5. Asymmetric relation : A binary relation on a set A is said to be
asymmetric if (a, b) R (b, a) R. c=(x, y) = sg (x y) ×c(x, y) = sg (y x)
6. Antisymmetric relation : A binary relation R defined on a set A is said 4. Consider relation R(x, y, z) defined as follows :
to antisymmetric relation if (a, b) R and (b, a) R a = b i.e., aRb and – R(x, y, z) iff y × z x
bRa a = b for a, b R. 5. We see that R is the result of substituting the recursive function × into
7. Transitive relation : A binary relation R on a set A is transitive recursive relation .
whenever (a, b) R and (b, c) R then (a, c) R 6. Thus, R is recursive.
i.e., aRb and bRc aRc. 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
Que 1.14. Write short notes on : f2(x, y, z) = x are recursive ... but that’s trivial using the identity
a. Equivalence relation functions).
b. Composition of relation
Que 1.16. Define the term partial order relation or partial ordering
OR
Write a short note on equality of relation. relation.
Answer Answer
a. Equivalence relation : A binary relation R defined on set A is called Partial Order Relation (POR) if
1. A relation R on a set A is said to be equivalence relation if it is R satisfies following properties :
reflexive, symmetric and transitive. i. (a, a) R a A (Reflexive)
2. The two elements a and b related by an equivalence relation are ii. If (a, b) R and (b, a) R, the a = b (Antisymmetric)
called equivalent. iii. If (a, b) R and (b, c) R (a, c) R where a, b, c A (Transitive)
3. So, a relation R is called equivalence relation on set A if it satisfies A set A together with a partial order relation R is called partial order set or
following three properties : poset.
i. (a, a) R a A (Reflexive)
Que 1.17. Write short notes on :
ii. (a, b) R (b, a) R (Symmetric)
iii. (a, b) R and (b, c) R (a, c) R (Transitive) a. Closure of relations
b. Composition of relation : b. Total order
1. Let R be a relation from a set A to B and S be a relation from set B c. Compatibility relation
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.
1–12 C (CS/IT-Sem-3) Set Theory, Functions & Natural Numbers Discrete Structures & Theory of Logic 1–13 C (CS/IT-Sem-3)
a – c is divisible by m
Answer a c (mod m), yes it is transitive.
a. Closure of relations : R is an equivalence relation.
i. Reflexive closure : Let R be a relation defined on set A. The To show : (x1 + x2) (y1 + y2) :
R IA is called reflexive closure of R, where IA = {(a, a)|a A} is It is given x1 y1 and x2 y2
diagonal or identity relation. i.e., x1 – y1 divisible by m
ii. Symmetric closure : Let R be a relation defined on set A. Then x2 – y2 divisible by m
R R–1 is called symmetric closure of R, where R–1 is inverse of R Adding above equation :
on A. (x1 – y1) + (x2 – y2) is divisible by m
b. Total order : A binary relation R on a set A is said to be total order iff it (x1 + x2) – (y1 + y2) is divisible by m
is i.e., (x1 + x2) (y1 + y2)
i. Partial order
Que 1.19. Let R be binary relation on the set of all strings of 0’s
ii. (a, b) R or (b, a) R a, b A
It is also called linear order. and 1’s such that R = {(a, b)|a and b are strings that have the same
c. Compatibility relation : A binary relation R defined on set A is said to number of 0’s}. Is R is an equivalence relation and a partial ordering
be compatible relation if it is reflexive and symmetric. It is denoted by ‘’. relation ? AKTU 2014-15, Marks 05
Que 1.18. Show that R = {(a, b)|a b (mod m)} is an equivalence
Answer
relation on Z. Show that if x1 y1 and x2 y2 then (x1 + x2) (y1 + y2).
For equivalence relation :
AKTU 2014-15, Marks 05 Reflexive : a R a (a, a) R a R
where a is a string of 0’s and 1’s.
Answer Always a is related to a because both a has same number of 0’s.
R = {(a, b) | a b (mod m)} It is reflexive.
For an equivalence relation it has to be reflexive, symmetric and transitive. Symmetric : Let (a, b) R
Reflexive : For reflexive a we have (a, a) R i.e., then a and b both have same number of 0’s which indicates that again
a a (mod m) both b and a will also have same number of zeros. Hence (b, a) R. It is
a – a is divisible by m i.e., 0 is divisible by m symmetric.
Therefore aRa, a Z, it is reflexive. Transitive : Let (a, b) R, (b, c) R
Symmetric : Let (a, b) Z and we have (a, b) R a and b have same number of zeros.
(a, b) R i.e., a b (mod m) (b, c) R b and c have same number of zeros.
a – b is divisible by m Therefore a and c also have same number of zeros, hence (a, c) R.
a – b = km, k is an integer It is transitive.
(b – a) = (– k) m R is an equivalence relation.
(b – a) = p m, p is also an integer For partial order, it has to be reflexive, antisymmetric and transitive. Since,
b – a is also divisible by m symmetricity and antisymmetricity cannot hold together. Therefore, it is not
b a (mod m ) (b, a) R partial order relation.
It is symmetric. Que 1.20. Let A {1, 2, 3,..........., 13}. Consider the equivalence relation
Transitive : Let (a, b) R and (b, c) R then
(a , b) R a – b is divisible by m on A × A defined by (a, b) R (c, d) if a + d = b + c. Find equivalence
a – b = t m, t is an integer ...(1.18.1) classes of (5, 8). AKTU 2014-15, Marks 05
(b, c) R b – c is divisible by m
b – c = s m, s is an integer ...(1.18.2)
Answer
From eq. (1.18.1) and (1.18.2)
a – b + b – c = (t + s) m A = {1, 2, 3, ...., 13}
a – c = lm, l is also an integer [(5, 8)] = [(a, b) : (a, b) R (5, 8), (a, b) A × A]
1–14 C (CS/IT-Sem-3) Set Theory, Functions & Natural Numbers Discrete Structures & Theory of Logic 1–15 C (CS/IT-Sem-3)
= [(a, b) : a + 8 = b + 5]
b R a
= [(a, b) : a + 3 = b]
[5, 8] = {(1, 4), (2, 5), (3, 6), (4, 7) aRb and bRa holds only when a = b. Relation is antisymmetric.
(5, 8), (6, 9), (7, 10), (8, 11) Transitive : Let a, b, c A and aRb and bRc
(9, 12), (10, 13)} b a, c b
ca
Que 1.21. The following relation on A = {1, 2, 3, 4}. Determine aRc
whether the following : Hence, relation is transitive.
a. R = {(1, 3), (3, 1), (1, 1), (1, 2), (3, 3), (4, 4)} Therefore, is a partial order relation.
b. R = A × A 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
Is an equivalence relation or not ? AKTU 2015-16, Marks 10 pair of elements of A and A is also a partial order relation. Hence, (A, )
is a lattice.
Answer
Que 1.23. Let n be a positive integer and S a set of strings. Suppose
a. R = {(1, 3), (3, 1), (1, 1), (1, 2), (3, 3), (4, 4)}
Reflexive : (a, a) R a A that R n is the relation on S such that sR nt if and only if
(1, 1) R, (2, 2) R s = t, or both s and t have at least n characters and first n characters
R is not reflexive. of s and t are the same. That is, a string of fewer than n characters is
Symmetric : Let (a, b) R then (b, a) R. related only to itself; a string s with at least n characters is related
(1, 3) R so (3, 1) R to a string t if and only if t has at least n characters and t beings with
(1, 2) R but (2, 1) R the n characters at the start of s. AKTU 2018-19, Marks 07
R is not symmetric.
Transitive : Let (a, b) R and (b, c) R then (a, c) R
Answer
(1, 3) R and (3, 1) R so (1, 1) R
(2, 1) R and (1, 3) R but (2, 3) R We have to show that the relation Rn is reflexive, symmetric, and transitive.
R is not transitive. 1. Reflexive : The relation Rn is reflexive because s = s, so that sRns
Since, R is not reflexive, not symmetric, and not transitive so R is not an whenever s is a string in S.
equivalence relation. 2. Symmetric : If sRn t, then either s = t or s and t are both at least n
b. R=A×A characters long that begin with the same n characters. This means that
Since, A × A contains all possible elements of set A. So, R is reflexive, tRn s. We conclude that Rn is symmetric.
symmetric and transitive. Hence R is an equivalence relation. 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
Que 1.22. Let (A, ) be a partially ordered set. Let be a binary characters, and either t = u or t and u are at least n characters long and
relation A such that for a and b in A, a is related to b iff b a. t and u begin with the same n characters. From this, we can deduce that
i. Show that is partially ordered relation. either s = u or both s and u are n characters long and s and u begin with
ii. Show that (A, ) is lattice or not. 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}.
Answer
i. (A, ) is a partially ordered relation if it is reflexive, antisymmetric and Is R equivalence relation. Draw the digraph of R.
transitive. AKTU 2017-18, Marks 07
Reflexive : Let a A then by definition of relation, aRa a a which
is true. Answer
Hence, the relation R i.e., is reflexive.
Antisymmetric : Let a, b A and Given that X = {1, 2, 3, 4, 5, 6, 7}
aRb b a and R = {(x, y) : (x – y) is divisible by 3 }
Then R is an equivalence relation if
a b
1–16 C (CS/IT-Sem-3) Set Theory, Functions & Natural Numbers Discrete Structures & Theory of Logic 1–17 C (CS/IT-Sem-3)
i. Reflexive : x X ( x x) is divisible by 3 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 }
So, ( x, x) X x X or, R is reflexive.
Also Range (f) Y
ii. Symmetric : Let x, y X and (x, y) R Classification of functions :
(x – y) is divisible by 3 (x – y) = 3n1, (n1 being an integer) 1. Algebraic functions : Algebraic functions are those functions which
(y – x) = – 3n2 = 3n2, n2 is also an integer consist of a finite number of terms involving powers and roots of the
So, y – x is divisible by 3 or R is symmetric. independent variable x.
iii. Transitive : Let x, y, z X and (x, y) R, (y, z) R Three particular cases of algebraic functions are :
Then x – y = 3n1, y – z = 3n2, n1, n2 being integers i. Polynomial functions : A function of the form a0xn + a1xn–1+...
x – z = 3(n1 + n2), n1 + n2 = n3 be any integer + an where n is a positive integer and a0, a1, ...., an are real constants
So, (x – z) is also divisible by 3 or (x, z) R and a0 0 is called a polynomial of x in degree n, for example
So, R is transitive. f (x) = 2x3 + 5x2 + 7x – 3 is a polynomial of degree 3.
Hence, R is an equivalence relation.
f (x )
ii. Rational functions : A function of the form where f (x) and
g( x )
1 3 g(x) are polynomials.
2
iii. Irrational functions : Functions involving radicals are called
3
irrational functions. f(x) = x + 5 is an example of irrational
4 7 6 function.
5 2. Transcendental functions : A function which is not algebraic is called
transcendental function.
Fig. 1.24.1. Diagraph of R. 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.
PART-4 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
Function : Definition, Classification of Functions, Operations on functions.
Functions, Recursively Defined Functions, Growth of 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
Questions-Answers called logarithm function.
Long Answer Type and Medium Answer Type Questions Que 1.26. Give the types / operations on functions.
Answer
Que 1.25. Define the term function. Also, give classification of it. 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
Answer there are distinct image in Y i.e., f is one-to-one iff
1. Let X and Y be any two non-empty sets. A function from X to Y is a rule f(x1) = f(x2) implies x1 = x2 x1, x2, X
that assigns to each element x X a unique element y Y. A B
f
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. Fig. 1.26.1. One-to-one.
1–18 C (CS/IT-Sem-3) Set Theory, Functions & Natural Numbers Discrete Structures & Theory of Logic 1–19 C (CS/IT-Sem-3)
This shows that every element z C has pre-image under gof. So, g f is This concept of recursion can be used to define sets, sequences and
onto. algorithms also.
Thus, g f is one-to-one onto function and hence (g f)–1 exists. We will define three functions which are called Basis function or Initial
By the definition of the composite functions, g f : A C. So, functions that are used in defining other functions by induction.
(g f)–1 : C A. 1. Zero function : (Z : z(x) = 0)
Also g–1 : C B and f–1 : B A. 2. Successor function : (S : s(x) = x + 1)
Then by the definition of composite functions, f–1 g–1 : C A. 3. Projection function or generalized identity function :
Therefore, the domain of (g f)–1 = the domain of f–1 g–1. Uin : Uin ( x1 , x2 ,.... xn ) xi )
Now (g f)–1 (z) = x (g f) (x) = z
where superscripts n indicates a number of argument of the function
g (f (x)) = z
and subscripts i indicates the value of the function is equal to ith
g (y) = z where y = f (x)
argument.
y = g–1 (z)
c. Primitive recursion :
f–1 (y) = f–1 (g–1 (z)) = (f–1 g–1) (z)
A function is called primitive recursion if and only if it can be constructed
x = (f–1 g–1) (z) [f–1 (y) = x]
from the initial functions and other known primitive recursive functions
Thus, (g f) (z) = (f g ) (z).
–1 –1 –1
by a finite number of operations and recursion only.
So, (g f)–1 = f–1 g–1.
For example : Consider the function
Que 1.29. Explain the following : f(x, y) = x + y
Now f(x, y + 1) = x + (y + 1)
a. Composition of functions = (x + y) + 1
b. Recursive function = f(x, y) + 1
c. Primitive recursion Also f(x, 0) = x + 0 = x
Now f(x, 0) = x = U11 (x) .....(1.29.1)
Answer
Also f(x, y + 1) = f(x, y) + 1
a. Composition of functions : = S{f(x, y)} where S is the successor function
If f : X Y and g : Y Z then the composition of f and g is a new function = {U33[x, y, f(x, y)]} ...(1.29.2)
from X to Z denoted by gof = g(f(x)) If we consider g(x) = U11(x) and h(x, y, z) = S·U33 (x, y, z)
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)}
x y = f(x) z = g f(x) Thus, f is obtained from the initial functions U11, U33 and S by applying
f g compositions once and recursion once. Hence, f is primitive recursive.
c2 g(n)
Questions-Answers
f(n)
c1 g(n) Long Answer Type and Medium Answer Type Questions
1 1 1 n a (r k 1)
Que 1.33. Prove by induction : + + ... + = . a + ar + ar2 + .... + ark–1 = ...(1.34.1)
1.2 2.3 n ( n + 1) ( n + 1) r 1
Now we will show that it is true for n = k + 1 using eq. (1.34.1)
AKTU 2016-17, Marks 10 i.e., a + ar + ar2 +.... + ark-1 + ark
Using eq. (1.34.1), we get
Answer a (r k 1)
+ ark
Let the given statement be denoted by S(n). r 1
1. Inductive base : For n = 1
ar k a ar k1 ar k a ( r k 1 1)
1 1 1 = =
= r 1 r 1
1.2 11 2
which is R.H.S. for n = k + 1, hence it is true for n = k + 1.
Hence S (1) is true. By mathematical induction, it is true for all n.
2. Inductive hypothesis : Assume that S (k) is true i.e.,
1 1 1 k Que 1.35. Prove that if n is a positive integer, then 133 divides
..... =
1.2 2.3 k(k 1) k 1
11n + 1 + 122n – 1. AKTU 2018-19, Marks 07
3. Inductive step : We wish to show that the statement is true for
n = k + 1 i.e.,
Answer
1 1 1 k1
..... = We prove this by induction on n.
1.2 2.3 (k 1)(k 2) k2 Base case : For n = 1, 11n+1 + 122n–1 = 112 + 121 = 133 which is divisible by
1 1 1 1 133.
Now, .....
1.2 2.3 k(k 1) ( k 1)(k 2) 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,
k 1 k2 2k 1 11n+1 + 122n–1 = 11k+1+1 + 122(k+1)–1
=
k 1 ( k 1)(k 2) ( k 1)(k 2) = 11k+2 + 122k+1
k1 = 11 * 11k+1 + 144 * 122k–1
= = 11 * 11k+1 + 11 * 122k–1 + 133 * 122k–1
k2
= 11[11k+1 + 122k–1] + 133 * 122k–1
Thus, S(k + 1) is true whenever S(k) is true. By principle of mathematical
= 11* 133A + 133 * 122k–1
induction, S(n) is true for all positive integer n.
= 133[11A + 122k–1]
Que 1.34. Prove by the principle of mathematical induction, that Thus if the hypothesis holds for n = k it also holds for n = k + 1. Therefore, the
statement given in the equation is true.
the sum of finite number of terms of a geometric progression,
a + ar + ar2 + ... arn–1 = a(rn – 1)/(r – 1) if r 1. Que 1.36. Prove by mathematical induction
AKTU 2014-15, Marks 05 n4 – 4n2 is divisible by 3 for all n > = 2.
AKTU 2017-18, Marks 07
Answer
Basis : True for n = 1 i.e., Answer
L.H.S = a Base case : If n = 0, then n4 – 4n2 = 0, which is divisible by 3.
a (r 1) Inductive hypothesis : For some n 0, n4 – 4n2 is divisible by 3.
R.H.S = =a
r1 Inductive step : Assume the inductive hypothesis is true for n. We need to
Therefore, L.H.S. = R.H.S. show that (n + 1)4 – 4(n + 1)2 is divisible by 3. By the inductive hypothesis, we
Induction : Let it be true for n = k i.e., 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.
1–26 C (CS/IT-Sem-3) Set Theory, Functions & Natural Numbers Discrete Structures & Theory of Logic 1–27 C (CS/IT-Sem-3)
3/p2 (3 divides p2) iii. Proof by Cases : In this method, we will cover up all the possible
3/p ( p is an integer) cases that we come across while proving the theorem.
p = 3x for some x Z Example : Prove that if x and y are real numbers, then max (x, y)
p2 = 9x2 ...(1.40.2) min (x, y) = x + y.
From eq. (1.40.1) and (1.40.2) we get, Case I : If x y, then max (x, y) + min (x, y) = y + x = x + y.
9x2 = 3q2 Case II : if x y, then max (x, y) + min (x, y) = x + y.
q2 = 3x2
3/q2 (3 divides q2)
3/q VERY IMPORTANT QUESTIONS
3 divides p and q which is contradiction to our assumption that p and
Following questions are very important. These questions
q are prime. Therefore, 3 is irrational.
may be asked in your SESSIONALS as well as
Que 1.41. Write a short note on the following with example : UNIVERSITY EXAMINATION.
i. Proof by contrapositive.
ii. Proof by exhaustive cases.
Q. 1. Prove for any two sets A and B that, (A B) = A B.
iii. Proof by cases.
Ans. Refer Q. 1.8.
Answer
Q. 2. Show that R = {(a, b)|a b (mod m)} is an equivalence
i. Proof by contrapositive : In this we can prove p q is true by
relation on Z. Show that if x1 y1 and x2 y2 then (x1 + x2)
showing ~ q ~ p is true. It is also called proof by contraposition.
(y1 + y2).
Example : Using method of contraposition if n is integer and 3n + 2 is
Ans. Refer Q. 1.18.
even then n is even.
Let p : 3n + 2 is even
Q. 3. Let R be binary relation on the set of all strings of 0’s and
q : n is even
1’s such that R = {(a, b)|a and b are strings that have the
Let ~ q is true i.e., n is odd
same number of 0’s}. Is R is an equivalence relation and a
n = 2k + 1, where k Z
partial ordering relation ?
Now, 3n + 2 = 3(2k + 1) + 2
Ans. Refer Q. 1.19.
= 2(3k + 2) + 1
= 2m + 1 where m = 3k + 2 Z
Q. 4. Let A {1, 2, 3,..........., 13}. Consider the equivalence relation
(3n + 2) is odd ~ p is true
on A × A defined by (a, b) R (c, d) if a + d = b + c. Find
Hence ~ q ~ p is true.
equivalence classes of (5, 8).
By method of contraposition p q is true.
Ans. Refer Q. 1.20.
ii. Proof by exhaustive cases : Some proofs proceed by exhausting all
the possibilities. We will examine a relatively small number of examples
Q. 5. The following relation on A = {1, 2, 3, 4}. Determine whether
to prove the theorem. Such proofs are called exhaustive proofs.
the following :
Example : Prove that n2 + 1 2n where n is a positive integer and
a. R = {(1, 3), (3, 1), (1, 1), (1, 2), (3, 3), (4, 4)}
1 n 4.
b. R = A × A
We will verify the given inequality n2 + 1 2n for n = 1, 2, 3, 4.
Is an equivalence relation or not ?
For n = 1; 1 + 1 = 2 which is true
Ans. Refer Q. 1.21.
For n = 2; 4 + 1 > 22 which is true
For n = 3; 9 + 1 > 23 which is true
Q. 6. Let n be a positive integer and S a set of strings. Suppose
For n = 4; 16 + 1 > 24 which is true
that Rn is the relation on S such that sRnt if and only if
In each of these four cases n2 + 1 2n holds true. Therefore, by method
s = t, or both s and t have at least n characters and first n
of exhaustive cases n2 + 1 2n, where n is the positive integer and
characters of s and t are the same. That is, a string of fewer
1 n 4 is true.
than n characters is related only to itself; a string s with at
1–30 C (CS/IT-Sem-3) Set Theory, Functions & Natural Numbers Discrete Structures & Theory of Logic 2–1 C (CS/IT-Sem-3)
2
at least n characters and t beings with the n characters at
the start of s.
Ans. Refer Q. 1.23.
Q. 10. Prove that n3 + 2n is divisible by 3 using principle of Part-2 : Cyclic Group, Cosets, ............................. 2–10C to 2–16C
mathematical induction, where n is natural number. Lagrange’s Theorem
Ans. Refer Q. 1.32.
Part-3 : Normal Subgroups, ................................ 2–17C to 2–18C
Permutation and
1 1 1 n Symmetric of Groups
Q. 11. Prove by induction : + + ... + = .
1.2 2.3 n ( n + 1) (n + 1)
Part-4 : Group Homomorphisms, ....................... 2–19C to 2–22C
Ans. Refer Q. 1.33. Definition and Elementary
Properties of Rings and Fields.
Q. 12. Prove by the principle of mathematical induction, that
the sum of finite number of terms of a geometric
progression,
a + ar + ar2 + ... arn–1 = a(rn – 1)/(r – 1) if r 1.
Ans. Refer Q. 1.34.
1. a * b G a, b G [closure property]
PART-1 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
Algebraic Structures : Definition, Groups, Subgroups and Order.
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
Questions-Answers For example : (Z, +), (R, +), and (Q, +) are all groups.
ii. Abelian group : A group (G, *) is called abelian group or commutative
Long Answer Type and Medium Answer Type Questions 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
Que 2.1. What is algebraic structure ? List properties of algebraic
elements in G are finite. For example G = {0, 1, 2, 3, 4, 5} under 6 is a
system. finite group.
Answer Infinite group : A group {G, *} is called infinite group if number of
element in G are infinite.
Algebraic structure : An algebraic structure is a non-empty set G equipped For example, (Z, +) is infinite group.
with one or more binary operations. Suppose * is a binary operation on G. iv. Order of group : Order of group G is the number of elements in group
Then (G, *) is an algebraic structure. G. It is denoted by o (G) or |G|. A group of order 1 has only the identity
Properties of algebraic system : Let {S, *, +} be an algebraic structure element.
where * and + binary operation on S : v. Groupoid : Let (S, *) be an algebraic structure in which S is a non-
1. Closure property : (a * b) S a, b, S empty set and * is a binary operation on S. Thus, S is closed with the
2. Associative property : (a * b) * c = a * (b * c) a, b, c S operation *. Such a structure consisting of a non-empty set S and a
3. Commutative property : (a * b) = (b * a) a, b S binary operation defined in S is called a groupoid.
4. Identity element : e S such that a * e = a (right identity) a S, Que 2.3. Describe subgroup with example.
e is called identity element of S with respect to operation *.
5. Inverse element : For every a S, a–1 S such that
Answer
a * a–1 = e = a– 1 * a
–1
here a is called inverse of ‘a’ under operation *. If (G, *) is a group and H G. The (H, *) is said to subgroup of G if
6. Cancellation property : (H, *) is also a group by itself. i.e.,
a * b = a * c b = c and b * a = c * a b = c a, b, c S and a 0 (1) a * b H a, b H (Closure property)
(2) e H such that a * e = a = e * a a H
7. Distributive property : a, b, c S
Where e is called identity of G.
a * (b + c) = (a * b) + (a * c) (right distributive)
(3) a – 1 H such that a * a – 1 = e = a– 1 * a a H
(b + c) * a = (b * a) + (c * a) (left distributive)
For example : The set Q+ of all non-zero +ve rational number is subgroup
8. Idempotent property : An element a S is called idempotent element
of Q – {0}.
with respect to operation * if a * a = a.
Que 2.4. Show that the set G = {x + y 2 |x, y Q} is a group with
Que 2.2. Write short notes on :
respect to addition.
i. Group ii. Abelian group
iii. Finite and infinite group iv. Order of group Answer
v. Groupoid
i. Closure :
Answer Let X = x1 + 2 y1
i. Group : Let (G, *) be an algebraic structure where * is binary operation Y = x2 + 2 y2
then (G, *) is called a group if following properties are satisfied : where x1, x2, y1, y2 Q and X, Y G
2–4 C (CS/IT-Sem-3) Algebraic Structures Discrete Structures & Theory of Logic 2–5 C (CS/IT-Sem-3)
Then X + Y = (x1 + 3. Then ah1, ah2, ...., ahm, are the members of aH, all distinct.
2 y1) + (x2 + 2 y2)
For, we have
= (x1 + x2) + (y1 + y2) 2 ahi = ahj hi = hj
= X1 + 2Y1 G where X1, Y1 Q by cancellation law in G.
Therefore, G is closed under addition [ Sum of two rational numbers is 4. Since G is a finite group, the number of distinct left cosets will also be
rational]. finite, say k. Hence the total number of elements of all cosets is km
ii. Associativity : which is equal to the total number of elements of G.
Let X, Y and Z G Hence
n = mk
X = x1 + 2 y1 Y = x2 + 2 y2 Z = x3 + 2 y3 This show that m, the order of H, is a divisor of n, the order of the
where x1, x2, x3, y1, y2, y3 Q group G.
Consider (X + Y) + Z = (x1 + 2 y1 + x2 + 2 y2) + (x3 + 2 y 3) We also find that the index k is also a divisor of the order of the group.
= ((x1 + x2) + (y1 + y2) 2 ) + (x3 + 2 y 1) Que 2.6. Define identity and zero elements of a set under a binary
= (x1 + x2 + x3) + (y1 + y2 + y3) 2 ...(2.4.1) operation *. What do you mean by an inverse element ?
Also X + (Y + Z) = (x1 + 2 y1) + ((x2 + 2 y2) + (x3 + 2 y3)) Answer
= (x1 + 2 y1) + ((x2 + x3) + (y2 + y3) 2 ) Identity element : An element e in a set S is called an identity element with
= (x1 + x2 + x3) + (y1 + y2 + y3) 2 ...(2.4.2) respect to the binary operation * if, for any element a in S
From eq. (2.4.1) and (2.4.2) a*e= e*a=a
(X + Y) + Z = X + (Y + Z) If a * e = a, then e is called the right identity element for the operation * and
Therefore, G is associative under addition. if e * a = a, then e is called the left identity element for the operation *.
iii. Identity element : Zero element : Let R be an abelian group with respect to addition. The
Let e G be identity elements of G under addition then 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
(x + y 2 ) + (e1 + e2 2 ) = x + y 2
respects to the binary operation *. If corresponding to each element
where e = e1 + e2 2 and e1, e2, x, y Q a S there exists an element b S such that
a*b= b*a=e
e1 + e2 2 = 0 + 0 2 Then b is said to be the inverse of a and is usually denoted by a – 1. We say a
e1 = 0 and e2 = 0 is invertible.
Therefore, 0 G is identity element.
iv. Inverse element : Que 2.7. Prove that (Z6, (+6)) is an abelian group of order 6, where
– x – y 2 G is inverse of x + y 2 G. Z6 = {0, 1, 2, 3, 4, 5}. AKTU 2014-15, Marks 05
Therefore, inverse exist for every element x + y 2 G such that, y Q.
Hence, G is a group under addition. Answer
Answer *6 1 2 3 4 5
The composition table of G is
1 1 2 3 4 5
1 –1 i –i 2 2 4 0 2 4
*
3 3 0 3 0 3
1 1 –1 i –i
4 4 2 0 4 2
–1 –1 1 –i i
5 5 4 3 2 1
i i –i –1 1 Since, 2 *6 3 = 0 but 0 S i.e., S is not closed under multiplication modulo 6.
–i –i i –1 1 So, S is not a group.
Que 2.10. Let G = {a, a2, a3, a4, a5, a6 = e}. Find the order of every
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. element.
2. Associativity : The elements of G are complex numbers, and we know
Answer
that multiplication of complex numbers is associative.
3. Identity : Here, 1 is the identity element. o(a) : a6 = e o(a) = 6
4. Inverse : From the composition table, we see that the inverse elements o(a2) : (a2)3 = a6 = e o (a2) = 3
of 1, – 1, i, – i are 1, – 1, – i, i respectively. o(a3) : (a3)2 = a6 = e o(a3) = 2
2–8 C (CS/IT-Sem-3) Algebraic Structures Discrete Structures & Theory of Logic 2–9 C (CS/IT-Sem-3)
common. Since G is a finite group, the number of distinct right cosets of H in Thus order of each subgroup of a finite group G is a divisor of the order of the
G will be finite, say, equal to k. The union of these k distinct right cosets of H group.
in G is equal to G. Cor 1 : If H has m different cosets in G then by Lagrange’s theorem :
Thus, if Ha1, Ha2,...., Hak are the k distinct right cosets of H in G. Then o(G) = m o(H)
G = Ha1 Ha2 Ha3 .... Hak o(G )
the numbe r of elements in G = the numbe r of e lements in m=
o( H )
Ha1 + ...... + the number of elements in Ha2 +......+ the number of elements in
o(G )
Hak [G : H] =
O(G) = km o( H )
n = km Cor 2 : If |G| = n and a G then an = e
n Let |a| = m am = e
k= Now, the subset H of G consisting of all integral powers of a is a subgroup of
m
m is a divisor of n. G and the order of H is m.
O(H) is a divisor of O(G). Then by Lagrange’s theorem, m is divisor of n.
Proof of converse : If G be a finite group of order n and n G, then Let n = mk, then
an = e an = amk = (am)k = ek = e
Let o (a) = m which implies am = e. Que 2.23.
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. a. Prove that every cyclic group is an abelian group.
Then, by the Lagrange’s theorem, m is divisor of n. b. Obtain all distinct left cosets of {(0), (3)} in the group
Let n = mk, then (Z6, +6) and find their union.
an = amk = (am)k = ek = e c. Find the left cosets of {[0], [3]} in the group (Z6, +6).
Yes, the converse is true. AKTU 2016-17, Marks 10
Que 2.22. State and explain Lagrange’s theorem.
Answer
Answer a. Let G be a cyclic group and let a be a generator of G so that
G = <a> = {an : n Z}
Lagrange’s theorem :
If g1 and g2 are any two elements of G, there exist integers r and s such
If G is a finite group and H is a subgroup of G then o(H) divides o(G).
that g1 = ar and g2 = as. Then
Moreover, the number of distinct left (right) cosets of H in G is o(G)/o(H).
g1 g2 = ar as = ar+s = as+r = as . ar = g2g1
Proof : Let H be subgroup of order m of a finite group G of order n.
So, G is abelian.
Let H {h1, h2, ..., hm}
b. [0] + H = [3] + H, [1] + [4] + H and [2] + H = [5] + H are the three
Let a G. Then aH is a left coset of H in G and aH = {ah1, ah2, ..., ahm} has m
distinct left cosets of H in (Z6 , + 6 ).
distinct elements as ahi = ahj hi = hj by cancellation law in G.
We would have the following left cosets :
Thus, every left coset of H in G has m distinct elements.
g1H = {g1 h, h H}
Since G is a finite group, the number of distinct left cosets will also be finite.
g2H = {g2 h, h H}
Let it be k. Then the union of these k-left cosets of H in G is equal to G.
gnH = {gn h, h H}
i.e., if a1H, a2H, ..., akH are right cosets of H in G then
The union of all these sets will include all the g s, since for each set
G = a1H a2H ... akH.
gk = {gk h, h H}
o(G) = o(a1H) + o(a2H) + ... + o(akH)
we have ge gk = {gk h, h H}
(Since two distinct left cosets are mutually disjoint.)
where e is the identity.
n = m + m + ... + m (k times)
Then if we make the union of all these sets we will have at least all the
n elements of g. The other elements are merely gh for some h. But since ghG
n = mk k =
m they would be repeated elements in the union. So, the union of all left cosets
o(G ) of H in G is G, i.e.,
k= .
o( H ) Z6 = {[0], [1], [2], [3], [4], [5]}
2–16 C (CS/IT-Sem-3) Algebraic Structures Discrete Structures & Theory of Logic 2–17 C (CS/IT-Sem-3)
Answer
PART-4
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. Group Homomorphism, Definition and Elementary Properties of
i.e., Ring and Fields.
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. Questions-Answers
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 Long Answer Type and Medium Answer Type Questions
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}
Que 2.29. Discuss homomorphism and isomorphic group.
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 Answer
b H.
– 1
Homomorphism : Let (G1, •) and (G2, *) be two groups then a mapping
Now, (a b – 1) x = a (b – 1 x) [ is associative] f : G1 G2 is called a homomorphism if f(a • b) = f(a) * f(b) for all a, b G1.
= a (x b – 1) [ use b – 1 H] Thus f is homomorphism from G1 to G2 then f preserves the composition in
= (a x) b – 1 [ a H] G1 and G2 i.e., image of composition is equal to composition of images.
= (x a) b – 1
= x (a b – 1) The group G2 is said to be homomorphic image of group G1 if there exist a
a b–1 H homomorphism of G1 onto G2.
Therefore, H is a subgroup of group G. Isomorphism : Let (G1, •) and (G2, *) be two groups then a mapping
Let h H and g G and any x in G. f : G1 G2 is an isomorphism if
Consider i. f is homomorphism.
(g h g – 1) x = (g g – 1 h) x [ h H]
ii. f is one to one i.e., f(x) = f(y) x = y x, y G1.
= (e h) x = h x
= xh [ h H] iii. f is onto.
= x (h g g – 1)
Que 2.30. Give the definitions of rings, integral domains and fields.
= x (g h g – 1) [ h H]
g h g – 1 H for any g G
H is a normal subgroup of G. Answer
Ring : A ring is an algebraic system (R, +, •) where R is a non-empty set and
Que 2.28. If N and M are normal subgroup of G then N M is a + and • are two binary operations (which can be different from addition and
normal subgroup of G. multiplication) and if the following conditions are satisfied :
1. (R, +) is an abelian group.
Answer
2. (R, •) is semigroup i.e., (a • b) • c = a • (b • c) a, b, c R.
As N and M are subgroups of G then N M is a subgroup of G. Let g G 3. The operation • is distributive over +.
and a N M i.e., for any a, b, c R
a N and a M. a • (b + c) = (a • b) + (a • c) or (b + c) • a = (b • a) + (c • a)
Since N is normal subgroup of G, gag–1 N Integral domain : A ring is called an integral domain if :
Since M is normal subgroup of G, gag–1 M i. It is commutative
gag–1 N M is a normal subgroup of G. ii. It has unit element
iii. It is without zero divisors
Hence N M is a normal subgroup of G.
2–20 C (CS/IT-Sem-3) Algebraic Structures Discrete Structures & Theory of Logic 2–21 C (CS/IT-Sem-3)
Field : A ring R with at least two elements is called a field if it has following iv. Here 0 is the additive identity and 1 is the multiplicative identity. Identity
properties : property is satisfied.
i. R is commutative v. Inverse exists in both the tables. The additive inverse of 0, 1 are 1, 0
ii. R has unity respectively and the multiplicative inverse of non-zero element of Z2
iii. R is such that each non-zero element possesses multiplicative inverse. is 1.
For example, the rings of real numbers and complex numbers are also fields. vi. Multiplication is distributive over addition.
Hence (Z2, +2, *2) is a ring as well as field. Since, we know that every field is
Que 2.31. Consider a ring (R, +, ) defined by a • a = a, determine an integral domain therefore it is also an integral domain.
whether the ring is commutative or not.
Que 2.33. If the permutation of the elements of {1, 2, 3, 4, 5} are
AKTU 2014-15, Marks 05
given by a = (1 2 3) (4 5), b = (1) (2) (3) (4 5), c = (1 5 2 4) (3). Find the value
Answer of x, if ax = b. And also prove that the set Z4 = (0, 1, 2, 3) is a commutative
ring with respect to the binary modulo operation +4 and *4.
Let a, b R (a + b)2 = (a + b)
(a + b) (a + b) = (a + b) AKTU 2015-16, Marks 10
(a + b)a + (a + b)b = (a + b)
Answer
(a2 + ba) + (ab + b2) = (a + b)
ax = b (123) (45) x = (1) (2) (3) (4, 5)
(a + ba) + (ab + b) = (a + b) ( a2 = a and b2 = b)
(a + b) + (ba + ab) = (a + b) + 0 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
ba + ab = 0
a + b = 0 a + b = a + a [being every element of its own additive inverse]
1 2 3 4 5 1 2 3 4 5
b=a 2 3 1 5 4 x = 1 2 3 5 4
ab = ba
1
R is commutative ring. 1 2 3 4 5 1 2 3 4 5
x=
2 3 1 5 4 1 2 3 5 4
Que 2.32. Write out the operation table for [Z2, +2, * 2]. Is Z2 a
ring ? Is an integral domain ? Is a field ? Explain. 2 3 1 5 4 1 2 3 4 5
=
1 2 3 4 5 1 2 3 5 4
Answer
1 2 3 4 5 1 2 3 4 5
The operation tables are as follows : =
we have Z2 = {0, 1} 3 1 2 5 4 1 2 3 5 4
+2 0 1 *2 0 1
1 2 3 4 5
x=
3 1 2 4 5
0 0 1 0 0 0
1 1 0 1 0 1 4 0 1 2 3 4 0 1 2 3
Since (Z2, +2, *2) satisfies the following properties : 0 0 1 2 3 0 0 0 0 0
i. Closure axiom : All the entries in both the tables belong to Z2. Hence, 1 1 2 3 0 1 0 1 2 3
closure is satisfied. 2 2 3 0 1 2 0 2 0 2
ii. Commutative : In both the tables all the entries about the main diagonal 3 3 0 1 2 3 0 3 2 1
are same therefore commutativity is satisfied. We find from these tables :
iii. Associative law : The associative law for addition and multiplication i. All the entries in both the tables belong to Z4. Hence, Z4 is closed with
are also satisfied. respect to both operations.
2–22 C (CS/IT-Sem-3) Algebraic Structures Discrete Structures & Theory of Logic 2–23 C (CS/IT-Sem-3)
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 VERY IMPORTANT QUESTIONS
both operations. Following questions are very important. These questions
iii. Associative law : The associative law for addition and multiplication may be asked in your SESSIONALS as well as
a +4 (b +4 c) = (a +4 b) +4 c for all a, b, c Z4 UNIVERSITY EXAMINATION.
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 Q. 1. Let H be a subgroup of a finite group G. Prove that order of
identity for Z4. H is a divisor of order of G.
v. Existence of inverse : The additive inverses of 0, 1, 2, 3 are 0, 3, 2, 1 Ans. Refer Q. 2.5.
respectively.
Q. 2. Prove that (Z6, (+6)) is an abelian group of order 6, where
Multiplicative inverse of non-zero element 1, 2, 3 are 1, 2, 3 respectively.
Z6 = {0, 1, 2, 3, 4, 5}.
vi. Distributive law : Multiplication is distributive over addition i.e., Ans. Refer Q. 2.7.
a ×4(b +4c) = a ×4b + a ×4c
(b +4c) ×4a = b ×4a + c ×4a Q. 3. Let G = {1, – 1, i, – i} with the binary operation multiplication
For, a ×4(b +4c) = a ×4(b + c) for b +4 c = b + c (mod 4) be an algebraic structure, where i = 1 . Determine
= least positive remainder when a × (b + c) is whether G is an abelian or not.
divided by 4
Ans. Refer Q. 2.8.
= least positive remainder when ab + ac is divided
by 4 Q. 4. Write the properties of group. Show that the set (1, 2, 3, 4, 5)
= ab +4ac is not group under addition and multiplication modulo 6.
= a ×4b +4a ×4c Ans. Refer Q. 2.9.
For a ×4b = a × b (mod 4)
Since (Z4, +4) is an abelian group, (Z4, ×4) is a semigroup and the operation is Q. 5. Let G be a group and let a, b G be any elements.
distributive over addition. The (Z4, +4, ×4) is a ring. Now (Z4, ×4) is commutative Then
with respect to ×4. Therefore, it is a commutative ring. i. (a–1)–1 = a
ii. (a * b)–1 = b–1 * a–1.
Que 2.34. What is meant by ring ? Give examples of both Ans. Refer Q. 2.11.
commutative and non-commutative rings.
Q. 6. Prove that the intersection of two subgroups of a group is
AKTU 2018-19, Marks 07 also subgroup.
Ans. Refer Q. 2.12.
Answer
Ring : Refer Q. 2.30, Page 2–19C, Unit-2. Q. 7. Let G be the set of all non-zero real number and let
a * b = ab/2. Show that (G *) be an abelian group.
Example of commutative ring : Refer Q. 2.31, Page 2–20C, Unit-2.
Ans. Refer Q. 2.13.
Example of non-commutative ring : Consider the set R of 2 × 2 matrix
with real element. For A, B, C R Q. 8. Prove that inverse of each element in a group is unique.
A * (B + C) = (A * B) + (A * C) Ans. Refer Q. 2.14.
also, (A + B) * C = (A * C) + (B * C)
* is distributive over +. Q. 9. Prove that every group of prime order is cyclic.
(R, +, *) is a ring. Ans. Refer Q. 2.16.
We know that AB BA, Hence (R, +, *) is non-commutative ring.
2–24 C (CS/IT-Sem-3) Algebraic Structures Discrete Structures & Theory of Logic 3–1 C (CS/IT-Sem-3)
3
Ans. Refer Q. 2.17.
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. CONTENTS
c. Find the left cosets of {[0], [3]} in the group (Z6, +6).
Ans. Refer Q. 2.23. Part-1 : Lattices : Definition, ................................. 3–2C to 3–10C
Properties of Lattices–Bounded,
Q. 14. Write and prove the Lagrange’s theorem. If a group Complemented, Modular
G = {...., – 3, 2, – 1, 0, 1, 2, 3,.....} having the addition as binary and Complete Lattice
operation. If H is a subgroup of group G where x2 H such
that x G. What is H and its left coset w.r.t 1 ? Part-2 : Boolean Algebra : .................................... 3–10C to 3–13C
Ans. Refer Q. 2.24. Introduction, Axioms and
Theorems of Boolean Algebra
Q. 15. Consider a ring (R, +, ) defined by a • a = a, determine
whether the ring is commutative or not. Part-3 : Algebraic Manipulation .......................... 3–13C to 3–17C
of Boolean Expressions,
Ans. Refer Q. 2.31.
Simplification of Boolean
Functions, Karnaugh Maps
Q. 16. If the permutation of the elements of {1, 2, 3, 4, 5} are given
by a = (1 2 3) (4 5), b = (1) (2) (3) (4 5), c = (1 5 2 4) (3). Find the
Part-4 : Logic Gates, Digital ................................ 3–17C to 3–20C
value of x, if ax = b. And also prove that the set Z4 = (0, 1, 2, 3) Circuits and
is a commutative ring with respect to the binary modulo Boolean Algebra
operation +4 and *4.
Ans. Refer Q. 2.33.
3–2 C (CS/IT-Sem-3) Lattices and Boolean Algebra Discrete Structures & Theory of Logic 3–3 C (CS/IT-Sem-3)
Answer
PART-1
Types of lattice :
Lattices : Definition, Properties of Lattices–Bounded, 1. Bounded lattice : A lattice L is said to be bounded if it has a greatest
Complemented, Modular and Complete Lattice. element 1 and a least element 0. In such lattice we have
a 1 = 1, a 1 = a
a 0 = a, a 0 = 0
Questions-Answers a L and 0 a I
2. Complemented lattice : Let L be a bounded lattice with greatest
Long Answer Type and Medium Answer Type Questions
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
Que 3.1. Define lattice. Give its properties. A lattice L is called complemented if is bounded and if every element in
L has a complement.
Answer 3. Distributive lattice : A lattice L is said to be distributive if for any
A lattice is a poset (L, ) in which every subset {a, b} consisting of 2 elements element a, b and c of L following properties are satisfied :
has least upper bound (lub) and greatest lower bound (glb). Least upper i. a (b c) = (a b) (a c)
bound of {a, b} is denoted by a b and is known as join of a and b. Greatest ii. a (b c) = (a b) (a c)
lower bound of {a, b} is denoted by a b and is known as meet of a and b.
otherwise L is non-distributive lattice.
Lattice is generally denoted by (L, , ).
4. Complete lattice : A lattice L is called complete if each of its non-
Properties :
empty subsets has a least upper bound and greatest lower bound.
Let L be a lattice and a, b L then
For example :
1. Idempotent property :
i. (Z, ) is not a complete lattice.
i. aa=a ii. a a = a
2. Commutative property : 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
i. ab=ba ii. a b = b a
X Y = X Y and X Y. Every subset of S has glb and lub. So, S
3. Associative property :
is complete.
i. a (b c) = (a b) c ii. a (b c) = (a b) c
5. Modular lattice : A lattice (L, ) is called modular lattice if,
4. Absorption property :
a (b c) = (a b) c whenever a c for all a, b, c L.
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 Que 3.3. If the lattice is represented by the Hasse diagram given
iii. a b = a iff a b = b below :
6. Distributive Inequality : i. Find all the complements of ‘e’.
i. a (b c) (a b) (a c) ii. a (b c) (a b) (a c) ii. Prove that the given lattice is bounded complemented lattice.
b
7. Isotonicity :
Let a, b, c, L and a b, then a c
i. acbc ii. a c b c
8. Stability :
Let a, b, c, L, then f d
i. a b, a c a (b c), a (b c)
e
ii. a b, a c a (b c), a (b c)
Fig. 3.3.1.
Que 3.2. Explain types of lattice. AKTU 2014-15, Marks 10
3–4 C (CS/IT-Sem-3) Lattices and Boolean Algebra Discrete Structures & Theory of Logic 3–5 C (CS/IT-Sem-3)
Consider a1 = a1 0
Answer = a1 (a a2) [from (3.5.2)]
i. Complements of e are c and d which are as follows : = (a1 a) (a1 a2) [Distributive property]
c e = b , c e = f = (a a1) (a1 a2) [Commutative property]
de=b , de=f = I (a1 a2) [from (3.5.1)]
ii. A lattice is bounded if it has greatest and least elements. Here b is = a1 a2 ...(3.5.3)
greatest and f is least element.
Now Consider a2 = a2 0
Que 3.4. Define a lattice. For any a, b, c, d in a lattice (A, ) if a b = a2 (a a1) [from (3.5.2)]
and c d then show that a c b d and a c b d. = (a2 a) (a2 a1) [Distributive property]
= (a a2) (a1 a2) [Commutative property]
AKTU 2018-19, Marks 07
= I (a1 a2) [from (3.5.1)]
Answer = a1 a2 ...(3.5.4)
Hence, from (3.5.3) and (3.5.4),
Lattice : Refer Q. 3.1, Page 3–2C, Unit-3.
a1 = a2
Numerical :
So, for bounded distributive lattice complement is unique.
As a b and c d, a b b d and c d b d.
Hasse diagram of [P(a, b, c), ] or [P(a, b, c), ] is shown in Fig. 3.5.1.
By transtivity of , a b d and c b d.
{a, b, c}
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.
{a, b} {a, c} {b, c}
So a c b d.
Que 3.5. Let L be a bounded distributed lattice, prove if a
complement exists, it is unique. Is D12 a complemented lattice ? {a} {b} {c}
Draw the Hasse diagram of [P (a, b, c), <], (Note : ‘<’ stands for subset).
Find greatest element, least element, minimal element and maximal
element. AKTU 2015-16, Marks 15
OR
Fig. 3.5.1.
Draw the Hasse diagram of [P (a, b, c), ] (Note : ‘’ stands for subset).
Find greatest element, least element, minimal element and maximal Greatest element is {a, b, c} and maximal element is {a, b, c}..
The least element is and minimal element is .
element. AKTU 2015-16, Marks 10
Que 3.6. The directed graph G for a relation R on set A = {1, 2, 3,
Answer 4} is shown below :
Let a1 and a2 be two complements of an element a L.
Then by definition of complement 1 2
a a1 I
...(3.5.1)
a a1 0
a a2 I 3 4
...(3.5.2)
a a2 0 Fig. 3.6.1.
3–6 C (CS/IT-Sem-3) Lattices and Boolean Algebra Discrete Structures & Theory of Logic 3–7 C (CS/IT-Sem-3)
i. Verify that (A, R) is a poset and find its Hasse diagram. Now a b = least upper bound of a, b
ii. Is this a lattice ? = least {all upper bounds of a, b}
iii. How many more edges are needed in the Fig. 3.6.1 to extend
(A, R) to a total order ? = least {b, c, ...} [using a b c]
iv. What are the maximal and minimal elements ? =b ...(3.7.1)
AKTU 2014-15, Marks 10 and b c = greatest lower bound of b, c
= maximum {all lower bounds of b, c}
Answer = maximum {b, a, ...} [using a b c]
i. The relation R corresponding to the given directed graph is, =b ...(3.7.2)
R = {(1, 1), (2, 2), (3, 3), (4, 4), (3, 1), (3, 4), (1, 4), (3, 2)} Eq. (3.7.1) and (3.7.2) gives, a b = b c
R is a partial order relation if it is reflexive, antisymmetric and transitive. b. (a b) (b c) (a b) (a c) = b
Reflexive : Since aRa, a A . Hence, it is reflexive. Consider, (a b) (b c)
Antisymmetric : Since aRb and bRa then we get a = b otherwise aRb = b b [using a b c and definition of and ]
or bRa. =b ...(3.7.3)
Hence, it is antisymmetric. and (a b) (a c) = b c
Transitive: For every aRb and bRc we get aRc. Hence, it is transitive. =b ...(3.7.4)
Therefore, we can say that (A, R) is poset. Its Hasse diagram is : From eq. (3.7.3) and (3.7.4), (a b) (b c) = (a b) (a c) = b.
1
Que 3.8.
2
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
4
distributive. AKTU 2016-17, Marks 10
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 Answer
not a lattice. a.
1 2 3 4 1. The theorem is true if the subset has 1 element, the element being
1 1 1 1 its own glb and lub.
2 2 2 2. It is also true if the subset has 2 elements.
3 1 2 3 1 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 1 1 4
4. If L contains more than k elements, consider the subset
iii. Only one edge (4, 2) is included to make it total order. {a1, a2, ..., ak + 1} of L.
iv. Maximals are {1, 2} and minimals are {3, 4}. 5. Let w = lub (a1, a2, ..., ak).
6. Let t = lub (w, ak + 1).
Que 3.7. In a lattice if a b c, then show that
7. If s is any upper bound of a1, a2, ..., ak + 1, then s is each of a1, a2, ...,
a. ab=bc ak and therefore s w.
b. (a b) (b c) = (a b) (a c) = b AKTU 2016-17, Marks 10 8. Also, s ak + 1 and therefore s is an upper bound of w and ak + 1.
9. Hence s t.
Answer 10. That is, since t each a1, t is the lub of a1, a2, ..., ak + 1.
a. Given : a b c 11. The theorem follows for the lub by finite induction.
3–8 C (CS/IT-Sem-3) Lattices and Boolean Algebra Discrete Structures & Theory of Logic 3–9 C (CS/IT-Sem-3)
12. If L is finite and contains m elements, the induction process stops (P(S), ) is not a lattice because ({a, b},{b, d}) has no lub and glb.
when k + 1 = m.
Que 3.10. Explain modular lattice, distributive lattice and bounded
b.
1. The diamond is modular, but not distributive. lattice with example and diagram. AKTU 2017-18, Marks 10
2. Obviously the pentagon cannot be embedded in it.
3. The diamond is not distributive : Answer
y (x z) = y (y x) (y z) = 1 Modular distributive and bounded lattice : Refer Q. 3.2, Page 3–2C,
4. The distributive lattices are closed under sublattices and every Unit-3.
sublattice of a distributive lattice is itself a distributive lattice. Example :
5. If the diamond can be embedded in a lattice, then that lattice has a Let consider a Hasse diagram :
non-distributive sublattice, hence it is not distributive. 1
Que 3.12. For any positive integer D36, then find whether (D36, ‘|’)
Fig. 3.9.1. is lattice or not ? AKTU 2017-18, Marks 07
3–10 C (CS/IT-Sem-3) Lattices and Boolean Algebra Discrete Structures & Theory of Logic 3–11 C (CS/IT-Sem-3)
4. Complement laws :
Answer
a. a + a = 1 b. a.a = 0
D36 = Divisor of 36 = {1, 2, 3, 4, 6, 9, 12, 18, 36}
Basic theorems :
Hasse diagram :
(1 3) = {3, 6}, (1 2) = {2, 4}, (2 6) = {6, 18}, (9 4) = {} Let a, b, c B, then
36
1. Idempotent laws :
12 12 a. a+a=a b. a.a = a
2. Boundedness (Dominance) laws :
6
4 9 a. a+1=1 b. a.0 = 0
3. Absorption laws :
2 3
a. a + (a.b) = a b. a.(a + b) = a
1
Since, 9 4 = {} 4. Associative laws :
So, D36 is not a lattice. a. (a + b) + c = a + (b + c) b. (a.b).c = a.(b.c)
5. Uniqueness of complement :
PART-2 a + x = 1 and a.x = 0, then x = a
Boolean Algebra : Introduction, Axioms and Theorems of 6. Involution law : (a) = a
Boolean Algebra.
7. a. 0 = 1 b. 1 = 0
8. De-Morgan’s laws :
Questions-Answers a. (a + b) = a.b b. (a.b) = a + b
Long Answer Type and Medium Answer Type Questions Que 3.14. Prove the following theorems :
a. Absorption law : Prove that a, b, B
i. a.(a + b) = a ii. a + a.b = a
Que 3.13. What is Boolean algebra ? Write the axioms of Boolean
b. Idempotent law : Prove that a B, a + a = a and a.a = a.
algebra. Also, describe the theorems of it. c. De Morgan’s law : Prove that a, b, B
i. (a + b) = a.b ii. (a. b) = a + b
Answer d. Prove that 0 = 1 and 1 = 0.
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 Answer
and () is unary operation in B. The elements 0 and 1 are zero (least) and unit a. Absorption law :
(greatest) elements of lattice (B, +, .). B is called a Boolean algebra if the i. To prove : a.(a + b) = a
following axioms are satisfied for all a, b, c in B. Let a.(a + b) = (a + 0).(a + b) by Identity law
Axioms of Boolean algebra : = a + 0.b by Distributive law
= a + b.0 by Commutative law
If a, b, c B, then
= a+0 by Dominance law
1. Commutative laws : = a by Identity law
a. a+b=b+a b. a.b = b.a ii. To prove : a + a.b = a
2. Distributive laws : Let a + a.b = a.1 + a.b by Identity law
= a.(1 + b) by Distributive law
a. a + (b.c) = (a + b).(a + c) b. a.(b + c) = (a.b) = (a.c) = a.(b + 1) by Commutative law
3. Identity laws : = a.1 by Dominance law
a. a+0=a b. a.1 = a = a by Identity law
3–12 C (CS/IT-Sem-3) Lattices and Boolean Algebra Discrete Structures & Theory of Logic 3–13 C (CS/IT-Sem-3)
b. Idempotent law :
To prove : a + a = a and a.a = a Que 3.15. Define Boolean algebra. Show that in a Boolean algebra
Let a= a+0 by Identity law meet and join operations are distributive to each other.
= a + a. a by Complement law
= (a + a).(a + a) by Distributive law Answer
= (a + a).1 by Complement law Boolean algebra : Refer Q. 3.10, Page 3–10C, Unit-3.
= a+a by Identity law
Meet and join operations are distributive :
Now let a = a.1 by Identity law
= a.(a + a) by Complement law 1. Let L be a poset under an ordering . Let a, b L.
= a.a + a.a by Distributive law 2. We define :
= a.a + 0 by Complement law a b (read “a join b”) as the least upper bound of a and b, and
= a.a by Identity law
a b(read “a meet b”) as greatest lower bound of a and b.
c. De Morgan’s law :
i. To prove : (a + b) = a.b 3. Since the join and meet operation produce a unique result in all cases
To prove the theorem we will show that where they exist, we can consider them as binary operations on a set if
(a + b) + a.b = 1 they always exist.
Consider (a + b) + a.b = {(a + b) + a}.{(a + b) + b}by Distributive law 4. A lattice is a poset L (under ) in which every pair of elements has a lub
= {(b + a) + a}.{(a + b) + b} and a glb.
by Commutative law 5. Since a lattice L is an algebraic system with binary operations and , it
= {b + (a + a)}.{a + (b + b)} is denoted by [L, , ].
by Associative law
= (b + 1).(a + 1) by Complement law 6. Let us consider,
a. [P(A), , ] is a lattice for any set A and
= 1.1 by Dominance law
b. The join operation is the set operation of union and the meet
=1 ...(3.14.1)
Also consider (a + b).ab = ab.(a + b) by Commutative law operation is the operation of intersection; that is, = and = .
= ab.a + ab.b by Distributive law 7. It can be shown that the commutative laws, associative laws, idempotent
= a.(ab) + a.(b b) by Commutative law laws, and absorption laws are all true for any lattice.
= (a. a).b + a(b. b) by Associative law 8. An example of this is clearly [P(A); , ], since these laws hold in the
= 0. b + a.0 by Complement law algebra of sets.
= b.0 + a.0 by Commutative law
9. This lattice is also distributive such that join is distributive over meet
= 0+0 by Dominance law
and meet is distributive over join.
=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. PART-3
ii. To prove : (a. b) = a + b Algebraic Manipulation of Boolean Expressions, Simplification
Follows from principle of duality, that is, interchange operations + and • of Boolean Functions, Karnaugh Maps.
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 Questions-Answers
= a + a by Involution law
= a + a by Commutative law Long Answer Type and Medium Answer Type Questions
=1 by Complement law
Now (0) = 1
0 = 1 Que 3.16. Express each Boolean expression as SOP and then in its
1 = 0. complete sum-of-products form.
3–14 C (CS/IT-Sem-3) Lattices and Boolean Algebra Discrete Structures & Theory of Logic 3–15 C (CS/IT-Sem-3)
Answer Answer
a. E = x.x.y + x.x.y + x.y.z = x.y + x.y.z = x.y' a. f(x, y, z) = (0, 1, 5, 7)
( x.x.y = 0 and x.y is contained in x.y.z) z
xy 0 1
Complete SOP form = x.y (z + z) ( z is missing) 00 0 1
= x.y.z + x.y. z 01 2 3
b. E = z.(x+ y) + y = x.z + y.z + y
11 6 7
Then E = x.z(y + y) + y.z.(x + x) + y.(x + x) (z + z) f=xy+xz
10 4 5
(by Complement law)
= x.y.z + x.y.z + x.y.z + x.y.z + x.y.z + x.z.y Fig. 3.18.1.
+ x.y.z+ x.y.z b. f (x, y, z) = (1, 2, 3, 6, 7)
yz
= x.y.z + x.y.z + x.y.z + x.y.z + x.y.z + x.y.z x 00 01 11 10
0 0 1 3 2
Que 3.17. Define a Boolean function of degree n. Simplify the
1 4 5 7 6
following Boolean expression using Karnaugh maps
Fig. 3.18.2.
xyz + xy'z + x'y'z + x'yz + x'y'z'
f= xz+y
Answer
Que 3.19. Simplify the following Boolean function using K-map :
Boolean function of degree n :
F(x, y, z) = (0, 2, 3, 7)
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. AKTU 2017-18, Marks 07
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. Answer
yz
3. A function from Bn to B is called a Boolean function of degree n. x 00 01 11 10
4. For example, the function F(x, y) = xy from the set of ordered pairs of 0 1 1 1
Que 3.18. Simplify the following Boolean functions using three = ((AB)) (A + (AB))
= AB (A (A + B))
Que 3.22. Find the Sum-Of-Products and Product-Of-s um
= AB (AA + AB)
expansion of the Boolean function F(x, y, z) = (x + y) z.
= AB(0 + AB) = AB AB
AKTU 2018-19, Marks 07
= ABB
=0 Answer
Here, we find that the expression is not in minterm. For getting minterm, F(x, y, z) = (x + y)z
we simplify and find that its value is already zero. Hence, no need to use
K-map for further simplification. x y z x+y z (x + y)z
b. A B C D + A B C D + A B CD + A B CD = A B 1 1 1 1 0 0
= A BCD + ABCD + ABCD + ABCD 1 1 0 1 1 1
CD AB 1 0 1 1 0 0
A B C D 1 1 0 0 1 1 1
A B C D 1
0 1 1 1 0 0
AB CD 1
0 1 0 1 1 1
AB CD 1
0 0 1 0 0 0
Fig. 3.20.1.
0 0 0 0 1 0
On simplification by K-map, we get AB corresponding to all the four
one’s. Sum-Of-Product :
F(x, y, z) = xyz + xyz + xyz
Que 3.21. Find the Boolean algebra expression for the following
Product-Of-Sum :
F(x, y, z) = (x + y + z)(x + y+ z)(x+ y + z)(x+ y+ z)
system. AKTU 2016-17, Marks 7.5
(x+ y+ z')
A
B
C PART-4
Logic Gates, Digital Circuits and Boolean Algebra.
Questions-Answers
Fig. 3.21.1.
Long Answer Type and Medium Answer Type Questions
Answer
A ABC
B Que 3.23. Consider the Boolean function.
C ABC + A(B + C )
A.(B + C )
B a. f(x1, x2, x3, x4) = x1 + (x2. (x1 + x4) + x3. (x2 + x4))
B + C i. Simplify f algebraically
ii. Draw the logic circuit of the f and the reduction of the f.
C
b. Write the expres sions E 1 = (x + x * y) + (x/y) and
Fig. 3.21.2.
E2 = x + ((x * y + y)/y), into
3–18 C (CS/IT-Sem-3) Lattices and Boolean Algebra Discrete Structures & Theory of Logic 3–19 C (CS/IT-Sem-3)
/
Answer x
y
a. i. f(x1, x2, x3, x4) = x1 + (x2.(x1 + x4) + x3.(x2+ x4) +
= x1 + x2.x1 + x2.x4 + x3.x2 + x3.x4 y
*
= x1 + x2 + x2.x4 + x3.x2 + x3.x4
y
= x1 + x2.(1 + x4) + x3.x2 + x3.x4 x
Fig. 3.23.3.
= x1 + x2 + x3.x2 + x3.x4
= x1 + x2 + x3 + x3.x4 Prefix : + x / + * x y y y
Postfix : x x y * y + y / +
= x1 + x2 + x3.(1 + x4)
= x1 + x2 + x3 Que 3.24. Construct circuits that produce the following output :
ii. Logic circuit :
F(X, Y, Z) = (X + Y + Z) ( XYZ )
x1 x1 + x2 + x3
x2
x3 Answer
The logic network is shown below :
Fig. 3.23.1.
Reduction of f : X X+Y+Z
f (x1, x2, x3, x4) = x1 + (x2.(x1 + x4) + x3.(x2 + x4) Y
Z
= x1 + (x2.x1 + x2.x4) + (x3.x2 + x3.x4)
= x1 + x2.x1 + x2.x4 + x3.x2 + x3.x4 (X + Y + Z) X Y Z
b. E1 = (x + x * y) + (x/y)
Binary tree is : X
X
Y XYZ
+ Y
Z
+ / Z
Fig. 3.24.1.
x * x y
XY Z + XYZ + XY
Z
Z X YZ
3 4
XY
Fig. 2.
i. Verify that (A, R) is a poset and find its Hasse diagram.
Fig. 3.25.2. ii. Is this a lattice ?
iii. How many more edges are needed in the Fig. 2 to extend
(A, R) to a total order ?
VERY IMPORTANT QUESTIONS iv. What are the maximal and minimal elements ?
Ans. Refer Q. 3.6.
Following questions are very important. These questions
may be asked in your SESSIONALS as well as Q. 5. In a lattice if a b c, then show that
UNIVERSITY EXAMINATION. a. a b = b c
b. (a b) (b c) = (a b) (a c) = b
Ans. Refer Q. 3.7.
Q. 1. If the lattice is represented by the Hasse diagram given
below : Q. 6.
i. Find all the complements of ‘e’. a. Prove that every finite subset of a lattice has an LUB and a
ii. Prove that the given lattice is bounded complemented GLB.
lattice. b. Give an example of a lattice which is a modular but not a
b distributive.
c Ans. Refer Q. 3.8.
a
Q. 7. Show that the inclusion relation is a partial ordering on
the power set of a set S. Draw the Hasse diagram for
f d inclusion on the set P(S), where S = {a, b, c, d}. Also determine
e whether (P(S), ) is a lattice.
Fig. 1. Ans. Refer Q. 3.9.
3–22 C (CS/IT-Sem-3) Lattices and Boolean Algebra Discrete Structures & Theory of Logic 4–1 C (CS/IT-Sem-3)
4
lattice with example and diagram.
Ans. Refer Q. 3.10.
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. Propositional Logic
Ans. Refer Q. 3.11.
and Predicate Logic
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.
4–2 C (CS/IT-Sem-3) Propositional Logic & Predicate Logic Discrete Structures & Theory of Logic 4–3 C (CS/IT-Sem-3)
Table. 4.2.1.
PART-1 S. No. Connective words Name of connective Symbol
Propositional Logic : Proposition, Well Formed Formula,
1. Not Negation ~ or or –
Truth Tables.
2. And Conjunction
3. Or Disjunction
Questions-Answers
4. If-then Implication
Long Answer Type and Medium Answer Type Questions
5. If and only if Biconditional
iv. Converse
Que 4.3. What do you mean by well formed formula ?
v. Contrapositive AKTU 2014-15, Marks 10
Answer OR
1. Well formed formula is defined as a mathematical expression Define inverse.
represented in well defined form and uses parenthesis, braces and
Answer
square brackets to avoid the ambiguity.
i. Conjunction : If p and q are two statements, then conjunction of p and
2. Logical statements are also represented in well defined form using
q is the compound statement denoted by p q and read as
parenthesis according to priority of operations. To generate well formed
“p and q”. Its truth table is,
formula recursively, following rules are used :
i. An atomic statement P is a well formed formula. p q pq
ii. If P is well formed formula then ~ P is also a well formed. T T T
If P and Q are well formed formulae then (P Q), (P Q), (P Q)
iii. T F F
and (P Q) are also well formed formulae.
F T F
iv. A statement consists of variables, parenthesis and connectives is
recursively a well formed formula iff it can be obtained by applying F F F
the above three rules. Example :
For example :
1. (P (P Q) p : Ram is healthy.
2. ((P Q) R) q : He has blue eyes.
Que 4.4. Write short notes on : p q : Ram is healthy and he has blue eyes.
i. Truth table ii. Logical equivalence 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
Answer or q”. Its truth table is,
i. Truth table : A truth table is a table that shows the truth value of a
compound proposition for all possible cases. p q pq
p q (p q) p q (p q) p ~p T T T
T T T T T T T F T F T
F T T
T F F T F T F T
F F F
F T F F T T
F F F F F F Example :
ii. Logical equivalence : If two propositions P (p, q, .....) and Q (p, q, ...) p : Ram will go to Delhi.
where p, q, ..... are propositional variables, have the same truth values q : Ram will go to Calcutta.
in every possible case, the propositions are called logically equivalent or
simply equivalent, and denoted by p q : Ram will go to Delhi or Calcutta.
P (p, q, .......) Q (p, q, ........) iii. Conditional : If p and q are propositions. The compound proposition if
Que 4.5. Explain the following terms with suitable example : 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,
i. Conjunction
ii. Disjunction
iii. Conditional
4–6 C (CS/IT-Sem-3) Propositional Logic & Predicate Logic Discrete Structures & Theory of Logic 4–7 C (CS/IT-Sem-3)
4. Distributive laws : p q
a. p (q r) (p q) (p r) ~q
b. p (q r) (p q) (p r) ~p
5. Identity laws : 3. Hypothetical syllogism : By this rule whenever the two implications
a. p F p p q and q r are true then the implication p r is also true.
b. p T T The argument is of the form :
c. p F F
p q
d. p T p
q r
6. Complement laws :
p r
a. p ~P T
4. Disjunctive syllogism : By this rule if the premises p q and ~ q are
b. p ~p F true then p is true.
c. ~T F The argument is of the form :
d. ~F T p q
7. Involution law : ~q
a. ~(~p) p p
8. De Morgan's laws : 5. Addition : By this rule if p is true then p q is true regardless the truth
a. ~ (p q) ~p ~q value of q.
The argument is of the form :
b. ~ (p q) ~p ~q
p
9. Absorption laws :
p q
a. p (p q) p
6. Simplification : By this rule if p q is true then p is true.
b p (p q) p The argument is of form :
These laws can easily be verified using truth table. p q p q
Que 4.8. Discuss theory of inference in propositional logic. p or q
7. Conjunction : By this rule if p and q are true then p q is true.
Answer The argument is of the form :
Rules of inference are the laws of logic which are used to reach the given p
conclusion without using truth table. Any conclusion which can be derived q
using these laws is called valid conclusion and hence the given argument is p q
valid argument.
8. Constructive dilemma : By this rule if (p q) (r s) and p r are
1. Modus ponens (Law of detachment) : By this rule if an implication true then q s is true.
p q is true and the premise p is true then we can always conclude that The argument is of form :
q is also true. ( p q) ( r s)
The argument is of the form : p r
p q q s
p 9. Destructive dilemma : By this rule if (p q) (r s) and ~ q s
q are true.
2. Modus tollens (Law of contraposition) : By this rule if an implication The argument is of the form :
p q is true and conclusion q is false then the premise p must be false.
The argument is of the form :
4–10 C (CS/IT-Sem-3) Propositional Logic & Predicate Logic Discrete Structures & Theory of Logic 4–11 C (CS/IT-Sem-3)
Answer Answer
i. We have Tautology, contradiction and contingency : Refer Q. 4.6, Page 4–7C,
((p q) ~ (~ p (~ q r))) (~ p ~ q) (~ p r) Unit-4.
((p q) ~ (~ p ~ (q r))) (~ (p q) ~ ( p r)) Proof : ((p q) (~ p r)) (q r)
(Using De Morgan's Law)
p q r ~P (p q) (~ p r) (A B) (q r) C D
[(p q)] (p (q r)) ~ ((p q) (p r))
[(p q) (p q) (p r)] ~ (( p q) (p r)) =A =B =C =D
(Using Distributive Law) F F F T F T T F F
[((p q) (p q)] (p r) ~ ((p q) (p r))
F F T T F T T T T
((p q) (p r)) ~ ((p q) (p r))
x ~ x where x = (p q) (p r) F T F T T T T T T
T F T T T T T T T 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)] T F F F T F T F F
T F T F T T T T T
Que 4.11. “If the labour market is perfect then the wages of all
T T F F T F T T T
persons in a particular employment will be equal. But it is always
the case that wages for such persons are not equal therefore the T T T F T T T T T
labour market is not perfect”. Test the validity of this argument So, ((p q) (~ p r)) (q r) is contingency.
using truth table. AKTU 2014-15, Marks 10
Que 4.13.
Answer i. Find a compound proposition involving the propositional
Let p1 : The labour market is perfect. variables p, q, r and s that is true when exactly three
p2 : Wages of all persons in a particular employment will be equal. propositional variables are true and is false otherwise.
~p2 : Wages for such persons are not equal. ii. Show that the hypothesis “It is not sunny this afternoon and it
~p1 : The labour market is not perfect. is colder than yesterday”, “We will go swimming only if it is
The premises are p1 p2 , ~ p2 and the conclusion is ~ p1. The argument 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
p1 p2, ~ p2 ~ p1 is valid if ((p1 p2) ~ p2) ~ p1 is a tautology.
Its truth table is, sunset” lead to the conclusion “We will be home by sunset.”
OR
p1 p2 ~p1 ~p2 p1 p2 (p1 p2) ~p2 (p1p2 ~ p2) ~p1 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,”
T T F F T F T “If we do not go swimming, then we will take a canoe trip.” and
T F F T F F T “If we take a canoe trip, then we will be home by sunset” lead to
the conclusion “We will be home by sunset.”
F T T F T F T
AKTU 2018-19, Marks 07
F F T T T T T
Answer
Since ((p1 p2) ~p2) ~p1 is a tautology. Hence, this is valid argument.
i. The compound proposition will be : (p q r) s
Que 4.12. What is a tautology, contradiction and contingency ?
ii. Let p be the proposition “It is sunny this afternoon”, q be the proposition
Show that (p q) ( p r) (q r) is a tautology, contradiction or “It is colder than yesterday”, r be the proposition “We will go swimming”,
contingency. AKTU 2018-19, Marks 07 s be the proposition ‘‘We will take a canoe trip’’, and t be the proposition
“We will be home by sunset”.
4–14 C (CS/IT-Sem-3) Propositional Logic & Predicate Logic Discrete Structures & Theory of Logic 4–15 C (CS/IT-Sem-3)
Answer Answer
Rule of inference is a logical form consisting of function which takes premises, a. Symbolic form :
analyzes their syntax and returns a conclusion. Let P(x): x is healthy and Q(x): x do all work
Rules of inference :
i. Universal specification : By this rule if the premise ( x) P (x) is true x(P(x) Q(x))
then P(c) is true where c is particular member of UD.
Negation : ( x (P(x) Q(x))
(x) P ( x)
b. Symbolic form :
P ( c)
Let P(x) : x is a person
ii. Universal generalization : By this rule if P(c) is true for all c in UD
then (x) P(x) is true. A(x, y) : x admires y
P ( c) The given statement can be written as “There is a person who is not
(x) P ( x) admired by some person” and it is (x) ( y)[P(x) P(y) A(x, y)]
x is not free in any of given premises. Negation : ( x) ( y) [P (x) P(y) A(x, y)]
iii. Existential specification : By this rule if (x) P(x) is true then P(x) is c. Symbolic form :
true for some particular member of UD.
Let N(x, y) : x and y are neighbours
(x) P ( x)
H(x, y) : x should help y
P (c)
P(x, y) : x will help y
c is some member of UD.
iv. Existential generalization : By this rule if P(c) is true for some The statement can be written as “For every person x and every person
particular member c in UD, then ( x) P (x) is true y, if x and y are neighbours, then either x should help y or y will not help
P ( c) x” and it is ( x) ( y)[N(x, y) (H(x, y) P(y, x))]
(x) P ( x) Negation : ( x) ( y) [N(x, y) (H (x, y) P (y, x))]
c is some member of UD.
v. Universal modus ponens : By this rule if P(x) Q(x) is true for every Que 4.18. Express the following statements using quantifiers and
x and P(c) is true for some particular member c in UD then Q(c) is true. logical connectives.
( x) P ( x) Q( x) a. Mathematics book that is published in India has a blue cover.
P (c) b. All animals are mortal. All human being are animal. Therefore,
Q(c) all human being are mortal.
c. There exists a mathematics book with a cover that is not blue.
vi. Universal modus tollens : By this rule if P(x) Q(x) is true for every d. He eats crackers only if he drinks milk.
x and ~ Q(c) is true for some particular c in UD then ~ Q(c) is true. e. There are mathematics books that are published outside India.
( x) P ( x) Q( x)
~ Q(c) f. Not all books have bibliographies. AKTU 2015-16, Marks 10
~ P (c) Answer
Que 4.17. Write the symbolic form and negate the following a. P(x) : x is a mathematic book published in India
statements : Q(x) : x is a mathematic book of blue cover
a. Everyone who is healthy can do all kinds of work. x P(x) Q(x).
b. Some people are not admired by everyone.
c. Everyone should help his neighbours, or his neighbours will b. P(x) : x is an animal
Q(x) : x is mortal
not help him. AKTU 2016-17, Marks 10
x P(x) Q(x)
4–18 C (CS/IT-Sem-3) Propositional Logic & Predicate Logic Discrete Structures & Theory of Logic 4–19 C (CS/IT-Sem-3)
Que 4.19.
VERY IMPORTANT QUESTIONS
i. Express this statement using quantifiers : “Every student in
this class has taken some course in every department in the Following questions are very important. These questions
school of mathematical sciences”. may be asked in your SESSIONALS as well as
ii. If x yP( x , y) is true, does it necessarily follow that yP( x , y) is UNIVERSITY EXAMINATION.
true ? Justify your answer.
5
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 Trees, Graph and
sunset.” UNIT
Ans. Refer Q. 4.13. Combinatorics
Q. 6. Show that : (r ~ q, r S, S ~ q, p q) ~ p are
inconsistent.
Ans. Refer Q. 4.14.
Q. 8. Express the following statements using quantifiers and Part-3 : Binary Search Tree ................................. 5–8C to 5–12C
logical connectives.
a. Mathematics book that is published in India has a blue Part-4 : Graphs : Definition ................................ 5–12C to 5–15C
cover. and Terminology
b. All animals are mortal. All human being are animal. Representation of Graph
Therefore, all human being are mortal.
c. There exists a mathematics book with a cover that is not Part-5 : Multigraph Bipartite .............................. 5–15C to 5–24C
Graphs, Planar Graph
blue.
Isomorphism and
d. He eats crackers only if he drinks milk.
Homomorphism of Graphs
e. There are mathematics books that are published outside
India. Part-6 : Graph Coloring ....................................... 5–24C to 5–24C
f. Not all books have bibliographies.
Ans. Refer Q. 4.18. Part-7 : Recurrence Relation and ..................... 5–24C to 5–36C
Generating Function :
Q. 9. Translate the following sentences in quantified expressions Recursive Definition of
of predicate logic. Function, Recursive
i. All students need financial aid. Algorithms, Method of Solving
ii. Some cows are not white. Recurrences, Combinatorics :
iii. Suresh will get if division if and only if he gets first div. Introduction, Counting Techniques,
iv. If water is hot, then Shyam will swim in pool. Pigeonhole Principle
v. All integers are either even or odd integer.
Ans. Refer Q. 4.20.
5–2 C (CS/IT-Sem-3) Trees, Graph and Combinatorics Discrete Structures & Theory of Logic 5–3 C (CS/IT-Sem-3)
Questions-Answers
b c
Long Answer Type and Medium Answer Type Questions
d e
h i
b c
d j k
Fig. 5.1.1. e f
l
ii. Forest : A forest is a collection of disjoint tree. It is an undirected, g h
disconnected, acyclic graph. i
Fig. 5.2.1.
Answer
i. The node a is the root node. Questions-Answers
ii. The node g, h, i, j and l are leaves.
Long Answer Type and Medium Answer Type Questions
iii. Nodes Parent node
b, c a
d b Que 5.3. Define preorder, inorder, and postorder tree traversal.
j, k c
e, f d Give an example of preorder, postorder, and inorder traversal of a
g, h e binary tree of your choice with at least 12 vertices.
i f OR
l k Explain in detail about the binary tree traversal with an example.
AKTU 2016-17, Marks 10
iv. Nodes Children
a b, c Answer
b d
Tree traversal : A traversal of tree is a process in which each vertex is
c j, k
visited exactly once in a certain manner. For a binary tree we have three
d e, f
e g, h types of traversal :
f i 1. Preorder traversal : Each vertex is visited in the following order :
k l a. Visit the root (N).
v. b and c b. Visit the left child (or subtree) of root (L).
e and f c. Visit the right child (or subtree) of root (R).
g and h 2. Postorder traversal :
a. Visit the left child (subtree) of root.
j and k
b. Visit the right child (subtree) of root.
vi. Nodes Depth c. Visit the root.
3. Inorder traversal :
a 1
b, c 2 a. Visit the left child (subtree) of root.
d, j, k 3 b. Visit the root.
e, f, l 4 c. Visit the right child (subtree) of root.
g, h, i 5 A binary tree with 12 vertices :
Answer
E R
Root is G. Fig. 5.4.4.
G Que 5.5. Define a binary tree. A binary tree has 11 nodes. It’s
inorder and preorder traversals node sequences are :
Fig. 5.4.1.
Preorder : A B D H I E J L C F G
Element to left of G in inorder traversal are Q B A and B comes first in Inorder : H D I B J E K A F C G
preorder traversal. Therefore tree will be
Draw the tree. AKTU 2018-19, Marks 07
G
Answer
Binary tree : Refer Q. 5.1(iii), Page 5–2C, Unit-5.
B 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
Q A and right sides of ‘A’.
Fig. 5.4.2. A
Now elements on the right of G in inorder traversal are CPEDR and P comes HDIBJEK FCG
first. Therefore tree will be
Step 2 : We recursively follow the above steps and we get
A
G
B C
A
B P
B C D E F G
Q A HDI JEK F G H I J K
Fig. 5.4.3.
Que 5.6. Given the inorder and postorder traversal of a tree T :
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 Inorder : HFEABIGDC Postorder : BEHFACDGI
respectively. Determine the tree T and it's Preorder. AKTU 2017-18, Marks 07
5–8 C (CS/IT-Sem-3) Trees, Graph and Combinatorics Discrete Structures & Theory of Logic 5–9 C (CS/IT-Sem-3)
Answer Answer
The root of tree is I. Binary search tree :
I 1. A binary search tree is a binary tree T in which data is associated with
Now elements on right of I are D, G, C and G comes last of all in postorder the vertices.
traversal. 2. The data are arranged so that, for each vertex v in T, each data item in
I the left subtree of v is less than the data item in v and each data item
G in the right subtree of v is greater than the data item in v.
Now D and C are on right of G and D comes last of G and I postorder 3. The binary tree T in Fig. 5.7.1, is a binary search tree since every
traversal so vertex in T exceeds every number in its left subtree and is less than
every number in its right subtree.
I
G
50
D
40 70
C
Que 5.7. What is a binary search tree ? Form a binary search nuthatch
tree for the words vireo, warbler, egret, grosbeak, nuthatch, and
kingfisher
kingfisher. Explain each step.
5–10 C (CS/IT-Sem-3) Trees, Graph and Combinatorics Discrete Structures & Theory of Logic 5–11 C (CS/IT-Sem-3)
3. Insert 63 :
Que 5.8. Write algorithm for following :
55
i. Searching and inserting a node in BST
ii. Deleting a node in BST
20 63
Answer 4. Insert 10 :
i. Searching and inserting a node in BST : 55
Consider a binary search tree T and we have to insert or search an ITEM in
the tree. 20 63
9. Insert 11 :
Questions-Answers
55
10 28 60 93 Que 5.10. What do you mean by graph ? Also, explain directed and
undirected graph.
5 11
Answer
10. Insert 40 :
A graph is a non-linear data structure consisting of nodes and edges. A graph
55 consists of two sets as follows :
1. Set V of nodes or point or vertices of graph G.
20 63
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).
10 28 60 93
For example :
V4 c V3
5 11 40 e
d b
11. Insert 68 :
V1 V2
55 a
Fig. 5.10.1.
20 63
Order : If G is finite then number of vertices in G denoted by |V (G)| is
called order of G.
10 28 60 93 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
5 11 40 68 each edge e E is associated with an ordered pair of vertices as shown
12. Insert 25 : below :
c
55
20 63
a b
10 28 60 93 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 :
5 11 25 40 68 a b
PART-4
Graphs : Definition and Terminology, Representation of Graph. c d
Fig. 5.10.3.
5–14 C (CS/IT-Sem-3) Trees, Graph and Combinatorics Discrete Structures & Theory of Logic 5–15 C (CS/IT-Sem-3)
c. Bipartite graph The graphs shown in Fig. 5.12.4 are 2-regular graphs.
d. Planar graph The graph shown in Fig. 5.12.5 is 3-regular graph.
Answer
a. Simple and multigraph :
i. Simple graph : A graph in which there is only one edge between
Fig. 5.12.5.
a pair of vertices is called a simple graph.
c. Bipartite graph :
e
i. Bipartite graph : A graph G = (V, E) is bipartite if the vertex set
V1 V2 V can be partitioned into two subsets (disjoint) V1 and V2 such that
Fig. 5.12.1. 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).
ii. Multigraph : Any graph which contains some parallel edges is
(V1, V2) is called a bipartition of G.
called a multigraph.
e3 x1 x2 x3 x1 x2 x3 x4
V4 V3 which
x4
redrawn
e4 e2 as :
y1 y2 y3 y1 y2 y3
V1 V2
e1 Fig. 5.12.6. Some bipartite graphs.
Fig. 5.12.2.
ii. Complete bipartite graph : The complete bipartite graph on m
b. Complete graph and regular graph : and n vertices, denoted Km, n is the graph, whose vertex set is
i. Complete graph : A simple graph, in which there is exactly one partitioned into sets V1 with m vertices and V2 with n vertices in
edge between each pair of distinct vertices is called a complete which there is an edge between each pair of vertices 1 and 2
graph. The complete graph of n vertices is denoted by Kn. The where 1 is in V1 and 2 is in V2. The complete bipartite graphs
graphs K1 to K5 are shown below in Fig. 5.12.3. K2,3, K2,4, K 3,3, K3,5, and K2,6
(a) (b ) (c )
Fig. 5.14.2.
(a) (b )
Fig. 5.12.8. Some planar graph. Que 5.15. Prove that K3 and K4 are planar graphs. Prove that K5 is
i. Refer Q. 5.12(c), Page 5–15C, Unit-5. Similarly complete K4 graph has 4 vertices and 6 edges.
iii. Number of edge in K7 : Since, Kn is complete graph with n vertices. K4 is planar graph
The complete K5 graph contains 5 vertices and 10 edges.
7(7 1) 7 6
Number of edge in K7 = = 21 Now 3 – e = 3 × 5 – 10 = 15 – 10 = 5 6
2 2
Hence K5 is non planar since for a graph to be planar 3v – e 6.
Number of edge in K3, 6 :
Since, Kn, m is a complete bipartite graph with n V1 and m V2 Que 5.16. What are Euler and Hamiltonian graph ?
Number of edge in K3, 6 = 3 × 6 = 18 OR
iv. Refer Q. 5.15(d), Page 5–18A, Unit-5. Explain the following terms with example :
i. Homomorphism and Isomorphism graph
Que 5.14. Explain isomorphism and homomorphism of graph. ii. Euler graph and Hamiltonian graph
iii. Planar and Complete bipartite graph
Answer AKTU 2014-15, Marks 10
Isomorphism of graph : Two graphs are isomorphic to each other if :
Answer
i. Both have same number of vertices and edges.
ii. Degree sequence of both graphs are same (degree sequence is the i. Refer Q. 5.14, Page 5–18C, Unit-5.
sequence of degrees of the vertices of a graph arranged in non-increasing ii. Eulerian path : A path of graph G which includes each edge of G
order). exactly once is called Eulerian path.
Eulerian circuit : A circuit of graph G which include each edge of G exactly
Example : 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
Fig. 5.14.1. V2
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., V5 V4 D C
by insertion of vertices of degree two) or by the merger of edges in series. Fig. 5.16.1.
5–20 C (CS/IT-Sem-3) Trees, Graph and Combinatorics Discrete Structures & Theory of Logic 5–21 C (CS/IT-Sem-3)
Hamiltonian graph : A Hamiltonian circuit in a graph G is a closed path 4. If we travel along the trail then each time we visit a vertex. We use
that visit every vertex in G exactly once except the end vertices. A graph G is two edges, one in and one out.
called Hamiltonian graph if it contains a Hamiltonian circuit. 5. This is also true for the start vertex because we also end there.
For example : Consider graphs given below : 6. Since an Eulerian trail uses every edge once, the degree of each
D C D C vertex must be a multiple of two and hence there are no vertices of
F odd degree.
7. Now we shall prove that if a non-empty connected graph has no
E vertices of odd degree then it is Eulerian.
A B A B
(a) (b ) 8. Let every vertex of G have even degree.
Fig. 5.16.2.
9. We will now use a proof by mathematical induction on |E(G)|, the
Graph given is Fig. 5.16.2(a) is a Hamiltonian graph since it contains a number of edges of G.
Hamiltonian circuit A – B – C – D – A while graph in Fig 5.15.2(b) is not a
Basis of induction :
Hamiltonian graph.
Let |E(G)| = 0, then G is the graph K1, and G is Eulerian.
Hamiltonian path : The path obtained by removing any one edge from a
Hamiltonian circuit is called Hamiltonian path. Hamiltonian path is subgraph Inductive step :
of Hamiltonian circuit. But converse is not true. 1. Let P(n) be the statement that all connected graphs on n edges of
even degree are Eulerian.
The length of Hamiltonian path in a connected graph of n vertices is
n – 1 if it exists. 2. Assume P(n) is true for all n < |E(G)|.
iii. Refer Q. 5.12, Page 5–15C, Unit-5. 3. Since each vertex has degree at least two, G contains a cycle C.
4. Delete the edges of the cycle C from G.
Que 5.17.
5. The resulting graph, G say, may not be connected.
a. Prove that a connected graph G is Euler graph if and only if
6. However, each of its components will be connected, and will have
every vertex of G is of even degree.
fewer than |E(G)| edges.
b. Which of the following simple graph have a Hamiltonian circuit
7. Also, all vertices of each component will be of even degree, because
or, if not a Hamiltonian path ? AKTU 2016-17, Marks 15 the removal of the cycle either leaves the degree of a vertex
unchanged, or reduces it by two.
a b a b a b g
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,
e c d c
d c e
f c1 say, of one of the components of G .
10. We then traverse that component’s Eulerian trail, finally returning
d
to the cycle C at the same vertex, c1.
G1 G2 G3 11. We then continue along the cycle C, traversing each component of
G as it meets the cycle.
Fig. 5.17.1.
12. Eventually, this process traverses all the edges of G and arrives
back at u, thus producing an Eulerian trail for G.
Answer
13. Thus, G is Eulerian by the principle of mathematical induction.
a.
b. G1 : The graph G1 shown in Fig. 5.17.1 contains Hamiltonian circuit, i.e.,
1. First of all we shall prove that if a non-empty connected graph is
a – b – c – d – e – a and also a Hamiltonian path, i.e., abcde.
Eulerian then it has no vertices of odd degree.
G2 : The graph G2 shown in Fig. 5.17.1 does not contain Hamiltonian
2. Let G be Eulerian.
circuit since every cycle containing every vertex must contain the edge
3. Then G has an Eulerian trail which begins and ends at u. 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 Discrete Structures & Theory of Logic 5–23 C (CS/IT-Sem-3)
i 1 j 1
n2 + k2 – 2nk
i j
3. Adjacency matrix of a graph AKTU 2017-18, Marks 07
k
or (n
i 1
i 1)2 + 2(non-negative terms) = n2 + k2 – 2nk Answer
1. Breadth First Search (BFS) : Breadth First Search (BFS) is an
[ ni – 1 0, nj – 1 0]
algorithm for traversing or searching tree or graph data structures. It
k
or (n
i 1
i 1)2 n2 + k2 – 2nk starts at the tree root and explores the neighbour nodes first, before
moving to the next level neighbours.
k k k Algorithmic steps :
or n 1 2 n
i 1
2
i
i 1 i 1
i n2 + k2 – 2nk Step 1 : Push the root node in the queue.
Step 2 : Loop until the queue is empty.
k Step 3 : Remove the node from the queue.
or n
i 1
2
i k 2n n2 + k2 – 2nk Step 4 : If the removed node has unvisited child nodes, mark them as
k
visited and insert the unvisited children in the queue.
or n 2
i n n2 + k2 – 2nk – k + n Depth First Search (DFS) :
i 1 Depth First Search (DFS) is an algorithm for traversing or searching
= n(n – k + 1) – k (n – k + 1) tree or graph data structures. One starts at the root (selecting some
= (n – k)(n – k + 1) ...(5.18.1) arbitrary node as the root in the case of a graph) and explores as far as
We know that the maximum number of edges in the ith component of possible along each branch before backtracking.
Algorithmic steps :
ni ni (ni 1)
G= C2 = Step 1 : Push the root node in the stack.
2 Step 2 : Loop until stack is empty.
Therefore, the maximum number of edges in G is : Step 3 : Pick the node of the stack.
n n n
1 1 1 Step 4 : If the node has unvisited child nodes, get the unvisited child
2
ni (ni 1) = 2 2
i i =
2
2
i n node, mark it as traversed and push it on stack.
5–24 C (CS/IT-Sem-3) Trees, Graph and Combinatorics Discrete Structures & Theory of Logic 5–25 C (CS/IT-Sem-3)
Step 5 : If the node does not have any unvisited child nodes, pop the recurrence relation. Recurrence relations are also called difference equations
node from the stack. because they can be written in terms of the difference between the
2. Refer Q. 5.16, Page 5–19C, Unit-5. consecutive terms of a sequence.
3. Refer Q. 5.11, Page 5–14C, Unit-5. For example : ar = 4ar – 1 r1
ar = ar – 1 – 2ar – 2 r2
PART-6 are recurrence relations.
Graph Coloring. Order of recurrence relation : The difference between the highest and
lowest subscripts of ar or f(x) or yn is called the order of recurrence relation.
For example :
Questions-Answers 1. The equation 13ar + 12ar – 1 = 0 is of order 1 (i.e., r – (r – 1) = 1).
2. The equation 8 f(x) + 2 f(x + 1) + f(x + 2) = k(x) is of order 2
Long Answer Type and Medium Answer Type Questions (i.e., (x + 2) – x = 2).
Degree of recurrence relation : The highest power of ar or f(x) or yn is
called degree of recurrence relation.
Que 5.21. Write a short note on graph coloring.
For example :
1. The equation y3k + 2 + 2y2k + 1 – yk = 0 has the degree 3 as the highest
Answer
power of yk is 3.
1. Suppose that G (V, E) is a graph with no multiple edges, a vertex colouring
2. The equation a4r + 2a3r – 1 + 3a2r – 2 + 4ar – 3 = 0 has the degree 4, as the
of G is an assignment of colours.
highest power of ar is 4.
2. A graph G is m-colourable if there exists a colouring of G which uses m
colours. Que 5.23. What do you mean generating function ? Solve the
3. Colouring the vertices such a way such that no two adjacent vertices recurrence relation :
have same colour is called proper colouring otherwise it is called an = 2 an–1 – an–2, n 2 given a0 = 3, a1 = – 2
improper colouring. using generating function.
Answer
PART-7
Generating function : The generating function for the sequence a0, a1, ...
Recurrence Relation and Generating Function : Recursive ak, ... of real numbers is infinite series given by
Definition of Function, Recursive Algorithms, Method of
Solving Recurrences, Combinatorics : Introduction, G(x) = a0 + a1x + a2x2 + ...... + akxk + ...... = a x
k0
k
k
a x
n 2
n
n
= 2 an 1 x an 2 x
n2
n n
n 2
...(5.23.2)
Que 5.22. Write a short note on recurrence relation.
We know, G(x) = a
n 0
n x n a0 a1 x a2 x 2 a3 x3 ... ...(5.23.3)
b. These base values are used to define the other values of the function Number of integers divisible by (2 and 5) = 25
by using the function recursively. Number of integers divisible by (2 and 7) = 17
Example : ar = 3 ar–1, r 1, a0 = 1 Number of integers divisible by (3 and 5) = 16
then a1 = 3a0 = 3 Number of integers divisible by (3 and 7) = 11
a2 = 3a1 = 3 (3a0) = 32 a0 = 32 Number of integers divisible by (5 and 7) = 7
and so on. Number of integers divisible by (2, 3 and 5) = 8
ar = 3r, r 0
Number of integers divisible by (2, 3, and 7) = 5
ii. Pigeonhole principle :
Number of integers divisible by (2, 5, and 7) = 3
The pigeonhole principle is sometime useful in counting methods.
Number of integers divisible by (3, 5 and 7) = 2
If n pigeons are assigned to m pigeonholes then at least one pigeonhole ––––
contains two or more pigeons (m < n). 135
––––
Proof : Number of integers between 1 and 250 that are divisible by any of the
1. Let m pigeonholes be numbered with the numbers 1 through m. integer (2, 3, 5 and 7) = 293 – 135 = 158.
2. Beginning with the pigeon 1, each pigeon is assigned in order to the Que 5.34. How many different rooms are needed to assign 500
pigeonholes with the same number.
3. Since m < n i.e., the number of pigeonhole is less than the number of classes, if there are 45 different time periods during in the university
pigeons, n-m pigeons are left without having assigned a pigeonhole. time table that are available ?
4. Thus, at least one pigeonhole will be assigned to a more than one pigeon. Answer
5. We note that the pigeonhole principle tells us nothing about how to Using pigeonhole principle :
locate the pigeonhole that contains two or more pigeons.
n 1 500 1
6. It only asserts the existence of a pigeon hole containing two or more Here n = 500, m = 45 = 1 1
pigeons. m 45
At least 12 rooms are needed.
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.35. A total of 1232 student have taken a course in Spanish,
Que 5.33. Find the number of integers between 1 and 250 that are 879 have taken a course in French, and 114 have taken a course in
Russian. Further 103 have taken courses in both Spanish and
divisible by any of the integers 2, 3, 5, and 7. French, 23 have taken courses in both Spanish and Russian, and 14
have taken courses in both French and Russian. If 2092 students
Answer
have taken least one of Spanish, French and Russian, how many
1, 2, 3, -------------- 250 students have taken a course in all three languages ?
Number of integers between 1 and 250 that are divisible by 2 :
Quotient of last number 2 – quotient of first number 2 AKTU 2018-19, Marks 07
(250 2 ) – (1 2) = 125 – 0 = 125
Answer
Number of integers between 1 and 250 that are divisible by 3
(250 3) – (1 3) = 83 – 0 = 83 Let S be the set of students who have taken a course in Spanish, F be the set
Number of integers between 1 and 250 that are divisible by 5 of students who have taken a course in French, and R be the set of students
(250 5) – (1 5) = 50 – 0 = 50 who have taken a course in Russian. Then, we have
Number of integers between 1 and 250 that are divisible by 7 |S| = 1232, |F| = 879, |R| = 114, |S F| = 103, |S R| = 23,
(250 7) – (1 7) = 35 – 0 = 5 |S R| = 14, and |SF R| = 23.
Total number of integers divisible by only 2, 3, 5, 7, individually are Using the equation
125 + 83 + 50 + 35 = 293 |SF R| = |S|+ |F|+ |R| – |S F| – |S R| – |S R| + |S
Number of integers divisible by (2 and 3) = 41 F R|,
5–36 C (CS/IT-Sem-3) Trees, Graph and Combinatorics Discrete Structures & Theory of Logic 5–37 C (CS/IT-Sem-3)
2092 = 1232 + 879 + 114 – 103 – 23 – 14 +|SF R|, Q. 4.Define the following with one example :
|SF R| = 7. i.Bipartite graph
ii.Complete graph
|S F| = 103 iii.How many edges in K7 and K3, 6
|S F R| = ?
iv. Planar graph
Ans. Refer Q. 5.13.
Q. 6.
|S| = 1232 a. Prove that a connected graph G is Euler graph if and only if
|F| = 879 every vertex of G is of even degree.
b. Which of the following simple graph have a Hamiltonian
|S R| = 23
circuit or, if not a Hamiltonian path ?
|F R| = 14
a b a b a b g
|R| = 114 |S F R| = 2092
Fig. 5.35.1.
c d c f
e d c e
1
to the condition y0 = 0, y1 = 2.
Ans. Refer Q. 5.24.
Set Theory, Functions
Q. 11. Solve the recurrence relation using generating function :
an – 7an – 1 + 10an – 2 = 0 with a0 = 3, a1 = 3. and Natural Numbers
Ans. Refer Q. 5.25.
(2 Marks Questions)
Q. 12. Solve the recurrence relation ar+2 – 5ar+1 + 6 ar = (r + 1)2.
Ans. Refer Q. 5.26.
Q. 13. Solve ar – 6ar – 1 + 8ar – 2 = r.4r, given a0 = 8, and a1 = 1. 1.1. What do you understand by partition of a set ?
Ans. Refer Q. 5.27. Ans. A partition of a set A is a collection of non-empty subsets A1,
A2, ......, An called blocks, such that each element of A is in exactly
Q. 14. Solve the recurrence relation : ar + 4ar – 2 + 4ar – 2 = r . 2 one of the blocks. i.e.,
Ans. Refer Q. 5.28. i. A is the union of all subsets A1 A2 ..... An = A.
ii. The subsets are pairwise disjoint, Ai Aj = for i j.
Q. 15. Suppose that a valid codeword is an n-digit number in
decimal notation containing an even number of 0’s. Let an 1.2. Define transitive closure with suitable example.
denote the number of valid codewords of length n satisfying Ans. The relation obtained by adding the least number of ordered pairs
the recurrence relation an = 8an – 1 + 10n – 1 and the initial to ensure transitivity is called the transitive closure of the relation.
condition a1 = 9. Use generating functions to find an explicit The transitive closure of R is denoted by R+.
formula for an.
Ans. Refer Q. 5.29. 1.3. Let R be a relation on the set of natural numbers N, as
R = {(x, y) : x, y N, 3x + y = 19}. Find the domain and range of
Q. 16. Suppose that a cookie shop has four different kinds of R. Verify whether R is reflexive. AKTU 2016-17, Marks 02
cookies. How many different ways can six cookies be
chosen ? Ans. By definition of relation,
R = {(1, 16), (2, 13), (3, 10), (4, 7), (5, 4), (6, 1)}
Ans. Refer Q. 5.31.
Domain = {1, 2, 3, 4, 5, 6}
Q. 17. A total of 1232 student have taken a course in Spanish, 879 Range = {16, 13, 10, 7, 4, 1}
have taken a course in French, and 114 have taken a course R is not reflexive since (1, 1) R.
in Russian. Further 103 have taken courses in both Spanish
and French, 23 have taken courses in both Spanish and 1.4. Show that the relation R on the set Z of integers given by
Russian, and 14 have taken courses in both French and R = {(a, b) : 3 divides a – b}, is an equivalence relation.
Russian. If 2092 students have taken least one of Spanish, AKTU 2016-17, Marks 02
French and Russian, how many students have taken a
course in all three languages ? Ans. Reflexive : a – a = 0 is divisible by 3
(a, a) R a Z
Ans. Refer Q. 5.35.
R is reflexive.
Symmetric : Let (a, b) R a – b is divisible by 3
– (a – b) is divisible by 3
b – a is divisible by 3
(b, a) R
R is symmetric.
Transitive : Let (a, b) R and (b, c) R
a – b is divisible by 3 and b – c is divisible by 3
SQ–2 C (CS/IT-Sem-3) 2 Marks Questions Discrete Structures & Theory of Logic SQ–3 C (CS/IT-Sem-3)
Every element of B is associated with a unique element of A i.e., f(x1) = f(x2) implies x1 = x2 x1, x2, X
for any a A is pre-image of some b B where b = f(a) a = f–1(b)
A B
i.e., for b B, there exists f–1 image a A. f
Hence, f–1 is onto.
1.14. Define multiset and power set. Determine the power set
A = {1, 2}. AKTU 2015-16, Marks 02
Fig. 1.18.1. One-to-one.
Ans. Multiset : Multisets are sets where an element can occur as a
member more than once. 2. Onto function (Surjection or surjective function) : Let
For example : A = { p, p, p, q, q, q, r, r, r, r} f : X Y then f is called onto function iff for every element y Y
B = { p, p, q, q, q, r} there is an element x X with f(x) = y or f is onto if Range (f) = Y.
are multisets. X Y
Power set : A power set is a set of all subsets of the set.
The power set of A = {1, 2} is {{}, {1}, {2}}. f
2
A = [1, 1, 4, 2, 2, 3], B = [1, 2, 2, 6, 3, 3]
AKTU 2017-18, Marks 02
Ans. Union : Let A and B be two multisets. Then, A B, is the multiset
where the multiplicity of an element in the maximum of its
multiplicities in A and B.
Algebraic Structures
Intersection : The intersection of A and B, A B, is the multiset
where the multiplicity of an element is the minimum of its
(2 Marks Questions)
multiplicities in A and B.
Numerical :
A = {1, 1, 4, 2, 2, 3}, B = {1, 2, 2, 6, 3, 3} 2.1. List the properties of cosets.
Union : A B = {1, 2, 3, 4, 6} Ans. Let H be a subgroup of G and ‘a’ and ‘b’ belong to G. Then,
Intersection : A B = {1, 2, 2, 3} i. a aH
ii. aH = H iff a H
iii. aH = bH
iv. aH = bH iff a–1 b H
= 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 Discrete Structures & Theory of Logic SQ–9 C (CS/IT-Sem-3)
3
which each variable appears exactly once in either true or
complemented form, but not both.
Lattices and Boolean 3.6. Show that the relation is a partial ordering on the set of
Algebra integers, Z.
Ans. Since :
(2 Marks Questions) 1. a a for every a, is reflexive.
2. a b and b a imply a = b, is antisymmetric.
3. a b and b c imply a c, is transitive.
It follows that is a partial ordering on the set of integers and
3.1. Explain maximal and minimal element. (Z, ) is a poset.
Ans. Maximal element : An element ‘a’ in the poset is called a maximal
element of P if a x for no ‘x’ in P, that is, if no element of P strictly 3.7. Consider A = {x R : 1 < x < 2} with as the partial order.
succeeds ‘a’. Find
Minimal element : An element ‘b’ in P is called a minimal element i. All the upper and lower bounds of A.
of P if x b for no ‘x’ in P. ii. Greatest lower bound and least upper bound of A.
Ans.
3.2. What do you mean by sublattice ? i. Every real number 2 is an upper bound of A and every real
Ans. A non-empty subset L of a lattice L is called a sublattice of L if number 1 is a lower bound of A.
a, b L so that a b, a b L i.e., the algebra (L, , ) is a ii. 1 is a greatest lower bound and 2 is the least upper bound of A.
sublattice of (L, , ) iff L is closed under both operations and.
3.8. Determine
3.3. Write the following in DNF (x + y) (x + y). i. All maximal and minimal elements
AKTU 2015-16, Marks 02 ii. Greatest and least element
iii. Upper and lower bounds of ‘a’ and ‘b’, ‘c’ and ‘d’
Ans. Given : (x + y) (x + y) c d
The complete CNF in two variables (x, y)
= (x + y) (x + y) (x + y) (x + y) f
Hence, f (x, y) = (x + y) (x + y)
[f (x, y)] = [(x + y) (x + y)]
= xy + xy e
which is the required DNF. b
a
3.4. Explain lattice homomorphism and lattice isomorphism. Fig. 3.8.1.
Ans. Lattice homomorphism : Let (L, *, ) and (S, , ) be two lattices. Ans.
A mapping g : L S is called a lattice homomorphism from the i. Maximal elements = c, d, Minimal element = a, b
lattice (L, *, ) to (S, , ) if for any a, b L ii. Greatest and least elements do not exist.
g(a * b) = g(a) g(b) and (g b) = g(a) g(b). iii. Upper bound for a,b are e, f, c, d.
Lattice isomorphism : If a homomorphism g : L S of two Upper bound for c,d are does not exist.
lattices (L, *, ) and (S, ,) is bijective i.e., one-to-one onto, then Lower bound for a,b are does not exist.
g is called an isomorphism. Lower bound for c,d are f, e, a, b.
3.5. Define minterm and maxterm. 3.9. Let (A, ) be a distributive lattice. Show that if a x = a y
Ans. Minterm : A minterm of ‘n’ variables is a product of ‘n’ literals in and a x = a y for some a then x = y.
which each variable appears exactly once in either true or Ans. We have x = x (x a) = x (y a) ( Given condition)
complemented form, but not both. = (x y) (x a)
SQ–12 C (CS/IT-Sem-3) 2 Marks Questions Discrete Structures & Theory of Logic SQ–13 C (CS/IT-Sem-3)
3.11. For a given function, F = xy xy , find complement of F. 3.15. Draw the Hasse diagram of D30. AKTU 2018-19, Marks 02
Ans. F = xy xy
Ans.
F = xy (A + A = A)
Take the complement of both sides, 30
F = x y 6 15
10
Using De Morgan’s first law, we get,
3
F = xy 2 5
F = xy 1
Fig. 3.15.1.
3.12. Obtain an equivalent expression for [(x. y) (z + xy)].
Ans. Applying general form of De-Morgan’s theorem, we get
3.16. Define the terms : DNF and CNF.
[(x.y) (z + xy)] = (x.y) + (z + xy)= x + y [z + (x + y)] Ans. Disjunction Normal Form (DNF) : A logical expression is said
= x + y + zx + zy = x + x .z + y + yz = x + y + z to be in Disjunction Normal Form if it is the sum of elementary
[Applying x + xy = x and x + xy = x + y] product, i.e., join of elementary product.
Conjunctive Normal Form (CNF) : A logical expression is said
3.13. Show that the “greater than or equal” relation (>=) is a to be in Conjunctive Normal Form if it is the product of elementary
partial ordering on the set of integers. sums.
Example : p q, (p q) (~ p q)
AKTU 2016-17, Marks 02
Ans. Reflexive :
a a a Z (set of integer)
(a, a) A
R is reflexive.
Antisymmetric : Let (a, b) R and (b, a) R
a b and b a
a=b
R is antisymmetric.
Transitive : Let (a, b) R and (b, c) R
SQ–14 C (CS/IT-Sem-3) 2 Marks Questions Discrete Structures & Theory of Logic SQ–15 C (CS/IT-Sem-3)
statement is “If a steel rod is not stretched then it has not been
4
heated”.
Propositional Logic 4.5. Give truth table for converse, contrapositive and inverse.
Ans. The truth table of the four propositions are as follows :
and Predicate Logic
Conditional Converse Inverse Contrapositive
(2 Marks Questions) p q pq qp ~p ~q ~q~p
T T T T T T
4.1. What is compound proposition ? T F F T T F
Ans. A proposition obtained from the combinations of two or more
propositions by means of logical operators or connectives of two F T T F F T
or more propositions or by negating a single proposition is referred F F T T T T
to as composite or compound proposition.
4.2. Show the implications without constructing the truth 4.6. Show that contrapositive are logically equivalent; that is
~q~ppq
table (P Q) Q P Q. AKTU 2016-17, Marks 02 Ans. The truth table of ~ q ~ p and p q are shown below and the
Ans. (P Q) Q P Q logical equivalence is established by the last two columns of the
Take L.H.S table, which are identical.
(P Q) Q = (~P Q) Q
p q ~p ~q ~q~p pq
= (~(~P Q)) Q
= (P ~ Q) Q T T F F T T
= (P Q) (~ Q Q)
T F F T F F
= (P Q) T = P Q
It is equivalent. F T T F T T
5
than the data item in V.
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
5.1. Explain trivial tree and non-trivial tree.
Ans. A tree with only one vertex is called a trivial tree. A tree with of edges of G. AKTU 2016-17, Marks 02
more than one vertex is called non-trivial tree. Ans. We know that
b. Directed multigraph : k-edge coloring : A proper edge coloring with k different colors is
e7 called a (proper) k-edge coloring.
v1 e3 v2
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 SP–1 C (CS/IT-Sem-3) SP–2 C (CS/IT-Sem-3) Solved Paper (2014-15)
Time : 3 Hours Max. Marks : 100 f. Show that every group of order 3 is cyclic.
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 + SOLUTION OF PAPER (2014-15)
((xy + y)/y), into
i. Prefix notation ii. Postfix notation 1. Attempt any four parts : (5 × 4 = 20)
a. Show that R = {(a, b)|a b (mod m)} is an equivalence
4. Attempt any two parts : (10 × 2 = 20) relation on Z. Show that if x 1 y 1 and x 2 y 2 then
a. i. Show that ((p q) ~ (~ p (~ q ~ r))) (~ p ~q ) (~p r) (x1 + x2) (y1 + y2).
is a tautology without using truth table. Ans. R ={(a, b) | a b (mod m)}
ii. Rewrite the following arguments using quantifiers, For an equivalence relation it has to be reflexive, symmetric and
variables and predicate symbols : transitive.
a. All birds can fly. Reflexive : For reflexive a we have (a, a) R i.e.,
b. Some men are genius. a a (mod m)
c. Some numbers are not rational. a – a is divisible by m i.e., 0 is divisible by m
d. There is a student who likes mathematics but not Therefore aRa, a Z, it is reflexive.
geography. Symmetric : Let (a, b) Z and we have
(a, b) R i.e., a b (mod m)
b. “If the labour market is perfect then the wages of all persons a – b is divisible by m
in a particular employment will be equal. But it is always a – b = km, k is an integer
the case that wages for such persons are not equal (b – a) = (– k) m
therefore the labour market is not perfect”. Test the validity (b – a) = p m, p is also an integer
of this argument using truth table. b – a is also divisible by m
b a (mod m ) (b, a) R
c. Explain the following terms with suitable example : It is symmetric.
i. Conjunction Transitive : Let (a, b) R and (b, c) R then
ii. Disjunction (a , b) R a – b is divisible by m
iii. Conditional a – b = t m, t is an integer ...(1)
iv. Converse (b, c) R b – c is divisible by m
v. Contrapositive b – c = s m, s is an integer ...(2)
From eq. (1) and (2)
5. Attempt any two parts : (10 × 2 = 20) a – b + b – c = (t + s) m
a. Solve the recurrence relation by the method of generating a – c = lm, l is also an integer
function a – c is divisible by m
ar – 7 ar–1 + 10ar–2 = 0, r 2 a c (mod m), yes it is transitive.
Given a0 = 3 and a1 = 3. R is an equivalence relation.
To show : (x1 + x2) (y1 + y2) :
b. Solve the recurrence relation It is given x1 y1 and x2 y2
ar+2 – 5ar+1 + 6 ar = (r + 1)2 i.e., x1 – y1 divisible by m
x2 – y2 divisible by m
c. Explain the following terms with example : Adding above equation :
i. Homomorphism and Isomorphism graph (x1 – y1) + (x2 – y2) is divisible by m
ii. Euler graph and Hamiltonian graph (x1 + x2) – (y1 + y2) is divisible by m
iii. Planar and Complete bipartite graph i.e., (x1 + x2) (y1 + y2)
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) SP–6 C (CS/IT-Sem-3) Solved Paper (2014-15)
[(5, 8)] = [(a, b) : (a, b) R (5, 8), (a, b) A × A] Then we have a * a – 1 = e, where a – 1 G.
= [(a, b) : a + 8 = b + 5] Also (a – 1) – 1 * a – 1 = e
= [(a, b) : a + 3 = b] Therefore, (a – 1) – 1 * a – 1 = a * a – 1.
[5, 8] = {(1, 4), (2, 5), (3, 6), (4, 7) Thus, by right cancellation law, we have (a – 1) – 1 = a.
(5, 8), (6, 9), (7, 10), (8, 11) ii. Let a and b G and G is a group for *, then a * b G (closure)
(9, 12), (10, 13)} Therefore, (a * b) – 1 * (a * b) = e. ....(1)
Let a – 1 and b – 1 be the inverses of a and b respectively, then a – 1,
2. Attempt any four parts : (5 × 4 = 20) b – 1 G.
a. Prove that (Z6, (+6)) is an abelian group of order 6, where Therefore, (b – 1 * a – 1) * (a * b) = b – 1 * (a – 1 * a) * b (associativity)
Z6 = {0, 1, 2, 3, 4, 5}. = b–1 * e * b = b–1 * b = e ...(2)
Ans. The composition table is : From eq. (1) and (2) we have,
+6 0 1 2 3 4 5 (a * b) – 1 * (a * b) = (b – 1 * a – 1)* (a * b)
(a * b) – 1 = b – 1 * a –1 (by right cancellation law)
0 0 1 2 3 4 5
1 1 2 3 4 5 0
c. Prove that the intersection of two subgroups of a group is
2 2 3 4 5 0 1 also subgroup.
3 3 4 5 0 1 2
Ans. Let H1 and H2 be any two subgroups of G. Since at least the identity
4 4 5 0 1 2 3 element e is common to both H1 and H2.
5 5 0 1 2 3 4
H1 H2
Since 2 +6 1 = 3 In order to prove that H1 H2 is a subgroup, it is sufficient to prove
4 +6 5 = 3 that
From the table we get the following observations : a H1 H2, b H1 H2 ab–1 H1 H2
Closure : Since all the entries in the table belong to the given set Now a H1 H2 a H1 and a H2
Z6. Therefore, Z6 is closed with respect to addition modulo 6. b H1 H2 b H1 and b H2
Associativity : The composition ‘+6’ is associative. If a, b, c are any But H1, H2 are subgroups. Therefore,
three elements of Z6, a H1, b H1 ab–1 H1
a +6 (b +6 c) =a +6 (b + c) [ b +6 c = b + c (mod 6)] a H2 , bH2 ab–1 H2
= least non-negative remainder when a + (b + c) is divided by 6. Finally, ab–1 H1, ab–1 H2 ab–1 H1 H2
= least non-negative remainder when (a + b) + c is divided by 6. Thus, we have shown that
= (a + b) +6 c = (a +6 b) +6 c. a H1 H2, b H1 H2 ab–1 H1 H2.
Identity : We have 0 Z6. If a is any element of Z6, then from the Hence, H1 H2 is a subgroup of G.
composition table we see that
0 +6 a = a = a +6 0 d. Write and prove the Lagrange’s theorem. If a group
Therefore, 0 is the identity element. G = {...., – 3, 2, – 1, 0, 1, 2, 3,.....} having the addition as binary
Inverse : From the table we see that the inverse of 0, 1, 2, 3, 4, 5 operation. If H is a subgroup of group G where x2 H such
are 0, 5, 4, 3, 2, 1 respectively. For example 4 +6 2 = 0 = 2 +6 4 implies that x G. What is H and its left coset w.r.t 1 ?
4 is the inverse of 2. Ans. Lagrange’s theorem :
Commutative : The composition is commutative as the elements If G is a finite group and H is a subgroup of G then o(H) divides
are symmetrically arranged about the main diagonal. The number o(G). Moreover, the number of distinct left (right) cosets of H in G
of elements in the set Z6 is 6. is o(G)/o(H).
(Z6, +6) is a finite abelian group of order 6. Proof : Let H be subgroup of order m of a finite group G of order n.
Let H {h1, h2, ..., hm}
b. Let G be a group and let a, b G be any elements. Then Let a G. Then aH is a left coset of H in G and aH = {ah1, ah2, ...,
i. (a–1)–1 = a ahm} has m distinct elements as ahi = ahj hi = hj by cancellation
ii. (a * b)–1 = b–1 * a–1. law in G.
Ans. Thus, every left coset of H in G has m distinct elements.
i. Let e be the identity element for * in G.
Discrete Structures & Theory of Logic SP–9 C (CS/IT-Sem-3) SP–10 C (CS/IT-Sem-3) Solved Paper (2014-15)
Since G is a finite group, the number of distinct left cosets will also 5. Since a is not the identity element, therefore o(a) is definitely 2.
be finite. Let it be k. Then the union of these k-left cosets of H in G Let o(a) = m. If H is the cyclic subgroup of G generated by a then
is equal to G. o (H = o (a) = m).
i.e., if a1H, a2H, ..., akH are right cosets of H in G then 6. By Lagrange’s theorem m must be a divisor of p. But p is prime and
G = a1H a2H ... akH. m 2. Hence, m = p.
o(G) = o(a1H) + o(a2H) + ... + o(akH) 7. H = G. Since H is cyclic therefore G is cyclic and a is a generator
(Since two distinct left cosets are mutually disjoint.) of G.
n = m + m + ... + m (k times)
n 3. Attempt any two parts : (10 × 2 = 20)
n = mk k = a. The directed graph G for a relation R on set A = {1, 2, 3, 4} is
m
shown below :
o(G )
k= .
o( H )
Thus order of each subgroup of a finite group G is a divisor of the 1 2
order of the group.
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, ....} 3 4
ii. Since there is no lub of 1 and 2 and same for 2 and 4. The given c. Consider the Boolean function
poset is not a lattice. a. f(x1, x2, x3, x4) = x1 + (x2. (x'1 + x4) + x3. (x'2 + x'4))
1 2 3 4 i. Simplify f algebraically.
ii. Draw the logic circuit of the f and the reduction of the f.
1 1 1 1
b. Write the expressions E1 = (x + xy) + (x/y) and E2 = x +
2 2 2 ((xy + y)/y), into
3 1 2 3 1 i. Prefix notation ii. Postfix notation
4 1 1 4 Ans.
iii. Only one edge (4, 2) is included to make it total order. a. i. f(x1, x2, x3, x4) = x1 + (x2.(x1 + x4) + x3.(x2+ x4)
iv. Maximals are {1, 2} and minimals are {3, 4}. = x1 + x2.x1 + x2.x4 + x3.x2 + x3.x4
= x1 + x2 + x2.x4 + x3.x2 + x3.x4
b. If the lattice is represented by the Hasse diagram given
= x1 + x2.(1 + x4) + x3.x2 + x3.x4
below :
i. Find all the complements of ‘e’. = x1 + x2 + x3.x2 + x3.x4
ii. Prove that the given lattice is bounded complemented = x1 + x2 + x3 + x3.x4
lattice. = x1 + x2 + x3.(1 + x4)
b
= x1 + x2 + x3
a c ii. Logic circuit :
x1 x1 + x2 + x3
x2
x3
f d
Fig. 4.
e
Fig. 3. Reduction of f :
Ans. f (x1, x2, x3, x4) = x1 + (x2.(x1 + x4) + x3.(x2 + x4)
i. In a given lattice, greatest element is b and least element is e. An = x1 + (x2.x1 + x2.x4) + (x3.x2 + x3.x4)
element x in lattice is called a complement of element y if
y x = b and y x = e = x1 + x2.x1 + x2.x4 + x3.x2 + x3.x4
For element e, b. E1 = (x + x * y) + (x/y)
eb=b , e b=e Binary tree is :
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.
x * x y
Now the complement of all elements is given below :
Complement of a = {c, d}
Complement of b = {e} x y
Complement of c = {a, f}
Complement of d = {a, f} Fig. 5.
Complement of e = {b} Prefix : ++ x * x y / xy
Complement of f = {c, d} Postfix : xx y * + xy / +
Since, complement of every element exists and lattice is bounded. E2 = x + ((x * y + y)/y)
So, the given lattice is bounded complemented lattice.
Hence proved.
Discrete Structures & Theory of Logic SP–13 C (CS/IT-Sem-3) SP–14 C (CS/IT-Sem-3) Solved Paper (2014-15)
x2 – 5 x + 6 = 0
(x – 3) (x – 2) = 0 x = 3, 2
The homogeneous solution is : (a) (b ) (c )
ar(h) = C12r + C2 3r Fig. 7.
Isomorphism of graph : Two graphs are isomorphic to each
Let the particular solution be :
other if :
ar(p) = A0 + A1r + A2r2 i. Both have same number of vertices and edges.
From eq. (1) ii. Degree sequence of both graphs are same (degree sequence is the
A0 + A1 (r + 2) + A2 (r + 2)2 – 5 {A0 + A1 (r + 1)} + A2 (r + 1)2} sequence of degrees of the vertices of a graph arranged in non-
increasing order).
+ 6A0 + 6A1r + 6A2 r2 Example :
= r2 + 2 r + 1
(A0 + 2A1 + 4A2 –5A0 – 5A1 – 5A2 + 6A0) + r (A1 + 4A2 – 5A1 – 10A2 +
6A1)
+ r2 ( A2 – 5A2 + 6A2) = r2 + 2r + 1
Fig. 8.
Comparing both sides, we get, ii. Eulerian path : A path of graph G which includes each edge of G
2A0 – 3A1 – A2 = 1 ...(2) exactly once is called Eulerian path.
2A1 – 6A2 = 2 ...(3) Eulerian circuit : A circuit of graph G which include each edge of
G exactly once.
2A2 = 1 A2 = 1/2 Eulerain graph : A graph containing an Eulerian circuit is called
From eq. (3), 2A1 – 3 = 2 Eulerian graph.
5 For example : Graphs given below are Eulerian graphs.
A1 = V1 V3 A B
2 V2
From eq. (2)
15 1 V5 V4 D
2A0 – =1 C
2 2 Fig. 9.
9 Hamiltonian graph : A Hamiltonian circuit in a graph G is a
2A0 – 8 = 1 A0 = closed path that visit every vertex in G exactly once except the end
2
vertices. A graph G is called Hamiltonian graph if it contains a
9 5 r2
ar(p) = r Hamiltonian circuit.
2 2 2 For example : Consider graphs given below :
The final solution is,
D C D C
9 5 r2
ar = ar(h) + ar(p) = C1 2r + C2 3r + + r F
2 2 2
E
A B A B
c. Explain the following terms with example : (a) (b )
i. Homomorphism and Isomorphism graph Fig. 10.
ii. Euler graph and Hamiltonian graph Graph given is Fig. 10(a) is a Hamiltonian graph since it contains a
iii. Planar and Complete bipartite graph Hamiltonian circuit A – B – C – D – A while graph in Fig 10(b) is not
Ans. a Hamiltonian graph.
i. Homomorphism of graph : Two graphs are said to be Hamiltonian path : The path obtained by removing any one edge
homomorphic if one graph can be obtained from the other by the from a Hamiltonian circuit is called Hamiltonian path. Hamiltonian
creation of edges in series (i.e., by insertion of vertices of degree path is subgraph of Hamiltonian circuit. But converse is not true.
two) or by the merger of edges in series.
Discrete Structures & Theory of Logic SP–19 C (CS/IT-Sem-3) Discrete Structures & Theory of Logic SP–1 C (CS/IT-Sem-3)
Note : Attempt all parts. All parts carry equal marks. Write answer of
each part in short. (2 × 10 = 20)
(a) (b )
Fig. 11. Some planar graph.
SECTION – A
Complete bipartite graph : The complete bipartite graph on m
and n vertices, denoted Km, n is the graph, whose vertex set is
1. a. Define multiset and power set. Determine the power set
partitioned into sets V1 with m vertices and V2 with n vertices in
A = {1, 2}.
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
b. Show that [((p q) r) (~ p)] (q r) is tautology or
K2,3, K2,4, K 3,3, K3,5, and K2,6
contradiction.
SECTION – B SECTION – C
2. Prove that n3 + 2n is divisible by 3 using principle of 10. Let L be a bounded distributed lattice, prove if a complement
mathematical induction, where n is natural number. exists, it is unique. Is D12 a complemented lattice ? Draw
the Hasse diagram of [P (a, b, c), <], (Note : ‘<’ stands for
3. Solve the recurrence relation using generating function : subset). Find greatest element, least element, minimal
an – 7an – 1 + 10an – 2 = 0 with a0 = 3, a1 = 3. element and maximal element.
4. Express the following statements using quantifiers and 11. Determine whether each of these functions is a bijective
logical connectives. from R to R.
a. Mathematics book that is published in India has a blue a. f(x) = x2 + 1
cover. b. f(x) = x3
b. All animals are mortal. All human being are animal. c. f(x) = (x2 + 1)/(x2 + 2)
Therefore, all human being are mortal.
c. There exists a mathematics book with a cover that is not 12. a. Prove that inverse of each element in a group is unique.
blue. b. Show that G = [(1, 2, 4, 5, 7, 8), ×9] is cyclic. How many
d. He eats crackers only if he drinks milk. generators are there ? What are they ?
e. There are mathematics books that are published outside
India.
f. Not all books have bibliographies.
5. Draw the Hasse diagram of [P (a, b, c), ] (Note : ‘’ stands
for subset). Find greatest element, least element, minimal
element and maximal element.
3. Since m < n i.e., the number of pigeonhole is less than the number
SOLUTION OF PAPER (2015-16) of pigeons, n – m pigeons are left without having assigned a pigeon
hole.
Note : Attempt all parts. All parts carry equal marks. Write answer of 4. Thus, at least one pigeonhole will be assigned to a more than one
each part in short. (2 × 10 = 20) pigeon.
T T T T F T T F T T F T F F F
T T F T F F F F T F T T F F F
T F T T F F T F T F F F F T T
T F F T F F F F T
f. How many 4 digit numbers can be formed by using the
F T T T T T T T T digits 2, 4, 6, 8 when repetition of digits is allowed ?
F T F T T F F F T Ans. When repetition is allowed :
The thousands place can be filled by 4 ways.
F F T F T F T T F The hundreds place can be filled by 4 ways.
The tens place can be filled by 4 ways.
F F F F T F T T F The units place can be filled by 4 ways.
Total number of 4 digit number = 4 × 4 × 4 × 4 = 256
Question is incorrect. Since the result of the question is
contingency. g. The converse of a statement is : If a steel rod is stretched,
then it has been heated. Write the inverse of the statement.
c. State and prove pigeonhole principle.
Ans. The statement corresponding to the given converse is “If a steel
Ans. Pigeonhole principle : If n pigeons are assigned to m pigeonholes rod is stretched, then it has been heated”. Now the inverse of this
then at least one pigeon hole contains two or more pigeons (m < n). statement is “If a steel rod is not stretched then it has not been
Proof : heated”.
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.
SP–6 C (CS/IT-Sem-3) Solved Paper (2015-16) Discrete Structures & Theory of Logic SP–7 C (CS/IT-Sem-3)
h. If a and b are any two elements of group G then prove Step III : Inductive step : We have to show that S(k + 1) is true
(a * b) – 1 = (b – 1 * a – 1). i.e., (k + 1)3 + 2(k + 1) is divisible by 3
Ans. Consider (a * b) * (b – 1 * a – 1) Consider (k + 1)3 + 2(k + 1)
= a * (b * b – 1) * a – 1 = k3 + 1 + 3k2 + 3k + 2k + 2
= a * e * a– 1 = (k3 + 2k) + 3(k2 + k + 1)
= a * a–1= e = 3s + 3l where l = k2 + k + 1 N
Also (b * a ) * (a * b) = b – 1 * (a – 1 * a) * b
– 1 – 1 = 3(s + l)
= b–1 * e * b Therefore, S(k + 1) is true
= b–1 * b = e Hence by principle of mathematical induction S(n) is true for all
Therefore (a * b) 1 = b – 1 * a – 1 for any a, b G
– n N.
i. If f : A B is one-one onto mapping, then prove that 3. Solve the recurrence relation using generating function :
an – 7an – 1 + 10an – 2 = 0 with a0 = 3, a1 = 3.
f –1 : B A will be one-one onto mapping.
Ans. n – 7an – 1 + 10 an – 2 = 0,
a
Ans. Proof : Here f : A B is one-to-one and onto.
a1, a2 A and b1, b2 B so that Let in assume n 2
b1 = f(a1), b2 = f (a2) and a1 = f–1(b1), a2 = f–1 (b2) Multiply by xn and take sum from 2 to .
As f is one-to-one
f(a1) = f(a2) a1 = a2 an xn 7 an –1 xn 10 an2 xn 0
b1 = b2 f–1(b1) = f–1(b2) n 2 n2 n 2
i.e., f (b1) = f–1(b2) b1 = b2
–1
(a2 x2 + a3 x3 + a4 x4 + ....) – 7 (a1 x2 + a2 x3 + ....)
f is one-to-one function.
–1
+ 10 (a0 x2 + a1 x3 + ....) = 0
As f is onto.
Every element of B is associated with a unique element of A i.e., We know that
for any a A is pre-image of some b B where b = f(a) a = f–1(b)
i.e., for b B, there exists f–1 image a A.
G(x) = an xn a0 a1 x ....
n0
Hence, f–1 is onto. 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
j. Write the following in DNF (x + y) (x + y). = 3 + 3x – 21 x = 3 – 18 x
Ans. Given : (x + y) (x + y)
3 18 x 3 18 x
The complete CNF in two variables (x, y) G(x) =
= (x + y) (x + y) (x + y) (x + y) 10 x 7 x 1 10 x 5 x 2 x 1
2 2
1 4 4 1 a a2 I
G(x) = = ...(2)
5 x 1 2x 1 1 2x 1 5x a a2 0
an = 4.2n – 5n Consider a1 = a1 0
= a1 (a a2) [from (2)]
4. Express the following statements using quantifiers and = (a1 a) (a1 a2) [Distributive property]
logical connectives.
= (a a1) (a1 a2) [Commutative property]
a. Mathematics book that is published in India has a blue
cover. = I (a1 a2) [from (1)]
b. All animals are mortal. All human being are animal. = a1 a2 ...(3)
Therefore, all human being are mortal. Now Consider a2 = a2 0
c. There exists a mathematics book with a cover that is not = a2 (a a1) [from (2)]
blue.
= (a2 a) (a2 a1) [Distributive property]
d. He eats crackers only if he drinks milk.
e. There are mathematics books that are published outside = (a a2) (a1 a2) [Commutative property]
India. = I (a1 a2) [from (1)]
f. Not all books have bibliographies. = a1 a2 ...(4)
Ans. Hence, from (3) and (4),
a. P(x) : x is a mathematic book published in India
a1 = a2
Q(x) : x is a mathematic book of blue cover
So, for bounded distributive lattice complement is unique.
x P(x) Q(x).
Hasse diagram of [P(a, b, c), ] is shown in Fig. 1.
b. P(x) : x is an animal
Q(x) : x is mortal {a, b, c}
x P(x) Q(x)
R(x) : x is a human being
x R(x) P(x).
{a, b} {a, c} {b, c}
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 {c}
{a} {b}
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 Fig. 1.
x P(x) Q(x).
Greatest element is {a, b, c} and maximal element is {a, b, c}.
f. P(x) : x is a book having bibliography ~ x, P(x). The least element is and minimal element is .
5. Draw the Hasse diagram of [P (a, b, c), ] (Note : ‘’ stands 6. Simplify the following boolean expressions using k-map :
for subset). Find greatest element, least element, minimal a. Y = ((AB) + A + AB)
element and maximal element. b. A B C D + A B C D + A B CD + A B CD = A B
Ans. Let a1 and a2 be two complements of an element a L. Ans.
Then by definition of complement a. Y = ((AB) + A + AB)
a a1 I = ((AB)) (A + (AB))
...(1) = (AB) ((A) (AB))
a a1 0
SP–10 C (CS/IT-Sem-3) Solved Paper (2015-16) Discrete Structures & Theory of Logic SP–11 C (CS/IT-Sem-3)
= AB (A (A + B)) ab = 4
= AB (AA + AB) 4
b=
= AB(0 + AB) = AB AB a
= ABB
4
=0 The inverse of a is , a G.
Here, we find that the expression is not in minterm. For getting a
v. Commutative : Let a, b G
minterm, we simplify and find that its value is already zero. Hence,
no need to use K-map for further simplification. ab
a*b=
b. A B C D + A B C D + A B CD + A B CD = A B 2
= A BCD + ABCD + ABCD + ABCD ba ab
and b*a=
CD AB 2 2
* is commutative.
ABCD 1 Thus, (G, *) is an abelian group.
ABCD 1
8. The following relation on A = {1, 2, 3, 4}. Determine whether
ABCD 1
the following :
ABCD 1 a. R = {(1, 3), (3, 1), (1, 1), (1, 2), (3, 3), (4, 4)}.
Fig. 2. b. R = A × A
Is an equivalence relation or not.
On simplification by K-map, we get AB corresponding to all the
Ans.
four one’s.
a. R = {(1, 3), (3, 1), (1, 1), (1, 2), (3, 3), (4, 4)}
Reflexive : (a, a) R a A
7. Let G be the set of all non-zero real number and let
(1, 1) R, (2, 2) R
a*b = ab/2. Show that (G*) be an abelian group.
R is not reflexive.
Ans. Symmetric : Let (a, b) R then (b, a) R.
i. Closure property : Let a, b G.
(1, 3) R so (3, 1) R
a*b=
ab
G as ab 0 (1, 2) R but (2, 1) R
2 R is not symmetric.
* is closure in G. Transitive : Let (a, b) R and (b, c) R then (a, c) R
ii. Associativity : Let a, b, c G (1, 3) R and (3, 1) R so (1, 1) R
bc a(bc) abc (2, 1) R and (1, 3) R but (2, 3) R
Considera * (b * c) = a * R is not transitive.
2 4 4
Since, R is not reflexive, not symmetric, and not transitive so R is
ab (ab) c abc
(a * b) * c = * c =
2 not an equivalence relation.
4 4 b. R = A × A
* is associative in G. Since, A × A contains all possible elements of set A. So, R is reflexive,
iii. Existence of the identity : Let a G and e such that symmetric and transitive. Hence R is an equivalence relation.
ae
a*e= =a
2 9. If the permutation of the elements of {1, 2, 3, 4, 5} are given
ae = 2a by a = (1 2 3) (4 5), b = (1) (2) (3) (4 5), c = (1 5 2 4) (3). Find the
e=2 value of x, if ax = b. And also prove that the set Z4 = (0, 1, 2, 3)
2 is the identity element in G. is a commutative ring with respect to the binary modulo
iv. Existence of the inverse : Let a G and b G such that a * b = operation +4 and *4.
e=2 Ans. ax = b (123) (45) x = (1) (2) (3) (4, 5)
ab
=2 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5
x
2 2 3 1 4 5 1 2 3 5 4 1 2 3 5 4
SP–12 C (CS/IT-Sem-3) Solved Paper (2015-16) Discrete Structures & Theory of Logic SP–13 C (CS/IT-Sem-3)
1 2 3 4 5 1 2 3 4 5 SECTION – C
=
3 1 2 5 4 1 2 3 5 4
10. Let L be a bounded distributed lattice, prove if a complement
1 2 3 4 5 exists, it is unique. Is D12 a complemented lattice ? Draw
x=
3 1 2 4 5 the Hasse diagram of [P (a, b, c), <], (Note : ‘<’ stands for
subset). Find greatest element, least element, minimal
4 0 1 2 3 4 0 1 2 3 element and maximal element.
0 0 1 2 3 0 0 0 0 0 Ans. Let a1 and a2 be two complements of an element a L.
Then by definition of complement
1 1 2 3 0 1 0 1 2 3
a a1 I
2 2 3 0 1 2 0 2 0 2 ...(1)
a a1 0
3 3 0 1 2 3 0 3 2 1
We find from these tables : a a2 I
...(2)
i. All the entries in both the tables belong to Z4. Hence, Z4 is closed a a2 0
with respect to both operations. Consider a1 = a1 0
ii. Commutative law : The entries of 1st, 2nd, 3rd, 4th rows are identical = a1 (a a2) [from (2)]
with the corresponding elements of the 1st, 2nd, 3rd, 4th columns = (a1 a) (a1 a2) [Distributive property]
respectively in both the tables. Hence, Z4 is commutative with respect = (a a1) (a1 a2) [Commutative property]
to both operations.
= I (a1 a2) [from (1)]
iii. Associative law : The associative law for addition and multiplication
= a1 a2 ...(3)
a +4 (b +4 c) = (a +4 b) +4 c for all a, b, c Z4
Now Consider a2 = a2 0
a ×4 (b ×4 c) = (a ×4 b) ×4 c, for all a, b, c Z4
= a2 (a a1) [from (2)]
can easily be verified.
= (a2 a) (a2 a1) [Distributive property]
iv. Existence of identity : 0 is the additive identity and 1 is
multiplicative identity for Z4. = (a a2) (a1 a2) [Commutative property]
v. Existence of inverse : The additive inverses of 0, 1, 2, 3 are 0, 3, 2, = I (a1 a2) [from (1)]
1 respectively. = a1 a2 ...(4)
Multiplicative inverse of non-zero element 1, 2, 3 are 1, 2, 3 Hence, from (3) and (4),
respectively. a1 = a2
vi. Distributive law : Multiplication is distributive over addition i.e., So, for bounded distributive lattice complement is unique.
a ×4(b +4c) = a ×4b + a ×4c Hasse diagram of [P(a, b, c), ] is shown in Fig. 3.
(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
SP–14 C (CS/IT-Sem-3) Solved Paper (2015-16) Discrete Structures & Theory of Logic SP–15 C (CS/IT-Sem-3)
B.Tech. Section-B
(SEM. III) ODD SEMESTER Note : Attempt any five questions from this section. (10 × 5 = 50)
THEORY EXAMINATION, 2016-17 2. Write the s ymbolic form and negate the following
DISCRETE STRUCTURES AND statements :
• Everyone who is healthy can do all kinds of work.
GRAPH THEORY • Some people are not admired by everyone.
• Everyone should help his neighbours, or his neighbours
Time : 3 Hours Max. Marks : 100 will not help him.
Section-A
c f Note : Attempt all parts. All parts carry equal marks. Write answer of
e c d d c e each part in short. (2 × 10 = 20)
d. Show that the “greater than or equal” relation (>=) is a iii. There exists an element 0 R such that
partial ordering on the set of integers. 0 + a = a = a + 0, a R
Ans. Reflexive : iv. To each element a in R there exists an element – a in R such that
a a a Z (set of integer) a + (– a) = 0
(a, a) A v. Multiplication is associative i.e.,
R is reflexive.
a.(b.c) = (a.b).c, a b, c R
Antisymmetric : Let (a, b) R and (b, a) R
a b and b a vi. Multiplication is distributive with respect to addition i.e., for all
a=b a, b, c R,
R is antisymmetric. Example of ring with zero divisors : R = {a set of 2 × 2
Transitive : Let (a, b) R and (b, c) R matrices}.
a b and b c Field : A ring R with at least two elements is called a field if it has
a c (a, c) R following properties :
R is transitive. i. R is commutative
Hence, R is partial order relation. ii. R has unity
iii. R is such that each non-zero element possesses multiplicative
e. Distinguish between bounded lattice and complemented inverse.
lattice. For example : The rings of real numbers and complex numbers
are also fields.
Ans. Bounded lattice : A lattice which has both elements 0 and 1 is
called a bounded lattice.
Complemented lattice : A lattice L is called complemented lattice h. State the applications of binary search tree.
if it is bounded and if every element in L has complement. Ans. One of the most common applications is to efficiently store data in
sorted form in order to access and search stored elements quickly.
f. Find the recurrence relation from yn = A2n + B(–3)n. For example, std :: map or std :: set in C++ Standard Library.
Binary tree as data structure is useful for various implementations
Ans. Given : yn = A2n + B (– 3)n
Therefore, yn + 1 = A(2)n + 1 + B (– 3)n + 1 of expression parsers and expression solvers.
= 2A (2)n – 3B (– 3)n
and yn + 2 = A(2)n + 2 + B (– 3)n + 2 i. Define multigraph. Explain with example in brief.
= 4A (2)n + 9B (– 3)n Ans. A multigraphs G(V, E) consists of a set of vertices V and a set of
Eliminating A and B from these equations, we get edges E such that edge set E may contain multiple edges and self
loops.
yn 1 1 Example :
yn1 2 – 3 = 0 a. Undirected multigraph :
yn 2 4 9 e2
v1 v2
= yn + 2 – yn + 1 – 6yn = 0 which is the e6
required recurrence relation.
e5
g. Define ring and give an example of a ring with zero divisors. e1
e3
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 e4
v4 v3
and it satisfies the following properties :
i. Addition is associative i.e.,
Fig. 1.
(a + b) + c = a + (b + c) a, b, c R
ii. Addition is commutative i.e.,
a + b = b + a a, b R
Discrete Structures & Theory of Logic SP–7 C (CS/IT-Sem-3) SP–8 C (CS/IT-Sem-3) Solved Paper (2016-17)
b. Directed multigraph : will not help x” and it is ( x) ( y)[N(x, y) (H(x, y) P(y, x))]
e7
v1 e3 v2 Negation : ( x) ( y) [N(x, y) (H (x, y) P (y, x))]
O(G) = km = n(n – k + 1) – k (n – k + 1)
n = km = (n – k)(n – k + 1) ...(1)
n We know that the maximum number of edges in the ith component
k= of
m
m is a divisor of n. ni (ni 1)
ni
O(H) is a divisor of O(G). G= C2 =
2
Proof of converse : If G be a finite group of order n and n G,
then Therefore, the maximum number of edges in G is :
an = e
Let o (a) = m which implies am = e.
1
2
ni (ni 1) =
1
2
ni2 ni =
1
2
ni2 n
Now, the subset H of G consisting of all the integral power of a is a 1
subgroup of G and the order of H is m. (n – k)(n – k + 1) by using eq. (1)
2
Then, by the Lagrange’s theorem, m is divisor of n.
Let n = mk, then
an = amk = (am)k = ek = e 1 1 1 n
6. Prove by induction : + + ... + = .
Yes, the converse is true. 1.2 2.3 n ( n + 1) ( n + 1)
Ans. Let the given statement be denoted by S(n).
5. Prove that a simple graph with n vertices and k components 1. Inductive base : For n = 1
(n k) ( n k 1) 1 1 1
can have at most edges. =
2 1.2 11 2
Ans. Let the number of vertices in each of the k-components of a graph Hence S (1) is true.
G be n1, n2, ...., nk, then we get 2. Inductive hypothesis : Assume that S (k) is true i.e.,
n1 + n2 + ... + nk = n where ni 1 (i = 1, 2, ..., k)
1 1 1 k
k k ..... =
n 1 = n – k k(k 1) k 1
k
Now, (n
i 1
i 1) =
i 1
i
i 1
1.2 2.3
3. Inductive step : We wish to show that the statement is true for
2 n = k + 1 i.e.,
k
(ni 1) = n + k – 2nk
2 2
1 1 1 k1
i 1 ..... =
k k
1.2 2.3 (k 1)(k 2) k2
or (n
i 1
i 1)2 2 (ni 1)(n j 1) = n2 + k2 – 2nk
i 1 j 1 Now,
1
1
.....
1
1
i j 1.2 2.3 k(k 1) ( k 1)(k 2)
k
k2 2k 1
or (n
i 1
i 1)2 + 2(non-negative terms) = n2 + k2 – 2nk =
k
1
k 1 ( k 1)(k 2) ( k 1)(k 2)
[ ni – 1 0, nj – 1 0] k1
k =
k2
or (n
i 1
i 1) n2 + k2 – 2nk
2
n 0
an 2 t n – 5
n 0
an 1 t n 6
n 0
an t n 5
n 0
n
tn
=
t2
=
1/ 4
(1 – 5t)(1 – 3t) t 1/2 (2 – 5) (2 – 3)
G(t) – a0 – a1 t G (t) – a0 1 2 2
– 5 6 G (t )
t2 t 1 – 5t 1
Put a0 = 0 and a1 = 2 =
3
t2 Again,
G(t) – 2t – 5t G(t) + 6t2 G(t) = 2t D E
1 – 5t =
(1 – 3t)(1 – 2t) (1 – 3t) (1 – 2t)
t2
G(t) – 5t G(t) + 6t2 G(t) = + 2t 2t
1 – 5t D = (1 – 3t)
(1 – 3t)(1 – 2t) t 1/3
t2
G(t) (1 – 5t + 6t2) = + 2t
1 – 5t 2t 2/3
= = 2
(1 – 2t) t 1/3 (3 – 2)
t2
(6t2 – 5t + 1) G(t) = + 2t 3
1 – 5t
2t
t2 2t E = (1 – 2t)
G(t) = (1 – 3t)(1 – 2t) t 1/ 2
(1 – 5t)(3t – 1)(2t – 1) (3t – 1)(2t – 1)
2t 2/2
t2 2t = = –2
= (1 – 3t) t 1/ 2 2–3
(1 – 5t)(1 – 3t)(1 – 2t) (1 – 3t)(1 – 2t) 2
Let
1/ 6 1/ 2 1/3 2 2
t2 A B C G(t) = – –
= (1 – 5t) (1 – 3t) (1 – 2t) (1 – 3t) (1 – 2t)
(1 – 5t)(1 – 3t)(1 – 2t) (1 – 5t) (1 – 3t) (1 – 2t)
1/6 3/2 5/3
= –
t2 1 – 5t (1 – 3t) 1 – 2t
A = (1 – 5t)
(1 – 5t)(1 – 3t)(1 – 2t) t 1/5
1 3 5
an t n = (5t)n (3t) n – (2t)n
t2 n 0
6 n 0
2 n 0
3 n 0
=
(1 – 3t)(1 – 2t) t 1/5 1 n 3 n 5 n
an = (5) (3) – (2)
1 / 25 1 6 2 3
= =
(1 – 3 / 5)(1 – 2 / 5) 6
8. a. Prove that every finite subset of a lattice has an LUB and a
t2 GLB.
B = (1 – 3t)
(1 – 5t)(1 – 3t)(1 – 2t) t 1/3 b. Give an example of a lattice which is a modular but not a
distributive.
t2 1/9 Ans.
= =
(1 – 5t)(1 – 2t) t 1/3 3 – 5 3 – 2 a.
3 3 1. The theorem is true if the subset has 1 element, the element being
1 its own glb and lub.
= – 2. It is also true if the subset has 2 elements.
2
Discrete Structures & Theory of Logic SP–13 C (CS/IT-Sem-3) SP–14 C (CS/IT-Sem-3) Solved Paper (2016-17)
3. Suppose the theorem holds for all subsets containing 1, 2, ..., k A binary tree with 12 vertices :
elements, so that a subset a1, a2, ..., ak of L has a glb and a lub.
A
4. If L contains more than k elements, consider the subset
B C
{a1, a2, ..., ak + 1} of L.
D G
5. Let w = lub (a1, a2, ..., ak). E F
6. Let t = lub (w, ak + 1). H I
7. If s is any upper bound of a1, a2, ..., ak + 1, then s is each of a1, a2, ..., J K L
ak and therefore s w. Fig. 3.
8. Also, s ak + 1 and therefore s is an upper bound of w and ak + 1. Preorder (NLR) : A B D H I E J C F K L G
9. Hence s t. Inorder (LNR) : HDIBJEAKFLCG
10. That is, since t each a1, t is the lub of a1, a2, ..., ak + 1. Postorder (LRN) : H I D J E B K L F G C A
11. The theorem follows for the lub by finite induction. Section-C
12. If L is finite and contains m elements, the induction process stops
when k + 1 = m. Note : Attempt any two questions from this section. (15 × 2 = 30)
b. 10. a. Prove that a connected graph G is Euler graph if and only if
1. The diamond is modular, but not distributive. every vertex of G is of even degree.
2. Obviously the pentagon cannot be embedded in it. b. Which of the following simple graph have a Hamiltonian
3. The diamond is not distributive : circuit or, if not a Hamiltonian path ?
y (x z) = y (y x) (y z) = 1 a b a b a b g
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.
c d c f
e d c e
9. Explain in detail about the binary tree traversal with an
example.
d
Ans. 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 G1 G2 G3
we have three types of traversal : Fig. 4.
1. Preorder traversal : Each vertex is visited in the following order : Ans.
a. Visit the root (N). a.
b. Visit the left child (or subtree) of root (L). 1. First of all we shall prove that if a non-empty connected graph is
c. Visit the right child (or subtree) of root (R). Eulerian then it has no vertices of odd degree.
2. Postorder traversal : 2. Let G be Eulerian.
a. Visit the left child (subtree) of root. 3. Then G has an Eulerian trail which begins and ends at u.
b. Visit the right child (subtree) of root. 4. If we travel along the trail then each time we visit a vertex. We use
c. Visit the root. two edges, one in and one out.
3. Inorder traversal : 5. This is also true for the start vertex because we also end there.
a. Visit the left child (subtree) of root. 6. Since an Eulerian trail uses every edge once, the degree of each
b. Visit the root. vertex must be a multiple of two and hence there are no vertices of
c. Visit the right child (subtree) of root. 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) SP–16 C (CS/IT-Sem-3) Solved Paper (2016-17)
But since ghG they would be repeated elements in the union. So, B.Tech.
the union of all left cosets of H in G is G, i.e.,
Z6 = {[0], [1], [2], [3], [4], [5]} (SEM. III) ODD SEMESTER
c. Let Z6 = {[0], [1], [2], [3], [4], [5]} be a group.
H = {[0], [3]} be a subgroup of (Z6, +6).
THEORY EXAMINATION, 2017-18
The left cosets of H are, DISCRETE STRUCTURES &
[0] + H = {[0], [3]}
[1] + H = {[1], [4]}
THEORY OF LOGIC
[2] + H = {[2], [5]}
[3] + H = {[3], [0]} Time : 3 Hours Max. Marks : 70
[4] + H = {[4], [1]}
[5] + H = {[5], [2]} 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) Discrete Structures & Theory of Logic SP–3 C (CS/IT-Sem-3)
e. Simplify the following Boolean function using K-map : Note : 1. Attempt all Sections. If require any missing data; then choose
F(x, y, z) = (0, 2, 3, 7) suitably.
2. Any special paper specific instructions.
SECTION-C
3. Attempt any one part of the following : (7 × 1 = 7) SECTION – A
a. Solve ar – 6ar – 1 + 8ar – 2 = r.4r, given a0 = 8, and a1 = 1.
1. Attempt all questions in brief. (2 × 7 = 14)
b. Show that : (r ~ q, r S, S ~ q, p q) ~ p are a. Define Eulerian path, circuit and graph.
inconsistent. Ans. Eulerian path : A path of graph G which includes each edge of G
exactly once is called Eulerian path.
4. Attempt any one part of the following : (7 × 1 = 7) Eulerian circuit : A circuit of graph G which include each edge of
a. Write the properties of group. Show that the set (1, 2, 3, 4, 5) G exactly once.
is not group under addition and multiplication modulo 6. Eulerain graph : A graph containing an Eulerian circuit is called
Eulerian graph.
b. Prove by mathematical induction
n4 – 4n2 is divisible by 3 for all n > = 2. b. Let A = (2, 4, 5, 7, 8) = B, aRb if and only if a + b <= 12. Find
5. Attempt any one part of the following : (7 × 1 = 7) relation matrix.
a. Explain modular lattice, distribute lattice and bounded Ans. R = {(2, 4), (2, 5), (2, 7), (2, 8) (4, 2), (4, 5), (4, 7), (4, 8) (5, 2), (5, 4),
lattice with example and diagram. (5, 7), (7, 2), (7, 4), (7, 5), (8, 2), (8, 4), (2, 2), (4, 4), (5, 5)}
2 4 5 7 8
b. Draw the Hasse diagram of (A, ), where 2 1 1 1 1 1
A = {3, 4, 12, 24, 48, 72} and relation be such that a b if a
4 1 1 1 1 1
divides b.
mij = 5 1 1 1 1 0
6. Attempt any one part of the following : (7 × 1 = 7)
7 1 1 1 0 0
a. Given the inorder and postorder traversal of a tree T :
Inorder : HFEABIGDC Postorder : BEHFACDGI 8 1 1 0 0 0
Determine the tree T and it's Preorder.
c. Explain edge colouring and k-edge colouring.
b. Translate the following sentences in quantified expressions Ans. Edge coloring : An edge coloring of a graph G may also be thought
of predicate logic. of as equivalent to a vertex coloring of the line graph L(G), the
i. All students need financial aid. ii. Some cows are not white. graph that has a vertex for every edge of G and an edge for every
iii. Suresh will get if division if and only if he gets first div. pair of adjacent edges in G.
iv. If water is hot, then Shyam will swim in pool. k-edge coloring : A proper edge coloring with k different colors is
v. All integers are either even or odd integer. called a (proper) k-edge coloring.
7. Attempt any one part of the following : (7 × 1 = 7) d. Define chromatic number and isomorphic graph.
a. Define and explain any two the following : Ans. Chromatic number : The minimum number of colours required
1. BFS and DFS in trees for the proper colouring of a graph so that no two adjacent vertices
2. Euler graph have the same colour, is called chromatic number of a graph.
3. Adjacency matrix of a graph Isomorphic graph : If two graphs are isomorphic to each other
then :
b. Solve the recurrence relation : ar + 4ar – 2 + 4ar – 2 = r2. i. Both have same number of vertices and edges.
SP–4 C (CS/IT-Sem-3) Solved Paper (2017-18) Discrete Structures & Theory of Logic SP–5 C (CS/IT-Sem-3)
ii. Degree sequence of both graphs are same (degree sequence is the Ans. 3 + 33 + 333 + ............ + 3333 ... = (10n + 1 – 9n – 10)/27
sequence of degrees of the vertices of a graph arranged in non- Let given statement be denoted by S(n)
increasing order). 1. Inductive base : For n = 1
(102 9(1) 10) 100 19 81
e. Define union and intersection of multiset and find for
3= ,3= =3
27 27 27
A = [1, 1, 4, 2, 2, 3], B = [1, 2, 2, 6, 3, 3] 3 = 3. Hence S(1) is tree.
Ans. Union : Let A and B be two multisets. Then, A B, is the multiset 2. Inductive hypothesis : Assume that S(k) is true i.e.,
where the multiplicity of an element in the maximum of its 3 + 33 + 333 + ............ + 3333 = (10k + 1 – 9k – 10)/27
multiplicities in A and B. 3. Inductive steps : We have to show that S(k + 1) is also true i.e.,
Intersection : The intersection of A and B, A B, is the multiset 3 + 33 + 333 + ............ (10k + 2 – 9(k + 1) – 10)/27
where the multiplicity of an element is the minimum of its Now, 3 + 33 + ............ + 33 ............ 3
multiplicities in A and B. = 3 + 33 + 333 + ............ + 3 ............ 3
Numerical : = (10k + 1 – 9k – 10)/27 + 3(10k + 1 – 1)/9
A = {1, 1, 4, 2, 2, 3}, B = {1, 2, 2, 6, 3, 3} = (10k + 1 + 9k – 10 + 9.10k + 1 – 9)/27
Union : A B = {1, 2, 3, 4, 6} = (10k + 1 + 9.10k + 1 – 9k – 8 – 10)/27 = (10k + 2 – 9(k + 1) – 10)/27
Intersection : A B = {1, 2, 2, 3} 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.
f. Find the contrapositive of “If he has courage, then he will
b. Define the following with one example :
win”.
i. Bipartite graph ii. Complete graph
Ans. If he will not win then he does not have courage.
iii. How many edges in K7 and K3, 6 iv. Planar graph
g. Define rings and write its properties. Ans.
i. Bipartite graph : A graph G = (V, E) is bipartite if the vertex set
Ans. Ring : A non-empty set R is a ring if it is equipped with two binary
V can be partitioned into two subsets (disjoint) V1 and V2 such that
operations called addition and multiplication and denoted by '+'
every edge in E connects a vertex in V1 and a vertex V2 (so that no
and '.' respectively i.e., for all a, b R we have a + b R and a.b R
edge in G connects either two vertices in V1 or two vertices in V2).
and it satisfies the following properties :
(V1, V2) is called a bipartition of G.
i. Addition is associative i.e.,
(a + b) + c = a + (b + c) a, b, c R x1 x2 x3 x1 x2 x3 x4
which
ii. Addition is commutative i.e., x4
redrawn
a + b = b + a a, b R as :
iii. There exists an element 0 R such that y1 y2 y3 y1 y2 y3
0 + a = a = a + 0, a R
Fig. 1. Some bipartite graphs.
iv. To each element a in R there exists an element – a in R such that
a + (– a) = 0 ii. Complete graph : A simple graph, in which there is exactly one
v. Multiplication is associative i.e., edge between each pair of distinct vertices is called a complete
graph. The complete graph of n vertices is denoted by Kn. The
a.(b.c) = (a.b).c, a b, c R
graphs K1 to K5 are shown below in Fig. 2.
vi. Multiplication is distributive with respect to addition i.e., for all
a, b, c R,
SECTION-B
K1 K2 K3 K4 K5
2. Attempt any three of the following : (7 × 3 = 21) Fig. 2.
a. Prove by mathematical induction
n(n – 1) n
3 + 33 + 333 + ............ 3333 = (10n + 1 – 9n – 10)/27 Kn has exactly = C2 edges
2
SP–6 C (CS/IT-Sem-3) Solved Paper (2017-18) Discrete Structures & Theory of Logic SP–7 C (CS/IT-Sem-3)
iii. Number of edge in K7 : Since, Kn is complete graph with n vertices. (y – x) = – 3n2 = 3n2, n2 is also an integer
7(7 1) 7 6 So, y – x is divisible by 3 or R is symmetric.
Number of edge in K7 = = 21
2 2 iii. Transitive : Let x, y, z X and (x, y) R, (y, z) R
Number of edge in K3, 6 : Then x – y = 3n1, y – z = 3n2, n1, n2 being integers
Since, Kn, m is a complete bipartite graph with n V1 and m V2 x – z = 3(n1 + n2), n1 + n2 = n3 be any integer
Number of edge in K3, 6 = 3 × 6 = 18 So, (x – z) is also divisible by 3 or (x, z) R
iv. Planar graph : So, R is transitive.
A graph G is said to be planar if there exists some geometric Hence, R is an equivalence relation.
representation of G which can be drawn on a plane such that no
two of its edges intersect except only at the common vertex. 1 3
2
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.
4 7 6
5
Fig. 4. Diagraph of R.
(a) (b )
Fig. 3. Some planar graph. e. Simplify the following Boolean function using K-map :
F(x, y, z) = (0, 2, 3, 7)
c. For any positive integer D36, then find whether (D36, ‘|’) is Ans.
yz
lattice or not ? x 00 01 11 10
Ans. D36 = Divisor of 36 = {1, 2, 3, 4, 6, 9, 12, 18, 36} 0 1 1 1
Hasse diagram :
1 1
(1 3) = {3, 6}, (1 2) = {2, 4}, (2 6) = {6, 18}, (9 4) = {}
36
F = x z yz
12 12
SECTION-C
6
4 9 3. Attempt any one part of the following : (7 × 1 = 7)
3
a. Solve ar – 6ar – 1 + 8ar – 2 = r.4r, given a0 = 8, and a1 = 1.
2
Ans. ar – 6ar – 1 + 8ar – 2 = r4r
1 The characteristic equation is, x2 – 6x + 8 = 0, x2 – 2x – 4x + 8 = 0
Since, 9 4 = {}
(x – 2) (x – 4) = 0, x = 2, 4
So, D36 is not a lattice.
The solution of the associated non-homogeneous recurrence relation is,
ar(h) = B1(2)r + B2(4)r ...(1)
d. Let X = {1, 2, 3 ...... 7} and R = {(x, y)|(x – y) is divisible by 3}. Is
Let particular solution of given equation is, ar(p) = r2(A0 + A1r)4r
R equivalence relation. Draw the digraph of R.
Substituting in the given equation, we get
Ans. Given that X = {1, 2, 3, 4, 5, 6, 7}
r2(A0 + A1r)4r – 6(r – 1)2 (A0 + A1(r – 1))4r – 1
and R = {(x, y) : (x – y) is divisible by 3 }
+ 8(r – 2)2 (A0 + A1(r – 2)4r – 2 = r4r
Then R is an equivalence relation if
6
i. Reflexive : x X ( x x) is divisible by 3 r 2A 0 + A 1r 3 – [(A0r2 – 2A0r + A0) + (A1r3 – A1 – 3A1r2 + 3A1r)2]
4
So, ( x, x) X x X or, R is reflexive. 8
ii. Symmetric : Let x, y X and (x, y) R + 2 [(A0r2 – 4rA0 + 4A0) + (A1r3 – 8A1 – 6A1r2 + 12A1r)] = r
4
(x – y) is divisible by 3 (x – y) = 3n1, (n1 being an integer)
SP–8 C (CS/IT-Sem-3) Solved Paper (2017-18) Discrete Structures & Theory of Logic SP–9 C (CS/IT-Sem-3)
We need to show that (n + 1)4 – 4(n + 1)2 is divisible by 3. By the Bounded lattice : Since, the given lattice has 1 as greatest and 0
inductive hypothesis, we know that n4 – 4n2 is divisible by 3. as least element so it is bounded lattice.
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. b. Draw the Hasse diagram of (A, ), where
Now (n + 1)4 – 4(n + 1)2 – (n4 – 4n2) A = {3, 4, 12, 24, 48, 72} and relation be such that a b if a
= n4 + 4n3 + 6n2 + 4n + 1 – 4n2 – 8n – 4 – n4 + 4n2 divides b.
= 4n3 + 6n2 – 4n – 3, Ans. Hasse diagram of (A, ) where A = {3, 4, 12, 24, 48, 72}
which is divisible by 3 if 4n3 – 4n is. Since 4n3 – 4n = 4n(n + 1) 1
(n – 1), we see that 4n3 – 4n is always divisible by 3.
Going backwards, we conclude that (n + 1)4 – 4(n + 1)2 is divisible by
3, and that the inductive hypothesis holds for n + 1. a b c
By the Principle of Mathematical Induction, n4 – 4n2 is divisible by 3,
for all n N.
0
Fig. 6.
5. Attempt any one part of the following : (7 × 1 = 7)
a. Explain modular lattice, distribute lattice and bounded
6. Attempt any one part of the following : (7 × 1 = 7)
lattice with example and diagram.
a. Given the inorder and postorder traversal of a tree T :
Ans. Modular distributive and bounded lattice :
Inorder : HFEABIGDC Postorder : BEHFACDGI
Types of lattice :
Determine the tree T and it's Preorder.
1. 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. Ans. The root of tree is I.
2. Distributive lattice : A lattice L is said to be distributive if for I
any element a, b and c of L following properties are satisfied : Now elements on right of I are D, G, C and G comes last of all in
i. a (b c) = (a b) (a c) postorder traversal.
ii. a (b c) = (a b) (a c) I
otherwise L is non-distributive lattice. G
3. Bounded lattice : A lattice L is said to be bounded if it has a Now D and C are on right of G and D comes last of G and I postorder
greatest element 1 and a least element 0. In such lattice we have traversal so
a 1 = 1, a 1 = a
a 0 = a, a 0 = 0 I
a Land 0 a I G
Example : D
Let consider a Hasse diagram : C
1
Now element left of I are H F E A B in inorder traversal and A
comes last of all in postorder traversal. Therefore tree will be
a b c I
G
A D
0 C
Fig. 5.
Now H F E are on left of A in inorder traversal and B comes last of all
Modular lattice :
and continuing in same manner. We will get final binary tree as
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.
SP–12 C (CS/IT-Sem-3) Solved Paper (2017-18) Discrete Structures & Theory of Logic SP–13 C (CS/IT-Sem-3)
some arbitrary node as the root in the case of a graph) and explores
I
as far as possible along each branch before backtracking.
G
A Algorithmic steps :
D
F B C Step 1 : Push the root node in the stack.
Step 2 : Loop until stack is empty.
H E Step 3 : Pick the node of the stack.
Preorder traversal of above binary tree is CAFHEBDGI Step 4 : If the node has unvisited child nodes, get the unvisited
child node, mark it as traversed and push it on stack.
b. Translate the following sentences in quantified expressions Step 5 : If the node does not have any unvisited child nodes, pop the
of predicate logic. node from the stack.
i. All students need financial aid. ii. Some cows are not white. 2. Eulerian graph : A graph containing an Eulerian circuit is called
iii. Suresh will get if division if and only if he gets first div. Eulerian graph.
iv. If water is hot, then Shyam will swim in pool. For example : Graphs given below are Eulerian graphs.
v. All integers are either even or odd integer. V1 V3 A B
V2
Ans.
i.x [S(x) F(x)]
ii.~ [(x) (C(x) W(x))] V5 V4 D C
iii.Sentence is incorrect so cannot be translated into quantified expression. Fig. 7.
iv. W(x) : x is water Eulerian path : A path of graph G which includes each edge of G
H(x) : x is hot
exactly once is called Eulerian path.
S(x) : x is Shyam
Eulerian circuit : A circuit of graph G which include each edge of
P(x) : x will swim in pool
G exactly once.
x [((W(x) H(x)) (S(x) P(x))]
The existence of Eulerian paths or Eulerian circuits in a graph is
v. E(x) : x is even
O(x) : x is odd related to the degree of vertices.
x (E(x) O(x)) a. Adjacency matrix :
i. Representation of undirected graph :
7. Attempt any one part of the following : (7 × 1 = 7) The adjacency matrix of a graph G with n vertices and no parallel
a. Define and explain any two the following : edges is a n × n matrix A = [aij] whose elements are given by
1. BFS and DFS in trees aij = 1, if there is an edge between ith and jth vertices
2. Euler graph
= 0, if there is no edge between them
3. Adjacency matrix of a graph
ii. Representation of directed graph :
Ans.
1. Breadth First Search (BFS) : Breadth First Search (BFS) is an The adjacency matrix of a digraph D, with n vertices is the matrix
algorithm for traversing or searching tree or graph data structures. A = [aij]n×n in which
It starts at the tree root and explores the neighbour nodes first,
aij = 1 if arc (vi, vj) is in D
before moving to the next level neighbours.
Algorithmic steps : = 0 otherwise
Step 1 : Push the root node in the queue. For example :
Step 2 : Loop until the queue is empty. V1 V4
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. V2 V3
Depth First Search (DFS) :
Fig. 8.
Depth First Search (DFS) is an algorithm for traversing or searching
tree or graph data structures. One starts at the root (selecting
SP–14 C (CS/IT-Sem-3) Solved Paper (2017-18) Discrete Structures & Theory of Logic SP–1 C (CS/IT-Sem-3)
v1 v2 v3 v4 B.Tech.
v1 0 1 1 1
(SEM. III) ODD SEMESTER
A = v2 1 0 1 0
v3 1 1 0 1
THEORY EXAMINATION, 2018-19
DISCRETE STRUCTURES AND
v4 1 0 1 0
THEORY OF LOGIC
b. Solve the recurrence relation : ar + 4ar – 2 + 4ar – 2 = r2.
Ans. ar + 4ar – 1 + 4ar – 2 = r2 Time : 3 Hours Max. Marks : 70
The characteristic equation is,
x2 + 4x + 4 = 0 Note : 1. Attempt all Sections. If require any missing data; then choose
(x + 2)2 = 0
suitably.
x = –2, – 2 2. Any special paper specific instructions.
The homogeneous solution is, a(h) = (A0 + A1r) (– 2)r
The particular solution be, a(p) = (A0 + A1r) r2 SECTION – A
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 1. Attempt all questions in brief. (2 × 7 = 14)
a. Find the power set of each of these sets, where a and b are
A0(r2 + 4r2 – 8r + 4 + 4r2 – 16r + 16) +A1 (r3 + 4r3 – 4 – 12r2 + 12r + 4r3
distinct elements.
– 32 – 24r2 + 48r) = r2
i. {a} ii. {a, b}
A0(9r2 – 24r + 20) + A1(9r3 – 48r2 + 60r – 36) = r2 iii. {, {}} iv. {a, {a}}
Comparing the coefficient of same power of r, we get
9A0 – 48A1 = 1 ...(1) b. Define ring and field.
20A0 – 36A1 = 0 ...(2)
c. Draw the Hasse diagram of D30.
3 5
Solving equation (1) and (2) A0 = A1
53 159 d. What are the contrapositive, converse, and the inverse of
The complete solution is, the conditional statement : “The home team wins whenever
3 5 2 it is raining” ?
ar = ar(p) + ar(h) = (A0 + A1r) (– 2)r + r r
53 159
e. How many bit strings of length eight either start with a ‘1’
bit or end with the two bit ‘00’ ?
SECTION-B
French and Russian, how many students have taken a b. Find the Sum-Of-Products and Product-Of-sum expansion
course in all three languages ? of the Boolean function F(x, y, z) = (x + y) z.
b. i. Let H be a subgroup of a finite group G. Prove that order of 6. Attempt any one part of the following : (7 × 1 = 7)
H is a divisor of order of G. a. What is a tautology, contradiction and contingency ? Show
that (p q) ( p r) (q r) is a tautology, contradiction
ii. Prove that every group of prime order is cyclic. or contingency.
c. Define a lattice. For any a, b, c, d in a lattice (A, ) if a b and b. Show that the premises “It is not sunny this afternoon and
c d then show that a c b d and a c b d. 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
d. Show that ((p q) ~ (~p (~q ~r))) (~p ~q) (~ p r) is canoe trip.” and “If we take a canoe trip, then we will be
a tautology without using truth table. home by sunset” lead to the conclusion “We will be home by
sunset.”
e. Define a binary tree. A binary tree has 11 nodes. It’s inorder
and preorder traversals node sequences are : 7. Attempt any one part of the following : (7 × 1 = 7)
Preorder : A B D H I E J L C F G a. What are different ways to represent a graph. Define Euler
Inorder : H D I B J E K A F C G circuit and Euler graph. Give necessary and sufficient
Draw the tree. conditions for Euler circuits and paths.
3. Attempt any one part of the following : (7 × 1 = 7) b. Suppose that a valid codeword is an n-digit number in
a. Prove that if n is a positive integer, then 133 divides 11n + 1 + decimal notation containing an even number of 0’s. Let an
122n – 1. denote the number of valid codewords of length n satisfying
the recurrence relation an = 8an – 1 + 10n – 1 and the initial
b. Let n be a positive integer and S a set of strings. Suppose condition a1 = 9. Use generating functions to find an explicit
that Rn is the relation on S such that sRnt if and only if formula for an.
s = t, or both s and t have at least n characters and first n
characters of s and t are the same. That is, a string of fewer
than n characters is related only to itself; a string s with at
least n characters is related to a string t if and only if t has
at least n characters and t beings with the n characters at
the start of s.
Ans.
SOLUTION OF PAPER (2018-19)
30
Note : 1. Attempt all Sections. If require any missing data; then choose 6 15
suitably. 10
2. Any special paper specific instructions. 3
2 5
SECTION – A 1
Fig. 1.
1. Attempt all questions in brief. (2 × 7 = 14)
a. Find the power set of each of these sets, where a and b are d. What are the contrapositive, converse, and the inverse of
distinct elements. the conditional statement : “The home team wins whenever
i. {a} ii. {a, b} it is raining” ?
iii. {, {}} iv. {a, {a}} Ans. Given : The home team wins whenever it is raining.
Ans. q(conclusion) : The home team wins.
i. Power set of {a} = {{}, {a}} p(hypothesis) : It is raining.
ii. Power set of {a, b} = {{}, {a}, {b}, {a, b}} Contrapositive : ~ q ~ p is “if the home team does not win
iii. Power set of {, {}} = {} then it is not raining”.
iv. Power set of {a, {a}} = {{}, {a}, {{a}}, {a, {a}}} Converse : q p is “if the home team wins then it is raining”.
Inverse : ~ p ~ q is “if it is not raining then the home team does
b. Define ring and field. not win”.
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 '+' e. How many bit strings of length eight either start with a ‘1’
and '.' respectively i.e., for all a, b R we have a + b R and a.b R bit or end with the two bit ‘00’ ?
and it satisfies the following properties : Ans.
i. Addition is associative i.e., 1. Number of bit strings of length eight that start with a 1 bit :
(a + b) + c = a + (b + c) a, b, c R 27 = 128.
ii. Addition is commutative i.e., 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
a + b = b + a a, b R
and end with bits 00 : 25 = 32
iii. There exists an element 0 R such that Hence, the number is 128 + 64 – 32 = 160.
0 + a = a = a + 0, a R
iv. To each element a in R there exists an element – a in R such that f. Define injective, surjective and bijective function.
a + (– a) = 0 Ans.
v. Multiplication is associative i.e., 1. One-to-one function (Injective function or injection) : Let
a.(b.c) = (a.b).c, a b, c R 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
vi. Multiplication is distributive with respect to addition i.e., for all
a, b, c R, f(x1) = f(x2) implies x1 = x2 x1, x2, X
Field : A ring R with at least two elements is called a field if it has
following properties : A B
f
i. R is commutative
ii. R has unity
iii. R is such that each non-zero element possesses multiplicative
inverse.
=11 * 11k+1 + 144 * 122k–1 1. Closure property : Since all the entries of the composition table
=11 * 11k+1 + 11 * 122k–1 + 133 * 122k–1 are the elements of the given set, the set G is closed under
=11[11k+1 + 122k–1] + 133 * 122k–1 multiplication.
=11* 133A + 133 * 122k–1 2. Associativity : The elements of G are complex numbers, and we
= 133[11A + 122k–1] know that multiplication of complex numbers is associative.
Thus if the hypothesis holds for n = k it also holds for n = k + 1. 3. Identity : Here, 1 is the identity element.
Therefore, the statement given in the equation is true. 4. Inverse : From the composition table, we see that the inverse
elements of 1, – 1, i, – i are 1, – 1, – i, i respectively.
b. Let n be a positive integer and S a set of strings. Suppose 5. Commutativity : The corresponding rows and columns of the
that Rn is the relation on S such that sRnt if and only if table are identical. Therefore the binary operation is commutative.
s = t, or both s and t have at least n characters and first n Hence, (G, *) is an abelian group.
characters of s and t are the same. That is, a string of fewer
than n characters is related only to itself; a string s with at b. What is meant by ring ? Give examples of both commutative
least n characters is related to a string t if and only if t has and non-commutative rings.
at least n characters and t beings with the n characters at Ans. Ring : A ring is an algebraic system (R, +, •) where R is a non
the start of s. empty set and + and • are two binary operations (which can be
Ans. We have to show that the relation Rn is reflexive, symmetric, and different from addition and multiplication) and if the following
transitive. conditions are satisfied :
1. Reflexive : The relation Rn is reflexive because s = s, so that sRns 1. (R, +) is an abelian group.
whenever s is a string in S. 2. (R, •) is semigroup i.e., (a • b) • c = a • (b • c) a, b, c R.
2. Symmetric : If sRn t, then either s = t or s and t are both at least n 3. The operation • is distributive over +.
characters long that begin with the same n characters. This means i.e., for any a, b, c R
that tRn s. We conclude that Rn is symmetric. a • (b + c) = (a • b) + (a • c) or (b + c) • a = (b • a) + (c • a)
3. Transitive : Now suppose that sRn t and tRn u. Then either s = t or Example of commutative ring :
s and t are at least n characters long and s and t begin with the same Let a, b R (a + b)2 = (a + b)
n characters, and either t = u or t and u are at least n characters (a + b) (a + b) = (a + b)
long and t and u begin with the same n characters. From this, we (a + b)a + (a + b)b = (a + b)
can deduce that either s = u or both s and u are n characters long (a2 + ba) + (ab + b2) = (a + b)
and s and u begin with the same n characters, i.e., sR n u. (a + ba) + (ab + b) = (a + b) ( a2 = a and b2 = b)
Consequently, Rn is transitive. (a + b) + (ba + ab) = (a + b) + 0
ba + ab = 0
4. Attempt any one part of the following : (7 × 1 = 7) a + b = 0 a + b = a + a [being every element of its own additive
a. Let G = {1, – 1, i, – i} with the binary operation multiplication inverse]
be an algebraic structure, where i = 1 . Determine b=a
ab = ba
whether G is an abelian or not.
R is commutative ring.
Ans. The composition table of G is Example of non-commutative ring : Consider the set R of 2 × 2
matrix with real element. For A, B, C R
* 1 –1 i –i
A * (B + C) = (A * B) + (A * C)
1 1 –1 i –i also, (A + B) * C = (A * C) + (B * C)
* is distributive over +.
–1 –1 1 –i i (R, +, *) is a ring.
i i –i –1 1 We know that AB BA, Hence (R, +, *) is non-commutative ring.
inclusion on the set P(S), where S = {a, b, c, d}. Also determine Sum-Of-Product :
whether (P(S), ) is a lattice. F(x, y, z) = xyz + xyz + xyz
Ans. Show that the inclusion relation () is a partial ordering on the Product-Of-Sum :
power set of a set S. F(x, y, z) = (x + y + z)(x + y+ z)(x+ y + z)(x+ y+ z)
Reflexivity : A A whenever A is a subset of S. (x+ y+ z')
Antisymmetry : If A and B are positive integers with A B and B
A, then A = B. 6. Attempt any one part of the following : (7 × 1 = 7)
Transitivity : If A B and B C, then A C. a. What is a tautology, contradiction and contingency ? Show
Hasse diagram : that (p q) ( p r) (q r) is a tautology, contradiction
{a, b, c, d} or contingency.
Ans. Tautology, contradiction and contingency :
1. Tautology : Tautology is defined as a compound proposition that is
always true for all possible truth values of its propositional variables
{a, b, d} {a, c, d}
{a, b, c} {b, c, d} 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.
{a, c} {b, c} {b, d} {c, d}
{a, b} {a, c} 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
{a} {b} {c} {d} 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.
Fig. 6. 3. Contingency : A proposition which is neither tautology nor
(P(S), ) is not a lattice because ({a, b},{b, d}) has no lub and glb. contradiction is called contingency.
Here the last column of truth table contains both T and F.
b. Find the Sum-Of-Products and Product-Of-sum expansion Proof : ((p q) (~ p r)) (q r)
of the Boolean function F(x, y, z) = (x + y) z.
Ans. F(x, y, z) = (x + y)z
p q r ~P (p q) (~ p r) (A B) (q r) C D
=A =B =C =D
x y z x+y z (x + y)z
F F F T F T T F F
1 1 1 1 0 0
F F T T F T T T T
1 1 0 1 1 1 F T F T T T T T T
1 0 1 1 0 0 F T T T T T T T T
1 0 0 1 1 1 T F F F T F T F F
0 1 1 1 0 0 T F T F T T T T T
T T F F T F T T T
0 1 0 1 1 1
T T T F T T T T T
0 0 1 0 0 0
So, ((p q) (~ p r)) (q r) is contingency.
0 0 0 0 1 0
SP–14 C (CS/IT-Sem-3) Solved Paper (2018-19) Discrete Structures & Theory of Logic SP–15 C (CS/IT-Sem-3)
b. Show that the premises “It is not sunny this afternoon and ii. Representation of directed graph
it is colder than yesterday,” “We will go swimming only if it b. Incidence matrix :
is sunny,” “If we do not go swimming, then we will take a i. Representation of undirected graph
canoe trip.” and “If we take a canoe trip, then we will be ii. Representation of directed graph
home by sunset” lead to the conclusion “We will be home by 2. Linked representation : In this representation, a list of vertices
sunset.” adjacent to each vertex is maintained. This representation is also
Ans. called adjacency structure representation. In case of a directed
i. The compound proposition will be : (p q r) s graph, a care has to be taken, according to the direction of an edge,
ii. Let p be the proposition “It is sunny this afternoon”, q be the while placing a vertex in the adjacent structure representation of
proposition “It is colder than yesterday”, r be the proposition “We another vertex.
will go swimming”, s be the proposition ‘‘We will take a canoe trip’’, Euler circuit and Euler graph :
and t be the proposition “We will be home by sunset”. Eulerian circuit : A circuit of graph G which include each edge of
Then the hypothesis becomes p q, r p, r s, and s t. The G exactly once.
conclusion is simply t. Eulerain graph : A graph containing an Eulerian circuit is called
We construct an argument to show that our hypothesis lead to the Eulerian graph.
conclusion as follows : For example : Graphs given below are Eulerian graphs.
V1 V3 A B
S. No. Step Reason V2
1. pq Hypothesis V5 V4 D C
2. p Simplification using step 1 Fig. 7.
3. rp Hypothesis Necessary and sufficient condition for Euler circuits and
paths :
4. r Modus tollens using steps 2 and 3 1. A graph has an Euler circuit if and only if the degree of every
vertex is even.
5. rs Hypothesis
2. A graph has an Euler path if and only if there are at most two
6. s Modus ponens using steps 4 and 5 vertices with odd degree.
the fact that many results of matrix algebra can be readily applied G(x) – 1 =
n 1
an x n (8a
n 1
n –1 x
n
10 n–1 x n )
to study the structural properties of graph from an algebraic point
of view.
a. Adjacency matrix : = 8 a
n 1
n –1 x
n
10
n 1
n –1 n
x
i. Representation of undirected graph
SP–16 C (CS/IT-Sem-3) Solved Paper (2018-19) Discrete Structures & Theory of Logic SP–1 C (CS/IT-Sem-3)
B.Tech.
= 8x a
n 1
n –1 x
n –1
x 10
n 1
n –1 n –1
x
(SEM. III) ODD SEMESTER
THEORY EXAMINATION, 2019-20
= 8x a x
n 0
n
n
x 10
n 0
n
xn
DISCRETE STRUCTURES & THEORY
= 8xG(x) + x/(1 – 10x) OF LOGIC
Therefore, we have
G(x) – 1 = 8xG(x) + x/(1 – 10x) Time : 3 Hours Max. Marks : 100
Expanding the right hand side of the equation into partial fractions
gives
Note : 1. Attempt all Section.
G(x) =
1 1 1
2 1 8 x 1 10 x
Section-A
This is equivalent to
1. Answer all questions in brief. (2 × 10 = 20)
1
G(x) =
2 n 0
8n xn 10 n x n
a. Define various types of functions.
n 0
b. How many symmetric and reflexive relations are possible
1 n from a set A containing ‘n’ elements ?
= (8 10n ) x n
n 0
2
c. Let Z be the group of integers with binary operation *
1 n defined by a * b = a + b – 2, for all a, b Z. Find the identity
an = (8 10n )
2 element of the group (Z, *).
Section-C
3. Answer any one part of the following : (1 × 10 = 10)
a. Find the number between 1 to 500 that are not divisible by
any of the integers 2 or 3 or 5 or 7.
= (P T) (Q R) (T Q)( P R) [ T P = T] Now remove vertex x and edge incident on v.
= (Q R) ( P R) Then we will left with graph G* given as
So, the given expression is not a tautology.
(a) (b ) e
Fig. 1. Some planar graph.
Proof : We will use induction to prove this theorem. v2 v3
Step I : Inductive base : Fig. 5.
Assume that e = 1 Then we have two cases given in figure below : 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
(a) (b)
Fig. 2.
In Fig. 1 (a) we have v = 2 and r = 1 v + r – e = 2 + 1 – 1 = 2 v2 v3
In Fig. 1 (b) we have v = 1 and r = 2 v + r – e = 1 + 2 – 1 = 2 Fig. 6.
Hence vertified Now number of edges in G* are k so by inductive hypothesis,
Step II : Inductive hypothesis : Euler formula holds for G*.
Let us assume that given theorem is true for e = k Now since G has one more edges and region than G* with same vertices.
i.e., for k edges So v + r – e = v + r1 + 1 – e1 – 1 = v + r1 – e1 = 2
Step III : Inductive step : Hence Euler’s formula also holds for G.
We have to show that theorem is true for k + 1 edges. Hence by Principle of mathematical induction Euler’s Theorem
Let graph G has k + 1 edges. holds true.
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 Section-C
we find an edge we have a new vertex atleast we will reach a
vertex with degree one as shown in Fig. 3. 3. Answer any one part of the following : (1 × 10 = 10)
a. Find the number between 1 to 500 that are not divisible by
x any of the integers 2 or 3 or 5 or 7.
v
Ans. Let A, B, C and D be the sets of integers between 1 and
500(inclusive) which are divisible by 2, 3, 5, and 7, respectively.
We want |(A B C D)C|. Now
Fig. 3.
SP–10 C (CS/IT-Sem-3) Solved Paper (2019-20) Discrete Structures & Theory of Logic SP–11 C (CS/IT-Sem-3)
|(A B C D)| = |A| + |B| + |C| + |D| – |A B| – |A 3. The operation • is distributive over +.
C| – |A D| – |B C| – |B D| – |C D| + |A B C| + i.e., for any a, b, c R
|A B D| + |A C D| + |B C D| – |A B C D| a • (b + c) = (a • b) + (a • c) or (b + c) • a = (b • a) + (c • a)
We have Elementary properties of a ring :
500 500 500 500 Let a, b and c belong to a ring R. Then
|A| = = 250 |B| = = 166 |C| = = 100 |D| =
7
1. a.0 = 0. a = 0 2. a.(– b) = (– a).b = – (a.b)
2 3 5
= 71 3. (– a).(– b) = a.b
4. a(b – c) = a.b – a.c and (b – c).a = b.a – c.a
500 500 500
|A B| = = 83 |A C| = = 50 |A D| = = 35 For example : If a, b R then (a + b)2 = a2 + ab + ba + b2
6 10 14 We have (a + b)2 = (a + b) (a + b)
500 500 500 = a (a + b) + b (a + b) [by right distributive law]
|B C| = = 33 |B D| = = 23 |C D| = = 14
15 21 35 = (aa + ab) + (ba + bb)[by right distributive law]
500 500 = a2 + ab + ba + b2
|A B C| = = 16 |A B D| = = 11
30 42
b. Prove or dis prove that intersection of two normal
500 500
|A C D| = = 7 |B C D| = =4 subgroups of a group G is again a normal subgroup of G.
70 105
Ans. Let H1 and H2 be any two subgroups of G. Since at least the identity
500 element e is common to both H1 and H2.
|A B C D| = =2
210 H1 H2
So |A B C D| = 385. In order to prove that H1 H2 is a subgroup, it is sufficient to prove
Hence, the number between 1 to 500 that are not divisible by 2 or that
3 or 5 or 7 is 500 – 385 = 115. a H1 H2, b H1 H2 ab–1 H1 H2
Now a H1 H2 a H1 and a H2
b. Is the “divides” relations on the set of positive integers b H1 H2 b H1 and b H2
transitive ? What is the reflexive and symmetric closure of But H1, H2 are subgroups. Therefore,
the relation ? a H1, b H1 ab–1 H1
R = {(a, b)|a > b} on the set of positive integers. a H2 , bH2 ab–1 H2
Ans. Yes, divides relation on the set of positive integers is transitive. Finally, ab–1 H1, ab–1 H2 ab–1 H1 H2
Numerical : Thus, we have shown that
Reflexive : a = a aa a H1 H2, b H1 H2 ab–1 H1 H2.
(a, a) R a is real number. Hence, H1 H2 is a subgroup of G.
R is reflexive
Symmetric : Let (a, b) R 5. Answer any one part of the following : (10 × 1 = 10)
a b b a (b, a) R a. Let (L, , , ) be a distribute lattice and a, b L. If a b = a
R is not symmetric c and a b = a c then show that b = c.
R is not an equivalence relation. Ans. b = b (a b) (Absorption)
= b (a c) (hypothesis)
4. Answer any one part of the following : (1 × 10 = 10) = (b a) (b c) (distributive law)
a. What is ring ? Define elementary properties of ring with = (a c) (b c) (hypothesis)
example. = (a b) c (distributive law)
Ans. Ring : A ring is an algebraic system (R, +, •) where R is a non- = (a c) c (hypothesis)
empty set and + and • are two binary operations (which can be =c (Absorption)
different from addition and multiplication) and if the following
conditions are satisfied : b. Obtain the principle disjunction and conjunctive normal
1. (R, +) is an abelian group. forms of the formula (p r) (q p).
2. (R, •) is semigroup i.e., (a • b) • c = a • (b • c) a, b, c R. Ans. Principle disjunction normal form :
(p r) (p q)
SP–12 C (CS/IT-Sem-3) Solved Paper (2019-20) Discrete Structures & Theory of Logic SP–13 C (CS/IT-Sem-3)
b. Prove the validity of the following argument “if the races b. A collection of 10 electric bulbs contain 3 defective ones.
are fixed so the casinos are cooked, then the tourist trade i. In how many ways can a sample of four bulbs be selected ?
will decline. If the tourist trade decreases, then the police ii. In how many ways can a sample of 4 bulbs be selected
will be happy. The police force is never happy. Therefore, which contain 2 good bulbs and 2 defective ones ?
the races are not fixed.” iii. In how many ways can a sample of 4 bulbs be selected so
Ans. Let that either the sample contain 3 good ones and 1 defectives
p : Race are fixed. ones or 1 good and 3 defectives ones ?
q : Casinos are cooked. Ans.
r : Tourist trade will decline. i. Four bulbs can be selected out of 10 bulbs in
s : Police will be happy. 10! 10 9 8 7
The above argument can be written in symbolic form as
10C =
= 210 ways
4
4! 6! 4 3 2 1
(p q) r
ii. Two bulbs can be selected out of 7 good bulbs in 7C2 ways and 2
r s~s
~ p defective bulbs can be selected out of 3 defective bulbs in 3C2 ways.
Thus, the number of ways in which a sample of 4 bulbs containing
So,
1. (p q) r (Given Premise) 2. r s (Given Premise) 2 good bulbs and 2 defective bulbs can be selected as
3. ~ s (Given Permise) 4. ~ r Modus tollens using 2 and 3 7! 3! 76
7C × 3C = 3 = 63
5. ~ (p q) Modus tollen using 1 and 4 2 2
2! 5! 2! 1! 2
6. ~ p ~ q iii. Three godd bulbs can be selected from 7 good bulbs in 7C3 ways
and 1 defective bulb can be selected out of 3 defective ones in 3C1
7. Answer any one part of the following : (7 × 1 = 7) ways.
a. Solve the following recurrence equation using generating Similarly, one good bulb can be selected from 7 good bulb in 7C1
function ways and 3 defective ones in 3C3 ways.
G(K) – 7 G(K – 1) + 10 G (K – 2) = 8K + 6 So, the number of ways of selecting a sample of 4 bulbs containing
Ans. G(K) – 7 G(K – 1) + 10 G (K – 2) = 8K + 6 3 good ones and 1 defective or 1 good and 3 defective ones are
Now, the characteristics equation is :
7! 3! 7! 3!
x2 – 7x + 10 = 0 7C
3 × 3C1 + 7C1 × 3C3 =
x2 – 5x – 2x + 10 = 0 3! 4! 1! 2! 1! 6! 3! 0!
x(x – 5) – 2(x – 5) = 0 765
= 3 7 = 35 × 3 + 7 = 112
x = 2, 5 32
The homogeneous solution is Gh(K) = C12K + C25K
Let the particular solution be
Gp(K) = A0 + A1K
A0 + A1 K – 7{A0 + A1(K – 1)} + 10 {A0 + A1(K – 2)} = 8K + 6
A0 + A1 K – 7A0 – 7A1K + 7A1 + 10A0 + 10A1K – 20A1 = 8K + 6
4 A0 + 4A1K – 13A1 = 8K + 6
Comparing the coefficient we get,
4A1 = 8
A1 = 2
4 A0 – 13A1 = 6
A0 = (6 + 13A1)/4 = (6 + 26)/4 = 8
Solution is given by
= Gh(K) + Gp(K) = C12K + C22K + 2K + 8