Start learning →

GATE CSE Discrete Mathematics — practice questions

Explore 13 free Discrete Mathematics questions in GATE CSE Computer Science. Open each question or exercise to read its content, reference answers and available explanation.

Practise Discrete Mathematics with Quill →

Discrete Mathematics questions and exercises with answers

Showing questions 1–13 of 13.

The IMPLICATION $P \to Q$ is FALSE in exactly which case?Read the answer and worked solution →The CONTRAPOSITIVE of $P \to Q$ isRead the answer and worked solution →Which statements are LOGICALLY EQUIVALENT to $P \to Q$?Read the answer and worked solution →The NEGATION of $\forall x\, P(x)$ isRead the answer and worked solution →The POWER SET of a set with $n$ elements hasRead the answer and worked solution →$|A \cup B|$ (size of union) equalsRead the answer and worked solution →A function $f: A \to B$ is INJECTIVE (one-to-one) ifRead the answer and worked solution →How many DIFFERENT 5-bit binary strings are there?Read the answer and worked solution →$\binom{n}{k} = \binom{n}{n-k}$. This identity reflectsRead the answer and worked solution →In how many ways can 7 people sit in a ROW?Read the answer and worked solution →How many DIFFERENT subsets of size 3 can be selected from a set of 7 elements?Read the answer and worked solution →How many ways to put 10 IDENTICAL balls into 4 DISTINCT boxes (each box can hold 0 or more)?Read the answer and worked solution →A PREDICATE $P(x)$ isRead the answer and worked solution →

Worked practice questions

The IMPLICATION $P \to Q$ is FALSE in exactly which case?

  1. P true, Q true
  2. P false, Q true
  3. P true, Q false
  4. P false, Q false
Show answer and solution

Correct answer: C. P true, Q false

1. The truth table of $P \to Q$: - T → T: TRUE - T → F: FALSE (the only false case) - F → T: TRUE (vacuously) - F → F: TRUE (vacuously) 2. An implication is FALSE only when the premise holds but the conclusion fails. 3. The 'vacuously true' cases (premise false) sometimes confuse people but are essential — they make implications useful for proving general statements. _Source: Oscar Levin, "Discrete Mathematics: An Open Introduction", §0.2 (Implications)._

Open this question →

The CONTRAPOSITIVE of $P \to Q$ is

  1. $Q \to P$ (converse)
  2. $\neg P \to \neg Q$ (inverse)
  3. $\neg Q \to \neg P$
  4. $P \land \neg Q$
Show answer and solution

Correct answer: C. $\neg Q \to \neg P$

1. CONTRAPOSITIVE: negate and reverse both sides. $P \to Q$ becomes $\neg Q \to \neg P$. 2. CRUCIAL: an implication and its contrapositive are LOGICALLY EQUIVALENT — they have the same truth table. 3. Example: 'If it rains, the street is wet' has contrapositive 'If the street is not wet, it did not rain'. 4. Option A is the CONVERSE (not logically equivalent). Option B is the INVERSE (also not equivalent). Option D is the NEGATION of the implication. _Source: Oscar Levin, "Discrete Mathematics: An Open Introduction", §0.2 (Implications, Converse, Inverse, Contrapositive)._

Open this question →

Which statements are LOGICALLY EQUIVALENT to $P \to Q$?

  1. Converse and inverse only
  2. Contrapositive only
  3. Converse only
  4. All three (converse, inverse, contrapositive)
Show answer and solution

Correct answer: B. Contrapositive only

1. Among the four related statements: - Implication: $P \to Q$ - Converse: $Q \to P$ - Inverse: $\neg P \to \neg Q$ - Contrapositive: $\neg Q \to \neg P$ 2. ONLY the implication and its CONTRAPOSITIVE share the same truth table. 3. CONVERSE and INVERSE share each other's truth table but are NOT equivalent to the original. 4. So the only equivalent statement is the contrapositive — option B. _Source: Oscar Levin, "Discrete Mathematics: An Open Introduction", §0.2 (Logical equivalence)._

Open this question →

How to practise

  1. Choose a Discrete Mathematics question and try to work out your answer.
  2. Open the question to check the correct answer and read its worked solution.
  3. Continue in the app for bite-sized lessons, explanations and review with Quill. You can start without creating an account.

More Computer Science topics

AlgorithmsDatabase Management SystemsCompiler DesignOperating SystemsComputer NetworksTheory of Computation