Discrete Mathematics

Discrete Mathematics CS 2610 : Discrete Mathematics CS 2610 September 12, 2006

Agenda : Agenda Last class Functions Vertical line rule Ordered pairs Graphical representation Predicates as functions This class More on functions!

Function Terminology : Function Terminology Given a function f:AB A is the domain of f. B is the codomain of f. If f(a)=b, b is the image of a under f. a is a pre-image of b under f. In general, b may have more than 1 pre-image. The range R of f (or image of f) is : R={b | a f(a)=b } -- the set of all images For any set S  A, the image of S, f(S) = { b  B | a  S, b = f(a)} For any set T  B, the inverse image of T f−1(T) = { a  A | f(a)  T }

Example : Example f A B Domain Codomain The image of Mike under f is John Smith Mike is a pre-image of John Smith under f R (f) = {John Smith, Richard Boone} f(Mike,Mario,Jill) = {John Smith, Richard Boone} f-1(Richard Boone) = {Joe, Jill}

Example : Example Given a function f: Z  Z where f(x) = x2 -- the domain of f is the set of all integers -- the codomain of f is the set of all integers -- the range of f is the set of all integers that are perfect squares {0, 1, 4, 9, 16, 25, …}

Function Composition : Function Composition Given the functions g:AB and f:BC, the composition of f and g, f ○g: AC defined as f ○g (a) = f ( g (a) ) f ○g (h) ?

Function Composition : Function Composition Properties Associative: Given the functions g:AB and f:BC and h:CD then h ○ (f ○g)  (h ○ f ) ○ g

Function Self-Composition : Function Self-Composition A function f: AA (the domain and codomain are the same) can be composed with itself f: People  People where f(x) is the father of x f ○f (Mike) is the father of the father of Mike f ○f ○ f (Mike) ? f ○f ○ f ○ f(Mike) ?

Injective Functions (one-to-one) : Injective Functions (one-to-one) A function f: A  B is one-to-one (injective, an injection) iff f(x) = f(y)  x = y for all x and y in the domain of f (xy(f(x) = f(y)  x = y)) Equivalently: xy(x  y  f(x)  f(y)) Every b  B has at most 1 pre-image

Surjective Functions (onto) : Surjective Functions (onto) A function f: A  B is onto (surjective, an surjection) iff yx( f(x) = y) where y  B, x  A Every b  B has at least one pre-image

Bijective Functions : Bijective Functions A function f: A  B is bijective iff it is one-to-one and onto (a one-to-one correspondence) f The domain cardinality equals the codomain cardinality A B

Inverse Functions : Inverse Functions Let f : A  B be a bijection, the inverse of f, f -1:B  A such that for any b  B, f -1(b) = a when f (a) = b A B f f-1

Inverse Functions : Inverse Functions Let f: A  B be a bijection, and f-1:B  A be the inverse of f: f-1 ○ f = IA = (f-1○f)(a) = f-1 (f(a)) = f-1 (b) = a f ○ f-1 = IB = (f○f-1)(b) = f(f-1 (b)) = f(a) = b A B f f-1

Functions: Real Functions : Functions: Real Functions Given f :RR and g :RR then (f  g): RR, is defined as (f  g)(x) = f(x)  g(x) (f . g): RR is defined as (f g)(x) = f(x) × g(x) Example: Let f :RR be f(x) = 2x and g :RR be g(x) = x3 (f+g)(x) = x3+2x (f . g)(x) = 2x4