Informatyka MIMUW

$\def\RR{\mathbb{R}} \def\pot#1{{\sf P}(#1)} \def\<{\langle} \def\>{\rangle} \def\incl{\subseteq} \def\A{{\cal A}} \def\B{{\cal B}} \def\tz{\;\;|\;\;}$

Zadanie 1

Zaznacz na rysunku zbiory:

1. $\{\< x, y\> \in \RR^2 \tz (x^2+y^2 > 1) \Rightarrow (y+x > 0)\}$,
2. $\{x \in \RR \tz (x^2<0) \Rightarrow (x^2 >0)\}$,
3. $\{x \in \RR \tz \forall x \; (x^2 > 0)\}$,
4. $\{x \in \RR \tz \exists z \forall y \;(y > (x-z)^2)\}$,
5. $\{\< x, y\> \in \RR^2 \tz (x^2+y^2 > 1) \Rightarrow \exists z (x^2 + (y-z)^2 < \frac{1}{4})\}$.

Zadanie 2

Udowodnij, że dla dowolnych zbiorów $A$, $B$, $C$ zachodzi równość:

1. $A = (A \cap B) \cup (A - B)$,
2. $A \cap (B \cup C)= (A \cap B) \cup (A \cap C)$,
3. $A - (B \cup C)= (A - B) \cap (A - C)$,
4. $(A \cup B) - C = (A - C) \cup (B - C)$.

Zadanie 3

Sprawdź czy dla dowolnych zbiorów $A$, $B$, $C$ zachodzi następująca implikacja:

1. jeśli $A \cup B = A \cup C$ to $B = C$,
2. jeśli $A - B = A - C$ to $B = C$,
3. jeśli $A - B = B - A$ to $A = B$.

Zadanie 4

Sprawdź czy dla dowolnych zbiorów $A$, $B$, $C$, $D$ zachodzi następująca implikacja:

1. jeśli $A \incl B$ to $A \cap B = A$,
2. jeśli $A \incl B$ i $C \incl D$ to $A \cap C \incl B \cap D$,
3. jeśli $A \incl B$ to $C- B \incl C - A$,
4. jeśli $A \incl B$ to $-A \supseteq -B$.

Zadanie 5

Sprawdź czy dla dowolnych zbiorów $A$ i $B$ zachodzi:

1. $\pot{A \cup B} = \pot{A} \cup \pot{B}$,
2. $\pot{A \cap B} = \pot{A} \cap \pot{B}$.

Zadanie 6

Udowodnij, że dla dowolnych zbiorów $A$ i $B$, zawieranie $A \incl B$ zachodzi wtedy i tylko wtedy gdy $\pot{A} \incl \pot{B}$.

Zadanie 7 (przykład z wykładu)

Udowodnij, że dla dowolnego zbioru $A$ zachodzi $\bigcup\pot{A} = A$.

Zadanie 8

Niech $\A \incl \pot{\RR}$ będzie rodziną zbiorów spełniających warunek $\forall B \in \A \;\forall C \incl \RR (C \incl B \Rightarrow C \in A)$. Udowodnij, że $\bigcup \A = \{z \in \RR \tz \{z\} \in \A\}$.

Zadanie 9

Sprawdź czy dla dowolnych rodzin zbiorów $\A$ i $\B$ zachodzi implikacja:

1. jeśli $\A \incl \B$ to $\bigcup \A \incl \bigcup \B$,
2. jeśli $\A \incl \B$ to $\bigcap \A \supseteq \bigcap \B$.

Zadanie 10

Udowodnij, że dla dowolnych rodzin zbiorów $\A$ i $\B$ zachodzi $\bigcup (\A \cup \B) = (\bigcup \A) \cup (\bigcup \B)$. Czy zachodzi równość $\bigcup (\A \cap \B) = (\bigcup \A) \cap (\bigcup \B)$?

Zadanie 11

Rodzina zbiorów $\A$ jest łańcuchem jeśli dla każdych $X,Y \in \A$ zachodzi $X \incl Y$ lub $Y \incl X$. Udowodnij, że:

1. iloczyn dowolnej niepustej rodziny łańcuchów jest łańcuchem,
2. suma łańcucha łańcuchów jest łańcuchem.