1
Seat No.: Enrolment
GUJARAT TECHNOLOGICAL UNIVERSITY
MCA SEMESTER- I • EXAMINATION SUMMER 2017
Subject Code: 2610003 Date: 16-06-2017
Subject Name: Discrete Mathematics for Computer Science
Time: 10:30 am 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

Test the validity of the following arguments.
Every integer is a rational number.
3 is an integer.
Therefore, 3 is a rational number.
Let R and S be two relations on a set of positive integers.
R x
S x I
Find R o R and R o S o R.
03
04

Find all sub algebra of Boolean algebra ‹ S30, Λ, 1 ›.
07
Q.2

Prove that set G is a finite abelian group of order 6 with respect to multiplication modulo 7.
07

Given a set S the equivalence relation on S which generates the partition 4,5}.Draw a graph of a relation.
Show without constructing truth table that statement formula is a tautology.
04
03
OR

Let and consider the following collections of subsets of S.
Find which subsets are partitions and which subsets are covering of S.
A
B
C
D
In the following show that statement formula A logically implies statement formula B
A
04
03
Q.3

Prove that S6= is a sub lattice of D>.
07

Give an indirect proof to show that if n² 3 is odd, then n is even.
07
OR
Q.3

Draw Hasse diagram of following Posets.
where x
07

Find the complements of every element of the lattice Sn, for n 45 check for complemented lattice.
07
Q.4

Define: Cyclic Group. Find the generator of
07
2

Check whether the following two posets are lattice or not.
In any Boolean algebra show that a 0 b
04
03
OR
Q.4

Use K-map method to find a minimal SOP expression.

Write the following Boolean expression in an equivalent SOP canonical form
in three variables x1, x2 and x3.
x1 x2
04
03

Show in a lattice if a b and c d then a*c b *d.
In any Boolean algebra show that a b 0
04
03
Q.5

Define Path, Out degree, Strongly connected graph
Symbolize the following sentences by using predicates, quantifiers and
Logical connectives.
Either today is Monday or 7 is an integer number.
If John is in Florida, then 17 is an odd integer.
Construct the truth table for given statement formulas.

p
03
02
02

Define node base of a simple diagraph. Find the reachability set of all nodes for the diagraph given in fig. Also find the node base for it.
V1 V2 V7
V8
V4
V9
V3 V5 V6
07
OR
Q.5

Explain Adjacency matrix of graph G with example.
2)Write a short note on a directed tree
04
03

Find all the components of the following graph.
07

A
B
F
D
C
E
A
B
C
D
V1
V4
V5
V2
V3