Discrete Mathematics

The language of proof, and the mathematics computing is built on

About this course

Proof technique, logic and the discrete structures — counting, number theory, recurrences and graphs — that underpin computer science.

What you will be able to do

  • Read and write rigorous proofs, including by induction and contradiction
  • Use sets, relations and functions precisely, including notions of infinity
  • Count configurations with the standard combinatorial tools
  • Apply elementary number theory and solve recurrences
  • Model problems with graphs and reason about their properties

What this course covers

  • Divisibility and the Divides Relation
  • Primes, the Sieve of Eratosthenes, and Unique Factorization
  • Greatest Common Divisor and Euclid's Algorithm
  • Bézout's Identity and Modular Inverses via Extended Euclid
  • Modular Arithmetic and Congruence
  • RSA Public-Key Cryptography
  • Number Theory as the Foundation of Cryptography
  • Product Rule and Sum Rule
  • Factorials and Permutations
  • Combinations (N Choose R)
  • Binomial Theorem and Pascal's Triangle
  • Counting as Engine of Computing and Probability
  • Relations as sets of ordered pairs
  • Four properties of a relation
  • Equivalence relations and partitions
  • Partial orders and incomparability
  • Hasse diagrams
  • Proof that congruence mod 3 is an equivalence relation
  • Graph basics: vertices, edges, and types
  • Handshake lemma and its corollary
  • Walks, paths, cycles, and connected components
  • Breadth-first and depth-first search
  • Euler circuits vs. Hamilton circuits
  • Trees: connected acyclic graphs
  • Graph Optimization: Local Rules, Global Optima
  • Graph Coloring and Chromatic Number
  • Planarity and Euler's Formula
  • Non-Planarity of K₅ and K₃,₃ via Euler's Corollary
  • Minimum Spanning Trees: Kruskal and Prim
  • Matchings and Hall's Marriage Theorem
  • Graph Optimization as a Unifying Theme and Course Clause
  • Functions: domain, codomain, image, and definition
  • Injective, surjective, and bijective functions
  • Cardinality and comparing infinite set sizes via bijection
  • Countable infinity and listable sets
  • Cantor's diagonal argument: the reals are uncountable
  • Implications for computability: programs vs. computable functions
  • Why the Sum Rule Needs Extending
  • Inclusion-Exclusion Principle
  • Inclusion-Exclusion in Action: Divisibility and Derangements
  • Pigeonhole Principle
  • Combinatorial and Bijective Proofs
  • Applications to Computing and Probability
  • Lecture Synthesis and Capstone Verification
  • Overview of Discrete Mathematics
  • Propositions
  • Logical Connectives and Truth Tables
  • The Conditional (If-Then)
  • Logical Equivalence and De Morgan's Laws
  • Course Roadmap and the 'Spine' of Discrete Mathematics
  • Four bridges: pure math to computation
  • Logic becomes circuits
  • Counting becomes complexity: P, NP, and P vs NP
  • Graphs become networks
  • Number theory becomes cryptography: RSA
  • Discrete mathematics as the computational universe
  • Limits of propositional logic and motivation
  • Predicates
  • Universal and existential quantifiers
  • Nested quantifiers and order dependence
  • Rules of inference
  • Socrates syllogism as a complete proof
  • Sample Spaces, Events, and Probability Axioms
  • Conditional Probability and Bayes' Theorem
  • The Medical Test Problem (Base-Rate Effect)
  • Random Variables and Expected Value
  • The Binomial Distribution
  • Connections to Computing and Applications
  • Lecture Summary and Course Spine (Clause Ten)
  • What a proof is and why it gives certainty
  • Direct proof
  • Contrapositive proof
  • Why examples cannot prove a universal claim
  • Proof by contradiction
  • Proof hygiene and the full toolkit summary
  • The problem: proving claims about all natural numbers
  • The principle of mathematical induction
  • The two ingredients: base case, inductive step, and inductive hypothesis
  • Worked induction: the sum formula
  • Strong induction
  • Well-ordering principle and induction traps

Syllabus

  1. Proof and the Language of Mathematics

    1. L2 · Logic - The Language of Proof
    2. L3 · Predicates and Inference
    3. L4 · How to Prove It
    4. L5 · Mathematical Induction

  2. Relations, Functions and Infinity

    1. L6 · Relations and Order
    2. L7 · Functions and Infinity

  3. Counting and Probability

    1. L8 · Counting
    2. L9 · Advanced Counting
    3. L10 · Discrete Probability

  4. Number Theory and Recurrences

    1. L11 · Number Theory

  5. Graphs and Synthesis

    1. L13 · Graphs
    2. L14 · Graph Theory II
    3. L15 · The Discrete Universe