Discrete Math

Lecture slides

What is a set defined by enumeration?

{1, 2, 3}

What is a set defined by property?

{x ∈ S | T(x)}, e.g., {x ∈ N | 1 ≤ x ≤ 5}

What is the empty set?

∅

What does A ⊂ B mean?

All elements of A are elements of B

When are two sets equal?

A = B ⇔ A ⊂ B and B ⊂ A

What is cardinality of a finite set?

#S or |S|

What is the power set of S?

P(S) or 2^S, the set of all subsets of S

Theorem on power set cardinality?

If #S = n, then #P(S) = 2^n

What is the complement of A?

Ā — elements in universal set but not A

What is union A ∪ B?

Elements in A or B or both

What is intersection A ∩ B?

Elements in both A and B

What is difference A \ B?

Elements in A but not B

What is symmetric difference A △ B?

(A ∪ B) \ (A ∩ B) = (A \ B) ∪ (B \ A)

Example: A={0,1,2,3,4}, B={2,4,6,8,10}, A △ B?

{0,1,3,6,8,10}

What is Cartesian product A × B?

{(a,b) | a ∈ A, b ∈ B}

Example: A={0,1,2}, B={1,2}, A × B?

{(0,1),(0,2),(1,1),(1,2),(2,1),(2,2)}

De Morgan’s laws?

(A ∪ B)̄ = Ā ∩ B̄ and (A ∩ B)̄ = Ā ∪ B̄

What is N?

{1, 2, 3, …}

What is Z?

{…, −2, −1, 0, 1, 2, …}

What is the existential quantifier?

∃

What is the universal quantifier?

∀

Example of ∃?

∃n ∈ N : 2n = 6

Example of ∀?

∀m ∈ N : m ∈ Z

What is a function?

Association x ↦ f(x); subset of D × R with unique f(x) per x

Meaning of := ?

Definition, let it be equal with

Example function: x ∈ R, x ↦ ?

x²

Not a function: x ∈ R⁺, x ↦ ?

number with square x

Function: n ∈ N, n ↦ ?

greatest odd divisor of n

Constant function?

f(x) = c

First order function?

f(x) = ax + b, a ≠ 0

Second order factored form?

a · (x − (−b+√(b²−4ac))/2a) · (x − (−b−√(b²−4ac))/2a)

Injective definition?

f(a) = f(b) implies a = b

Surjective definition?

∀ y ∈ R ∃ x ∈ D : f(x) = y

Bijective?

Injective and surjective

Mathematical induction base step?

Prove for n = 1

Inductive hypothesis?

Assume true for k

Inductive step?

Prove true for k + 1

Example to prove by induction?

1 + 3 + … + (2n−1) = n², ∀n ∈ N