a (vesesen SNI 095) U.G. DEGREE EXAMINATION, NOVEMBER 2023. B.Sc. — Computer Science — First Semester DISCRETE MATHEMATICS ‘Time : Three hours F Maximum : 75 marks PART A — (10 x 1= 10 marks) Answer the following objective questions by choosing the correction option. 1, A— is an ordered collection of objects. (a) Relation (b) Function () Set (d) Proposition 2. The set O of odd positive integers less than 10 can ~ be expressed by —————— (a) {1, 2, 3} (b) {1, 3, 5,7, 9} m G25 () (1,5, 7,9, 1B 3. pv qis logically equivalent to (8) “a9. —> zP (b) @>P () -=po7q (d) poaov ird {IN ax ni in a _{p oq) is logically equivalent to fa) GeoP (b) pend © pea @ -qe-P ‘A non empty set A is termed as an algebraic structure (@) with respect to binary operation * (b) “with respect to ternary operation ? (©) with respect to binary operation * (@ with respect to unary operation ~ An algebraic structure is called a semigroup. fa) @,*) &) @+%) © @+ @ &*) Let A= |ka, |, B= lash.» be an n x n matrices and k be a scalar then det (4) is equal to (a) Kdet (b+) Kedet (c) K%det(b) (d) All of the above 2 SNI 095 10. ll. a Let A be a nilpotent matrix of order n then (a) A*=0 (b) nA=O () A=nl, Tis Identity matrix (@)_Allof the above order defined by S<= R ifa divides & edges in the Hasse diagram of is ——____ fa) 6 ) 5 @ 9 @ 4 Suppose X = {a, b, c, d} and s, is the partition X, m =a, b,c}, d). The number of ordered pars of the equivalence relations induced by (a) 15 ) 10 @ 34 @ 5 PART B — (6 x 4= 20 marks) Answer ALL the questions in not more thes 200 words each. (a) Explain about set theory. Give few exameiss Or (b) Give examples of finite sets. 312, (a) (b) 13. (a) @) 14. (a) ) (ay a Explain in details about conditional and Bi-conditional operation. Or Write the truth table for the following given statement (Pv Q) A(~P>Q). Write down important notes on Lagrange theorem. Or If Gis a finite group then let P be a subgroup of G, Suppose that the order n of P is relatively prime to the index |G:S|=m. Using the Lagrange theorem prove that N= {aeG|an =e}. Explain in details about matrix inverse. Or 12 3 Find the inverse of a matrix/4 5 6|. 729 ee 15. 16. 17. —_— oJ ’ (a) Let A={I, 2, 3, 6) where a is related to be by divisibility, meaning “a divides 6”. Let's prove that the relation is a partial order, construct a Hasse diagram, and determine its maximal and minimal elements. Or (b) Suppose we are given the following partial ordering, indicated in the Hasse diagram below, and subset $= {10, 15}. Then the least upper bound of 10 and 15 is 30, which is the least common multiple, and the place where 10 “joins” 13. And the greatest lower bound of 10 and 15 is 5, which is the greatest common divisor and the place where 10 “meets” 15. PART C — (8 x 15 = 45 marks) Answer any THREE questions in not more than 1500 words each. Let us assume that Fis a relation on the set R real numbers defined by xFy if and only if x-y is an integer. Prove that F is an equivalence relation on R. Prove that {K3(¥ + Z)eXs2GYvZe(KaY)o>Z. SNI 095 518. 19. - 20. e Let G a finite group and let J and K be two distinct Sylow p-group, where p is a prime number and divides the order |G]. of G. Using Lagrange theorem prove that the product JK will never be a subgroup of G. Find the rank of matrix A by using the row echelon form. 1 2\3 A=|2 114 3 O)5 Consider the set A = (4, 5, 6, 7).. Let R be the relation S on A. Draw the directed graph and the Hasse diagram of R. 6 SNI 095U21CSA11 S 0202 | U.G. DEGREE EXAMINATION, NOVEMBER 2022. Cc ———_ ‘ & : ie 3 ; 1. u g 2, Time : Three hours B.Sc. Computer Science — First Semester DISCRETE MATHEMATICS Maximum : 75 marks PART A — (10 x 1= 10 marks) Answer ALL the following objective questions by choosing the correct options. A function f: A — Bsaid to be —————— if for every y¢B there exists atleast one element of xé€A such that f(x) =y. (a) surjective (b) _ bijective (c) injective (ad) automorphism The set {ce R:a) Infimum (©) Bounded (@_ Unbounded - Let (L, a, V) be an algebraic lattice and xe then RAK= a @) x o 2 © 3 $0202(a) ) 12. (@) ) 13. (@) (b) PART B— (5 x 4 = 20 marks) 14. Answer ALL questions. Show that /:R>(0,1) defined by fF) = + al is a bijection. 4 Or a 9 If 2 is reflexive and transitive relation on a set A show that ROR™ is an equivalence relation on A. Verify the truth table for the following: 1. @ ~@>Q=pa~q G) ~peg=epedg Or State and prove Demorgan’s Law. Prove that every group of prime order is © cyclic. Or State and prove Fermat's theorem. 4 S 0202 @ ) @) (b) Show that the following system of equations. 2x+6y=-11 6x +20y-62=-3 6y-18z=-11 is inconsistent. Or Verify Cayley Hamilton theorem for the 12 0 matrix A=/2 -1 0 |. 0 0 -1 Express the ~—-Boolean_ function F=(xay)v(x'a2z) in a product of max term form. Or If (Z,v, 4) be a complemented distributive lattice, then prove that for any a,be L. vb b 1 aa 2 @ @) an 0 a) < o 5 S 0202Ill. 16. Lie 18, 19. 20, PART C — (8 x 15 = 45 marks) Answer any THREE questions. (a) Show that the function f:R-> R defined by f(x) =8x-1, xe R is a bijective. (b) Let f:A+B and g:B>C be bijective then (gof)* = (fog). Construct a truth table for the following: @ [praaql>q ) (pe 9 or © pe der) @) (pa~p)>q State and prove Lagrange’s theorem. Find the characteristic roots and characteristic 21 -1 vectors of the matrix|0 3 -2), 24 8 Verify that F(x, Xp, ay) =%3 Ax) v (%, NXg) V (xg AX) — S 0202