Calculus describes continuous change; this subject describes things you can count and list, which is what computers actually work with. It is also known as discrete mathematics. Logic is how conditions work in code, sets and relations are how databases work, counting is how you estimate cost, and graphs are how networks and dependencies are modelled. This article revisits the five units of the JNTUK course.
Unit 1: Mathematical logic
Propositions and connectives
A proposition is a statement that is true or false. Connectives build compound statements.
| Connective | Symbol | Programming equivalent |
|---|---|---|
| Negation | ¬p | !p |
| Conjunction | p ∧ q | p && q |
| Disjunction | p ∨ q | p || q |
| Implication | p → q | !p || q |
| Biconditional | p ↔ q | p == q |
The implication p → q is false only when p is true and q is false. Its contrapositive ¬q → ¬p is equivalent; its converse q → p is not.
Equivalences and normal forms
A tautology is always true, a contradiction always false. Key laws: De Morgan’s (¬(p ∧ q) ≡ ¬p ∨ ¬q), distributive, absorption and double negation. Every formula can be written in conjunctive normal form (CNF) or disjunctive normal form (DNF), which is how SAT solvers and logic minimizers work.
Predicate logic and proofs
Predicates add variables and quantifiers: ∀x (for all) and ∃x (there exists). Negation swaps them: ¬∀x P(x) ≡ ∃x ¬P(x).
| Proof method | Idea |
|---|---|
| Direct | Assume p, derive q |
| Contrapositive | Prove ¬q → ¬p instead |
| Contradiction | Assume the opposite and reach an absurdity |
| Induction | Prove the base case, then show k implies k + 1 |
| Rules of inference | Modus ponens: from p and p → q, conclude q |
Today: every
ifcondition is propositional logic; De Morgan’s laws are used to simplify conditions and filters. Prolog and rule engines work on predicates. Induction is how you prove that a loop or a recursive function is correct.
Unit 2: Sets, relations and functions
Sets
A set is an unordered collection of distinct elements. Operations: union, intersection, difference, complement and power set (the set of all subsets; a set of n elements has 2ⁿ subsets). The inclusion-exclusion principle: |A ∪ B| = |A| + |B| − |A ∩ B|. A multiset allows repeats.
Relations
A relation R on a set is a set of ordered pairs. Its properties:
| Property | Meaning |
|---|---|
| Reflexive | Every element relates to itself |
| Symmetric | If aRb then bRa |
| Antisymmetric | If aRb and bRa then a = b |
| Transitive | If aRb and bRc then aRc |
| Type | Properties | Example |
|---|---|---|
| Equivalence relation | Reflexive, symmetric, transitive | “Same remainder mod 5”; splits a set into equivalence classes |
| Partial order | Reflexive, antisymmetric, transitive | “Divides”, “is a subset of” |
A partial order is drawn as a Hasse diagram. A lattice is a partial order where every pair has a least upper bound and a greatest lower bound. Closures add the fewest pairs to gain a property; the transitive closure is found by Warshall’s algorithm.
Functions
A function assigns each input exactly one output.
| Type | Meaning |
|---|---|
| Injective (one-to-one) | Different inputs give different outputs |
| Surjective (onto) | Every element of the codomain is hit |
| Bijective | Both; has an inverse |
The pigeonhole principle: placing n + 1 items into n boxes puts at least two in one box. It shows that any hash function must have collisions when keys outnumber slots.
Today: a database table is a relation, and a join composes relations. Equivalence classes are how union-find groups items, and a primary key is an injective function. Partial orders model dependencies (build order, package versions).
Unit 3: Algebraic structures and number theory
Algebraic structures
| Structure | Requirements | Example |
|---|---|---|
| Semigroup | Closed and associative operation | Strings with concatenation |
| Monoid | Semigroup with an identity | Integers with addition (identity 0) |
| Group | Monoid where every element has an inverse | Integers with addition |
| Abelian group | A group where the order does not matter | Integers with addition |
Subgroups, cosets and Lagrange’s theorem (the order of a subgroup divides the order of the group) are part of the syllabus. Rings and fields add a second operation; Boolean algebra is the algebra of logic gates.
Number theory
- Divisibility and gcd: Euclid’s algorithm finds gcd(a, b) by repeated remainders.
- Modular arithmetic: a ≡ b (mod n) means n divides a − b. Fermat’s little theorem and Euler’s theorem give shortcuts for powers.
- Prime numbers and the fundamental theorem of arithmetic: every integer is a unique product of primes.
Today: public-key cryptography (RSA, Diffie-Hellman, elliptic curves) rests on modular arithmetic and groups. Checksums, hash functions and error-correcting codes use finite fields. Associativity is also the reason map-reduce can split work across machines.
Unit 4: Combinatorics and recurrence relations
Counting
| Rule | Meaning |
|---|---|
| Sum rule | If tasks are alternatives, add the ways |
| Product rule | If tasks are done one after another, multiply the ways |
| Permutations | Ordered arrangements: P(n, r) = n! / (n − r)! |
| Combinations | Unordered selections: C(n, r) = n! / (r! (n − r)!) |
The binomial theorem expands (x + y)ⁿ with coefficients C(n, k), and Pascal’s triangle lists them. Permutations with repeated items and distributing objects into boxes use variants of the same formulas. The principle of inclusion and exclusion counts the union of several overlapping sets.
Recurrence relations
A recurrence relation defines a sequence in terms of earlier terms, such as the Fibonacci numbers F(n) = F(n − 1) + F(n − 2).
| Type | Solution method |
|---|---|
| Linear homogeneous with constant coefficients | Solve the characteristic equation; the roots give the general form |
| Non-homogeneous | General solution plus a particular solution |
| Generating functions | Encode a sequence as a power series and solve algebraically |
Example: aₙ = 2aₙ₋₁ with a₀ = 1 gives aₙ = 2ⁿ. The recurrence T(n) = 2T(n/2) + n, which describes merge sort, solves to n log n.
Today: counting tells you whether brute force is feasible: there are n! orders of n tasks and 2ⁿ subsets, which explains why some problems become impossible at modest n. Recurrences are how you analyse the running time of any recursive algorithm.
Unit 5: Graph theory
A graph G = (V, E) has vertices and edges. It can be directed or undirected, and weighted or not.
Basic ideas
| Concept | Meaning |
|---|---|
| Degree | Number of edges at a vertex. The sum of all degrees is twice the number of edges (the handshaking lemma) |
| Path, cycle, connected | A route; a closed route; every vertex reachable from every other |
| Tree | A connected graph with no cycles; n vertices and n − 1 edges |
| Complete graph Kₙ | Every pair of vertices joined |
| Bipartite | Vertices split into two groups with edges only between groups |
| Planar | Can be drawn without crossing edges (Euler: V − E + F = 2) |
Graphs are stored as an adjacency matrix (fast edge lookup, O(V²) space) or an adjacency list (compact for sparse graphs).
Special paths and problems
| Topic | Idea |
|---|---|
| Euler path or circuit | Uses every edge once. Exists when all degrees are even (circuit) or exactly two are odd (path) |
| Hamiltonian cycle | Visits every vertex once. No simple test; NP-complete |
| Graph colouring | Colour vertices so adjacent ones differ; the chromatic number is the fewest colours (four colours suffice for any planar map) |
| Spanning tree | A tree connecting all vertices; minimum spanning trees by Prim and Kruskal |
| Isomorphism | Two graphs with the same structure under relabelling |
| Traversal | BFS and DFS |
Today: social networks, road maps, the internet, dependency trees and Kubernetes object relationships are all graphs. Colouring models register allocation in compilers and timetable scheduling. Spanning trees are what the spanning tree protocol uses to avoid loops in switched networks.
One-minute recap
| Unit | Key idea | You meet it in |
|---|---|---|
| 1. Logic | Connectives, De Morgan, quantifiers, induction | Conditions, rule engines, correctness proofs |
| 2. Sets, relations, functions | Equivalence, partial order, injective and bijective maps | Databases, union-find, dependency order |
| 3. Algebraic structures, number theory | Groups, modular arithmetic, gcd | Cryptography, hashing, checksums |
| 4. Combinatorics, recurrences | Permutations, combinations, solving recurrences | Complexity analysis, capacity estimates |
| 5. Graph theory | Paths, trees, colouring, planarity | Networks, schedulers, compilers |
Next in Engineering Revisited: Probability & Statistics.
Written by Claude, Anthropic’s AI assistant, as part of Engineering Revisited, a quick refresher of the B.Tech subjects one at a time.