Discrete Mathematics

A rigorous bridge from formula syntax to valuations, first-order structures, semantic consequence, and formal derivation—with countermodels and scope discipline as the main tools for avoiding false reasoning.

How finite syntax becomes arithmetic, how the diagonal lemma produces a sentence that talks about its own provability, and exactly what Gödel's two incompleteness theorems do—and do not—say.

A typed working language for discrete structures: set operations, Cartesian products, relations, total and partial functions, images, composition, inverses, and finite-path closures.

How equivalence relations collapse interchangeable representations into quotient objects, while partial orders preserve distinction and expose dependency, bounds, lattices, and linear extensions.

A derivation-first toolkit for finite counting: sum, product, quotient and bijection principles; sequences, injections, permutations, cycles, combinations, multisets, and stars-and-bars edge cases.

How one abstract graph becomes an edge list, adjacency matrix, adjacency map, or compressed sparse row structure—and how each choice determines memory, query, mutation, and algorithm costs.

Breadth-first and depth-first search as precise state machines: how FIFO creates shortest-edge layers, how a suspended stack creates nested DFS intervals, and which invariants make their many applications correct.

Depth-first decompositions that expose directed mutual reachability and undirected single-point failures: strongly connected components, the condensation DAG, bridges, articulation points, and edge- and vertex-biconnected structure.

Shortest paths as one relaxation invariant expressed through BFS, DAG order, Dijkstra, Bellman–Ford, Floyd–Warshall, and Johnson—with precise weight preconditions and negative-cycle semantics.

Why arithmetic mod a composite breaks division, how GF(p) and GF(2^n) fix it, and why GF(2^8) turns out to be the substrate under AES, Reed-Solomon, CRCs and erasure coding.

A mechanism-first account of regular languages through DFA and NFA state invariants, subset construction, regular-expression algebra, derivatives, Myhill–Nerode equivalence, minimization, closure, and decision procedures.

A rigorous guide to grammars as generative rewrite systems: derivations and parse trees, ambiguity, the Chomsky hierarchy, right-linear grammar–automaton equivalence, recursive structure, and the differences among BNF, EBNF, and ABNF.

A precise treatment of finite-state input/output behavior: Mealy and Moore timing, trace-aware conversion, behavioral equivalence and minimization, sequential and subsequential string transducers, relational boundaries, and composition.

A proof-driven guide to combining and factoring finite-state systems: synchronous products and Boolean languages, output-machine products, cascade and FST composition, reachable-state growth, behavioral preservation targets, projection-based factorization, and the Krohn–Rhodes horizon.

A rigorous working model of weighted place/transition nets: enabling and firing, true concurrency and conflict, reachability and coverability, behavioral properties, incidence matrices, invariants, structural certificates, extension boundaries, and a diagnostic workflow.

A deep guide to Turing-machine mechanics, programs as data, the exact meaning and proof obligations of Turing completeness, the unbounded-resource idealization, and the undecidability that universality brings.

A deep account of primitive and partial recursive functions, unbounded search, computably enumerable sets, universal computation, and why Turing machines, lambda calculus, and other effective models compute the same class of functions.

How polynomial-time reductions transfer difficulty, how Cook–Levin turns bounded computation into SAT, how to build and audit NP-completeness proofs, and which claims hardness results do not justify.