Chapter 19 - Functions. In this chapter, the following content will be discussed: Relations and functions, definition of function, examples of functions, one-to-one function, onto function, bijective function (one-to-one correspondence), inverse functions. | (CSC 102) Lecture 19 Discrete Structures Previous Lecture Summery Properties of relations Reflexive, Symmetric and Transitive Relations Equivalence Relations Properties of Congruence Modulo n Transitive closure of a relations Combining Relations Partial Order Relations Hasse Diagrams Functions Today’s Lecture Relations and Functions Definition of Function Examples of Functions One-to-One Function Onto Function Bijective Function (One-to-One correspondence) Inverse Functions Relations If we want to describe a relationship between elements of two sets A and B, we can use ordered pairs with their first element taken from A and their second element taken from B. Since this is a relation between two sets, it is called a binary relation. Definition: Let A and B be sets. A binary relation R from A to B is a subset of A B. In other words, for a binary relation R we have R A B. We use the notation aRb to denote that (a, b) R and aRb to denote that (a, b) R. Relations If we have two sets A = {1,2,3,4,5} and B = {5,6,7,8,9} The cartesian product of A and B is A × B = { (1,5), (1,6), (1,7), (1,8), (1,9), (2,5), (2,6), (2,7), (2,8), (2,9), (3,5), (3,6), (3,7), (3,8), (3,9), (4,5), (4,6), (4,7), (4,8), (4,9), (5,5), (5,6), (5,7), (5,8), (5,9) }. The rule is to add 4: R = { (1,5), (2,6), (3,7), (4,8), (5,9) }. The domain is the set of all values which are first members of the ordered pairs in the relation, ., Dom (R) = {1, 2, 3, 4, 5} The range is the set of all values which are second members of the ordered pairs in the relation, ., Range (R) = {5, 6, 7, 8, 9} Relations 5 6 7 8 9 1 2 3 4 5 The Rule is ‘ADD 4’ One to One Relations Dom (R) = {1, 2, 3, 4, 5} Range (R) = {5, 6, 7, 8, 9} Relations Ahmed Peter Ali Jaweria Hamad Paris London Dubai New York Cyprus Has Visited Many to Many relation Dom (R) = {Ahmad, Peter, Jaweria, Hamad} Range (R) = {Paris, London, Dubai, New York, Cyprus} Note That: Ali is not in the Domain Bilal Peter Salman Ali George Aziz 62 64 66 . | (CSC 102) Lecture 19 Discrete Structures Previous Lecture Summery Properties of relations Reflexive, Symmetric and Transitive Relations Equivalence Relations Properties of Congruence Modulo n Transitive closure of a relations Combining Relations Partial Order Relations Hasse Diagrams Functions Today’s Lecture Relations and Functions Definition of Function Examples of Functions One-to-One Function Onto Function Bijective Function (One-to-One correspondence) Inverse Functions Relations If we want to describe a relationship between elements of two sets A and B, we can use ordered pairs with their first element taken from A and their second element taken from B. Since this is a relation between two sets, it is called a binary relation. Definition: Let A and B be sets. A binary relation R from A to B is a subset of A B. In other words, for a binary relation R we have R A B. We use the notation aRb to denote that (a, b) R and aRb to denote that (a, b) R. Relations If we have two sets A =
