Informatyka MIMUW

\(\def\RR{\mathbb{R}}
\def\NN{\mathbb{N}}
\def\pot#1{{\sf P}(#1)}
\def\la{\langle}
\def\ra{\rangle}
\def\incl{\subseteq}
\def\A{{\cal A}}
\def\B{{\cal B}}
\def\R{{\cal R}}
\def\tz{\;\;|\;\;}
\)

Zadanie 1 (iloczyn kartezjański)

Znajdź iloczyn kartezjański \(A \times B\), gdzie

1. \(A = \{a\}\), \(B = \{b\}\),
2. \(A = \emptyset\), \(B = \emptyset\),
3. \(A = \emptyset\), \(B = \{b\}\),
4. \(A = \{a\}\), \(B = \{b,c\}\),

Zadanie 2 (zbiór wszystkich relacji)

Dla przykładów \(A\) i \(B\) z poprzedniego zadania podaj zbiór wszystkich relacji w \(A \times B\).

Zadanie 3

Niech \(R, S \subseteq A \times A\). Czy z tego, że \(R \cdot S = S \cdot R\) wynika, że \(R=S\) lub \(R =1_A\) lub \(S =1_A\) ?

Zadanie 4

Znajdź przykład 5-elementowej relacji symetrycznej w zbiorze \(\NN\). Czy istnieje 5-elementowa relacja zwrotna w \(\NN\)? A 5-elementowa relacja przechodnia?

Zadanie 5

Niech \(R\) będzie relacją dwuargumentową w zbiorze \(A\). Czy możliwe jest, że

1. \(R^{-1}\subseteq R\) i \(R \not = R^{-1}\)?
2. \(R^{-1} = A\times A - R\)?

Zadanie 6

Niech \(\R\) będzie niepustą rodziną relacji w \(B\times C\) i niech \(s \subseteq A \times B\). Udowodnij, że:

1. \(s \cdot (\bigcup \R) = \bigcup \{s \cdot r \tz r \in \R\}\),
2. \(s \cdot (\bigcap \R) \subseteq \bigcap \{s \cdot r \tz r \in \R\}\). Czy \(\subseteq\) można zastąpić przez \(=\)?
3. \( (\bigcup \R)^{-1} = \bigcup \{ r^{-1} \tz r \in \R\}\),
4. \( (\bigcap \R)^{-1} = \bigcap \{ r^{-1} \tz r \in \R\}\),

Zadanie 7

Czy suma, iloczyn i złożenie dwóch relacji symetrycznych jest relacją symetryczną ? To samo pytanie może być też postawione dla relacji zwrotnych, przechodnich, antysymetrycznych i spójnych.

Zadanie 8

Udowodnij, że suma łańcucha relacji przechodnich jest relacją przechodnią.

Zadanie 9

Niech \(r\) będzie relacją dwuargumentową w zbiorze \(\NN^\NN\) określoną następująco:

\(\la f, g \ra \in r \quad \Leftrightarrow \quad \forall n:\NN\, (f(n) \,|\, g(n) \lor g(n) \,|\, f(n))\)
Czy relacja \(r\) jest zwrotna, symetryczna, przechodnia, antysymetryczna? Czym jest \(r \cdot r\) ?

Zadanie 10 (najczęściej robione na wykładzie)

Niech \(r\) będzie relacją dwuargumentową w zbiorze \(A\) i niech \(r^+\) (najmniejsza relacja przechodnia zawierająca \(r\)) będzie zdefiniowana wzorem \(r^+=\bigcap \{s \tz r \subseteq s \land s\) jest relacją przechodnią w \(A\}\). Udowodnij, że \(r^+ = \bigcup \{r^n \tz n \in \NN-\{0\}\}\), gdzie \(r^1 = r\) i \(r^{n+1} = r \cdot r^n\).

Zadanie 11

Dla relacji \(r \subseteq A \times A\), niech \(f_r : N \to N\) będzie funkcją daną wzorem \(f_r(n) = r^n\), gdzie \(r^n = r \cdot \ldots \cdot r\) oznacza \(n\)-krotne złożenie relacji \(r\) (przy czym \(r^0 = id_A\)). Dla jakich \(r\) ciąg \(\{f_r(i)\}_{i\in\NN}\) jest wstępujący (tj. dla każdego \(i \in \NN\) zachodzi \(f_r(i) \subseteq f_r(i+1)\)) ?