END TERM EXAMINATION

Paper Code: BCA-101

Subject: Discrete Mathematics

Time: 3 Hours

Maximum Marks: 75

Note: Attempt five questions in all including Q.no.1 which is compulsory.

Q1. Attempt any five of the following: (5x5=25)
(a) Let R be the relation in the natural number N defined by the open sentence "x - y is divisible by 5", prove that R is an equivalence relation.
(b) Write the truth table for the formula (p ∧ q) → (p ∨ r).
(c) Consider (A, ≤) where A = {1, 2, 3, 4, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}}. Draw the Hasse diagram of A.
(d) Draw the complete bipartite graph of K2,4 and K3,3.
(e) Define tautology and contradiction.
(f) In a survey of 200 musicians, it was found that 40 wore gloves on the left hand and 39 wore gloves on the right hand. If 160 wore no gloves at all, how many wore a glove on (i) only the right hand? (ii) Only the right hand? (iii) On both hands

Q2. (a) Prove that (A-B) U (B-A) = (A U B) - (A ∩ B) (6.5)
(b) Let U = {a, b, c, d, e}, A = {a, b, d} and B = {b, d, e}. Find (1) A U B (2) B ∩ A (3) B - A (4) A ∩ B (5) B' (6) A' ∪ B' (6)

Q3. (a) Write the contrapositive, converse, and inverse of the conditional statement "The Indian Cricket wins when Sachin Tendulkar Scores 100". (6.5)
(b) Obtain PCNF of (p ∧ r) ∨ (q ∨ p) and hence obtain its PDNF. (6)

Q4. (a) Prove that every chain is a distributive lattice. (6)
(b) Draw a Hasse diagram of (X, ≤) where X = {1, 2, 3, 4, 6, 8, 12, 24} and R be a division relation. Find the Hasse diagram of the poset. (6.5)

Q5. (a) Let D30 = {1, 2, 3, 5, 6, 10, 15, 30} and Let the relation R be divisor on D30. (6)
1. Find all lower bounds of 10 and 15.
2. GLB of 10 and 15.
3. All upper bounds of 10 and 15.
4. LUB of 10 and 15.
5. Draw the Hasse Diagram.
(b) Draw the Hasse diagram representing the partial ordering {(A, B)|A ⊆ B} on the power set P(S) where S = {a, b, c}. Find the maximal, minimal, greatest and least elements of this partially ordered set. Is it complemented Lattice? Justify your answer. (6.5)

Q6. (a) Find the number of integers between 1 and 250 that are divisible by any of the integers 2, 3, 5, and 7. (6)
(b) There are six men and five women in a room. Find the number of ways four persons can be drawn from the room if (1) they can be male or female, (2) two must be men and two females (3) they must all be of the same sex. (6.5)

Q7. (a) Solve recurrence relation S(n) - 3S(n-1) = 5(3^n) with S(0) = 2. (6)
(b) There are three files of identical red, blue and green balls, where each file contains at least 10 balls. In how many ways can 10 balls be selected? (1) If there is no restriction. (2) If at least 1 red ball must be selected. (3) If at least 1 red, at least 2 blue, and at least 3 green balls must be selected (4) If at most 1 red ball is selected. (6.5)

Q8. (a) Draw the complete graph K5 with vertices A, B, C, D, E. Draw all complete subgraphs of K5 with 4 vertices. (6)
(b) Prove that a connected graph G is Euler graph if and only if every vertex of G is of even degree. (6.5)

Q9. (a) If G is a connected simple graph with n vertices with n≥3 such that the degree of every vertex in G is at least n/2, then prove that G is a Hamilton cycle. (6)
(b) Let δ(G) & Δ(G) denotes minimum and maximum degrees of all the vertices of G respectively. Then show that for a non-directed graph G, δ(G) ≤ 2|E|/|V| ≤ Δ(G). (6.5)