poniedziałek, 24 listopada 2014

Ćwiczenia 7: porządki cz. 2

Zadania

  1. Rozważmy częściowy porządek \(\langle A \leadsto B, \leq \rangle\), gdzie \(A \leadsto B\) to zbiór funkcji częściowych z A do B i \(f \leq g\), wtedy i tylko wtedy, gdy dla każdego \(a \in A\) albo \(f(a)\) jest nieokreślone, albo obie funkcje są określone i \(f(a) = g(a)\). Czy \(\langle A \leadsto B, \leq \rangle\) jest kratą zupełną?
  2. Udowodnij, że \(\langle A \leadsto B, \leq \rangle\) jest częściowym porządkiem zupełnym.
  3. Niech A i B będą zbiorami częściowo uporządkowanymi i niech funkcje \(f : A \to B\) i \(g : B \to A\) będą monotoniczne. Udowodnić, że następujące warunki są równoważne:
    a) \(\forall a \in A \forall b \in B (a \leq g(b) \leftrightarrow f(a) \leq b  )\)
    b) \(\forall a \in A (a \leq g(f(a))) \wedge \forall b \in B (f(g(b)) \leq b)\).
  4. Podaj przykład takiego przekształcenia monotonicznego f w kracie \(\langle P(\mathbb{N}), \subseteq \rangle\), że kres górny zbioru \( \{ f^n(\emptyset) \mid  n \in \mathbb{N}\} \) nie jest najmniejszym punktem stałym.
  5. Niech A będzie częściowym porządkiem zupełnym i niech \(f : A \to A\) będzie ciągła. Udowodnić, że jeśli \(a \leq f(a)\), to istnieje taki punkt stały b funkcji f, że \(a \leq b\).

Praca domowa

  1. Które z następujących stwierdzeń jest prawdziwe dla dowolnego zbioru częściowo uporządkowanego  \(\langle X, \leq \rangle\) i dowolnych \(A, B \subseteq X\):
    a) Jeśli w X istnieje \(\sup A\) i \(\sup B\), to istnieje \(\sup (A \cup B)\).
    b) Jeśli w X istnieje \(\sup (A \cup B)\), to istnieją.\(\sup A\) i \(\sup B\).
  2. Niech X będzie zbiorem częściowo uporządkowanym i niech \(A \subseteq X\) nie ma elementu największego. Niech \(B = \{b \in X \mid \forall a \in A (b > a) \}. \) Pokazać, że jeśli istnieje \(\inf B\), to istnieje \(\sup A\) oraz \(\sup A = \inf B \in B\).
  3. Dla chętnych: skończyć zadanie 4 z zajęć.

poniedziałek, 17 listopada 2014

Wykład "Ataki na aplikacje internetowe"

Zapraszam na wykład mojego kolegi z pracy Michała Kołodziejskiego pt. "Ataki na aplikacje internetowe". Wykład odbędzie się w czwartek 20 listopada 2014 roku o godzinie 14 (bez kwadransa) w sali 5070.


Ćwiczenia 6: porządki

Zadania

  1. W zbiorze \(\{1,2,3,5,12,15,18,180\}\) uporządkowanym przez relację podzielności wskazać elementy minimalne, maksymalne, najmniejsze, największe. Czy istnieją w tym zbiorze pięcioelementowe łańcuchy? a trzyelementowe antyłańcuchy? Wskaż kres dolny zbioru \(\{3,12\}\) oraz kres górny zbioru \(\{2,5\}\).
  2. Podać przykład zbioru częściowo uporządkowanego z dwoma elementami maksymalnymi, 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.
  3. Rozpatrzmy częściowe uporządkowanie zbioru \(\{0,1\}^{\mathbb{N}}\):
    \[ f \leq g \hbox{ wtw. } \forall_x f(x) \leq g(x)\]
    a) Czy ten porządek jest liniowy?
    b) Czy istnieje w nim łańcuch nieskończony?
    c) Czy istnieje antyłańcuch nieskończony?
    d) Czy ma element największy, najmniejszy, minimalny, maksymalny?
  4. Czy zbiór \(\{01^n \mid n \in \mathbb{N}\}\) ma kres górny (dolny) w zbiorze \(\{0,1\}^{*}\) uporządkowanym leksykograficznie?
  5. Czy zbiór \(\{0^n1 \mid n \in \mathbb{N}\}\) ma kres górny (dolny) w zbiorze \(\{0,1\}^{*}\) uporządkowanym leksykograficznie?
  6. Dany jest następujący częściowy porządek w zbiorze \(P(\mathbb{N} - \{\emptyset\}\):
    \[X \leq Y \hbox{wtw.} ((\min(X) < \min(Y))
    \vee (\min(X) = \min(Y) \wedge X \subseteq Y).\]
    a) Czy ten porządek jest liniowy?
    b) Czy istnieje w tym zbiorze nieskończony ciąg malejący?
    c) Wskaż elementy minimalne, maksymalne, największe, najmniejsze.

 Praca domowa

  1. Jeśli \(\leq\) jest cześciowym porządkiem w A, to relację < nazywamy ostrym uporządkowaniem wyznaczonym przez \(\leq\). Pokazać, że ostre uporządkowania wyznaczone przez porządki częściowe to dokładnie te relacje, które są przechodnie i przeciwzrotne.
  2. Niech \(\langle X, r \rangle, \langle Y, s \rangle \) będą niepustymi zbiorami częściowo uporządkowanymi. Pokazać, że
    a) \(\langle X \oplus Y, r \oplus s \rangle \) jest zbiorem częściowo uporządkowanym bez elementu największego.
    b) Dla dowolnego \(a \in X \oplus Y\) element a jest minimalny w \(\langle X \oplus Y, r \oplus s \rangle \) wtedy i tylko wtedy, gdy a jest elementem minimalnym w \(\langle X, r \rangle\) lub \(\langle Y, s \rangle \).

poniedziałek, 3 listopada 2014

Ćwiczenia 5: relacje

Zadania

  1.  Znaleźć przykład pięcioelementowej relacji na zbiorze liczb naturalnych, która jest
    a) przechodnia,
    b) symetryczna,
    c) zwrotna.
  2. Dla jakich relacji \(r \subseteq A \times A\) zachodzą równości \(r \cdot r^{-1} = r^{-1} \cdot r = 1_A\)?
  3. Udowodnić, że \(r^+ = \bigcup_{n > 0} r^n\).
  4. Niech \(r, s \subseteq A \times A\). Czy dla dowolnych relacji \(r,s\) prawdziwa jest równość \((r^*)^{-1} = (r^{-1})^*\)?

Praca domowa

  1. Niech \(\mathcal{R}\) będzie taką niepustą rodziną relacji przechodnich w zbiorze A, że dla dowolnych \(r, s \in \mathcal{R}\)  zachodzi \(r \subseteq s\) lub \(s \subseteq r\). Udowodnić, że \(\bigcup \mathcal{R}\) jest relacją przechodnią.
  2. Niech\(\varphi : P(\mathbb{N}) \to P(P(\mathbb{N}) \times P(\mathbb{N}))\) będzie taką funkcją, że dla dowolnego \(Z \in P(\mathbb{N})\)
    \[\varphi(Z) = \{\langle X, Y\rangle \mid Z \subseteq X \cap Y\}.\]
    a) Czy \(\varphi\) jest różnowartościowa?
    b) Czy \(\varphi\) jest na?
    c) Która z poniższych równości zachodzi dla dowolnych \(Z_1, Z_2 \in P(\mathbb{N})\)
    • \(\varphi(Z_1 \cap Z_2) = \varphi(Z_1) \cap \varphi(Z_2)\),
    • \(\varphi(Z_1 \cup Z_2) = \varphi(Z_1) \cup \varphi(Z_2)\)?