Course Summary

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

     but probably not:

   • Q = rational numbers (dense)
     • except when considering them as ordered pairs of integers

     and certainly not:

   • R = real numbers (continuous)
     • except when considering them by finite approximation (as computers do; see Braverman 2013)

   ---

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

   3. The study of any 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 A "correctly" describes "the world",
             then tval(A) = T
             else tval(A) = F

   4. propositional logic:
      1. syntax of truth-functional connectives:
         1. ¬A (negation)
         2. (A ∧ B) (conjunction)
         3. (A ∨ B) (inclusive disjunction)
         4. (A ⊕ B) (exclusive disjunction)
         5. (A → B) (material conditional)
         6. (A ↔ B) (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. logical equivalence: A ≡ B iff, for all rows of t-table, tval(A) = tval(B)
            • DeMorgan, distributive laws, etc.

   5. first-order predicate logic:
      1. "sub-atomic" propositions:
         • If "P" is an n-place predicate
           
           (names a property of a single object
           or a binary relation between 2 objects
           or an n-ry relation among >2 objects)

           and t_i are terms (noun phrases),

           then 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(all 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
         • To prove ∀xA(x):
           choose arbitrary object c in domain;
           prove A(c);
           then invoke UG to justify ∀xA(x)

         • Direct proof of conditional:
           To prove (p→q):
           suppose p;
           & prove q

         • Proof by contradiction:
           To prove p:
           suppose ¬p;
           & derive contradiction

         • Etc.

   ---

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

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

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

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

      4. empty set: ∅ = {}

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

   3. 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 |

   4. 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 between A and B
           =def R &sube A × B

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

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

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

      5. set complement: ‾S = U – S, where U is the "universe"

   5. Proof Strategies for Sets:
      • e.g.)
        To prove that 2 sets are equal:
        Replace each set by its definition (using Di–v);
        Then use FOL proof strategies to prove that the defs are equivalent.
        • 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 from A to B
              ∧ (∀a ∈ A)(∀b, b′∈ B)[((a, b) ∈ ƒ ∧ (a, b′) ∈ ƒ) → b = b′]

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

      (Warning: This way of saying it may make it easier to understand,
      but it also makes it trivially true!)

      i.e., same input → same output
      i.e., no two objects in range have the same pre-image
      i.e., no two outputs have the same input

   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 the composition of ƒ with g
      (where g's output becomes ƒ's input)
      is:
      (ƒ 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 whose domain is 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 prove (∀n ∈ N)P(n):
      

      1. (base case) Prove P(0)
      2. (inductive case) Prove (∀k ∈ N)[P(k) → P(k+1)]:
         To do that,
         1. suppose (inductive hypothesis) P(k), for arbitrary k
            
         2. and then prove 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?
     • You are given them for free!
       (That's the base case!)
   1. Values of some functions (the computable ones) 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.
      1. Example: Recursive definition of well-formed formula of propositional logic
         • base case:
           Let p be an atomic proposition.
           Then p is a wff of propositional logic

         • recursive case:
           Let A, B be wffs of propositional logic.
           Then:  ¬A
                      (A ∧ B)
                      (A ∨ B)
                      (A ⊕ B)
                      (A → B)
                      (A ↔ B)
           are all wffs of propositional logic.

      2. Example: Recursive definition of well-formed formula of FOL
         • base case:
           Let P be an n-place predicate.
           Let t₁, …, t_n be terms.
           Then P(t₁, …, t_n) is a wff of FOL.

         • recursive case:
           Let A, B be wffs of FOL.
           Let v be a variable.
           Then:  ¬A
                      (A ∧ B)
                      (A ∨ B)
                      (A ⊕ B)
                      (A → B)
                      (A ↔ B)
                      ∀vA
                      ∃vA
           are all wffs of FOL.

      3. Example: Recursive definition of rooted tree

   3. Proof by structural induction:
      To prove P(x) for data structure x defined recursively:
      • (base case)
        Prove 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 prove that P(x′) holds for the newly constructed objects.

   4. 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 recurrence (ƒ_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. Set up the characteristic equation:

         r² – c₁r – c₂ = 0

      2. Solve it for r₁, r₂ (where r₁ ≠ r₂)
         (use quadratic formula)

      3. Find α₁, α₂ such that a_n = α₁r₁ⁿ + α₂r₂ⁿ (which is not expressed recursively)
         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
         (i.e., the boldfaced formula in Ciii, above)

   ---

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 R ⊆ A × 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.
         • Namely, the relation of being in the same subset.

   3. 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 (or "bag") 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 is a "bag" of ordered pairs of vertices

       • A binary relation R can be represented by digraphs:

         R is reflexive	↔	every vertex has a loop
         R is symmetric	↔	for each edge, there is an inverse edge
         R is anti-symmetric	↔	the only pairs of inverse edges are loops.
         R is transitive	↔	every path of 2 edges has a shortcut.

       • 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.

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

            1. A connected multigraph has an Euler circuit
               ↔
               every vertex has even degree

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

         3. 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
            1. Traveling Salesman problem:
               1. Given a graph, find its shortest Hamiltonian circuit
               2. This is: NP, NP-hard, & NP-complete

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

    ---

11. Trees

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

    2. 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 (a "forest" of) 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.

1. What should I study for the final exam?

2. How should I study?