COSI 29A Discrete Structure

Notes of COSI 29A

Discrete Mathematics: An Open Introduction Notes

1. 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 ones
     • 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\wedge Q$
       • Ddisjunction: P or Q, $P\vee Q$
       • Implication/Condition: if P then Q/P only if Q, $P\to Q$, P is hypothesis/antecedent, conclusion/consequent
       • Biocondition: P if and only if Q, $P\leftrightarrow Q$
       • Negation: not P, $\mathrm{\neg }P$
   • Truth conditions:
     • $P\to 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
     • Converse of $P\to Q$ is $Q\to P$, the converse and the original statement can have different truth values
     • Contrapositive statement of $P\to Q$ is $\mathrm{\neg }Q\to \mathrm{\neg }P$, the contrapositive and the original statement have the same truth value
   • If and only if
     • $P\leftrightarrow Q$ is logically equivalent to $(P\to Q)\wedge (Q\to P)$
   • Necessary and sufficient
     • P is necessary for Q means $Q\to P$
     • P is sufficient for Q means $P\to Q$
     • P is necessary and sufficient for Q means $P\leftrightarrow Q$
   • 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 a predicate
     • Two quantifiers: existential and universal
       • Existential: $\mathrm{\exists }$, there exists/there is, $\mathrm{\exists }x(x<0)$ means there is a number less than 0
       • Universal: $\mathrm{\forall }$, for all/every, $\mathrm{\forall }x(x\ge 0)$ means every numebr is gerater than or equal to 0
       • Negation:
         • $\mathrm{\neg }\mathrm{\exists }x(P(x))$ is equivalent to $\mathrm{\forall }x(\mathrm{\neg }P(x))$
         • $\mathrm{\neg }\mathrm{\forall }x(P(x))$ is equivalent to $\mathrm{\exists }x(\mathrm{\neg }P(x))$
     • Implicit quantifiers: in order for a predicate to become a statement, we implicitly assume the variable is universally quantified
2. 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
     • $\mathrm{\neg }(P\wedge Q)$ is equivalent to $\mathrm{\neg }P\vee \mathrm{\neg }Q$
     • $\mathrm{\neg }(P\vee Q)$ is equivalent to $\mathrm{\neg }P\wedge \mathrm{\neg }Q$
   • Implications are Disjunctions: $P\to Q$ is equivalent to $\mathrm{\neg }P\vee Q$
   • Double negation: $\mathrm{\neg }\mathrm{\neg }P$ is equivalent to $P$
   • Negation of an Implication: $\mathrm{\neg }(P\to Q)$ is equivalent to $P\wedge \mathrm{\neg }Q$
   • Decutsion: given a set of true premises, the conclusion should be true
   • Predicate logic extends propositional logic
3. 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 $\mathrm{\neg }P\to Q$ is true, where Q is false, this implies P is true
   • Direct proof
   • Proof by contrapositive: prove $P\to Q$ using $\mathrm{\neg }Q\to \mathrm{\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
4. 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: $A=\{0,2,4,6,...\}=\{x\in \mathbb{N}:\mathrm{\exists }n\in \mathbb{N}(x=2n)\}=\{x\in \mathbb{N}:xiseven\}$
     • The notation is often called the set builder notation
   • Special Sets
     • empty set: $\mathrm{\varnothing }$
     • universal set: $\mathcal{U}$
     • natural numbers: $\mathbb{N}=\{0,1,2,3,...\}$
     • integers: $\mathbb{Z}=\{...,-2,-1,0,1,2,...\}$
     • rational numbers: $\mathbb{Q}$
     • real numbers: $\mathbb{R}$
     • power set of A: $\mathcal{P}(A)$
   • Set Theory Notation
     • $:$ such that
     • $A\subseteq B$: A is a subset of B
     • $A\subset B$: A is a proper subset of B
     • $A\cap B$: intersection of A and B
     • $A\cup B$: union of A and B
     • $A\times B$: Cartesian product of A and B
     • $A\setminus B$: set difference between A and B
     • $\overline{A}$: complement of A
     • $|A|$: cardinality (or size) of A
   • Venn Diagrams
5. Functions Ch 0.4
   • Introduction
     • 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
     • Notaion: $f:X\to 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
       • $\mathrm{\forall }y\in Y$, $\mathrm{\exists }x\in X$, 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
       • $\mathrm{\forall }{x}_1\in X,\mathrm{\forall }{x}_2\in X$, if $f(x_1)=f(x_2)$, then $x_1=x_2$
       • $\mathrm{\forall }{x}_1\in X$, $\mathrm{\forall }{x}_2\in X$, if $x_1\ne x_2$, then $f(x_1)\ne f(x_2)$
     • Bijection: if a function is both onto and injective, then it is called bijective function or bijection
   • Image and Inverse Image
     • $f:X\to Y$: let $A\subseteq X$ and $B\subseteq Y$,
       • Image of A: $f(A)=\{f(a)\in Y:a\in A\}$
       • Inverse image of B: $f^{-1}(B)=\{a\in X:f(a)\in B\}$
     • 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
       • Use $x_1,x_2$ 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|\ge |f(A)|$, when f is injective, we have $|A|=|f(A)|$
     • Generally, we don't know $|B|$ and $|f^{-1}B|$. If f is injective, $|B|\ge |f^{-1}(B)|$. If f is surjective, $|B|\ge |f^{-1}(B)|$. If f is bijective, $|B|=|f^{-1}(B)|$
     • $A\subseteq f^{-1}(f(A))$
       • The two set are equal when f is injective
       • Proper subset example: f: {1,2} -> {1}, f(1) = f(2) = 1
     • $f(f^{-1}(B))\subseteq B$
       • The two set are equal when f is surjective
       • Proper subset example: f: {1,2} -> {1,2,3}, f(1) = 1, f(2) = 2
     • $f(A\cup B)=f(A)\cup f(B)$
     • $f^{-1}(A\cup B)=f^{-1}(A)\cup f^{-1}(B)$
     • $f(A\cap B)\subseteq f(A)\cap f(B)$
       • f: {0, 1} -> {0,1} f(0) = f(1) = 1
     • $f^{-1}(A\cap B)=f^{-1}(A)\cap f^{-1}(B)$
6. Additive and Multiplicative Principles Ch 1.1
   • 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=\mathrm{\varnothing }$, then $|A\cup B|=|A|+|B|$
   • Cartesian Product: Givens sets A and B, we can form the set $A\ast B=\{(x,y):x\in A\wedge y\in B\}$
   • Multiplicative principle with sets: Given two sets A and B, we have $|A\ast B|=|A|\ast |B|$
   • Cardinality of a union(2 sets): $|A\cup B|=|A|+|B|-|A\cap B|$
   • Cardinality of a union(3 sets): $|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cup C|-|B\cap C|+|A\cap B\cap C|$
7. Binomial Coefficients Ch 1.2
   • Subsets: $|\mathcal{P}(A)|=2^{|A|}$
   • Big Strings:
     • Bit is short for binary digit
     • A n-bit string is a bit string of length n. That is, it's a string containing n symbols, each of which is a bit, either 0 or 1
     • The weight of a bit string is the number of 1's in it
     • $B^n$ is the set of all n-bit strings
     • $B_k^n$ is the set of all n-bit strings of weight k
     • Obviously: $|B_k^n|=|B_{k-1}^{n-1}|+|B_k^{n-1}|$
   • Lattice Paths
     • 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\ge 0$ and integer k with $0\le k\le n$ there is a number $(\genfrac{}{}{0ex}{}{n}{k})$, reads n choose k
       • $(\genfrac{}{}{0ex}{}{n}{k})=|B_k^n|$
       • $(\genfrac{}{}{0ex}{}{n}{k})$ is the number of subsets of a set of size n each with cardinality k
       • $(\genfrac{}{}{0ex}{}{n}{k})$ is the number of lattice paths of length n containing k steps to the right
       • $(\genfrac{}{}{0ex}{}{n}{k})$ is the coefficient of $x^k{y}^{n-k}$ in the expansion of $(x+y{)}^n$
       • $(\genfrac{}{}{0ex}{}{n}{k})$ is the numebr of ways to select k objects from a total of n objects
     • Pascal's Triangle
8. Combinations and Permutations Ch 1.3
   • Permutations
     • A permutation is a possible rearrangement of objects
     • There are $n!=n\ast (n-1)\ast (n-2)\ast ...2\ast 1$ permutations of n(distinct) elements
     • k-permutation of n elements: $P(n,k)$ is the number of k-permutations of n elements, the number of ways to arrange k objects chosen from n distinct objects: $$P(n,k)=\frac{n!}{(n-k)!}=n(n-1)(n-2)...(n-(k-1))$$
     • Closed formulat for $(\genfrac{}{}{0ex}{}{n}{k})$: $$(\genfrac{}{}{0ex}{}{n}{k})\frac{n!}{(n-k)!k!}=\frac{n(n-2)...(n-(k-1))}{k(k-1)(k-2)...1}$$
9. Combinatorial Proofs Ch 1.4
   • Binomial Identity
     • $(\genfrac{}{}{0ex}{}{n}{0})=1$ and $(\genfrac{}{}{0ex}{}{n}{n})=1$
     • $(\genfrac{}{}{0ex}{}{n}{k})=(\genfrac{}{}{0ex}{}{n-1}{k-1})+(\genfrac{}{}{0ex}{}{n-1}{k})$
     • $(\genfrac{}{}{0ex}{}{n}{k})=(\genfrac{}{}{0ex}{}{n}{n-k})$
     • $(\genfrac{}{}{0ex}{}{n}{0})+(\genfrac{}{}{0ex}{}{n}{1})+(\genfrac{}{}{0ex}{}{n}{2})+\cdots +(\genfrac{}{}{0ex}{}{n}{n})=2^n$
   • Combinatorial Proof
     • In general, to give a combinatorial proof for a binomial identity, say A = B, you do the following:
       • 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
10. Sequences
    • Describing Sequences Ch 2.1
      • A sequence is simply an ordered list of numbers
      • Notations: $a_0,a_1,...$, or $(a_n{)}_{n\in \mathbb{N}}$, or $(a_n{)}_{n=\ge 0}$, or simply $(a_n)$. If we omit $a_0$, then the sequence is $(a_n{)}_{n\ge 1}$. The 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:
        • The square numbers, the $(s_n{)}_{n\ge 1}$ has closed formula, $s_n=n^2$
        • The triangle numbers: the $(T_n{)}_{n\ge 1}$ has closed formulat $T_n=\frac{n(n+1)}{2}$
        • The triangle numbers: the $(a_n{)}_{n\ge 0}$ has closed formulat $a_n$
        • The Fibonacci numbers: defined recursively by $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=r{a}_{n-1}$ with $a_0=a$, closed formula: $a_n=a\ast r^n$
        • Summing arithmetic sequences: reverse and add
          • Formula: $\sum _{k=0}^{n-1}(a+kd)=\frac{n}{2}(2a+(n-1)d)$
        • Summing geometric sequences: multiply, shift and subtract
          • Formula: $\sum _{k=0}^{n-1}(a{r}^k)=a\frac{1-r^n}{1-r}$
      • Polynomial Fitting Ch 2.3
        • Difference:
          • For sequence $(a_n{)}_{n\ge 0}$, its first difference is $(a_n-a_{n-1}{)}_{n\ge 1}$ , its second difference is $((a_n-a_{n-1})-(a_{n-1}-a_{n-2}){)}_{n\ge 2}$
          • If the $k$th difference of a sequence is constant, the we say a sequence is a ${\mathrm{\Delta }}^k$-constant sequence
            • If a sequence is arithmetic, then it is ${\mathrm{\Delta }}^1$-constant, which means the first difference of itself is constant
        • Finite difference:
          • The closed formula for a sequence will be a degree $k$ polynomial if and only if the sequence is ${\mathrm{\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$, the characteristic polynomial is $x^2+\alpha x+\beta =0$
          • If ${\tau }_1$ and ${\tau }_2$ are two distinct roots of the characteristic polynomial, then the solution to the recurrence relation is $a_n=a{\tau }_1^n+b{\tau }_2^n$, where a and b are constants determined by the initial conditions
          • If there is only one solution $\tau$, then the solution to the recurrence relation is $a_n=a{\tau }^n+bn{\tau }^n$, where a and b are constants determined by the initial conditions
      • Induction Ch 2.5
        • Induction Proof Structure: Lect $P(n)$ be the statement..., to prove $P(n)$ is true for all $n\ge 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)\to P(k+1)$ for all $k\ge 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\ge 0$
        • Strong Induction Proof Structure: Lect $P(n)$ be the statement..., to prove $P(n)$ is true for all $n\ge 0$, you must prove two facts:
          • Base case: Prove that $P(0)$ is true
          • Inductive caser: Assume $P(k)$ is true for all $k<n$. Prove that $P(n)$ is true
        • Some results
          • $1+...+n=\frac{n\ast (n+1)}{2}$
          • $1^2+...+n^2=\frac{n\ast (n+1)\ast (2\ast n+1)}{6}$
          • $1^3+...+n^3=(\frac{n\ast (n+1)}{2}{)}^2$
          • Consider $\zeta (s)=\sum _{n=1}^{\mathrm{\infty }}\frac{1}{n^s}$
            • Then $\zeta (s)=\frac{1}{\mathrm{\Gamma }(s)}={\int }_0^{\mathrm{\infty }}\frac{x^{s-1}}{e^x-1}dx$
            • $\zeta (-1)=-\frac{1}{12}$, $\zeta (0)=-\frac{1}{2}$, $\zeta (1)=\mathrm{\infty }$, $\zeta (2)=\frac{{\pi }^2}{6}$, $\zeta (4)=\frac{{\pi }^4}{90}$
11. Graph Definitions Ch 4.1

• 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\to V_2$ between the vertices of the graphs such that $\{a,b\}$ is an edge in $G_1$ iff $\{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^{{}^{\prime }}=(V^{{}^{\prime }},E^{{}^{\prime }})$ is a subgraph of $G=(V,E)$, and write $G^{{}^{\prime }}\subseteq G$, provided $V^{{}^{\prime }}\subseteq V$ and $E^{{}^{\prime }}\subseteq E$. $G^{{}^{\prime }}=(V^{{}^{\prime }},E^{{}^{\prime }})$ is a induced subgraph of $G=(V,E)$ provided $V^{{}^{\prime }}\subseteq V$ and every edge in E whose vertices are still in $V^{{}^{\prime }}$ is also an edge in $E^{{}^{\prime }}$
• 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 _{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

1. Logical Formulas Ch 3.1
   • Java uses && for and, || for or
   • P Xor Q notation: $P\oplus Q$
   • Negation P: $\overline{P}$, or $\mathrm{\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\wedge (B\vee C)=(A\wedge B)\vee (A\wedge C)$
   • Distributive Law of OR over AND: $A\vee (B\wedge C)=(A\vee B)\wedge (A\vee 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
2. Inference Rules Ch 3.4
   • $(A\wedge B)\vee Ciff(A\vee C)\wedge (B\vee C)$
   • $(A\vee B)\wedge Ciff(A\wedge C)\vee (B\wedge C)$
   • $(A\wedge B)iff(B\wedge A)$
   • $(A\wedge B)\wedge CiffA\wedge (B\wedge C)$
   • $T\wedge AiffA$
   • $F\wedge AiffF$
   • $A\wedge AiffA$
   • $A\wedge \mathrm{\neg }AiffF$
   • $A\mathrm{\neg }(\mathrm{\neg }A)iffA$
   • $A\vee (\mathrm{\neg }A)iffT$
   • $\mathrm{\neg }(A\wedge B)iff\mathrm{\neg }A\vee \mathrm{\neg }B$
   • $\mathrm{\neg }(A\vee B)iff\mathrm{\neg }A\wedge \mathrm{\neg }B$
3. Predicate Formulas Ch 3.6
   • General syntax: $condition{x}_1.condition{x}_2....condition{x}_N.P(x_1,x_2,...,x_N)$
   • Quantifiers
     • Always true:
       • For all x $\in$ D, P(x) is true
       • P(x) is true for every x in teh set, D
     • Sometimes true:
       • There is an x $\in$ D such that P(x) is true
       • P(x) is true for some x in the set, D
       • P(x) is true for at least on x $\in$ D
     • Universal quantification: an assertion that a predicate is always true
     • Existential quantification: an assertion that a predicate is sometimes true
   • Mixing Quantifiers
     • For every even integer n greater that 2, there exists primes p and q such that n = p + q: $\mathrm{\forall }$ n $\in$ Evens, $\mathrm{\exists }$ p $\in$ Primes, $\mathrm{\exists }$ q $\in$ Primes. n = p + q
   • Order of Quantifiers: swapping the order of different quantifiers usually changes the meaning of a proposition
   • Variables over the domain:
     • Simplification: $\mathrm{\forall }$ x $\mathrm{\exists }$ y. Q(x,y) => $\mathrm{\forall }$ x $\mathrm{\exists }$ y. Q(x,y)
     • The unnamed nonempty set that x and y range over is called the domain of discourse, of just domain
   • Negating Quantifiers
     • Equivalence: NOT($\mathrm{\forall }$ x. P(x)) iff $\mathrm{\exists }$ x. NOT(P(x))
     • Equivalence: NOT($\mathrm{\exists }$ x. P(x)) iff $\mathrm{\forall }$ x. NOT(P(x))
   • Validity for Predicate Formulas
     • In order for a predicate formula to be valid, it should be true all across its domain
     • Valid assertion: $\mathrm{\exists }$ x $\mathrm{\forall }$ y. P(x,y) implies $\mathrm{\forall }$ y $\mathrm{\exists }$ x. P(x, y)
     • Not valid assertion: $\mathrm{\forall }$ y $\mathrm{\exists }$ x. P(x,y) implies $\mathrm{\exists }$ x $\mathrm{\forall }$ y. P(x, y) (x maybe y related, so there is no universal x)
4. 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
5. Sets Ch 4.1
   • Introduction
     • Informally, a set is a bunch of elements
   • Some Popular Sets: $\mathrm{\varnothing }$, $\mathbb{N}$, $\mathbb{Z}$, $\mathbb{Q}$, $\mathbb{R}$, $\mathbb{C}$
   • Comparing and Combining Sets
     • $\subseteq$: subset, $\subset$: strict subset
     • $x\in A\cup B$ iff $x\in A$ OR $x\in B$
     • $x\in A\cap B$ iff $x\in A$ AND $x\in B$
     • $x\in A\setminus B$ iff $x\in A$ AND $x\notin B$
     • $B\in \mathcal{P}\mathcal{(}\mathcal{A}\mathcal{)}$ iff $B\subseteq A$
   • Proving Set Equalities: to prove $A=B$, we need to prove $\mathrm{\forall }x.x\in A$ iff $x\in B$
6. Sequences Ch 4.2
   • A list of ordered elements are called sequence
   • Use $\lambda$ for empty sequence
7. 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 S under f:
     • $f(S)=\{b\in S|f(s)=bforsomes\in S\}$
     • $range(f)=f(domain(f))$
   • Function Composition
     • For $f:A\to B$ and $g:B\to C$, the composition $g\circ f$ or g with f is $(g\circ f)(x)=g(f(x))$ and its from A to C
8. 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\ast 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
   • Image: $R(A)
   • Inverse relation: $R^{-1}$, $b{R}^{-1}a$ IFF $aRb$
   • Inverse image: $R^{-1}(B)$
9. Finite Cardinality Ch 4.5
   • If A is a finite set, the cardinality of A, written $|A|$, is the number of elements in A
   • Definition:
     • $AsurjB$ iff there is a surjective function from A to B
     • $AinjB$ iff there is an injective function from A to B
     • $AbijB$ iff there is a bijective function from A to B
   • Theorem: For finite sets A, B:
     • $AsurjB$ IFF $|A|\ge |B|$
     • $AinjB$ IFF $|A|\le |B|$
     • $AbigB$ IFF $|A|=|B|$
   • For a finite with n elements, there are $2^n$ subsets
10. 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,...,P_n$ are finite sets, then $|P_1\ast P_2\ast ...\ast P_n|=|P_1|\ast |P_2|\ast ...\ast |P_n|$
      • Sum Rule: if $P_1,P_2,...,P_n$ are disjoint sets, then $|P_1\cup P_2\ast \cup ...\cup P_n|=|P_1|+|P_2|+...+|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\ast n_2\ast ...\ast 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
        • Stirling's formula: $n!\approx \sqrt{2\pi n}(\frac{n}{e}{)}^n$
        • 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\to B$ is k-to-1, then $|A|=k\ast |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: $(\genfrac{}{}{0ex}{}{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 $(\genfrac{}{}{0ex}{}{n}{k})=\frac{n!}{k!(n-k)!}$
      • Bit Sequences: the number of n-bit sequences with exactly k ones is $(\genfrac{}{}{0ex}{}{n}{k})$
    • Sequences with Repetitions Ch 14.6
      • Split subsets: lete A be an n-element set and $k_1,k_2,...,k_m$ be nonegative integers whose sum is n. A $(k_1,k_2,...,k_m)$-split of A is an sequence $(A_1,A_2,...,A_m)$ where the $A_i$ are disjoint subsets of A and $|A_i|=k_i$ for i = 1,...,m
      • Multinomial coefficient: for $n,k_1,...,k_m\in \mathbb{N}$, such that $k_1+k_2+...+k_m=n$, define the nultinomial coefficient $(\genfrac{}{}{0ex}{}{n}{k_1,k_2,...,k_m})=\frac{n!}{k_1!k_2!...k_m!}$
      • Subset Split Rule: the numer of $(k_1,k_2,...,k_m)$-split of an n-element set is $(\genfrac{}{}{0ex}{}{n}{k_1,k_2,...,k_m})$
      • Bookkeeper Rule: let $l_1,...,l_m$ be distinct eleemnts. The number of sequence s with $k_1$ occurrences of $l_1$, and $k_2$ occurrences of $l_2$,..., and $k_m$ occurrences of $l_m$ is $(\genfrac{}{}{0ex}{}{k_1+k_2+...+k_m}{k_1,...,k_m})$
      • The binomial Theorem: $(a+b{)}^n=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})a^{n-k}{b}^k$
      • Multinomial Theorem: for all $n\in \mathbb{N}$, $(z_1+z_2+...+z_m{)}^n=\sum _{\begin{array}{c}k1,...,k_m\in \mathbb{N}\\ k_1+k_2+...+k_m=n\end{array}}(\genfrac{}{}{0ex}{}{n}{k_1,k_2,...,k_m})z_1^{k_1}{z}_2^{k_2}...z_m^{k_m}$
    • Counting Practice: Poker Hands Ch 14.7
      • Poker cards have 4 suits and 13 ranks
      • Four-of-a-kind: four cards with the same rank
        • Method 1: $13\ast (\genfrac{}{}{0ex}{}{4}{3})$
        • Method 2: $\frac{52\ast 3\ast 2}{3!}$
      • Hands with a full house: three cards of one rank and two cards of another rank
        • Method 1: $13\ast (\genfrac{}{}{0ex}{}{4}{3})\ast 12\ast (\genfrac{}{}{0ex}{}{4}{2})$
        • Method 2: $\frac{52\ast 3\ast 2}{3!}\ast \frac{48\ast 3}{2!}$
      • Hands with two pairs: two cards of one rank, two cards of anotehr rank, and on card of a third rank
        • Method 1: $\frac{13\ast (\genfrac{}{}{0ex}{}{4}{2})\ast 12\ast (\genfrac{}{}{0ex}{}{4}{2})}{2}\ast 11\ast (\genfrac{}{}{0ex}{}{4}{1})$
        • Method 2: $(\genfrac{}{}{0ex}{}{13}{2})\ast (\genfrac{}{}{0ex}{}{4}{2})\ast (\genfrac{}{}{0ex}{}{4}{2})\ast 11\ast (\genfrac{}{}{0ex}{}{4}{1})$
        • Method 2: $\frac{\frac{52\ast 3}{2!}\ast \frac{48\ast 3}{2!}}{2}\ast 44$
      • Hands with every suit: at least one card from every suit
        • Method 1: $\frac{{13}^4\ast 4\ast 12}{2}$
    • The Pigeonhole Principle Ch 14.8
      • 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\to B$, there exist two different elements of A that are mapped by f to the same element of B
        • Generalized pigeohole Principle: if $|A|>k\ast |B|$, then every total function $f:A\to 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\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$
      • Inclusion-Exclusion: $|\bigcup _{i=1}^n{S}_i|=\sum _{i=1}^n|S_i|-\sum _{1\le i<j\le n}|S_i\cap S_j|+\sum _{1\le i<j<k\le n}|S_i\cap S_j\cap S_k|+...+(-1{)}^n|\bigcap _{i=1}^n{S}_i|$
      • Inclusion-Exclusion-II:
      • $|\bigcup _{i=1}^n{S}_i|=\sum _{\mathrm{\varnothing }\ne I\subseteq \{1,...,n\}}(-1{)}^{|I|+1}|\bigcap _i{S}_i|$
    • Combinatorial Proof Ch 14.10
      • Pascal's Triangle Identity: $(\genfrac{}{}{0ex}{}{n}{k})=(\genfrac{}{}{0ex}{}{n-1}{k-1})+(\genfrac{}{}{0ex}{}{n-1}{k})$
      • Giving a combinatorial proof:
        • Define a set S
        • Show that $|S|=n$ by counting one way
        • Show that $|S|=m$ by counting another way
        • Conclude that $n=m$
      • Equality: $\sum _{r=0}^n(\genfrac{}{}{0ex}{}{n}{r})(\genfrac{}{}{0ex}{}{2n}{n-r})=(\genfrac{}{}{0ex}{}{3n}{n})$
11. Induction Ch 5
    • Ordinary Induction Ch 5.1
      • 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 $m\in \mathbb{N}$
12. 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 $\frac{d(d-1)...(d-(n-1))}{d^n}<e^{-(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-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 $Pr:S\to \mathbb{R}$ such that
          • $Pr[\omega ]\ge 0$ for all $$S, and
          • $\sum _{\omega \in S}Pr[\omega ]=1$
        • 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: $Pr[E]::=\sum _{\omega \in E}Pr[\omega ]$
      • Probability Rules from Set Theory
        • Sum Rule: if $E_0,E_1,...,E_n,...$ are pairwise disjoint events, then $Pr[\bigcup _{n\in \mathbb{N}}{E}_n]=\sum _{n\in \mathbb{N}}Pr[E_n]$
        • Union Bound: $Pr[E_1\cup ...\cup E_n\cup ...]\le Pr[E_1]+...+Pr[E_n]+...$
      • Uniform Probability Spaces
        • A finite probability space, S, is said to be uniform if $Pr[\omega ]$ is the same for every outcome $\omega \in$ S
        • For any event $E\subseteq S$, $Pr[E]=\frac{|E|}{|S|}$
      • Probability Spaces can be infinite
13. Conditional Probability

• Definition and Notation Ch 17.2
  • The expression $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 $Pr[X|Y]=\frac{Pr[X\cap Y]}{Pr[Y]}$
• Why Tree Diagrams Work Ch 17.4
  • Conditional Probability Product Rule - 2 Events: $Pr[E_1\cap E_2]=Pr[E_1]\ast Pr[E_2|E_1]$
  • Conditional Probability Product Rule - 3 Events: $Pr[E_1\cap E_2\cap E_3]=Pr[E_1]\ast Pr[E_2|E_1]\ast Pr[E_3|E_1\cap E_2]$
  • Bayes' Rule: $Pr[B|A]=\frac{Pr[A|B]\ast Pr[B]}{Pr[A]}$
• The Law of Total Probability Ch 17.5
  • Law of Total Probability - single event: $Pr[A]=Pr[A|E]\ast Pr[E]+Pr[A|\overline{E}]\ast Pr[\overline{E}]$
  • Law of Total Probability - 3 events: if $E_1,E_2,$ and $E_3$ are disjoint and $Pr[E_1\cup E_2\cup E_3]=1$, then $Pr[A]=Pr[A|E_1]\ast Pr[E_1]+Pr[A|E_2]\ast Pr[E_2]+Pr[A|E_3]\ast Pr[E_3]$
  • Bayes's Rule - 3 events: $Pr[E_1|A]=\frac{Pr[A|E_1]\ast Pr[E_1]}{Pr[A|E_1]\ast Pr[E_1]+Pr[A|E_2]\ast Pr[E_2]+Pr[A|E_3]\ast Pr[E_3]}$
• Independence Ch 17.7
  • Definition: an event with probability 0 is defined to be independent of every event(including itself). If $Pr[B]\ne )$, then event A is independent of event B iff $Pr[A|B]=Pr[A]$
  • A is independent of B iff $Pr[A\cap B]=Pr[A]\ast Pr[B]$
  • A set $A_1,A_2,...,$ of events is k-way independent iff every set of k of these events is mutually independent. The set is pairwise independent iff it is 2-way independent

14. 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\to B$
    • The standard properties of a relation can be visualized in terms of a diagram: write $a\to b$ if $a\in A$ and $b\in B$ and a is associated with b in R
    • $\le 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 $\le 1$ arrow out property
      • surjective when it has the $\ge 1$ arrow in property
      • total when it has the $\ge 1$ arrow out property
      • injective when it has the $\le 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}$ of a relation $R:A\to B$ is the relation from B to A defined by the rule $b{R}^{-1}a$ iff $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

1. 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$
       • $(\mathrm{\forall }x\varphi )\wedge \psi ⟺\mathrm{\forall }x(\varphi \wedge \psi )$
       • $(\mathrm{\forall }x\varphi )\vee \psi ⟺\mathrm{\forall }x(\varphi \vee \psi )$
       • $(\mathrm{\exists }x\varphi )\vee \psi ⟺\mathrm{\exists }x(\varphi \vee \psi )$
       • $(\mathrm{\exists }x\varphi )\vee \psi ⟺\mathrm{\exists }x(\varphi \vee \psi )$
       • Two examples:
         • $(\mathrm{\exists }(x^2=1)\wedge (0=y))⟺\mathrm{\exists }x(x^2=1\wedge 0=y)$
         • $(\mathrm{\exists }(x^2=1)\wedge (0=x))$ does not mean$\mathrm{\exists }x(x^2=1\wedge 0=x)$
     • Negation
       • $\mathrm{\neg }\mathrm{\exists }x\varphi ⟺\mathrm{\forall }x\mathrm{\neg }\varphi$
       • $\mathrm{\neg }\mathrm{\forall }x\varphi ⟺\mathrm{\exists }x\mathrm{\neg }\varphi$
     • Implication: when the variable quantified in one sub-formula does not appear free in the other sub-formula
       • $(\mathrm{\forall }x\varphi )\to \psi ⟺\mathrm{\exists }x(\varphi \to \psi )$
       • $(\mathrm{\exists }x\varphi )\to \psi ⟺\mathrm{\forall }x(\varphi \to \psi )$
       • $\varphi \to (\mathrm{\exists }x\psi )⟺\mathrm{\exists }x(\varphi \to \psi )$
       • $\varphi \to (\mathrm{\forall }x\psi )⟺\mathrm{\forall }x(\varphi \to \psi )$

2. A formula of first-order logic is in Skolem normal form if it is in prenex normal form with only universal first-order quantifiers

3. 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
     • $\mathrm{\exists }x,\mathrm{\forall }y.f(x,y).\to \mathrm{\forall }y.f(a,y).$
     • $\mathrm{\forall }x,\mathrm{\exists }y.f(x,y).\to \mathrm{\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

4. 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⊬Cons(F)$