Home › GATE CSE › computerscience › Discrete Mathematics › Which statements are LOGICALLY EQUIVALENT to $P …
Which statements are LOGICALLY EQUIVALENT to $P \to Q$?
AConverse and inverse only
BContrapositive only
CConverse only
DAll three (converse, inverse, contrapositive)
Answer & 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)._
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