Discrete Structures

# Course Summary

 Last Update: 27 April 2009 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:
• N+ = 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 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 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. (pq) (conjunction)
3. (pq) (inclusive disjunction)
4. (pq) (exclusive disjunction)
5. (pq) (material conditional)
6. (pq) (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: pq iff, for all rows of t-table, tval(p) = tval(q)

• 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

• Direct proof of conditional
(to show (pq), suppose p & show q)

(to show p, suppose ¬p & derive contradiction)

• 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 as list of elements: S = {e1, …, en}

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

4. empty set: ∅ = {}

5. S = T ↔ ∀x[xSxT]

3. Venn diagrams, Euler circles

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

5. 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"

6. 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 of A to B
∧ (∀aA)(∀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. ƒ: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 (ƒ 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 on 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 show (∀nN)P(n):

1. (base case) Show P(0)
2. (inductive case) Show (∀kN)[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 T1, …, Tn be 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.

• 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 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. Find the characteristic equation:

r² – c1rc2 = 0

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

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.

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

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 edge 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

• Planar graphs:

1. Graph G is planar
=def G can be drawn in the plane without any edges crossing.

• Graphs containing K5 or K3,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
• has no simple circuits

• (i.e., has no circuits & no multiple edges)

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. traversals: