MUN Computer Science 1002 - Lab 6

Functions and relations

Materials:

Please bring scratch paper and pens/pencils.
During the quiz, you can use only the paper notes you made solving the lab, as well as the text of the lab itself.

Review:

Vocabulary

 

Individual work

Solve each of the following exercises.

  1. For each of the following functions, identify domain, codomain and range. State whether the function is total, one-to-one, onto, bijection.
    1. $f\colon \mathbb{R} \to \mathbb{R}$, $f(x)=\lceil 2x \rceil$, where $\lceil z \rceil$ is the ceiling of $z$, that is, the smallest integer greater than or equal to $z$.
    2. Let universe $U=\{a,b,c,\dots,z\}$, and let $A\subseteq U$ be a set. Then $f_A\colon U \to \{0,1\}$ is defined as $f_A(x) =1$ if $x \in A$, and $f_A(x)=0$ if $x \notin A$ (this $f_A$ is called the characteristic function of $A$). For this question, let $A$ be all vowels in $U$. How would your answer change if $A = \emptyset$?
    3. $f \colon \{0,1\}^* \to \mathbb{N}$, where $f(x)=k$ if the length of string $x$ is $k$.
  2. Give two examples of functions, $f\colon \{1,2,3\} \to \{a,b,c\}$ and $g\colon \mathbb{Z} \to \mathbb{Z}$ such that $f$ and $g$ are both
    1. bijections
    2. one-to-one, but not onto (not necessarily total)
    3. neither one-to-one, nor onto
  3. For each of the following pairs, describe $f^{-1}$, $g^{-1}$, $f \circ g$ and $g \circ f$.
    1. $f \colon \mathbb{R} \to \mathbb{R}$, $f(x) = 2x$, and $g \colon \mathbb{R} \to \mathbb{R}$, $g(x)=x+10$.
    2. $f \colon \{0,1\}^* \to \{0,1\}^*$, $f(x)$ is reverse of $x$ (for example, $f(00111)=11100$; if $x=x_1 \dots x_k$ where $x_1,\dots, x_k \in \{0,1\}$, then $f(x)=x_k x_{k-1} \dots x_2 x_1$), and $g \colon \{0,1\}^*\to \{0,1\}^*$ is a circular shift to the right: that is, if $x=x_1\dots x_k$, then $g(x) = x_k x_1 x_2 \dots x_{k-1}$ (for example, $g(00111)=10011$). Hint: you can describe your answers by saying what happens on $x=x_1\dots x_k$.

Group exercises

For this part of the lab, you will be working in groups of three. In the first part of the exercise, you will create examples of relations and draw some of them on paper. Then, each of three people in the group picks one of the topics below, and solves the corresponding questions. Then, each of you will explain to two of your peers how you have solved these questions. Your explanation should be good enough that they can then solve similar questions on their own.

Exercise 1

For each of the following binary relations on $A =\{0,1,2,3\}$, draw a graph of the relation and state if it is reflexive, anti-reflexive, neither, symmetric, anti-symmetric, neither, transitive, order (total or partial) or equivalence.
  1. $R = \{(x,y) \in A \times A \mid x \leq y \}$
  2. $R = \{ (x,y) \in A \times A \mid |x-y|=1 \}$
  3. $R = \{ (x,y) \in A \times A \mid x \equiv y \mod 2 \}$

Exercise 2

Now, pick your topics. Each of you will draw graphs of two out of three relations as described below; you would not draw a relation corresponding to your topic number (you'll get your friends' answers to work on). All relations below will be on the set A={square, circle, triangle, star, diamond}.
  1. $R_1$: an example of an equivalence which is not equality (that is, there are pairs $(x,y) \in R_1$ where $x \neq y$).
  2. $R_2$: an example of a non-transitive, not reflexive and not anti-reflexive relation.
  3. $R_3$: an example of a partial order that is not a total order (draw the actual relation; you will then give this to your friend to draw Hasse diagram for it).

Exercise 3

Now, each of you will solve your selected topic. Then, as before, make sure to explain to your friends what you did, so that all of you are on top of each topic.

Topic 1: Equivalence classes

Any equivalence relation $R \subseteq A \times A$ partitions $A$ into equivalence classes such that elements are related by $R$ within the class, and not related to anything outside the class. Now, for each of the following equivalence relations, describe the partition of the original set $A$ into equivalence classes according to that relation.
  1. $A_1= \{0,1,2,3,4,5,6,7,8,9\}$, $R = \{ (x,y) \mid where |x-y| $ is even $\}$. Here, $|x-y|=x-y$ when $x \geq y$, and $|x-y|=y-x$ when $x < y$.
  2. Each of the two relations $R_1$ drawn by your friends.
  3. $A_2 = A_1^*$ (that is, all strings made from $\{0,1,\dots, 9\}$). $R=\{(x,y) \mid$ x and y start with the same letter $\}$. Hint: $A_2$ also contains an empty string.

Topic 2: Transitive closure

A transitive closure of a binary relation $R$ is the smallest transitive relation $R^+$ such that $R \subseteq R^+$. For example, $x < y$ (but not $x \leq y$) is a transitive closure of the relation $\{(x,y)| x+1=y\}$. A transitive closure of any $R$ can be computed by repeatedly adding pairs $(x,z)$ whenever $(x,y)$ and $(y,z)$ were either in $R$ or added earlier. A transitive closure of a transitive relation $R$ is $R$ itself. When relations are viewed as graphs, then there is an edge $(x,y)$ in $R^+$ if there is a way to get from $x$ to $y$ in the graph of $R$ by following a sequence of edges.

Topic 3: Hasse diagrams

Let $R$ be partial order on $A$. A graph of $R$ would contain a loop on every vertex (because $R$ is reflexive), and potentially a lot of edges because of transitivity. For example, let $A=\mathcal{P}(\{1,2,3\})$, and consider a partial order relation $R=\{(B,C) \in A \times A \mid B \subseteq C\}$. Then the graph of $R$ would have edges $(\emptyset,\{1\})$, $(\emptyset, \{1,2\})$, $(\emptyset,\{1,2,3\})$, $(\{1\}, \{1,2\})$, $(\{1\},\{1,2,3\})$ and so on, making a messy picture. A Hasse diagram is a way to draw a cleaner graph corresponding to the same partial order, by eliminating all edges implied by other edges using reflexivity and transitivity. That is, in a Hasse diagram, we do not draw loops, and only draw an edge $(a,b)$ if there are no edges $(a,c)$ and $(c,b)$ already in the diagram. Also, we draw smaller elements below larger elements, and skip arrows. For example, a Hasse diagram of the subset relation on $A=\mathcal{P}(\{1,2,3\})$ is as follows.

{1,2,3} {1,2} {1,3} {2,3} {1} {2} {3}

Review after the group activity

Let $A = \{abc, a, bc, ac, ab, bac \} $ (that is, $A \subset \{a,b,c\}^*)$.

  1. Let $R_1= \{ (ac,bc), (bc,ac), (bc, ab), (ab,bc), (ab, ac), (ac, ab), (abc,bac), (bac,abc), (abc,abc), (a,a), (bc,bc), (ac,ac), (ab,ab), (bac,bac) \} $. Draw a graph of $R_1$. In how many classes equivalence classes does $R_1$ partition $A$? List elements of each equivalence class. How would you describe this equivalence relation on $A$?
  2. Let $R_2 = \{$(a,ab), (a,ac),(ab,abc), (bc,abc), (abc,a), (ac, bac)$\}$. Draw a graph of $R_2$ and a graph of its transitive closure $R_2^+$. For each of $R_2$ and $R_2^+$, say if it is reflexive/anti-reflexive/neither, symmetric/anti-symmetric/neither, transitive/not transitive.
  3. Draw a Hasse diagram of $R_3=\{(x,y) \mid $ x=y or x is a substring of y $\}$. That is, R_3= $\{(x,x) | x \in A \} \cup \{$ (a,ab), (a,ac), (a, abc), (ab,abc), (bc,abc), (a, bac), (ac, bac) $\}$