Home › GATE CSE › computerscience › Discrete Mathematics › The IMPLICATION $P \to Q$ is FALSE in exactly wh…
The IMPLICATION $P \to Q$ is FALSE in exactly which case?
AP true, Q true
BP false, Q true
CP true, Q false
DP false, Q false
Answer & 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)._
Related questions
A PREDICATE $P(x)$ isHow many ways to put 10 IDENTICAL balls into 4 DISTINCT boxes (each box can hold 0 or moreHow many DIFFERENT subsets of size 3 can be selected from a set of 7 elements?In how many ways can 7 people sit in a ROW?$\binom{n}{k} = \binom{n}{n-k}$. This identity reflectsHow many DIFFERENT 5-bit binary strings are there?The PIGEONHOLE PRINCIPLE states that if $n$ pigeons are placed into $m$ holes with $n > m$A function $f: A \to B$ is INJECTIVE (one-to-one) if