Intro to Discrete Structures Lecture 10 Pawel M Wocjan School of Electrical Engineering and Computer Science University of Central Florida wocjan eecs ucf edu Intro to Discrete StructuresLecture 10 p 1 33 Membership Table A B C B C A B C A B A C A B A C Intro to Discrete StructuresLecture 10 p 2 33 Generalized Union Definition 6 The union of a collection of sets is the set that contains those element that are members of at least one set in the collection We use the notation A1 A2 An n Ai i 1 to denote the union of the sets A1 A2 An Intro to Discrete StructuresLecture 10 p 3 33 Generalized Intersection Definition 6 The intersection of a collection of sets is the set that contains those element that are members of all sets in the collection We use the notation A1 A2 An n Ai i 1 to denote the intersection of the sets A1 A2 An Intro to Discrete StructuresLecture 10 p 4 33 Functions Definition 1 Let A and B be nonempty sets A function f from A to B is an assignment of exactly one element of B to each element A We write f a b if b is the unique element of B assigned by the function f to the element a of A We write f A B if f is a function from A to B Intro to Discrete StructuresLecture 10 p 5 33 Functions Intro to Discrete StructuresLecture 10 p 6 33 Domain Codomain Definition 2 If f A B we say that A is the domain and B the codomain of F If f a b we say that b is the image of a and b is the preimage of b The range of f is the set of all images of elements of A If f A B we also say that f maps from A to B Intro to Discrete StructuresLecture 10 p 7 33 Image Definition Let S A and f A B The image of S under the function f is the set f S t B s S t f s Intro to Discrete StructuresLecture 10 p 8 33 Injective Functions Definition 5 The function f A B is called injective or one to one iff a A b A f a f b a b Intro to Discrete StructuresLecture 10 p 9 33 Surjective Functions Definition 7 The function f A B is called surjective or onto iff b B a A f a b Intro to Discrete StructuresLecture 10 p 10 33 Bijective Function Definition 8 The function f A B is called bijective if it is both surjective and injective Intro to Discrete StructuresLecture 10 p 11 33 Examples Intro to Discrete StructuresLecture 10 p 12 33 Inverse Function Definition 9 Let f A B be a bijective function Then the inverse function f 1 is the function from B to A that assigns to b B the unique element a A such that f a b Intro to Discrete StructuresLecture 10 p 13 33 Composition of Functions Let g A B and f B C The composition of the functions f and g denoted by f g is defined by f g a f g a Intro to Discrete StructuresLecture 10 p 14 33 Composition of f and f 1 Intro to Discrete StructuresLecture 10 p 15 33 Graphs of Functions Let f A B The graph of the function f is the subset of A B defined by a b A B f a b Intro to Discrete StructuresLecture 10 p 16 33 Examples The graph of f n 2n 1 from Z to Z Intro to Discrete StructuresLecture 10 p 17 33 Examples The graph of f x x2 from Z to Z The graph of f x x2 from R to R Intro to Discrete StructuresLecture 10 p 18 33 Floor and Ceiling Functions Definition 12 The floor function assigns to the real number x the largest integer that is less or equal to x The value of the floor function is denoted by x The ceiling function assigns to the real number x the smallest integer that is greater or equal to x The value of the ceiling function is denoted by x Intro to Discrete StructuresLecture 10 p 19 33 Functions Graphs of Floor and Ceiling Intro to Discrete StructuresLecture 10 p 20 33 Factorial Function The factorial function f N Z is denoted by f n n The value of f n n is the product of the first n positive integers so n 1 2 n 1 n and f 0 1 Intro to Discrete StructuresLecture 10 p 21 33 Strictly Increasing Decreasing Definition 6 Let f A B with A B R The function f is called increasing if f x f y strictly increasing if f x f y whenever x y Intro to Discrete StructuresLecture 10 p 22 33 Addition Multiplication of Functions Definition 3 Let f1 f2 A R Then f1 f2 and f1 f2 are also functions from A to R defined by f1 f2 x f1 x f2 x f1 f2 x f1 x f2 x 1 2 Intro to Discrete StructuresLecture 10 p 23 33 Sequences and Summations Intro to Discrete StructuresLecture 10 p 24 33 Sequences Intro to Discrete StructuresLecture 10 p 25 33 Summation Intro to Discrete StructuresLecture 10 p 26 33 Intro to Discrete StructuresLecture 10 p 27 33 Intro to Discrete StructuresLecture 10 p 28 33 Intro to Discrete StructuresLecture 10 p 29 33 Intro to Discrete StructuresLecture 10 p 30 33 Intro to Discrete StructuresLecture 10 p 31 33 Intro to Discrete StructuresLecture 10 p 32 33 Intro to Discrete StructuresLecture 10 p 33 33
View Full Document
Unlocking...