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 (x0 2x 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 5a
6a
3n using the method
07
n
n 1
n2
of undetermined coefficients.
OR
(c) Solve the recurrence relation using the method of generating function
07
a 5a
6a
3n ,n ;
2 a ,
0 a .
2
n
n 1
n2
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
Ris 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
v5
v2
v3
(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 2x ,
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