Download GTU (Gujarat Technological University Ahmedabad) B.Tech/BE (Bachelor of Technology/ Bachelor of Engineering) 2020 Summer 4th Sem 3140708 Discrete Mathematics Previous Question Paper

Enrolment No.___________

**GUJARAT TECHNOLOGICAL UNIVERSITY**

**BE - SEMESTER? IV EXAMINATION ? SUMMER 2020**

**Subject Code: 3140708**

**Date:29/10/2020**

**Subject Name: Discrete Mathematics**

**Time: 10:30 AM TO 01:00 PM**

**Total Marks: 70**

**Instructions:**

**1. Attempt all questions.**

**2. Make suitable assumptions wherever necessary.**

**3. Figures to the right indicate full marks.**

**Marks**

**Q.1 (a)**If

*A*=

*{a, b}*and

*B*=

*{c, d}*and

*C*=

*{e, f}*then find

*(i)*(

*A*

*B*)

*U*(

*B*

*C*)

**03**

(

*ii*)

*A*(

*BUC*).

**(b)**Define even and odd functions. Determine whether the function

**04**

*f*:

*I*

*R*defined by

*f*(

*x*0 2

*x*7 is one-to-one or bijective.

**(c) (i)**Show that the relation

*x*

*y*(mod

*m*) defined on the set of integers

*I*is

**03**

an equivalence relation.

**(ii)**Draw the Hasse diagram for the partial ordering {( ,

*A B*) /

*A*}

*B*on

**04**

the power set

*P*(

*S*) , where

*S*{

*a*, ,

*b*}.

*c*

**Q.2 (a)**Define equivalence class. Let

*R*be the relation on the set of integers

*I*

**03**

defined by

*( x ? y )*is an even integer, find the disjoint equivalence classes

**(b)**A committee of

*5*persons is to be formed from

*6*men and

*4*women. In

**04**

how many ways can this be done when (i) at least

*2*women are included

(ii) at most

*2*women are included ?

**(c)**Solve the recurrence relation

2

*a*5

*a*

6

*a*

3

*n*using the method

**07**

*n*

*n*1

*n*2

of undetermined coefficients.

**OR**

**(c)**Solve the recurrence relation using the method of generating function

**07**

*a*5

*a*

6

*a*

3

*n*,

*n*;

2

*a*,

0

*a*.

2

*n*

*n*1

*n*2

0

1

**Q.3 (a)**Define simple graph, degree of a vertex and complete graph.

**03**

**(b)**Define tree. Prove that there is one and only one path between every pair

**04**

of vertices in a tree

*T.*

**(c) (i)**A graph

*G*has

*15*edges,

*3*vertices of degree

*4*and other vertices of

**03**

degree

*3*. Find the number of vertices in

*G*.

**(ii)**Define

vertex disjoint and edge disjoint subgraphs by drawing the

**04**

relevant graphs.

**OR**

**Q.3 (a)**Show that (

*G*, ) is a cyclic group, where

*G={ 0, 1, 2, 3, 4 }.*

**03**

5

**(b)**Define the following by drawing graphs (i) weak component (ii)

**04**

unilateral component (iii) strong component.

**(c) (i)**Construct the composite tables for

*(i)*addition modulo

*4*and

*(ii)*

**03**

multiplication modulo

*4*for

*Z*

}

3

,

2

,

1

,

0

{

. Check whether they have

4

identity and inverse element.

*a*0

**04**

**(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

**Q.4 (a)**Define algebraic structure, semi group and monoid. Also give related

**03**

examples.

**(b)**Use Warshall's algorithm to obtain path matrix from the adjacency matrix

**04**

of

*v*

*v*

1

4

*v*5

*v*2

*v*3

**(c) (i)**Is the algebraic system

*( Q, * )*a group? Where

*Q*is the set of

**03**

rational numbers and * is a binary operation defined by

*a**

*b*

*a*

*b*

*ab*,

*a*

,

*b*.

*Q*

**(ii)**Let

*( Z, + )*be a group, where

*Z*is the set of integers and + is an

**04**

operation of addition. Let

*H*be a subgroup of

*Z*consisting of elements

multiple of

*5*. Find the left cosets of

*H*in

*Z.*

**OR**

**Q.4 (a)**Prove that there are always an even number of vertices of odd degree in a

**03**

graph.

**(b)**Prove that every subgroup H of an abelian group is normal.

**04**

**(c) (i)**Find the number of edges in a

*r*? regular graph with

*n*? vertices.

**03**

**(ii)**A tree

*T*has

*4*vertices of degree

*2, 4*vertices of degree

*3, 2*vertices

**04**

of degree

*4*. Find the number of pendant vertices in

*T.*

**Q.5 (a)**Show that the operation * defined by

*y*

*x**

*y*

*x*on the set

*N*of natural

**03**

numbers is neither commutative nor associative.

**(b)**Prove that an algebraic structure

*( G, * )*is an abelian group, where

*G*is

**04**

the set of non-zero real numbers and * is a binary operation defined by

*ab*

*a**

*b*

.

2

**(c) (i)**Find out using truth table, whether (

*p*

*r*)

*p*is a tautology.

**03**

**(ii)**Obtain the dnf of the form (

*p*(

*q*

*r*)).

**04**

**OR**

**Q.5 (a)**If

*f*:

*x*2

*x*,

2

*g*:

*x*

*x*and

*h*:

*x*(

*x*),

1 then show that

**03**

(

*fog*)

*oh*

(

*fo goh*).

**(b)**Define lattice. Determine whether the POSET

,

1

({

,

3

,

2

)

1

};

5

,

4

is lattice.

**04**

**(c) (i)**If

*p:*product is good,

*q:*service is good,

*r:*company is public limited,

**03**

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

**04**

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

This post was last modified on 04 March 2021