Kerala university
Second semester BCA degree
examination July 2015
(2013 admission onwards)
Mathematics
Time:3 hours Max
Marks:80
SECTION 1
All the first ten questions are compulsory. Each question carries 1
mark. Answer in one word to maximum of two sentences:
1.
State De morgans’s laws
2.
What is meant by tautology?
3.
When will you say that a function f
:A to B is invertible?
4.
Define equivalence relation.
5.
Give an example of a totally ordered
set
6.
Give an example of a non abelian
group
7.
Find the number of edges in a
complete graph on 6 vertices
8.
Check whether the set Z of integers
with binary operation * such that x* y = xy is a semigroup or not.
9.
Give an example of a regular graph on
five vertices.
10. Define
bipartite graph.
SECTION -11
Answer any 8 questions from among the questions 11 to 22. They carry two
marks each.
11. What
is meant by Boolean expression? Give an example.
12. Draw
the truth table of conditional and biconditional statements
13. Obtain
disjunctive normal forms of:
a.
p^(p àq)
b.
(pVq)’ iff p^q
14. Let
R be an equivalence relation on a set A. Prove that R induces a partition on A
15. Is
the following function one-one ?
F : N à N
where F(n) = 2n, if n is even
n,
n is odd
16. Let
f(x)= x+3, g(x)=x-4, h(x)=5x are functions from R to Rwhere R is the set of
real numbers. Show that fo(goh)=(fog)oh.
17. Let
Z be the set of integers and let T be the set of all even integers. Show that
the semi groups (Z,t) and (T,t) are isomorphic.
18. Define
Hamming distance and state its properties.
19. Prove
that in a simple digraph sum of out degree of all the vertices is equal to the
sum of in degree of all vertices and this sum is equal to the number of edges.
20. Construct
a DFSAM that accept exactly the strings of x’s and y’s that have even number of
y’s.
21. Prove
that in a group G the identity element and inverse of an element is unique.
22. Draw
the complete graph on 4 vertices and find it adjacency matrix.
SECTION – 111
Answer any 6 questions from among the questions 23 to 31. They carry
four marks each.
23. Explain
the resolution principle with a suitable example.
24. Test
the validity of the argument
pàq
q/p
25. Let
A= {1,2,3,4} and R be the raltion { (1,2) , (2,3), (3,4) , (2,1)}. Find the transitive
closure by using Warshal’s algorithm.
26. Let
A be the set of non -zero integers and let ~ be the raltion defined on
A X A by (a,b)~ (c,d) whenever ad=bc. Check whether ~ is an equivalence
relation.
27. Define
bijection. Show that if f anf g are bijections from X to Y and Y to Z
respectively then gof: X to Z is also a bijection.
28. Define
group isomorphisms. Let G be the group of real numbers under addition and let G’
be the group of positive real numbers under multiplication. Show that f:G to G’
defined by f(x)= e^x is an isomorphism.
29. Define
ring and give an example.
30. Explain
the depth first search algorithm with a suitable example.
31. Sketch
the graph of each function:
a.
F(x) = 0.5x – 1
b.
G(x)=0, if x=0
1/x, if x is not equal
to 0
SECTION – 1V
Answer any two questions from among the questions 32 to 35. They carry
15 marks each.
32. a.
Test the validity of the argument:
if a man is a bachelor, he is
unhappy
if a man is unhappy he dies
young.
Bachelors die young.
b. show that the propositions
(p^q)’ and p’Vq’ are logically equivalent.
c. Verify the proposition pV (p^q)’ is a tautology.
33. a.
Explain breadth first search algorithm with a suitable example.
b.Find the inverse of the following functions:
1. f(x) = 2x-3
2. g(x) = (2x-3) / (5x-7)
34. a.Explain
and prove the inclusion – exclusion theorem in set theory.
b.Prove that a hamming code can correct all combinations of k or fewer
errors if and only if the minimum distance between any two code is atleast
2k+1.
35. a.Explain
the communication model and error correction in detail.
b.Let G be a directed graph. Show that a vertex v is the root of a
strongly connected component of G if and only if it lowlink[v]=v.
No comments:
Post a Comment