Page 1 of 2
Seat No.: Enrolment
GUJARAT TECHNOLOGICAL UNIVERSITY
MCA Integrated- SEMESTER II • EXAMINATION Winter 2018
Subject Code: 4420601 Date: 01/01/2019
Subject Name: Discrete Mathematics For Computer Science
Time: 02:30p.m. To 05:00p.m 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
Least Upper Bound
Maximum
Sub-Lattice
Group
Path
Atoms
Cycle
07

Show that a ⊕ ⊕ a ⊕ b
03
Show that ⊕ y ⊕ ⊕ y ⊕
04
Q.2

Draw Hasse Diagram for poset: <S36 D means division, Write cover of each elements of S36.
07

Define Sub Boolean Algebra. State the necessary and sufficient condition for a subset becomes Sub-Boolean algebra. Find all sub Boolean algebra of D>.
07
OR

Draw Hasse Diagram for poset:
S18
ii)<S24
07
Q.3

Use the Quine-Mc Clusky method to simplify the sum-of-products expression
f .
07

Define K-map. Use the K-map representation to find expression of
Σ
07
Σ
OR
Q.3

Define K-map. Use the K-map representation to find expression of
Σ
07
Σ

Explain distributive lattice and complemented lattice by giving a suitable example.
04
Determine the join-irreducible, meet-irreducible, atoms and anti-atoms for given lattice.
03
Q.4

Define Cyclic group. Prove that is isomorphic to Z7, .
07

Show that the set is not a group with respect to addition.
07
Page 2 of 2
OR
Q.4 Prove that the set G is a finite abelian froup of order 5 with respect to
multiplication modulo 5.
07
Define Cyclic group. Find generators of 07
Q.5 Define node base of a simple digraph. Find reachablility set of all nodes for the following diagraph.
07
Define: Directed tree and its leaf. Draw the graph of the tree represented by

Obtain the binary tree corresponding to it.
07
OR
Q.5 Find the strong components of the following diagraph. Also find its unilateral and weak
components. Also find weather this graph is strongly connected, unilaterally connected, weakly
connected.
07
Define Graph, Directed edge of graph, Adjacent Vertex, Parallel edge, Isomorphic graph, In degree
of a node, Cycle of a path with suitable example.
07