Free Discrete Math Cheatsheet

Home

Homework Help

Study Help

Roadmaps

Cheatsheets

Image to LaTeX

Courses

Contact

Discrete Math Cheatsheet

Definitions, Symbols, Formulas, and Notes — All in One Place.

Show Shortcuts

Logical Connectives

Term	Symbol	Definition	Logical Expression
Negation	$\neg$ $\sim$ $\overset{―}{}$	Not	$\neg p$ $\sim p$ $\overset{―}{p}$
Conjunction	$\land$	And	$p$ AND $q$ $p \land q$
Disjunction	$\lor$	Or	$p$ OR $q$ $p \lor q$
Implication Conditional	$\to$	If, Then. If $p$ , then $q$ $p$ implies $q$	$p \to q$
Biconditional	$\leftrightarrow$	If And Only IF. $p$ if and only if $q$	$p \leftrightarrow q$
Converse		If $q$ , then $p$	$q \to p$
Inverse		If $\neg p$ , then $\neg q$ .	$\neg p \to \neg q$
Contrapositive		If $\neg q$ , then $\neg p$ .	$\neg q \to \neg p$
Therefore	$∴$	Usually goes before the final statement in a proof.
Such That	: $∋$	Expresses a condition that must be fulfilled
If and Only If Symbol Iff	$\leftrightarrow$	Expresses that the truth of a statement on one side of the array requires the truth of the statement on the other side of the arrow.

Logical Equivalences

Term		Equivalence
Identity Laws		$p \land T \equiv p$ $p \lor F \equiv p$
Domination Laws Null Laws		$p \land F \equiv F$ $p \lor T \equiv T$
Idempotent Laws		$p \lor p \equiv p$ $p \land p \equiv p$
Double Negation Law Involution Law		$\neg (\neg p) \equiv p$
Commutative Laws		$p \lor q \equiv q \lor p$ $p \land q \equiv q \land p$
Associative Laws		$(p \lor q) \lor r \equiv p \lor (q \lor r)$ $(p \land q) \land r \equiv p \land (q \land r)$
Distributive Laws		$p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$ $p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)$
De Morgan's Laws		$\neg (p \lor q) \equiv (\neg p) \land (\neg q)$ $\neg (p \land q) \equiv (\neg p) \lor (\neg q)$
Absorption Laws		$p \land (p \lor q) \equiv p$ $p \lor (p \land q) \equiv p$
Negation Laws		$p \land \neg p \equiv F$ $p \lor \neg p \equiv T$
Logical Equivalence		$p \equiv q$

Logic Definitions

Term		Definition
Proposition	A sentence that is either true or false, but not both.
Contradiction	A proposition that is always false.
Contingency	A proposition that is neither a tautology nor a contradiction.
Tautology	A proposition that is always true.
Truth Table	A table used to determine the truth value of a logical expression based on all possible combinations of input truth values.
Predicate	A logical statement whose truth value is a function of one or more variables.

Quantifiers

Term		Symbol		Definition		Example
Universal Quantifier	$\forall$	For all $x$ , $p (x)$ For all For any For each	$\forall x p (x)$
Existential Quantifier	$\exists$	There exists $x$ such that $p (x)$ There exists There is at least one	$\exists x p (x)$

Term

Symbol

Definition

Example

Universal Quantifier

\forall

For all $x$ , $p (x)$

For all

For any

For each

\forall x p (x)

Existential Quantifier

\exists

There exists $x$ such that $p (x)$

There exists

There is at least one

\exists x p (x)

Logical Equivalences (Conditional)

Term
$p \to q \equiv \neg p \lor q$
$p \to q \equiv \neg q \to \neg p$
$p \lor q \equiv \neg p \to q$
$p \land q \equiv \neg (p \to \neg q)$
$\neg (p \to q) \equiv p \land \neg q$
$(p \to q) \land (p \to r) \equiv p \to (q \land r)$
$(p \to r) \land (q \to r) \equiv (p \lor q) \to r$
$(p \to q) \lor (p \to r) \equiv p \to (q \lor r)$
$(p \to r) \lor (q \to r) \equiv (p \land q) \to r$

Logical Equivalence (Biconditional)

Term
$p \leftrightarrow q \equiv (p \to q) \land (q \to p)$
$p \leftrightarrow q \equiv \neg p \leftrightarrow \neg q$
$p \leftrightarrow q \equiv (p \land q) \lor (\neg p \land \neg q)$
$\neg (p \leftrightarrow q) \equiv p \leftrightarrow \neg q$

Rules of Inference

Term

Rule of Inference

Tautology

Example

Modus Ponens

Law of Detachment

\begin{aligned} p \to q \\ p \\ ∴ q \end{aligned}

((p \to q) \land p) \Rightarrow q

$p \to q$	"If it is raining, then I will make tea."
$p$	"It is raining."
$∴ q$	"Therefore, I will make tea."

Modus Tollens

\begin{aligned} p \to q \\ \neg q \\ ∴ \neg p \end{aligned}

(p \to q) \land \neg q \Rightarrow \neg p

Addition

\begin{aligned} q \\ ∴ q \lor r \end{aligned}

p \Rightarrow (p \lor q)

Simplification

\begin{aligned} q \land r \\ ∴ q \end{aligned}

(p \land q) \Rightarrow p

Resolution

\begin{aligned} p \lor q \\ \neg p \lor r \\ ∴ q \lor r \end{aligned}

(p \lor q) \land (\neg p \lor r) \Rightarrow (q \lor r)

Hypothetical Syllogism

\begin{aligned} p \to q \\ q \to r \\ ∴ p \to r \end{aligned}

(p \to q) \land (q \to r) \Rightarrow (p \to r)

Disjunctive Syllogism

\begin{aligned} p \lor q \\ \neg p \\ ∴ q \end{aligned}

(p \lor q) \land \neg p \Rightarrow q

Set Theory

Term	Definition	Notation
Set	A collection of objects, enclosed in braces.	$A = {1, 2, 3, 4}$
Element Member	An object in a set.	$\in$
Cardinality Size	The total number of elements in a set. For example: $A = {1, 2, 3, 4} . \| A \| = 4$	$\| X \|$
Set Builder Notation	A special notation used to describe sets that are too complex to list between braces. For example: $\begin{array}{l} E = {\dots - 4, - 2, 0, 2, 4 \dots} \\ E = {2 n : n \in Z} \end{array}$	$X = {expression : rule}$
Finite Set	A set with a countable amount of elements.
Infinite Set	A set with an infinite amount of elements.
Ordered Pair	A list $x, y$ of two things $x$ and $y$ .	$(x, y)$
Empty Set	A set that has no elements.	$\emptyset$ ${}$
Powerset	The power set of any given set is a set of all the subsets of that set, including the empty set and the set itself. The power set is denoted as $P (A)$ for a set $A$ .	$P (A)$
Subset	A subset is a set where every element of this set is also an element of another set. More formally, a set $A$ is a subset of a set $B$ if every element of $A$ is also an element of $B$ . This is denoted $A \subseteq B$ .	$A \subseteq B$ $\forall x : x \in A \to x \in B$
Proper Subset	A proper subset is a subset of a set that is not identical to the original set. More formally, if $A$ is a subset of $B$ , and there is at least one element in $B$ that is not in $A$ , then $A$ is a proper subset of $B$ .	$A \subset B$ $A \subseteq B \land \exists y \in B : y \notin A$
Superset	A set's superset contains all of its elements, potentially along with additional elements.	$A \supseteq B$
Proper Superset	A superset that is not equal to the original set.	$A \supset B$
Set Equality	The condition where two sets contain exactly the same elements.	$A \subseteq B \land B \subseteq A$ $A = B$
Universal Set	A set which contains all elements under consideration in a context or problem.	$U$
Power Set	Given a set S, the power set contains all subsets of S, including the empty set and S itself.	$P (A)$
Tuple	An ordered list of elements, often represented as $(x, y)$	$(1, 2)$
Roster Notation	A concise way to represent a set by listing its elements, separated by commas and enclosed in braces.	$A = {1, 2, 3, 4}$
Disjoint Set	Sets that have no elements in common.	$A$ and $B$ are disjoint if and only if $A \cap B = \emptyset$

Common Sets

Term	Symbol	Definition	Examples
Natural Numbers	$N$	The set of natural numbers (Positive Integers)	$N = {1, 2, 3, 4, 5, 6, 7, \dots}$
Integers	$Z$	The set of integers.	$Z = {\dots, - 3, - 2, - 1, 0, 1, 2, 3, 4, \dots}$
Rational Numbers	$Q$	The set of rational numbers.	$Q = {x : x = \frac{m}{n}$ , where $m, n \in Z$ and $n \neq 0}$
Real Numbers	$R$	The set of real numbers.	${- 5, - 2.5, 2.5, 5}$
Prime Numbers	$P$	The set of prime numbers, which are integers greater than 1 with no positive divisors other than 1 and themselves	$P = {2, 3, 5, 7, 11, 13 \dots}$
Whole Numbers	$W$	The set of all positive integers, including zero.	$W = {0, 1, 2, 3, 4, 5, \dots}$
Irrational Numbers	$I$	The set of numbers that cannot be expressed as a ratio of two integers. Examples include the square root of 2.	${\sqrt{(} 2), π}$

Set Operations

Term	Notation	Definition
Set Complement	$\overset{―}{A}$	Let $A$ be a set with a universal set $U$ . The complement of $A$ is the set $\overset{―}{A} = U - A$ .
Set Intersection	$\cap$	Given two sets $A$ and $B$ , their intersection is a set composed only of the elements that are both in $A$ and in $B$ .
Set Union	$\cup$	Given two sets $A$ and $B$ , their union is the set composed of all elements both in $A$ and $B$ .
Cartesian Product	$\times$ $A \times B = {(a, b) : a \in A, b \in B}$	The multiplication of two sets $A$ and $B$ , resulting in a set of ordered pairs of elements from $A$ and $B$ .
Cartesian Power	$A^{n}$ $A^{n} = A \times A \times \dots \times A = {(x_{1}, x_{2}, \dots, x_{n}) : x_{1}, x_{2}, \dots, x_{n} \in A}$	The cartesian product of a set $A$ with itself $n$ times.
Set Difference	$A ∖ B$	The difference of two sets $A$ and $B$ is the set of all elements that are in $A$ but not in $B$ .
Symmetric Difference	$A Δ B$ ${x ∣ x \in A \leftrightarrow x \notin B}$	A set operation that yields a new set containing elements that are in either of the two sets but not in both.

Counting

Term	Symbol	Definition	Formula
List		An ordered sequence of objects, enclosed in parenthesis.	$(a, b, c, d, e)$
Empty List		A special list with no entries.
Multiplication Principle		Suppose in making a list of length $n$ there are $a_{1}$ possible choices for the first entry, $a_{2}$ possible choices for the second entry, $a_{3}$ possible choices for the third entry, and so on. Then the total number of different lists that can be made this way is the product of $a_{1} \cdot a_{2} \cdot a_{3} \dots a_{n}$
Factorial	$n!$	The product of all positive integers up to a given number $n$ .	$n! = n \cdot (n - 1) \cdot (n - 2) \dots 3 \cdot 2 \cdot 1$
Combination	$C (n, k)$	The number of ways to choose a subset of $k$ elements from a set of $n$ distinct elements, without considering the order.	$C (n, k) = \frac{n!}{k! (n - k)!}$
Permutation	$P (n, k)$	The number of ways to arrange $k$ elements from a set of $n$ distinct elements, considering the order.	$P (n, k) = \frac{n!}{(n - k)!}$
Binomial Theorem		The binomial theorem describes the algebraic expansion of powers of a binomial. For any positive integer $n$ and any real numbers $a$ and $b$ , the binomial theorem states that $(a + b)^{n} = \sum_{k = 0}^{n} C (n, k) \cdot a^{n - k} \cdot b^{k}$	$(a + b)^{n} = \sum_{k = 0}^{n} C (n, k) \cdot a^{n - k} \cdot b^{k}$
Pigeonhole Principle		If $n$ objects are placed into $m$ containers and $n > m$ , then at least one container must contain more than one object.
Generalized Pigeonhole Principle		The Generalized Pigeonhole Principle is an extension of the Pigeonhole Principle. It states that if $N$ objects are placed into $m$ containers and $N > m$ , then at least one container must contain at least $⌈ \frac{N}{m} ⌉$ objects.
Principle of Inclusion and Exclusion		A counting technique used to calculate the number of elements in the union of several sets by correcting for overcounting.

Functions

Term		Definition
Function		A mathematical relation between a set of inputs (domain) and a set of possible outputs (codomain), where each input is related to exactly one output.
Domain		The domain of a function is the set of all possible input values for which the function is defined. It specifies the valid inputs that the function can operate on.
Codomain		The codomainof a function is the set that includes all possible output values that the function can produce. It provides a broader range than the actual outputs and may include values that the function doesn't necessarily map to.
Range Image		The range of a function, $f (A)$ , also known as a function's image, is the set of all actual output values that the function can produce for the given inputs. It represents the values attained by applying the function to elements in its domain.
One-To-One (Injective) Function		A function in which different elements in the domain map to different elements in the codomain. No two different inputs produce the same output.
Onto (Surjective) Function		A function in which every element in the codomain has at least one pre-image in the domain. The function covers the entire codomain.
Bijective Function		A function that is both injective (one-to-one) and surjective (onto). Each element in the domain maps to a unique element in the codomain, and every element in the codomain has a pre-image.
Inverse Function		For a bijective function $f : A \to B$ , the inverse function $f^{- 1} : B \to A$ is such that $f (f^{- 1} (y)) = y$ for all $y$ in the codomain of $f$ and $f^{- 1} (f (x)) = x$ for all $x$ in the domain of $f$ .
Function Composition		The composition of two functions $f$ and $g$ is a new function denoted by $g \circ f$ , defined as $(g \circ f) (x) = g (f (x))$ .
Generating Function		A generating function is a formal power series used to encode information about a sequence of numbers or combinatorial structures into a single function,

Sequences and Series

Term	Definition	Formula
Summation Notation	A concise way to represent the sum of a sequence. It uses the symbol $\sum$ and specifies the terms to be summed, the variable of summation, and the range of values for the variable.	$\sum_{i = 1}^{n} a_{i}$
Geometric Sequence	A sequence in which the ratio of any two consecutive terms is constant. It can be represented by the formula $a_{n} = a_{1} \cdot r^{(n - 1)}$ , where $a_{n}$ is the $n$ -th term, $a_{1}$ is the first term, $n$ is the number of terms, and $r$ is the common ratio.	$a_{n} = a_{1} \cdot r^{(n - 1)}$
Fibonacci Sequence	A sequence where each term is the sum of the two preceding terms, usually starting with 0 and 1. The Fibonacci sequence is represented as 0, 1, 1, 2, 3, 5, 8, 13, ...	$F_{0} = 0, F_{1} = 1$ $F_{n} = F_{n - 1} + F_{n - 2}$
Periodic Sequence	A periodic sequence is a sequence of numbers that repeats itself after a fixed number of terms, called the period.	$a_{n} = a_{n + k}$
Quadratic Sequence	A quadratic sequence is a sequence of numbers where each term is generated by a quadratic function of the form $a n^{2} + b n + c$ , where $a$ , $b$ , and $c$ are constants and $n$ is the term number.
Power Series	A power series represents a function as a sum of powers of xx. Depending on the convergence properties, a power series may converge only for certain values of xx (within its radius of convergence).	$\sum_{n = 0}^{\infty} a_{n} x^{n}$
Binomial Series	The binomial series is a specific form of power series representing the expansion of $(1 + x)^{n}$ . The binomial series converges when $\| x \| < 1$ .	$\sum_{k = 0}^{\infty} (\binom{n}{k}) x^{k}$
Harmonic Series	The harmonic series is the sum of the reciprocals of the positive integers. It diverges as $n$ approaches infinity, meaning it grows without bound.	$H_{n} = \sum_{k = 1}^{n} \frac{1}{k}$
Sum of Geometric Sequence	The sum of the terms of a geometric sequence. It can be represented by the formula $S_{n} = \frac{a_{1} (r^{n} - 1)}{r - 1}$ , where $S_{n}$ is the sum of the first $n$ terms, $a_{1}$ is the first term, $n$ is the number of terms, and $r$ is the common ratio.	$S_{n} = \frac{a_{1} (r^{n} - 1)}{r - 1}$
Sum of Arithmetic Sequence	The sum of the terms in an arithmetic sequence.	$S_{n} = \frac{n}{2} (2 a_{1} + (n - 1) d)$
Recurrence Relations	An equation that recursively defines a sequence in terms of its previous terms. It expresses each term as a function of one or more previous terms.
Arithmetic Sequence	A sequence in which the difference of any two consecutive terms is constant. It can be represented by the formula $a_{n} = a_{1} + (n - 1) d$ , where $a_{n}$ is the $n$ -th term, $a_{1}$ is the first term, $n$ is the number of terms, and $d$ is the common difference.	$a_{n} = a_{1} + (n - 1)$
Convergence	Convergence occurs when the terms in a sequence or series approach a finite limit as the index or the number of terms increases, indicating stability or convergence towards a specific value.
Radius of Convergence	Given a power series in the form $\sum_{n = 0}^{\infty} c_{n} (x - a)^{n}$ , the radius of convergence is the number R where the series converges absolutely for all $x$ in the interval $(a - R, a + R)$ , and diverges for $x$ outside this interval.
Divergence	Divergence occurs when a sequence or series does not approach a finite limit as the index or the number of terms increases, indicating instability or divergence towards positive or negative infinity.

Graph Theory

Term	Definition	Formula
Vertex, Node	A vertex represents a distinct point or object in a graph.	$V$
Edge	An edge represents a connection or relationship between two nodes or vertices. It defines the link or interaction between the entities represented by the connected nodes.	$E$
Walk	A sequence of vertices in a graph where consecutive vertices are connected by edges. It can include repeated vertices and edges.
Open Walk	A walk in a graph that starts and ends at different vertices.
Closed Walk	A walk in a graph that starts and ends at the same vertex.
Circuit	A closed walk in a graph where vertices may be repeated but no edge is repeated.
Cycle	A closed walk in a graph where no edge is repeated. Every cycle is a circuit, but not every circuit is a cycle.
Bipartite Graph	A graph whose vertices can be divided into two disjoint sets such that every edge connects a vertex from one set to a vertex in the other set. A common notation is $G = (V, E)$ with $V = V_{1} \cup V_{2}$ and $E \subseteq (V_{1} \times V_{2}) \cup (V_{2} \times V_{1})$ .
Directed Graph	A graph in which edges have a direction, indicating a one-way relationship between the connected vertices. Also known as a digraph.
Subgraph	A graph formed by selecting a subset of vertices and edges from a larger graph, preserving the relationships between the selected vertices.
Trail	A walk in a graph where no edge is repeated. Vertices may be repeated, but edges are distinct.
Path	A trail in a graph where no vertex is repeated. Both vertices and edges are distinct along the path.
Euler Circuits	A circuit in a graph that visits every edge exactly once and returns to the starting vertex. For a graph to have an Euler circuit, every vertex must have an even degree.
Euler Paths	A path in a graph that visits every edge exactly once. For a graph to have an Euler path, it must have exactly two vertices with an odd degree (or zero odd-degree vertices).
Hamilton Circuits	A Hamiltonian circuit is a traversal of a graph that visits each vertex exactly once and returns to the starting vertex.
Hamilton Paths	A Hamiltonian path is a traversal of a graph that visits each vertex exactly once. Unlike a Hamiltonian circuit, it doesn't necessarily return to the starting vertex.
Matching	A set of edges in a graph, with no two edges sharing a common vertex. A maximum matching is the largest possible matching in a graph.
Euler's Formula	In graph theory, Euler's formula relates the number of vertices, edges, and faces of a connected planar graph. It is expressed as $V - E + F = 2$ , where $V$ is the number of vertices, $E$ is the number of edges, and $F$ is the number of faces.
Graph Coloring	Coloring a graph is an assignment of labels (colors) to its vertices such that no two adjacent vertices have the same color.
Chromatic Numbers	The chromatic number of a graph is the minimum number of colors needed for a valid coloring.
Complete Graph	A complete graph is a graph in which each pair of distinct vertices is connected by a unique edge.
Null Graph	A null graph is a graph with no edges, meaning it consists solely of isolated vertices. It is the simplest possible graph, containing no connections between any pair of vertices.
Degree	Degree is a measure of the connectivity of a vertex in a graph, representing the number of edges incident to that vertex. In undirected graphs, the degree of a vertex is simply the count of adjacent edges, while in directed graphs, there are separate in-degree and out-degree measures.
Adjacency	In a graph, vertices that share an edge are said to be adjacent.
Incidency	If a vertex is incident to an edge, it means the vertex is directly connected to the edge. Similarly, when an edge is incident to a vertex, it is directly connected to the vertex.
Graph Isomorphism	Graph isomorphism is a property of two graphs where despite having potentially different vertex and edge labels, their structures remain identical, meaning there exists a bijective mapping between their vertices preserving adjacency relationships.
In-degree	The number of edges the number of edges that are directed towards a vertex in a directed graph.
Out-degree	The number of edges that are directed away from a vertex in a directed graph.

Advanced Graph Theory

Term		Definitions
Wheel		A type of graph that contains a cycle of length nn (called the rim) and a single vertex (called the hub) that is connected to every vertex on the rim.
Countable Graph		A graph is countable if its vertex set is countable, meaning it has either a finite number of vertices or a countably infinite number of vertices.
Graph Transitivity		In a directed graph, transitivity refers to the property where if there exists a directed edge from vertex $A$ to vertex $B$ , and another directed edge from vertex $B$ to vertex $C$ , then there is also a directed edge from vertex $A$ to vertex $C$
Tournament		A directed graph in which every pair of distinct vertices is connected by exactly one directed edge.
Hypergraph		A generalization of a graph in which an edge can connect any number of vertices, rather than just two.
Partial Transversal		In the context of hypergraphs, a partial transversal is a subset of vertices that intersects with some, but not necessarily all, of the hyperedges.
Edge-Disjoint Paths		In a graph, edge-disjoint paths are paths that do not share any common edges.
Vertex-Disjoint Paths		In a graph, vertex-disjoint paths are paths that do not share any common vertices, except possibly for their endpoints.
VW-Disconnecting Set		In a graph, a VW-disconnecting set is a set of vertices that, when removed from the graph, disconnects all paths between a set of source vertices $V$ and a set of target vertices $W$ .
VW-Separating Set		n a graph, a VW-separating set is a set of vertices that, when removed from the graph, separates all paths between a set of source vertices $V$ and a set of target vertices $W$ .
Dual Graph		In the context of planar graphs, the dual graph of a planar graph is a graph that represents the faces of the original graph as vertices, and connects two vertices if the corresponding faces share an edge.
Network		A graph that represents connections between nodes, often used to model transportation systems, communication networks, etc.
Source		In a network or flow graph, a source is a node from which flow originates.
Sink		In a network or flow graph, a sink is a node where flow is consumed or terminates.
Flow		In the context of flow networks, flow refers to the quantity of some resource (e.g., water, data) that is sent through edges from a source to a sink, subject to certain capacity constraints.
Graph Saturation		The process of adding edges to a graph in order to satisfy certain connectivity or degree requirements.
Cut		A partition of the vertices of a graph into two disjoint sets such that removing the edges that connect the two sets disconnects the graph.
Max-flow min-cut theorem		A theorem relating to networks that states that the maximum flow from a source to a sink in a flow network is equal to the minimum capacity of a cut in the network.
Arcs		A directed edge that connects two vertices, indicating a one-way connection from one vertex (the tail) to another vertex (the head).
Dual Graph		In directed graphs, arcs are directed edges that connect two vertices, indicating a one-way connection from one vertex to another
Strong Connection		A strong connection typically refers to a directed graph where there exists a directed path from every vertex to every other vertex.
Weak Connection		A weak connection typically refers to an undirected graph where there exists a path between every pair of vertices.

Integers

Term	Definition	Formula
Prime Number	A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. In other words, it cannot be formed by multiplying two smaller natural numbers.
Composite Number	A composite number is a natural number greater than 1 that is not a prime number. It has divisors other than 1 and itself, meaning it can be formed by multiplying two smaller natural numbers.
Odd Number	An odd number is a natural number that is not divisible evenly by 2. In other words, it leaves a remainder of 1 when divided by 2.	$2 n + 1$
Even Number	An even number is a natural number that is divisible evenly by 2. It leaves no remainder when divided by 2.	$2 n$
Greatest Common Divisor	The largest positive integer that divides two or more integers without leaving a remainder.	$gcd (a, b)$
Prime Factorization	The expression of a composite number as the product of its prime factors. For a positive integer $n$ , the prime factorization is written as $n = p_{1}^{e_{1}} \cdot p_{2}^{e_{2}} \cdot \dots \cdot p_{k}^{e_{k}}$ , where $p_{1}, p_{2}, \dots, p_{k}$ are prime numbers and $e_{1}, e_{2}, \dots, e_{k}$ are their respective exponents.
Chinese Remainder Theorem	The Chinese Remainder Theorem states that states that if $m_{1}, m_{2}, \dots, m_{k}$ are pairwise coprime positive integers, and $a_{1}, a_{2}, \dots, a_{k}$ are any integers, then there exists a unique integer $x$ such that $x \equiv a_{1} (\mod m_{1})$ , $x \equiv a_{2} (\mod m_{2})$ , $\dots$ , $x \equiv a_{k} (\mod m_{k})$ .
The Division Algorithm	A fundamental theorem stating that given any integers $a$ and $b$ , with $b > 0$ , there exist unique integers $q$ and $r$ such that $a = b q + r$ , where $0 \leq r < \| b \|$ .
Linear Diophantine Equation	An equation of the form $a x + b y = c$ , where $a, b,$ and $c$ are integers, and $x$ and $y$ are variables. A solution exists if and only if $c$ is a multiple of the greatest common divisor of $a$ and $b$ .
Euclidean Algorithm	An extension of the Euclidean Algorithm used to find the coefficients $x$ and $y$ such that $a x + b y = gcd (a, b)$ . It is often applied in finding modular inverses.
Extended Euclidean Algorithm	The smallest positive integer that is a multiple of two or more integers. It is often denoted as $lcm [a, b]$ for integers $a$ and $b$ .
Least Common Multiple	The smallest positive integer that is a multiple of two or more integers. It is often denoted as $lcm [a, b]$ for integers $a$ and $b$ .
Modular Multiplicative Inverse	For an integer $a$ and a modulus $m$ , the modular multiplicative inverse of $a$ (mod $m$ ) is an integer $x$ such that $a x \equiv 1 (\mod m)$ . It exists if and only if $a$ and $m$ are coprime.
Coprime	Two integers are said to be coprime if their greatest common divisor is 1

Relations

Term		Definition
Relation		A relation between sets is a set of ordered pairs. It describes how elements from one set relate to elements in another set.
Reflexive Relation		A relation on a set where every element is related to itself. Formally, for all $a$ in the set, $(a, a)$ is in the relation.
Symmetric Relation		A relation on a set where if $(a, b)$ is in the relation, then $(b, a)$ is also in the relation for all $a, b$ in the set.
Transitive Relation		A relation on a set where if $(a, b)$ and $(b, c)$ are in the relation, then $(a, c)$ is also in the relation for all $a, b, c$ in the set.
Binary Relation		A binary relation describes a connection or relationship between pairs of elements in a set.
Irreflexive Relation		A relation on a set where no element is related to itself. Formally, for all $a$ in the set, $(a, a)$ is not in the relation.
Antisymmetric Relation		A relation on a set where if $(a, b)$ is in the relation, then $(b, a)$ is not in the relation for all $a, b$ in the set.
Partitions		A partition of a set is a grouping of its elements into non-empty subsets, in such a way that every element is included in exactly one subset.
Equivalence Relation		A relation on a set that is reflexive, symmetric, and transitive. It divides the set into equivalence classes where elements within a class are equivalent.
Equivalence Class		An equivalence class is a group of elements from a set that are considered equivalent to each other based on some defined equivalence relation.
Partial Ordering		A partial ordering satisfies reflexivity, antisymmetry, and transitivity but may not be total.
Total Ordering		A total ordering is a relation that is reflexive, antisymmetric, and transitive.
Cover Relation		In a partially ordered set, a cover relation describes when one element is immediately greater than another, with no elements in between.
Linear Extension		A linear extension is a total order that maintains the same order relationship as the partial order, arranging elements in a sequence without any ambiguity or conflict in the ordering.

Discrete Probability

Term	Definition	Formula
Bayes' Theorem	A mathematical formula that describes the probability of an event based on prior knowledge of conditions that might be related to the event. It is named after the Reverend Thomas Bayes.
Bernoulli Trials	A sequence of independent experiments or trials, each with only two possible outcomes: success or failure. The trials are identically distributed.
Conditional Probability	The probability of event $A$ occurring given that event $B$ has occurred. It is calculated using the formula $P (A \| B) = \frac{P (A \cap B)}{P (B)}$ .	$P (A \| B) = \frac{P (A \cap B)}{P (B)}$
Expected Value	The average value of a random variable. For a discrete random variable $X$ , the expected value $E (X)$ is calculated as the sum of each possible value multiplied by its probability: $E (X) = \sum x P (X = x)$ .	$E (X) = \sum x P (X = x)$
Independent Events	Two events are independent if the occurrence of one event does not affect the occurrence of the other. For independent events, the probability of both events occurring is the product of their individual probabilities: $P (A \cap B) = P (A) \cdot P (B)$ .	$P (A \cap B) = P (A) \cdot P (B)$
Distribution	In statistics, a distribution is a function that describes the likelihood of obtaining the possible values that a random variable can take.

Proof-Writing Techniques

Term	Definition	Example
Direct Proof	A proof of some statement one arrives at through logical, sequential statements.	Prove that the sum of any two odd integers is even. Assume m and n are two odd integers. $m = 2 x + 1, n = 2 y + 1$ for some integers $x$ and $y$ . $m + n = 2 x + 1 + 2 y + 1$ $m + n = 2 x + 2 + 2 y$ $m + n = 2 (x + y + 1)$ As we may write the sum of $m$ and $n$ in the form $2 a$ where a is some integer, the sum of $m$ and $n$ is even.
Proof by Contrapositive	A method of proof that begins supposes the contrapositive is true and through logical, sequential statements, proves the original statement. You might use this if the contrapositive is easier to prove than the original statement.	Prove that if $x^{2} - 6 x + 5$ is even, $x$ is odd. We will prove the contrapositive, e.g., if $x$ is even, $x^{2} - 6 x + 5$ is odd Suppose x is even. Therefore, we may write x as $x = 2 a$ for some integer $a$ . Substitute for x $x^{2} - 6 x + 5$ = $4 a^{2} - 12 a + 5$ We can then factor. $4 a^{2} - 12 a + 5$ = $2 (2 a^{2} - 6 a + 2) + 1$ We can rewrite our expression as $2 b + 1$ , where $b = 2 (2 a^{2} - 6 a + 2)$ Therefore, $x^{2} - 6 x + 5$ is odd Therefore, $x$ is odd if $x^{2} - 6 x + 5$ is even
Proof by Contradiction	A proof of some statement that begins with the assumption that it is not true, and then reasons that it is impossible for it to be untrue.	Prove that if $p^{2}$ is even, $p$ is even Suppose $p$ is odd. Therefore, we may write $p$ as $p = 2 a + 1$ for some integer $a$ . Substitute for $p$ $p^{2} = (2 a + 1)^{2}$ $(2 a + 1)^{2} = 4 a^{2} + 4 a + 1$ We can rewrite our expression as $2 b + 1$ , where $b = 2 (2 a^{2} + 2)$ However, $p^{2}$ must be even, so this is not possible. Therefore, $p$ must be even.
Proof by Induction	A method of proof where one proves a base case where n=1, assumes it is true for n =k, and then proves it is true for n=k+1	Prove that $11^{n} - 6$ is divisible by $5$ for every positive integer $n$ . Base Case: When $n = 1$ , $11^{1} - 6 = 5$ , which is divisible by $5$ Inductive Hypothesis: Assume that $11^{k} - 6$ is divisible by $5$ for every positive integer $k$ We can rewrite this as $11^{k} - 6 = 5 m$ or $11^{k} = 5 m + 6$ Inductive Step: We must prove that $11^{k + 1} - 6$ is divisible by $5$ for every positive integer $k$ $11^{k + 1} - 6 = (11 \cdot 11^{k}) - 6$ $11^{k + 1} - 6 = (11 \cdot (5 m + 6)) - 6$ $11^{k + 1} - 6 = 55 m + 66 - 6$ $11^{k + 1} - 6 = 55 m + 60 = 5 (11 m + 12)$ Therefore, by induction, $11^{n} - 6$ is divisible by $5$ for every positive integer $n$ .
Proof by cases	A method of proof that separates the original statement into separate cases and then proves them individually.	Prove that $n^{2} \geq n$ for all integers $n$ Case 1: n is positive For positive integers $n > 0$ , we can rewrite $n^{2}$ as $n \times n$ . Since $n > 0$ , $n \times n$ is at least $n$ because it is $n$ added to itself $n - 1$ times. Hence, $n^{2} \geq n$ for $n > 0$ . Case 2: n is negative For negative integers $n < 0$ , $n^{2}$ is positive, and $n$ is negative. Since the square of a negative number is positive and greater than the negative number itself, $n^{2} \geq n$ for $n < 0$ . Case 3: n is 0 $0^{2}$ = 0 $0 \geq 0$
QED	Stands for the Latin "quod erat demonstrandum," and usually appears at the end of a proof to signify it is complete.

AI Study Tools for STEM Students Worldwide.

info@compscilib.com Contact Us

Company

About Us Pricing AI Homework Help AI Study Help Roadmaps Cheatsheets Image to Text Tool Privacy Policy Terms of Use Accessibility Commitment

Courses

Computer Organization Discrete Math Linear Algebra Networking Statistics

Stay up to date

Instagram Discord Eventbrite TikTok Twitter LinkedIn Slack YouTube