Informatyka MIMUW

$\def\NN{\mathbb{N}} \def\RR{\mathbb{R}} \def\ZZ{\mathbb{Z}} \def\QQ{\mathbb{Q}} \def\r{\,r\,} \def\R{\cal R} \def\pot#1{{\sf P}(#1)} \def\la{\langle} \def\ra{\rangle} \def\fczesc{\mathrel{{-}\mskip-2.7mu{\circ}\mskip-2.7mu{\rightarrow}}} \def\poz{\vphantom{f}}$

Zadanie 1

Podaj przykład zbioru częściowo uporządkowanego z dwoma elementami maksymalnymi i jednym minimalnym, bez elementu najmniejszego i z takim czteroelementowym antyłańcuchem, który jest ograniczony z góry ale nie ma kresu górnego.

Zadanie 2

W zbiorze $\{2,3,4,5,6,8,9,12,24\}$, uporządkowanym częściowo przez relację podzielności ($m \preceq n$ wtedy i tylko wtedy gdy $n = m\cdot k$, dla pewnego $k \in \NN$) wskaż wszystkie elementy minimalne, maksymalne, największe i najmniejsze. Czy istnieją w tym zbiorze trzyelementowe łańcuchy lub antyłańcuchy?

Zadanie 3

Niech $r \subseteq \NN^\NN\times \NN^\NN$ będzie relacją określoną następująco: $f\r g \Leftrightarrow \forall_{n \in \NN} \; f(n) \leq g(n)$. Udowodnij, że $\la\NN^\NN, r\ra$ to częściowy porządek. Wskaż elementy minimalne, najmniejsze, maksymalne, największe, nieskończony łańcuch, nieskończony antyłańcuch. Czy jest to porządek liniowy? Czy jest gęsty?

Zadanie 4

Rozpatrzmy zbiór $\{0,1\}^*$ z porządkiem leksykograficznym $\preceq_{lex}$. Znajdź kres górny i dolny (jeśli istnieją) dla następujących zbiorów:

1. $A=\{01^n \; | \; n \in \NN\}$
2. $B=\{0^n1 \; | \; n \in \NN\}$
3. $C=\{w \in \{0,1\}^* \; | \; \textrm{liczba zer i jedynek w słowie}\; w\; \textrm{jest taka sama}\}$
4. $D=C-\{\epsilon\}$
5. $E=\{0,1\}^* - C$

Zadanie 6

Jak zmienią sie odpowiedzi gdy kresy powyższych zbiorów będą szukane w częściowym porządku $\la\{0,1\}^\NN \cup \{0,1\}^*, \preceq_{lex}\ra$, gdzie $\{0,1\}^\NN \cup \{0,1\}^*$ jest zbiorem słów skończonych lub nieskończonych nad alfabetem $\{0,1\}$, a $w \preceq_{lex} v$ zachodzi wtedy i tylko wtedy gdy $w$ jest prefiksem $v$ lub gdy istnieje pozycja $i$ taka, że $w_i=0$ i $v_i=1$?

Zadanie 7

Które z następujacych stwierdzeń są prawdziwe dla dowolnego porządku $\la X,\leq\ra$ i dowolnych $A,B\subseteq X$:

1. Jeśli istnieje $\sup(A\cup B)$, to istnieją $\sup A$ i $\sup B$?
2. Jeśli istnieją $\sup A$ i $\sup B$, to istnieje $\sup(A\cup B)$?
3. Jeśli istnieją $\sup A$, $\sup B$ i $\sup(A\cup B)$, to $\sup(A\cup B)=\sup\{\sup A,\sup B\}$?

Zadanie 8

Niech $A$ i $B$ będą zbiorami częściowo uporządkowanymi i niech funkcje $f:A\to B$ oraz $g:B\to A$ będą monotoniczne. Udowodnić, że następujące warunki są równoważne:

1. $\forall a{\in}A\;\forall b{\in}B\;(a\leq g(b) \Leftrightarrow f(a)\leq b)$;
2. $\forall a{\in}A\;(a\leq g(f(a)))$ oraz $\forall b{\in}B\;(f(g(b))\leq b)$.

Zadanie 9

Niech $A$ będzie dowolnym zbiorem i niech $B \subseteq A \times A$. Udowodnij, że istnieje maksymalny zbiór $C \subseteq A$ taki, że $C\times C \subseteq B$.

Zadanie 10

Udowodnij, że każdy częściowy porządek można rozszerzyć do liniowego.

Zadanie 11

Niech $A$ będzie dowolnym zbiorem do którego należą $0$ i $1$ i niech $f: \pot{A^*} \to \pot{A^*}$ będzie określona następująco

Udowodnij, że $f$ jest monotoniczna, zbadaj jakie są jej punkty stałe i udowodnij, że $\{0,1\}^*$ jest jej najmniejszym punktem stałym.

Zadanie 12 (omawiane na wykładzie)

Rozważmy częściowy porządek $\la A \fczesc B, \subseteq\ra$, gdzie $A \fczesc B)$ to zbiór funkcji częściowych z $A$ do $B$ i $f \, \subseteq\, g$ wtedy i tylko wtedy gdy dla każdego $a \in A$ albo $f(a)$ jest nieokreślone, albo obie funkcje $f$ i $g$ są określone w $a$ i $f(a)=g(a)$. Czy $\la A \fczesc B, \subseteq\ra$ jest kratą zupełną?

Zadanie 13 (omawiane na wykładzie)

Udowodnij, że porządek $\la A \fczesc B, \subseteq\ra$ zdefiniowany powyżej jest zupełny.

Zadanie 14

Niech $A = \{3 - {1\over 2n} \;|\; n \in \NN - \{0\}\}$, $B = \{\pi - {2\over n} \;|\; n \in \NN - \{0\}\}\cup \{4\}$, $C = \{0\} \cup \{{1\over n} \;|\; n \in \NN - \{0\}\}\cup \{2 - {1\over n} \;|\; n \in \NN - \{0\}\}$. Rozpatrzmy zbiory $A$, $B$, $A \cup B$, $C$, $\NN$, $\ZZ$, $\QQ$, $\QQ - \{0\}$, $\RR$, $\RR - \{0\}$ uporządkowane liniowo przez zwykłą relację ,,$\leq$''. Które z nich są izomorficzne?