1. Sets, Relations, Functions & Propositional Logic
A relation R on a set A is reflexive if (a,a) ∈ R for every a ∈ A, symmetric if (a,b) ∈ R implies (b,a) ∈ R, and transitive if (a,b) ∈ R and (b,c) ∈ R imply (a,c) ∈ R. A relation that is all three is an equivalence relation (partitions A into disjoint equivalence classes); a relation that is reflexive, antisymmetric and transitive is a partial order. Functions are a special case of relations where every input maps to exactly one output — injective (one-to-one), surjective (onto) and bijective (both) are the standard classifications.
Propositional logic works with statements combined via AND (∧), OR (∨), NOT (¬), implication (→) and biconditional (↔). An implication p→q is false only when p is true and q is false — this single truth-table fact resolves most implication-based questions. A statement true under every possible assignment of its variables is a tautology; one always false is a contradiction.
p q p -> q
T T T
T F F <- only case where implication is FALSE
F T T
F F T
A common trap: "if it rains, I carry an umbrella" is NOT falsified
by carrying an umbrella when it doesn't rain (F,T row is still TRUE).Equivalence relations reappear directly in DBMS (functional dependency closures) and in automata theory (Myhill-Nerode equivalence classes) — this isn't standalone math, it's infrastructure for Weeks 13 and 15.
2. Graph Theory, Combinatorics & Recurrence Relations
A graph G = (V, E) consists of vertices and edges. Key terms: degree of a vertex (number of incident edges); a graph is connected if there's a path between every pair of vertices; a tree is a connected acyclic graph with exactly |V|-1 edges; Eulerian path/circuit visits every edge exactly once (exists iff exactly 0 or 2 vertices have odd degree); Hamiltonian path/circuit visits every vertex exactly once (no simple general criterion — NP-complete to decide in general, covered again in Week 12).
Combinatorics questions typically use permutations (nPr = n!/(n-r)!, order matters) and combinations (nCr = n!/(r!(n-r)!), order doesn't matter), plus the pigeonhole principle (if n items go into m < n boxes, some box gets more than one item). Recurrence relations (e.g. T(n) = 2T(n-1) + 1) are solved by substitution/unrolling or the characteristic-equation method for linear recurrences with constant coefficients.
3. Group Theory, Boolean Algebra & Linear Programming
A group is a set with a binary operation satisfying closure, associativity, an identity element, and every element having an inverse — abelian if the operation is also commutative. A lattice is a partially ordered set where every pair of elements has both a least upper bound (join) and a greatest lower bound (meet). Boolean algebra is a special lattice satisfying distributive and complement laws, and it directly underlies digital circuit design — De Morgan's laws (¬(A∧B) = ¬A ∨ ¬B, and its dual) are the single most-tested identity.
Linear programming (LP) optimizes a linear objective function subject to linear constraints — the syllabus expects familiarity with formulating a small LP problem and solving it graphically for two variables (plotting the feasible region as the intersection of half-planes and evaluating the objective at each corner point, since an optimal solution always occurs at a vertex of the feasible region).
For any bounded linear program, the optimum always occurs at a vertex (corner point) of the feasible region — you never need to check interior points, only the corners, which is what makes graphical LP solvable by hand for two-variable problems.
4. Hands-on Exercise
Classify relations and solve a 2-variable LP by hand
Discrete math is best cemented by working small, complete examples rather than reading definitions passively.
Part 1 — Relations:
- Define R on {1,2,3,4} as (a,b) ∈ R if a divides b. List all pairs in R and check whether R is reflexive, symmetric and transitive.
- State whether R is a partial order, and if so, draw its Hasse diagram.
Part 2 — Linear programming:
- Maximise Z = 3x + 5y subject to x + y ≤ 4, x ≤ 3, x,y ≥ 0.
- Plot the feasible region, identify all corner points, and evaluate Z at each to find the optimum.
- State the optimal (x, y) and the maximum value of Z.
Always test reflexive, then symmetric, then transitive, in that order and exhaustively over every pair — skipping a single pair is the most common source of a wrong classification on this topic.
5. Exam-Style Practice (UGC NET Pattern)
Five NTA-pattern questions covering relations, logic, graphs and Boolean algebra.
Q1
A relation R on a set is reflexive, symmetric AND transitive. What is R called, and what structure does it impose on the set?
A) A partial order; it creates a total ranking
B) An equivalence relation; it partitions the set into disjoint classes
C) A function; it maps each element to one output
D) A lattice; it defines joins and meets
A relation R on a set is reflexive, symmetric AND transitive. What is R called, and what structure does it impose on the set?
A) A partial order; it creates a total ranking
B) An equivalence relation; it partitions the set into disjoint classes
C) A function; it maps each element to one output
D) A lattice; it defines joins and meets
Correct answer: B) An equivalence relation; it partitions the set into disjoint classes. A relation satisfying all three properties (reflexive, symmetric, transitive) is by definition an equivalence relation, and every equivalence relation partitions its set into disjoint equivalence classes.
Q2
For which combination of truth values is the implication p → q false?
A) p true, q true
B) p true, q false
C) p false, q true
D) p false, q false
For which combination of truth values is the implication p → q false?
A) p true, q true
B) p true, q false
C) p false, q true
D) p false, q false
Correct answer: B) p true, q false. An implication p → q is false in exactly one case: when the antecedent p is true but the consequent q is false. In all other combinations it is true.
Q3
A connected graph has an Eulerian circuit (a closed walk using every edge exactly once) if and only if:
A) Every vertex has even degree
B) Exactly two vertices have odd degree
C) The graph is a tree
D) The graph has no cycles
A connected graph has an Eulerian circuit (a closed walk using every edge exactly once) if and only if:
A) Every vertex has even degree
B) Exactly two vertices have odd degree
C) The graph is a tree
D) The graph has no cycles
Correct answer: A) Every vertex has even degree. A connected graph has an Eulerian circuit if and only if every vertex has even degree; exactly two odd-degree vertices gives an Eulerian path (not a closed circuit) instead.
Q4
Which of the following is the correct De Morgan's law dual for ¬(A ∨ B)?
A) ¬A ∨ ¬B
B) ¬A ∧ ¬B
C) A ∧ B
D) A ∨ B
Which of the following is the correct De Morgan's law dual for ¬(A ∨ B)?
A) ¬A ∨ ¬B
B) ¬A ∧ ¬B
C) A ∧ B
D) A ∨ B
Correct answer: B) ¬A ∧ ¬B. De Morgan's laws state ¬(A ∧ B) = ¬A ∨ ¬B and ¬(A ∨ B) = ¬A ∧ ¬B — the negation of an OR becomes an AND of the negations.
Q5
In a bounded, two-variable linear programming problem, where does the optimal solution always occur?
A) At the centroid of the feasible region
B) At a vertex (corner point) of the feasible region
C) At the midpoint of the longest constraint edge
D) It can occur at any interior point equally
In a bounded, two-variable linear programming problem, where does the optimal solution always occur?
A) At the centroid of the feasible region
B) At a vertex (corner point) of the feasible region
C) At the midpoint of the longest constraint edge
D) It can occur at any interior point equally
Correct answer: B) At a vertex (corner point) of the feasible region. For a bounded linear program, the optimal value of a linear objective function always occurs at a vertex of the feasible region — this is why graphical LP only requires evaluating corner points.