Discrete Mathematics — Concise Notes (4 Units)
Prepared for: [Link] (IT) — 2nd Year
Contents: Unit I — Logic & Sets; Unit II — Relations & Functions; Unit III — Counting & Recurrence; Unit
IV — Graphs & Trees
Unit I — Propositional & Predicate Logic; Sets; Proof Techniques
1. Propositional Logic
- Proposition: a statement that is either true or false. - Logical connectives: ¬ (not), ∧ (and), ∨ (or), →
(implies), ↔ (iff). - Truth tables: how to compute compound proposition truth values. - Tautology,
contradiction, contingency. - Logical equivalences (De Morgan, distributive, associative, commutative,
implication equivalence). - Normal forms: CNF (Conjunctive Normal Form), DNF (Disjunctive Normal
Form).
Example — show (p → q) ≡ (¬p ∨ q):
Construct truth table or use implication equivalence: p→q is ¬p ∨ q.
2. Predicate Logic
- Predicates and quantifiers: ∀ (for all), ∃ (exists). - Free vs bound variables, domain of discourse. -
Negation of quantifiers: ¬(∀x P(x)) ≡ ∃x ¬P(x); ¬(∃x P(x)) ≡ ∀x ¬P(x). - Translating English statements to
predicate logic and vice-versa.
3. Sets and Operations
- Sets, elements, subset (⊆), proper subset (⊂). - Set operations: union ∪, intersection ∩, difference \,
complement. - Power set P(A), cardinality |A|. - Venn diagrams, inclusion-exclusion principle for two and
three sets. - Indexed sets and Cartesian product A×B.
4. Methods of Proof
- Direct proof, proof by contrapositive, proof by contradiction. - Mathematical induction (weak/ordinary
induction): base case, inductive step. - Strong induction. - Proof techniques for inequalities and divisibility.
Practice Problems (Unit I):
1. Prove: ¬(p ∧ q) ≡ (¬p ∨ ¬q) (De Morgan). 2. Translate: 'Every student in the class passed the exam' into
predicate logic. 3. Using induction prove that 1 + 2 + ... + n = n(n+1)/2.
Unit II — Relations, Functions & Algebraic Structures
1. Relations
- A relation R on set A is a subset of A×A. - Properties: reflexive, symmetric, antisymmetric, transitive. -
Equivalence relations and equivalence classes; partition induced by an equivalence relation. - Partial
orders (posets), Hasse diagrams, maximal/minimal elements, least/greatest elements.
Example — Equivalence relation:
On integers, define a ~ b if a ≡ b (mod n). Show reflexive, symmetric, transitive and describe
equivalence classes.
2. Functions
- Function f: A → B; injective (one-to-one), surjective (onto), bijective. - Composition of functions, inverse
functions. - Countability: finite, countably infinite (e.g., integers), uncountable (e.g., real numbers). -
Pigeonhole principle and simple applications.
3. Boolean Algebra & Binary Relations (short)
- Boolean algebra: algebraic structure with operations ∧, ∨, ¬ satisfying axioms. - Application: logic
simplification, switching circuits. - Basics of binary relations used in computer science.
Practice Problems (Unit II):
1. Let R be relation on {1,2,3,4} with pairs ... (construct examples to test properties). 2. Prove: If f■g is
injective then g is injective. 3. Show that the set of rational numbers is countable.
Unit III — Counting, Recurrence Relations & Generating Functions
1. Basics of Counting
- Rule of sum and product, permutations and combinations. - Permutations with repetition, combinations
with repetition. - Binomial theorem: (x+y)^n and binomial coefficients C(n,k). - Multinomial coefficients,
stars-and-bars method.
2. Advanced Counting Principles
- Inclusion-Exclusion principle (general form). - Pigeonhole principle (simple and generalized). -
Applications: derangements, counting onto functions.
3. Recurrence Relations
- Linear recurrence relations with constant coefficients. - Homogeneous vs non-homogeneous;
characteristic equation method. - Examples: Fibonacci sequence, solving a_n = 3a_{n-1} - 2a_{n-2}, etc. -
Generating functions as a tool to solve recurrences.
Example — Fibonacci via characteristic equation:
F_n = F_{n-1} + F_{n-2} with F_0=0, F_1=1. Characteristic equation r^2 = r + 1 → r = (1±√5)/2. General
solution and constants fit initial conditions.
Practice Problems (Unit III):
1. How many 6-letter strings can be formed from English alphabet with at least one vowel? 2. Solve
recurrence: a_n = 4a_{n-1} - 4a_{n-2}, a_0=1, a_1=4. 3. Use inclusion-exclusion to count permutations
with no fixed points (derangements).
Unit IV — Graph Theory & Trees
1. Graphs: Definitions & Types
- Graph G = (V, E): vertices V, edges E. Simple graphs, multigraphs, directed graphs. - Degree of vertex,
handshake lemma (sum of degrees = 2|E|). - Paths, cycles, connectedness, components. - Special
graphs: complete graph K_n, complete bipartite K_{m,n}, complement graph.
2. Trees
- Tree: connected acyclic graph. Equivalent properties: |E| = |V|-1 for connected tree, unique path between
vertices. - Rooted trees, binary trees, spanning trees (Kruskal's and Prim's algorithms for minimum
spanning tree — brief idea). - Applications: expression trees, searching, network design.
3. Eulerian and Hamiltonian
- Eulerian trail/circuit: uses every edge exactly once; condition (for undirected connected graphs) — all
vertices have even degree for Eulerian circuit; exactly 0 or 2 vertices of odd degree for Eulerian trail. -
Hamiltonian path/cycle: visits each vertex exactly once. No simple necessary-and-sufficient condition, but
Dirac's and Ore's theorems give sufficient conditions.
4. Planarity and Graph Coloring (overview)
- Planar graphs, Euler's formula for connected planar graphs: |V| - |E| + |F| = 2. - Graph coloring, chromatic
number, applications to scheduling.
Practice Problems (Unit IV):
1. Prove handshake lemma and use it to show that the number of vertices of odd degree is even. 2. Find
all spanning trees of a small graph (example). 3. Determine if K_{3,3} is planar (use Kuratowski's theorem
idea).
Quick Reference — Formulas & Techniques
- Inclusion-Exclusion (two sets): |A∪B| = |A| + |B| - |A∩B|. - Binomial coefficient: C(n,k) = n!/(k!(n-k)!). -
Sum of first n integers: n(n+1)/2. - Geometric sum: 1 + r + r^2 + ... + r^n = (r^{n+1}-1)/(r-1) (r≠1). -
Characteristic equation routine for linear recurrences.
Study plan suggestion (how to use this PDF):
1. Read one unit per 2–4 days, focus on definitions and theorems. 2. Solve the practice problems at end of
each unit. 3. Try past year question papers of your college for applied practice. 4. Ask me to explain any
theorem step-by-step or to solve a particular problem — I can provide worked solutions.
Prepared by: ChatGPT — Compact discrete mathematics notes. If you want more solved examples,
flashcards, or video-style step explanations, tell me which unit to start with.