Skip to content
Wyatt's Notes — University

Discrete Mathematics

Discrete Mathematics

Discrete mathematics provides the mathematical foundations required throughout computer science. Unlike continuous mathematics, which studies quantities that vary smoothly, discrete mathematics concerns structures that are distinct and separated, such as integers, graphs, and logical propositions. Mastery of these concepts is essential for reasoning about algorithms, data structures, and computational systems.

Key Concepts

The major topics include propositional and predicate logic, which formalise reasoning; set theory, relations, and functions, which describe mathematical structures; proof techniques such as induction and contradiction, which establish the validity of propositions; combinatorics, which counts and analyses discrete configurations; and graph theory, which models pairwise relationships between objects.

Contents

  1. Propositional and Predicate Logic
  2. Sets, Relations, and Functions
  3. Proof Techniques
  4. Combinatorics
  5. Graph Theory
  6. Recurrence Relations
  7. Problem Set

Overview

University-level discrete mathematics notes covering logic, sets, proofs, combinatorics, and graphs.

Topics Covered

  • Logic and Proofs: Propositional logic, predicate logic, proof techniques
  • Sets and Relations: Set operations, relations, functions, equivalence relations
  • Combinatorics: Counting principles, permutations, combinations, generating functions
  • Graph Theory: Paths, cycles, trees, planarity, graph colouring

Prerequisites

  • Basic mathematical maturity
  • Familiarity with mathematical notation
  • No prior programming experience required

How to Use These Notes

Start with logic and proofs to build foundational reasoning skills, then progress to combinatorics and graph theory. Each section includes worked examples and practice problems.

Use the sidebar to browse topics, or start with the introductory pages linked from the sidebar.

Additional Resources

Each section includes:

  • Detailed explanations of key concepts
  • Worked examples with step-by-step solutions
  • Practice problems with answers
  • Common pitfalls and how to avoid them
  • Connections to other areas of computer science

Study Tips

  1. Master proofs first: Induction and contradiction are essential for all topics
  2. Practice counting: Combinatorics requires practice to recognise patterns
  3. Draw graphs: Visualise graph problems to find solutions
  4. Learn standard examples: Know the properties of common graphs (complete, bipartite, planar)
  5. Connect to algorithms: Discrete math is the language of algorithm analysis