1
Seat No.: Enrolment
GUJARAT TECHNOLOGICAL UNIVERSITY
MCA SEMESTER-I• EXAMINATION WINTER 2017
Subject Code: 610003 Date: 01-01-2018
Subject Name: Discrete Mathematics for Computer Science (DMCS)
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.
Q.1 Define: Boolean algebra. Draw Hasse diagram of and determine all the
sub Boolean of the Boolean algebra ‹ S30, Λ, 0 1 ›.
07
Use Predicate, Quantifier and logical connectives, Rules of inferences,
Argument forms to prove the following consequence is valid.
All athletes are healthy. All healthy people take vitamins. Grant is an athlete.
Therefore Grant takes vitamin.
07
Q.2 Define Lower bound and greatest lower bound. Let
P 15, 24, be a poset. Draw the Hasse diagram. Find
i)The maximal element minimal element.
ii) The greatest and the least element.
iii)The lower bounds of if any the upper bound of 15 if any.
iv) GLB of 45} LUB of 15}.
07
Using proof by contradiction method, prove that 2 is an irrational number. 07
OR
Define an equivalence relation. Prove that the relation "congruence modulo 3"
given by ≡ x-y is divisible by over the positive integer is an
equivalence relation.
07
Q.3 Define: Sub lattice. Verify whether the given sets are sub lattice of or
not. ,GCD LCM] 15 ,GCD LCM]
07
Use the Karnaugh map representation to find a minimal sum-of-products
expression of f(a c Σ
07
OR
Q.3 Define complemented lattice. Which of two lattices for n=30 and n=45
are complemented? Draw Hasse Diagram of these lattices.
07
Use the Quine McClusky method to simplify the SOP expansion,
f(a c Σ 10, 12, 14).
07
Q.4 Define: Group and Abelian group. Show that in a group
if for every b € b)2 a2 b2, then is an Abelian group.
07
Define :Left coset of a subgroup in the group<G,
Find left cosets of in the group
07
OR
2
Q.4 Define Cyclic group. Show that

is a cyclic group and find all the
generators of

5 Where
5
07
Show that the symmetric set (S3 is a group. Is it abelian? Justify.
07
Q.5 Define Nodebase. Find Nodebase of the following digraph.
07
Define adjacency matrix. Draw di-graph of given adjacency matrix.Find
in-degree out-degree of each vertex from the given adjacency matrix.
1 1
1 1 1
1 1
1
1
A





07
OR
Q.5 Define: Strong component, Unilateral component and weak component of the
digraph.
Determine Strong component, Unilateral component and weak component of
the following digraph.
07
Define tree. Give three different representation of the given tree.

07