B4.2-R3: DISCRETE STRUCTURES
: JANUARY 2006
NOTE:
1. Answer question 1 and any FOUR questions from 2 to 7.
2. Parts of the same question should be answered together and in the same sequence
Time: 3 Hours Total Marks: 100
1. a) Can a relation R in a set A be both symmetric and anti symmetric? Justify your answer.
b) Write the negation of the following by changing the quantifiers:
“Every complete bipartite graph is not planer.”
c) Prove absorption low in a Boolean algebra.
d) How many ways can one right and one left shoe be selected from 10 pairs of shoes without obtaining a pair?
e) What is the largest possible number of vertices in a graph with 35 edges and all vertices of degree at least 3?
f) Find a grammar to generate the set
{0 m1 n | m and n are non negative integers)}
g) Let (A,*) be an algebraic system, where * is a binary operation such that for any a and b in A
a*b = a
Show that this operation is associative.
(7x4)
2. a) Suppose R is an arbitrary transitive and reflexive relation on a set A. Prove that the relation E defined by “x E y iff x R y and y R x” is an equivalence relation.
b) Prove or disprove the validity of the following argument:
i) Every living thing is a plant or animal.
ii) Ram’s dog is alive and is not a plant.
iii) All animals have heart.
iv) Hence Ram’s dog has a heart.
(9+9)
3. a) Prove that is R is a partial ordering relation on a set S, then for n ³ 2,there can not be a sequence s 1, s 2, s 3,…. s n of distinct elements of S such that s 1 R s 2 R s 3…Rs nRs 1.
b) Minimize following switching function
å m (0, 2, 8, 12, 13).
c) Consider the group (Z 4, Å ): the integer modulo 4 group with respect to the operation Å : addition modulo 4. Does H={[0], [2]} form a subgroup of Z 4. If yes, is it a normal subgroup? Justify.
(6+6+6)
4. a) Solve the following:
a n = 2 a n-1 + 1
where
a 0 =0
a 1 =1
a 2 =3.
b) Find a generating function to count the number of integral solutions of
e 1 + e 2+ e 3 = 10 if for each i, 0 £ e 1
(9+9)
For more questions papers visit www.DoeaccOnline.com, www.IgnouOnline.com
5. a) Show that complement of a regular set is a regular set.
b) Write a grammar/ regular expression for the language on the alphabet {0,1} having all the strings with different first and last symbols.
c) Find a deterministic finite state machine that recognizes the set:
L={0 i10 j | i ³ 1, j ³ 1}
(6+6+6)
6. a) Apply Dijkstra’s algorithm to determine a shortest path between a and z in the following graph:
The numbers associated with the edges are distances between vertices.
b) Obtain the principal conjunctive normal form and principal disjunctive normal form of the formula S given by
( Ø P ® R) L (Q « P)
c) State pigeon hole principle show that in a sequence of n2+1 distinct integers, there is either an increasing subsequence of length (n+1) or decreasing subsequence of length.
(6+6+6)
