π§ 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
| # | Note | Whatβs inside | Priority |
|---|---|---|---|
| 01 | 01 Propositions | What is / isnβt a proposition, propositional variables | β |
| 02 | 02 Logical Connectives | Β¬ β§ β¨ β β β with truth tables | βββ |
| 03 | 03 Implication Deep Dive | only if, necessary/sufficient, unless, converse/contrapositive | βββ |
| 04 | 04 Precedence and Truth Tables | Operator precedence, building truth tables | ββ |
| 05 | 05 Translation and Consistency | English β logic, system-specification consistency | ββ |
| 06 | 06 Logic Puzzles | Knights & knaves, detective puzzle, GATE 2015 coin toss | ββ |
| 07 | 07 Tautology Contradiction Satisfiability | Tautology, contradiction, contingency, SAT, validity | βββ |
| 08 | 08 Logical Equivalences | All standard laws + conditional/biconditional identities | βββ |
| 09 | 09 Rules of Inference | 8 inference rules, valid arguments, fallacies, limitations | βββ |
| 10 | 10 Beyond the Slides | CNF/DNF, functional completeness, counting functions, duality | βββ |
| 11 | 11 GATE PYQs | All 9 PYQs from the slides, solved with shortcuts | βββ |
| 12 | 12 Practice Problems | 30 new problems (Easy β GATE 2-mark), hidden answers | βββ |
| 13 | 13 Flashcards | Spaced Repetition deck | ββ |
| 14 | 14 Memory Tricks and Traps | Mnemonics + every edge case GATE uses to trap you | βββ |
| 15 | 15 Cheat Sheet | One-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
- βWhich is a tautology / NOT a tautology?β β use the assume-itβs-false trick (07 Tautology Contradiction Satisfiability).
- βWhich expressions are equivalent?β β convert to form or Boolean algebra (+, Β·, β) (08 Logical Equivalences).
- βWhich inference is valid?β β spot Modus Tollens vs. denying the antecedent (09 Rules of Inference).
- Truth-teller / liar puzzles β case-split on the speakerβs type (06 Logic Puzzles).
- Custom operator defined by a truth table β read off minterms (11 GATE PYQs β GATE 2009).
- 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)
- Day 1 β 01 Propositions, 02 Logical Connectives, 03 Implication Deep Dive
- Day 2 β 04 Precedence and Truth Tables, 05 Translation and Consistency, 06 Logic Puzzles
- Day 3 β 07 Tautology Contradiction Satisfiability, 08 Logical Equivalences
- Day 4 β 09 Rules of Inference, 10 Beyond the Slides
- Day 5 β 11 GATE PYQs (timed) β 12 Practice Problems β review 14 Memory Tricks and Traps
- Ongoing β review 13 Flashcards daily; re-read 15 Cheat Sheet weekly
β 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
Date Question / Source My mistake Correct idea Linked note
Next chapter β First Order Logic