Mathematical FunctionsIn 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 aSINGLE answer. (You should also get the same answeralways.) Functions graphed on the x-y plane have to pass thevertical line test.Now, in discrete mathematics, we will be using functions a bitdifferently & we will also coin a new term “relation”. Inparticular, a function is a specific type of relation.In standard high school mathematics, we typically deal withfunctions of one variable. We always graph a function of theform 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 ofvalues that are VALID to “plug” in to the equation. This set isthe domain. Similarly, the “answer” you get out of the functionwill always lie in a particular set. This set is the range.The problem with using standard functions for discretemathematics is that many are defined for all real numbers.Namely, it would be nice if we could list every value in thedomain of some function. But, we CAN NOT list out each realnumber. (We can list out each integer however...)The basis of functions and relations in discrete mathematics isthe idea that values of a domain and range should be subsets ofa set that can be listed, such as the integers, color, etc.As we go through different things, I will make analogies tomathematical functions, so you can see the similarities betweenthese and the functions and relations for discrete mathematics.RelationsA relation is something that relates one set of values to anotherset of values. Sometimes the relationship that is specifiedbetween 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 relationCocktails 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 upto 9 pairs listed in our relation for Cocktails.Graphically, we could use a directed graph to represent thisinformation as follows:Of course, you can see there are some restrictions with onlybeing able to define binary relations. For example, even if weextended our sets A and B from the previous example toprovide for fully stocked bar, we STILL could not define arelation that would include a Long Island Ice Tea. (For any onenot familiar with this drink, it contains 4 elements from anextended 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 thecartesian product A1 x A2 x A3 ... x An. The degree of thisrelation R is n.Now, we could define a relation on A x A x B x B x B x B thatwould include a Long Island Ice tea as an element of it.Of course, it is probably more typical that an n-ary relation becomprised of several different sets, but there is no rule againstdefining a relation using the same set repeatedly, as we havedone above.Also, we can denote an n-ary relation using a table as follows:Mixer 1 Mixer 2 Liquor 1 Liquor 2 Liquor 3 Liquor 4Coke LemonJuiceVodka Tequila Rum Gin... ... ... ... ... ...Composition of RelationsIn math class, given two functions f(x) and g(x), you probablyhad to figure out the composition of the functions, which isdenoted either by f(g(x)) OR fg(x).Basically, the way this worked is that you “plugged in” youroriginal x into one function, THEN you used the “answer” thatyou 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. Hereis the formal definition of the composition of two relations Rand 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 arelation, we write the relations in the order we apply them, notthe opposite order, as is done with functions.) Basically, whenyou compose the relations R and S, you get a third relationwhich relates elements from the set A to the set C, as long asthe “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 CompositionIf R A x B, S B x C and T C x D, then we have thefollowing:(R S) T = R (S T)Essentially, when doing multiple relation composition,associativity is preserved.First of all, we see that both sides define a relation over the setA x D. Next, we have to prove that both define the samerelation 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, bydefinition 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, bScand cTd.If we break down the definition of R (S T) in a similarmanner, we will get the exact same thing. Similarly, using thedirected 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
View Full Document
Unlocking...