Download AKTU B-Tech 8th Sem 2016-17 NOE048 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 NOE048 Discrete Mathematics Question Paper

Printed Pages 1 2 R011 WitisaszLmonLJ?l?Mfirsmankm?s
Time : 3 Hours
B. TECH.
THEORY EXAMINATION (SEM?VIII) 2016-17
DISCRETE MATHEMATICS
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?
b) 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 ?ve 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 +1 lan_2 ? 6an_3 with condition
610 =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 ?gure does not contain Hamiltonian Circuit.
0
b \ C
g) Let G be a group; for fixed element G , let Gx = {a e G : ax = xa} show that GX is a
subgroup of G for all x e G.
h) Determine the generating function of the numeric function ar Where (i)
nr=V+4r+1 r>0 (m a, =5 r>0
www.FirstRanker.com

www.FirstRanker.com www.FirstRanker.com
SECTION ? C
Attempt any two parts of the following questions: 2 x 15 = 30
(i) Show that A U (E m C ) = (A U E) (W (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 = ajb 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
www.FirstRanker.com