Functions Read Section 1.8 MSU/CSE 260 Fall 2009 1 Outline Introduction: definitions, example and terminology, image of a subset of domain, sum and product of functions One-to-one functions: strictly increasing, decreasing functions Onto functions Bijections: identity functions

Graphs of Functions Inverse Functions Compositions of Functions Some Important Functions: Floor, Ceiling and Factorial functions MSU/CSE 260 Fall 2009 2 Function Example Consider your final grades in CSE 260. Your grades will be one of the values from the set {4, 3.5, 3, 2.5, 2, 1.5, 1, 0} What kind of properties does this assignment

have? Consider the courses you are taking this semester. { (A123, CSE 260), (A123, CSE 232), (A123, MTH 234), (A123, DYLANTHOMAS 111)} What kind of properties does this assignment have? MSU/CSE 260 Fall 2009 3 Introduction Definition: Let A, B be sets. A function f from A to B, denoted f: A B, is an assignment where each element of A is assigned exactly one element of B. Notation:

f: A B We write f (a) = b, if b is the element of B assigned under f to the element a of A. We also say f maps A to B Formally, f is a function from A to B if and only if xA !yB f(x) = y. where ! is the uniqueness quantifier. MSU/CSE 260 Fall 2009 4 Example f: A B Students A Adams Marie Stevens Sara

Grades 4 3 2 1 0 MSU/CSE 260 Fall 2009 B f(Adams)=1 f(Marie)=4 f(Stevens)=3 f(Sara)=3 5 Domain, Co-domain, Definition: Let f be a function from A to B, that is, f: A B. Then A is called the domain of f, and B is the codomain of f. If f(a) = b, then

b is called the image of a, and a is a pre-image of b. The range of f is the set of all images of elements of A. How are codomain and range related? Range is a subset of the codomain MSU/CSE 260 Fall 2009 6 Example f (Adams)=1 f (Marie)=4

f: A B Students A f (Stevens)=3 Adams Marie Stevens Sara f (Sara)=3 Grades 4 3 2 1 0 B The image of Marie is 4; the pre-images of 3 are Stevens and Sara; the range of f is {1, 3, 4}.

MSU/CSE 260 Fall 2009 7 Sum, Products of real-valued Functions Definition: Let f1 and f2 be functions from A to R. Then f1 + f2 and f1 f2 are also functions from A to R, defined as: (f1 + f2)(x) = f1(x) + f2(x) (f1 f2)(x) = f1(x) f2(x) Note that if f1 and f2 do not have the same domain, the above operations do not make sense. MSU/CSE 260 Fall 2009

8 Image of a subset of a domain Definition: Let f be a function from A to B, and let S be a subset of A. The image of S, denoted f (S), is the subset of B consisting of the images of the elements of S. Formally: f (S) = { f (s) | s S}. Note that f (A) is the range of f . In the previous Example, f ({Adams, Sara}) = {3, 1} MSU/CSE 260 Fall 2009

9 One-to-one Functions Definition: A function f from A to B is said to be one-to-one, or injective, if and only if distinct elements of the domain have distinct images. That is, xA yA f (x) = f (y) x = y. a b c 1 2 3 4 MSU/CSE 260 Fall 2009 10 Onto Functions

Definition: A function f from A to B is said to be onto, or surjective, if and only if its range and codomain are the same. That is, yB xA f(x) = y. a b c d 1 2 3 MSU/CSE 260 Fall 2009 11 Bijections Definition: A function f: A B is a bijection, or one-to-one correspondence, if it is both one-to-one and onto.

Note that the cardinalities (when dealing with finite sets) of domain and codomain of a bijection are equal. a b c d 1 2 3 4 MSU/CSE 260 Fall 2009 12 Summary of Function Types 1-to1 but not onto a b c

Neither 1-to-1 nor onto 1 2 3 4 a b c d onto but not 1-to-1 both 1-to-1 and onto; bijection a b c d a b c

d 1 2 3 1 2 3 4 a b c MSU/CSE 260 Fall 2009 1 2 3 4 1 2 Not a 3 function 4 13

Monotonic Functions Definition: Let A and B be subsets of R, the set of real numbers. A function f: A B is strictly increasing if xA yA x < y f (x) < f (y). f: A B is strictly decreasing if xA yA x < y f (x) > f (y). Note that strictly increasing, or strictly decreasing (strictly monotone) functions must be one-to-one. MSU/CSE 260 Fall 2009 14 Inverse Function Definition: Let function f: A B be a bijection. The inverse function of f, denoted f -1, is the function, f -1 : B A, that assigns to each element b

of B the element a of A such that f (a) = b. aA bB f(a) = b f -1(b) = a. f is called invertible. f a b c d 1 2 3 4 MSU/CSE 260 Fall 2009 f -1(1) = d f -1(2) = b

f -1(3) = a f -1(4) = c 15 Inverse Function Example: Let f : Z Z, where f (x) = x + 1. f is a bijection; what is f -1? Suppose f (x) = y; then x + 1= y; so x = y - 1= f -1(y) f -1(x) = x 1. MSU/CSE 260 Fall 2009 16 Identity Function

Let A be a set. The identity function on A is the function A : A A, where x A A (x) = x. Notes: A assigns each element of A to itself. A is a bijection. MSU/CSE 260 Fall 2009 17 Characteristic and Constant Functions Let A be a subset of universe U. The characteristic function fA : U {0, 1}, is

such that fA (x) = 1 if x A and fA (x) = 0 if (x A ) Let A be a set. The constant function f : A {t} maps each element of A to the same value t. MSU/CSE 260 Fall 2009 18 Compositions of Functions Definition: Let g be a function from A to B and f a function from B to C, that is, g: A B f: B C The composition of f and g, denoted f o g, is function from A to C, defined as follows xA ( f o g)(x) = f (g(x)). A={a, b, c, d} B={q, p , k, v} C={1, 2, 3, 4}

g a b c d q p k v f MSU/CSE 260 Fall 2009 1 2 3 4 (f o g)(a) = 2 (f o g)(b) = 3 (f o g)(c) = 1 (f o g)(d) = 2

19 Composition of Functions fog g A f B MSU/CSE 260 Fall 2009 c 20 Example Consider the two functions f : Z Z, where f (x) = 2x + 3 g: Z Z, where g (x) = 3x + 2.

What are f o g, and g o f ? f o g: Z Z, where (f o g)(x) = f (g(x)) = f (3x + 2) = 2(3x + 2) + 3 = 6x +7 g o f: Z Z, where (g o f )(x) = g( f (x)) = g (2x + 3) = 3(2x + 3) +2 = 6x + 11 MSU/CSE 260 Fall 2009 21 Example Consider the following R R functions: 1 3 f ( x) x 4 x g ( x) 2 h( x ) x 4 x 1 Compute the following:

1. f f 5. f h 2. f g 6. f (h g ) 3. g f 7. ( f h) g 4. h g MSU/CSE 260 Fall 2009 22 Example Consider the following R R functions : f ( x) x3 4 x g ( x) 1 x2 1 h( x ) x 4 Compute the following : 1.

f f f ( x 3 4 x ) ( x 3 4 x )3 4( x 3 4 x ) 3 2 2 1 1 1 1 4( x 1) 2. f g f ( g ( x )) f 2 2 4 2 ( x 2 1)3 x 1 x 1 x 1 1 3. g f g ( f ( x )) g ( x 3 4 x ) 3 ( x 4 x)2 1 Note that f g g f MSU/CSE 260 Fall 2009 23 Example. 1 g ( x) 2

x 1 3 Recall that f ( x ) x 4 x 4. h g h( g ( x )) 1 x2 1 1 6. f (h g ) f 2 x 1 4 4 h( x ) x 4 4

4 4 3 5. f h f ( x ) ( x ) 4( x 4 ) 1 2 x 1 4 3 1 4 4 2

x 1 3 1 1 4 7. ( f h ) g 2 4 2 x 1 x 1 Note that at least for this example we have f (h g ) ( f h) g In fact, the above is true always. MSU/CSE 260 Fall 2009 24

Graph of a Function Definition: Let f: A B. The graph of f is the set of ordered pairs Gf = {(x, f (x)) | x A}. MSU/CSE 260 Fall 2009 25 Graph of a Function. The graph of the function f : Z Z, where f (n) = 2n + 1, is Gf = {(n, 2n + 1) | n Z} (2,5) f (n) (1,3) (0,1) (-1,-1)

n MSU/CSE 260 Fall 2009 26 Important Integer Functions Whole numbers constitute the backbone of discrete mathematics. We often need to convert fractions or arbitrary real numbers to integers. These integer functions will help us do that. Besides the identity function, some important functions are: The floor function, The ceiling function, The mod function.

MSU/CSE 260 Fall 2009 27 Floor Function Definition: The floor function from R to Z assigns to the real number x, the largest integer x. The value of the floor function at x is denoted by x. xR nZ x = n n x < n + 1. Examples:

18 = 18 3.75 = 3 4.5 = 5 MSU/CSE 260 Fall 2009 28 Ceiling Function The ceiling function from R to Z assigns to the real number x the smallest integer x. The value of the ceiling function at x is denoted by x. xR nZ x = n n 1 < x n. xR x 1 < x x x < x + 1. Examples:

18= 18 3.75 = 4 4.5 = 4 MSU/CSE 260 Fall 2009 29 Floor and Ceiling Functions, recap * x x 0 * x x MSU/CSE 260 Fall 2009

30 Properties of x and x xR xR xR xR xR xR xR xR xR nZ x = n n x < n + 1. nZ x = n n 1 < x n. nZ x = n x 1 < n x.

nZ x = n x n < x +1. x 1 < x x x < x + 1. x = x x = x mZ x + m = x + m mZ x + m = x + m * x * x 0 x x MSU/CSE 260 Fall 2009 31 Example Prove or disprove the following statements about real numbers: a)

x x b) 2 x 2 x c) x y x y {0,1} d) xy x y e) x x 1 2 2 MSU/CSE 260 Fall 2009 32 Example: Solution Prove or disprove the following statements about real numbers: a) x x Answer: True b)

2 x 2 x Answer: False, try x c) x y x y {0,1} Answer: True d) xy x y 1 Answer: Fasle, try x , y 3 4 e) x x 1 2 2 Answer: Fasle, try x 4

MSU/CSE 260 Fall 2009 1 2 33 Integer Functions MSU/CSE 260 Fall 2009 34 MSU/CSE 260 Fall 2009 35 Example Prove or disprove the following statements about real numbers: a) x x b) 2 x 2 x c)

x y x y {0,1} d) xy x y e) x x 1 2 2 MSU/CSE 260 Fall 2009 36 Example: Solution Prove or disprove the following statements about real numbers: a) x x Answer: True b) 2 x 2 x Answer: False, try x c) x y x y {0,1} Answer: True

d) xy x y 1 Answer: False, try x , y 3 4 x x 1 e) 2 2 1 2 Answer: False, try x 4 MSU/CSE 260 Fall 2009 37 The mod Function

When dividing an integer n by a number m , the quotient of the division is n/m. What about a simple notation for the remainder of this division? Thats what the mod function is about: n mod m m is called modulus n = m n/m + n mod m quotient remainder MSU/CSE 260 Fall 2009 38 Example Formally, the mod function is a mapping: mod : Z Z+ N where n mod m = n m n/m

Examples: 5 mod 3 = 5 (3 5/3 ) = 5 (3 1.6 ) = 5 (3 1 ) = 2 MSU/CSE 260 Fall 2009 39 Example n mod m = n (m n/m ) Examples: -5 mod 3 = -5 (3 -5/3 ) = -5 (3 -1.6 ) = -5 (3 (-2)) = 1. We also write: 5 2 mod 3, 9 0 mod 3, -5 1 mod 3. MSU/CSE 260 Fall 2009

40 mod Function m + 0 m-1 1 2 MSU/CSE 260 Fall 2009 41 List Search Methods Problem: Given a list of elements, how fast can we decide whether or not a given input element belongs to the list?

Linear search Binary search; need to sort the list first Hash table MSU/CSE 260 Fall 2009 42 Hash Functions MSU/CSE 260 Fall 2009 43 Hash Functions A hash function h: keys integers maps keys to small integers (buckets) Ideal features:

The function should be easy to compute The range values should be evenly distributed Given an image, it should not be easy to find its pre-image Applications Searching/indexing Information hiding File signature MSU/CSE 260 Fall 2009 44 Hashing for Indexing

A hash function h: keys integers maps keys to small integers (buckets) Ideally this mapping is done in a random manner so that the bucket values are evenly distributed despite irregularities in the keys. For simplicity, we will assume that the keys are also integers, denoted by k, and the number of buckets is demoted by m. Note that the buckets are indexed 0 through m - 1. MSU/CSE 260 Fall 2009 45 Example Storing CSE 260, both sections, PIDs\A Using Hash Function h(PID) = k mod 31 Histogram

Frequency 9 8 7 6 5 4 3 2 1 0 0 1 2 3 4 5

6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 Bin MSU/CSE 260 Fall 2009 46

Simple Hash Functions h(k) = k mod m Suggestion: Choose m to be a prime number that isnt close to a power of 2. h(k) = k(k + 3) mod m MSU/CSE 260 Fall 2009 47 Hashing for Hiding Information Here, the hash function maps a string to another string with the property of being very difficult to reverse the result of the

hash. Used in hiding users password MSU/CSE 260 Fall 2009 48 How password is checked. MSU/CSE 260 Fall 2009 49 Hashing for file signature The hash function maps a large string (e.g., a file) to a fixed size string called digest Examples:

MD5 (Message-Digest algorithm 5), gives a 128-bit hash (digest) SHA-1 (Secure Hash Algorithm) is a most commonly used from SHA series of cryptographic hash functions, designed by the National Security Agency SHA-1 produces the 160-bit hash value. Original SHA (or SHA-0) also produce 160-bit hash value, but SHA-0 has been withdrawn by the NSA shortly after publication and was superseded by the revised version commonly referred to as SHA-1. The other functions of SHA series produce 224-, 256-, 384- and 512-bit hash values. MSU/CSE 260 Fall 2009 50 Secure Hashes in Python >>> from hashlib import md5 >>> md5("cse201").hexdigest() 'fa8190eb6032a99f61d822c2474980bf >>> from hashlib import sha1 >>> sha1("cse201").hexdigest() '44dd02666ee30406837b6b5897c6d013fdf4 1dc1'

MSU/CSE 260 Fall 2009 51