1. (Functions)
Let Consider the functions given by
Compute the following function values:
2. (Properties of functions)
Which of the three functions , and in Exercise 1 is onto? Which are 1-1?
COMP9020 20T1 - Week 3 Problem Set
https://cgi.cse.unsw.edu.au/~cs9020/20T1/probs/prob3/index.php
COMP9020 20T1
Week 3 Problem Set Foundations of ComputerScience Functions and Relations
3. (Matrix functions)
Prove each of the following statements.
a. (AT)T = A for any matrix A.
b. If two matrices A and B are of the same size, then (A + B)T = AT + BT.
c. A(B + C) = AB + AC for any matrix A of size m × n and matrices B, C of size n × p.
4. (Boolean functions)
a. Give all elements of BOOL(2), that is, all functions over two Boolean variables.
b. Show that there are elements in BOOL(n) for
5. (Properties of binary relations)
1 of 2 4/03/2020, 4:58 pm COMP9020 20T1 - Week 3 Problem Set https://cgi.cse.unsw.edu.au/~cs9020/20T1/probs/prob3/index.php
Reflexivity
Antireflexivity
Symmetry
Antisymmetry
Transitivity
b. For each of the following statements, give a valid proof if it is true for all relations and over arbitrary sets . If the statement is not always true,
provide a counterexample.
If and are symmetric, then is symmetric.
If and are antisymmetric, then is antisymmetric.
6. Challenge Exercise
Consider a set and the binary relation defined by .
Prove that is transitive if and only if
