Posted onEdited onInComputer Science Symbols count in article: 31kReading time ≈28 mins.
Notes of COSI 29A
Discrete
Mathematics: An Open Introduction Notes
Mathematical Statements Ch 0.2
A statement is any declarative sentence which is either true or
false
A statement is atomic if it cannot be divided into smaller
statements, otherwise it is called molecular
Logical connective: connect simpler statements to build more
complicated one
Binary connective: used to connect two statements, and,
or, if then, if and only if
Uniary connective: used for only one statement,
not
Priority: not > and > or > xor > implies > iff
Truth value
true, false
The truth value of a molecular statement is determined on the truth
of its atomic statements and the connectives
Propositional variable(aka sentential variable), used to stand
for(usually atomic) statements
The content of the statement does not matter, only the truth value
matters
Notation: P, Q, R
More notations
Conjunction: P and Q, \(P \land
Q\)
Disjunction: P or Q, \(P \lor
Q\)
Implication/Condition: if P then Q/P only if Q, \(P \rightarrow Q\), P is
hypothesis/antecedent, Q is conclusion/consequent
Biocondition: P if and only if Q, \(P
\leftrightarrow Q\)
Negation: not P, \(\neg P\)
Truth conditions
\(P \rightarrow Q\): if P is true,
then true if Q is true, otherwise false; if P is false, then true for
always. Another way, if Q is true, then always true
If a and b are legs of a right triangle with hypotenuse c, then
\(a^2+b^2=c^2\)
Converse and Contrapositive
Conver of \(P \rightarrow Q\) is
\(Q \rightarrow P\), the converse and
the original statement can have different truth values
Contrapositive statement of \(P
\rightarrow Q\) is \(\neg Q \rightarrow
\neg P\), the contrapositive and the original statement have the
same truth value
Implication Equivalence
A implies B
A only if B
if A then B
B if A
B when A
A is sufficient for B
B is necessary for A
Predicates and Quantifiers
A boolean function with one or more variables is not a statement, it
is ap predicate
Two quantifiers: existential and universal
Existential: \(\exists\), there
exists/there is, \(\exists x(x<0)\)
means there is a number that is less than 0
Universal: \(\forall\), for
all/every, \(\forall x(x \geq 0)\)
means every number that is greater than or equal to 0
Negation:
\(\neg \exists x(P(x))\) is
equivalent to \(\forall x(\neg
P(x))\)
\(\neg \forall x(P(x))\) is
equivalent to \(\exists x(\neg
P(x))\)
Implications quantifiers: in order for a predicate to become a
statement, we implicitly assume the variable is universally
quantified
Propositional Logic Ch 3.1
A proposition is a statement, propositional logic studies the ways
statements can interact with each other
We can use truth table to determine the truth value of a
proposition
Logically equivalence: if both statements are both true or both
false(they have the same truth value), then they are logically
equivalent
De Morgan's Laws
\(\neg (P \land Q)\) is equivalent
to \(\neg P \lor \neg Q\)
\(\neg (P \lor Q)\) is equivalent
to \(\neg P \land \neg Q\)
Implications are disjunctions: \(P
\rightarrow Q\) is equivalent to \(\neg
P \lor Q\)
Double negation: \(\neg \neg P\) is
equivalent to P
Negation of an implication: \(\neg(P
\rightarrow Q)\) is equivalent to \(P
\land \neg Q\)
Decutsion: given a set of true premises, the conclusion should be
true
Predicate logic extends propositional logic
Proofs Ch 3.2
Proof by contradiction
Proof is an argument. The argument is valid so conclusion must be
true if premises are true
To prove P is true, we prove \(\neg P
\rightarrow Q\) is true, where Q is false, this implies P is
true
Direct Proof
Proof by contrapositive: prove \(P
\rightarrow Q\) using \(\neg Q
\rightarrow \neg P\)
Pigeonhole Principle: If more than n pigeons fly into n pigeon
holes, then at least one pigeon hole will contain at least two
pigeons
Proof by (counter) example
For existential statement, we can prove by finding one example
In order for a statement to be not valid, find an example where its
negation is true
Proof by cases: the statement is true for all cases
Sets Ch 0.3
Introduction
A set is an unordered collection of objects
Two sets are equal if they contain the same elements
Notation
A is the set containing the elements 1, 2 and 3: \(A =\{1,2,3\}\)
a is an element of set A: \(a \in
A\)
a is not an element of set A: \(a \notin
A\)
even numbers: \[ \begin{align*}A
&= \{0,2,4,6,\dots\} \\ &= \{x \in \mathbb{N}: \exists n \in
N(x=2n)\} \\ &=\{x \in \mathbb{N}: \text{x is even}\}
\end{align*}\]
The notation is often called the set builder notation
A function is a rule that assigns each input exactly one output, the
output is the image of the input, the set of inputs is called the
domain, the set of all allowable outputs is called the codomain, the set
of actual outputs is called the range
Notation: \(f: X \rightarrow Y\),
the function with name \(f\), domain
\(x\), and codomain \(Y\)
Describing functions
Rule of four: each function can be described in four ways,
algebracially(a formula), numerically(a table), graphically, or in
words
Using an explicit formula to calculate the image of any element in
the domain is a great way to describe a function, and these explicit
rules are closed formulas for the function
Surjections, Injecetions, and Bijections
Surjection: the function is onto or the function maps the domain
onto the codomain, the codomain is just the range
\(\forall y \in Y, \exists x \in X,
\text{s.t.} y = f(x)\)
Injection: for one element in the codomain, it can be the image of
at most one element in the domain, then the function is one-to-one or
injective
Notice: \(f^{-1}(y)\) is the
complete inverse image of \(y\) under
\(f\), it is not the image of \(y\) under \(f^{-1}\), because \(f^{-1}\) may not exist
Some results
if \(g \circ f\) is injective: then
f is injective. if \(g \circ f\) is
surjective, then g is surjective
if \(x_1 = x_2, \text{and} f(x_1) =
f(x_2)\), we can prove \(x_1 =
x_2\)
for every \(z \in C\), there is
\(x \in A\), then \(y = f(x) \in B\)
Consider \(A = \{1\}, B = \{1,2\},C=\{1\},
f(1)=1,g(1)=g(2)=1\), then f is not surjective, g is not
injective
if f and g are injective/surjective/bijective, so is \(g \circ f\)
Generally, \(|A| \geq |f(A)|\),
when f is injective, we have \(|A| =
|f(A)|\)
Generally, we don't know \(|B| \text{and}
|f^{_1}(B)|\). If f is injective, \(|B|
\geq |f^{-1}(B)|\), if f is surjective, \(|B| \leq |f^{-1}(B)|\), if f is bijective,
\(|B| = |f^{-1}(B)|\)
Additive principle: if event A can occur in m ways, and event B can
occur in n disjoint ways, then the event A or B can occur in m + n
ways
Multiplicative principle: if event A can occur in m ways, and each
possibility for A allows for exactly n ways for event B, then the event
A and B can occur in m * n ways
Additive principle with sets: Given two sets A and B, if \(A \cap B = \emptyset\), then \(|A \cup B| = |A| +|B|\)
Cartesian Product: Givens sets A and B, we can form the set \(A \times B = \set{(x,y): x \ A \text{ and } y \in
B}\)
Multiplicative principle with sets: Given two sets A and B, we have
\(|A*B| = |A|*|B|\)
The integer lattice is the set of all points in the Cartesian plane
for which both the x and y coordinates are integers
A lattice path is one of the shortest possible paths connecting two
points on the lattice, moving only horizontally and vertically
Binomial Coefficients
Binomial coefficients are the coefficients in the expanded version
of a binomial
For each integer \(n \geq 0\) and
integer k with \(0 \leq k \leq n\)
there is a number \(\binom{n}{k}\),
reads n choose k
\(\binom{n}{k} = |B^{n}_{k}|\)
\(\binom{n}{k}\) is the number of
subsets of a set of size n each with cardinality k
\(\binom{n}{k}\) is the number of
lattice paths of length n containing k steps to the right
\(\binom{n}{k}\) is the coefficient
of \(x^k y^{n-k}\) in the expansion of
\((x+y)^k\)
\(\binom{n}{k}\) is the numebr of
ways to select k objects from a total of n objects
Pascal's Triangle
Combinations and Permutations Ch 1.3
Permutation is a possible rearrangement of objects
There are \(n! =
n*(n-1)*(n-2)*\dots*2*1\) permutations of n(distinct)
elements
k-permutation of n elements: \(P(n,
k)\), the number of ways to arrange k objects chosen from n
distinct objects: \[P(n,k) =
\frac{n!}{(n-k)!} = n*(n-1)*\dots*(n-(k-1))\]
Closed formula for \(\binom{n}{k}\): \[\binom{n}{k} = \frac{n!}{(n-k)!k!} =
\frac{n*\dots*(n-(k-1))}{k*\dots*1}\]
Find a counting problem you will be able to answer in two ways.
Explain why one answer to the counting problem is A
Explain why the other answer to the counting problem is B
Since both A and B are the answers to the same question, we must
have A = B
Sequences
Describing Sequences Ch 2.1
A sequence is simply an ordered list of numbers
Notation: \(a_0, a_1,\dots, \text{ or }
(a_n)_{n\in \mathbb{N}} \text{ or } (a_n)_{n \geq 0} \text{ or simply }
(a_n)\). If we omit \(a_0\),
then the sequence is \((a_n)_{n \geq
1}\). n is called index
Closed formula: a closed formula for \((a_n)_{n\in \mathbb{N}}\) is a formula for
\(a_n\) using a fixed finite number of
operations on n
Recursive definition: a recursive definition(sometimes called an
inductive definition) for a sequence \((a_n)_{n\in \mathbb{N}}\) consists of a
recurrence relation: an equation relating a term of the sequence to
previous terms and an initial condition: a list of a few terms of the
sequence
Common sequences
Square numbers: \(a_n = n^2\)
Triangle numbers: \(a_n =
\frac{n(n+1)}{2}\)
The fibonacci numbers: \(F_n=F_{n-1}+F_{n-2}\) with \(F_1 = F_2=1\)
Arithmetic and Geometric Sequences Ch 2.2
If the terms of a sequence differ by a constant, we say the sequence
is arithmetic. If the initial term \(a_0\) of the sequence is a and the common
difference is d, then we have recursive definition: \(a_n=a_{n-1}+d\) with \(a_0=a\), closed formula: \(a_n = a +dn\)
A sequence is called geometric if the ratio between successive terms
is constant. Suppose the initial term \(a_0\) is an the common ratio is r, then we
have recursive definition: \(a_n=ra_{n-1}\) with \(a_0=a\), closed formula: \(a_n=a*r^n\)
For sequence \((a_n)_{n\geq 0}\),
its first difference is \((a_n - a_{n-1})_{n
\geq 1}\), its second difference is \(((a_n - a_{n-1})-(a_{n-1}-a_{n-2}))_{n \geq
2}\)
If the \(kth\) order difference of
a sequence is constant, then we say a sequence is a \(\Delta^{k}\)-constant sequence
If a sequence is arithmetic, then it is \(\Delta^{1}\)-constant
Finite difference
The closed formula for a sequence will be a degree \(k\) polynomial if and only if the sequence
is \(\Delta^k\)-constant
You can try differencing the sequence for some degrees, if the
difference consequence is constant, then you can use polynomial fitting
to find the closed form for the sequence
Solving Recurrence Relations Ch 2.4
Characteristic equations: Suppose \(a_n +
\alpha a_{n-1} + \beta a_{n-2} = 0\), its characteristic equation
is \(x^2+\alpha x+\beta = 0\)
If \(\gamma_1\) and \(\gamma_2\) are two distinct roots of the
characteristic eqution, then the solution to the recurrence relation is
\(a_n = a\gamma_1^{n} + b
\gamma_2^{n}\), where a and b are constants determined by the
initial conditions
If there is only one solution \(\gamma\) to the characteristic equation,
then the solution to the recurrence relation is \(a_n = a\gamma^{n} + bn \gamma^{n}\), where
a and b are constants determined by the initial conditions
Induction Ch 2.5
Induction Proof Structure: Let \(P(n)\) be the statement, to prove \(P(n)\) is true for all \(n \geq 0\), you must prove two facts:
Base case: Prove that \(P(0)\) is
true, you do this directly, this is often easy
Inductive case: Prove that \(P(k)
\rightarrow P(k+1)\) for all \(k \geq
0\). This is the proof of an if-then statement, so you can assume
\(P(k)\)(it's called the inductive
hypothesis) is true, you must then explain why \(P(k+1)\) is also true, given that
assumption
Then by the principle of mathematical induction, the statement \(P(n)\) is true for all \(n \geq 0\)
Strong induction proof structure: Let \(P(n)\) be the statement, to prove \(P(n)\) is true for all \(n \geq 0\), you must prove two facts:
Base case: Prove that \(P(0)\) is
true
Inductive case: Assume \(P(k)\) is
true, for all \(K < n\), prove that
\(P(k)\) is true
Some results
\(1+\dots+n=\frac{n(n+1)}{2}\)
\(1^2+\dots+n^2=\frac{n(n+1)(2n+1)}{6}\)
\(1^3+\dots+n^3=(\frac{n(n+2)}{2})^2\)
Consider the Riemann zeta function: \(\zeta(s) =
\sum\limits_{n=1}^{\infty}\frac{1}{n^s}\)
We have \(\zeta(s) * \Gamma(s) =
\int_{0}^{\infty}\frac{x^{s-1}}{e^x-1}dx\)
Definition: a graph is an ordered pair \(G
= (V,E)\) consisting of a nonempty set V (called the vertices)
adn a set E (called the edges) of two-element subsets of V
Isomorphic Graphs: a isomorphism between two graphs \(G_1\) and \(G_2\) is a bijection \(f: V_1 \rightarrow V_2\) between the
vertices of the graphs such that \(\set{a,
b}\) is an edge in \(G_1\) iff
\(\set{f(a), f(b)}\) is an edge in
\(G_2\). Two graphs are isomorphic if
there is an isomorphism between them. In this case we write \(G_1 \cong G_2\)
Subgraphs: \(G'=(V',E')\) is a subgraph of
\(G=(V, E)\), and write \(G' \subseteq G\), provided \(V' \subseteq V\) and \(E' \subseteq E\). \(G'=(V',E')\) is a induced
subgraph of \(G=(V, E)\), provided
\(V' \subseteq V\) and every edge
in E whose vertices are in \(V'\)
is also an edge in \(E'\)
Simple graph: no pairs of vertices is connected more thant once, and
no vertex is connected to itself. Other graphs are multigraphs
Connected graph: there is a path between any two vertices
Complete graph: if every pair of vertices are connected by a edge,
then the graph is complete
Degree of a vertex: number of edges emanating from a given vertex
Handshake Lemma: in any graph, the sum of the degrees of vertices in
the graph is always twice the number of edges, i.e. \(\sum\limits_{v \in V}d(v) = 2e\)
Proposition: in any graph, the number of vertices with odd degree
must be even
Mathematics for Computer
Science Notes
Logical Formulas Ch 3.1
Java uses && for and , || for
or
P xor Q notation: \(P \oplus
Q\)
Negation of P: \(\bar{P}\), or
\(\neg P\)
Validity: a valid formula is one which is always true
Satisfiability: a satisfiable formula is one which can sometimes be
true
A statement P is satisfiable iff its negation NOT(P) is not
valid
Distributive Law of And over OR: \(A \land
(B \lor C) = (A \land B) \lor (A \land C)\)
Distributive Law of OR over AND: \(A \lor
(B \land C) = (A \lor B) \land (A \lor C)\)
Proving Equivalences:
Approach 1: use truth table, there are \(2^N\) situations for \(N\) variables
Approach 2: use algebra to prove equivalence
SAT problem: the genereal problem of deciding whether a proposition
is satisfiable is called SAT
Inference Rules Ch 3.4
\((A \land B)\lor C \leftrightarrow (A
\lor C)\land (B \lor C)\)
\((A \lor B)\land C \leftrightarrow (A
\land C)\lor (B \land C)\)
\((A \land B) \leftrightarrow (B \land
A)\)
\((A \land B) \land C \leftrightarrow A
\land(B \land C)\)
\(\text{True} \land A \leftrightarrow
A\)
\(\text{False} \land A \leftrightarrow
\text{False}\)
\(A \land A \leftrightarrow
A\)
\(A \land \neg A \leftrightarrow
\text{False}\)
\(A \lor (\neg A) \leftrightarrow
\text{True}\)
\(\neg(A \land B) \leftrightarrow \neg A
\lor \neg B\)
\(\neg(A \lor B) \leftrightarrow \neg A
\land \neg B\)
In order for a predicate formula to be valid, it should be true all
across its domain
Valid assertion: \(\exists x, \forall y.
P(x,y) \rightarrow \forall y, \exists x. P(x,y)\)
Not valid assertion: \(\forall y, \exists
x. P(x,y) \rightarrow \exists x, \forall y. P(x, y)\) (This is
invalid because x and y may be related, so there is no such universal
x)
What is a Proof Ch 1
Logical Deductions
Example: a proof of P and a proof P implies Q is a proof of Q.
Antecedents: P, P implies Q, Conclusion/consequent: Q
Rule
P implies Q, and Q implies R => P implies R
NOT(P) implies NOT(Q) => Q implies P
Proving an implication: P implies Q
Method 1: assume P is true, then Q logically follows
Method 2: we prove the contrapositive, then use method 1 with the
contrapositive
Proving an if and only if
Method 1: prove each statement implies the other
Method 2: construct a chain of iffs
Proof by Cases
Proof by contradiction/ indirect proof: show that if a proposition
were false, then some flse fact would be true
In order to prove P: we use proof by contradiction, supopose P is
false, deduce something false, then there is a contradiction, then P
must be true
Sets Ch 4.1
Introduction: informally, a set is a bunch of elements
Some popular sets: \(\emptyset,
\mathbb{N}, \mathbb{Z}, \mathbb{Q}, \mathbb{R}, \mathbb{C}\)
Comparing and combining sets
\(\subseteq\): subset, \(\subset\): strict subset
\(x \in A \cup B \leftarrow x \in A \text{
or } x\in B\)
\(x \in A \cap B \leftarrow x \in A \text{
and } x\in B\)
\(x \in A \setminus B \leftarrow x \in A
\text{ and } x\notin B\)
\(B \subseteq \mathcal{P}(A)
\leftrightarrow B \subseteq A\)
Proving set equalities: to prove \(A =
B\), we need to prove \(A \subseteq B
\text{ and } B \subseteq A\)
Sequences Ch 4.2
A list of ordered eleemnts are called sequence
Use \(\lambda\) for empty
sequence
Functions Ch 4.3
A function assigns an element of one set, called the domain, to an
element of another set, called the codomain
Functions are often defined by formulas
Functions can be defined using tables
Image of set S under f: \(f(S) =
\set{f(x): \forall x \in S }\)
range of f: \(\text{range}(f) =
f(\text{domain of f})\)
Function Composition: for \(f: A
\rightarrow B\) and \(g: B \rightarrow
C\), the composition of g and f is \((g
\circ f): A \rightarrow C |(g \circ f)(x) = g(f(x))\)
Binary Relations Ch 4.4
Binary relations define relations between two objects
Definition: a binary relation R, consists of a set A called the
domain of R, and a set B called the codomain of R, and a subset of A*B
called the graph of R. R is said between A and B, or from A to B
Relation can be function, surjective, total, injective, or
bijective
If A is a finite set, the cardinality of A, written \(|A|\), is the number of elements in A
Definition
\(A \text{ surj }B
\leftrightarrow\) there is a surjective function from A to B
\(A \text{ inj }B \leftrightarrow\)
there is a injective function from A to B
\(A \text{ bij }B \leftrightarrow\)
there is a bijective function from A to B
Theorem: For finite sets A, B
\(A \text{ surj }B \leftrightarrow |A|\geq
|B|\)
\(A \text{ inj }B \leftrightarrow |A|\leq
|B|\)
\(A \text{ bij }B \leftrightarrow |A|=
|B|\)
For a finite with n elements, there are \(2^n\) subsets
Cardinality Rule Ch 14
Counting One Thing by Counting Another Ch 14.1
Bijection Rule: if there is a bijection between two things, then
they have the same size
Counting Sequences Ch 14.2
Product rule: if \(P_1,
P_2,\dots,P_n\) are finite sets, then \(|P_1 * P_2 * \dots * P_n| =
|P_1|*|P_2|*\dots*|P_n|\)
Sum rule: if \(P_1, P_2,\dots,P_n\)
are disjoint finite sets, then \(|P_1 \cup P_2
\cup \dots \cup P_n| = |P_1|+|P_2|+\dots+|P_n|\)
Generalized Product Rule Ch 14.3
Generalized Product Rule: Let S be a set of length-k sequences. If
there are \(n_1\) possible for first
entries, \(n_2\) possible second
entries for each first entry, ..., \(n_k\) possible kth entries for each
sequence of first k - 1 entries, then: \(|S| =
n_1 * n_2 * \dots * n_k\)
Permutations
A permutation of a set S is a sequence that contains every element
of S excatly once
There are a total of \(n!\)
permutations of an n-element set
From the above formula, we have \(log(n!)
\approx nlog(n)\)
Division rule Ch 14.4
k-to-1 function: maps exactly k elements of the domain to every
element of the codomain
Division Rule: if \(f: A \rightarrow
B\) is k-to-1, then \(|A| =
k*|B|\)
Round Table Problem: arrange n knights at a round table, there is a
n-to-1 function, so there are \((n-1)!\) arrangements
Counting subsets Ch 14.5
n choose k: \(\binom{n}{k}\), it
can denote the number of k-element subsets of an n-element set
Subset Rule: the number of k-element subsets of an n-element set is
\(\binom{n}{k} =
\frac{n!}{k!(n-k)!}\)
Bit Sequences: the number of n-bit sequences with exactly k ones is
\(\binom{n}{k}\)
Sequences with repetitions Ch 14.6
Split subsets: let A be an n-element set and \(k_1,k_2,\dots,k_m\) be nonnegative integers
whose sum is n. A \((k_1,k_2,\dots,k_m)\)-split of A is an
sequence \((A_1,A_2,\dots,A_m)\) where
\(A_i\) are disjoint subsets of A and
\(|A_i| = k_i\) for \(i=1,\dots,m\)
Multinomial coefficient: for \(n,k_1,k_2,\dots,k_m \in \mathbb{N}\), s.t.
\(k_1+k_2+\dots+k_m=n\), define the
multinomial coefficient \(\binom{n}{k_1,k_1,\dots,k_m} = \frac{n!}{k_1 ! k_2
!\dots k_m !}\)
Subset split rule: the number of \((k_1,k_2,\dots,k_m)\)-split of an n-element
set is \(\binom{n}{k_1,k_1,\dots,k_m}\)
Bookkeeper rule: let \(l_1,\dots,l_m\) be distince elements. The
amount of sequences s with \(k_1\)
occurrences of \(l_1\), \(\dots\), and \(k_m\) occurrences of \(l_m\) is \(\binom{k_1 +\dots
+k_m}{k1,\dots,k_m}\)
The binomial theorem: \((a+b)^n =
\sum\limits_{k=0}^{n}\binom{n}{k}a^k b^{n-k}\)
Multinomial theorem: for all \(n \in
\mathbb{N}, (z_1+\dots+z_m)^n = \sum\limits_{\substack{k_1,\dots,k_m \in
\mathbb{N} \\ k_1+\dots+k_m =n}} \binom{n}{k_1,\dots,k_m}
z_{1}^{k_1}\dots z_{m}^{k_m}\)
Counting practice: poker hands Ch 14.7
Poker cards have 4 suits (club, diamond, heart, spade) and 13
ranks(ace, 2, ...,10, jack, queen, king). The 2 jokers are not taken
into consideration
Hands with a four-of-a-kind: draw 5 cards, with 4 of the one rank
Pigeonhole principle: if there are more pigeons than holes they
occupy, then at least two pigeons must be in the same hole
Pigeonhole Principle
Total function: a function that is defined on all elements of its
domain is called a total function
If \(|A| > |B|\), then for every
total function \(f: A \rightarrow B\),
there are two different elements in A mapped to the same element in
B
Generalized pigeohole Principle: if \(|A|
> k*|B|\), then every total function \(f: A \rightarrow B\) maps at least k + 1
different elements of A to the same element of B
Inclusion-Exclusion Ch 14.9
Union of two sets \(|A \cup B| = |A| + |B|
- |A \cap B|\)
Union of three sets \[|A \cup B \cup C| =
|A| + |B| +|C| - |A \cup B| - |A \cup C| - |B \cup C| + |A \cap B \cap
C|\]
Inclusion-Exclusion: \(|\bigcup\limits_{i=1}^{n}
S_i|=\sum\limits_{i=1}^{n}|S_i| - \sum\limits_{1\leq i \leq j \leq
n}|S_i \cap S_j| + \sum\limits_{1\leq i \leq j \leq k \leq n} |S_i \cap
S_j \cap S_k| + \dots +
(-1)^{n}|\bigcap\limits_{i=1}^{n}S_i|\)
The Induction Principle: Let P be a predicate on nonnegative
integers. If P(0) is true, and P(n) implies P(n + 1) for all nonnegative
integers n, then P(m) is true for all nonnegative integers, m
A template for induction proofs
State that the proof uses induction
Define an appropriate predicate P(n)
Prove that P(0) is true
Prove that P(n) implies P(n + 1) for every nonnegative integer
n
Invoke induction
Strong induction Ch 5.2
Principle of Strong Induction: Let P be a predicate on nonnegative
integers. If P(0) is true, and for all \(n \in
\mathbb{N}\), P(0), P(1),..., P(n) together imply P(n + 1), then
P(m) is true for all
Events and probability space
The four step method Ch 16.2
Step 1: Find the sample space
Step 2: Define the events of interest
Step 3: Determine outcome probabilities
Step 4: Compute event probabilities
The birthday principle Ch 16.4
There are d days in a year, and there are n students, then the
probability that all students have different birthdays are \(\text{prob} = \frac{d(d-1)\dots(d-(n-1))}{d^n}
< e^{-\frac{n(n-1)}{2d}}\)
The birthday principle: if there are d days in a year, and \(\sqrt{2d}\) people in a room, then the
probability that two share a birthday is about \(1-\frac{1}{e}\approx 0.632\)
Set theory and probability
Probability space
A countable sample space S is a nonempty countable set. an element
\(\omega \in S\) is called an outcome,
a ubset of S is called an event
A probability function on a sample space S is a total function \(\text{Pr}: S \rightarrow \mathbb{R}\) s.t.
\(\text{Pr}(\omega) \geq 0\), for
all \(\omega \in S\)
A sample space together with a probability function is called a
probability space. For any event \(E \subseteq
S\), the probability of E is defined to be the sum of the
probabilities of the outcome in E: \(\text{Pr}(E) ::=\sum\limits_{\omega \in E}
\text{Pr}(\omega)\)
Uniform probability spaces
A finite probability space, S, is said to be uniform if \(\text{Pr}(\omega)\) is the same for every
outcome \(\omega \in S\)
For any event \(E \subseteq S\),
\(\text{Pr}(E) = \frac{|E|}{|S|}\)
Probability space can be infinite
Conditional Probability
Definition and notation Ch 17.2
The expression \(\text{Pr}(X|Y)\)
denotes the probability of event X, given that event Y happens
Let X and Y be events where Y has nonzero probability. Then \(\text{Pr}(X|Y) = \frac{\text{Pr}(X\cap
Y)}{\text{Pr}(Y)}\)
Law to total probability on single event: \(\text{Pr}(A) = \text{Pr}(A|E)*\text{Pr}(E) +
\text{Pr}(A|\bar{E})*\text{Pr}(\bar{E})\)
Law of total probability on 3 events, if \(E_1, E_2,\) and \(E_3\) are disjoint and \(\text{Pr}(E_1 \cup E_2 \cup E_3) = 1\),
then \(\text{Pr}(A) =
\text{Pr}(A|E_1)*\text{Pr}(E_1)+\text{Pr}(A|E_2)*\text{Pr}(E_2)+\text{Pr}(A|E_3)*\text{Pr}(E_3)\)
Bayes's rule on 3 events: \(\text{Pr}(E_1|A)=\frac{\text{Pr}(A|E_1)*\text{Pr}(E_1)}{\text{Pr}(A|E_1)*\text{Pr}(E_1)+\text{Pr}(A|E_2)*\text{Pr}(E_2)+\text{Pr}(A|E_3)*\text{Pr}(E_3)}\)
Independence Ch 17.7
Definition: an event with probability 0 is defined to be independent
of every event(including itself). If \(\text{Pr}(B) \neq 0\), then event A is
independent of event B \(\leftrightarrow
\text{Pr}(A|B) = \text{Pr}(A)\)
A is independent of B \(\leftrightarrow
\text{Pr}(A \cap B) = \text{Pr}(A) * \text{Pr}(B)\)
A set \(A_1, A_2,\dots\) of events
is k-way independent \(\leftrightarrow\) every set of k of these
events is mutually independent. The set is pairwise independent \(\leftrightarrow\) it is 2-way
independent
Binary Relations Ch 4.4
Binary relations define relations between two objects
Definition: a binary relation, R, consists of a set, A, called the
domain of R, a set, B, called the codomain of R, and a subset of A * B
called the graph of R. R is called between A and B or from A to B. For
functions, we write \(R: A \rightarrow
B\)
The standard properties of a relation can be visualized in terms of
a diagram: write \(a \rightarrow b\) if
\(a \in A\) and \(b \in B\) and a is associated with b in
R
\(\leq 1\) arrow property: every
point in the domain column has at most one arrow coming out of it
A binary relation, R, is
a function when it has the \(\leq
1\) arrow out property
surjective when it has the \(\geq
1\) arrow in property
total when it has the \(\geq 1\)
arrow out property
injective when it has the \(\leq
1\) arrow in property
bijective when it has both the \(=
1\) arrow out and the \(= 1\)
arrow in property
Relational images
Definition: the image of a set Y, under a relation R, written \(R(Y)\), is the set of elements of the
codomain, B, of R that are related to some element in Y. In terms of the
relation diagram, \(R(Y)\) is the set
of points with an arrow coming in that starts from some point in Y
Inverse relations
Definition: the inverse \(R^{-1}\),
or a relation \(R: A \rightarrow B\),
is the relation from B to A defined by the rule \(bR^{-1}a \leftrightarrow aRb\)
Inverse images
Definition: the image of a set under the relation, \(R^{-1}\), is called the inverse image of
the set. That is, the inverse image of a set, X, under the relation, R,
is defined to be \(R^{-1}(X)\)
Inference
A formula of the predicate calculus is in prenex normal form (PNF)
if it is written as a string of quantifiers and bound variables, called
the prefix, followed by a quantifier-free part, called the matrix
Conversion to PNF
Conjunction and disjunction: when x is not a free variable of \(\psi\)
\((\forall x \phi)\land \psi
\Longleftrightarrow \forall x(\phi \land \psi)\)
\((\forall x \phi)\lor \psi
\Longleftrightarrow \forall x(\phi \lor \psi)\)
\((\exists x \phi)\land \psi
\Longleftrightarrow \exists x(\phi \land \psi)\)
\((\exists x \phi)\lor \psi
\Longleftrightarrow \exists x(\phi \lor \psi)\)
Two examples
\((\exists(x^2=1)\land(0=y))
\Longleftrightarrow \exists x (x^2=1 \land 0=y)\)
\((\exists(x^2=1)\land(0=x))\) does
not mean \(\exists x (x^2=1 \land
0=y)\)
Negation
\(\neg \exists x \phi \Longleftrightarrow
\forall x \neg \phi\)
\(\neg \forall x \phi \Longleftrightarrow
\exists x \neg \phi\)
Implication: when the variable quantified in one sub-formula does
not appear free in the other sub-formula
\((\forall x \phi) \rightarrow \psi
\Longleftrightarrow \exists x (\phi \rightarrow \psi)\)
\((\exists x \phi) \rightarrow \psi
\Longleftrightarrow \forall x (\phi \rightarrow \psi)\)
\(\phi \rightarrow (\exists x \psi)
\Longleftrightarrow \exists x (\phi \rightarrow \psi)\)
\(\phi \rightarrow (\forall x \psi)
\Longleftrightarrow \forall x (\phi \rightarrow \psi)\)
A formula of first-order logic is in Skolem normal form if it is in
prenex normal form with only universal first-order quantifiers
Truth trees for predicate logic
Negate the conclusion
Replace each existential variable with a point to set up the domain,
if there the domain is empty(meaning there is no existential variable in
the statements), just make one, this step is called skolemization
\(\exists x, \forall y, f(x,y)
\longrightarrow \forall y, f(a,y)\)
\(\forall x, \exists y, f(x,y)
\longrightarrow \forall x, f(x,g(x))\)
Use points in the domain to determine if there are contradictions
If there are contradiction on each branch, then the negation of the
conclusion is wrong and then the conclusion itself is correct
If the tree has infinite branches and we cannot find a contradiction
for each branch(sometimes even the tree has infinite branches, we can
logically find a contradiction on each branch), then we cannot prove or
disprove the conclusion
Gödel's incompleteness theorems
The first theorem: Any consistent formal system F within which a
certain amount of elementary arithmetic can be carried out is
incomplete; i.e., there are statements of the language of F which can
neither be proved nor disproved in F.
The second theorem: Assume F is a consistent formalized system which
contains elementary arithmetic. Then \(F
\not\vdash \text{Cons}(F)\)