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 ZA propositional formula is in 3-CNF if it is in CNF and every clause has exactly three literals.
Source: Lecture 28, Slide 13.
A 3-coloring of a graph is a way of coloring its nodes one of the three colors such that no two connected nodes have the same color.
Source: Lecture 28, Slide 56.
The 3-coloring problem is: Given an indirected graph $G$, is there a legal 3-coloring of its nodes?
Source: Lecture 28, Slide 57.
The language 3SAT is defined as follows: $3SAT = \{ \langle \phi \rangle \; | \; \phi \text{ is a satisfiable 3-CNF formula\}$
Source: Lecture 28, Slide 13.
$\aleph_0$ is the cardinality of $\mathbb{N}$. That is, $|\mathbb{N}| = \aleph_0$.
Source: Lecture 00, Slide 49.
A TM $M$ accepts a string $w$ if it enters the accept state when run on $w$. $M$ does not accept $w$ if it either rejects $w$ or loops infinitely on $w$
Source: Lecture 19, Slide 21.
An $alphabet$ is a finite set of characters. Typically we use $\sum$ to refer to an alphabet.
Source: Lecture 12, Slide 21.
A CFG is said to be ambiguous if there is at least one string with two or more parse trees.
Source: Lecture 17, Slide 37.
A binary relation $R$ over a set $A$ is called antisymmetric iff:
Source: Lecture 07, Slide 27.
In a mathematical proof, an arbitrary choice of $x$ is a statement that $x$ is left unspecified so that any result proven about $x$ will prove the result for any choice of $x$.
Source: Lecture 01, Slide 19.
See edge.
A binary operator $\ast$ is called associative if for any $a$, $b$, and $c$, we have $a \ast (b \ast c) = (a \ast b) \ast c$.
Source: Lecture 01, Slide 43.
An $automaton$ (plural: $automata$) is a mathematical model of a computing device.
Source: Lecture 12, Slide 18.
See base case.
The part of an inductive proof in which you prove that $P(0)$ is true.
Source: Lecture 03, Slide 6.
A biconditional is a statement of the form "$P$ if and only if $Q$". This can be abbreviated $P$ iff $Q$ and is only true if both $P \to Q$ and $Q \to P$ are true. To prove a biconditional, you must show both implications are true.
Source: Lecture 02, Slide 19.
The biconditional connective $p \leftrightarrow q$ is read "$p$ if and only if $q$." Intuitively, either both $p$ and $q$ are true, or neither of them are.
Source: Lecture 10, Slide 36.
A bijection is a function that associates each element of the codomain with a unique element of the domain. A bijective function is both injective and surjective. They are sometimes called "one-to-one correspondences".
Source: Lecture 08, Slide 37.
A binary operator is an operator that takes in two operands.
Source: Lecture 01, Slide 34.
A binary relation over a set $A$ is a subset of $A \times A = A^2$. That is, it is a subset of the Cartesian product of A with itself. Intuitively speaking, a relation $R$ over $A$ is such that, for every $x, y \in A$, the statement $xRy$ is either true or false, depending on whether $(x, y) \in R \subseteq A^2$.
Source: Lecture 07, Slide 45.
A bit is a value that is either 0 or 1. The set of all bits is denoted $\mathbb{B}$.
Source: Lecture 01, Slide 33.
A bitstring is a finite sequence of bits.
Source: Lecture 01, Slide 56.
Cantor's theorem states that for any set $S$, that $|S| < |\wp(S)|$.
Source: Lecture 00, Slide 68.
For any sets $R$, $S$, and $T$, if $|S| \leq |T|$ and $|T| \leq |S|$, then $|S| = |T|$.
Source: Lecture 09, Slide 42.
The cardinality of a set $S$, denoted $|S|$, is the number of elements it contains. By definition, two sets have the same cardinality precisely if their elements can be put into a one-to-one correspondence.
Source: Lecture 00, Slide 48.
The Cartesian Product $A \times B$ of two sets is defined as $$A \times B \equiv \{ (a, b) | a \in A \text{ and } b \in B \}$$ We denote $A^2 \equiv A \times A$.
Source: Lecture 07, Slide 44.
If $f$ is a function from $A$ to $B$, $B$ is called the codomain of $f$.
Source: Lecture 08, Slide 25.
Every effective method of computation is either equivalent to or weaker than a Turing machine.
Source: Lecture 20, Slide 26.
A clause is a many-way OR (disjunction) of literals.
Source: Lecture 28, Slide 8.
Regular languages are closed under complementation.
Source: Lecture 13, Slide 14.
The (UNPROVEN) claim that the Hailstone sequence for $n$ always terminates.
Source: Lecture 19, Slide 19.
A binary operator $\ast$ is commutative if for any $a$ and $b$, $a \ast b = b \ast a$.
Source: Lecture 01, Slide 52.
Given a language $L \subseteq \sum$*, the complement of that language (denoted $\bar{L}$) is the language of all strings in $\sum$* not in $L$.
Formally: $\bar{L}$ = $\sum$* - $L$
Source: Lecture 13, Slide 10.
A propositional logic formula $\phi$ is in conjunctive normal form (CNF) if it is the many-way AND (conjunction) of clauses.
Souce: Lecture 28, Slide 9.
The minimum number of colors needed to color a graph is called that graph's chromatic number.
Source: Lecture 06, Slide 49.
Let $f:A \rightarrow B$ and $g:B \rightarrow C$. The composition of $f$ and $g$ (denoted as $g \circ f$) is the function $g \circ f: A \rightarrow C$ defined $$(g \circ f)(x)=g(f(x))$$
Note that function composition is associative: $h \circ (g \circ f) = (h \circ g) \circ f$
Source: Lecture 08, Slide 40.
In an undirected graph, two nodes $u$ and $v$ are called connected iff 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 05, Slide 29.
A connected component of an undirected graph $G = (V, E)$ is a nonempty set $C \subseteq V$ where
Source: Lecture 06, Slide 16.
A collection of four objects to describe a language:
Source: Lecture 17, Slide 6.
A language L is context free iff there is a CFG G such that L = $\mathcal{L}$(G).
Source: Lecture 17, Slide 14.
To prove $P$ by contradiction: Assume that $P$ is false. Based on this assumption, conclude something impossible. So long as your logic throughout the proof is sound, the only way you can arrive at an impossible statement is if your original assumption was true. Thus, $P$ cannot be false and must be true.
Source: Lecture 02, Slide 34.
The contrapositive of an implication "If $P$, then $Q$" is "If not $Q$, then not $P$". The contrapositive of an implication is logically equivalent, so to prove an implication, it suffices to prove the contrapositive.
Source: Lecture 02, Slide 15.
A convex polygon is a polygon where, for any two points in or on the polygon, the line between those points is contained within the polygon.
Source: Lecture 04, Slide 10.
A cycle in a graph is a path from a node to itself.
Source: Lecture 05, Slide 26.
$\lnot(p \land q) \equiv \lnot p \lor \lnot q$
$\lnot(p \lor q) \equiv \lnot p \land \lnot q$
Source: Lecture 10, Slide 101.
A sequence of steps where nonterminals are replaced by the right hand side of a production.
Source: Lecture 17, Slide 9.
A model of computation is deterministic if at every point in the computation, there is exactly one choice that can make.
Source: Lecture 13, Slide 22.
A DFA is a Deterministic Finite Automaton.
Source: Lecture 12, Slide 55.
The difference of two sets $A$ and $B$, denoted $A - B$ or $A \backslash B$, is the set of all elements in $A$ but not in $B$.
Source: Lecture 00, Slide 32.
A direct proof is a proof of a result that works by beginning with a set of starting assumptions and directly establishing the truth of the statement.
Source: Lecture 01, Slide 8.
A graph in which each edge has a direction (a "from" node and a "to" node).
Source: Lecture 05, Slide 13.
If $f$ is a function from $A$ to $B$, $A$ is called the domain of $f$.
Source: Lecture 08, Slide 25.
In first-order logic, each variable refers to some object in a set called the domain of discourse.
Source: Lecture 10, Slide 131.
A graph consists of a set of nodes connected by edges.
Source: Lecture 05, Slide 12.
An effective method of computation is a form of computation with the following properties:
Source: Lecture 20, Slide 25.
An element of a set is some object directly contained within the set. If $x$ is an element of $S$, we write $x \in S$.
Source: Lecture 00, Slide 21.
Given a convex polygon, an elementary triangulation of that polygon is a way of connecting the vertices with lines such that (a) no two lines intersect, and (b) the polygon is converted into a set of triangles.
Source: Lecture 04, Slide 29.
The empty set (denoted $\emptyset$) is the set containing no elements.
Source: Lecture 00, Slide 16.
The empty string (denoted $\varepsilon$) is the string with no characters.
Source: Lecture 12, Slide 21.
A sum of no numbers is called the empty sum and is defined to be zero. In summation notation: $$\sum_{i=1}^0 x_i = 0$$ by definition for any $x_i$.
Source: Lecture 03, Slide 21.
An equivalence relation is a relation that is reflexive, symmetric, and transitive.
Source: Lecture 07, Slide 15.
A special predicate = that says whether two objects are equal to one another. For propositions that are equal, see Biconditional
Source: Lecture 10, Slide 136.
Source: Lecture 07, Slide 18.
A proof in which we show that there is at least one object of a particular type, and in which we also show that there is at most one object of a particular type. For instance, we use this method to show that every node belongs to exactly one connected component of a graph.
Source: Lecture 06, Slide 23.
An integer $n$ is even if there exists an integer $k$ such that $n = 2k$.
Source: Lecture 01, Slide 9.
A statement of the form $\exists x. \psi$ asserts that for some choice of $x$ in our domain, $\psi$ is true.
Source: Lecture 11, Slide 22.
An existential statement is a statement of the form "there exists an $x$ for which $P(x)$ is true". Remember, the negation of an existential statement is a universal statement.
Source: Lecture 01, Slide 29.
The symbol $\bot$ is a value that is always false.
Source: Lecture 10, Slide 47.
First-order logic is a logical system for reasoning about properties of objects.
Source: Lecture 10, Slide 123.
A finite automaton is a mathematical machine for determining whether a string is contained within some language. Each finite automaton consists of a set of $states$ connected by $transitions$.
Source: Lecture 12, Slide 27.
A formal language is a set of strings. We say that $L$ is a language over $\sum$ if it is a set of strings formed from characters in $\sum$.
Source: Lecture 12, Slide 22.
Every planar graph is 4-colorable
Source: Lecture 06, Slide 50.
A function is a means of associating each object in one set with an object in some other set.
Formally, a function $f$ is a mapping such that every element of A is associated with a single element of B. So, for each $a \in A$, there is some $b \in B$ with $f(a)=b$. Also, if $f(a)=b_0$ and $f(a)=b_1$, then $b_0=b_1$.
Source: Lecture 08, Slide 25.
In first-order logic, functions map objects to one another. Functions can take in any number of arguments, but each function has a fixed arity. Functions evaluate to objects.
Source: Lecture 11, Slide 12.
A mathematical structure for representing relationships, consisting of a set of nodes connected by edges.
Source: Lecture 05, Slide 12.
Formally, a graph is an ordered pair $G = (V,E)$, where $V$ is a set of nodes and $E$ is a set of edges.
Source: Lecture 05, Slide 18.
A TM $M$ halts on a string $w$ if it enters the accept state or the reject state when run on $w$.
Source: Lecture 19, Slide 21.
A Hasse diagram is a graphical representation of a partial order.
Source: Lecture 07, Slide 35.
An identity element for a binary operator $\ast$ is a value $z$ such that for any $a$, we have $a \ast z = z \ast a = a$.
Source: Lecture 01, Slide 37.
An implication is a statement of the form "If $P$, then $Q$". We can denote that $P$ implies $Q$ using the shorthand $P \to Q$. We call $P$ the antecedent and $Q$ the consequent. Remember, the negation of the implication "If $P$, then $Q$" is "$P$ is true, but $Q$ is false".
Source: Lecture 02, Slide 9.
The connective $p \to q$ is read "if $p$ then $q$"
Source: Lecture 10, Slide 58.
An independent set in an undirected graph is a set of vertices that have no edges between them.
Source: Lecture 28, Slide 18.
Given an undirected graph $G$ and a natural number $n$, the independent set problem is: Does $G$ contain an independent set of size at least $n$?
Source: Lecture 28, Slide 19.
The principle of mathematical induction states that if for some $P(n)$ the following hold: $P(0)$ is true and for any $n \in \mathbb{N}$, we have $P(n) \to P(n+1)$, then for any $n \in \mathbb{N}$, $P(n)$ is true.
To prove a statement by induction, we start by proving a base case $P(0)$ holds. Then, we assume that $P(n)$ holds for some $n$ and show that this implies that $P(n+1)$ must also be true. We call this step the inductive step and call $P(n)$ the inductive hypothesis.
Source: Lecture 03, Slide 4.
A function $f:A \rightarrow B$ 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.
Formally, $f:A \rightarrow B$ is an injection iff for any $x_0$, $x_1$ $\in A$, if $f(x_0) = f(x_1)$, then $x_0=x_1$.
Source: Lecture 08, Slide 32.
All input strings of a Turing Machine are written in the input alphabet $\sum$.
Source: Lecture 18, Slide 9.
An instantaneous description (ID) of a Turing machine is a string representation of the TM's tape, state and tape head location
Source: Lecture 20, Slide 11.
An integer is a number with no decimal part (..., -2, -1, 0, 1, 2, ...). The set of all integers is denoted $\mathbb{Z}$.
Source: Lecture 00, Slide 22.
The intersection of two sets $A$ and $B$, denoted $A \cap B$, is the set of all elements contained in $A$ and contained in $B$.
Source: Lecture 00, Slide 31.
See Rational.
An undirected graph $G = (V, E)$ with no self-loops (edges from a node to itself) is called $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 49.
The language of an automaton is the set of strings that the automaton accepts. If $D$ is an automaton, we denote the language of $D$ as $\mathcal{L}(D)$.
$\mathcal{L}(D)$ = { $w$ $\in$ $\sum$* | $D$ accepts $w$ }.
Source: Lecture 12, Slide 51.
The language of a CFG G with alphabet $\sum$ and start symbol S is:
$\mathcal{L}(G)$ = { $w$ $\in$ $\sum$* | $S$ $\rightarrow$* $w$ }.
Source: Lecture 17, Slide 10.
A lemma is a smaller result proven to help establish a larger result.
Source: Lecture 01, Slide 47.
The length of a cycle is the number of edges in that cycle.
Source: Lecture 05, Slide 26.
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 05, Slide 23.
A literal in propositional logic is a variable or its negation
Source: Lecture 28, Slide 8.
See Logical conjunction
$p \land q$ is true if both $p$ and $q$ are true (inclusive OR) Also called Logical OR
Source: Lecture 10, Slide 13.
In propositional logic, connectives encode how propositions are related, such as "If you liked it, then you should have put a ring on it."
Source: Lecture 10, Slide 11.
$p \lor q$ is true if at least one of $p$ or $q$ are true (inclusive OR) Also called Logical OR
Source: Lecture 10, Slide 13.
If two propositional logic statements $\phi$ and $\psi$ always have the same truth values as one another, they are called logically equivalent. We denote this by $\phi \equiv \psi$.
Source: Lecture 10, Slide 100.
A logical operator is an operator that takes in a number of bits and produces a bit.
Source: Lecture 01, Slide 33.
$\lnot p$ is true if and only if $p$ is false. Also called Logical NOT
Source: Lecture 10, Slide 13.
See Logical negation
See logical disjunction
A TM $M$ loops infinitely (or just loops) a string $w$ if it enters the neither the accept state nor the reject state when run on $w$.
Source: Lecture 19, Slide 21.
A mapping from $A$ to $B$ is a function $f$ from $A$ to $B$.
Source: Lecture 08, Slide 25.
A natural number is a nonnegative integer (0, 1, 2, 3, ...). The set of all natural numbers is denoted $\mathbb{N}$.
Source: Lecture 00, Slide 21.
The natural numbers can be defined inductively as seen in Lecture 03, Slide 62.
$\lnot \forall x. \phi \equiv \exists x. \lnot \phi$
$\lnot \exists x. \phi \equiv \forall x. \lnot \phi$
Source: Lecture 11, Slide 104.
An NFA is a Nondeterministic Finite Automaton. It's conceptually similar to a DFA, but equipped with the vase power of nondeterminism.
Source: Lecture 13, Slide 21.
A graph consists of a set of nodes connected by edges.
Source: Lecture 05, Slide 12.
A model of computation is nondeterministic if the computing machine may have multiple decisions that it can make at one point.
Source: Lecture 13, Slide 22.
A nondeterministic Turing machine is a variant on a Turing machine where there can be any number of transitions for a given state/tape symbol combination.
Source: Lecture 19, Slide 34.
An integer $n$ is odd if there exists an integer $k$ such that $n = 2k + 1$.
Source: Lecture 01, Slide 9.
An ordered pair $(a, b)$ is a pair of elements in a specific order: $(0, 1) \neq (1, 0)$. Two ordered pairs are equal iff each of their components are equal.
Source: Lecture 05, Slide 17.
A tree encoding the steps in a derivation
Source: Lecture 17, Slide 33.
A binary relation $R$ is a partial order over a set $A$ iff it is
Source: Lecture 07, Slide 29.
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 \leq k \leq n – 1$.
Source: Lecture 05, Slide 23.
A piecewise function is a function with different rules applying to different elements. Example:
$$ f(n) = \begin{cases} n/2 & \text{if }n\text{ is even}\\ (n+1)/2 & \text{otherwise} \end{cases} $$
Source: Lecture 08, Slide 30.
The pigeonhole principle states that given $m$ objects (pigeons) to place in $n$ bins (holes), if $m > n$, then there exists a bin with more than object in it.
Source: Lecture 02, Slide 23.
A graph is called a planar graph iff there is some way to draw it in a 2D plane without any of the edges crossing.
Source: Lecture 06, Slide 42.
The power set of a set $S$, denoted $\wp(S)$, is the set of all subsets of $S$.
Source: Lecture 00, Slide 45.
In first-order logic, predicates describe the properties of objects. Predicates can take any number of arguments, but each predicate has a fixed number of arguments (called its arity) Applying a predicate to arguments produces a proposition, which is either true or false.
Source: Lecture 10, Slide 134.
If (for some $P(n)$) $P(0)$ is true and for any $n \in \mathbb{N}$ we have $P(n) \rightarrow P(n+1)$, then for any $n \in \mathbb{N}$, $P(n)$ is true.
Source: Lecture 04, Slide 3.
See principle of complete induction.
The following properties hold for the connectivity relation $\leftrightarrow$:
Source: Lecture 06, Slide 8.
A proof by cases is a proof that branches off into different parts based on a set of possible options.
Source: Lecture 01, Slide 38.
A set $S$ is a proper subset of a set $T$ (denoted $S \subset T$) if $S \subseteq T$ and $S \ne T$.
Source: Lecture 00, Slide 44.
A proposition is a statement that is, by itself, either true or false.
Source: Lecture 10, Slide 05.
Propositional logic is a mathematical system for reasoning about propositions and how they relate to one another.
Source: Lecture 10, Slide 11.
In propositional logic, each proposition is represented by a propositional variable. (usually represented as lower-case letters) Each variable can take one one of two values: true or false.
Source: Lecture 10, Slide 12.
If
Source: Lecture 04, Slide 26.
In first-order logic, quantifiers allow us to reason about multiple objects simultaneously. A quantifier is a statement that expresses that some property is true for some or all choices that could be made.
Source: Lecture 11, Slide 14.
A rational number is a number $r$ that can be written as $r = \dfrac{p}{q}$ where $p$ and $q$ are integers and $q \neq 0$. A number that is not rational is irrational.
Source: Lecture 02, Slide 38.
A real number is a number measuring an arbitrary quantity. $e$, $\pi$, and $\sqrt{2}$ are all real numbers. The set of all real numbers is denoted $\mathbb{R}$.
Source: Lecture 00, Slide 22.
RE is the set of all recognizable languages.
Source: Lecture 19, Slide 22.
A language $L$ is recognizable iff it is the language of some TM.
Source: Lecture 19, Slide 22.
A binary relation $R$ over a set $A$ is reflexive iff for all $x \in A$, the relation $xRx$ holds.
Source: Lecture 07, Slide 9.
See Binary Relation.
A language $L$ is called a regular language iff there exists a DFA $D$ such that $\mathcal{L}(D)$ = $L$
Source: Lecture 13, Slide 9.
A TM $M$ rejects a string $w$ if it enters a reject state when run on $w$. $M$ does not reject $w$ if it either accepts $w$ or loops on $w$.
Source: Lecture 19, Slide 21.
A propositional logic formula $\phi$ is called satisfiable if there is some assignment to its variables that makes it evaluate to true.
Source: Lecture 28, Slide 7.
An assignment of true and false to the variables of a propositional logic formula $\phi$ that makes it evaluate to true is called a satisfying assignment.
Source: Lecture 28, Slide 7.
A binary operator $\ast$ with identity element $z$ is called self-inverting when for any $a$, we have $a \ast a = z$.
Source: Lecture 01, Slide 41.
Sentences in first-order logic can be constructed from predicates applied to objects.
Source: Lecture 10, Slide 135.
A set is an unordered collection of distinct objects, which can be anything, including other sets.
Source: Lecture 00, Slide 13.
Set-builder notation is a way to describe an arbitrary set by describing a rule by which its elements should be chosen.
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 05, Slide 27.
A simple path in a graph is a path that does not revisit any nodes or edges.
Source: Lecture 05, Slide 27.
A $string$ is a finite sequence of characters drawn from some alphabet.
Source: Lecture 12, Slide 21.
A set $A$ is a subset of $B$ (denoted $A \subseteq B$) when every element of $A$ is also an element of $B$.
Source: Lecture 00, Slide 42.
A subroutine of a Turing Machine is a small set of states in the TM such that they perform a small computation.
Source: Lecture 18, Slide 26.
A function $f:A \rightarrow B$ is called surjective (or onto) if each element of the codomain has at least one element of the domain that maps to it.
Formally, $f:A \rightarrow B$ is a surjection iff for every $b \in B$, there exists at least one $a \in A$ such that $f(a)=b$.
Source: Lecture 08, Slide 34.
The symmetric difference of two sets $A$ and $B$, denoted $A \triangle B$, is the set of all elements that belong to exactly one of $A$ and $B$.
Source: Lecture 00, Slide 34.
A binary relation $R$ over a set $A$ is called symmetric iff for all $x, y \in A$, if $xRy$, then $yRx$.
Source: Lecture 07, Slide 11.
A tape alphabet $\Gamma$, where $\sum \subseteq \Gamma$. The tape alphabet contains all symbols that can be written to the tape.
Source: Lecture 18, Slide 9.
The tape head of a Turing Machine can read and write a single memory cell at a time
Source: Lecture 18, Slide 7.
A binary relation $R$ over a set $A$ is called total iff for any $x \in A$ and $y \in A$, at least one of $xRy$ or $yRx$ is true.
Source: Lecture 07, Slide 33.
A binary relation $R$ over a set $A$ is called a total order iff it is a partial order and it is total.
Source: Lecture 07, Slide 33.
A binary relation $R$ over a set $A$ is called transitive iff for all $x, y, z \in A$, if $xRy$ and $yRz$, then $xRz$.
Source: Lecture 07, Slide 13.
The symbol $\top$ is a value that is always true.
Source: Lecture 10, Slide 47.
A finite automaton equipped with an infinite tape as its memory. It consists of 3 parts:
Source: Lecture 18, Slide 8.
The union of two sets $A$ and $B$, denoted $A \cup B$, is the set of all elements contained in $A$ or contained in $B$.
Source: Lecture 00, Slide 30.
A statement of the form $\exists!x. \psi$. asserts that for some unique choice of $x$ in our domain, $\psi$ is true.
Source: Lecture 12, Slide 10.
A graph in which the edges connect two nodes, with no "from" node or "to" node. You can also think of them as directed graphs where each edge goes both ways.
Source: Lecture 05, Slide 14.
A statement of the form $\forall x. \psi$ asserts that for every choice of $x$ in our domain, $\psi$ is true.
Source: Lecture 11, Slide 18.
There is a Turing machine $U_{TM}$ called the universal Turing machine that, when run on $\langle M, w\rangle$, where $M$ is a Turing machine and $w$ is a string, simulates $M$ running on $w$.
Source: Lecture 21, Slide 8.
A universal statement is a statement of the form "for all $x$, $P(x)$ is true". Remember, the negation of a universal statement is an existential statement.
Source: Lecture 01, Slide 29.
An unordered pair is a set $\{a, b\}$ of two elements (remember that sets are unordered).
Source: Lecture 01, Slide 17.
A statement is vacuously true if it is true because it does not apply to anything.
Source: Lecture 00, Slide 43.
A Venn Diagram is a picture representing the overlap of two sets.
Source: Lecture 00, Slide 27.
See node.
The XOR operator (denoted $\oplus$) is a logical operator that takes in two bits and returns 0 if they are the same and 1 if they are different.
Source: Lecture 01, Slide 34.