DISTANCE EDUCATION
M.Sc. Years Integrated) DEGREE EXAMINATION,
MAY 2016.
DISCRETE MATHEMATICS
Time Three hours Maximum 100 marks
SECTION A — × 8 40 marks)
Answer any FIVE questions.
1. Construct the truth table for
Write in symbolic form the statements
The crop will be destroyed if there is a flood.
If either Terry takes Calculus or Ken takes
sociology then Larry will take English.
2. If A C then find
A B and B A . Also show that A B B A
and A A .
Give the power sets of the following


3. Show that the functions f x3 and 3
1
g x x for x
are inverses of one another.
4. Show that f given by
3
2



x
f x x is a
bijection and find its inverse.
Sub. Code
15
DE-3910
2
wk10
5. If relations R and S are both reflexive, then show that
R and R are also reflexive.
6. Give an example of a semi group but not a monoid.

Show that if every element in a group is its own
inverse then the group must be abelian.
7. Define graph and digraph, and give example to
each.
What is the maximum number of edges of an
undirected simple graph with n vertices?
8. Define
Complete graph
Bipartiate graph.
How many different directed tress are there with
the nodes?
SECTION B — × 15 60 marks)
Answer any FOUR questions.
9. Show that R .

Write an equivalent formula for





Q R
P which
contains neither the biconditional nor the
conditional.
DE-3910
3
wk10
10. Let be the set of integers and let R be the
relation defined by R y x is
divisible by 3}. Determine the equivalence classes
generated by the element of
Show that f defined by f 2x 3 is a
bijection and find its inverse. Also, compute f f
and f f .
11. Let f X be a function and A,B X . Show that
f f f and f f f .
12. For any three sets show that

A B A and A B A B C .
13. Prove that every subgroup of an abelian group is a
normal subgroup.
If f is a homomorphism, then prove that f
is 1-1 if and only if ker f
14. Define a planar graph. Give an example.
Prove that any connected graph with n vertices and
n edges is a tree.
15. Prove that a given connected graph G is an Euler graph
if and only if all vertices of G are of even degree.