Discrete Mathematics Cheat Sheet

The core ideas of Discrete Mathematics distilled into a single, scannable reference — perfect for review or quick lookup.

PiqCue — piqcue.com/discrete-mathematics/cheatsheet

Quick Reference

Set Theory

The study of collections of objects called sets, including operations such as union, intersection, difference, and complement. Set theory provides the foundational language for nearly all of modern mathematics and is essential for defining functions, relations, and data structures.

Propositional and Predicate Logic

Propositional logic studies statements that are either true or false and the connectives (AND, OR, NOT, implication) that combine them. Predicate logic extends this with quantifiers (for all, there exists) and predicates that describe properties of objects, enabling more expressive reasoning.

Graph Theory

The study of graphs, which are mathematical structures consisting of vertices (nodes) connected by edges (links). Graph theory models pairwise relationships and is used to analyze networks, optimize routes, schedule tasks, and solve connectivity problems.

Combinatorics

The branch of mathematics concerned with counting, arrangement, and combination of objects according to specified rules. It includes permutations, combinations, the pigeonhole principle, and generating functions, and is critical for analyzing algorithm complexity.

Mathematical Induction

A proof technique used to establish that a statement holds for all natural numbers. It consists of proving a base case and then showing that if the statement holds for an arbitrary case $n$, it also holds for $n + 1$ (the inductive step).

Relations and Functions

A relation is a set of ordered pairs that defines a relationship between elements of two sets. Functions are special relations where each input maps to exactly one output. Properties of relations include reflexivity, symmetry, transitivity, and equivalence.

Recurrence Relations

Equations that define a sequence recursively, where each term is expressed as a function of preceding terms. They are widely used to analyze the running time of recursive algorithms and to model growth processes.

Boolean Algebra

An algebraic structure that captures the essential properties of logical operations and set operations. It operates on binary values (true/false or 1/0) with AND, OR, and NOT operations, and is fundamental to digital circuit design and computer architecture.

Trees and Spanning Trees

A tree is a connected acyclic graph. Trees model hierarchical structures such as file systems, organizational charts, and decision processes. A spanning tree of a graph is a subgraph that includes all vertices and is a tree, useful for network design and optimization.

Modular Arithmetic

A system of arithmetic for integers where numbers 'wrap around' after reaching a certain value called the modulus. It is fundamental to number theory, cryptography, hashing algorithms, and error-detecting codes.

Key Terms at a Glance

Set:An unordered collection of distinct objects, called elements or members.

Subset:Set $A$ is a subset of set $B$ if every element of $A$ is also in $B$, written $A \subseteq B$.

Proposition:A declarative statement that is either true or false, but not both.

Tautology:A compound proposition that is true regardless of the truth values of its individual components.

Contradiction:A compound proposition that is false regardless of the truth values of its individual components.

Predicate:A statement containing variables that becomes a proposition when specific values are assigned to those variables.

Quantifier:A symbol indicating the scope of a variable: universal ($\forall$, for all) or existential ($\exists$, there exists).

Graph:A structure $G = (V, E)$ consisting of vertices $V$ and edges $E$ representing connections between vertices.

Directed Graph (Digraph):A graph in which edges have a direction, going from one vertex to another.

Degree of a Vertex:The number of edges incident to a vertex. In a directed graph, in-degree and out-degree are counted separately.

Isomorphism:A structure-preserving bijection between two graphs (or other algebraic structures).

Permutation:An ordered arrangement of distinct objects from a set.

Combination:An unordered selection of objects from a set, where order does not matter.

Binomial Coefficient:$\binom{n}{k}$, the number of ways to choose $k$ items from $n$, equal to $\frac{n!}{k!(n-k)!}$.

Recurrence Relation:An equation that defines each term of a sequence as a function of preceding terms.

Get study tips in your inbox

We'll send you evidence-based study strategies and new cheat sheets as they're published.

We'll notify you about updates. No spam, unsubscribe anytime.