Discrete Structures

Course Summary

 Last Update: 20 September 2013 Note: or material is highlighted

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. (AB) (conjunction)
3. (AB) (inclusive disjunction)
4. (AB) (exclusive disjunction)
5. (AB) (material conditional)
6. (AB) (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: AB 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 ti are terms (noun phrases),

then P(t1, …, tn) 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
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 (pq):
suppose p;
& prove q

To prove p:
suppose ¬p;

• Etc.

3. Sets

1. basic data structure for constructing all math & CS objects

2. Sets & elements (members):

1. eS: e is an element of set S

2. set described "extensionally" as list of elements: S = {e1, …, en}

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

4. empty set: ∅ = {}

5. S = T ↔ ∀x[xSxT]

3. Subsets:

1. ST ↔ ∀x[xSxT]
2. power set of S: (S) = {T  |  TS}
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)  |  sStT}

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

2. union: ST = {s  |  s &isin Ss &isin T}

3. intersection: ST = {s  |  s &isin Ss &isin T}

4. set difference: ST = {s  |  s &isin Ss ¬in T}

5. set complement: ‾S = US, 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 ƒ : AB is a function from A to B
=def ƒ is a binary relation from A to B
∧ (∀aA)(∀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. ƒ:AB is a 1-1 or injective function
=def (∀a, a′ ∈ A)(∀bB)[((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. ƒ:AB is an onto or surjective function
=def (∀bB)(&exist aA)[ƒ(a) = b]

i.e., for every possible output, there was an input

5. ƒ:AB is a 1-1 correspondence or a bijection
=def ƒ is 1-1 ∧ ƒ is onto

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

7. Let g:AB and ƒ:BC.
Then the composition of ƒ with g
(where g's output becomes ƒ's input)
is:
(ƒ o g):AC =def {(a, c)  |  (∃ bB)[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.

• (iN)ai = a0 + a1 + …

6. Mathematical Induction

1. Peano's version:

(∀ set SN) [( (0 ∈ S) ∧ (∀kN) [kSk+1 ∈ S] ) → S = N]

2. Property version:

(∀ property P) [( P(0) ∧ (∀kN)[P(k) → P(k+1)]) → (∀nN)P(n) ]

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

To prove (∀nN)P(n):

1. (base case) Prove P(0)
2. (inductive case) Prove (∀kN)[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?

(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
(AB)
(AB)
(AB)
(AB)
(AB)
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 t1, …, tn be terms.
Then P(t1, …, tn) is a wff of FOL.

• recursive case:
Let A, B be wffs of FOL.
Let v be a variable.
Then:  ¬A
(AB)
(AB)
(AB)
(AB)
(AB)
∀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):
an = c1an–1 + c2an–2

• Determines a "family" of sequences that differ only in their initial conditions:

• a0 = C0
• a1 = C1

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

1. Set up the characteristic equation:

r² – c1rc2 = 0

2. Solve it for r1, r2 (where r1r2)

3. Find α1, α2 such that an = α1r1n + α2r2n (which is not expressed recursively)
by solving 2 simultaneous equations in 2 unknowns (the αs),
using the initial conditions:

C0 = α1 + α2
C1 = α1r1 + α2r2

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 A1, …, An be sets.
Then R is an n-ary relation on the Ai
=def R ⊆ A1 × ... × An

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 isdef 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 isdef 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 T1, …, Tn be (a "forest" of) disjoint rooted trees with roots r1, …, rn.

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

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