Logic and Proof Techniques PYQs for GATE CS

Solve 7+ Logic and Proof Techniques previous year questions for GATE CS with answers and detailed solutions. Free sample questions below.

Chapter Roadmap: Logic and Proof Techniques

Chapter Roadmap

Logic and Proof Techniques

1. Propositional Translation and Implication

Translating English to logic. Mastering the implication operator. Foundational.

2. Tautologies and Logical Equivalence

Proving statements are always true/false. Simplifying logic using algebraic laws. High weightage.

3. Predicate Logic and Quantifier Translation

Moving to variables. Universal and existential quantifiers. Very high weightage.

4. Quantified Reasoning and Induction

Nested quantifiers. Proving infinite sequences using induction. Crucial for proofs.

Goal: Read any complex mathematical statement, translate it into perfect logic, and prove its validity.

The Art of Propositional Translation

What is a Proposition?

A proposition is a declarative sentence that has a definitive truth value: it must be either True or False, but never both, and never neither.

Propositions

"The sky is blue."
"Seven is a prime number."

Not Propositions

"Close the door." (Command)
"What is the time?" (Question)

The Translation Process

Identify the atomic (simple) declarative sentences.
Assign a lowercase letter (e.g., $p, q, r$ ) to each.
Identify the connecting words (and, or, if, then).
Map the connecting words to logical operators ( $\land, \lor, \to, \leftrightarrow$ ).

Logic and Proof Techniques: Solved Questions with Step-by-Step Explanations (7 Problems)

Question 1 · Engineering Mathematics · 2026_Set2 MCQ

For two different persons

x

and

y

, the predicate

M (x, y)

denotes that x knows y. Consider the following statement.

There is a person who does not know anyone else, but that person is known by everyone else.

Which one of the following expressions represents the above statement?

A.
$(\exists y) (\forall x) ((x \neq = y) \to (M (x, y) \land \neg M (y, x)))$
B.
$(\forall y) (\exists x) ((x \neq = y) \to (M (x, y) \land \neg M (y, x)))$
C.
$(\exists y) (\exists x) ((x \neq = y) \to (M (x, y) \land \neg M (y, x)))$
D.
$(\forall y) (\forall x) ((x \neq = y) \to (M (x, y) \land \neg M (y, x)))$

Correct Answer:

Step-by-Step Solution

Key idea: This is a nested quantifier translation question, recognizable because it describes a specific relational property ("knows") among a domain of people using phrases like "There is a person" and "everyone else".

Step 1: Identify the core components.

"There is a person" $\to \exists y$ . Let this person be $y$ .

"who does not know anyone else" $\to$ For all $x \neq = y$ , $y$ does not know $x$ . This is $\neg M (y, x)$ .

"but that person is known by everyone else" $\to$ For all $x \neq = y$ , $x$ knows $y$ . This is $M (x, y)$ .

Step 2: Combine the conditions for "everyone else".

For any $x$ , if $x \neq = y$ , then both conditions must hold: $M (x, y) \land \neg M (y, x)$ .

This translates to: $\forall x ((x \neq = y) \to (M (x, y) \land \neg M (y, x)))$ .

Step 3: Attach the outer quantifier.

"There is a person $y$ " wraps around the above:

$\exists y \forall x ((x \neq = y) \to (M (x, y) \land \neg M (y, x)))$ .

Step 4: Match with options.

Option A matches this exactly.

Answer: A

Question 2 · Engineering Mathematics · 2025_Set2 MCQ

Let

P (x)

be an arbitrary predicate over the domain of natural numbers.

Which ONE of the following statements is TRUE?

A.
$(P (0) \land (\forall x [P (x) \Rightarrow P (x + 1)])) \Rightarrow (\forall x P (x))$
B.
$(P (0) \land (\forall x [P (x) \Rightarrow P (x - 1)])) \Rightarrow (\forall x P (x))$
C.
$(P (1000) \land (\forall x [P (x) \Rightarrow P (x - 1)])) \Rightarrow (\forall x P (x))$
D.
$(P (1000) \land (\forall x [P (x) \Rightarrow P (x + 1)])) \Rightarrow (\forall x P (x))$

Correct Answer:

Step-by-Step Solution

Key idea: This is a mathematical induction question, recognizable because it asks to identify the correct logical formulation of the induction principle over the natural numbers.

Step 1: Recall the Principle of Mathematical Induction.

To prove that a predicate $P (x)$ is true for all natural numbers $x \in {0, 1, 2, \dots}$ , we need two steps:

Base Case: Prove $P (0)$ is true.
Inductive Step: Prove that for any arbitrary natural number $x$ , if $P (x)$ is true, then $P (x + 1)$ is true. This is written as $\forall x [P (x) \Rightarrow P (x + 1)]$ .

Step 2: Combine into a single logical implication.

If (Base Case AND Inductive Step) are true, then $P (x)$ is true for all $x$ .

$(P (0) \land (\forall x [P (x) \Rightarrow P (x + 1)])) \Rightarrow (\forall x P (x))$ .

Step 3: Evaluate the options.

Option A matches this standard formulation perfectly.

Options B and C use $P (x) \Rightarrow P (x - 1)$ , which would prove the property downwards (for $x \leq 0$ or $x \leq 1000$ ), not for all natural numbers.

Option D uses $P (1000)$ as the base case and goes upwards, which only proves $P (x)$ for $x \geq 1000$ , missing $0$ through $999$ .

Answer: A

Question 3 · Engineering Mathematics · 2025_Set1 MSQ

Which of the following predicate logic formulae/formula is/are CORRECT representation(s) of the statement: “Everyone has exactly one mother”?

The meanings of the predicates used are:

•

m o t h er (y, x)

y

is the mother of

x

•

n o t e q (x, y)

x

and

y

are not equal

A.
$\forall x \exists y \exists z (m o t h er (y, x) \land \neg m o t h er (z, x))$
B.
$\forall x \exists y [m o t h er (y, x) \land \forall z (n o t e q (z, y) \to \neg m o t h er (z, x))]$
C.
$\forall x \forall y [m o t h er (y, x) \to \exists z (m o t h er (z, x) \land \neg n o t e q (z, y))]$
D.
$\forall x \exists y [m o t h er (y, x) \land \neg\exists z (n o t e q (z, y) \land m o t h er (z, x))]$

Correct Answer:

["B","D"]

Step-by-Step Solution

Key idea: This is a multiple-select question on translating "exactly one" into predicate logic. The phrase "exactly one" requires two parts: existence (at least one) and uniqueness (at most one).

Step 1: Break down "Everyone has exactly one mother".

Part 1 (Existence): For every person $x$ , there exists at least one mother $y$ .

$\forall x \exists y m o t h er (y, x)$

Part 2 (Uniqueness): For every person $x$ , if $y$ is a mother and $z$ is also a mother, then $y$ and $z$ must be the same person ( $y = z$ ).

Alternatively, "there does not exist another person $z$ who is a mother".

Step 2: Evaluate Option B.

$\forall x \exists y [m o t h er (y, x) \land \forall z (n o t e q (z, y) \to \neg m o t h er (z, x))]$

This says: For every $x$ , there is a $y$ who is the mother, AND for all $z$ , if $z$ is not $y$ , then $z$ is NOT the mother.

This perfectly captures existence and uniqueness. (Option B is Correct).

Step 3: Evaluate Option D.

$\forall x \exists y [m o t h er (y, x) \land \neg\exists z (n o t e q (z, y) \land m o t h er (z, x))]$

This says: For every $x$ , there is a $y$ who is the mother, AND there does NOT exist a $z$ such that $z \neq = y$ AND $z$ is the mother.

The condition $\neg\exists z (P (z))$ is logically equivalent to $\forall z (\neg P (z))$ .

So $\neg\exists z (n o t e q (z, y) \land m o t h er (z, x))$ is equivalent to $\forall z \neg (n o t e q (z, y) \land m o t h er (z, x))$ , which by De Morgan's is $\forall z (n o t e q (z, y) \to \neg m o t h er (z, x))$ .

This is exactly Option B. (Option D is Correct).

Step 4: Evaluate Options A and C.

Option A just says there is a mother and a non-mother. It doesn't enforce uniqueness.

Option C says "if y is a mother, then there is a mother z who is equal to y". This is a tautology and doesn't guarantee existence or uniqueness.

Answer: B, D

Question 4 · Engineering Mathematics · 2024_Set2 MCQ

Let

p

and

q

be the following propositions:

p

: Fail grade can be given.

q

: Student scores more than 50% marks.

Consider the statement: “Fail grade cannot be given when student scores more than 50% marks.”

Which one of the following is the CORRECT representation of the above statement in propositional logic?

A.
$q \to \neg p$
B.
$q \to p$
C.
$p \to q$
D.
$\neg p \to q$

Correct Answer:

Step-by-Step Solution

Key idea: This is a propositional translation question, recognizable because it asks to convert an English sentence with conditional keywords into a logical formula.

Step 1: Identify the atomic propositions.

$p$ : Fail grade can be given.

$q$ : Student scores more than 50% marks.

Step 2: Translate the conditional statement.

The statement is: "Fail grade cannot be given when student scores more than 50% marks."

The word "when" acts as "if". So, "If student scores more than 50% marks, then fail grade cannot be given."

This translates to: If $q$ , then $\neg p$ .

In propositional logic, this is written as $q \to \neg p$ .

Step 3: Match with the options.

Option A matches $q \to \neg p$ .

Answer: A

Question 5 · Engineering Mathematics · 2023 MSQ

Geetha has a conjecture about integers, which is of the form

\forall x (P (x) ⟹ \exists y Q (x, y)),

where

P

is a statement about integers, and

Q

is a statement about pairs of integers.
Which of the following (one or more) option(s) would imply Geetha’s conjecture?

A.
$\exists x (P (x) \land \forall y Q (x, y))$
B.
$\forall x \forall y Q (x, y)$
C.
$\exists y \forall x (P (x) ⟹ Q (x, y))$
D.
$\exists x (P (x) \land \exists y Q (x, y))$

Correct Answer:

["B","C"]

Step-by-Step Solution

Key idea: This is a quantified reasoning question about nested quantifiers and implications. The conjecture $\forall x (P (x) ⟹ \exists y Q (x, y))$ requires that for every $x$ , if $P (x)$ holds, then some $y$ exists making $Q (x, y)$ true. We must test which options logically force this to be true for all $x$ .

Step 1: Analyze the conjecture structure.

The conjecture is a universal statement: for ALL $x$ , the implication $P (x) ⟹ \exists y Q (x, y)$ must hold. To imply this, an option must guarantee the condition for every possible $x$ .

Step 2: Evaluate Option A: $\exists x (P (x) \land \forall y Q (x, y))$ .

This asserts there is at least one specific $x_{0}$ where $P (x_{0})$ is true and $Q (x_{0}, y)$ is true for all $y$ . However, this gives no information about any other $x$ . If there exists another $x_{1}$ where $P (x_{1})$ is true but no $y$ satisfies $Q (x_{1}, y)$ , the conjecture fails. Thus, A does not imply the conjecture.

Step 3: Evaluate Option B: $\forall x \forall y Q (x, y)$ .

This asserts $Q (x, y)$ is true for every pair $(x, y)$ . Now take any arbitrary $x$ . If $P (x)$ is true, we can pick any $y$ (the domain is non-empty) and $Q (x, y)$ will be true. Thus $\exists y Q (x, y)$ is guaranteed. This implies the conjecture.

Step 4: Evaluate Option C: $\exists y \forall x (P (x) ⟹ Q (x, y))$ .

This asserts there is a single, fixed $y_{0}$ such that for all $x$ , $P (x) ⟹ Q (x, y_{0})$ . Now take any arbitrary $x$ . If $P (x)$ is true, then by the given condition, $Q (x, y_{0})$ must be true. Since $y_{0}$ exists, we have found a $y$ (namely $y_{0}$ ) such that $Q (x, y)$ is true. Thus $\exists y Q (x, y)$ holds for all $x$ . This implies the conjecture.

Step 5: Evaluate Option D: $\exists x (P (x) \land \exists y Q (x, y))$ .

Similar to Option A, this only guarantees the condition for one specific $x$ . It does not cover all $x$ , so it cannot imply the universal conjecture.

Answer: B, C

Question 6 · Engineering Mathematics · 2021_Set2 MSQ

Choose the correct choice(s) regarding the following propositional logic assertion

S

S : ((P \land Q) \to R) \to ((P \land Q) \to (Q \to R))

A.
$S$ is neither a tautology nor a contradiction.
B.
$S$ is a tautology.
C.
$S$ is a contradiction.
D.
The antecedent of $S$ is logically equivalent to the consequent of $S$ .

Correct Answer:

["B","D"]

Step-by-Step Solution

Key idea: This is a logical equivalence and tautology verification question, recognizable because it asks you to classify a complex implication $S$ and compare its antecedent to its consequent. The key method is to simplify both sides algebraically using the definition of implication and De Morgan's laws.

Step 1: Identify the antecedent and consequent of $S$ .

Let $X = (P \land Q) \to R$ (the antecedent).

Let $Y = (P \land Q) \to (Q \to R)$ (the consequent).

Step 2: Simplify the antecedent $X$ .

Using the definition $A \to B \equiv \neg A \lor B$ :

$X \equiv \neg (P \land Q) \lor R$

Applying De Morgan's law $\neg (A \land B) \equiv \neg A \lor \neg B$ :

$X \equiv \neg P \lor \neg Q \lor R$

Step 3: Simplify the consequent $Y$ .

First, simplify the inner implication $Q \to R$ :

$Q \to R \equiv \neg Q \lor R$

Now substitute back into $Y$ :

$Y \equiv (P \land Q) \to (\neg Q \lor R)$

Apply the definition of implication:

$Y \equiv \neg (P \land Q) \lor (\neg Q \lor R)$

Apply De Morgan's law:

$Y \equiv (\neg P \lor \neg Q) \lor (\neg Q \lor R)$

By associativity and idempotence ( $\neg Q \lor \neg Q \equiv \neg Q$ ):

$Y \equiv \neg P \lor \neg Q \lor R$

Step 4: Compare $X$ and $Y$ .

Both simplify to $\neg P \lor \neg Q \lor R$ , so $X \equiv Y$ .

Therefore, $S$ is of the form $X \to X$ , which is always true.

This means $S$ is a tautology, and the antecedent is logically equivalent to the consequent.

Answer: B, D

Question 7 · Engineering Mathematics · 2021_Set1 MCQ

Let

p

and

q

be two propositions. Consider the following two formulae in propositional logic.

S_{1} : (\neg p \land (p \lor q)) \to q

S_{2} : q \to (\neg p \land (p \lor q))

Which one of the following choices is correct?

A.
Both $S_{1}$ and $S_{2}$ are tautologies.
B.
$S_{1}$ is a tautology but $S_{2}$ is not a tautology.
C.
$S_{1}$ is not a tautology but $S_{2}$ is a tautology.
D.
Neither $S_{1}$ nor $S_{2}$ is a tautology.

Correct Answer:

Step-by-Step Solution

Key idea: This is a tautology checking question, recognizable because it asks to classify propositional formulae as tautologies. We can simplify the expressions algebraically using logical equivalences.

Step 1: Simplify the common subexpression.

Both $S_{1}$ and $S_{2}$ contain the term $(\neg p \land (p \lor q))$ .

Using the Distributive Law:

$\neg p \land (p \lor q) \equiv (\neg p \land p) \lor (\neg p \land q)$

Since $(\neg p \land p)$ is a contradiction (False):

$\equiv F \lor (\neg p \land q) \equiv \neg p \land q$ .

Step 2: Analyze $S_{1}$ .

$S_{1} : (\neg p \land q) \to q$

Using the Implication Law ( $A \to B \equiv \neg A \lor B$ ):

$\equiv \neg (\neg p \land q) \lor q$

Using De Morgan's Law:

$\equiv (p \lor \neg q) \lor q$

Using Associative Law:

$\equiv p \lor (\neg q \lor q)$

Since $(\neg q \lor q)$ is a tautology (True):

$\equiv p \lor T \equiv T$ .

Since $S_{1}$ simplifies to True for all values of $p$ and $q$ , $S_{1}$ is a tautology.

Step 3: Analyze $S_{2}$ .

$S_{2} : q \to (\neg p \land q)$

Using the Implication Law:

$\equiv \neg q \lor (\neg p \land q)$

Using the Distributive Law in reverse:

$\equiv (\neg q \lor \neg p) \land (\neg q \lor q)$

$\equiv (\neg q \lor \neg p) \land T \equiv \neg q \lor \neg p$ .

This expression is not always true (e.g., if $p = T$ and $q = T$ , it evaluates to $F \lor F = F$ ).

Therefore, $S_{2}$ is not a tautology (it is a contingency).

Step 4: Conclusion.

$S_{1}$ is a tautology, but $S_{2}$ is not.

Answer: B

Try a question

Login to view the complete previous-year questions and solutions

Personalised first. High quality throughout.

Built around you, not around a syllabus PDF

Revision that hits your weak spots

Questions calibrated to the real exam

Notes written for recall, not for volume

One place for everything

Honest progress

Unlock the whole course

Logic and Proof Techniques PYQs for GATE CS

Chapter Roadmap: Logic and Proof Techniques

Chapter Roadmap

1. Propositional Translation and Implication

2. Tautologies and Logical Equivalence

3. Predicate Logic and Quantifier Translation

4. Quantified Reasoning and Induction

The Art of Propositional Translation

What is a Proposition?

The Translation Process

Logic and Proof Techniques: Solved Questions with Step-by-Step Explanations (7 Problems)

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

More previous year questions (pyqs) in this unit