Description

CSE 15: Discrete Mathematics Laboratory 5
• This lab assignment will be graded and its grade will count towards the course grade.
• Start early.
Introduction
In the past week we have formally introduced the concept of function in class, and we have introduced functions in python. In this lab assignment you will practice with both. First, recall that in class we have defined that a function f : A → B is relation f over A × B such that for each a ∈ A, there is exactly one b ∈ B such that (a,b) ∈ f, and in such case we write b = f(a). To keep things simple, in this assignment we will only consider functions where both A and B are finite sets. Recall that A is the domain of f and B is the codomain of f.
When both A and B are finite, one way to represent f : A → B is to provide an enumeration of all couples
(a,b) ∈ A × B, such that b = f(a) (this is not necessarily efficient, but it does not matter for the time being.) Owing to the fact that f is a special type of relation, i.e., a subset of A×B, a function can therefore be represented as a set (recall the definition of graph of a function.) For example if A = {dog,cat,mouse} and B = {white,black} the following subset ot A × B represents (the graph of) a function f : A → B.
{(dog,white),(cat,black),(mouse,black)}
In python this structure can be represented by a set of tuples, where each tuple has two elements. The following two lines would build the set given above and the print it.
>>> L = [(’dog’,’white’), (’cat’,’black’),(’mouse’,’black’)]
>>> f = set(L)
>>> print(f)
{(’cat’, ’black’), (’dog’, ’white’), (’mouse’, ’black’)}
In the example, first we store the tuples into a list, and then we create a set with those tuples. There are obviously countless other ways to initialize f and get the same result. The following example builds a similar structure, but has a problem:
1
>>> L = L = [(’dog’,’white’), (’cat’,’black’),(’dog’,’black’)]
>>> f = set(L)
>>> print(f)
{(’dog’, ’black’), (’cat’, ’black’), (’dog’, ’white’)}
The problem is that in this case f is not the graph of a function because there are two entries where dog is the first element, and this is contrary to the definition of a function (every element in the domain must be associated with exactly one element in the codomain.)
With the above assumptions we then represents functions by giving their graph. Write two functions in python that satisfy the following specifications:
1. Write a function
is_a_graph(A,B,f)
that receives three parameters. The first is the domain, the second is the codomain, and the third is a subset of A × B. The function returns True if f represents the graph of a function f : A → B and False otherwise.
2. Write a function
is_surjective(A,B,f)
that receives three parameters. The first is the domain, the second is the codomain, and the third is the graph of a function represented as above. The function returns True if f is the graph of a surjective function and False otherwise. You can assume that in this case f is the graph of a function, i.e., you can ignore the case when f is not the graph of a function.
Suggestions: to solve this exercise it is necessary to analyze all elements in f. To this end, you can re-use the code provided in the file functionsexamples.py that is linked from the lab assignment. Therein we give the code for a function is injective that can be modified to answer the questions given above.
2