L06: Functions

Question 1

What is a function?

Answer 1

A function f is a binary relation between 2 sets: a domain and codomain

Has the property that each element of the domain is related to at most one element of the codomain -> its image

We write f(x) = y to mean that the image of x under the function f is y

The range of the function is the subset of elements of the codomain, each of which is the image of some element of the function domain

Question 2

Where does the function pattern occur?

Answer 2

Graph colouring
- fund a function from the vertices to a set of colours such that touching vertices are not the same colour

Warehouse location
- Find a function from stores to warehouse to indicate which store is supplied by which warehouse

Question 3

What is a total function?

Answer 3

In a total function, every element in the domain has an image in the codomain

Question 4

How can we use explicit representation for total functions?

Answer 4

We can have a table indexed by each element of the domain, and the domain for each variable is the codomain.

Question 5

How can we use occurrence representation for total functions?

Answer 5

We can have a 2D table with one dimension indexed by the domain, and the other indexed by the codomain. The domain for the variables are 0/1 to represent the relationship between the domain and codomain.

Constraint:
The sum of each column = 1(assuming the domain index is at the top)
This will ensure that each element of the domain has an image in the codomain

Question 6

What is a partial function?

Answer 6

In a partial function, some elements of the domain have no image in the codomain.

Question 7

How can we use explicit representation for partial functions?

Answer 7

We can have a table indexed by each element of the domain, and the domain for each variable is the codomain and a dummy variable, as not every element in the domain needs to have an image in the codomain

Question 8

How can we use occurrence representation for partial functions?

Answer 8

We can have a 2D table with one dimension indexed by the domain, and the other indexed by the codomain. The domain for the variables are 0/1 to represent the relationship between the domain and codomain.

Constraint:
The sum of each column <= 1(assuming the domain index is at the top)
This will ensure that each element of the domain has at most 1 image in the codomain

Question 9

What is an injection?

Answer 9

In an injective function, the images of distinct elements are distinct

I.e. no 2 elements in the domain map to the same element in the codomain

Question 10

How can we use explicit representation for injective functions?

Answer 10

We can have a table indexed by each element of the domain, and the domain for each variable is the codomain.

Constraints:
- Total function: allDifferent(injection)
- Partial function: allDifferent(injection) but ignoring repetition of the dummy variable

Question 11

How can we use occurrence representation for total injective functions?

Answer 11

We can have a 2D table with one dimension indexed by the domain, and the other indexed by the codomain. The domain for the variables are 0/1 to represent the relationship between the domain and codomain.

Constraints:
- The sum of each column = 1 (assuming the domain index is at the top)
This will ensure that each element of the domain has an image in the codomain
- The sum of each row <= 1 (assuming the codomain index is on the left)
This will ensure that each element of the codomain is only mapped from one element in the domain

Question 12

How can we use occurrence representation for partial injective functions?

Answer 12

We can have a 2D table with one dimension indexed by the domain, and the other indexed by the codomain. The domain for the variables are 0/1 to represent the relationship between the domain and codomain.

Constraints:
- The sum of each column <= 1 (assuming the domain index is at the top)
This will ensure that each element of the domain has at most 1 image in the codomain
- The sum of each row <= 1 (assuming the codomain index is on the left)
This will ensure that each element of the codomain is only mapped from one element in the domain

Question 13

What is a surjective function?

Answer 13

A function is surjective if every element in the codomain is the image of some element of the domain

I.e. every element in the codomain is image of an element in the domain

Question 14

How can we use explicit representation for surjective functions?

Answer 14

We can have a table indexed by each element of the domain, and the domain for each variable is the codomain.

Constraints:
- There must exist indices where each of the elements in the codomain appear

Question 15

How can we use occurrence representation for surjective functions?

Answer 15

We can have a 2D table with one dimension indexed by the domain, and the other indexed by the codomain. The domain for the variables are 0/1 to represent the relationship between the domain and codomain.

Constraints:
- The sum of each row >= 1 (assuming the codomain index is on the left)
This will ensure that each element of the codomain is mapped to at least once

Question 16

What is a bijection?

Answer 16

A bijection is both an injection and surjection.

• No 2 elements in the domain map to the same element in the codomain
• Every element in the codomain is mapped to from an element in the domain

It is implied that bijective functions are total

Question 17

How can we model a bijection using occurrence representation?

Answer 17

We can have a 2D table with one dimension indexed by the domain, and the other indexed by the codomain. The domain for the variables are 0/1 to represent the relationship between the domain and codomain.

Constraints:
- The sum of each column = 1 (assuming the domain index is at the top)
This will ensure that each element of the domain has 1 image in the codomain
- The sum of each row = 1 (assuming the codomain index is on the left)
This will ensure that each element of the codomain is only mapped from one element in the domain

The combination of these constraints that there is a unique 1-1 mapping for between elements in the domain and codomain

We are assuming that the number of elements in the domain is the same as the elements in the codomain.