Understanding Functions and Relations
Explore the concepts of functions and relations in mathematics, including the unique characteristics of functions, the power of relations, and the distinction between functions and relations. Learn about the theoretical basis for functional programming languages and the essential properties of functions.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Functions Are Relations A function is a relation where for a given input the output is unique. A relation may produce many different outputs for the same input. All functions are relations but most relations are not functions. Source set Target set w a x b y z c Functions are the theoretical basis for Functional programming languages such as Miranda and Haskell. 7.2
Relations are much more powerful than functions. And therefore relations take a lot more computer power to process than functions. That s why Relational databases are relatively slow. The advantages databases totally disadvantage though. of outweigh Relational this 7.3
Relations Are Not (Often) Functions This diagram shows a relation, not a function. Given an input of b the output may be any member of the set { w, y, z }. Source set Target set w a x b y z c 7.4
Functions Are Relations II Since functions are relations a function has a source and target. The source is the set of all possible inputs. The target is the set of all possible outputs. For a totalfunction dom f= source, ran f target For a partial function dom f source, ran f target For a given input the output of a function is unique. x dom f; y, z ran f f(x) = y f(x) = z y = z 7.5
Notation Essentially a function and a program are the same thing. Each takes an input value and transforms it into an output value. To emphasise the input output transformation we usually use one directional arrows when defining functions. Just as we use the two directional arrow when defining relations. R X Y If f is a function from A to B, we write f:A B The words mapping, transformation, correspondence, and operator are used as synonyms for function. 7.6
A total function f from set A to set B is a rule of correspondence that assigns to each element x in the set A exactly one element y in the set B. to each element x in the set A exactly one element y in the set B. to each element x in the set A exactly one element y in the set B. A total function f from set A to set B is a rule of correspondence that assigns A total function f from set A to set B is a rule of correspondence that assigns 1 2 2 4 3 6 4 8 10 5 Set A is the domain Set B is the range This is a total function --- it meets our conditions Whew! What did that say? Must use all the x s The x value can only be assigned to one y
Function: Let A and B be non empty sets. A function, denoted byf , from A to B is a relation from A to B such that: 1. Dom f = A, that is, for each a A, (a,b) f for some b B. In other words, f is defined at each a A. 2. If (x, y) f and (x, z) f then y = z. In this case, we say that f is well-defined or single valued. Note: No element of A is related to two elements of B. If (x, y) f , then we say that y is the image of x under f and write as y= f(x) If f is a function from A to B, we write f:A B The words mapping, transformation, correspondence, and operator are used as synonyms for function.
Lets look at another relation and decide if it is a total function. The second condition says each x can have only one y, but it CAN be the same y as another x gets assigned to. 1 2 2 4 3 6 4 8 10 5 Set A is the domain Set B is the range This is a total function ---it meets our conditions Must use all the x s The x value can only be assigned to one y
A good example that you can relate to is students in our maths class this semester are set A. The grade they earn out of the class is set B. Each student must be assigned a grade and can only be assigned ONE grade, but more than one student can get the same grade (we hope so---we want lots of A s). The example show on the previous screen had each student getting the same grade. That s okay. That s okay. A good example that you can relate to is students in our maths class this semester are set A. The grade they earn out of the class is set B. Each student must be assigned a grade and can only be assigned ONE grade, but more than one student can get the same grade (we hope so---we want lots of A s). The example shown on the previous screen had each student getting the same grade. 1 2 2 4 3 6 4 8 10 5 2 was assigned both 4 and 10 NO Is the relation shown above a function? Why not???
Check this relation out to determine if it is a TOTAL function. It is not---3 didn t get assigned to anything Comparing to our example, a student in maths must receive a grade 1 2 2 4 3 6 4 8 10 5 Set A is the domain Set B is the range This is not a total function---it doesn t assign each x with a y Must use all the x s The x value can only be assigned to one y
Check this relation out to determine if it is a total function. This is fine each student gets only one grade. More than one can get an A and I don t have to give any D s (so all y s don t need to be used). 1 2 2 4 3 6 4 8 10 5 Set A is the domain Set B is the range This is a total function Must use all the x s The x value can only be assigned to one y
Types of Functions: One to One Function (Injection) An injective function (or one-to-one) is a function whose range elements are mapped to by a unique element of the domain. ( or ) No element of B is the image of more than one element in A.
Onto Function(surjection) A surjective function (or onto) is a function whose range is the whole of the target set. Or A function f:A B is onto iff ran f= B.
One to One correspondence Function (bijection) A bijective function (or bijection) is a function which is total, surjective and injective
Inverse Function The inverse of a function is obtained by swapping the order of the elements in the pairs. The result will not be function unless the original function is injective.
Identity And Function Composition The identity function returns a value equal to its input and is denoted by Ix. x X Ix (x) = x Composition : f(x) = x + 1 g(x) = 5 * x g(f(3)) = g(3 + 1) = g(4) = 5 * 4 = 20 f(g(2)) = f(5 * 2) = f(10) = 10 + 1 = 11 Function composition (e.g. f(g(x))) is only possible if the output of the inner function can be the input to the outer function. ran g dom f Obviously, a composition defines a new function. 7.18
Function Composition Another way of writing composition is to use o. g o f where (g o f) x = g(f(x)) (g o f) 3 = g(f(3)) = g(4) = 20 Both g o f and f o g are functions but in general they will not be the same function. Generally g of f o g For example : x Z f(x) = x - 1 x N g(x) = 6 * x (g o f) 2 = g(f(2)) = g(1) = 6 (f o g) 2 = f(g(2)) = f(12) = 11 Clearly, these are not equal. 7.19
Function Override The override of f by g is denoted by f g. x Z f(x) = x - 1 x N g(x) = 6 * x (f g) 2 = g(2) = 12 (f g) -1 = f(-1) = -2 In the first case, 2 dom g so we apply g. In the second case -1 dom g so we apply f. Note that if the argument is not in the domain of either function then the result is undefined : if x dom f dom g then(f g) x = 7.20
