Download PTU B-Tech CSE-IT 2020 Dec 4th Sem 77626 Discrete Mathematics Question Paper

FirstRanker.com

Total No. of Pages : 03
Total No. of Questions : 18

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

B.Tech. (CSE/IT) (2018 Batch) (Sem.-4)
DISCRETE MATHEMATICS
Subject Code : BTCS-401-18
M.Code : 77626
Time : 3 Hrs. Max. Marks : 60

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

INSTRUCTIONS TO CANDIDATES :

1. SECTION-A is COMPULSORY consisting of TEN questions carrying TWO marks each.
2. SECTION-B contains FIVE questions carrying FIVE marks each and students have to attempt any FOUR questions.
3. SECTION-C contains THREE questions carrying TEN marks each and students have to attempt any TWO questions.

SECTION-A

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

Answer briefly :

1. Find the Cartesian product A x A if A = {0, 1, 3}.
2. Construct the truth table of the compound proposition (p v ¬q) ≡ (p ∧ q).
3. Define contrapositive of a conditional statement and find the same for of the following statement: “If you do your homework, you will not be punished”
4. What is the power set of the ‘empty set? What is the power set of the set {∅}? Here ∅ is an empty set.

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

5. State pigeonhole principle.
6. Find the greatest common divisor of 414 and 662 using the Euclidean algorithm.
7. Draw a Complete graph with 5 vertices.
8. Does there exits a simple graph with six vertices of degrees 1,1,3, 4,6,7? Justify.
9. Define a permutation group.

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

10. For any a,b in a Boolean algebra prove that (a+b)'=a'+b'.

SECTION-B

1. Show that ¬( p∨(¬p∧q))and ¬p∧¬q are logically equivalent by developing a series of logical equivalences.
2. In a survey it was found that 21 people liked product A, 26 liked product B and 29 liked product C. If 14 people liked products A and B, 12 liked products C and A, 14 people liked products B and C and 8 liked all the three products. Find how many liked product C only?
3. Let A be the set of integers and R be the relation defined on AxA by (a,b)R (c,d) if ad=bc. Prove that R is an equivalence relation.

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

4. Explain the following with suitable examples :
   1. Connected graph
   2. Planar graph
   3. Vertex colouring of a Graph
   4. Rooted tree

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

5. Show that the set G={1,2,3,4,5,6} is a finite abelian group of order 6 w.r.t. multiplication modulo 7.

SECTION-C

1. 1. Prove that √2 is irrational by giving a proof by contradiction.
   2. Find the number of arrangements of the letters of the word INDEPENDENCE. In how many of these arrangements
      1. All the vowels always occur together.
      2. Vowels never occur together.

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

2. 1. Prove that a finite integral domain is a field.
   2. Using Boolean algebra, show that : abc+ab'c+abc'+a’bc=ab+bc+ca

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

3. 1. Determine whether the following graph is :
      1. Hamiltonian, if yes, find the Hamiltonian cycle.
      2. Eulerian, if yes, find the Euler cycle.
   2. Use the well-ordering property to prove the division algorithm which states that if a is an integer and d is a positive integer, then there are unique integers q and r with 0 ≤ r < d and a=dq+r.

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

NOTE : Disclosure of Identity by writing Mobile No. or Making of passing request on any page of Answer Sheet will lead to UMC against the Student.