1. Set

Representations

Finite set: $C = \{a,b,…,k\}$

Infinite set: $C = \{a,b,k, …\}$

Others:

$S=\{j:j>0,\text{and j = 2k for k > 0}\}$

$S=\{j:\text{j is nonnegative and even}\}$ 无二义性

$\overline{\empty} = \text{Universal Set}$

DeMorgan’s Laws

$$ \overline{A\cup B} = \overline{A} \cap \overline{B} \\ \\ \overline{A\cap B} = \overline{A} \cup \overline{B} $$

Powersets

Powerset of S = the set of all the subsets of S (include $\empty$)

$P(S) = 2^S$

$|2^S| = 2^{|S|} ~(8 = 2^3)$

2. Functions

• If A = domain then f is a total function otherwise f is a partial function
• If f: A -> B is a bijection
  • f is total
  • for all a and a’ in A, a!=a’ implies f(a)!=f(a’)
  • for all b in B, there is a in A with f(a)=b

Big-Oh Notation

• Given two total function f,g:N→N,
  • we write f(n) = O(g(n)), if there are positive integers c and d such that, for all n≥ d, f(n) ≤ cg(n);
  • we write f(n) = Ω(g(n)), if there are positive integers c and d such that, for all n≥ d, cf(n) ≥ g(n).
• If f(n) = O(g(n)) and f(n) = Ω (g(n)), then we write f(n) = θ(g(n)).