Mathematical Functions In mathematics a function is an equation where you plug in a value and get an answer so to speak In particular whenever you plug in a particular value you must get a SINGLE answer You should also get the same answer always Functions graphed on the x y plane have to pass the vertical line test Now in discrete mathematics we will be using functions a bit differently we will also coin a new term relation In particular a function is a specific type of relation In standard high school mathematics we typically deal with functions of one variable We always graph a function of the form y f x where the left hand side is entirely dependent on x Depending on what the function f x is there is always a set of values that are VALID to plug in to the equation This set is the domain Similarly the answer you get out of the function will always lie in a particular set This set is the range The problem with using standard functions for discrete mathematics is that many are defined for all real numbers Namely it would be nice if we could list every value in the domain of some function But we CAN NOT list out each real number We can list out each integer however The basis of functions and relations in discrete mathematics is the idea that values of a domain and range should be subsets of a set that can be listed such as the integers color etc As we go through different things I will make analogies to mathematical functions so you can see the similarities between these and the functions and relations for discrete mathematics Relations A relation is something that relates one set of values to another set of values Sometimes the relationship that is specified between sets is meaningful other times it is not In general a relations are defined in the following manner A relation R defined over sets A and B is a subset of A x B Thus we have R A x B This is known as a binary relation because it relates elements between two sets Consider this example Let A Orange Juice Cranberry Juice Coke and B Rum Vodka Peach Schnapps If you had some modicum of taste we could define a relation Cocktails as follows Cocktails Orange Juice Vodka Cranberry Juice Vodka Coke Rum Orange Juice Peach Schnapps Of course if you do not have any standards we could have up to 9 pairs listed in our relation for Cocktails Graphically we could use a directed graph to represent this information as follows Of course you can see there are some restrictions with only being able to define binary relations For example even if we extended our sets A and B from the previous example to provide for fully stocked bar we STILL could not define a relation that would include a Long Island Ice Tea For any one not familiar with this drink it contains 4 elements from an extended version of set B Thus we should define relations between more than two items In general we can define an n ary relation as follows An n ary relation R over sets A1 A2 A3 An is a subset of the cartesian product A1 x A2 x A3 x An The degree of this relation R is n Now we could define a relation on A x A x B x B x B x B that would include a Long Island Ice tea as an element of it Of course it is probably more typical that an n ary relation be comprised of several different sets but there is no rule against defining a relation using the same set repeatedly as we have done above Also we can denote an n ary relation using a table as follows Mixer 1 Coke Mixer 2 Lemon Juice Liquor 1 Liquor 2 Liquor 3 Liquor 4 Vodka Tequila Rum Gin Composition of Relations In math class given two functions f x and g x you probably had to figure out the composition of the functions which is denoted either by f g x OR f g x Basically the way this worked is that you plugged in your original x into one function THEN you used the answer that you got from that function to plug in to the second function And the order in which you did it mattered The same will be true of the composition of two relations Here is the formal definition of the composition of two relations R and S where R A x B S B x C R S a c a A c C b a b R b c S Notice the difference in order here When we compose a relation we write the relations in the order we apply them not the opposite order as is done with functions Basically when you compose the relations R and S you get a third relation which relates elements from the set A to the set C as long as the answer from relation R can be the input for relation S We can use a directed graph again Consider this example A ABC NBC CBS FOX HBO B NYPD Blue Simpsons Letterman ER X Files Dennis Miller Show Monday Night Football C Dennis Miller Marge Rick Schroeder Gillian Anderson Noah Wyle David Letterman R ABC NYPD Blue NBC ER CBS Letterman HBO Dennis Miller Show FOX X Files S MNF Dennis Miller Simpsons Marge ER Noah Wyle X Files Gillian Anderson D Miller Show Dennis Miller NYPD Rick Schroeder Theorems about Relation Composition If R A x B S B x C and T C x D then we have the following R S T R S T Essentially when doing associativity is preserved multiple relation composition First of all we see that both sides define a relation over the set A x D Next we have to prove that both define the same relation over that set Formally if we break down the definition we have R S T a d a A and d D and for some c C a c R S and cTd Since a c R S means aRb and bSc for some b B by definition of R S the relation R S T consists of pairs a d A D such that for some b B and some c C aRb bSc and cTd If we break down the definition of R S T in a similar manner we will get the exact same thing Similarly using the directed graph of the situation will lead to the same conclusion Let R A B S B C and T B C denote 3 binary relations Then we have the following 1 R S T R S R T 2 R S T R S R T Usually this is a proper subset Here is why the first one holds First plug into the definition of R S T R S T a c a A c C b B aRb b c S T …
View Full Document
Unlocking...