Discrete Mathematics: A Practical Guide to Logic, Graphs, and Algorithms

Formal logic replaces ambiguous language with statements whose consequences can be checked. Propositional logic combines propositions using AND, OR, NOT, and implication. Suppose A means “access is granted” and C means “credentials are valid.” The requirement “access is granted only if credentials are valid” becomes A → C. This implication fails only when A is true and C is false. Its contrapositive, ¬C → ¬A, is equivalent; its converse, C → A, is not. Valid credentials might still be insufficient because an account is suspended. Distinguishing necessity from sufficiency prevents a common access-control specification error.

Predicate logic adds variables and quantifiers. “Every request has an assigned server” is ∀r ∃s Assigned(r,s), with requests and servers as the respective domains. It does not mean ∃s ∀r Assigned(r,s), which requires one server assigned to every request. To negate the first statement, reverse the quantifiers and negate the predicate: ∃r ∀s ¬Assigned(r,s). This describes a concrete failure condition: an unassigned request. Practitioners first define domains and predicates, then translate requirements, check small counterexamples, and use truth tables or automated solvers where appropriate. A solver result is meaningful only relative to the model and assumptions supplied.

Mathematical proofs establish claims for every permitted input, rather than only the examples tested. Direct proof follows definitions and established results; contradiction shows that denying a claim creates an inconsistency. Induction handles recursively structured objects and integer-indexed claims. For example, prove 1 + 2 + ... + n = n(n + 1)/2 for n ≥ 1. The base case n = 1 gives 1 = 1. Assuming the formula holds at n = k, adding k + 1 gives k(k + 1)/2 + (k + 1) = (k + 1)(k + 2)/2. This proves the next case, completing the induction.

Algorithm verification uses a similar structure through loop invariants. Consider an algorithm that sets s = 0 and adds array elements from left to right. After processing k elements, the invariant is s = the sum of the first k elements. Initialization establishes it at k = 0; each addition preserves it; termination at k = n yields the desired total. Correctness also requires showing termination, for example because n − k decreases each iteration and remains nonnegative. In software verification, arithmetic assumptions matter: a proof over mathematical integers does not automatically establish correctness for fixed-width integers that can overflow.

Combinatorics begins by identifying whether order matters and whether repetition is allowed. Choosing an unordered committee of three from eight people gives C(8,3) = 8!/(3!5!) = 56 possibilities. Assigning three distinct roles to different people gives 8 × 7 × 6 = 336 because role assignments distinguish outcomes. For a sequence of four symbols chosen independently from ten symbols, repetition allowed, there are 10⁴ possibilities. The multiplication principle applies when every partial choice admits the stated number of continuations; if constraints change that number, partition the problem into cases or use a recurrence.

As a constrained example, count six-bit strings containing exactly two ones with no adjacent ones. There are C(6,2) = 15 ways to choose the one-positions without restrictions. Exactly five choices place them together: positions (1,2) through (5,6). Therefore, 15 − 5 = 10 strings qualify. For larger versions, dynamic programming avoids enumerating every string by tracking the current position, the number of ones placed, and whether the preceding bit was one. Inclusion–exclusion handles overlapping forbidden conditions: |A ∪ B| = |A| + |B| − |A ∩ B|. These methods support test-case planning, capacity analysis, and search-space estimation, although counting configurations alone does not predict their real-world probabilities.

Discrete structures provide models for data and relationships. A relation on a set is a collection of ordered pairs. An equivalence relation is reflexive, symmetric, and transitive; it partitions the set into nonoverlapping equivalence classes. For example, integers are equivalent modulo 5 when their difference is divisible by 5. Every integer belongs to exactly one residue class represented by 0, 1, 2, 3, or 4. Partial orders instead satisfy reflexivity, antisymmetry, and transitivity. Set inclusion is a partial order, but not a total order: neither {a} nor {b} contains the other.

Algebra studies operations and the properties they obey. A group has closure, associativity, an identity, and an inverse for every element. Integers modulo 5 form a group under addition, but all five residues do not form a group under multiplication because zero has no multiplicative inverse. The nonzero residues modulo 5 do form a multiplicative group; for instance, 2 × 3 ≡ 1 mod 5. Residues modulo a positive integer m form a ring under addition and multiplication, and form a field when m is prime. These distinctions determine whether cancellation and division are valid. In implementation, “divide modulo m” must mean multiply by an existing modular inverse, not perform ordinary integer division.

Graph theory models objects as vertices and connections as edges. Before selecting graph algorithms, decide whether edges are directed, whether weights exist, and what those weights represent. Breadth-first search finds paths with the fewest edges in an unweighted graph. Dijkstra’s algorithm finds minimum-total-weight paths when edge weights are nonnegative. For a directed example, let A→B cost 4, A→C cost 1, C→B cost 2, B→D cost 1, and C→D cost 5. Starting at A, tentative distances are B = 4 and C = 1. Processing C improves B to 3 and sets D to 6; processing B then improves D to 4.

The resulting shortest route to D is A→C→B→D, with total cost 4. To recover the route, store a predecessor whenever a distance improves. An adjacency-list representation uses O(V + E) storage, and a standard binary-heap implementation of Dijkstra runs in O((V + E) log V) time. Negative edges invalidate Dijkstra’s greedy finalization argument; Bellman–Ford is an alternative and can detect negative cycles reachable from the source. Different graph questions require different tools: topological sorting schedules dependencies in directed acyclic graphs, while minimum spanning trees connect all vertices of a connected undirected graph at minimum total edge cost. A minimum spanning tree is not generally a shortest-path tree.

Number theory supplies efficient methods for working with integers. Euclid’s algorithm computes the greatest common divisor using gcd(a,b) = gcd(b,a mod b). For 252 and 105, the successive remainders are 42, 21, and 0, so the gcd is 21. The extended algorithm also finds integers x and y such that ax + by = gcd(a,b). This gives a modular inverse whenever gcd(a,m) = 1. For example, 26 = 3 × 7 + 5, 7 = 5 + 2, and 5 = 2 × 2 + 1. Back-substitution gives 1 = 3 × 26 − 11 × 7, so the inverse of 7 modulo 26 is −11 ≡ 15.

Modular exponentiation makes large powers manageable by repeatedly squaring and reducing. To calculate 3¹³ mod 17, use 13 = 8 + 4 + 1. The needed residues are 3² ≡ 9, 3⁴ ≡ 13, and 3⁸ ≡ 16, giving 3¹³ ≡ 16 × 13 × 3 ≡ 12 mod 17. Binary exponentiation uses O(log e) modular multiplications for exponent e, although each multiplication’s cost depends on operand size. Public-key cryptography builds on such arithmetic, but classroom computations are not secure protocols. Practical RSA, for example, also requires secure parameter generation and standardized padding; implementations need protection against timing and other side-channel attacks. Production systems should use vetted cryptographic libraries.

A reliable workflow starts with a precise question and an explicit model. For a routing feature, define vertices, permitted edges, and whether cost measures latency, distance, or money. State assumptions such as nonnegative weights and clarify whether the network can change during computation. Next, choose an algorithm, identify its correctness argument, and estimate time and memory requirements. Finally, implement with deliberate choices about numeric types, unreachable destinations, duplicate edges, and invalid inputs. Mathematical correctness and engineering robustness reinforce each other, but neither substitutes for the other.

Use small examples as executable checks, not as proofs. Compare optimized counting code against exhaustive enumeration on short sequences; compare shortest-path results against hand-calculated graphs; verify an inverse with (a × inverse) mod m = 1. Property-based tests can exercise many generated inputs, while formal reasoning addresses all inputs within stated assumptions. For an intermediate learning path, become comfortable with sets and algebra, then connect logic and proofs to counting, graphs, and modular computation. This is the central value of studying Discrete Mathematics through Erudex’s course focus: learning to justify a model and algorithm, not merely recognize a formula.