Logic and Proof Techniques Practice Questions for GATE CS

Solve 109+ Logic and Proof Techniques practice 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 (10 Problems)

Question 1 · Engineering Mathematics MCQ

Consider the following two statements regarding nested quantifier conjectures:

Assertion (A): The conjecture

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

implies that for every

x

satisfying

P (x)

, there is a specific

y

(which may depend on

x

) satisfying

Q (x, y)

.

Reason (R): The existential quantifier

\exists y

is inside the scope of the universal quantifier

\forall x

, meaning the choice of

y

is independent of

x

.

Which of the following options is correct?

A.
Both A and R are true and R is the correct explanation of A.
B.
Both A and R are true but R is not the correct explanation of A.
C.
A is true but R is false.
D.
A is false but R is true.

Correct Answer:

Step-by-Step Solution

Key idea: The order of nested quantifiers dictates dependency. An existential quantifier inside a universal quantifier means the existential variable depends on the universal variable.

Exam route: Assertion A correctly states that $y$ may depend on $x$ because $\exists y$ is inside $\forall x$ . Reason R claims that being inside the scope means $y$ is independent of $x$ , which is the exact opposite of the truth. Thus, A is true, but R is false.

Learning route:

Step 1: Evaluate Assertion (A). The statement $\forall x \exists y$ means "for every $x$ , there is a $y$ ". The $y$ can be chosen differently for each $x$ . Thus, $y$ depends on $x$ . A is True.

Step 2: Evaluate Reason (R). The reason claims that $\exists y$ being inside $\forall x$ means $y$ is independent of $x$ . This is false. Scope dependency means the inner variable depends on the outer variable. R is False.

Step 3: Combine the evaluations. A is true, but R is false.

Answer: A is true but R is false (Option C).

Tempting wrong path: A student might confuse the scope rule, thinking that being "inside" the scope isolates the variable, making it independent (Option A). This breaks at misunderstanding the direction of quantifier dependency.

Generalization: Inner quantifiers depend on outer quantifiers. $\forall x \exists y$ means $y$ depends on $x$ .

Verification: If $y$ were independent, the statement would be written $\exists y \forall x$ , meaning a single $y$ works for all $x$ .

Question 2 · Engineering Mathematics MCQ

Match the following implications with their correct negations.

List I (Implication) 1.

p \to q

p \to \neg q

\neg p \to q

List II (Negation) A.

\neg p \land \neg q

p \land q

p \land \neg q

A.
1-C, 2-B, 3-A
B.
1-B, 2-C, 3-A
C.
1-C, 2-A, 3-B
D.
1-A, 2-B, 3-C

Correct Answer:

Step-by-Step Solution

Key idea: The negation of an implication $A \to B$ is $A \land \neg B$ . The hypothesis remains unchanged, and the conclusion is negated.

Step 1: Negate item 1: $\neg (p \to q) \equiv p \land \neg q$ . This matches C.

Step 2: Negate item 2: $\neg (p \to \neg q) \equiv p \land \neg (\neg q) \equiv p \land q$ . This matches B.

Step 3: Negate item 3: $\neg (\neg p \to q) \equiv \neg p \land \neg q$ . This matches A.

Step 4: Combine the matches: 1-C, 2-B, 3-A.

Answer: 1-C, 2-B, 3-A (Option A).

Question 3 · Engineering Mathematics MCQ

Let the domain of discourse be $D = {2, 3, 4, 5}$ . Let $P (x)$ be the predicate " $x$ is prime". Which of the following statements is true?

A.
$\exists! x P (x)$
B.
$\forall x P (x)$
C.
$\exists x \neg P (x)$
D.
$\neg\exists x P (x)$

Correct Answer:

Step-by-Step Solution

Insight: The uniqueness quantifier $\exists!$ requires exactly one element to satisfy the predicate, while $\exists x \neg P (x)$ just requires at least one element to fail it.

Exam route: The prime numbers in ${2, 3, 4, 5}$ are 2, 3, and 5. Since there are three primes, $\exists! x P (x)$ is false. Since 4 is not prime, $\neg P (4)$ is true, making $\exists x \neg P (x)$ true.

Learning route:

Step 1: Identify the domain: ${2, 3, 4, 5}$ .

Step 2: Evaluate $P (x)$ for each element:

$P (2)$ is True (2 is prime).

$P (3)$ is True (3 is prime).

$P (4)$ is False (4 is not prime).

$P (5)$ is True (5 is prime).

Step 3: Evaluate Option A: $\exists! x P (x)$ means exactly one element is prime. We have three, so this is False.

Step 4: Evaluate Option B: $\forall x P (x)$ means all elements are prime. 4 is not, so this is False.

Step 5: Evaluate Option C: $\exists x \neg P (x)$ means at least one element is not prime. Since $P (4)$ is False, $\neg P (4)$ is True. This statement is True.

Step 6: Evaluate Option D: $\neg\exists x P (x)$ means no elements are prime. We have three primes, so this is False.

Answer: $\exists x \neg P (x)$ (Option C).

Tempting wrong path: A student might forget that 2, 3, and 5 are all prime, or mistakenly think 4 is prime, and conclude there is only one prime number in the set, choosing Option A. This breaks at incorrect identification of prime numbers.

Generalization: Always list all elements satisfying the predicate before evaluating uniqueness or existential negation.

Verification: 4 is definitively not prime, so $\neg P (4)$ is true, which directly satisfies $\exists x \neg P (x)$ .

Question 4 · Engineering Mathematics MCQ

Consider the following two statements regarding propositional and predicate logic translation:

Assertion (A): The statement "All computers are electronic" is correctly translated as

\forall x (C (x) \to E (x))

.

Reason (R): The universal quantifier

\forall

must be paired with the conjunction operator

\land

to properly restrict the domain of discourse.

Which of the following options is correct?

A.
Both A and R are true and R is the correct explanation of A.
B.
Both A and R are true but R is not the correct explanation of A.
C.
A is true but R is false.
D.
A is false but R is true.

Correct Answer:

Step-by-Step Solution

Insight: The universal quantifier "All" pairs with implication ( $\to$ ), while the existential quantifier "Some" pairs with conjunction ( $\land$ ).

Exam route: "All computers are electronic" translates to $\forall x (C (x) \to E (x))$ . Thus, Assertion A is true. Reason R claims $\forall$ pairs with $\land$ , which is the standard trap; $\forall$ pairs with $\to$ . Thus, R is false.

Learning route:

Step 1: Evaluate Assertion (A). The phrase "All A are B" is universally translated as $\forall x (A (x) \to B (x))$ . Here, A is "computers" and B is "electronic". The translation $\forall x (C (x) \to E (x))$ is perfectly correct. A is True.

Step 2: Evaluate Reason (R). The reason states that $\forall$ must be paired with $\land$ . This is incorrect. If we wrote $\forall x (C (x) \land E (x))$ , it would mean "Everything in the universe is both a computer and electronic", which restricts the domain incorrectly. The correct pairing for $\forall$ is $\to$ . R is False.

Step 3: Combine the evaluations. A is true, but R is false.

Answer: A is true but R is false (Option C).

Tempting wrong path: A student might believe that $\forall$ acts as a giant AND gate over the domain, and therefore the connective inside the predicate should also be $\land$ , leading them to choose Option A or B. This breaks at confusing the semantic meaning of the quantifier (generalized AND) with the syntactic connective used in the translation (implication).

Generalization: "All A are B" is strictly $\forall x (A (x) \to B (x))$ . Using $\land$ would incorrectly assert that everything in the universe is both A and B.

Verification: If the domain includes an apple, $C (apple)$ is false. In $C (apple) \to E (apple)$ , False $\to$ False is True, which is correct. In $C (apple) \land E (apple)$ , False $\land$ False is False, which incorrectly breaks the statement.

Question 5 · Engineering Mathematics MCQ

Let the domain be $D = {0, 1, 2, 3, 4}$ . Let $P (x, y)$ be the predicate $x - y = 3$ . How many values of $x \in D$ satisfy the statement $\exists y \in D P (x, y)$ ?

A.
2
B.
3
C.
4
D.
5

Correct Answer:

Step-by-Step Solution

Key idea: The existential quantifier $\exists y$ requires finding at least one valid $y$ in the domain for a given $x$ .

Exam route: Solve $x - y = 3$ for $y$ , giving $y = x - 3$ . For $y$ to be in $D$ , we need $0 \leq x - 3 \leq 4$ , which means $3 \leq x \leq 7$ . The only values of $x$ in $D$ that satisfy this are 3 and 4. Thus, 2 values.

Learning route:

Step 1: Understand the condition. We need $\exists y \in D$ such that $x - y = 3$ .

Step 2: Isolate $y$ . $y = x - 3$ .

Step 3: Apply the domain constraint. Since $y \in {0, 1, 2, 3, 4}$ , we must have $0 \leq x - 3 \leq 4$ .

Step 4: Solve the inequality for $x$ . Adding 3 to all parts gives $3 \leq x \leq 7$ .

Step 5: Intersect with the domain of $x$ . $x$ must be in ${0, 1, 2, 3, 4}$ and $3 \leq x \leq 7$ . The valid values are $x = 3$ and $x = 4$ .

Step 6: Count the valid values. There are exactly 2 values.

Answer: 2 (Option A).

Tempting wrong path: A student might make a sign error and solve $x + y = 3 ⟹ y = 3 - x$ . Then $0 \leq 3 - x \leq 4 ⟹ - 1 \leq x \leq 3$ . Intersecting with $D$ gives ${0, 1, 2, 3}$ , leading to a count of 4 (Option C). This breaks at the initial algebraic isolation of $y$ .

Generalization: Always isolate the existentially quantified variable carefully and apply the domain bounds strictly.

Verification: For $x = 3$ , $y = 0 \in D$ . For $x = 4$ , $y = 1 \in D$ . For $x = 2$ , $y = - 1 \in / D$ . The count is exactly 2.

Question 6 · Engineering Mathematics MCQ

Consider the statement: "The program terminates if the input is valid."

Let $p$ represent "The input is valid" and $q$ represent "The program terminates."

Which of the following is the correct propositional logic translation?

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

Correct Answer:

Step-by-Step Solution

Key idea: The word "if" introduces the hypothesis (antecedent) of the implication.

Step 1: Identify the hypothesis and conclusion. The statement is "The program terminates if the input is valid." This can be rewritten in standard form as "If the input is valid, then the program terminates."

Step 2: Assign variables. $p$ : "The input is valid" (hypothesis). $q$ : "The program terminates" (conclusion).

Step 3: Translate to logic. "If $p$ then $q$ " translates to $p \to q$ .

Answer: $p \to q$ (Option A).

Question 7 · Engineering Mathematics MCQ

Let $p$ be "The system crashes" and $q$ be "The power is stable."

Translate the statement: "The system crashes unless the power is stable."

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

Correct Answer:

Step-by-Step Solution

Key idea: "A unless B" translates to "If not B, then A", which is $\neg B \to A$ .

Step 1: Identify A and B. A: "The system crashes" ( $p$ ). B: "The power is stable" ( $q$ ).

Step 2: Apply the "unless" rule. "A unless B" becomes $\neg B \to A$ .

Step 3: Substitute variables. $\neg q \to p$ .

Answer: $\neg q \to p$ (Option B).

Question 8 · Engineering Mathematics MCQ

Let $p$ be "You score above 90%" and $q$ be "You get an A grade."

Which of the following represents " $p$ is a sufficient condition for $q$ "?

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

Correct Answer:

Step-by-Step Solution

Key idea: If $p$ is sufficient for $q$ , then having $p$ is enough to guarantee $q$ . This means $p \to q$ .

Step 1: Identify the sufficient condition. $p$ is sufficient for $q$ .

Step 2: Apply the rule. The sufficient condition is the hypothesis, so it goes on the left side of the implication arrow. Thus, $p \to q$ .

Answer: $p \to q$ (Option A).

Question 9 · Engineering Mathematics MCQ

A university rule states: "A student is eligible for the scholarship only if they maintain a GPA of 3.5 or higher."

Let $p$ be "Student is eligible for the scholarship" and $q$ be "Student maintains a GPA of 3.5 or higher."

What is the correct logical translation?

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

Correct Answer:

Step-by-Step Solution

Key idea: The phrase "only if" introduces the necessary condition, and the arrow points towards it. "A only if B" translates to $A \to B$ .

Step 1: Identify A and B. A: "Student is eligible" ( $p$ ). B: "Maintains GPA 3.5" ( $q$ ).

Step 2: Apply the "only if" rule. $p$ only if $q$ translates to $p \to q$ .

Answer: $p \to q$ (Option B).

Question 10 · Engineering Mathematics MCQ

Consider the following two statements:

Assertion (A): To simplify $\neg p \lor (q \land r)$ , one must expand it to $(\neg p \lor q) \land (\neg p \lor r)$ .

Reason (R): In logic, OR distributes over AND, whereas in standard algebra, addition does not distribute over multiplication.

Which of the following options is correct?

A.
Both A and R are true, but R is not the correct explanation of A.
B.
Both A and R are true, and R is the correct explanation of A.
C.
A is true, but R is false.
D.
A is false, but R is true.

Correct Answer:

Step-by-Step Solution

Key idea: In propositional logic, both AND and OR distribute over each other, unlike standard algebra.

Step 1: Evaluate Assertion (A). The expression $\neg p \lor (q \land r)$ requires distributing the OR over the AND. This yields $(\neg p \lor q) \land (\neg p \lor r)$ . Thus, A is true.

Step 2: Evaluate Reason (R). In logic, OR distributes over AND ( $p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)$ ). In standard algebra, addition does NOT distribute over multiplication ( $a + (b \times c) \neq = (a + b) \times (a + c)$ ). Thus, R is true.

Step 3: Determine the relationship. R correctly explains why A is true, highlighting the unique distribution property of logic compared to algebra.

Answer: Both A and R are true, and R is the correct explanation of A (Option B).

Try a question

Login to view the complete practice 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 Practice Questions 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 (10 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

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

More practice questions in this unit