[0:00]Code No. 184U Jawahar Lal Nehru Technological University, B.Tech II Year II Semester Examinations, July/August 2023. Discrete Mathematics (Common to CSE, IT, CSIT, CE(SE), CSE(CS) CSE(DS), CSD) Time: 3 Hours Max. Marks: 60. Note: This question paper contains two parts A and B. Part A for 10 marks, Part B for 50 marks. Part A is a compulsory question which consists of 10 sub questions, each carrying equal marks. Part B consists of 10 questions numbered from 2 to 11, carrying 10 marks each. From each unit there are two questions and the student should answer one of them. Hence the student should answer five questions from Part B. Part A 10 marks. 1a) Find the truth table for not P. 1b) The converse of a statement is given below. Write the inverse and contra positive statements. "If he is considerate of others, then a man is a gentleman." 1c) If A = {a,b,c,d}, B = {c,d,e} and C = {e,f,g,h}. Find B ∩ (A ∪ C). 1d) Let A = {1,2,3} and R = {(x,y) | x < y}, find MR. 1e) Define totally ordered set. 1f) What are the idempotent laws of Boolean algebra? 1g) How many outcomes are possible by costing a 6-faced die 10 times? 1h) State multinomial theorem. 1i) What is binary tree? Give an example. 1j) What is the maximum number of edges in a simple graph on n vertices? Part B 50 marks. 2a) Obtain the principal conjunctive normal form of the formula S given by not P implies R and Q if and only if P. 2b) Show that not P and not Q and R or Q and R or P and R is equivalent to R. Or 3a) Obtain principal disjunctive normal form of P or not P implies Q or not R. 3b) Show that not P if and only if Q is equivalent to not P if and only if not Q and P if and only if Q. 4a) Out of 30 students in a dormitory, 15 taken an art course, 8 taken a biology course and 6 taken a chemistry course. It is known that 3 students take all the three courses. Show that 7 or more students take none of the courses. 4b) Let A, B, C be subset of U. Prove or disprove (A union B) intersection (B union C) is a subset of (A union B).
[0:14]Or 5a) 35 children of a class draw a map. 26 children use red colour and some children use yellow colour. If 19 use both the colours, find the number of children who used the yellow colour. 5b) For the sets S, T and U, prove that (S intersection T) cross U = (S cross U) intersection (T cross U). 6a) Show that for a bounded distributive lattice, complement of an element is unique. 6b) For any a,b belongs to B, then prove that (i) a + ab = a (ii) a.(a+b) = a (B is a Boolean Algebra). Or 7a) In Boolean algebra B, for each a belongs to B, there exists a unique complement. 7b) Minimize the expression AB bar + A bar + AB bar. 8a) Show that C(n,0) + C(n,1) + C(n,2) + ... + C(n,n) = 2 to the power n. 8b) Enumerate the number of non-negative integral solutions to the equality x1 + x2 + x3 + x4 + x5 = 19. Or 9a) Prove that C(n,1)/C(n,0) + 2C(n,2)/C(n,1) + 3C(n,3)/C(n,2) + ... + nC(n,n)/C(n,n-1) = n(n+1)/2. 9b) Find the coefficients of x^5 y^10 z^5 w^5 in the expression of (x + 7y + 3z + w)^25. 10a) Determine whether the graphs shown below are isomorphic or not. Justify your answer. 10b) i) Give an example of a graph which is Hamiltonian but not Eulerian. ii) Give an example of a graph which is Eulerian but not Hamiltonian. Or 11a) Using Prim's algorithm, find a minimal spanning tree for the following weighted graph. 11b) For each of the following graphs, what does Brooks' Theorem tell you about the chromatic number of the graph? Find the chromatic number of each graph. i) The complete graph K20, ii) The bipartite graph K10,20, and iii) A cycle with 29 edges. ooOoo--
