0-2693/A-22
M. Sc. EXAMINATION, 2022
(Fourth Semester)
MATHEMATICS
Third Paper
Discrete Mathematical Structures
Time:3 Hours Maximum Marks: 85
Minimum Marks: 29
Section A
(Short Answer Type Questions)
Note: Attempt all questions. Each question carries
5 marks. 5x5-25
1. Define first and last elements with examples.
Or
State Pigeon Hole principle with an example.
(5/05/19)0-2693/A-22 P.T.O.
2. Write the duals of (png)vr and (pag)vi.
Or
Define free and bound variables.
be lattice in which and v denote
3. If (L, a
the operations of meet and join respectively
thenprove that
anb=baa, Va, b e L.
Or
Define modular lattice.
Ifa and b be any elements in a Boolean algebra
B then prove that a-+(a-b) = a.
Or
Express the Boolean expression
E=x(y+x'y+yz)
in terms of its minterm canonical form.
5. What is the characteristic equation of:
Q(k)+20(k-1)-3Q(k-2)-6Q(k-4)=0 ?
0-2693/A-22 2
Or
Give a recursive definition of f(n)= |n.
Section B
(Long Answer Type Questions)
Note Attempt all questions. Each question carries
12 marks. 12 5-60
1. (a) If:
A={1, 2, 3, 4}, B={1,3,9, 10,
C={5,6,7, 8}
R={(, 1),0, 3),(2, 9),(2, 10),(3, 3).
(4,10)}
S={(1, 5),(3, 7),(9, 7).(10, 8)).
then find ROS and its relation matrix and
relation graph.
Or
Find the greatest lower bound and the least
upper bound of the sets {3, 9, 12} and
{1, 2, 4, 5, 10} if they exist in the
poset(z4,1.
(5/05/20)0-2693/A-22 3 P.T.O.
(b) Prove that an cquivalence relation induces
a partition and a partition induces an
equivalence relation.
Or
Find the number of integers between 1
and 250 that are divisible by any of the
integers 2, 3, 5 and7.
2. (a) Prove that the connectives NAND and
NOR are commutative but not associative.
Or
Show that the connectives and are
functionally complete.
(b) Contact circuits that produce the following
outputs:
)p-4)+(p-g)
(ii) (pg)+(P-9)
Gii) (p+a)(p 4
0-2693/A-22
Or
Obtain the principal conjunctive normal
for
(i) (Pagar)v(-parng)v
(pA 4A~r)
(i) PAg)vpaqar).
3. (a) If (L, ) is a distributive lattice and
a, b, ce L, then prove that avb=avc
and aab=anc=»b=c.
Or
Show that DeMorgan's laws hold in a
complemented distributive lattice.
(b) Let the lattice L {1, 2, 3, 4, 6, 12), the
divisions of 12 ordered by divisibility.
Find
(i) The lower bound and upper bound of
L.
(ii) The complement of 4.
(i) Is L a complemented lattice ?
(5/05/21)0-2693/A-22 5 P.T.O.
Or
Show that dual of a latticc is a latticc
4. (a) For any a and b in a Boolcan algcbra
(B,+,) prove that (a+ b) =d b and
(a-b =a +b.
Or
Let S be a non-empty set and P(S) be its
power set. Show that the algebra set
P/S,n, U, ¢, S| is a Boolean algebra.
b) Prove that the order relation< is partial
order relation in a Boolean algebra.
Or
Draw a
switching circuit for the following
Boolean function and replace it by a
simpler one
F(x, , z)= x-z+|y (y+z)
(+x)]
0-2693/A-22
5.
5. (a), Use mathematical induction to show that
8-3" is a multiple of 5.
Or
Solve the recurrence relation:
fn)-7f(n--1)+10f(n-2)=6+ 8m
with f(0)=1 and f(1)=2.
(b) Using generating function solve the
difference equation
Yn+2-6n+1 +8y, =0, yo =1, =4.
Or
Solve
s()-7(-2)+6S(k-3)=0,
s(0)=8, S(1) =6 and S(2) =22.
(5/05/22)0-2693/A-22 150
