Discrete Math Resources & Cheat Sheet

$hero image$

Discrete Math Resources

Resources curated by the CompSciLib team to help you ace your Discrete Math course.

Symbols and Definitions

Common discrete math symbols, definitions, and formulas, all in one place.

Logic

Name	Symbol	Meaning	Notation
Proposition	Definition	A sentence that is either true or false, but not both.
Contradiction	Definition	A proposition that is always false.
Contingency	Definition	A proposition that is neither a tautology nor a contradiction.
Tautology	Definition	A proposition that is always true.
Goldbach Conjecture	Conjecture	Every even integer greater than 2 can be expressed as the sum of two prime numbers.
Truth Table	Definition	A table used to determine the truth value of a logical expression based on all possible combinations of input truth values.
Conjunction	$\land$	$p$ AND $q$	$p \land q$
Disjunction	$\lor$	$p$ OR $q$	$p \lor q$
Negation	$\neg$ , $\sim$ , $\overset{―}{}$	NOT	$\neg p$ , $\sim p$ , $\overset{―}{p}$
Implication, Conditional	$\Rightarrow$	If $p$ , then $q$ \| $p$ implies $q$	$p \Rightarrow q$
Biconditional	$\Leftrightarrow$	$p$ if and and only if $q$	$p \Leftrightarrow q$
Logical Equivalence	$\equiv$	$p$ and $q$ have identical truth values.	$p \equiv q$
Commutative Laws	Law	$\begin{array}{l} p \lor q \equiv q \lor p \\ p \land q \equiv q \land p \end{array}$
Associative Laws	Law	$\begin{array}{l} (p \lor q) \lor r \equiv p \lor (q \lor r) \\ (p \land q) \land r \equiv p \land (q \land r) \end{array}$
Distributive Laws	Law	$\begin{array}{l} 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) \end{array}$
Identity Laws	Law	$\begin{array}{l} p \lor F \equiv p \\ p \land T \equiv p \end{array}$
Negation Laws	Law	$\begin{array}{l} p \land \neg p \equiv F \\ p \lor \neg p \equiv T \end{array}$
Idempotent Laws	Law	$\begin{array}{l} p \lor p \equiv p \\ p \land p \equiv p \end{array}$
Domination Laws	Law	$\begin{array}{l} p \land F \equiv F \\ p \lor T \equiv T \end{array}$
Absorption Laws	Law	$\begin{array}{l} p \land (p \lor q) \equiv p \\ p \lor (p \land q) \equiv p \end{array}$
DeMorgan's Laws	Law	$\begin{array}{l} \neg (p \lor q) \equiv (\neg p) \land (\neg q) \\ \neg (p \land q) \equiv (\neg p) \lor (\neg q) \end{array}$
Double Negation Law	Law	$\neg (\neg p) \equiv p$
Implication	Law	$p \to q \equiv \neg p \lor q$
Modus ponens	Rule	$\begin{array}{l} p \to q \\ p \\ ∴ q \end{array}$
Modus tollens	Rule	$\begin{array}{l} p \to q \\ \neg q \\ ∴ \neg p \end{array}$
Elimination	Rule	$\begin{array}{l} p \lor q \\ \sim p \\ ∴ q \end{array}$
Transitivity	Rule	$\begin{array}{l} p \to q \\ q \to r \\ ∴ p \to r \end{array}$
Converse Error	Fallacy	$\begin{array}{l} p \to q \\ q \\ ∴ p \end{array}$
Inverse Error	Fallacy	$\begin{array}{l} p \to q \\ \sim p \\ ∴ - q \end{array}$
Universal Quantifier	$\forall$	For all $x$ , $p (x)$	$\forall x p (x)$
Existential Quantifier	$\exists$	There exists $x$ such that $p (x)$	$\exists x p (x)$

Sets

Name	Symbol	Meaning	Notation
Set	Definition	A collection of objects, enclosed in braces.	$A = {1, 2, 3, 4}$
Element, Member	Definition	An object in a set.
Cardinality, Size	$\| X \|$	The total number of elements in a set.	$A = {1, 2, 3, 4} . \| A \| = 4$
Set Builder Notation	$X = {expression : rule}$	A special notation used to describe sets that are too complex to list between braces.	$\begin{array}{l} E = {\dots - 4, - 2, 0, 2, 4 \dots} \\ E = {2 n : n \in Z} \end{array}$
Finite Set	Definition	A set with a countable amount of elements.
Infinite Set	Definition	A set with an infinite amount of elements.
Ordered Pair	$(x, y)$	A list $x, y$ of two things $x$ and $y$ .
Empty Set	$\emptyset$ , ${}$	A set that has no elements.
Universal Set	$U$	The universal set.
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$ .
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
Powerset	$P (A)$	PowerSet
Element	$\in$	Is an element of
Subset	$\subseteq$	Is an subset of
Proper Subset	$\subset$	Is a proper subset of
Set Intersection	$\cup$	Set Intersection
Set Union	$\cap$	Set Union
Cartesian Product	$\times$	The multiplication of two sets $A$ and $B$ , resulting in a set of ordered pairs of elements from $A$ and $B$ .	$A \times B = {(a, b) : a \in A, b \in B}$
Cartesian Power	$A^{n}$	The cartesian product of a set $A$ with itself $n$ times.	$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}$
Set Difference	$∖$	The difference of two sets $A$ and $B$ is the set of all elements that are in $A$ but not in $B$ .	$A ∖ B$

Counting

Name	Symbol	Meaning	Notation
List	Definition	An ordered sequence of objects, enclosed in parenthesis.	$(a, b, c, d, e)$
Empty List	Definition	A special list with no entries.	$()$
Multiplication principle	Definition	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}$ .