1
Seat No.: Enrolment
GUJARAT TECHNOLOGICAL UNIVERSITY
MCA INTEGRATED- SEMESTER-II• EXAMINATION SUMMER 2017
Subject Code: 4420601 Date: 31-05-2017
Subject Name: Discrete Mathematics for Computer Science (DMCS)
Time: 10.30am to 01.00pm 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 Join-irreducible elements atom of the Boolean algebra.
Draw Hasse diagram of (S210, and determine Join-irreducible elements and
atom of the Boolean algebra (S210, D).
07
For the poset
Draw the Hasse diagram and find
maximal elements and minimal elements
Greatest element and least element, if exists
Lower bounds of and
Upper bounds of and
07
Q.2 Show that in a lattice if x y z then x y y z
∗ ∗ b′) a
a∗ (a′ a ∗ b
03
02
02
Define Sublattice.
Check whether the following are sublattice of GCD,LCM) or not? Justify.
GCD,LCM)
GCD,LCM)
07
OR
Let be a lattice. For any a,b prove that a a b 07
Q.3 Use the Quine McCluskey method to simplify the sum-of-products
expression:

07
Define: Boolean Algebra. Find all Sub Boolean algebra of Boolean algebra
‹ S30, Λ, 0 1 ›
07
OR
Q.3 Check whether (S45 is a complemented lattice or not? Justify. 07
Use Karnaugh map representation to find a minimal sum-of-products
expression of the following:


07
Q.4 Define:Group. Show that in a group
for any a,b G if 2 2 2 a then must be abelian.
(ii)If be a group then for any two elements a and b of prove
that b-1 a
04
03
Define subgroup of a group, left coset of a subgroup in the group
Find left cosets of in the group
07
2
OR
Q.4 Define Cyclic group.
Show that is a cyclic group and find all the subgroups of
07
Define "Group" "normal subgroup" of a group. Determine all the subgroups
of the symmetric group given in the table below.
P1 P2 P3 P4 P5 P6
P1 P1 P2 P3 P4 P5 P6
P2 P2 P1 P5 P6 P3 P4
P3 P3 P6 P1 P5 P4 P2
P4 P4 P5 P6 P1 P2 P3
P5 P5 P4 P2 P3 P6 P1
P6 P6 P3 P4 P2 P1 P5
07
Q.5 Define Nodebase. Find Nodebase of the following digraph.
07
Define Adjacency matrix.
Obtain the adjacency matrix A of the digraph given below. Also find the
elementary paths of lengths 1 and 2 from to v1 to v4.
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 Binary tree. Convert the given tree into binary tree

07