Discrete Mathematics — Logic, Sets & Graph Theory
Discrete mathematics covers propositional logic, set theory, relations, functions, and combinatorics. GATE tests logical equivalences, counting principles, and graph properties extensively.
Key Points
- ·Propositional logic: AND (∧), OR (∨), NOT (¬), Implication (→), Biconditional (↔)
- ·Implication p→q ≡ ¬p∨q; contrapositive ¬q→¬p; converse q→p (NOT equivalent)
- ·Tautology: always true; Contradiction: always false; Contingency: depends on values
- ·Predicate logic: ∀x P(x) and ∃x P(x); negation swaps quantifier: ¬∀x ≡ ∃x¬
- ·Equivalence relation: reflexive + symmetric + transitive
- ·Pigeonhole: n+1 items in n boxes → at least one box has ≥ 2 items
- ·Euler circuit: all degrees even; Euler path: exactly 2 odd-degree vertices
Propositional Logic — Making Statements Precise
Imagine you want to write rules for a robot. "IF it is raining AND you have no umbrella, THEN you will get wet." Logic lets us express and reason about such statements precisely.
A proposition is a statement that is either true or false. "5 is even" is false. "The sky is blue" is true.
Truth Table for Basic Connectives
| p | q | p ∧ q (AND) | p ∨ q (OR) | ¬p (NOT) | p → q (IF p THEN q) | p ↔ q (iff) |
|---|---|---|---|---|---|---|
| T | T | T | T | F | T | T |
| T | F | F | T | F | F | F |
| F | T | F | T | T | T | F |
| F | F | F | F | T | T | T |
The most important row to memorise for GATE: p → q is FALSE only when p is TRUE and q is FALSE. Think: "I promised to bring you coffee (p). I came without coffee (q=false). I broke my promise."
Implication and Its Relatives
Given "If it rains (p), I carry an umbrella (q)":
| Name | Form | Equivalent to original? |
|---|---|---|
| Original | p → q | — |
| Converse | q → p | NO |
| Inverse | ¬p → ¬q | NO |
| Contrapositive | ¬q → ¬p | YES |
Why is contrapositive equivalent? "If I do NOT carry an umbrella, then it is NOT raining" — same meaning, just flipped and negated. The converse is a completely different claim.
Key Logical Equivalences
De Morgan's Laws (extremely important):
¬(p ∧ q) ≡ ¬p ∨ ¬q "not (A and B)" = "not A or not B"
¬(p ∨ q) ≡ ¬p ∧ ¬q "not (A or B)" = "not A and not B"
Implication as OR:
p → q ≡ ¬p ∨ q
Double negation:
¬(¬p) ≡ p
Example: Simplify ¬(p → q)
¬(p → q)
≡ ¬(¬p ∨ q) [implication as OR]
≡ p ∧ ¬q [De Morgan]
This means "p is true AND q is false" — exactly when implication fails!
Set Theory — Organising Collections
A set is a collection of distinct objects. Think of sets as circles in a Venn diagram.
A = {1, 2, 3, 4} B = {3, 4, 5, 6}
Venn Diagram:
┌────────────────────────┐
│ A B │
│ (1,2) (3,4) (5,6) │
└────────────────────────┘
A ∩ B = {3,4}
A ∪ B = {1,2,3,4,5,6}
A − B = {1,2} (in A but not B)
Important Counting Rules
Power set of A with |A| = n has 2ⁿ elements. Why? Each element is either IN or OUT of a subset — 2 choices per element.
A = {a, b, c}, |A| = 3
P(A) has 2³ = 8 subsets:
{}, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}
Inclusion-Exclusion:
|A ∪ B| = |A| + |B| − |A ∩ B|
For three sets: |A ∪ B ∪ C| = |A|+|B|+|C| − |A∩B| − |B∩C| − |A∩C| + |A∩B∩C|
Relations and Functions
A relation from A to B is a subset of A × B. A function f: A → B assigns exactly one output to each input.
Types of Functions
Injective (one-to-one): different inputs → different outputs
f(x₁) = f(x₂) implies x₁ = x₂
Surjective (onto): every output is hit by some input
For every y ∈ B, there exists x ∈ A such that f(x) = y
Bijective: both injective AND surjective
↔ has an inverse function
Counting functions: From A (|A|=m) to B (|B|=n): - Total functions: nᵐ - Injective functions: n × (n-1) × ... × (n-m+1) = P(n,m) [needs n ≥ m]
Equivalence Relations
A relation R on set A is an equivalence relation if it is: 1. Reflexive: aRa for all a (everyone is related to themselves) 2. Symmetric: aRb implies bRa (if I'm related to you, you're related to me) 3. Transitive: aRb and bRc implies aRc (if I know you and you know him, I know him)
An equivalence relation partitions the set into equivalence classes — disjoint groups.
Example: "same remainder when divided by 3" on integers: - Class [0] = {..., -3, 0, 3, 6, 9, ...} - Class [1] = {..., -2, 1, 4, 7, 10, ...} - Class [2] = {..., -1, 2, 5, 8, 11, ...}
Counting — Permutations and Combinations
Permutation (order matters): arrange r items from n = P(n,r) = n!/(n−r)! Combination (order doesn't matter): choose r items from n = C(n,r) = n!/[r!(n−r)!]
Think of it: how many ways to choose a president and vice-president from 10 people? - Permutation: P(10,2) = 10×9 = 90 (order matters — different roles)
How many ways to choose a 2-person committee from 10? - Combination: C(10,2) = 45 (order doesn't matter — same committee either way)
Pigeonhole Principle: If n+1 objects go into n boxes, at least one box has ≥ 2 objects.
Example: In a group of 13 people, at least 2 share a birth month. (13 people, 12 months — pigeonhole!)
Graph Theory Basics
A graph G = (V, E) has vertices and edges.
Handshaking Lemma
The sum of all vertex degrees equals twice the number of edges: Σ deg(v) = 2|E|
Therefore: number of odd-degree vertices is always even.
Euler Circuits and Paths
Euler circuit (visits every edge exactly once, returns to start): → Graph is connected AND all vertices have even degree
Euler path (visits every edge exactly once, different start/end): → Graph is connected AND exactly 2 vertices have odd degree
Example: Can you draw this figure without lifting your pen?
A
/|\
/ | \
B--C--D
Degrees: A=3, B=2, C=3, D=2
Odd-degree vertices: A and C (exactly 2) → Euler PATH exists (start at A, end at C).
Quick Check
Q1. Is ¬(p ∧ q) → (¬p ∨ ¬q) a tautology?
Answer: Yes — this is De Morgan's law, which is always true.
Q2. A = {1,2,3}, B = {2,3,4,5}. What is |A ∪ B|?
Answer: |A ∪ B| = |A| + |B| − |A ∩ B| = 3 + 4 − 2 = 5. (A ∩ B = {2,3})
Q3. A graph has 6 vertices each with degree 3. How many edges?
Answer: Σdeg = 6×3 = 18 = 2|E|, so |E| = 9.
Key Formulas
- Inclusion-Exclusion (2 sets): |A∪B| = |A|+|B|−|A∩B|
- Inclusion-Exclusion (3 sets): |A∪B∪C| = |A|+|B|+|C|−|A∩B|−|B∩C|−|A∩C|+|A∩B∩C|
- Permutation: P(n,r) = n!/(n-r)!
- Combination: C(n,r) = n!/[r!(n-r)!]
- Handshaking Lemma: Σ deg(v) = 2|E|
GATE Exam Tips
- ★p→q is FALSE only when p=T and q=F — the implication truth table trips many students
- ★Euler circuit: ALL degrees even. Euler path: exactly 2 odd-degree vertices. Easy to confuse.
- ★Contrapositive (¬q→¬p) is equivalent to p→q; converse (q→p) is NOT
- ★Power set size: always 2^n — a set with 0 elements has 1 subset (the empty set)
Finished reading this topic?
Mark it complete to track your study progress.