# Math 55 Definition List ## Lecture 1: Propositional Logic 1. A *proposition* is a declarative sentence that is either true or false but not both. A proposition has a *truth value* which is either $T$ or $F$. 2. A letter used to denote a proposition is called a *propositional variable*. 3. If $p$ is a proposition, the *negation* of $p$, denoted $\lnot p$, is the proposition "it is not the case that $p$". The truth value of $\lnot p$ is the opposite of that of $p$. 4. If $p$ and $q$ are propositions, the *conjunction* of $p$ and $q$ (denoted $p\land q$) is the proposition "p and q." Its truth value is $T$ when both $p$ and $q$ are $T$, and it is $F$ otherwise. 5. If $p$ and $q$ are propositions,he *disjunction* of $p$ and $q$ is the proposition "p or q". Its truth value is $T$ when at least one of $p$ or $q$ is $T$, and $F$ if both $p$ and $q$ are $F$. 7. If $p$ and $q$ are propositions, the *conditional* $p\rightarrow q$ is the proposition "if $p$ then $q$". Its truth values are given by the following *truth table* (which lists its truth values in terms of those of $p$ and $q$): [see Table 5 in Rosen] The *converse* of $p\rightarrow q$ is $q\rightarrow p$. 8. A *compound proposition* consists of logical operations (the four listed above) applied to propositions or propositional variables, possibly with parentheses. The truth value of a compound proposition can be mechanically determined given the truth values of its constituents. ## Lecture 2: Propositional Functions, Quantifiers, (begin) Rules of Inference 1. A compound proposition which is always true (regardless of the truth values of constituent propositions) is called a *tautology*. A compound proposition that is always false is called a *contradiction*. A compound proposition that is neither is called *contingent*. 2. Two compound propositions $c_1,c_2$ are *logically equivalent*, denoted $c_1\equiv c_2$, if they have the same truth values for all truth values of their propositional variables (and all domains of their propositional functions). 3. The *biconditional* $p\leftrightarrow q$ is the proposition $(p\rightarrow q)\land (q\rightarrow p)$ (read "if and only if"). Two propositions $p$ and $q$ are logically equivalent if $p\leftrightarrow q$ is a tautology. This is denotes $p\equiv q$. Logically equivalent propositions have the same truth table. 4. The *contrapositive* of a conditional $p\rightarrow q$ is $\lnot q\rightarrow \lnot p$. The contrapositive is logically equivalent to the original conditional. 5. A *propositional function* is a statement containing one or more variables (taking values in an implicitly or explicitly specified domain) which becomes a proposition when each variable is instantiated with a value. 6. The *universal quantification* of $P(x)$ is the proposition "For all $x$ in the domain, $P(x)", denoted$\forall xP(x)$. The *existential quantification* of$P(x)$is the proposition "There exists an$x$in the domain such that P(x)", denoted$\exists xP(x)$. 7. A variable appearing with a quantifier is called *bound*. A statement in which every variable appearing in a propositional function is bound is a proposition; otherwise it is not a proposition. ## Lecture 3: Rules of Inference for Quantifiers, Direct Proof, Contrapositive, Contradiction 1. An *argument* is a sequence of propositions each of which is a premise (i.e., an assumption) or a conclusion (i.e., follows from previous propositions via rules of inference). 2. An integer$n$is even if there exists an integer$k$such that$n=2k$. An integer$n$is odd if there exists an integer$k$such that$n=2k+1$. 3. A real number$x$is rational if there exist integers$p$and$q\neq 0$such that$x=p/q$. ## Lecture 4: More Proofs, Sets 1. A *set* is an unordered collection of objects which are called its *elements*. A set *contains* its elements, denoted$x\in A$. For every$x$, the statement "$x\in A$" must be a proposition (otherwise$A$is not a set). 2. The set with no elements is called the *empty set*, denoted$\varnothing$. 3. Two sets$A$and$B$are *equal*, denoted$A=B$, if they have the same elements, i.e.$\forall x(x\in A\leftrightarrow x\in B)$. 4. If$A$and$B$are sets,$A$is a subset of$B$, denoted$A\subseteq B$. if every element of$A$is an element of$B$, i.e.,$\forall x (x\in A \rightarrow x\in B)$. 5. If$A$is a set, the *power set* of$A$, denoted$\mathcal{P}(A)$, is the set of all subsets of$A$: $$\mathcal{P}(A)=\{S:S\subseteq A\}.$$ 6. If$A$and$B$are sets, their *union* is $$A\cup B = \{x:x\in A\lor x\in B\},$$ their *intersection* is $$A\cap B = \{x:x\in A\land x\in B\},$$ and their *difference* is $$A-B = \{x:x\in A\land \lnot x\in B\}.$$ If$A$is a subset of a *universe*$U$(which is just another set), then the *complement* of$A$(with respect to$U)$is $$\overline{A}= \{x\in U:x\notin A\}=U-A.$$ ## Lecture 5: Functions 1. The *cartesian product* of two sets$A$and$B$is the set of ordered pairs$(a,b)$such that$a\in A$and$b\in B$. It is denoted $$A\times B = \{(a,b):a\in A\land b\in B\}.$$ 2. If$A$and$B$are nonempty sets, a *function* from$A$to$B$is a rule which assigns exactly one element of$B$to each element of$A$. This assignment is denoted$f(a)=b$. If$f$is a function from$A$to$B$we write$f:A\rightarrow B$.$A$is called the *domain* of$f$and$B$is called the *codomain*. 3. A function$f:A\rightarrow B$is *onto* (*surjective*) if for every$b\in B$there exists an$a\in A$such that$f(a)=b$. 4. A function$f:A\rightarrow B$is *one to one* (*injective*) if for every$a_1,a_2\in A$,$f(a_1)=f(a_2)$implies$a_1$=$a_2$. (equivalently,$a_1\neq a_2$implies$f(a_1)\neq f(a_2)$). 5. A function$f:A\rightarrow B$is called a *bijection* if it is one to one and onto. 6. The composition of$f:B\rightarrow C$and$g:A\rightarrow B$is the function$f\circ g:A\rightarrow C$defined by$f\circ g(a)=f(g(a))$. 7. If a function is a bijection, then the function$f^{-1}(b)$which assigns to be the unique element$a\in A$mapping to$b$is called its inverse. 8. If$f:A\rightarrow B$and$S\subseteq A$then the *image* of$S$is$f(S) = \{b\in B:\exists a\in S s.t. f(a)=b\}$. The *inverse image* (preimage) of$S\subseteq B$is$f^{-1}(S) = \{a\in A:f(a)\in S\}$. The *range* of$f$is$f(A)$.$\newcommand{\Z}{\mathbb{Z}}$## Lecture 6: Cardinality 1.$\Z_+$denotes the set of positive integers. 2. A set$A$is called *finite* if it is the empty set or if it has exactly$n$elements for some$n\in \Z_+$. The *cardinality* of$A$, denoted$|A|$, is$n$. 3. Two sets$A$and$B$*have the same cardinality*, denoted$|A|=|B|$, if there is a bijection$f:A\rightarrow B$(also called a "one to one correspondence" in this context). If there is an injection$f:A\rightarrow B$we say that$|A|\le |B|$. If$|A|\le |B|$but$|A|\neq|B|$then we write$|A|<|B|$. 4. An infinite set with$|A|=|\Z_+|$is called *countable*. An infinite set which is not countable is called *uncountable*. 5. A function$f:\Z_+\rightarrow A$is called a *sequence*. If$f$is a bijection the sequence is called an *enumeration* of$A$. Theorems: The integers and rationals are countable. The interval$(0,1)$is uncountable. ## Lecture 7: Division, Modular Arithmetic 1. If$a\neq 0$and$b$are integers then$a$*divides*$b$(denoted$a|b$) if there exists an integer$k$such that$b=ka$. 2. ("Division Algorithm") If$a$is an integer and$d\in\Z_+$then there are unique integers$q,r$such that$a=dq+r$and$0\le r<d$.$q$is called the *quotient* and$r$is called the *remainder*, sometimeds denoted$r=a$**mod**$d$. 2. (Axiom) Well-ordering principle: Every nonempty subset of$\Z_{\ge 0}$has a least element. 3. For$a,b\in\Z$we say$a\equiv b (mod m)$if$m|(b-a)$. 4. If$b\in\Z_+$and$a\in \Z_+$then there is a unique way to write$a$as a sum of powers of$b$. This is called the *base b expansion* of$a$. ## Lecture 8: Primes, GCD, and Bezout's Theorem 1. An integer$n>1$is called *prime* if it has no divisors other than one and itself. An integer$n>1$is called *composite* if it is not prime. 2. If$a,b$are integers, not both zero, then the *greatest common divisor* of$a$and$b$, denoted$gcd(a,b)$is the largest$d\in \Z_+$such that$d|a$and$d|b$. Theorems in this lecture: Infinitude of Primes, Fundamental Theorem of Arithmetic, Bezout's theorem. ## Lecture 9: Inverses **Defn.**$\overline{a}$is an *inverse of$a$* modulo$m$if$a\overline{a}\equiv 1 (mod m)$. ## Lecture 10: Chinese Remainder Theorem, Cryptography ## Lectures 12/13: Induction, no definitions ## Lecture 14: Graphs, Paths, Circuits, Coloring A **graph** is a pair$G=(V,E)$where$V$is a finite set of **vertices** and$E$is a finite multiset of$2-$element subsets of$V$, called **edges**. If$E$has repeated elements$G$is called a *multigraph*, otherwise it is called a *simple graph*. We will not consider directed graphs or graphs with loops (edges from a vertex to itself). Two vertices$x,y\in V$are **adjacent** if$\{x,y\}\in E$. An edge$e=\{x,y\}$is said to be **incident with**$x$and$y$. The **degree** of a vertex$x$is the number of edges incident with it. A **path** of length$k$in$G$is an alternating sequence of vertices and edges $$x_0, e_1, x_1, e_2, \ldots, x_{k-1},e_k,x_k$$ where$e_i=\{x_{i-1},x_i\}\in E$for all$i=1\ldots k$. The path is said to *connect*$x_0,x_k$, *visit* the vertices$x_0,\ldots,x_k$, and *traverse* the edges$e_1,\ldots,e_k$. A path is called **simple** if it contains no repeated vertices. If$x_0=x_k$then the path is called a **circuit**. Note that in a simple graph (i.e., a graph with no multiple edges), a path is uniquely specified by the sequence of vertices$x_0,\ldots,x_k$(as there is only one possible choice of edge between each pair of consecutive vertices). A graph$G$is *connected* if for every pair of distinct vertices$x,y$of$G$, there is a path in$G$between$x$and$y$. A **k-coloring** of$G$is a function$f:V\rightarrow \{1,\ldots, k\}$such that$f(x)\neq f(y)$whenever$x$is adjacent to$y$. A graph is **$k-$colorable** if it has a$k$-coloring. (in class we did the case$k=2$) ## Lecture 15:$k$-coloring A graph$H=(W,F)$is a **subgraph** of$G$if$W\subseteq V$and$F\subseteq E$. If$W=V$then$H$is called a **spanning** subgraph of$G$. A **k-coloring** of$G$is a function$f:V\rightarrow \{1,\ldots, k\}$such that$f(x)\neq f(y)$whenever$x$is adjacent to$y$. **Defn.** If$G=(V,E)$is a graph, a subset$S\subseteq V$is called a *clique* if$xy\in E$for every pair of distinct vertices$x,y\in S$.$S$is called an *independent set* if$xy\notin E$for every pair of distinct vertices$x,y\in S$. **Defn.** If$G=(V,E)$is a graph, a subgraph$H$of$G$is called a *connected component* of$G$if$H$is connected and *maximal*, i.e., it is not possible to add any vertices or edges to$H$while keeping it connected (formally: if$H'$is a subgraph of$G$such that$H\neq H'$and$H$is a subgraph of$H'$, then$H'$must be disconnected.). ## Lectures 16-17: See the Graph Theory Notes ## Lecture 18: Counting An ordering of$n$distinct elements is called a *permutation*. An ordered sequence of$r$distinct objects chosen from$n$distinct objects is called an *r-permutation*. The number of$r-$permutations of$n$objects is denoted$P(n,r)$. An unordered set of$r$distinct objects chosen from$n$distinct objects is called an *r-combination*. The number of$r-$combinations of$n$objects is denoted$\binom{n}{k}$or$C(n,r)$. ## Lecture 19: Permutations and Combinations with repetitions No definitions. ## Lecture 20: Labeled and Unlabeled Tokens in Boxes, Recurrences A *recurrence relation* is a recursive definition of a sequence$(a_0,a_1,a_2,\ldots)$. ## Lecture 21: Pigeonole Principle Generalized Pigeonhole principle: If$N$objects are placed in$k$boxes, then at least one box contains at least$\lceil N/k\rceil$objects. ## Lecture 22: Probability$\renewcommand{\P}{\mathbb{P}}\newcommand{\R}{\mathbb{R}}$An *experiment* is a well-defined procedure with a set of possible *outcomes*. An *outcome* is a complete description of all relevant features of the result of an experiment. The set of all outcomes is called the *sample space*$S$. An *event* is a subset of the sample space$E\subseteq S$. A *probability space* consists of a sample space$S$along with a function$p:S\rightarrow \R$satisfying$p(s)\in [0,1]$for all$s\in S$and$\sum_{s\in S}p(s) = 1$. The *probability* of an event is $$\P(E)=\sum_{s\in E}p(s).$$ ## Lecture 23: Conditional Probability and Independence Two events$E,F\subseteq S$are *disjoint* if$E\cap F=\emptyset$. If$E,F$are events and$\P(F)>0$then the *probability of$E$given$F$* (also called$E$conditional on$F$) is: $$\P(E|F)=\frac{\P(E\cap F)}{P(F)}.$$ Two events$E$and$F$are *independent* if $$\P(E\cap F) = \P(E)\P(F).$$ If$\P(F)>0$this is equivalent to$\P(E|F)=\P(E)$and if$\P(E)>0$this is equivalent to$\P(F|E)=\P(F)$. ## Lecture 24: Random Variables and Linearity of Expectation$\newcommand{\E}{\mathbb{E}}$A *random variable* on a probability space$S,p$is a function$X:S\rightarrow \R$. The *expectation* of a random variable is defined as $$\E X = \sum_{s\in S} p(s) X(s).$$ This may be equivalently rewritten as a sum over the range of$X$: $$\E X = \sum_{r\in range(X)} r\cdot \P(X=r).$$ ## Lecture 25: Examples of Distributions If$X:S\rightarrow \R$is a random variable on a probability space, the function$p_X(r)=\P(X=r)$is called the *distribution* of the random variable. A *Bernoulli* random variable with bias$q\in [0,1]$has distribution$\P(X=0)=q, \P(X=1)=1-q$. A *Binomial* random variable with bias$q\in [0,1]$and$n$trials has distribution$\P(X=k)=\binom{n}{k}q^k(1-q)^{n-k}$for$0\le k\le n$. A *Geometric* random variable with success probability$q$has distribution$\P(X=k)=(1-q)^{k-1}q$for$k=1,2,\ldots$. ## Lecture 26: Algebra with random variables, Variance If$X,Y:S\rightarrow \R$are random variables, their *sum* is defined as$(X+Y)(s)=X(s)+Y(s)$. If$c$is a real number, the scalar multiple$cX$is defined as$(cX)(s) = c\cdot X(s)$. The *product* is defined as$(XY)(s) = X(s)Y(s)$. Notice that doing algebra on random variables means doing algebra on their outputs''. Two random variables$X,Y$are *independent* if for all$r_1,r_2\in\R$, the events$\{X=r_1\}$and$\{Y=r_2\}$are independent. This condition implies that$\E XY = \E X \E Y$, which is not true in general. The *variance* of a random variable is defined as$V(X) = \E (X-\mu_X)^2$here$\mu_X=\E X$. ## Lecture 27: Concentration Inequalities Markov's Inequality: If$Y$is a nonnegative random variable, then for every$t>0$: $$\P(Y\ge t)\le \frac{\E Y}{t}.$$ Chebyshev's Inequality: If$X$is any random variable, then for every$t>0\$: $$\P(|X-\E X|\ge t)\le \frac{V(X)}{t^2}.$$