Discrete Mathematics — Winter 2020

Find the power sets of (i)  a  , (ii)  a,b,c  .

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

(i) Let Nbe the set of natural numbers. Let Rbe a relation in Ndefined by xRy if and only if x3y 12. Examine the relation for (i) reflexive (ii) symmetric (iii) transitive. (ii) Draw the Hasse diagram representing the partial ordering {(a,b)/ a divides b} on {1,2,3,4,6,8,12}.

Let Rbe a relation defined in A={1,2,3,5,7,9} as R={(1,1), (1,3), (1,5), (1,7), (2,2), (3,1), (3,3), (3,5), (3,7), (5,1), (5,3), (5,5), (5,7), (7,1), (7,3), (7,5), (7,7), (9,9)}. Find the partitions of Abased on the equivalence relation R.

In a box there are 5 black pens, 3 white pens and 4 red pens. In how many ways can 2 black pens, 2 white pens and 2 red pens can be chosen?

Solve the recurrence relation a 4a 4a n3n using n n1 n2 undetermined coefficient method.

Define self-loop, adjacent vertices and a pendant vertax.

Define tree. Prove that if a graph Ghas one and only one path between every pair of vertices then Gis a tree.

(i) Find the number of edges in Gif it has 5 vertices each of degree 2. (ii) Define complement of a subgraph by drawing the graphs.

Show that the algebraic structure (G,*) is a group, where G {(a,b)/a,bR,a  0}and * is a binary operation defined by (a,b)*(c,d) (ac,bcd) for all (a,b),(c,d)G.

Define path and circuit of a graph by drawing the graphs.

(i) Show that the operation * defined by x*y  xy on the set Nof natural numbers is neither commutative nor associative. (ii) Define ring. Show that the algebraic system (Z , , ), where999 Z {0,1,2,3,...,8}under the operations of addition and multiplication9 of congruence modulo 9, form a ring.1

Define subgraph. Let Hbe a subgroup of (Z,+), where His the set of even integers and Zis the set of all integers and + is the operation of addition. Find all right cosets of Hin Z.

Define adjacency matrix and find the same for

(i) Draw the composite table for the operation * defined by x*y=x, x,yS {a,b,c,d}. (ii) Show that an algebraic structure (G,)is an abelian group, where 1 0 1 0 1 0  G={A,B,C,D},A ,B  ,C  ,       0 1  0 1 0 1 1 0  D and  is the binary operation of matrix multiplication.    0 1

Define indegree and outdegree of a graph with example.

Prove that the inverse of an element is unique in a group (G,*).

(i) Does a 3-regular graph with 5 vertices exist? (ii) Define centre of a graph and radius of a tree.

Check the properties of commutative and associative for the operation * defined by x*y=x+y-2 on the set Zof integers.

Define group permutation. Find the inverse of the permutation 1 2 3 4  .   3 1 4 2

(i) Show that  pq    pq  is a tautology. (ii) Obtain the d.n.f. of the form (p q)(pq).

03 Find the domain of the function f(x)  16 x2 .

Define lattice. Determine whether POSET  1,2,3,4,5  ;|  is a lattice.

Show that the propositions (pq) and pq are logically equivalent.