What are common examiner traps in Propositional and First-Order Logic?

Using implication (→) instead of conjunction (∧) with existential quantifiers (e.g., incorrectly choosing ∃ x (P(x) → Q(x)) for 'Some P are Q'). Failing to flip the quantifier when distributing over an implication antecedent: ∀ x (P(x) → W) (∃ x P(x)) → W, NOT (∀ x P(x)) → W. Conflating 'at least one' with 'exactly one' by omitting the uniqueness clause ∀ z (z ≠ y → ¬ P(z)). Assuming vacuous truth satisfies existential statements; translating 'everyone has a mother' must use ∀ x ∃ y, not ∀ x ∀ y (... → ...). Confusing variable positions in relational predicates (e.g., M(x, y) vs M(y, x) representing 'x knows y' vs 'y knows x'). Reversing the antecedent and consequent in English statements like 'B when A' or 'A only if B' (incorrectly writing p → q instead of q → ¬ p). Confusing the equivalence of biconditional p ↔ q with its exact negation XOR (p ∧ ¬ q) ∨ (¬ p ∧ q). Failing to flip the quantifier when distributing negation through ∀ or ∃. Misinterpreting divisibility conditions like ∃ z (x = y · z) over positive integers vs general integers. Assuming an existential premise ∃ x ( ) can imply a universal conclusion ∀ x ( ) over a non-singleton domain. Forgetting that any formula logically implies true, omitting it from the count of implied expressions. Confusing A B with B A when evaluating 'which option implies the conjecture' versus 'which option is implied by the conjecture'.

GATE CSE Propositional and First-Order Logic PYQs

Standard yield6.8% of Engineering Mathematics

Across the provided GATE CS exam papers (2012–2026), Propositional and First-Order Logic is tested through two major avenues: formalizing natural language state… Read the guide

Take topic test

Questions: 18
Asked: since 2011
Total marks: 26
Marks / paper: 1

18 GATE CSE Propositional and First-Order Logic PYQs with solutions, from Engineering Mathematics. Browse all GATE CSE PYQs.

Questions

Every official paper that asked this topic, newest first.

What GATE tests in Propositional and First-Order Logic

Concepts, patterns, formulas and traps distilled from past papers.

Across the provided GATE CS exam papers (2012–2026), Propositional and First-Order Logic is tested through two major avenues: formalizing natural language statements into first-order logic (FOL) expressions and analyzing algebraic/truth properties of propositional and predicate formulas (tautology checking, equivalence, and operator properties). Questions frequently test quantifier negation, conditional equivalences, and formal representations of existence, uniqueness, and contrapositives. The topic is evenly balanced between 1-mark conceptual items and 2-mark algebraic simplification or multi-quantifier questions.

Core concepts

Propositional logic connectives (AND, OR, NOT, IMPLIES, BICONDITIONAL, XOR)
Tautology, contradiction, and contingency verification
First-order logic translation of 'some', 'all', 'none', and 'exactly one'
Quantifier scope, binding, and distribution over logical connectives
Contrapositive, converse, and inverse relationships
Algebraic properties of Boolean operators (associativity, commutativity)
Truth assignments satisfying compound formulas over finite sets
Quantifier negation and duality rules (∀ vs ∃)
Propositional logic equivalences (implication, contrapositive, biconditional, XOR)
English language conditional phrasing ('B when A' A → B)
Domain-specific predicate interpretation (divisibility, prime definition, integer arithmetic)
Normal forms (CNF, DNF) for propositional connectives
Logical implication (A B)
Truth functional simplification in propositional logic
Universal and existential quantifiers (∀, ∃)
Quantifier scope and alternation order
Tautologies and trivial entailments (A true)

Recurring question patterns

Natural Language to First-Order Logic Translation
CommonMCQ1.5 marks2026, 2025, 2014, 2012
Translating English assertions involving universal or existential claims, relations, or uniqueness into correct first-order logic formulas.
Tautology and Equivalence Checking
CommonMCQ1.5 marks2021, 2014
Evaluating whether given propositional formulas or pairs of formulas are tautologies, contradictions, or logically equivalent using truth assignments or algebraic laws.
Quantifier Distribution and Predicate Validity
OccasionalMCQ2 marks2020
Testing the validity of moving quantifiers across logical connectives when subformulas do not contain free occurrences of the quantified variable.
Boolean Operator Properties and Custom Truth Tables
Occasionalmixed1.5 marks2016, 2015, 2014
Given an operator defined by a truth table or algebraic condition, checking structural properties like commutativity and associativity, or satisfying truth conditions on discrete domains.
Predicate Semantic Interpretation
OccasionalMCQ2 marks2011
A first-order predicate formula with nested quantifiers is given over an arithmetic or discrete domain (e.g., positive integers), and the candidate must identify which mathematical property (e.g., prime number, parity, divisor relation) the formula defines.
First-Order Logic Formula Equivalence & Quantifier Negation
OccasionalMCQ2 marks2013
Given a quantified logical expression, determine which option is or is not logically equivalent by applying quantifier duality, De Morgan's laws, and conditional equivalence.
Propositional Equivalence & Normal Forms
OccasionalMCQ1 marks2015
Identification of equivalent or non-equivalent propositional formulas (such as biconditional vs XOR, DNF/CNF representations, and material implication expansions).
Natural Language to Propositional Logic Translation
OccasionalMCQ1 marks2024
Mapping an English conditional/logical assertion (e.g., statements using 'when', 'unless', 'only if', 'if and only if') into the correct symbolic propositional representation.
Propositional Logical Implication Counting
CommonNAT1 marks2016
Given a compound premise $A$ (which can be simplified), determine how many among a provided list of propositional formulas $E_i$ satisfy the condition that $A \models E_i$ (i.e., $A \implies E_i$ is a tautology).
First-Order Logic Conjecture Entailment
CommonMSQ1 marks2023
Given a target quantified predicate statement (conjecture), identify all candidate first-order statements from options that logically imply the target statement, testing quantifier alternation ( $\forall \exists$ vs $\exists \forall$ ) and quantifier domain strength.

Formulas GATE uses

Implication Equivalence

P \rightarrow Q \equiv eg P \lor Q

Rewriting conditional statements into disjunctions to test tautologies, quantifier distributions, or contrapositives.

Negation of Implication

eg(P \rightarrow Q) \equiv P \land eg Q

Used when negating universal conditionals, e.g., 'not all rainy days are cold' leading to $\exists d (\text{Rainy}(d) \land eg \text{Cold}(d))$ .

Quantifier Negation (De Morgan's for Quantifiers)

eg \forall x \, P(x) \equiv \exists x \, eg P(x), \quad eg \exists x \, P(x) \equiv \forall x \, eg P(x)

Distributing negation over quantifiers during FOL translation and equivalence verification.

Quantifier Distribution with Constant Subformula

\forall x (P(x) \rightarrow W) \equiv (\exists x \, P(x)) \rightarrow W \quad \text{where $x$ is not free in $W$}

Checking validity of predicate logic transformations when moving quantifiers out of conditional scopes.

Uniqueness Condition in Predicate Logic

\forall z (z \neq y \rightarrow eg P(z)) \equiv eg \exists z (z \neq y \land P(z))

Formalizing 'exactly one' or uniqueness constraints alongside an existential assertion.

Material Implication Equivalence

p \to q \equiv eg p \lor q

Rewriting conditional statements into disjunctive form during equivalence testing and natural language formalization.

Biconditional Expansion

p \leftrightarrow q \equiv (p \to q) \land (q \to p) \equiv ( eg p \lor q) \land (p \lor eg q) \equiv (p \land q) \lor ( eg p \land eg q)

Checking equivalences and normal forms of biconditionals versus XOR ( $p \oplus q \equiv eg(p \leftrightarrow q)$ ).

Quantifier Negation Duality

eg \forall x \, P(x) \equiv \exists x \, eg P(x)$ and $ eg \exists x \, P(x) \equiv \forall x \, eg P(x)

Pushing negations past universal and existential quantifiers in FOL expressions.

De Morgan's Laws

eg(A \land B) \equiv eg A \lor eg B$, $ eg(A \lor B) \equiv eg A \land eg B

Distributing negation over conjunctions and disjunctions inside propositional and first-order formulas.

Modus Ponens Equivalence Simplification

P \wedge (P \implies Q) \equiv P \wedge Q

Used to simplify conjunctive premises containing implications to their minimal conjunctive truth requirement.

Quantifier Exchange / Swapping Implication

\exists y \forall x R(x, y) \implies \forall x \exists y R(x, y)

Used to determine if a uniform witness ( $\exists y \forall x$ ) implies the existence of a point-wise witness ( $\forall x \exists y$ ).

Examiner traps in Propositional and First-Order Logic

Using implication (→) instead of conjunction (∧) with existential quantifiers (e.g., incorrectly choosing ∃ x (P(x) → Q(x)) for 'Some P are Q').
Failing to flip the quantifier when distributing over an implication antecedent: ∀ x (P(x) → W) (∃ x P(x)) → W, NOT (∀ x P(x)) → W.
Conflating 'at least one' with 'exactly one' by omitting the uniqueness clause ∀ z (z ≠ y → ¬ P(z)).
Assuming vacuous truth satisfies existential statements; translating 'everyone has a mother' must use ∀ x ∃ y, not ∀ x ∀ y (... → ...).
Confusing variable positions in relational predicates (e.g., M(x, y) vs M(y, x) representing 'x knows y' vs 'y knows x').
Reversing the antecedent and consequent in English statements like 'B when A' or 'A only if B' (incorrectly writing p → q instead of q → ¬ p).
Confusing the equivalence of biconditional p ↔ q with its exact negation XOR (p ∧ ¬ q) ∨ (¬ p ∧ q).
Failing to flip the quantifier when distributing negation through ∀ or ∃.
Misinterpreting divisibility conditions like ∃ z (x = y · z) over positive integers vs general integers.
Assuming an existential premise ∃ x ( ) can imply a universal conclusion ∀ x ( ) over a non-singleton domain.
Forgetting that any formula logically implies true, omitting it from the count of implied expressions.
Confusing A B with B A when evaluating 'which option implies the conjecture' versus 'which option is implied by the conjecture'.

How questions are asked

Match English natural language statement to FOL formula
Identify which formula among 4 is NOT a tautology / is a tautology
Check equivalence between antecedent and consequent of a compound implication
Determine algebraic properties (commutativity, associativity) from an operator truth table
Evaluate truth of a logical formula over a concrete finite numerical set (NAT/MCQ)
Identify all valid predicate logic expressions for a uniqueness statement (MSQ)
Predicate semantic interpretation (find the mathematical meaning)
Equivalence / Non-equivalence verification (MCQ with multiple algebraic forms)
Natural language to symbolic logic formalization
Count the number of logically implied formulas (NAT)
Identify all statements that logically imply a target quantified formula (MSQ)

Paper trends

Shift from simple single-quantifier translations (e.g., 'Some real numbers are rational' in 2012) to complex nested quantifiers capturing uniqueness and asymmetric relations (e.g., 'Everyone has exactly one mother' in 2025, relational predicates in 2026).
2026, 2025, 2014, 2012
Adoption of MSQ formats to test equivalent syntactic representations of the same semantic statement or joint properties of antecedents and consequents.
2025, 2021
Testing boundary cases of quantifier movement over implications when variables are not free in the consequent/antecedent.
2020
Questions consistently target the core mechanics of logic: translation of conditional constructs at 1 mark and multi-quantifier equivalences or mathematical predicate modeling at 2 marks.
2024, 2015, 2013, 2011
Shift from pure formal algebraic manipulation of logical connectives to contextual real-world or mathematical semantic translations.
2024, 2011
Questions moved from numerical evaluation of propositional implication count (NAT) to conceptual first-order quantifier implication in multi-select format (MSQ).
2023, 2016

Difficulty notes

Easy questions typically involve single-quantifier translations ('Some A are B'), standard contraposition checks, or simple truth-table property evaluations (1 mark). Medium questions require handling nested quantifiers with distinct relational variables ( $x \neq y$ ), formalizing uniqueness constraints (e.g., 'exactly one mother'), or analyzing subtle quantifier distribution rules where a subformula lacks a free variable (2 marks).