Summary COS1501 Assignment 3 100% With Memo Discussion

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