Karnataka State Open University (KSOU) 2011-1st Sem M.Sc Mathematics (Discrete ) - Question Paper
Illllllllllllllllllllllll Math 1.4
I Semester M.Sc. Examination, May 2011 MATHEMATICS Discrete Mathematics
: 3 Hours Max. Marks : 80
Time
I.
Instructions : I) Answer any five questions.
2) All questions carry equal marks.
a) Define Logical Connectives. Construct the truth tables for the following statements :
i)
ii) (pvq)A(~pA~q). 6
b) Define Tautology. Show that the statement (poq)v(~pq)is a contingency. 4
c) Let n be an integer. Prove by indirect method, if n2 is odd, then n is odd. 4
i) Determine the truth value for each of the following statements :
i) If 2 is even, then 2 + 3 = 5.
ii) If 2 is even, then 2 + 3 ?= 5.
iii) If 2 is odd, then 2 + 3 = 5.
iv) If 2 is odd, then 2 + 3 5. 2
a) Define Disjunction Normal Form (DNF), Conjunctive Normal Form (CNF) and Principal Conjunctive Normal Form (PCNF). Obtain the Principal Conjunctive Normal Form of (p a q) A(~pAr). 5
b) Prove that the statement is true by using mathematical induction :
a + ar + ar2 + ... + arn_1 = :for r 1. 5
1-r
c) If n pigeon holes are occupied by n + I or more pigeons, then prove that atleast one pigeon hole is occupied by more than one pigeon. 6
3. a) A professor has got 5 books on Mathematics, 6 books on Physics and 7 books
on Chemistry. He selects 2 from Mathematics, 3 from Physics and 4 from Chemistry. Find number of ways that he can select these books. Also find in how many ways he can arrange the books so that no Physics books can be together. 5
b) Find the number of non-negative integral solution of the equality,
X1 + x2 + x3 + x4 + X a 30 with Xj > 2, Xp > 3, Xq > 4, Xr > 2 and X5 > 0. 5
c) Define the catalan numbers. Using the move R : (x, y) (x + 1, y) and U : (x, y) (x, y + 1), find how many ways can one go
i) from (0, 0) to (6, 6) and not above y = x.
ii) from (2, 1) to (7, 6) and not above y = x - 1. 6
4. a) Find the coefficient of xk in (1 + x + x2) (1 + x)n. 3
b) Find the generating function for the number of partitions of a positive integer n of the form n = X1 + 2x2 + 5xq, given X1, X2, X3 > 1. Hence find the number of partition for 12. 6
c) Explain the rule of solving first order recurrence relation. 4
d) Solve the recurrence relation an = 7an-1 given a2 = 98. 3
5. a) Solve the following recurrence relation by using Difference Method :
i) y+2 - 3y+1 + 2y = 5" + 2n
ii) un+2 + un+1 + un = n2 + n + 1. 10
b) Solve the Fibonacci recurrence relation Fn+2 = Fn+1 + Fn for n > 0, given
F0 = 0, F1 = 1. 6
6. a) Define the equivalence relation. Let R = {(x, y); x - y is divisible by 3}.
Then show that R is an equivalence relation on the set of integers Z. 6
b) Define Equivalence Class. Let R be an equivalence relation defined on a set A. Then prove the following :
i) Each equivalence class is nonempty and A is the union of all equivalence class.
ii) a R bo [a] = [b].
iii) Any two equivalence class are either identical or disjoint. 8
c) Define composition of relation.
Let A = {I, 2, 3, 4}, R = {(I, 2), (I, 3), (2, 4), (3, 2)},
S = {(I, 4), (4, 3), (2, 3), (3, I)}, find SOR. 2
7. a) Define connectivity relation Rw on R. Let R be a relation on a set A. Then
prove that is the transitive closure of R. 8
b) Let A be a set with |A| = n and let R be a relation on A. Then show that
Rw = RuR2u...uRn. 8
8. a) Let A = {I, 2, 3, 4} and Let R = {(I, 2), (2, 3), (3, 4), (2, I)}. Find the
transitive closure of R, by using Warshalls algorithm. 5
b) Define Partial Ordering in a set. Draw the Hasse diagram representing the positive divisors of 36. 3
c) Define Lattice. Let (L, <) be a lattice. Then prove that
a<b
.8
fa v c < b v c
|
Attachment: |
| Earning: Approval pending. |
