Quick Summary: The GATE DA AI syllabus lists “logic: propositional, predicate” — the machinery of exact reasoning. Propositional logic gives you connectives, truth tables, equivalence laws, inference rules and resolution; predicate (first-order) logic adds quantifiers and the art of translating English into symbols. GATE tests both with short, pattern-heavy questions that reward drilled fundamentals. This guide covers every concept with worked examples, the master equivalence table, and the exact traps examiners reuse.
By Piyush Wairale — Instructor, BS Data Science program at IIT Madras · IIT Madras alumnus · 10,000+ GATE students mentored · Last updated: August 2026 · Verified against the official IIT Madras GATE 2027 DA syllabus
Key Takeaways
- An implication p → q is false in exactly one case: p true and q false. It is equivalent to ¬p ∨ q, and to its contrapositive ¬q → ¬p — but NOT to its converse q → p or inverse ¬p → ¬q.
- De Morgan’s laws: ¬(p ∧ q) ≡ ¬p ∨ ¬q and ¬(p ∨ q) ≡ ¬p ∧ ¬q — negation flips the connective.
- Negating quantifiers swaps them: ¬∀x P(x) ≡ ∃x ¬P(x) and ¬∃x P(x) ≡ ∀x ¬P(x); the negation “walks inward” flipping each quantifier it passes.
- Valid inference: modus ponens (from p and p→q conclude q) and modus tollens (from ¬q and p→q conclude ¬p). The classic fallacies — affirming the consequent, denying the antecedent — are the wrong options in every GATE logic MCQ.
- Resolution works on CNF: from (A ∨ B) and (¬B ∨ C) conclude (A ∨ C); a proof by resolution derives the empty clause from the premises plus the negated conclusion.
On this page
Propositional logic & truth tables · The equivalence laws · Inference rules & resolution (worked) · Predicate logic & quantifiers · English → FOL translation (worked) · How GATE tests logic · 2-week plan · FAQs
Logic sits between search and probabilistic reasoning in the GATE DA AI section, and it is the most drill-friendly of the three: a small set of laws, a smaller set of traps, and question patterns that have barely changed in twenty years of GATE across papers. It also pays forward — resolution reappears inside inference engines, and the quantifier discipline you build here keeps every later mathematical statement honest. This guide covers the full syllabus item — logic: propositional, predicate — and pairs with the GATE DA Artificial Intelligence Course & Test Series and the free playlist below.
Watch Free: Artificial Intelligence for GATE DA — Full Playlist
Logic, search and reasoning under uncertainty — taught on the whiteboard with GATE-style problems by Piyush Wairale (IIT Madras):
Subscribe to Piyush Wairale IITM on YouTube for new GATE DA lectures, PYQ solutions and strategy sessions.
Propositional Logic: Syntax, Connectives and Truth Tables
A proposition is a statement that is definitely true or false. Five connectives build everything: negation ¬, conjunction ∧, disjunction ∨, implication →, and biconditional ↔. A formula’s meaning is its truth table; with n atomic propositions the table has 2ⁿ rows. A formula true in every row is a tautology; false in every row, a contradiction; true in some rows, a contingency. A formula is satisfiable if at least one row makes it true, and valid means tautology — and the bridge GATE tests: a formula is valid iff its negation is unsatisfiable.
The implication row is where marks are lost, so stare at it once and forever:
| p | q | p → q | ¬p ∨ q | q → p (converse) | ¬q → ¬p (contrapositive) |
|---|---|---|---|---|---|
| T | T | T | T | T | T |
| T | F | F | F | T | F |
| F | T | T | T | F | T |
| F | F | T | T | T | T |
Read the columns: p → q matches ¬p ∨ q and the contrapositive everywhere — but differs from the converse in two rows. “An implication is equivalent to its contrapositive, not its converse” has decided GATE options for decades. And the row everyone forgets: F → T is true — a false premise makes any implication true (“vacuously”).
The Equivalence Laws You Must Know Cold
- De Morgan: ¬(p ∧ q) ≡ ¬p ∨ ¬q; ¬(p ∨ q) ≡ ¬p ∧ ¬q.
- Implication elimination: p → q ≡ ¬p ∨ q; negation of implication: ¬(p → q) ≡ p ∧ ¬q.
- Biconditional: p ↔ q ≡ (p → q) ∧ (q → p) ≡ (p ∧ q) ∨ (¬p ∧ ¬q).
- Distribution: p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r), and dually for ∨ over ∧.
- Absorption, identity, domination: p ∨ (p ∧ q) ≡ p; p ∧ T ≡ p; p ∨ T ≡ T; plus double negation ¬¬p ≡ p.
The one to burn in deepest is ¬(p → q) ≡ p ∧ ¬q: “it is not the case that if it rains, the match is cancelled” means “it rains AND the match is not cancelled”. GATE loves testing this in words.
Inference Rules, CNF and Resolution — Worked
Two valid rules carry almost every argument question. Modus ponens: from p → q and p, conclude q. Modus tollens: from p → q and ¬q, conclude ¬p. Their evil twins are the classic fallacies: affirming the consequent (from p → q and q, wrongly concluding p) and denying the antecedent (from p → q and ¬p, wrongly concluding ¬q). When a GATE question presents an argument in English and asks whether it is valid, translate to symbols and check which of these four patterns it is — that is the entire skill.
Conjunctive normal form (CNF) writes a formula as an AND of OR-clauses. The conversion recipe: eliminate ↔ and →, push negations inward with De Morgan and double negation, then distribute ∨ over ∧. Resolution operates on CNF clauses: from (A ∨ B) and (¬B ∨ C), resolve on B to get (A ∨ C). To prove a conclusion by resolution, add its negation to the premises and derive the empty clause (a contradiction).
Worked example. Premises: p → q, q → r, p. Prove r. In CNF: (¬p ∨ q), (¬q ∨ r), (p), and the negated conclusion (¬r). Resolve (p) with (¬p ∨ q) → (q). Resolve (q) with (¬q ∨ r) → (r). Resolve (r) with (¬r) → empty clause. Contradiction reached, so r follows — hypothetical syllogism, verified mechanically. GATE asks resolution both directly (“which clause results from resolving…”) and as a validity check exactly like this one.
Predicate (First-Order) Logic: Quantifiers and Their Traps
Propositional logic cannot see inside “all humans are mortal”. Predicate logic adds predicates (P(x): “x is mortal”), constants, and two quantifiers: ∀x (for all) and ∃x (there exists). The four facts GATE returns to every year:
- Negation swaps quantifiers: ¬∀x P(x) ≡ ∃x ¬P(x), and ¬∃x P(x) ≡ ∀x ¬P(x). For nested quantifiers the negation walks inward flipping each one: ¬∀x∃y P(x,y) ≡ ∃x∀y ¬P(x,y).
- Order matters for mixed quantifiers: ∀x∃y Loves(x,y) (“everyone loves someone”) is NOT the same as ∃y∀x Loves(x,y) (“there is someone whom everyone loves”). The second implies the first; never the reverse. This single distinction is GATE’s favourite predicate-logic MCQ.
- Pairing conventions: ∀ pairs naturally with →, ∃ pairs with ∧. “All cats are lazy” is ∀x (Cat(x) → Lazy(x)); “some cat is lazy” is ∃x (Cat(x) ∧ Lazy(x)). Writing ∃x (Cat(x) → Lazy(x)) is the standard wrong option — it is true even if no cats exist.
- Instantiation rules: universal instantiation (from ∀x P(x) infer P(c) for any constant c) and existential generalization (from P(c) infer ∃x P(x)) are the valid directions; going the other way requires care (existential instantiation introduces a fresh constant).
English → First-Order Logic: A Worked Translation Set
| English | FOL | Watch out for |
|---|---|---|
| Every student passed | ∀x (Student(x) → Passed(x)) | ∀ with →, not ∧ |
| Some student passed | ∃x (Student(x) ∧ Passed(x)) | ∃ with ∧, not → |
| No student failed | ∀x (Student(x) → ¬Failed(x)) ≡ ¬∃x (Student(x) ∧ Failed(x)) | Two equivalent forms — GATE lists both |
| Not every student passed | ∃x (Student(x) ∧ ¬Passed(x)) | Negate ∀ → ∃ with negated body |
| Every student read some book | ∀x (Student(x) → ∃y (Book(y) ∧ Read(x,y))) | Different books allowed per student |
| Some book was read by every student | ∃y (Book(y) ∧ ∀x (Student(x) → Read(x,y))) | One shared book — stronger claim |
Work each row until the pattern is reflex: quantifier choice, connective pairing, quantifier order. Those three decisions are the whole of FOL translation at GATE level — and the drill sheet in the AI notes PDF has twenty more with answers.
How GATE Actually Tests Logic
- Tautology / satisfiability checks (1–2 marks): which of these formulas is a tautology (or unsatisfiable)? Truth-table the small ones; simplify the large ones with the laws.
- Equivalence identification (1 mark): which option equals p → q, or ¬(p → q)? The implication table above answers all of them.
- Argument validity (1–2 marks): an English argument to classify as modus ponens/tollens or one of the two fallacies.
- Quantifier negation (1–2 marks): negate a nested quantified statement; the “walk inward and flip” recipe.
- Translation MCQ (2 marks): pick the correct FOL for an English sentence — the ∀/→ vs ∃/∧ pairing and quantifier order decide it.
- Resolution mechanics (1–2 marks): the resolvent of two clauses, or whether the empty clause is derivable.
The 2-Week Logic Study Plan
- Days 1–3: connectives and truth tables; build the implication table from memory; classify ten formulas as tautology/contradiction/contingency.
- Days 4–6: equivalence laws; simplify formulas without truth tables; the negated-implication drill in words.
- Days 7–9: inference rules and fallacies on English arguments; CNF conversion; three resolution proofs end to end.
- Days 10–12: quantifiers — negation drills, order-of-quantifier contrasts, the translation table until reflex.
- Days 13–14: mixed GATE DA and GATE CS logic PYQs; error log; then close the AI section with search and reasoning under uncertainty.
Study the Full AI Section the Structured Way
Search, logic and reasoning under uncertainty — lectures, solved PYQs, tests and revision notes:
- GATE DA Artificial Intelligence Course & Test Series — every logic concept above with worked problems and topic-wise tests.
- GATE DA Artificial Intelligence Notes — Download PDF — equivalence laws, quantifier recipes and drill sheets in revision-ready form.
- Complete GATE DA 2027 Course — all 7 subjects in one package.
FAQs on Logic for GATE DA
Why is F → T true?
An implication only promises something when its premise holds. If the premise is false, the promise is never put to the test, so the implication is (vacuously) true. p → q is false only in the single case p = T, q = F.
What is the difference between the converse and the contrapositive?
For p → q: the converse is q → p (NOT equivalent), the inverse is ¬p → ¬q (NOT equivalent, but equivalent to the converse), and the contrapositive is ¬q → ¬p (equivalent to the original). Only the contrapositive preserves truth.
How do I negate ∀x∃y P(x,y)?
Walk the negation inward, flipping each quantifier: ¬∀x∃y P(x,y) ≡ ∃x¬∃y P(x,y) ≡ ∃x∀y ¬P(x,y). “It is not true that everyone has someone” becomes “someone has no one”.
Is resolution in the GATE DA syllabus?
Yes — inference in propositional and predicate logic is part of the “logic” item, and resolution is the standard inference procedure. Expect resolvent-of-two-clauses questions and short refutation proofs like the worked example above.
How many marks is logic worth in GATE DA?
Typically 2–3 marks of the AI section — but its habits (quantifier discipline, implication handling) silently protect marks across the whole paper, from probability statements to algorithm-property MCQs.
Logic is the cheapest insurance policy in GATE DA: two weeks of drills on one table of laws, four inference patterns and three quantifier recipes, and its questions become automatic. With search, logic and reasoning under uncertainty covered, the entire AI section is now in hand — see the full GATE DA syllabus roadmap for what to sequence next.
Master the GATE DA AI Section
Search, logic and reasoning under uncertainty — complete lectures, worked problems, PYQs and tests by Piyush Wairale (IIT Madras).
Join the AI Course & Test Series Download the AI Notes PDFOr get every subject together in the complete GATE DA course 2027.
Recent Post
Complete GATE RA 2027 guide to forward kinematics of manipulators: rotation matrices, homogeneous transformations, the DH convention, planar 2R and articulated RRR arms, the Jacobian, and five worked GATE-style problems with diagrams.
GATE 2027 registration is postponed: the portal now opens 27 August and closes 27 September 2026 (late fee till 5 October). New dates, reasons and what DA aspirants should do.
GATE DA 2027 registration opens Aug 27 at gate2027.iitm.ac.in. Step-by-step application guide: dates, fees, DigiLocker facial recognition, documents and mistakes to avoid.
A* search and alpha-beta pruning for GATE DA 2027: full open/closed-list trace, admissible heuristics, minimax with pruning counted leaf by leaf, solved problems.
Taylor series and maxima-minima for GATE DA 2027: standard expansions, e^0.1 and cos(0.2) approximated, derivative tests and the Hessian rule worked with solved problems.
Normal forms for GATE DA 2027: functional dependencies, attribute closure worked, 1NF to BCNF with full decompositions, checklist table and solved GATE problems.
Learn Daily, Wherever You Are
Free lectures, exam updates, PYQ discussions, and job alerts — delivered through our YouTube channel and Telegram communities.
