Download AKTU B-Tech 3rd Sem 2015-2016 NCS 302 Discrete Structures And Graph Theory Question Paper

Download AKTU (Dr. A.P.J. Abdul Kalam Technical University (AKTU), formerly Uttar Pradesh Technical University (UPTU) B-Tech 3rd Semester (Third Semester) 2015-2016 NCS 302 Discrete Structures And Graph Theory Question Paper

Printed Pages : 5 447 NCS-302
(Following Paper ID and Roll No. to be ?lled in your
Answer Book)
Roll No.
B.Tech.
(SEM. III) THEORY EXAMINATION. 2015?16
DISCRETE STRUCTURES AND GRAPH THEORY
[Time : 3 hours] [Total Marks : 100]
Section-A
1. Attempt all parts. All parts carry equal marks. Write
answers of each section in short. (10x2=20)
(a) De?ne multiset and power set. Determine the
power setA= {1, 2}.
(b) Show that [((pq) =>r) (~p))] =>(q=r) is tautology
or contradication.
(c) State and prove pigeon hole principle.
((1) Show that if setAhas 3 elements, then we can have
26 symmetric relation on A.
(e) Prove that (P v Q) ?> (P A Q) is logicaHy
? equivalenttoP 11?) Q. '7 ?
17300 (1) P.T.O.

Attempt any ?ve questions.
(1) How many 4 digit numbers can be formed by using
the digits 2, 4, 6, 8 when repetition of digits is
allowed.
(g) The converse of a statements is: .lfa steel rod is
stretched, then it has been heated. Write the inverse
of the statement.
(h) He and b are any two elements of group G then
prove (ab) ?l=(b?la ?l).
(i) If f : A -+ B is one-one onto mapping, then prove
that f "c B ~-) A will be one-one onto mapping.
(j) Write the following in DNF (x+y)(x?+y?).
\
Section-B
(10X5=50)
2. If Dn de?ne the set of all positive odd integers, Le.
Dn={l,3, 5 ........... }, then prove with the help of
mathematical induction P (n) : l+3n is divisible by 4.
3. Solve the recurrence relation using generating function:
an?7an?l+10n?2=0with aO=3, al=3.
r7300 (2) NCS-302
Express the ?ollowiag statements using quanti?ers and
logical connectives.
(3) Mathematics book that is published in India has a
blue covert
(b) All animals are modal. All human being are animal.
Therefore, all human being are mortal.
(c) There exists a mathematics book with a cover that
is not blue.
(d) He eats cracke-zs only if he drinks milk.
(6) There are mathematics books that are published
outside India.
(f) Not all books have bibliographies.
Draw the Haase digram of[p (a, b, c), g ], (Note: ?3 ?
stands for subset). Find greatest element, least element,
minimal element and maximal element.
Simplify the following boolean expressions usingk map:
a) Y=((AB)?+A?+AB)?
b) A?B?C?D?+A?B?C?D+A?B?CD+A?B?B?CD?==A?B?
17300 . (3) P120

Attempt any two questions.
10.
~.17300
Let G be the set af all non-zero real number and let
a*b=ab/2. Show that (G,*) be an abelian group.
The following relation on A={ l , 2, 3, 4}. Dtermine
whether the following :
a) R: {(13), (3,1), (1,1), (1,2), (3,3), (4,4)},
b) R=AXA
If the permutation of the elements of {1,2,3,4,5} are
given by a=(l 2 3)(4 5) , b=(1)(2)(3)(4 5) , c=(1 5 2
4)(3). Find the value 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.
Section-C
(2X15=30)
Let L be a bounded distributed lattice, prove if a
complement exists, it is unique. Is D12 a complemented
lattice? Draw the Hasse diagram of [P (a,b,c), g ], (N ote:
?g? stands for subset). F ind greatest element, least
element, minimal element and maximal element.
(4) NCS-302
11. Determine whether each 0fthese functions is a bijection
from R to R.
(a) f(x) = x2 + 1
(b) f(x) = x3
(c) 1?(x) = (x2 + l)/(x2 + 2)
12. a) Prove that inverse of each element in a group is
unique.
b) Show that G=[(l, 2, 4, 5, 7, 8), X9] is cyclic. How
many generators are there? What are they?
__x_.
17300 . (5) NCS?302