COS1501/203/1/2018
Tutorial letter 203/1/2018
Theoretical Computer Science 1
COS1501
Semester 1
School of Computing
Discussion of assignment 03
,Dear Student,
By this time you should have received the tutorial matter listed below. These can be downloaded
from myUnisa.
COSALLP/301/4/2018 General information regarding the School of Computing including
lecturers’ information;
COS1501/101/3/2018 General information about the module and the assignments;
COS1501/201/1/2018 Solutions to the first assignment, and examination information;
COS1501/202/1/2018 Solutions to the second assignment;
COS1501/203/1/2018 This tutorial letter;
MO001/4/2018 Learning units, example exam paper and other important information;
COS1501/102/3/2018 Solutions to self-assessment questions in assignments 02 and 03,
example assignments & solutions, example examination paper & solutions, and extra
questions & solutions.
Everything of the best with the exam!
Regards
COS1501 team
Discussion of assignment 03 semester 1.
Suppose U = {1, 2, 3, 4, 5, a, b, c} is a universal set with the subset A = {a, b, c, 1, 2, 3, 4}.
Answer questions 1 and 2 by using the given sets U and A.
Question 1
Which one of the following relations on A is NOT functional?
1. {(1, 3), (b, 3), (1, 4), (b, 2), (c, 2)}
2. {(a, c), (b, c), (c, b), (1, 3), (2, 3), (3, a)}
3. {(a, a), (c, c), (2, 2), (3, 3), (4, 4)}
4. {(a, c), (b, c), (1, 3), (3, 3)}
Answer: Alternative 1
Discussion
First we look at the definition of functionality:
Suppose R B × C is a binary relation from a set B to a set C. We may call R functional if the
elements of B that appear as first co-ordinates of ordered pairs in R do not appear in more than
one ordered pair of R.
We consider the relations provided in the different alternatives:
2
, COS1501/203
1. Let L = {(1, 3), (b, 3), (1, 4), (b, 2), (c, 2)} (say). L is not functional since the elements
1 and b appear more than once as first co-ordinates in ordered pairs of L.
2. Let M = {(a, c), (b, c), (c, b), (1, 3), (2, 3), (3, a)} (say).
M is a relation on A = {a, b, c, 1, 2, 3, 4}: {a, b, c, 1, 2, 3} = dom(M) A and
ran(M) = {a, b, c, 3} A. Each first co-ordinate appears only once as first co-ordinate thus M
is functional.
3. Let N = {(a, a), (c, c), (2, 2), (3, 3), (4, 4)} (say).
N is a relation on A = {a, b, c, 1, 2, 3, 4}: {a, c, 2, 3, 4} = dom(N) A and
ran(N) = {a, c, 2, 3, 4} A. Each first co-ordinate appears only once as first co-ordinate thus
N is functional.
4. Let S = {(a, c), (b, c), (1, 3), (3, 3)} (say).
S is a relation on A = {a, b, c, 1, 2, 3, 4}: {a, b, 1, 3} = dom(S) A and
ran(S) = {c, 3} A. Each first co-ordinate appears only once as first co-ordinate thus S is
functional.
From the arguments provided we can deduce that alternative 1 should be selected.
Refer to study guide, p 98.
Question 2
Which one of the following alternatives represents a surjective function from U to A?
1. {(1, 4), (2, b), (3, 3), (4, 3), (5, a), (a, c), (b, 1), (c, b)}
2. {(a, 1), (b, 2), (c, a), (1, 4), (2, b), (3, 3), (4, c)}
3. {(1, a), (2, c), (3, b), (4, 1), (a, c), (b, 2), (c, 3)}
4. {(1, a), (2, b), (3, 4), (4, 3), (5, c), (a, a), (b, 1), (c, 2)}
Answer: Alternative 4
Discussion
We look at the definitions of a function and of surjectivity:
Suppose R B × C is a binary relation from a set B to a set C. We may call R a function from
B to C if every element of B appears exactly once as the first co-ordinate of an ordered pair in R
(i.e. f is functional), and the domain of R is exactly the set B, ie dom(R) = B.
A function R from B to C is surjective iff ran(R) = C.
We have U = {1, 2, 3, 4, 5, a, b, c} and A = {a, b, c, 1, 2, 3, 4}.
We consider the relations provided in the different alternatives:
3
