Useful tip: If you use a browser like Google Chrome, clicking on the lecture slide link in an entry will take you to that slide in the PDF.
0-9 A B C D E F G H I J K L M N O P Q R S T U V W X Y ZIn an implication of the form "If P is true, then Q is true", the antecedent is the term "P is true".
Source: Lecture 02, Slide 14.
In mathematical proofs, an arbitrary choice of $x$ is a statement that $x$ is left unspecified so that any result proven about $x$ holds for any choice of $x$
Source: Lecture 01, Slide 24.
The arity of a predicate is the number of arguments it can take.
Source: Lecture 08, Slide 22.
A binary operator $\diamond$ is called associative when for any $a,b,c$ we have: $a\diamond (b \diamond c)=(a \diamond b) \diamond c$
Source: Lecture 01, Slide 59.
In a proof by induction, the first step in which you prove that P is true for 0.
Source: Lecture 03, Slide 6.
A biconditional is a statement of the form "P if and only if Q", often abbreviated "P iff Q".
Source: Lecture 02, Slide 27.
The biconditional operator $\leftrightarrow$ is used to represnet two-directional implication (i.e. "$p\leftrightarrow q$" means "$p \rightarrow q$" and "$q \rightarrow $p$".)
Source: Lecture 07, Slide 22.
A function that associates each element of the codomain with a unique element of the domain.
Source: Lecture 10, Slide 91.
A binary operator is an operator that operates on two operands. For example: +,-,XOR
Source: Lecture 01, Slide 48.
A bit is a value that can be either 0 or 1. The set $\mathbb{B}$={0,1} is the set of all bits.
Source: Lecture 01, Slide 47.
A bitstring is a finite sequence of bits (0s and 1s).
Source: Lecture 01, Slide 73.
Cantor's theorem states that every set is strictly smaller than its power set. If $S$ is a set, then $|S| \lt |\mathcal P \left({S}\right)| $.
Source: Lecture 00, Slide 87.
If $S$ and $T$ are sets where $|S| \leq |T|$ and $|T| \leq |S|$, then $|T| = |S|$.
Source: Lecture 11, Slide 25.
The cardinality of a set is the number of elements it contains.
Source: Lecture 00, Slide 46.
Proof: Lecture 11, Slide 104.
$|S| = |T|$ if there exists a bijection f from S to T.
Source: Lecture 11, Slide 5.
$|S| \leq |T|$ if there exists a injection f from S to T.
Source: Lecture 11, Slide 24.
$|S| < |T|$ iff $|S| \leq |T|$ and $|S| \neq |T|$ .
Source: Lecture 11, Slide 101.
The Cartesian Product $A \times B$ is defined as $\{(a, b) | a \in A, b \in B \}$
Source: Lecture 11, Slide 6.
The chromatic number of a graph is the minimum number of colors needed to color a graph.
Source: Lecture 06, Slide 62.
If f is a function from A to B, we call B the codomain of f.
Source: Lecture 10, Slide 68.
A binary operator $\diamond$ is called commutative when the following is always true: $a\diamond b = b \diamond a$
Source: Lecture 01, Slide 69.
See Principle of Complete (or Strong) Induction below.
Source: Lecture 05, Slide 5.
In an undirected graph, two nodes $u$ and $v$ are called connected if there is a path from $u$ to $v$. We denote this as $u\leftrightarrow v$. If $u$ is not connected to $v$, we write $u\not\leftrightarrow v$.
Source: Lecture 06, Slide 16.
A connected component of an undirected graph $G=(V,E)$ is a non empty set $C\subseteq V$ where
Source: Lecture 06, Slide 25.
In an implication of the form "If P is true, then Q is true", the consequent is the term "Q is true".
Source: Lecture 02, Slide 14.
The contrapositive of the statement "p → q" is the statement "¬q → ¬p".
Source: Lecture 08, Slide 7.
A cycle in a graph is a path from a node to itself.
Source: Lecture 06, Slide 13.
The following two equivalences are called De Morgan's Laws: $\lnot(p \land q) \equiv \lnot p \lor \not q$ and $\lnot(p \lor q) \equiv \lnot p \land \lnot q$.
Source: Lecture 07, Slide 50.
A proof that starts with an initial set of assumptions then applies simple logical steps to directly derive a result.
Source: Lecture 01, Slide 10.
A disproof is an argument establishing why a statement is false. This is often done by stating you will disprove a statement, writing its negation, and writing a normal proof that the statement is false.
Source: Lecture 02, Slide 4.
If f is a function from A to B, we call A the domain of f.
Source: Lecture 10, Slide 68.
The set of objects to which any variable can refer.
Source: Lecture 08, Slide 20.
Two propositional formulas are called equivalent if they have the same truth tables.
Source: Lecture 08, Slide 5.
An integer $n$ is even if there exists some integer $k$ such that $n=2k$
Source: Lecture 01, Slide 11.
An existential statement is a statement of the form: "There exists an $x$ for which $P(x)$ is true. The negation of an existential statement is a universal statement.
Source: Lecture 01, Slide 37.
An existence and uniqueness proof is one where you show that there is at least and at most one object of a type.
Source: Lecture 06, Slide 38.
A logical system for reasoning about properties of objects. Augments the logical connectives from proposition logic with predicates, functions, and quantifiers.
Source: Lecture 08, Slide 16.
A function f is a mapping from one set A to another set B such that every element of A is associated with a single element of B. For each a âˆˆ A, there is some b âˆˆ B with f(a) = b. If f(a) = bâ‚€ and f(a) = bâ‚?, then bâ‚€ = bâ‚?.
Source: Lecture 10, Slide 68.
A function maps objects to one another.
Source: Lecture 08, Slide 16.
A graph is an ordered pair $G=(V,E)$ where $V$ is a set of nodes, and $E$ isi a set of edges, which are either ordered pairs or unordered pairs of elements from $V$.
Source: Lecture 06, Slide 4.
An identity element for a binary operator $\diamond$, is some value $z$ such that for any $a$, $a\diamond z=z\diamond a=a$
Source: Lecture 01, Slide 22.
An implication is a statement of the form: If P is true, then Q is true.
Source: Lecture 02, Slide 13.
The $\rightarrow$ connective is used represent implications. The statement $p \rightarrow q$ means that "whenever $p$ is true, $q$ is true as well. The only truth values of p and q that make an implication false are when p is true and q is false. Otherwise, the implication is true."
Source: Lecture 07, Slide 18.
In a proof by induction during the inductive step: the assumption that $P$ is true for $k$
Source: Lecture 03, Slide 6.
In a proof by induction: prove that if $P$ is true for some arbitrary natural number $k$, then $P$ must also be true for $k+1$
Source: Lecture 03, Slide 6.
A function is called injective (or one-to-one) if each element of the codomain has at most one element of the domain that maps to it.
Source: Lecture 10, Slide 82.
The set $\mathbb{Z} = \left\{ ..., -2, -1, 0, 1, 2, ... \right\}$ is the set of all the integers.
Source: Lecture 00, Slide 22.
An irrational number is a number that is not rational.
Source: Lecture 02, Slide 49.
An undirected graph $G=(V,E)$ is k-colorable iff the nodes in $V$ can be assigned one of $k$ different colors such that no two nodes of the same color are joined by an edge.
Source: Lecture 06, Slide 62.
A lemma is a smaller result proven specifically as a stepping stone towards a larger result.
Source: Lecture 01, Slide 63.
The length of a cycle is the number of edges in that cycle.
Source: Lecture 06, Slide 13.
The length of a path is the number of edges it contains, which is one less than the number of nodes in the path.
Source: Lecture 06, Slide 9.
A logical operator is an operator that takes in some number of bits and produces a new bit as output.
Source: Lecture 01, Slide 47.
"If P is true before we perform an action, it is true after we perform an action."
Source: Lecture 03, Slide 54.
If f is a function from A to B, we say that f is a mapping from A to B.
Source: Lecture 10, Slide 68.
An argument that demonstrates why a mathematical statement is true.
Source: Lecture 01, Slide 7.
The set $\mathbb{N} = \left\{0, 1, 2, 3 ... \right\}$ is the set of all the natural numbers.
Source: Lecture 00, Slide 22.
Theorem: $|\mathbb{N}| = |\mathbb{N}^2|$.
Source: Lecture 11, Slide 21.
Theorem: $|\mathbb{N}| \neq |\mathbb{R}|$.
Source: Lecture 11, Slide 61.
The negation of statement X is the opposite of the statement. This is often used to disprove a statement.
Source: Lecture 02, Slide 5.
$\neg \forall x. \varphi \equiv \exists x. \neg \varphi$
$\neg \exists x. \varphi \equiv \forall x. \neg \varphi$
$\neg(p \wedge q) \equiv p \to \neg q$
$\neg(p \to q) \equiv p \wedge \neg q$
Source: Lecture 09, Slide 33.
A set which contains no elements is called a null set, also represented as $\phi$.
Source: Lecture 00, Slide 16.
An integer $n$ is odd if there exists some integer $k$ such that $n=2k+1$
Source: Lecture 01, Slide 11.
An ordered pair (a, b) is a pair of elements in a specific order.
Source: Lecture 05, Slide 65.
A path from $v_1$ to $v_n$ is a sequence of nodes $v_1,v_2,\ldots,v_n$ where $\{v_k, v_{k+1}\}\in E$ for all natural numbers in the range $1\le k\le n-1$.
Source: Lecture 06, Slide 9.
Functions specified with different rules applying to different elements.
Source: Lecture 10, Slide 75.
If m objects are placed into n bins, where m>n then some bin contains at least 2 objects.
Source: Lecture 10, Slide 08.
A planar graph is a graph where there is a way to draw it in a 2D plane without any of the edges crossing.
Source: Lecture 06, Slide 57.
A predicate describes properties of an object. Applying a predicate to arguments produces a proposition, which is either true or false.
Source: Lecture 08, Slide 22.
The principle of mathematical induction states that if $P(0)$ is true and for any $k \in \mathbb{N}$, if $P(k)$ being true implies $P(k+1)$ is true, then $P(n)$ is true for all $n \in \mathbb{N}$.
Source: Lecture 03, Slide 4.
The principle of complete (or strong) induction states that if $P(0)$ is true and for any $k \in \mathbb{N}$, if $P(0), P(1), \dots, P(k)$ all being true implies $P(k+1)$ is true, then $P(n)$ is true for all $n \in \mathbb{N}$.
Source: Lecture 04, Slide 60.
An argument that demonstrates why a conclusion is true.
Source: Lecture 01, Slide 6.
A proof by contradiction works as follows:
Source: Lecture 02, Slide 45.
A proof by induction is a way to use mathematical induction to show that some result is true for all natural numbers n.
Source: Lecture 03, Slide 6.
A proposition is a statement that is, by itself, either true or false.
Source: Lecture 07, Slide 5.
Propositional logic is a mathematical system for reasoning about propositions and how they relate to one another.
Source: Lecture 07, Slide 11.
One of the following: negation, conjunction, disjunction, implication, biconditional, true, false.
Source: Lecture 08, Slide 4.
A propositional variable is a variable that is either true or false.
Source: Lecture 07, Slide 12.
The power set of any set $S$, written $\mathcal P \left({S}\right)$, is the set of all subsets of $S$, including the empty set and $S$ itself.
Source: Lecture 00, Slide 43.
A quantifier is a statement that expresses that some property is true for some or all choices that could be made.
Source: Lecture 08, Slide 29.
A rational number is a number that can be written as $r = p/q$ where $p$ and $q$ are integers and $q\neq 0$.
Source: Lecture 02, Slide 49.
A binary operator $\diamond$ with identity element $z$ is called self-inverting when for any $a$ we have: $a\diamond a=z$
Source: Lecture 01, Slide 57.
A Set is an unordered collection of distinct objects, which can be anything (including other sets).
Source: Lecture 00, Slide 12.
A set builder notation is a mathematical notation for describing a set by stating the properties that its members must satisfy.
Source: Lecture 00, Slide 25.
A simple cycle in a graph is a cycle that does not revisit any nodes or edges (except the start/end node).
Source: Lecture 06, Slide 14.
A simple path in a graph is a path that does not revisit any nodes or edges.
Source: Lecture 06, Slide 14.
See Principle of Complete (or Strong) Induction below.
Source: Lecture 05, Slide 5.
A set $S$ is a subset of set $T$ (denoted $ S \subseteq T $ ) if all elements of $S$ are also elements of $T$.
Source: Lecture 00, Slide 40.
A tournament is a contest for $n \ge 1$ people in which each person plays exactly one game against each other person, and there are no ties.
Source: Lecture 04. Slide 39.
A visual representation of a tournament.
Source: Lecture 04. Slide 39.
A truth table is a table showing the truth value of a propositional logic formula as a function of its inputs.
Source: Lecture 07, Slide 14.
A universal statement is a statement of the form: "For all $x$, $P(x)$ is true. The negation of an existential statement is an existential statement.
Source: Lecture 01, Slide 37.
An unordered pair is a set {a, b} of two elements (remember that sets are unordered).
Source: Lecture 05, Slide 65.
A statement of the form "All objects of type $P$ are also of type $Q$" is called vacuously true if there are no objects of type $P$.
Source: Lecture 00, Slide 42.
A victory chain in a tournament is a way of lining up the players so that every player beats the player that comes after them.
Source: Lecture 04. Slide 40.
The exclusive or (called XOR for short), is a logical operator, denoted $\bigoplus$,that operates on two bits and returns 0 if they are the same and 1 if they are different.
Source: Lecture 01, Slide 48.