# Discrete Mathematics |Gate-2016| previous year questions| Set-5 Discrete Mathematics |Gate-2016|

1. Consider the following expressions:
(i)  false
(ii)  QQ
(iii) true
(iv)  P∨QP∨Q
(v) ¬QVP¬QVP

The number of expressions given above that are logically implied by P∧(P⇒Q)P∧(P⇒Q)) is _____________. [GATE – 2016]

a. 3
b. 4
c. 5
d. 6

2. Let p,q,r,sp,q,r,s represent the following propositions.

p:x∈{8,9,10,11,12}p:x∈{8,9,10,11,12}
q:xq:x is a composite number
r:xr:x is a perfect square
s:xs:x is a prime number

The integer x≥2x≥2 which satisfies ¬((p⇒q)∧(¬r∨¬s))¬((p⇒q)∧(¬r∨¬s)) is ______________. [GATE – 2016]

a. 11
b. 12
c. 13
d. 14

3. Which one of the following well-formed formulae in predicate calculus is NOT valid? [GATE – 2016]

a. (∀xp (x) ∨ ∀xq (x)) => (∃x  ¬ p(x)∨∀xq (x))
b. (∃xp (x)  ∨∃xq(x)) => ∃x (p(x) ∨ q(x))
c. (∃xp (x)  ∧q(x)) => (∃xp (x) ∧∃xq (x))
d. (∀x (p(x) ∨ q (x)) => (∀xp (x)∨∀xq (x))

4. A probability density function on the interval [a,1][a,1] is given by 1/x21/x2 and outside this interval the value of the function is zero. The value of aa is _________. [GATE – 2016]

a. 0.2
b. 0.3
c. 0.4
d. 0.5

5. A binary relation RR on N×NN×N is defined as follows: (a,b)R(c,d)(a,b)R(c,d) if a≤ca≤c or b≤d.b≤d. Consider the following propositions:

P:P: RR is reflexive
Q:Q: RR is transitive

Which one of the following statements is TRUE? [GATE – 2016]

a. Both P and Q are true
b. P is true and Q is false
c. P is false and Q is true
d. Both P and Q are false

6. Consider a set UU of 2323 different compounds in a Chemistry lab. There is a subset SS of UU of 99 compounds, each of which reacts with exactly 33 compounds of U.U. Consider the following statements:

I.I. Each compound in U SU S reacts with an odd number of compounds.
II.II. At least one compound in U SU S reacts with an odd number of compounds.
III.III. Each compound in U SU S reacts with an even number of compounds.

Which one of the above statements is ALWAYS TRUE? [GATE – 2016]

a. Only I
b. Only II
c. Only III
d. None

7. The coefficient of x12x12 in (x3+x4+x5+x6+…)3(x3+x4+x5+x6+…)3 is _____________. [GATE – 2016]

a. 8
b. 9
c. 10
d. 11

8. The minimum number of colours that is sufficient to vertex-colour any planar graph is _____________ . [GATE – 2016]

a. 4
b. 5
c. 6
d. 7