Gujarat University
MCA Semester I
DMS
Date; 7th February, 1990 Marks:50
Instructions:
1. Answer the two sections in separate answer books.
2. Question 1 in section I is compulsory. Attempt any two questions from question 2 to 5.
3. Question 6 in section II is compulsory. Attempt any two questions out of questions No. 7 to 10.
4. Each compulsory question carries 9 marks. Each of the other questions carries 8 marks.
Section I
Q-1 a) State, giving reasons, whether the following statements are true or false:
1. There is no subgroup of order 3 of a group of order 5.
2. The system <Z4*, X4> where Z4* = Z4 – {[0]} is a group.
b) Define a Boolean algebra. Exhibit <S,L ,V,Ø , F, T> as a Boolean algebra, where S is the set of statements
L, Ø , V, denote operation of conjunction, disjunction, negation respectively and F and T denote contradictions and tautologies respectively. In any Boolean algebra <B,* ,Å , /, 0, 1>, prove that
a = 0Û ( a * b’) (a’ * b’) = b. Show that a mapping from one Boolean algebra to another which preserves * and also preserves Å.
Q-2 a) Find the set of strings generated by the following grammar G = <{S,A,B,C}, {a, b}, S, f> wheref consists of
the set of productions:
S à aS, S àaB, B à bC, C à aC, C à a.
b) Consider H = <{1,5,7,11}, X12>, the subset of <Z12, X12>. Make the composition table of <H, X12>. Is it a
group? Justify.
Q-3 a) Prove that <Z3, +3, X3> is a filed whereas <Z4, +4, X4> is not a field. Give an example of a ring, which is not
an integral domain and that of an integral domain which is not a filed. Give reasons in favor of your answers.
b) Define a normal subgroup of a group. Determine all the subgroups of the symmetric <S3, ÿ>. Determine
which of these subgroups are normal and which are not. Give reasons.
Q-4 a) Define direct product of two lattices. Show that the lattice <Slog, D> is isomorphic to the direct product of
<S4, D> and <S25, D>.
If a lattice <B,Å , *> is distributive, prove that for a, b, c Î B.
a £ c Þ a Å ( b* c) = ( a Å b) * c
Show that thus result may not hold in a non-distributive lattice.
b) Define an atom in a Boolean algebra. Define A(x), x is an element of a Boolean algebra. State the properties of
A(x). Prove that , if A is the set of atoms of a finite Boolean algebra <B, *,Å , /, 0, 1> the this Boolean algebra is isomorphic with <r(A),Ç ,È , ~,f , A>.
Q-5 a) Define a Boolean expression. When is a Boolean expression said to be a min term? Obtain the sum-of-
products canonical form of the Boolean expression
a(x1, x2, x3, x4) = ( x1 * x2’) Å x4 and deduce its product-of-sums form.
b) Give the circuit diagram representation of the expression:
( a + (a + b + Ç))1/2 ). c. [b ( a + b+ Ç) + bc]
Minimize it using Karnaugh map representation.
Section II
Q-6 a) If X = {1,2,3,4,5} and r= {<x, y> | x > y} is a relation on it, draw the graph of r and give its relation matrix. Is
this relation transitive?
b) Define a graph as an abstract mathematical system. Explain the meanings of:
a simple graph, a digraph, a mixed graph, a weighted graph, isomorphic graphs.
Assuming that there are no loops and that isomorphic graphs are not distinguishable, draw all the possible
simple digraphs having 3 nodes and two edges and show that there are only four such graphs.
Q-7 a) Define a path in a simple digraph. When is a path said to be elementary? Define a node-base of a simple
digraph and state its properties. In the graph G = <V, E>, given in filed, give:
i) the indegree of v4.
ii) All the elementary cycles
iii) The set reachable from v2
iv) Two different node bases
b) When is a simple digraph said to be unilaterally connected? Show that a simple digraph, with no isolated nodes, is strongly connected iff there is a cycle in it which includes each node at least once. Write all the strong, weak and unilateral components of the graph of figure-1. Show that every node and edge of a graph is contained in exactly one weak component.
Q-8 a) Define adjacency matrix of a simple digraph. Obtain the adjacency matrix A of the graph G = <V, E> given as
(see fig-2)
i) Determine the number of paths of length 2 from v4 to v1
ii) Find the outdegree of v1
iii) Show that there exists a simple path of length 4 from v4 to v3.
Verify (i), (ii) and (iii) by calculating A2, AAT and A4.
b) Define the path matrix of a simple digraph. Define the Boolean product ALB of bit matrices A and B. If A
denotes the adjacency matrix <G,E>, describe how you will compute the path matrix P. Obtain the path matrix for the graph given in (a). Give the algorithm WARSHALL to produce P from A.
Q-9 a) Define a directed tree. Explain the difference between a directed tree and an ordered tree. When is a node v, in
a tree said to be a son of u? What is meant by an m-ary tree? Show, by giving an example, that a simple digraph in which exactly one node has indegree 0 and every other node has indegree 1, is not necessarily a directed tree. How will you determine, from the adjacency matrix of a simple diagraph, whether the graph is directed tree or not? If it is a directed tree, how will you determine its root and leaves? Prove that the total number of edges in a complete binary tree having n, leaves is 2 (ni- 1).
b) Consider the tree (see fig-3). Give three other ways to represent it. Determine the binary tree represented by
it. Give the algorithm POSTORDER to traverse this binary tree.
Obtain a test cover for the circuit (see fig-4) and construct a decision tree for it.
Q-10 a) When are two fields said to be isomorphic? Construct a field of order 4.
b) If <R4, +, *> is a ring, define R[x] and show that R[x] is a ring. If F is a field, show that R[x] is an integral
domain which need not be a field. Prove that f(x) = x3 + x+1 is not reducible over Z4.
