Download AKTU B-Tech 8th Sem 2016-17 Discrete Mathematics Question Paper

Download AKTU (Dr. A.P.J. Abdul Kalam Technical University (AKTU), formerly Uttar Pradesh Technical University (UPTU) B-Tech 8th Semester (Eight Semester) 2016-17 Discrete Mathematics Question Paper

PrintedPages :2 Roll No.| l l l l I l l l l l EOE048
B. TECH.
THEORY EXAMINATION (SEM?VIII) 2016-17
DISCRETE MATHEMATICS
Time : 3 Hours Max. Marks : 100
Note : Be precise in your answer. In case of numerical problem assume data wherever not provided.
SECTION ? A
1. Attempt all parts of the following question: 10 x 2 = 20
a) What is the difference in relation and function?
h) Define equivalence relation.
c) Transform following statement into symbolic form: J ack and J ill went up the hill.
(1) Define negation.
e) Find the permutations of the set A = {1, 2, 3, 4} taking two at a time.
f) There are 10 different people at a party. How many ways are there to pair them up into a
collection of 5 parings ?
g) Show that (I , +) is an abelian group.
h) Define cyclic group.
i) Define Hamiltonian Path.
j) Define Chromatic number.
SECTION ? B
2. Attempt any five parts of the following questions: 5 x 10 = 50
a) Let R be the relation on the set A of integers, defined by ny if x? y is divisible by 4. Show
that R is an equivalence relation, and describe the equivalence classes.
b) Show the implication
(i) (Pv?.P)?>Q?>(Pv?.P)?>R:>(Q?>R)
(ii) (P?)Q)?)Q:>PVQ
c) (c) Find the solution of recurrence relation an 2 6an_1 +11an_2 ? 6an_3 with condition
a0 =2,a1=5 and a2 =15
(1) Show that (F ,+,.) is a field where F is a set of all rational numbers and + and . are ordinary
addition and multiplication operators.
e) Show that number of odd degree vertices is always even.
f) Show that the graph shown in figure does not contain Hamiltonian Circuit.
0
A
b :3
g) Let G be a group; for fixed element G, let GX ={a eraxzxa} show that GX is a
subgroup of G for all x e G.
a
h) Determine the generating function of the numeric function r where (i)
ar =3?+4??,r20 (ii) a, =5,r20

SECTION ? C
Attempt any two parts of the following questions: 2 x 15 = 30
(i) Show that A U (E (W C ) = (A U 15??) (N (A U C ) Using Vein Diagram.
(ii) Show that whether the relation (x, y) e R, if x 2 y defined on the set of positive integer is
partial order relation.
(i) Consider an algebraic system (G,*) where G is the set of all all non-zero real numbers and *
is a binary operation defined by a *b = ?7? show that (G,*) is and abelian group.
(ii) Prove that if H1 and H 2 are two subgroups of G , then H1 0 H 2 is also a subgroup.
(i) State and prove Hand Shaking LemmSa.
? 1
(ii) Show that maximum number of edges in a simple graph with n vertices is M