Discrete Mathematics — Summer 2020

If A = {a, b} and B = {c, d} and C = {e, f} then find (i) (AB)U(BC) (ii)A(BUC).

Define even and odd functions. Determine whether the function f :I R defined by f(x0  2x7 is one-to-one or bijective.

(i) Show that the relation x  y(modm)defined on the set of integers Iis an equivalence relation. (ii) Draw the Hasse diagram for the partial ordering {(A,B)/ A B} on the power set P(S), where S {a,b,c}.

Define equivalence class. Let Rbe the relation on the set of integers I defined by ( x – y ) is an even integer, find the disjoint equivalence classes

Acommittee of 5 persons is to be formed from 6 men and 4 women. In how many ways can this be done when (i) at least 2 women are included (ii) at most 2 women are included ?

Solve the recurrence relation a 5a 6a 3n2using the method n n1 n2 of undetermined coefficients.

Solve the recurrence relation using the method of generating function a 5a 6a 3n,n2;a 0,a 2. n n1 n2 0 1

Define simple graph, degree of a vertex and complete graph.

Define tree. Prove that there is one and only one path between every pair of vertices in a tree T.

(i) Agraph Ghas 15 edges, 3 vertices of degree 4 and other vertices of degree 3. Find the number of vertices in G. (ii) Define vertex disjoint and edge disjoint subgraphs by drawing the relevant graphs.

Show that (G, ) is a cyclic group, where G={ 0, 1, 2, 3, 4 }.

Define the following by drawing graphs (i) weak component (ii) unilateral component (iii) strong component.

(i) Construct the composite tables for (i) addition modulo 4 and (ii) multiplication modulo 4 for Z {0,1,2,3}. Check whether they have4 identity and inverse element. a 0  (ii) Define ring. Show that the set M    /a,bRis not a ring b 0  under the operations of matrix addition and multiplication.1

Define algebraic structure, semi group and monoid. Also give related examples.

Use Warshall’s algorithm to obtain path matrix from the adjacency matrix of v v14 v5 v v23

(i) Is the algebraic system ( Q, * ) a group? Where Qis the set of rational numbers and * is a binary operation defined by a*babab, a,bQ. (ii) Let ( Z, + ) be a group, where Zis the set of integers and + is an operation of addition. Let Hbe a subgroup of Zconsisting of elements multiple of 5. Find the left cosets of Hin Z.

Prove that there are always an even number of vertices of odd degree in a graph.

Prove that every subgroup Hof an abelian group is normal.

(i) Find the number of edges in a r – regular graph with n – vertices. (ii) Atree Thas 4 vertices of degree 2, 4 vertices of degree 3, 2 vertices of degree 4. Find the number of pendant vertices in T.

Show that the operation * defined by x*y  xy on the set Nof natural numbers is neither commutative nor associative.

Prove that an algebraic structure ( G, * ) is an abelian group, where Gis the set of non-zero real numbers and * is a binary operation defined by ab a*b  .2

(i) Find out using truth table, whether (pr) p is a tautology. (ii) Obtain the dnf of the form (p (qr)).

If f :x  2x, g:xx2 and h:x (x1),then show that (fog)oh  fo(goh).

Define lattice. Determine whether the POSET ({1,2,3,4,5};1)is lattice.

(i) If p: product is good, q: service is good, r: company is public limited, write the following in symbolic notations (i) either product is good or the service is good or both, (ii) either the product is good or service is good but not both, (iii) it is not the case that both product is good and company is public limited. (ii) For the universe of integers, let p(x), q(x), r(x), s(x) and t(x) be the following open statements: p(x): x > 0; q(x): x is even; r(x): x is a perfect square; s(x): x is divisible by 4; t(x): x is divisible by 5. Write the following statements in symbolic form: (i) At least one integer is even, (ii) There exists a positive integer that is even, (iii) If x is even then x is not divisible by 5, (iv) No even integer is divisible by 5, (v) There exists an even integer divisible by 5.2