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