# Discrete Mathematical Structures July 2011

1.(a) Show that

p->q = (~p)vq

(b) Show that (pAq)—>(pvq) is a tautalogy.

(c) Show that (p^q)-(pvq) is a contradiction.

OR

(a) Define the following

(i)  Tautalogy

(iii) Contingency.

(b) Check til® validity of following argument

2 (a) Give an indirect proof of the theorem “If 3n+2 is odd, then is odd”.

(b) Show that ^ is irrational

OR

(a) Show that if n is an integer greater than 1, then n is either a prime or a product of primes.

(b) Sort the list x = [64, 25, 12, 11] using selection sort algorithm.

3 (a) Show the sum of the degrees of all the vertices in a graph is equal to twice the number of edges in the graph.

(b) Prove that a simple with n vertices and k components can have at most (n-k) (n-k+l)/2 edges.

OR

(a) Prove that the chromatic number of a graph will not exceed by more than one, the maximum degree of the vertices in a graph.

(b) Prove that a graph is a tree if and only if it is minimally connected.

(c) Find the complexity of a complete graph K3.

4.  (a) Let 100 of the 120 students of mathematics at a college take at least one of the languages Hindi, English and German. Also, let 65 study Hindi, 45 study English and 45 German. If 20 study Hindi and English, 25 study English and German and 15 study Hindi and German. Find the number of students who study all the three languages.

(b)Let A = {a,b,c,d,e} and B = {c,e,f,h,k.m} then prove if A and B are finite sets then \AkjB\=\A\ + \B\ — \Ac\B\.

(c) Show that the set of even positive integers is a countable set.

OR

(a) Determine whether each of the following functions is a bijection from R

(i) f(x) “ —3.x + 4

(ii) f(x) = —3x2 +7

(b) If (n+1) integers are selected from the set {1,2,…., 2n} then show that one of them divides another integer that has been selected.

(a)Define the following with example

(i)Reflexive relation

(ii)Symmetric relation

(iii)Transitive relation

(iv) Antisymmetric relation

(b) Show that (Z+ , divisibility) is a poset

5. (a) Show that in the set of integers I – {…., -2, -1, 0, 1, 2,….}, the relation aRb=>a = b (modn), ngN. is an equivalence relation.

(b) Show that an equivalence relation defined in a set A decomposes the set into disjoint classes.