⛓ Discrete Math & Number Theory

103 topics

• Statements and Truth Values (Intermediate) – A proposition is true or false, never both.
• Logical Connectives (Intermediate) – AND, OR, NOT, implication and biconditional.
• Truth Tables (Intermediate) – List all truth assignments to evaluate compound statements.
• Tautologies and Contradictions (Advanced) – Always true or always false statements.
• Logical Equivalence (Advanced) – Statements with identical truth tables.
• De Morgan’s Laws (Advanced) – Negation swaps AND and OR.
• Converse and Contrapositive (Advanced) – A conditional equals its contrapositive.
• Quantifiers (Advanced) – “For all” and “there exists”.
• Negating Quantified Statements (Advanced) – Flip the quantifier and negate the predicate.
• Proof by Direct Argument (Advanced) – Derive the conclusion from premises with valid steps.
• Proof by Contrapositive (Advanced) – Prove ¬q → ¬p instead of p → q.
• Proof by Contradiction (Advanced) – Assume the opposite and reach an impossibility.
• Proof by Cases (Advanced) – Split into exhaustive cases.
• Induction Principle (Advanced) – Prove P(1) and P(k)→P(k+1).
• Strong Induction (Expert) – Assume all earlier cases to prove the next.
• Well-Ordering Principle (Expert) – Every nonempty set of positive integers has a least element.
• Sets and Elements (Beginner) – Collections of distinct objects.
• Subsets and Power Sets (Intermediate) – A set with n elements has 2ⁿ subsets.
• Set Operations (Intermediate) – Union, intersection, difference and complement.
• Venn Diagrams (Intermediate) – Pictures of sets and their overlaps.
• Inclusion–Exclusion Principle (Advanced) – Count a union by correcting overlaps.
• Cartesian Products (Intermediate) – All ordered pairs from two sets.
• Relations (Advanced) – Subsets of A×B describing how elements relate.
• Equivalence Relations (Advanced) – Reflexive, symmetric and transitive relations partition a set.
• Partial Orders (Expert) – Reflexive, antisymmetric, transitive relations.
• Injective, Surjective, Bijective (Advanced) – One-to-one, onto and both.
• Cardinality of Sets (Expert) – Comparing sizes of infinite sets.
• Countable and Uncountable Sets (Expert) – ℕ and ℚ are countable; ℝ is not.
• Cantor’s Diagonal Argument (Expert) – Proof that real numbers are uncountable.
• Pigeonhole Principle (Advanced) – If n+1 objects go into n boxes, some box has two.
• Rule of Sum and Product (Intermediate) – Add for “or” choices, multiply for “and” choices.
• Factorials (Intermediate) – Product of integers up to n.
• Permutations with Repetition (Advanced) – Arrange objects when some are identical.
• Circular Permutations (Advanced) – Arrangements around a circle.
• Combinations with Repetition (Expert) – Stars and bars.
• Binomial Coefficients (Advanced) – Counts of k-subsets; entries of Pascal’s triangle.
• Binomial Theorem (Discrete) (Advanced) – Expansion of (x+y)ⁿ.
• Multinomial Coefficients (Expert) – Ways to split objects into labelled groups.
• Derangements (Expert) – Permutations with no fixed points.
• Catalan Numbers (Expert) – Count balanced parentheses, trees and paths.
• Stirling Numbers (Expert) – Count partitions and cycles.
• Partitions of Integers (Expert) – Ways to write n as a sum of positive integers.
• Generating Functions (Expert) – Encode sequences as power series.
• Recurrence Relations (Advanced) – Define sequences by earlier terms.
• Solving Linear Recurrences (Expert) – Use the characteristic equation.
• Closed Form of Fibonacci (Binet) (Expert) – Explicit formula using the golden ratio.
• Tower of Hanoi (Advanced) – Minimum moves for n disks.
• Divide-and-Conquer Recurrences (Expert) – Master theorem for T(n) = aT(n/b) + f(n).
• Graphs: Basics (Intermediate) – Vertices connected by edges.
• Degree and Handshake Lemma (Advanced) – Sum of degrees is twice the number of edges.
• Types of Graphs (Advanced) – Simple, directed, weighted, complete, bipartite.
• Paths, Cycles and Connectivity (Advanced) – Walks through graphs and connected components.
• Euler Paths and Circuits (Advanced) – Traverse every edge once if degrees are even.
• Hamiltonian Paths (Expert) – Visit every vertex exactly once.
• Trees (Advanced) – Connected graphs without cycles; n vertices have n−1 edges.
• Spanning Trees (Advanced) – Subtrees that connect all vertices.
• Minimum Spanning Trees (Expert) – Connect all vertices with least total weight.
• Shortest Paths (Dijkstra) (Expert) – Find least-cost routes from a source.
• Breadth- and Depth-First Search (Advanced) – Systematic graph traversal.
• Planar Graphs (Expert) – Graphs drawable without crossing edges.
• Graph Colouring (Expert) – Assign colours so adjacent vertices differ.
• Four Colour Theorem (Expert) – Every planar map is 4-colourable.
• Bipartite Graphs and Matching (Expert) – Pair vertices of two sets using edges.
• Network Flow and Max-Flow Min-Cut (Expert) – Maximum flow equals minimum cut capacity.
• Adjacency Matrices (Advanced) – Represent graphs as matrices.
• Divisibility (Intermediate) – a | b if b = ak for some integer k.
• Division Algorithm (Intermediate) – Every integer has a unique quotient and remainder.
• Fundamental Theorem of Arithmetic (Advanced) – Unique factorisation into primes.
• Infinitude of Primes (Advanced) – Euclid’s proof that there are infinitely many primes.
• Sieve of Eratosthenes (Intermediate) – List primes by crossing out multiples.
• Prime Number Theorem (Expert) – Approximately n/ln n primes below n.
• GCD and LCM (Advanced) – Greatest common divisor and least common multiple.
• Extended Euclidean Algorithm (Expert) – Find x, y with ax + by = gcd(a,b).
• Bézout’s Identity (Expert) – gcd is an integer combination of a and b.
• Linear Diophantine Equations (Expert) – Integer solutions of ax + by = c.
• Congruences (Advanced) – a ≡ b (mod n) when n divides a−b.
• Modular Arithmetic (Advanced) – Addition and multiplication respect congruence.
• Modular Inverses (Expert) – a⁻¹ mod n exists iff gcd(a,n)=1.
• Linear Congruences (Expert) – Solve ax ≡ b (mod n).
• Chinese Remainder Theorem (Expert) – Solve systems of congruences with coprime moduli.
• Fermat’s Little Theorem (Expert) – For prime p, aᵖ ≡ a mod p.
• Euler’s Totient Function (Expert) – Count integers coprime to n.
• Euler’s Theorem (Expert) – a^φ(n) ≡ 1 mod n for coprime a, n.
• Wilson’s Theorem (Expert) – p is prime iff (p−1)! ≡ −1 mod p.
• Quadratic Residues (Expert) – Squares modulo a prime.
• Legendre Symbol and Reciprocity (Expert) – Test residues and relate primes.
• Primitive Roots (Expert) – Generators of the multiplicative group modulo p.
• Multiplicative Functions (Expert) – Functions like σ, τ, φ, μ with f(mn)=f(m)f(n) for coprimes.
• Divisor Functions (Expert) – Count and sum divisors.
• Perfect and Amicable Numbers (Expert) – Numbers linked to their divisor sums.
• Mersenne Primes (Expert) – Primes of the form 2ᵖ−1.
• Pythagorean Triples Parametrisation (Expert) – Generate all primitive triples.
• Pell’s Equation (Expert) – Integer solutions of x² − Dy² = 1.
• Fermat’s Last Theorem (Expert) – No integer solutions of xⁿ+yⁿ=zⁿ for n>2.
• Goldbach and Twin Prime Conjectures (Expert) – Famous unsolved problems about primes.
• RSA Cryptography (Expert) – Public-key encryption using prime factorisation difficulty.
• Diffie–Hellman Key Exchange (Expert) – Shared secret from public values.
• Hash Functions and Checksums (Advanced) – Map data to short fixed-size values; check digits use modular arithmetic.
• Boolean Algebra (Advanced) – Algebra of true/false values.
• Logic Gates and Circuits (Advanced) – AND, OR, NOT gates implement Boolean functions.
• Finite Automata (Expert) – Machines recognising regular languages.
• Algorithm Complexity (Big-O) (Expert) – How running time grows with input size.
• Sorting Algorithm Analysis (Expert) – Compare comparison-based sorts.