DOEACC Society 2006 DOEACC B Level B4.2 Discrete Structure ( ) - Question Paper

B4.2-R3: DiscRETE STRUCTURES
NOTE:
Time: three Hours Total Marks: 100
1.
a) i) Determine the power sets of {f , { f }}.
ii) Let S={2, 5, Ö2, 25, p, 5/2} and T={4, 25, Ö2, 6, 3/2}
obtain SÇT and T´(SÇT).
b) For integers a,b describe a ~ b if and only if 2a +3b = 5n for a few integer n. Show that ~
describes an equivalence relation on Z.(set of Integers).
c) describe a Monoid.
d) Draw the Hassediagrams for every of the subsequent partial orders.
i) ( { 1,2,3,4,5,6},£ )
ii) ( { {a},{a,b},{a,b,c},{a,b,c,d},{a,c},{c,d} },Í )
e) What is a Spanning tree?
f) Write the converse, inverse and contrapositive of P®Q.
g) Show that the functions f : R ® (1, ¥) and g : (1,¥ ) ® R
described by f(x)=32x +1,
2
log3( x 1)
g( x )
-
= are inverse of every others.
(7x4)
2.
a) obtain the principal disjunctive normal form of (PÙQ) Ú (~PÙR) Ú (QÙR).
b) Show that ~ (PÙQ) follows from ~ P Ù ~Q.
c) In a group of 25 students, 12 have taken Mathematics,8 have taken Mathematics but not
Biology. obtain the number of students who have taken Mathematics and biology and
those who have taken Biology but not Mathematics.
(6+6+6)
3.
a) For any a, b, c, d in a lattice (A, £), if a £ b and c £ d then Prove that (aÚ c) £ (bÚ d) and
(a Ùc) £ (b Ùd) (where Ú is join and Ù is meet operation).
b) Prove that if the meet operation is distributive over the join operation in a lattice, then the
join operation is also distributive over the meet operation.
c) Minimize the subsequent expressions using Karnaugh map.
F = ABC + ABC + ABC + ABC
(6+6+6)
B4.2-R3 Page one of three July, 2006
1. ans ques. one and any 4 ques. from two to 7.
2. Parts of the identical ques. should be answered together and in the identical
sequence.
4.
a) Apply Dijkstra’s algorithm to the graph provided beneath and obtain the shortest path from a to f.
(Show all the steps)
6
1 2
2 five 3
4
7
1
b) describe briefly the following:
i) Cut set
ii) Hamiltonian path
iii) Bipartite Graph
iv) Isomorphic graph
c) For the subsequent graph, obtain its spanning tree of minimal Cost using Kruskal algorithm.
16
21 11
5
19 6
33 14
10
18
(8+4+6)
5.
a) In how many ways seven women and three men are organizes in a row if the three men must always
stand next to every other.
b) i) State pigeonhole principle.
ii) Suppose that a patient is provided a prescription of 45 pills with the instruction to
take at lowest 1 pill per day for 30 days. Then prove that there must be a period
of consecutive days during which the patient takes a total of exactly 14 pills.
B4.2-R3 Page two of three July, 2006
b d
f
e
a
c
1 2
6
5 4
3
c) If Fn satisfies the Fibonacci relation for the Fibonacci series (1,1,2,3…) described by the
recurrence relation, Fn = Fn-1+Fn-2, F0=F1=1 then prove that nth Fibonacci number is provided
by (for n = 0,1,2,3, -----------).
[(1 five n ) (1 five n )]
2n 5
1
Fn = + - -
(6+6+6)
6.
a) Prove that for any a and b in a Boolean algebra
A Ú B = A Ù B and
A Ù B = A Ú B
b) describe the subsequent terms:
i) Permutation of a set
ii) Abelian group
iii) Subgroup
iv) Group Homomorphism.
c) Prove that every finite group of order n is isomorphic to a permutation group of degree n.
(4+8+6)
7.
a) Prove by mathematical induction the following, 3n>n3 for n>3.
b) obtain the regular expressions for a Valid Identifier of any length in C language:
(The rule of an Identifier in C language is that 1st character is an alphabet or an
Underscore and the consequent letters are alphabet and/or digit and/or underscore, no
extra symbols are allowed other than described above).
c) describe a finite State Machine.
d) compute the greatest common divisor of 240 and 70(Step wise) by using Euclid’s
algorithm.
(6+4+4+4)
B4.2-R3 Page three of three July, 2006

Earning:   Approval pending.