Birla Institute of Technology and Science, Pilani
First Semester 2021-22
MATH F213 Discrete Mathematics
Mid-Semester Examination
Time : 90 mins Date : 28-10-2021 Max. Marks : 60
Total number of questions : 10, Number of pages : 2
1. Let Q be any propositional function and P be a tautology. Determine, with justification,
which of the following propositional functions are logically equivalent to Q.
(i) (P ∨ (∼ P )) ∨ Q, (ii) (P ∨ Q) ∧ Q, (iii) (Q ∨ (∼ Q)) ∧ (P ∧ Q). [6]
2. Consider the predicates, on the universe U = the set of all citizens, given by P (x) : x is
a politician, L(x) : x is a liar. Write symbolically, using only the connectives ∼, ∧ but
without using the universal quantifier, the proposition ’All politicians are liars’. [4]
3. Using abbreviated truth table method, decide whether the following propositional func-
tion, of propositional variables p, q, r, s, is a tautology or contradiction or contingency :
[(p → q) ∧ (r → s) ∧ (p ∨ r)] → (q ∨ s). [7]
4. Let a human, named Adams, be denoted by a and consider the following predicates on
the universe U = the set of all humans.
W (x) : x works in the factory, U (x) : x is a union member, M (x) : x is in a managerial
position.
Write the following inference symbolically and determine if it is valid or faulty. If valid,
establish the validity by using the fundamental rules of inference in each step, otherwise
establish that it is not valid. [6]
Anyone who works in the factory is either a union member or in a managerial
position. Adams is neither a union member nor in a managerial position.
Therefore Adams does not work in the factory.
5. Let a sequence {Dn }n∈N be recursively defined by Dn = (n − 1) Dn−1 + Dn−2 ; n ≥ 3
with D1 = 0, D2 = 1. By mathematical induction on n, show that Dn = nDn−1 + (−1)n
for all integers n ≥ 2. [7]
6. Find the coefficient of x26 in (x3 + x4 + x5 + · · · + x10 )5 . [4]
7. Using generating functions, determine the number of ways to select five integers from
the closed interval [50, 90], no two of them consecutive. [6]
8. Determine the sequence (an )∞
n=0 where
∞
X x(x + 5)
an x n = .
n=0
(1 − 2x)(1 − x)3
[7]
p(x)
9. Let A(x) = q(x)
denote the generating function for the solution of the recurrence relation
an + 2an−1 − 5an−2 − 6an−3 = 4n , n ≥ 3
a0 = 1, a1 = a2 = 0,
where p(x), q(x) are polynomials with deg p(x) < 4 = deg q(x). Determine q(x) and
p(−1). [6]
10. Solve the recurrence relation
an = (n − 1)an−1 + (n + 1)!, n ≥ 2
a1 = 1.
[7]
Page 2
8
9
this point onwards
10
