🧠 Propositional Logic β€” GATE CS Hub

What this folder is

A complete GATE-focused vault for Discrete Mathematics β†’ Chapter 1: Propositional Logic, built from the Neso Academy slides (103 pages) and extended with the topics GATE asks that the slides skip. Every topic note has: concept β†’ truth tables β†’ GATE tips β†’ traps β†’ quick self-check.


πŸ—ΊοΈ Map of Content

#NoteWhat’s insidePriority
0101 PropositionsWhat is / isn’t a proposition, propositional variables⭐
0202 Logical ConnectivesΒ¬ ∧ ∨ βŠ• β†’ ↔ with truth tables⭐⭐⭐
0303 Implication Deep Diveonly if, necessary/sufficient, unless, converse/contrapositive⭐⭐⭐
0404 Precedence and Truth TablesOperator precedence, building truth tables⭐⭐
0505 Translation and ConsistencyEnglish β†’ logic, system-specification consistency⭐⭐
0606 Logic PuzzlesKnights & knaves, detective puzzle, GATE 2015 coin toss⭐⭐
0707 Tautology Contradiction SatisfiabilityTautology, contradiction, contingency, SAT, validity⭐⭐⭐
0808 Logical EquivalencesAll standard laws + conditional/biconditional identities⭐⭐⭐
0909 Rules of Inference8 inference rules, valid arguments, fallacies, limitations⭐⭐⭐
1010 Beyond the SlidesCNF/DNF, functional completeness, counting functions, duality⭐⭐⭐
1111 GATE PYQsAll 9 PYQs from the slides, solved with shortcuts⭐⭐⭐
1212 Practice Problems30 new problems (Easy β†’ GATE 2-mark), hidden answers⭐⭐⭐
1313 FlashcardsSpaced Repetition deck⭐⭐
1414 Memory Tricks and TrapsMnemonics + every edge case GATE uses to trap you⭐⭐⭐
1515 Cheat SheetOne-page revision sheet for the night before⭐⭐⭐

πŸ”— Concept Flow

graph LR
    A[Propositions] --> B[Connectives]
    B --> C[Implication variants]
    B --> D[Precedence & Truth tables]
    D --> E[Translation & Consistency]
    E --> F[Puzzles]
    D --> G[Tautology / SAT / Validity]
    G --> H[Equivalences]
    H --> I[Rules of Inference]
    H --> J[CNF/DNF & Completeness]
    I --> K[First Order Logic]

🎯 How GATE tests this chapter

Question patterns that keep repeating

  1. β€œWhich is a tautology / NOT a tautology?” β†’ use the assume-it’s-false trick (07 Tautology Contradiction Satisfiability).
  2. β€œWhich expressions are equivalent?” β†’ convert to form or Boolean algebra (+, Β·, ’) (08 Logical Equivalences).
  3. β€œWhich inference is valid?” β†’ spot Modus Tollens vs. denying the antecedent (09 Rules of Inference).
  4. Truth-teller / liar puzzles β†’ case-split on the speaker’s type (06 Logic Puzzles).
  5. Custom operator defined by a truth table β†’ read off minterms (11 GATE PYQs β€” GATE 2009).
  6. Counting (rows, functions, satisfying assignments) β†’ 10 Beyond the Slides.

Formats: MCQ (1/2 marks, negative marking), MSQ (no negative marking, but all correct options needed), NAT (numeric, no options).


πŸ“… Suggested study plan (5 sessions)


βœ… Mastery checklist

  • I can write all 6 truth tables from memory in under 1 minute
  • I can convert any β€œonly if / unless / necessary / sufficient” sentence to instantly
  • I know which of converse / inverse / contrapositive is equivalent to
  • I can check a tautology without a full truth table
  • I can recite De Morgan, absorption, distributive, and the 9 conditional identities
  • I can name all 8 rules of inference and the 2 classic fallacies
  • I can convert to CNF/DNF and test functional completeness
  • I’ve solved all 9 PYQs and scored β‰₯ 80% on the practice set

πŸ“ Mistake log

Track every question you get wrong

DateQuestion / SourceMy mistakeCorrect ideaLinked note

Next chapter β†’ First Order Logic