Gujarat University
MCA Semester I
DMS
Date: 9th March, 1989 Marks:50
Instructions:
1. Attempt any three questions from section I and any three questions from section II.
2. Each question carries equal marks
3. Attempt each section on separate book.
Section I
Q-1 a) Find the left coset of {p1, p3, p6} in the group <S3,ÿ > given as:
ÿ 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 p3 p6 p1 p2 p3
p5 p5 p4 p2 p3 p4 p1
p6 p6 p5 p4 p2 p1 p5
b) Show that the set N of natural numbers is a semigroup under the operation x * y = max (x, y). Is it a a
monoid?
Q-2 a) Define cyclic group. Write the composition table for <x4, +4>. Show that <S6, +6> is a cyclic group,
where S6 is the set of integers module 6.
b) Show that in a group <G, *> , if for any a, b ÎG, (a * b) 2 = a2 * b2 then <G, *> must be an abelian group.
Q-3 a) Write the following Boolean expressions in an equivalent sum-of-products canonical form in three
variables x1, x2, x3.
(i) x1 * x2 ii) (x1 Å x2)’ * x3
b) Show that a lattice if a £ b£ c, than a Å b = b *c and (a * b) Å (b * c) = b = (a Å b) * (a Å c)
Q-4 a) Define group Homomorphism.
Let L = {0, 1} and the lattice <L,£ > be given as
0
½
v 0
Draw the diagrams for the lattices <L2, £ > and <L3, £ >.
b) Simplify the following Boolean expressions:
i) (a * b)’ Å (a Å b)’
ii) (a’ * b’ * c’) Å (a * b’ * c) Å ( a* b’ * c’)
Q-5 a) Define Boolean functions:
Use the Karnaugh Map representation to find a minimal sum of products expression of the following
functions:
f ( a, b, c, d) = å (0, 6, 7, 8, 12, 14)
b) Obtain the sum of products canonical forms of the following Boolean expressions:
i) x1 Å ( x2 * x3’)
ii) (x1 Å x2)’ Å (x1’ * x3)
Section II
Q-6 a) Define :
i) Directed graph
ii) Simple graph
iii) Chain or walk
iv) Fundamental circuit
b) Prove that there are at most 2n-1 vertices at the nth level of a binary tree.
Q-7 a) Prove that every n vertex strongly connected digraph contains at least n edges, where n ³ 2.
b) Show that the sum of indegrees of all the nodes of a simple digraph is equal to the sum of the outdegrees
of all its nodes in any directed graph.
Q-8 a) The complement G of a graph G = <V, E> is a graph having the same vertices as G, but the property that
two distinct vertices G are adjacent iff the same two vertices of G are not adjacent. We will designate G as the pair (V, E). Draw the complement of the graph as shown in fig-1.
b) Find out the reachable sets of (I) v6 (ii) v2 (iii) {v5, v1, v2} (iv) {v1, v6, v9, v10} for the graph as
shown in fig-2. And also find out a node base for it also.
Q-9 a) Sketch out the list structure representation as shown in fig-3.
b) A tree has 2 vertices of degree 2 one vertix of degree 3 and 3 vertices of degree 4. How many vertices of
degree 1 does it have?
Q-10 a) Define finite field. Prove that any field is an integral domain.
b) Define a ring. Show that <S14, +7, X7> is commutative with identity.
OR
Q-10 a) Let x = {1,2,…., 7} and R = {<x, y> | x –y is divisible by 3}, show that R is an equivalence relation.
b) If F: xà y and g: y à z and both f and g are onto functions. Show that gof is also onto. Is gof one-to-one
if both g and f are one-to-one?
