Course Summary

1. Discrete math studies:
   • "separated" or "gappy" objects
   • that are countable
   • and not dense (and hence not continuous)
   It studies:
   • Z⁺ = {1,2,3,...} (positive integers)
   • N = {0,1,2,3,...} (natural numbers)
   • Z = {...—3,—2,—1,0,1,2,3,...} (integers)

     but probably not:

   • Q = rational numbers (dense)

     and certainly not:

   • R = real numbers (continuous)

   ---

2. Logic
   1. mathematical theory of "correct" reasoning
   2. formal language for talking & reasoning about math & CS

   3. The study of a language includes:
      1. syntax: study of relationships among symbols
         • e.g., the grammar of a language

      2. semantics: study of relationships between symbols and "the world"
         • i.e., the study of meaning

         • if proposition P "correctly" describes "the world",
             then tval(P) = T
             else tval(P) = F

   4. propositional logic:
      1. syntax of truth-functional connectives:
         1. ¬P (negation)
         2. (P ∧ Q) (conjunction)
         3. (P ∨ Q) (inclusive disjunction)
         4. (P ⊕ Q) (exclusive disjunction)
         5. (P → Q) (material conditional)
         6. (P ↔ Q) (biconditional)

      2. semantics: given by truth tables
         1. tautology: all rows of t-table are T

         2. contradiction: all rows of t-table are F

         3. P ≡ Q iff tval(P) = tval(Q) in all rows
            • DeMorgan, distributive laws, etc.

   5. first-order predicate logic:
      1. "sub-atomic" propositions:
         • Where "P" is a predicate (names a property or relation)
           and t_i are terms (noun phrases):

           P(t₁,...,t_n) is an atomic proposition

      2. quantifiers:
         • ∀xP(x) (universal quantifier)
         • ∃xP(x) (existential quantifier)

   6. Deductive reasoning depends on Rules of Inference:
      1. valid argument "forms" (patterns)
         • an argument (form) is valid
           =def it is truth-preserving

           i.e., if tval(premises) = T, then tval(conclusion) = T

         • Modus Ponens
           Modus Tollens
           Hypothetical Syllogism
           Simplification
           Addition
           Conjunction
           Resolution;

           Universal Instantiation & Generalization
           Existential Instantiation & Generalization

      2. proof strategies
         • Direct proof of conditional
           (to show (P→Q), suppose P & show Q)

         • Proof by contradiction
           (to show P, suppose ¬P & derive contradiction)

         • Etc.

   ---

3. Sets
   1. basic data structure for constructing all math & CS objects
      • math = logic + sets
      • (compare: program = algorithm + data structures)

   2. Sets & elements (members):
      1. e ∈ S: e is an element of set S

      2. set as list of elements: S = {e₁,...,e_n}

      3. set as objects satisfying proposition: S = {e  |  P(e)}

      4. empty set: ∅ = {}

      5. S = T ↔ ∀x[x ∈ S ↔ x ∈ T]

   3. Venn diagrams, Euler circles

   4. Subsets:
      1. S ⊆ T ↔ ∀x[x ∈ S → x ∈ T]
      2. power set of S: ℘(S) = {T  |  T ⊆ S}
      3. cardinality of S: | S | = number of elements of S
         • | ℘(S) | = 2^| S |

   5. Set operations:

      1. ordered pairs: (a,b) = { {a}, {a,b} }

         • Cartesian (or: cross) product: S × T = {(s,t)  |  s ∈ S ∧ t ∈ T}

         • Let A,B be sets
           Then R is a binary relation of A to B
           =def R &sube A × B

      2. union: S ∪ T = {x  |  x &isin S ∨ s &isin T}

      3. intersection: S ∩ T = {x  |  x &isin S ∧ s &isin T}

      4. set difference: S — T = {x  |  x &isin S ∧ s ¬in T}

   6. set identities: DeMorgan, distributive laws, etc.

   ---

4. Functions (as Relations)

   1. Let A,B be sets
      Then ƒ : A → B is a function from A to B
      =def ƒ is a binary relation of A to B
              ∧ (∀a ∈ A)(∀b,b′∈ B)[(a,b) ∈ ƒ ∧ (a,b′) ∈ ƒ → b=b′]

      i.e., [ƒ(a)=b ∧ ƒ(a)=b′ → b=b′]

      i.e., no two objects in range have the same pre-image

   2. functions are not "machines" or formulas;
      they are input-output pairs
      • formulas and algorithms tell you how to compute outputs from inputs.

   3. ƒ:A→B is a 1-1 or injective function
      =def (∀a,a′ ∈ A)(∀b ∈ B)[(a,b) ∈ ƒ ∧ (a′,b) ∈ ƒ → a = a′]

      i.e., (∀a,a′ ∈ A)[ƒ(a) = ƒ(a′) → a = a′]

      i.e., if 2 outputs are the same, then their inputs were the same
      i.e., no two objects in domain have the same image

   4. ƒ:A→B is an onto or surjective function
      =def (∀b ∈ B)(&exist a ∈ A)[ƒ(a) = b]
      i.e., for every possible output, there was an input

   5. ƒ:A→B is a 1-1 correspondence or a bijection
      =def ƒ is 1-1 ∧ ƒ is onto

   6. Let ƒ:A→B be a 1-1 correspondence between A and B.
      Then the inverse of ƒ is ƒ^-1:B→A = {(b,a)  |  (a,b) ∈ ƒ}

   7. Let g:A→B and ƒ:B→C.
      Then (ƒ o g):A → C =def {(a,c)  |  (∃ b ∈ B)[g(a)=b ∧ ƒ(b)=c]}
      i.e., (ƒ o g)(a) = ƒ(g(a))

   ---

5. Sequences and Series (Summations)
   1. A sequence is the output of a function on N;
      it is an ∞-tuple

   2. A series (or summation) =def the sum of some or all of the terms in a sequence.
      • ∑(i ∈ N)[a_i] = a₀ + a₁ + ...

   ---

6. Mathematical Induction
   1. Peano's version:

      (∀ set S ⊆ N) [( (0∈S) ∧ (∀k∈N) [k ∈ S → k+1 ∈ S] ) → S=N ]

   2. Property version:

      (∀ property P) [( P(0) ∧ (∀k ∈ N)[P(k) → P(k+1)]) → (∀n ∈ N)P(n) ]

   3. Rule of inference version, in "strategy" form:

      To show (∀n ∈ N)P(n):
      

      1. (base case) Show P(0)
      2. (inductive case) Show (∀k ∈ N)[P(k) → P(k+1)]:
         To do that,
         1. suppose (inductive hypothesis) P(k), for arbitrary k
            
         2. and then show P(k+1)

   ---

7. Recursive Definitions
   
   • A recursive definition tells you how to get more of something if you've got some already.

   • How do you get any in the first place?
     • That's the base case!
   1. Values of a function can be defined recursively
      in terms of "initial conditions" ("base case")
      and a "recurrence relation" ("recursive case")
      • Example: Recursive definition of Fibonacci function
        • base case (initial conditions)
          Fib(0) = 0
          Fib(1) = 1

        • recursive case (recurrence relation):
          Fib(n) = Fib(n-1) + Fib(n-2)

   2. Objects can be defined recursively
      by showing "basic" examples
      and giving rules to "construct" "new" (or more complex) objects from "old" (or less complex) ones.
      • Example: Recursive definition of rooted tree
        • base case:
          Let r be a vertex.
          Then r is a rooted tree with root r.

        • recursive case:
          Let T₁,...,T_n be disjoint rooted trees with roots r₁,...,r_n.

          Let r be a vertex different from any of these r_i.

          Then the graph consisting of r with an edge to each r_i is a rooted tree with root r.

      • Proof by structural induction:
        To show P(x) for data structure x defined recursively:
        • (base case)
          Show P(x) for the base case of x's recursive definition.

        • (recursive case)
          Suppose that P(x) holds for each of the simpler objects used to construct more complex objects x′ in the recursive definition.
          Then show that P(x′) holds for the newly constructed objects.

   3. Recursion is the heart of CS!
      • A function is "computable" ↔ it can be defined recursively
      • A function is "computable" ↔ there is a recursive algorithm for computing it.

   ---

8. Recurrence Relations
   1. The recursive case of a recursive definition

   2. Linear homogeneous recurrence relations of degree 2 with constant coefficients:
      • A generalization of the Fibonacci sequence (ƒ_n = ƒ_n-1 + ƒ_n-2):
        a_n = c₁a_n-1 + c₂a_n-2

      • Determines a "family" of sequences that differ only in their initial conditions:
        • a₀ = C₀
        • a₁ = C₁

   3. Procedure for "solving" a recurrence relation
      (i.e., finding a non-recursive formula for each term):
      1. Find the characteristic equation:

         r² — c₁r — c₂ = 0

      2. Solve it for r₁, r₂
         (use binomial formula)

      3. Find α₁, α₂ such that a_n = α₁r₁ⁿ + α₂r₂ⁿ (which is not recursive)
         by solving 2 simultaneous equations in 2 unknowns (the αs),
         using the initial conditions:
         C₀ = α₁ + α₂
         C₁ = α₁r₁ + α₂r₂

      4. Then plug the αs back into the non-recursive formula.

   ---

9. Relations
   1. Let A be a set.
      Let R ⊆ A × A be a binary relation on A.
      Then:

      i.	R is reflexive	=def	(∀a ∈ A)R(a,a)
      ii.	R is symmetric	=def	(∀a,b ∈ A)[R(a,b) → R(b,a)]
      iii.	R is anti-symmetric	=def	(∀a,b ∈ A)[R(a,b) ∧ R(b,a) → a=b]
      iv.	R is transitive	=def	(∀a,b,c ∈ A)[R(a,b) ∧ R(b,c) → R(a,c)]

   2. Let A,B,C be sets.
      Let R ⊆ A × B.
      Let S ⊆ B × C.
      Then the composite of R and S is:

      S o R =def {(a,c) ∈ A × C  |  (∃b ∈ B)[R(a,b) ∧ S(b,c)]

   3. Let R,S be binary relations on set A.
      Let P be some possible property of relations.
      Then S is the P-closure of R =def
      
      R ⊆ S
      ∧ P(S)
      ∧ &forall S′[R ⊆ S′ ∧ P(S′) → S ⊆ S′]
      1. Let Δ_A = {(a,a)  |  a ∈ A} be the "diagonal" relation on A.
         Then R ∪ Δ_A is the reflexive closure of R.

      2. R ∪ R^-1 is the symmetric closure of R.

      3. Let R* = {(a,b) ∈ A  |  ∃ path in R of length ≥ 1 from a to b}
         be the connectivity relation for R.
         Then R* is the transitive closure of R.

   4. Let R ⊆ A².
      Then R is an equivalence relation =def
      
           R is reflexive
      ∧ R is symmetric
      ∧ R is transitive
      1. Every equivalence relation creates equivalence classes
         (=def sets of elements that are equivalent to each other)

      2. The set of equivalence classes partitions the set of elements.
         • mutually exclusive subsets (equiv classes are disjoint)
         • jointly exhaustive subsets (nothing is left out)

      3. Every partition creates an equivalence relation.

   5. Let R ⊆ A².
      Then R is a partial ordering of A =def
      
           R is reflexive
      ∧ R is anti-symmetric
      ∧ R is transitive
      • E.g.: ≤, ⊆, ≥, ⊆, =
      • But not: <, ⊂, >, ⊃

   6. Let A₁,...,A_n be sets.
      Then R is an n-ary relation on the A_i
      =def R ⊆ A₁ × ... × A_n

   ---

10. Graphs
    1. Let V be a non-∅ set (of "vertices")
       Let E be a multiset of pairs of vertices (i.e., "edges").
       Then G = (V,E) is a graph.

    2. Let G be a graph.
       Then G is a di(rected )graph =def E ⊆ V²

       • A binary relation R can be represented by digraphs:

         R is reflexive	↔	every vertex has a loop
         R is symmetric	↔	every edge has an "anti-parallel" "companion"
         R is anti-symmetric	↔	the only "anti-parallel pairs" of edges are loops.
         R is transitive	↔	every path of 2 edges has a shortcut.

       • Let G be an undirected graph.
         Then | E | = (∑{v∈V_G}deg(v))/2.

       • Let G be a digraph.
         Then | E | = ∑deg^—(v) = ∑deg⁺(v).

       • Circuits and paths:
         1. An Euler circuit in graph G is_def a path that:
            1. starts & ends at the same vertex
            2. contains every edge at least once
            3. does not contain any edge more than once.

            1. An Euler path in G satisfies only (2) & (3)

            2. A connected multigraph has an Euler circuit
               ↔
               every edge has even degree

            3. A connected multigraph has an Euler path but no Euler circuit
               ↔
               it has exactly 2 vertices of odd degree

         2. A Hamiltonian circuit in graph G is_def a path that:
            1. starts & ends at the same vertex
            2. contains every vertex at least once
            3. does not contain any other vertex more than once

       • Planar graphs:
         1. Graph G is planar
            =def G can be drawn in the plane without any edges crossing.
            • Graphs containing K₅ or K_3,3 as subgraphs,
              and graphs all of whose vertices have degree > 5,
              are not planar

         2. Euler's formula:

            Let G be a connected, planar, simple graph
            that divides the plane into a set R of regions.
            Then:

            | R | = | E | — | V | + 2

       • 4 Color Thm: No map needs > 4 colors.

    ---

11. Trees
    1. A tree is a graph that:
       • is connected
       • is undirected
       • has no simple circuits

    2. Rooted trees are digraphs...
       • ...because the "parent-child" relation is an ordered pair

    3. Binary trees have vertices with ≤ 2 children:
       • "left" & "right" child, which are the roots of...
       • ... the "left" & "right" sub-trees

    4. T is a binary search tree =def:
       
       • each v ∈ V_T is labeled with name of item to be stored or searched for: key(v)

       • (∀ v ∈ V_T) [key(v)  >  key of any v′ in v's L-subtree
                               ∧ key(v)  <  key of any v′ in v's R-subtree]

    5. decision trees

    6. game trees

    7. traversals:
       • breadth-first
       • depth-first
       • pre-order
       • in-order
       • post-order