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.

--- Content provided by‍ FirstRanker.com ---

SECTION – A

10 x 2 = 20

1. Attempt all parts of the following question:
   1. What is the difference in relation and function?
   2. Define equivalence relation.
   3. Transform following statement into symbolic form: Jack and Jill went up the hill.
   4. Define negation.

   --- Content provided by FirstRanker.com ---

   5. Find the permutations of the set A = {1,2,3,4} taking two at a time.
   6. There are 10 different people at a party. How many ways are there to pair them up into a collection of 5 parings ?
   7. Show that (I,+) is an abelian group.
   8. Define cyclic group.
   9. Define Hamiltonian Path.

   --- Content provided by FirstRanker.com ---

   10. Define Chromatic number.

SECTION – B

5 x 10 = 50

2. Attempt any five parts of the following questions:
   1. Let R be the relation on the set A of integers, defined by xRy if x - y is divisible by 4. Show that R is an equivalence relation, and describe the equivalence classes.
   2. Show the implication
      1. (P?¬P)?Q?(Pv¬P)?R

      --- Content provided by⁠ FirstRanker.com ---

      2. (P?Q)?Q?PvQ
   4. Show that (F, + , .) is a field where F is a set of all rational numbers and + and . are ordinary addition and multiplication operators.
   5. Show that number of odd degree vertices is always even.
   6. Show that the graph shown in figure does not contain Hamiltonian Circuit.

   --- Content provided by‍ FirstRanker.com ---

   7. Let G be a group; for fixed element G, let G1 = {a?G:ax = xa} show that G1 is a subgroup of G for all x ?G.
   8. Determine the generating function of the numeric function a_r where
      1. a_r = 3^r +4^r+1, r > 0
      2. a_r = 5, r>0

--- Content provided by​ FirstRanker.com ---

SECTION - C

2 x 15 = 30

3. Attempt any two parts of the following questions:
   1. Show that AU(BnC)=(A?B)n(A?C) Using Vein Diagram.
   2. Show that whether the relation (x, y) ? R, if x= y defined on the set of positive integer is partial order relation.
4. 1. Consider an algebraic system (G,*) where G is the set of all non-zero real numbers and * is a binary operation defined by a*b= ab/4. Show that (G,*) is an abelian group.

   --- Content provided by‍ FirstRanker.com ---

   2. Prove that if H1 and H2 are two subgroups of G, then H1nH2 is also a subgroup.
5. 1. State and prove Hand Shaking Lemma.
   2. Show that maximum number of edges in a simple graph with n vertices is n(n-1)/2
   3. Find the solution of recurrence relation a_n =6a_n-1+11a_n-2-6a_n-3 with condition a0 = 2, a1 = 5 and a2 = 15

   --- Content provided by​ FirstRanker.com ---

For more papers visit: FirstRanker.com