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'.

Propositional and First-Order Logic

18 Qs · since 2011 · 26 marks · 1 marks/paperStandard yield

Take topic test

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-ord… Guide

Type

GATE CSE 2026 Set 2Q11MCQ1 markEasyFor 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?
GATE CSE 2025 Set 1Q48MSQ2 marksMediumWhich 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: • $mother(y,x)$ : $y$ is the mother of $x$ • $noteq(x,y)$ : $x$ and $y$ are not equal
GATE CSE 2024 Set 2Q12MCQ1 markEasyLet $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…
GATE CSE 2023Q26MSQ1 markMediumGeetha has a conjecture about integers, which is of the form $\forall x\Big(P(x) \implies \exists y Q(x,y)\Big),$ 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?
GATE CSE 2021 Set 1Q7MCQ1 markEasyLet $p$ and $q$ be two propositions. Consider the following two formulae in propositional logic. $S_1 : \quad ( eg p \land (p \lor q)) \rightarrow q$ $S_2 : \quad q \rightarrow ( eg p \land (p \lor q))$ Which one of the following choices is correct?
GATE CSE 2021 Set 2Q15MSQ1 markEasyChoose the correct choice(s) regarding the following propositional logic assertion $S$ : $S : ((P \wedge Q) \rightarrow R) \rightarrow ((P \wedge Q) \rightarrow (Q \rightarrow R))$
GATE CSE 2020Q39MCQ2 marksMediumWhich one of the following predicate formulae is NOT logically valid? Note that $W$ is a predicate formula without any free occurrence of $x$ .
GATE CSE 2016 Set 1Q1NAT1 markEasyLet $p, q, r, s$ represent the following propositions. $p: x \in \{8, 9, 10, 11, 12\}$ $q: x\text{ is a composite number}$ $r: x\text{ is a perfect square}$ $s: x\text{ is a prime number}$ The integer $x \ge 2$ which satisfies $eg((p \Rightarrow q) \wedge ( eg r \vee eg s))$ is ________ .
GATE CSE 2016 Set 2Q1NAT1 markEasyConsider the following expressions: (i) $false$ (ii) $Q$ (iii) $true$ (iv) $P \vee Q$ (v) $eg Q \vee P$ The number of expressions given above that are logically implied by $P \wedge (P \Rightarrow Q)$ is ________.
GATE CSE 2015 Set 1Q14MCQ1 markEasyWhich one of the following is NOT equivalent to $p \leftrightarrow q$ ?
GATE CSE 2015 Set 1Q28MCQ2 marksEasyDiagramThe binary operator $\neq$ is defined by the following truth table. Which one of the following is true about the binary operator $\neq$ ?
GATE CSE 2014 Set 1Q53MCQ2 marksEasyWhich one of the following propositional logic formulas is TRUE when exactly two of $p$ , $q$ , and $r$ are $\text{TRUE}$ ?
GATE CSE 2014 Set 2Q53MCQ2 marksMediumWhich one of the following Boolean expressions is NOT a tautology?
GATE CSE 2014 Set 3Q1MCQ1 markEasyConsider the following statements: $\text{P:}$ Good mobile phones are not cheap $\text{Q:}$ Cheap mobile phones are not good $\text{L: P}$ implies $\text{Q}$ $\text{M: Q}$ implies $\text{P}$ $\text{N: P}$ is equivalent to $\text{Q}$ Which one of the following about L, M, and N is $\textbf{CORRECT}$ ?
GATE CSE 2014 Set 3Q53MCQ2 marksEasyThe CORRECT formula for the sentence, “not all rainy days are cold” is
GATE CSE 2013Q47MCQ2 marksMediumWhich one of the following is NOT logically equivalent to $eg \exists x (\forall y (\alpha) \wedge \forall z (\beta))$ ?
GATE CSE 2012Q13MCQ1 markEasyWhat is the correct translation of the following statement into mathematical logic? “Some real numbers are rational”
GATE CSE 2011Q30MCQ2 marksMediumWhich one of the following options is CORRECT given three positive integers $x$ , $y$ and $z$ , and a predicate $P(x) = eg (x = 1) \land \forall y ((\exists z (x = y * z)) \Rightarrow (y = x) \lor (y = 1))$

Topic guide

What does GATE test in Propositional and First-Order Logic?

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
common · MCQ · 1.5 marks · 2026, 2025, 2014, 2012
Translating English assertions involving universal or existential claims, relations, or uniqueness into correct first-order logic formulas.
Tautology and Equivalence Checking
common · MCQ · 1.5 marks · 2021, 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
occasional · MCQ · 2 marks · 2020
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
occasional · mixed · 1.5 marks · 2016, 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
occasional · MCQ · 2 marks · 2011
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
occasional · MCQ · 2 marks · 2013
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
occasional · MCQ · 1 marks · 2015
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
occasional · MCQ · 1 marks · 2024
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
common · NAT · 1 marks · 2016
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
common · MSQ · 1 marks · 2023
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).