Which of these is logically equivalent to "If it rains, the match is cancelled"?

If the match is not cancelled, it does not rain

If the match is cancelled, it rains

If it does not rain, the match is not cancelled

If the match is not cancelled, it does not rain

It rains and the match is cancelled

Which of the following is NOT a tautology?

((p → q) ∧ (q → r)) → (p → r)

Propositional and First-Order Logic

Logic is the one topic in this section where a candidate can be certain of the answer, because every question in propositional logic can be settled by enumeration — and where marks are nonetheless lost, because enumeration under a clock is slow and the shortcuts are unfamiliar. Two of them do most of the work. First, an implication is a disjunction in disguise: p → q is exactly ¬p ∨ q, and rewriting it that way turns a nest of arrows into something De Morgan can be applied to directly. Second, only the contrapositive is equivalent. From p → q you may conclude ¬q → ¬p and nothing else: the converse q → p and the inverse ¬p → ¬q are both independent of the original, and confusing either with it is the commonest single error in the topic — GATE sets it deliberately by putting all three in the option list. Beyond that, remember what an implication with a false antecedent does: it is true, vacuously, which is why "if x is a prime greater than 2 then x is odd" is not falsified by x = 4. The first-order half adds quantifiers and two rules worth holding exactly. Negation flips the quantifier and moves inward: ¬∀x P(x) is ∃x ¬P(x), and ¬∃x P(x) is ∀x ¬P(x). And the order of unlike quantifiers matters: over the reals ∀x ∃y (x < y) is true — every number has something above it — while ∃y ∀x (x < y) is false, since it claims one number above all of them. Swapping them is not a rearrangement, it is a different statement, and a question that offers both is testing whether you read the order rather than the symbols.

The Implication, and Its Three Impostors

Four statements built from p → q, and which of them are equivalent to it
Name and form	Equivalent to p → q?	Why it matters
The original: p → q ≡ ¬p ∨ q	Yes — by definition	Rewriting the arrow as a disjunction is the first move in almost every simplification question.
Contrapositive: ¬q → ¬p	Yes — the only one	Both halves negated and swapped. This is the substitution a proof by contraposition rests on.
Converse: q → p	No	Swapped but not negated. "All squares are rectangles" does not give "all rectangles are squares".
Inverse: ¬p → ¬q	No	Negated but not swapped. It is the contrapositive of the converse, which is why the two stand or fall together.

⚠️ A false antecedent makes an implication true

p → q is false in exactly one row of its truth table: p true and q false. Everywhere else it is true, including both rows where p is false — the vacuous case. So "if 2 + 2 = 5 then the moon is cheese" is a true statement, and a question asking you to count the rows where a formula holds must count those rows too. The habit that protects the mark is to look for the single falsifying row rather than to check all four: an implication fails only where its antecedent holds and its consequent does not.

Truth tables grow as 2ⁿ. Three variables is eight rows, four is sixteen. A question that gives five variables is not asking for a table — it is asking for an algebraic simplification or a single well-chosen row.
Distinct Boolean functions of n variables number 2^(2ⁿ). For two variables that is 2⁴ = 16, which is why the sixteen two-input gates exhaust the possibilities and there is no seventeenth to discover. The count of functions and the count of rows are different questions and both appear.
A tautology is true in every row, a contradiction in none, and a contingency in some. Modus ponens (p ∧ (p → q)) → q, disjunctive syllogism ((p ∨ q) ∧ ¬p) → q, and hypothetical syllogism ((p → q) ∧ (q → r)) → (p → r) are all tautologies, and all three were confirmed by enumeration for this chapter.

Quantifiers — Negation and Order

Two mechanical rules cover nearly every first-order question GATE sets, and both are worth applying symbol by symbol rather than by intuition.

Push the negation inward, flipping each quantifier as it passes. ¬∀x P(x) ≡ ∃x ¬P(x); ¬∃x P(x) ≡ ∀x ¬P(x). Applied twice: ¬∀x ∃y P(x, y) ≡ ∃x ∀y ¬P(x, y). The quantifiers keep their order and each changes its kind — a step candidates often reverse, producing ∀x ∃y ¬P, which is a different claim.
Unlike quantifiers do not commute. ∀x ∃y and ∃y ∀x say different things, and the second is the stronger: it demands one y that works for every x. Over the reals ∀x ∃y (x < y) is true and ∃y ∀x (x < y) is false. Like quantifiers do commute: ∀x ∀y is the same as ∀y ∀x, and likewise for two existentials.

🧠 Translate "all" with an implication and "some" with a conjunction

"Every student passed" is ∀x (Student(x) → Passed(x)) — an implication, so it is vacuously true in a world with no students. "Some student passed" is ∃x (Student(x) ∧ Passed(x)) — a conjunction, which is false in that same empty world. Swapping the connectives is the standard mistranslation and it produces two statements that are nearly always wrong: ∀x (Student(x) ∧ Passed(x)) claims everything in the universe is a student, and ∃x (Student(x) → Passed(x)) is satisfied by any non-student at all.

Key takeaways

p → q is ¬p ∨ q. Rewriting the arrow as a disjunction is the first move in nearly every simplification question.
Only the contrapositive ¬q → ¬p is equivalent to p → q. The converse and the inverse are not, and GATE puts all three in the options.
An implication fails in exactly one row — antecedent true, consequent false. A false antecedent makes it vacuously true.
n variables give 2ⁿ rows and 2^(2ⁿ) distinct Boolean functions. Two variables: 4 rows, 16 functions — two different questions.
Negation flips a quantifier and moves inward: ¬∀x ∃y P ≡ ∃x ∀y ¬P. The order is preserved; the kinds change.
∀x ∃y and ∃y ∀x are different statements, the second stronger. Over the reals the first of x < y is true and the second false.
Translate "all" with →, "some" with ∧. Swapping them gives two statements that are almost always wrong.

Practice questions (8)

Attempt each one before opening the answer. Every explanation names the tempting wrong option as well as the right one, because that is where marks are lost.

The proposition p → q is logically equivalent to:
1. p ∨ ¬q
2. ¬p ∨ q
3. p ∧ ¬q
4. ¬p ∧ q
Show answer
Answer: B — ¬p ∨ q
An implication is false only when p is true and q is false, and ¬p ∨ q is false in exactly that row too — so the two agree on all four rows. Option C is the negation of the implication, which is worth knowing in its own right: ¬(p → q) ≡ p ∧ ¬q, and it is the form a proof by contradiction assumes. Option A swaps which side is negated, giving a formula false only when p is false and q is true — the negation of the converse. Reaching for ¬p ∨ q the moment an arrow appears is what makes De Morgan applicable to a nest of implications.
Which of these is logically equivalent to "If it rains, the match is cancelled"?
1. If the match is cancelled, it rains
2. If it does not rain, the match is not cancelled
3. If the match is not cancelled, it does not rain
4. It rains and the match is cancelled
Show answer
Answer: C — If the match is not cancelled, it does not rain
The original is p → q with p = "it rains" and q = "the match is cancelled". Its contrapositive ¬q → ¬p is option C, and only the contrapositive is equivalent. Option A is the converse and option B the inverse, and both are independent of the original: the match might be cancelled for some other reason, which makes A false while the original holds, and B false in the same situation. Option D is a conjunction, which asserts that it actually is raining — the implication asserts nothing about whether p is true. Note that A and B are equivalent to each other, since the inverse is the contrapositive of the converse, which is why an examiner can offer both without giving anything away.
The number of distinct Boolean functions of two variables is:
1. 4
2. 8
3. 16
4. 256
Show answer
Answer: C — 16
A function of two variables is fixed by its output on each of the 2² = 4 input rows, and each output is one of two values — so there are 2⁴ = 16 functions. The general formula is 2^(2ⁿ), and the double exponent is what makes this grow so fast: three variables give 2⁸ = 256, which is option D and is the answer to the next question in this family. Option A is the number of rows and option B the number of rows for three variables, and offering both alongside the answer is how an examiner checks that you know which count was asked. Sixteen is also why there is no seventeenth two-input logic gate to discover.
The negation of ∀x ∃y P(x, y) is:
1. ∃x ∀y ¬P(x, y)
2. ∀x ∃y ¬P(x, y)
3. ∀y ∃x ¬P(x, y)
4. ∃y ∀x ¬P(x, y)
Show answer
Answer: A — ∃x ∀y ¬P(x, y)
Push the negation inward one quantifier at a time, flipping each as it passes and leaving the order alone: ¬∀x (…) becomes ∃x ¬(…), and then ¬∃y P becomes ∀y ¬P. The result is ∃x ∀y ¬P(x, y). Option B flips nothing and is the commonest wrong answer — it negates the predicate while leaving both quantifiers as they were, which says something quite different. Options C and D reorder the quantifiers as well, and unlike quantifiers do not commute, so reordering changes the statement rather than restating it. Read the answer back in words as a check: the original says every x has some y that works, and its negation says some x has no y that works.
Over the domain of real numbers, consider S₁ = ∀x ∃y (x < y) and S₂ = ∃y ∀x (x < y). Then:
1. Both are true
2. S₁ is true and S₂ is false
3. S₁ is false and S₂ is true
4. Both are false
Show answer
Answer: B — S₁ is true and S₂ is false
S₁ says: for every real x there is some real y above it. True — take y = x + 1, and the y is allowed to depend on x. S₂ says: there is one real y above every real x. False — no real number exceeds all reals, since y itself would have to exceed y. So S₁ true, S₂ false. The two formulas contain the same symbols in a different order, and that order is the entire question: in ∀x ∃y the y may be chosen after seeing x, while in ∃y ∀x it must be chosen first and work for all of them. Whenever a question offers both orderings, translate each into a sentence before comparing them — the symbols look interchangeable and the sentences never do.
Which of the following is NOT a tautology?
1. (p ∧ (p → q)) → q
2. ((p → q) ∧ (q → r)) → (p → r)
3. (p → q) → (q → p)
4. p → (q → p)
Show answer
Answer: C — (p → q) → (q → p)
Option C fails on the row p false, q true: then p → q is true, q → p is false, and a true antecedent with a false consequent makes the whole formula false. So it is not a tautology — it is the claim that an implication gives its own converse, which is exactly the error the previous questions were about. The other three are standard tautologies and were checked by enumeration: A is modus ponens, B is hypothetical syllogism, and D holds because whenever p is true, q → p is true whatever q does. The fastest route on a question like this is not to build four truth tables but to look for one falsifying row in each candidate, and to try p false with q true first, since that is the row that breaks converses.
Which of the following are tautologies? (More than one option may be correct.)
1. ((p ∨ q) ∧ ¬p) → q
2. (p → q) ↔ (¬q → ¬p)
3. (p → q) ↔ (¬p → ¬q)
4. p ↔ q
Show answer
Answer: A — ((p ∨ q) ∧ ¬p) → q; B — (p → q) ↔ (¬q → ¬p)
A is disjunctive syllogism: if p ∨ q holds and p does not, q must — true in every row. B says an implication and its contrapositive are equivalent, which is the one equivalence this chapter insists on, so the biconditional is a tautology. C makes the same claim for the inverse, and fails on p false with q true, where p → q is true and ¬p → ¬q is false. D is a contingency, not a tautology: p ↔ q is true only on the two rows where p and q agree, and a formula true in some rows and false in others is precisely what a tautology is not. Two correct out of four, and since an MSQ gives no partial credit, judging all four is the only way to score it — which costs nothing, because a wrong MSQ carries no penalty.
The number of truth assignments to p, q and r that satisfy (p ∨ q) ∧ (¬p ∨ r) is _____.
Numerical answer — type the value.
Show answer
Answer: 4
There are 2³ = 8 assignments; 4 of them satisfy the formula. Split on p rather than tabulating all eight. If p is true, the first clause holds automatically and the second needs r, so q is free: 2 assignments (p, q, r) = (T, T, T) and (T, F, T). If p is false, the second clause holds automatically and the first needs q, so r is free: 2 more, (F, T, T) and (F, T, F). Total 4, and the case split does in two lines what a table does in eight rows. Splitting on the variable that appears in both clauses is the general trick — it is the same idea as unit propagation in a SAT solver, and it is what makes these questions fast rather than merely finite.