Informatyka MIMUW

1.
\( \displaystyle \begin{align*} (x,z)\in T \circ ( S \circ R ) \Leftrightarrow \\ \exists_{u} [(x,u)\in ( S \circ R ) \wedge (u,z)\in T]\Leftrightarrow \\ \exists_{u} [\exists_{v}( (x,v)\in R\wedge (v,u)\in S) \wedge (u,z)\in T]\Leftrightarrow \\ \exists_{u} \exists_{v}[ (x,v)\in R\wedge (v,u)\in S \wedge (u,z)\in T]\Leftrightarrow \\ \exists_{v} \exists_{u}[ (x,v)\in R\wedge ((v,u)\in S \wedge (u,z)\in T)]\Leftrightarrow \\ \exists_{v} [ (x,v)\in R\wedge \exists_{u}((v,u)\in S \wedge (u,z)\in T)]\Leftrightarrow \\ \exists_{v} [ (x,v)\in R\wedge (v,z)\in T \circ S]\Leftrightarrow \\ (x,z) \in (T \circ S) \circ R \\ \end{align*} \)
2.
\( \displaystyle \begin{align*} (x,z)\in (S \circ R )^{-1} \Leftrightarrow \\ (z,x) \in S\circ R \Leftrightarrow \\ \exists_{y} [(z,y) \in R \wedge (y,x)\in S] \Leftrightarrow \\ \exists_{y} [(y,z) \in R^{-1} \wedge (x,y)\in S^{-1}] \Leftrightarrow \\ (x,z)\in R^{-1} \circ S^{-1} \\ \end{align*} \)
3.
\( \displaystyle \begin{align*} (x,z)\in R \Rightarrow \\ \exists_{y} (x,u) \in R \wedge \exists_{v} (v,y)\in R \Leftrightarrow \\ x\in R_L \wedge y\in R_P \Leftrightarrow \\ (x,y) \in R_L \times R_P \end{align*} \)
4.
\( \displaystyle \begin{align*} x \in (S \circ R)_L \Leftrightarrow \\ \exists_{z} (x,z)\in S\circ R \Leftrightarrow \\ \exists_{z} \exists_{y} [(x,y)\in R \wedge (y,z)\in S ] \Rightarrow \\ \exists_{z} \exists_{y} (x,y)\in R \Leftrightarrow \\ \exists_{y} (x,y)\in R \Leftrightarrow \\ x \in R_L \end{align*} \)
5. Dowód \( \displaystyle (S \circ R)_P \subset S_P \) jest analogiczny do poprzedniego.
6.
\( \displaystyle \begin{align*} x\in (R^{-1} )_L \Leftrightarrow \\ \exists_{y} (x,y)\in R^{-1} \Leftrightarrow \\ \exists_{y} (y,x)\in R \Leftrightarrow \\ x\in R_P \end{align*} \)

W poniższych punktach (1-4) pokażemy, że dowolna para należy do zbioru po lewej stronie odpowiedniej równości wtedy i tylko wtedy, gdy należy do prawej. W punkcie 5, pokazujemy jedynie implikację w prawą stronę, gdyż mamy udowodnić inkluzję.

1.
\( \displaystyle \begin{align*} (x,y)\in (R\cup S)^{-1} \Leftrightarrow \\ (y,x)\in (R\cup S) \Leftrightarrow \\ (y,x)\in R \vee (y,x) \in S \Leftrightarrow \\ (x,y)\in R^{-1} \vee (x,y) \in S^{-1} \Leftrightarrow \\ (x,y)\in R^{-1} \cup S^{-1} \end{align*} \)

2. Dowód drugiej równości jest analogiczny do dowodu pierwszej, wystarczy użyć \( \displaystyle \cap \) w miejsce \( \displaystyle \cup \) oraz \( \displaystyle \wedge \) w miejsce \( \displaystyle \vee \).

3.
\( \displaystyle \begin{align*} (x,y)\in (R^{-1})^{-1} \Leftrightarrow \\ (y,x)\in R^{-1} \Leftrightarrow \\ (x,y)\in R \end{align*} \)

4.
\( \displaystyle \begin{align*} (x,z)\in (R \cup S ) \circ T \Leftrightarrow \\ \exists_y [(x,y) \in T \wedge (y,z)\in (R \cup S )] \Leftrightarrow \\ \exists_y [(x,y) \in T \wedge ((y,z)\in R \vee (y,z)\in S ))] \Leftrightarrow \\ \exists_y [((x,y) \in T \wedge (y,z)\in R) \vee ((x,y) \in T \wedge (y,z)\in S ))] \Leftrightarrow \\ [\exists_y ((x,y) \in T \wedge (y,z)\in R)] \vee [\exists_y ((x,y) \in T \wedge (y,z)\in S )] \Leftrightarrow \\ (x,z)\in (R \circ T) \vee (x,z)\in (S \circ T) \Leftrightarrow \\ (x,z)\in (R \circ T) \cup (S \circ T) \end{align*} \)

5.
\( \displaystyle \begin{align*} (x,z)\in (R \cap S ) \circ T \Leftrightarrow \\ \exists_y [(x,y) \in T \wedge (y,z)\in (R \cap S )] \Leftrightarrow \\ \exists_y [(x,y) \in T \wedge ((y,z)\in R \wedge (y,z)\in S ))] \Leftrightarrow \\ \exists_y [((x,y) \in T \wedge (y,z)\in R) \wedge ((x,y) \in T \wedge (y,z)\in S ))] \Rightarrow \\ [\exists_y ((x,y) \in T \wedge (y,z)\in R)] \wedge [\exists_y ((x,y) \in T \wedge (y,z)\in S )] \Leftrightarrow \\ (x,z)\in (R \circ T) \wedge (x,z)\in (S \circ T) \Leftrightarrow \\ (x,z)\in (R \circ T) \cap (S \circ T) \end{align*} \)

Pokażemy najpierw, że dla każdej relacji \( \displaystyle R \) mamy

\( \displaystyle \bigcup \bigcup R = R_L \cup R_P. \quad \mbox{(3.12)} \)

Zaczniemy od inkluzji \( \displaystyle \subset \). Weźmy dowolny element \( \displaystyle x \in \bigcup \bigcup R \), wtedy musi istnieć element \( \displaystyle y\in \bigcup R \) taki, że \( \displaystyle x\in y \). Skoro \( \displaystyle y\in \bigcup R \), to musi istnieć para \( \displaystyle (a,b) \in R \) taka, że \( \displaystyle y\in (a,b) \). Wobec tego z definicji pary uporządkowanej \( \displaystyle y=\{a\} \) lub \( \displaystyle y=\{a,b\} \). Ponieważ \( \displaystyle x\in y \), to \( \displaystyle x=a \) i wtedy \( \displaystyle x\in R_L \) lub \( \displaystyle x=b \) i wtedy \( \displaystyle x\in R_P \). Wobec tego \( \displaystyle x\in R_L \cup R_P \).

Pokażemy teraz prawdziwość inkluzji \( \displaystyle \supset \) w równaniu 3.12. Weźmy dowolny element \( \displaystyle a\in R_L \) wtedy istnieje element \( \displaystyle b\in R_P \) taki, że \( \displaystyle (a,b)\in R \), a więc \( \displaystyle \{(a,b)\} \subset R \). Stąd otrzymujemy

\( \displaystyle \bigcup \bigcup \{(a,b)\} \subset \bigcup \bigcup R. \)

Ponieważ \( \displaystyle \bigcup \bigcup \{(a,b)\}= \bigcup \{\{a\},\{a,b\}\} = \{a,b\} \), to otrzymujemy \( \displaystyle \{a,b\} \subset R \), a więc \( \displaystyle a\in R \). Analogiczne rozumowanie można przeprowadzić dla elementu \( \displaystyle b\in R_P \). Zakończyliśmy więc dowód równości 3.12.

W temacie ćwiczenia implikacja w lewą stronę jest oczywista. Jeśli \( \displaystyle A \) jest zbiorem, to \( \displaystyle \bigcup \bigcup A \) jest zbiorem i \( \displaystyle A \) jest podzbiorem iloczynu kartezjańskiego dwóch zbiorów, więc musi być relacją. Dla implikacji w prawą stronę załóżmy, że \( \displaystyle A \) jest relacją, wtedy

\( \displaystyle A \subset A_L \times A_P \subset (A_L \cup A_P) \times (A_L \cup A_P) = (\bigcup \bigcup A) \times ( \bigcup \bigcup A) \)