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)
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
