Discrete Structures & Optimization

Why this unit matters

Unit 1 is one of the heaviest-weighted units in the UGC NET CS paper. Questions here are almost always analytical, they hand you a formula, a graph, or a logical expression and ask you to compute something. That makes them learnable. A candidate who genuinely understands propositional logic, graph traversal, and the simplex method can reliably pick up 8-12 marks from this unit alone. The concepts also reappear implicitly in Unit 2 (Boolean gates), Unit 4 (relational algebra), and Unit 5 (scheduling as an optimization problem). Treat this unit as infrastructure, not as isolated trivia.

Syllabus map

Every named topic in the official UGC NET CS Code 87 syllabus for Unit 1:

• Mathematical Logic: propositional logic, propositional equivalences, predicate logic, quantifiers (universal, existential), nested quantifiers, rules of inference (modus ponens, modus tollens, hypothetical syllogism, resolution), Normal forms: conjunctive normal form (CNF), disjunctive normal form (DNF), principal normal forms, Sets and Relations: set operations (union, intersection, complement, difference, Cartesian product), Venn diagrams, properties of relations (reflexive, symmetric, antisymmetric, transitive), equivalence relations, equivalence classes, partial orders, Hasse diagrams, lattices, Counting and Discrete Probability: basics of counting, pigeonhole principle, permutations, combinations, binomial theorem, inclusion-exclusion principle, mathematical induction, strong induction, probability axioms, conditional probability, Bayes' theorem, discrete distributions, Group Theory: binary operations, groups, subgroups, cyclic groups, semigroups, monoids, products of groups, quotient groups, isomorphism, homomorphism, automorphism, rings, integral domains, fields, Graph Theory: simple graphs, multigraphs, weighted graphs, paths, circuits, shortest paths (Dijkstra, Bellman-Ford), Eulerian paths and circuits, Hamiltonian paths and circuits, planar graphs, Euler's formula, graph coloring, chromatic number, bipartite graphs, trees, rooted trees, prefix codes, binary trees, tree traversals (preorder, inorder, postorder), spanning trees (Kruskal, Prim), cut sets, connectivity, Boolean Algebra: Boolean functions, truth tables, minterms and maxterms, Karnaugh maps, simplification, NAND/NOR completeness, Optimization: linear programming (LP), mathematical model, graphical solution, simplex method, dual simplex, sensitivity analysis, duality theory; integer programming; transportation model, assignment model (Hungarian method); PERT and CPM, critical path, float/slack, resource levelling

Mathematical Logic

Propositional Logic

A proposition is any statement that is either true or false. The five connectives you must know cold:

• Negation (NOT): changes truth value, Conjunction (AND): true only when both operands are true, Disjunction (OR): false only when both operands are false, Implication (p -> q): false only when p is true and q is false, Biconditional (p <-> q): true when both have the same truth value

Important equivalences to memorise:

• De Morgan's laws: NOT(p AND q) = (NOT p) OR (NOT q), Contrapositive: (p -> q) is logically equivalent to (NOT q -> NOT p), Implication rewrite: (p -> q) is equivalent to (NOT p OR q), Double negation: NOT(NOT p) = p

Predicate Logic and Quantifiers

A predicate is a statement containing a variable, e.g., P(x) = "x is even." Quantifiers bind variables:

• Universal quantifier: "for all x, P(x)" is true only if P(x) holds for every x in the domain, Existential quantifier: "there exists x such that P(x)" is true if at least one x satisfies P(x)

Negation rules for quantifiers (critical for NET):

• NOT(for all x, P(x)) = there exists x such that NOT P(x), NOT(there exists x, P(x)) = for all x, NOT P(x)

Normal Forms

CNF: every clause is a disjunction of literals, and the formula is a conjunction of clauses. DNF: every term is a conjunction of literals, and the formula is a disjunction of terms.

To convert a formula to CNF: apply De Morgan's repeatedly until only atomic negations remain, then distribute AND over OR.

Rules of Inference

Modus ponens: from p and (p -> q), conclude q. Modus tollens: from NOT q and (p -> q), conclude NOT p. Hypothetical syllogism: from (p -> q) and (q -> r), conclude (p -> r). Disjunctive syllogism: from (p OR q) and NOT p, conclude q. Resolution: from (p OR q) and (NOT p OR r), conclude (q OR r). This is the basis of automated theorem proving.

Sets and Relations

Set Operations and Properties

For sets A and B in universe U:

• A union B contains elements in A or B or both, A intersection B contains elements in both A and B, Complement of A contains elements in U but not in A, A minus B = A intersection (complement of B), Cartesian product A x B = all ordered pairs (a, b) with a in A, b in B

Cardinality rule: |A union B| = |A| + |B| - |A intersection B|

Relations and Their Properties

A relation R on set A is a subset of A x A.

• Reflexive: (a, a) is in R for every a in A, Symmetric: if (a, b) is in R then (b, a) is in R, Antisymmetric: if (a, b) and (b, a) are both in R then a = b, Transitive: if (a, b) and (b, c) are in R then (a, c) is in R

Equivalence relation: reflexive + symmetric + transitive. It partitions the set into disjoint equivalence classes.

Partial order: reflexive + antisymmetric + transitive. A set with a partial order is a POSET (partially ordered set). A Hasse diagram omits self-loops and upward-implied edges.

Counting and Discrete Probability

Pigeonhole Principle

If n+1 objects are placed in n boxes, at least one box has at least 2 objects. Generalised: if kn+1 objects go into n boxes, some box has at least k+1 objects.

Example: Among any 13 people, at least 2 share a birth month.

Permutations and Combinations

P(n, r) = n! / (n-r)!, ordered selection of r from n distinct items. C(n, r) = n! / (r! * (n-r)!), unordered selection.

Binomial theorem: (x + y)^n = sum from k=0 to n of C(n,k) * x^k * y^(n-k).

Inclusion-Exclusion Principle

|A1 union A2 union ... union An| = sum of |Ai| - sum of |Ai intersection Aj| + ... + (-1)^(n+1) * |A1 intersection ... intersection An|

Bayes' Theorem

P(A | B) = P(B | A) * P(A) / P(B)

This is used in classification problems (naive Bayes) and appears in NET questions framed as conditional probability puzzles.

Mathematical Induction

Prove a statement P(n) for all n >= base case:

1. Base case: show P(base) is true.
2. Inductive step: assume P(k) is true (inductive hypothesis), then prove P(k+1) is true.

Group Theory

Groups and Subgroups

A group (G, *) satisfies: closure, associativity, identity element, and inverse for every element.

• Abelian (commutative) group: additionally, a * b = b * a for all a, b., Subgroup: a non-empty subset H of G that is itself a group under the same operation., Lagrange's theorem: the order (size) of any subgroup H divides the order of G., Cyclic group: generated by a single element g, i.e., G = {g^0, g^1, g^2, ...}.

A semigroup has closure and associativity only. A monoid adds an identity element. A group adds inverses.

Isomorphism, Homomorphism, Automorphism

A homomorphism f: G -> H satisfies f(a * b) = f(a) * f(b). It preserves structure but need not be one-to-one.

An isomorphism is a bijective homomorphism. Two groups are isomorphic if there is an isomorphism between them, they are structurally identical.

An automorphism is an isomorphism from a group to itself.

Rings, Integral Domains, Fields

A ring (R, +, *) is an abelian group under addition, with multiplication that is associative and distributive over addition.

An integral domain is a commutative ring with no zero divisors: if a * b = 0, then a = 0 or b = 0.

A field is a commutative ring where every non-zero element has a multiplicative inverse. All fields are integral domains, but not vice versa. The set of real numbers is a field; the integers are only an integral domain.

Graph Theory

Basic Definitions and Types

A simple graph has no self-loops and no parallel edges. A multigraph allows parallel edges. A weighted graph assigns a numerical weight to each edge.

Degree of a vertex: number of edges incident to it. The handshaking lemma: sum of all degrees = 2 * (number of edges). This means the number of vertices with odd degree is always even.

Paths, Circuits, and Connectivity

A path visits each vertex at most once. A circuit (cycle) is a closed path. A graph is connected if there is a path between every pair of vertices.

Shortest path algorithms:

• Dijkstra's algorithm: works for non-negative edge weights. Time complexity O((V + E) log V) with a priority queue., Bellman-Ford: handles negative weights. O(VE). Detects negative cycles.

Eulerian and Hamiltonian

Eulerian path: traverses every edge exactly once. A connected graph has an Eulerian path if and only if it has exactly 0 or 2 vertices of odd degree.

Eulerian circuit: Eulerian path that returns to start. Requires every vertex to have even degree.

Hamiltonian path: visits every vertex exactly once. Hamiltonian circuit: returns to start. Unlike Eulerian, no simple polynomial-time algorithm is known, it is NP-complete.

Planar Graphs and Euler's Formula

A planar graph can be drawn in the plane without edge crossings. Euler's formula: V, E + F = 2, where V = vertices, E = edges, F = faces (including the outer face).

For a connected simple planar graph: E <= 3V, 6. For bipartite planar graphs: E <= 2V, 4.

K5 (complete graph on 5 vertices) and K3,3 (complete bipartite) are not planar, Kuratowski's theorem.

Graph Coloring

The chromatic number X(G) is the minimum number of colors needed to color vertices so that no two adjacent vertices share a color.

Four-color theorem: every planar graph has chromatic number at most 4.

Bipartite graphs have chromatic number 1 (empty graph) or 2. A graph is bipartite if and only if it has no odd-length cycle.

Trees and Spanning Trees

A tree is a connected acyclic graph. For a tree with V vertices: E = V, 1, exactly one path between any two vertices.

A rooted tree has one designated root; every edge is directed away from root. In a binary tree each node has at most 2 children.

Prefix codes (Huffman codes): no codeword is a prefix of another. Represented as a binary tree where leaves are symbols.

Spanning tree of a graph G: a subgraph that is a tree and includes all vertices of G. A connected graph with V vertices has a spanning tree with exactly V-1 edges.

Prim's algorithm: greedy, grows the spanning tree one vertex at a time, O(E log V). Kruskal's algorithm: sorts edges by weight, uses union-find, O(E log E).

Boolean Algebra

A Boolean algebra is a set B = {0, 1} with operations AND (+), OR (*), NOT ('), satisfying complement, identity, commutative, distributive, and De Morgan laws.

A Boolean function of n variables can be represented as a truth table with 2^n rows, as a sum of minterms (SOP), or as a product of maxterms (POS).

Karnaugh maps simplify Boolean expressions visually. Group adjacent 1s in groups of 1, 2, 4, 8, 16 (powers of 2). A larger group gives a simpler expression. Wrap around the edges, the map is toroidal.

NAND and NOR are each functionally complete: any Boolean function can be built using only NAND gates, or only NOR gates.

Optimization

Linear Programming

LP maximises or minimises a linear objective function subject to linear inequality constraints.

Standard form: maximise c^T x, subject to Ax <= b, x >= 0.

Graphical method (for 2 variables): plot constraints as half-planes. The feasible region is a convex polygon. The optimal value lies at a corner (vertex) of this polygon.

Simplex method: moves from corner to adjacent corner along improving edges. In practice, exponential in the worst case but polynomial on average. Each iteration: find entering variable (most positive reduced cost), find leaving variable (minimum ratio test), pivot.

Dual simplex: starts with a dual feasible but primal infeasible solution, useful after adding cuts in integer programming.

Sensitivity analysis: studies how the optimal solution changes when objective coefficients or RHS constants are perturbed within a range (the allowable range).

Duality: every LP (primal) has a corresponding dual LP. If the primal has an optimal solution, so does the dual, and their optimal objective values are equal (strong duality).

Integer Programming

When variables must be integers, use branch-and-bound (split feasible region) or cutting planes (add constraints that cut off fractional solutions but not integer ones).

Transportation and Assignment

Transportation problem: minimise cost of shipping goods from m sources to n destinations with supply and demand constraints. Balanced when total supply equals total demand. Initial solution by north-west corner or Vogel's method; optimise with MODI (UV) method.

Assignment problem: n workers, n jobs, minimise total cost. Solved in O(n^3) by the Hungarian algorithm: subtract row and column minima, find a perfect matching in zeros.

PERT and CPM

PERT (Program Evaluation and Review Technique) handles uncertain activity durations: optimistic (to), most likely (tm), pessimistic (tp). Expected duration = (to + 4*tm + tp) / 6. Variance = ((tp, to) / 6)^2.

CPM (Critical Path Method): deterministic durations. The critical path is the longest path from start to finish, it determines the minimum project duration. Activities on the critical path have zero float (slack).

Float = Latest Start, Earliest Start = Latest Finish, Earliest Finish.

Resource levelling: redistribute resources to avoid peaks without extending the project duration.

Worked Examples

Example 1: Propositional Logic, Normal Form

Express (p -> q) AND (q -> r) in CNF.

Step 1: Rewrite implications. (NOT p OR q) AND (NOT q OR r). Step 2: Each clause is already a disjunction of literals. This is CNF. Two clauses: {NOT p, q} and {NOT q, r}.

By resolution on these two clauses (resolving on q): we can derive (NOT p OR r), i.e., p -> r. This confirms the hypothetical syllogism rule.

Example 2: Counting, Inclusion-Exclusion

In a class of 100 students, 60 like math, 45 like CS, and 30 like both. How many like neither?

|Math union CS| = 60 + 45, 30 = 75. Neither = 100, 75 = 25 students.

Example 3: Graph Theory, Critical Analysis

A connected graph G has 7 vertices and 9 edges. Check if it is a tree.

A tree with 7 vertices has exactly 6 edges. This graph has 9 edges, so it is not a tree. It has 9, 6 = 3 extra edges, meaning it has 3 independent cycles (the cyclomatic number, also called the circuit rank, is 3).

Example 4: Shortest Path, Dijkstra's

Graph with vertices A, B, C, D and edges: A-B=4, A-C=2, B-D=5, C-B=1, C-D=8.

Start at A. Distance: A=0, B=inf, C=inf, D=inf. Visit A: update B=4, C=2. Visit C (smallest): update B=min(4, 2+1)=3, D=min(inf, 2+8)=10. Visit B: update D=min(10, 3+5)=8. Visit D: done. Shortest path A to D = 8, via A->C->B->D.

Example 5: LP, Graphical Method

Maximise Z = 3x + 2y subject to: x + y <= 4, x <= 3, y <= 3, x >= 0, y >= 0.

Corner points of feasible region: (0,0), (3,0), (3,1), (1,3), (0,3). Z values: 0, 9, 11, 9, 6. Optimal: x=3, y=1, Z=11.

Quick-Revision Summary

• Implication (p->q) is false only when p is true and q is false., A relation is an equivalence relation if and only if it is reflexive, symmetric, and transitive., Eulerian circuit exists iff every vertex has even degree (connected graph)., Hamiltonian circuit, no polynomial test exists., A tree on V vertices has exactly V-1 edges., Lagrange's theorem: order of subgroup divides order of group., K5 and K3,3 are the smallest non-planar graphs (Kuratowski)., Euler's formula: V, E + F = 2 (connected planar graph)., Critical path has zero float; determines minimum project duration., PERT expected time = (to + 4tm + tp) / 6., Simplex moves along corners of feasible polyhedron., Hungarian algorithm solves assignment in O(n^3).

How to Study This Unit

1. Start with propositional logic, do truth tables by hand for 3-variable formulas until equivalences become instinctive.
2. For graph theory, draw examples: draw K5, a bipartite graph, a spanning tree. Visual understanding beats memorisation.
3. Practice Dijkstra and Kruskal on small examples (5-6 nodes) until you can run them in your head.
4. For LP, solve at least 3 graphical problems from scratch, draw the feasible region, find all corners, evaluate the objective.
5. PERT-CPM questions are formula-heavy but predictable; make a cheat-sheet and drill with previous-year questions.
6. Group theory questions on NET tend to be definition-checking or order calculations, know Lagrange's theorem cold.
7. Boolean algebra: practice K-map simplification for 3-variable and 4-variable maps.
8. Solve the last 10 years of NET CS previous papers for Unit 1 questions, patterns repeat.