Discrete Mathematics — Winter 2022

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

If1 A   4 , 5 , 7 , 8 , 1 0  , B   4 , 5 , 9  and C 1,4,6,9, then verify that A   B  C    A  B    A  C 04 .

Define Functionally complete set of connectives, Principal Disjunctive Normal Form (PDNF). Obtain PDNF for the expression    p  q     p  q    q  r  07

Define Partial Order Relation. Illustrate with an example.

Define one – one function. Show that the function f : R  R , f  x   3 x  704 is one – one and onto both. Also find its inverse.

Solve the recurrence relation a n   5 a n  1  6 a n  2 with initial condition a0  1 and a1   107 using method of undetermined coefficients.

Use generating function to solve a recurrence relation a 3a 2 with n n1 a 1.0

Define Partition of a Set. Let A1,2,3,4,5 and R    1 , 2  ,  1 , 1  ,  2 , 1  ,  2 , 2  ,  3 , 3  ,  4 , 4  ,  5 , 5   be an equivalence relation on A. Determine the partition for R  103 , if it an equivalence relation.

Draw Hasse Diagram for the lattice S ,D where Sis the set of3030 divisors of 30 and Dis the relation divides.

Show that the set Sof all matrices of the form   a b b a  where a , b  R07 is a field with respect to matrix addition and matrix multiplication.

Define Semi Group, Monoid. Give an example of an algebraic structure which is semi group but not monoid.

Consider the a relation2 Rdefined on A   1 , 2 , 3  whose matrix representation is given below. Determine its inverse R1and complement R '04 . 1 0 0   M  1 1 1 R   0 0 1  

Define free variable and bound variable. Rewrite the following argument using quantifiers, variables and predicate symbols. Prove the validity of the argument. “All healthy people eat an apple a day. Ram does not eat apple a day. Ram is not a healthy person.”

Define Abelian group and prove that the set  0 , 1 , 2 , 3 , 4  is a finite abelian group under addition modulo 5 as binary operation.

Define even permutation. Show that the permutation   is odd and  16 04 is even.

Define Principal Ideal. Find all the principal Ideal of the ring   0 , 1 , 2 , 3 , 4 , 5  , 6 , 6 07 .

Define cut vertex. List out all the cut vertices of the graph given in Figure 1.

Define adjacency matrix and path matrix of a graph. Find out adjacency matrix for the graph given in Figure 1.

Define the terms: Simple Graph, Multi – Graph, Weighted Graph, Degree of a vertex, in degree and out degree of a vertex. Illustrate each with an example.

State Lagrange’s theorem and find out all possible subgroups of group   1 ,  1 , i ,  i  ,  03 .

Define Eulerian graph, Planar Graph. Justify whether the graph given in Figure 1 is Planer or not using Euler’s formula.

Define Binary tree, Spanning tree, Minimal Spanning tree, Find the minimal spanning tree for the weighted graph given in Figure 2.

Define Cyclic group, Normal subgroup. Illustrate with an example.

Form a binary search tree for the data 16,24,7,5,8,20,40,3.

Explain Post order traversal. Given the postorder and inorder traversal of a binary tree, draw the unique binary tree. Postorder: d e c f b h i g a Inorder: d c e b f a h g i. Figure 1 Figure