Ma2265 - Discrete Mathematics 5l2811

MA2265 - Discrete Mathematics UNIT I 1. Check the validity of the following argument. “If the band could not play rock music or the refreshments were not delivered on time, then the New year’s party would have been cancelled and Alice would have been angry. If the party were cancelled, then refunds would have to be made. No refunds were made”. (ii) Show that R  S follows logically from the premises C  D,(C  D)  H, H  (A  B) and (A  B)   R  S  . 2. Translate the following predicate calculus formula into English sentence  x[C  x    y  C(y   F  x, y ]. Here C(x) : x has a computer, F(x ,y) : x and y are friends. The universe for both x and y is the set of all students of your college. 3. Prove that  p  q    p  r    q  r   r is a tautology. 4. Find the PDNF and PCNF of  p q  (p  r)   q r  . 5. Check whether the hypothesis “ It is not sunny this afternoon and it is colder than yesterday”, “ we will go swimming only if it is sunny” , “If we do not go swimming then we will take a canoe trip” and “ If we take a canoe trip, then we will be home by sunset” lead to the conclusion “we will be home by sunset”. UNIT II

n(n  1)(n  2)(n  3) , n 1. 4 Using generating function method to solve the Fibonacci series Solve s(k) – 10 s(k-1) + 9 s(k-2) = 0 with s(0) = 3 , s(1) = 11. Using mathematical induction show that 2n 2  32n1 is divisible by 7, n  0 . Prove the principle of inclusion-exclusion using mathematical induction Find the number of positive integers not exceeding 100 that are divisible by 5 or 7.

1. Show that 1.2.3  2.3.4  3.4.5  . . .  n(n  1)(n  2)  2. 3. 4. 5. 6.

UNIT III 1. Define Eulerian graph and Hamiltonian graph. Give an example of (I) a graph which is Hamiltonian but not Eulerian. (II) a graph which is Eulerian but not Hamiltonian. (III) a graph which is both Eulerian and Hamiltonian. (IV) a graph which is non Eulerian and non Hamiltonian

2. Check the given graph is strongly connected, weakly connected and unilaterally connected or not. If G is a simple graph with n- vertices and k- components then the no.of (n  k ) (n  k  1) edges is atmost 2 3. A connected graph G is Eulerian if and only if every vertex of G is of even degree. Find the Hamiltonian path and Hamiltonian cycle, if it exist. Also identify the Euler circuit

4. Check the given two graphs G and G’ are Isomorphic or not.

5. Let G be a (p, q) graph. Let M be the maximum degree of the vertices of G and let m be the 2q minimum degree of the vertices of G. Show that m  M. p UNIT IV 1. State and prove Fundamental theorem on homomorphism of groups Let ( G , * ) be a finite cyclic group generated by an element a  G. If G is of order n,prove that an = e and G = { a , a2 , …, an = e} where n is the least positive integer for which an = e. 2. Prove that every finite group of order n is isomorphic to a permutation group of degree n.

3. Let (G ,H , * ) be a group and a  G,. Let f : G  G be given by f(x) = a*x*a-1 for every x G prove that f is an isomorphism of G onto G. 4. State and prove Lagranges Theorem 5. The intersection of any two normal subgroup of a group is a normal subgroup. 6. A subgroup H of G is normal iff each left coset of H in G is equal to the right coset of H in G. UNIT V In a Lattice show that a  b and c  d implies a *c  b * d. Let ( L,  ) be a lattice. For any a, b  L, a  b  a  b = a  a  b = b. In a distributive lattice prove that a *b = a * c and a  b = a  c implies that b = c Show that every distributive lattice is modular. Whether the converse is true? Justify Your claim 5. Establish De.Morgan’s laws in a Boolean Algebra. 6. State and prove distributive inequalities of a Lattice 7. Show that in a complemented and distributed lattice a  b  a * b '  0  a ' b  1  b '  a ' 1. 2. 3. 4.