M.C.A. DEGREE EXAMINATION, MAY 2017
First Year
DISCRETE MATHEMATICS
Time 3 Hours Maximum Marks 70
SECTION A × 15 45)
Answer any three of the following
Q1) Show that .
Write a DNF of the following statement p↔q) r}.
Q2) On the set Z of all integers, a relation R is defined by aRb if and only if a2 b2.
Verify that R is equivalence relation.
Let R be a binary relation define as R − determine whether R is
reflexive, symmetric and transitive.
Q3) A question paper contains 10 questions of which 7 are to be answered. In how many
ways a student can select the 7 questions.
If he select 3 questions from the first five and 4 from the last five.
ii) If he should select at least 3 from the first five.
Solve recurrence relation 2
1 3 n n a a n n − − for 0 a =3.
Q4) In any group by proving the inverse of every element is unique. Show that
1 1 1 b a,b G − − − ∀ ∈ .
Prove the laws of idempotent, commutative, associative and absorption in a lattice.
Q5) Using generating function, find the number of integer solutions of the equation:
1 2 3 4 x x x x =25 .
SECTION B × 4 20)
Answer any five from the following
Q6) Show that ∀x ≡∀ x P ∧∀xQ(x) .
Q7) Quantify the following arguments into predicate form:
Some integers are divisible by 5.
All real numbers are complex numbers.
Every living thing is a plant or an animal.
Everybody likes somebody.
Q8) The functions f :R→R and g :R→R are defined by f =3x 7 for all x ∈ R and
3 g x −1) for all x ∈ R verify that f is one-to-one but g is not.
Q9) From 6 boys and 4 girls, 5 are to be selected for admission for a particular course. In How
many ways can be done if there must be exactly 2 girls?
Q10) Prove the following identify C(n r −1) .
Q11) Find the recurrence relation and initial condition for the following sequence:
12, 20, 30, 42.
Q12) Draw the Hasse diagram of the relation R on A whose matrix as given
below:
1 0 1 1 1
0 1 1 1 1
0 0 1 1 1
0 0 0 1 0
0 0 0 0 1
.
Q13) On the set Q of all rational numbers, the operation is defined by a b a b ab.
Show that, under this operation Q forms commutative monoid.
SECTION C × 1
Answer all questions
Q14) Define tautology of logical expression.
Q15) Define binary relation.
Q16) Define first order recurrence relations.
Q17) Define monoid.
Q18) Define distributed lattice.