Ćwiczenia 11: relacje równoważności

Zadania

1. Jaka jest najmniejsza i największa (w sensie zawierania) relacja równoważności w zbiorze A?
2.  Czy istnieje relacja równoważności w \(\NN\), która ma:
   a) dokładnie dwie klasy abstrakcji po 37 elementów,
   b) dwie klasy abstrakcji po 37 elementów, trzy klasy abstrakcji po 33 elementy i jedną nieskończoną klasę abstrakcji,
   c) nieskończenie wiele klas abstrakcji, każda o nieskończonej liczbie elementów.
3. Niech \(R \subseteq \NN^\NN \times \NN^\NN\) będzie określona tak:
   \[ \langle f, g \rangle \hbox{ wtw. } \forall n(f(n) - g(n) \hbox{ jest liczbą parzystą. })\]
   a) Pokazać, że R jest relacją równoważności.
   b) Opisać klasę abstrakcji funkcji identycznościowej.
   c) Czy zbiór \((\NN\to\NN)/_R\) jest nieskończony?
   d) Czy zbiór \(\{f: \NN\to \NN \mid f(0) = 2\}\) jest klasa abstrakcji tej relacji?
4. Niech \(r \subseteq \NN^\NN \times \NN^\NN\) będzie określona tak:
   \[ \langle f, g \rangle \hbox{ wtw. } f(\NN) = g(\NN).\]
   a) Udowodnić jednym krótkim zdaniem, że r jest relacją równoważności.
   b) Znaleźć \([\lambda x.1]_r\) i \([id_{\NN}]_r\).
   c) Czy zbiór wszystkich funkcji różnowartościowych jest klasą abstrakcji tej relacji?
   d) Czy istnieje dwuelementowa klasa abstrakcji?
5. Niech \(r\) będzie relacją równoważności w \(\NN\) i niech \(f : \NN \times \NN \to P(\NN)\) będzie taka, że:
   \[f(\langle x,y \rangle) = [x]_r \cup [y]_r\]
   a) Czy f jest różnowartościowa?
   b) Czy f jest na \(P(\NN)\)?
   c) Znaleźć \(f^{-1}(\{ [3]_r \})\).
   d) Znaleźć \(f(r)\).
6. Niech A będzie niepustym zbiorem i niech \(f:A \to A\).
   a) Udowodnić, że jeśli f jest różnowartościowa, to relacja \(r \subseteq A \times A\) dana warunkiem
   \[ x r y \hbox{ wtw. } \exists n \in \NN (f^n(x) = y \hbox{ lub } f^n(y) = x) \]
   jest relacją równoważności.
   b) Czy prawdziwe jest twierdzenie odwrotne, tj. jeśli r jest relacją równoważności, to f musi być różnowartościowa?

Praca domowa

Zadania 180, 186.
Dla chętnych: zadanie 192.

Ćwiczenia 10: logika pierwszego rzędu

Zadania

1.  W strukturze \(\mathcal{A} =\langle \NN, P^{\mathcal{A}},Q^{\mathcal{A}}\rangle\), gdzie:
   \( \langle a,b \rangle \in P^{\mathcal{A}}\) wtedy i tylko wtedy, gdy \(a+b \geq 6\),
   \( \langle a,b \rangle \in Q^{\mathcal{A}}\) wtedy i tylko wtedy, gdy \(b = a + 2\),
   wyznaczyć wartość
   a) formuły \(\forall x P(x,y) \to \exists xQ(x,y)\), przy wartościowwaniu \(v(y) = 7\),
   b) formuły \(\forall x P(x,y) \to \forall xQ(x,y)\), przy wartościowwaniu \(v(y) = 7\),
   c) formuły \(\forall x P(x,y) \to \exists xQ(x,z)\), przy wartościowwaniu \(u(y) = 3, u(z) = 2\).
   
2. Podać przykład modelu i wartościowania, przy którym formuła
   \[ P(x,f(x)) \to \forall x \exists y P(f(y), x) \]
   jest a) spełniona b) niespełniona.
3. Dla każdej z następujących par struktur wskaż formułę prawdziwą w jednej z nich a w drugiej nie (dla utrudnienia można oczekiwać formuły otwartej spełnialnej w jednej strukturze, a w drugiej nie):
   a) \(\langle \QQ, +, \cdot, 0, 1\rangle\) i \(\langle \RR, +, \cdot, 0, 1\rangle\),
   b) \(\langle \NN, +, 0 \rangle\) i \(\langle \NN, \cdot, 1\rangle\),
   c) \(\langle P_2, \parallel \rangle\) i \(\langle P_2, \bot \rangle\), gdzie \(P_2\) to zbiór prostych w \(\RR^2\),
   d) \(\langle P_2, \bot \rangle\) i \(\langle P_3, \bot \rangle\), gdzie \(P_2\) to zbiór prostych w \(\RR^2\), a \(P_3\) to zbiór prostych w \(\RR^3\),
   e) \(\langle \NN, \leq \rangle\) i \(\langle \ZZ, \leq\rangle\).
4. Sygnatura \(\Sigma\) składa się z symbolu równości i dwóch jednoargumentowych symboli relacyjnych R, S i jednego jednoragumentowego symbolu funkcyjnego f.
   a) Napisać zdanie prawdziwe dokładnie w tych modelach \(\mathcal{A} =\langle A, R^{\mathcal{A}},S^{\mathcal{A}}, f^{\mathcal{A}}\rangle\), w których obraz zbioru \(R^{\mathcal {A}}\) przy funkcji \(f^{\mathcal {A}}\) zawiera się w zbiorze \(S^{\mathcal {A}}\).
   b) Napisać zdanie prawdziwe dokładnie w tych modelach \(\mathcal{A} =\langle A, R^{\mathcal{A}},S^{\mathcal{A}}, f^{\mathcal{A}}\rangle\), w których zbiór \(S^{\mathcal {A}}\) jest przeciwobrazem zbioru \(R^{\mathcal {A}}\) przy funkcji \(f^{\mathcal {A}}\).
5. Zapisać następujące stwierdzenia w języku arytmetyki  liczb naturalnych (\(+, \cdot, 0, 1, =\)) używając symboli logicznych i kwantyfikatorów.
   a) Liczba a jest mniejsza lub równa liczbie b.
   b) Liczba a jest resztą z dzielenia liczby b przez c.

Praca domowa

1. Dla każdej z następujących par struktur wskaż formułę prawdziwą w jednej z nich a w drugiej nie (dla utrudnienia można oczekiwać formuły otwartej spełnialnej w jednej strukturze, a w drugiej nie):
   a) \(\langle \RR, +, \cdot, 0, 1\rangle\) i \(\langle P(\NN), \cup, \cap, \emptyset, \NN\rangle\),
   b) \(\langle \NN, +, 0, \rangle\) i \(\langle \{a,b\}^*, \cdot, \epsilon \rangle\),
   c) \(\langle \ZZ, \leq \rangle\) i \(\langle \QQ, \leq \rangle\).
2. Sygnatura \(\Sigma\) składa się z symbolu równości i dwóch dwuargumentowych symboli relacyjnych R, S. Napisać zdanie prawdziwe dokładnie w tych modelach \(\mathcal{A} =\langle A, R^{\mathcal{A}},S^{\mathcal{A}}\rangle\), w których:
   a) złożenie relacji \(R^{\mathcal{A}}\) z relacją \(S^{\mathcal{A}}\) jest identyczne ze złożeniem relacji \(S^{\mathcal{A}}\) z relacją \(R^{\mathcal{A}}\),
   b) relacja \(S^{\mathcal{A}}\) jest najmniejszą relacją symetryczną zawierającą \(R^{\mathcal{A}}\).

Ćwiczenia 9: rachunek zdań

Zadania

1. Znaleźć, o ile istnieje, taką formułę zdaniową \(\alpha\), aby następujące formuła była tautologią rachunku zdań:
   a) \( (\alpha \to p) \to (p\to q) \),
   b)\( ((r \to (\neg q \wedge p)) \to \alpha) \to (\alpha \wedge (p\to q) \wedge r) \).
2.  Udowodnić, że dla dowolnej funkcji \(f: \{0,1\}^k \to \{0,1\}\) istnieje formuła zdaniowa \(\alpha\), w której występują tylko zmienne zdaniowe \(p_1, ...,p_k\) o tej własności, że dla dowolnego wartościowania zdaniowego \(v\) zachodzi:
   \[ [\alpha]_v = f(v(p_1), \ldots, v(p_k))\]
   Innymi słowy: formuła \(\alpha\) definiuje funkcję \(f\).
3. Czy następujące zbiory formuł są spełnialne?
   a) \( \{ p \to \neg q, q \to \neg r, r \to \neg p \} \),
   b) \( \{ p\to q, q \to r, r \vee s \leftrightarrow \neg q \} \),
   c) \( \{ s \to p, p \vee \neg q, \neg (s \wedge p), s \} \).
4. Zbadać, czy następujące rozumowania są logicznie poprawne. Każde stwierdzenie trzeba zastąpić zmienną zdaniowa, następnie należy stwierdzić czy konkluzja wynika z koniunkcji przesłanek.
   a) Jeśli Jones jest komunistą, to Jones jest ateista. Jonest jest ateistą. Zatem Jones jest komunistą.
   b) Jeśli temperatura i ciśnienie nie zmieniają się, nie ma deszczu. Temperatura nie zmieniła się. Zatem jeśli spadł deszcz, to ciśnienie się zmieniło.

Praca domowa

Zadanie 115 ze zbioru zadań.

Ćwiczenia 8: porządki cz. 2

Zadania

1.  Udowodnić, że jeśli w porządku częściowym każdy dwuelementowy podzbiór ma kres górny, to każdy niepusty podzbiór ma kres górny.
2. Podać przykład zupełnego porządku częściowego, który nie jest kratą zupełną. (Wskazówka: takim porządkiem jest zbiór funkcji częściowych z relacją zgodności.)
3. 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\), że \(a \leq b\).

Praca domowa

Zadania 381 i 366 (bez pytania o bijekcję).

Dla chętnych: zadanie 386. Definicja: Krata - częściowy porządek, w którym każdy dwuelementowy podzbiór ma kres górny.

Ćwiczenia 7: porządki

Zadania

1. (Utajnione) Zadanie z kartkówki. 
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\}^{\NN}\) takie, że
   \[ 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 w nim antyłańcuch nieskończony?
   d) Czy ma element maksymalny, minimalny, najmniejszy, największy?
4. Czy zbiór \(\{01^n \mid n \in \NN\}\) ma kres górny (dolny) w zbiorze \(\{0,1\}^{\NN}\) uporządkowanym leksykograficznie?
5. Czy zbiór \(\{0^n1 \mid n \in \NN\}\) ma kres górny (dolny) w zbiorze \(\{0,1\}^{\NN}\) uporządkowanym leksykograficznie?

Praca domowa

Zadania 352 i 353 ze zbioru zadań.

Ćwiczenia 6: równoliczość i relacje

Zadania

1. Pokazać, że jeśli \(A \sim B\), to \(P(A) \times P(B) \sim \{0,1,2,3\}^A\).
2. Znaleźć przykład pięcioelementowej relacji na zbiorze liczb naturalnych, która jest
   a) przechodnia,
   b) symetryczna,
   c) zwrotna.
3. Niech \(r = \{ \langle A, B\rangle \in P(\NN) \times P(\NN) \mid A \subseteq B\}\) i \(s = \{ \langle A, B\rangle \in P(\NN) \times P(\NN) \mid A \cap B = \emptyset\}\).
   a) Czy \(r \cdot s  = s \cdot r\)?
   b) Czy \(r^{-1} = r\)?
   c) Czy \(s^{-1} = s\)?
4. Dla jakich relacji \(r \subseteq A \times A\) zachodzą równości \(r \cdot r^{-1} = r^{-1} \cdot r = id_{A}\)?

Praca domowa

Zadania 163 i 491 a,b,e ze zbioru zadań.

Ćwiczenia 5: funkcje

Zadania

1. Niech funkcja \(f : P(\NN) \to (\NN \to \NN) \) będzie taka, że
   \[f(S)(n) = max\{ x \in S \cup \{0\} \mid x \leq n \}.\]
   a) Czy f jest różnowartościowa?
   b) Czy f jest na \(\NN \to \NN\)?
   c) Udowodnić, że \(f(\NN)(\NN) = \NN\).
   d) Udowodnić, że dla dowolnego \(S \subseteq \NN\) zachodzi
   \[f(S)^{-1}(S) = \NN \hbox{ wtw. } 0 \in S\]
   e) Udowodnić, że \(f^{-1}(C) = \{\emptyset, \{0\}\}\), gdzie C to zbiór funkcji stałych.
2. Funkcję \(F : (\NN \to P(\NN)) \to P(\NN)\) jest określona warunkiem
   \[ F(x) = \bigcup \{x(i) \mid i \in \NN\}.\]
   a) Czy F jest różnowartościowa?
   b) Czy F jest na \(P(\NN)\)?
   c) Czy istnieje zbiór \(A \subseteq \NN\) taki, że \(F^{-1}(\{A\})\) jest jednoelementowy?
   d) Czy istnieje zbiór \(A \subseteq \NN\) taki, że \(F^{-1}(\{A\})\) jest czteroelementowy?
3. Podać przykład pary funkcji \(f,g : \NN \to \NN\) spełniających wszystkie poniższe warunki:
   a)\(\forall x( g(x) \neq x)\),
   b) \(g \circ g = id_{\NN}\),
   c) \(f \circ g = g\),
   d) \(f\) jest na \(\NN\),
   e) obrazem zbioru liczb parzystych przy przekształceniu g jest zbiór liczb nieparzystych.
4. Podać przykład pary funkcji \(f,g : \NN \to \NN\) spełniających wszystkie poniższe warunki:
   a)\(\forall x( g(x) \neq x)\),
   b) \(g \circ g = id_{\NN}\),
   c) \(f \circ g = f\),
   d) \(f\) jest na \(\NN\),
   e) obrazem zbioru liczb parzystych przy przekształceniu g jest zbiór liczb nieparzystych.
5.  Pokazać, że funkcja \(\varphi:P(A)^B \to P(A\times B)\) taka, że
   \[ \varphi(f) = \{\langle a,b\rangle \in A \times B \mid  a \in f(b)\} \]
   jest bijekcją.
6. Znaleźć przykład takiej funkcji \(f: \NN\to\NN\), że przeciwobraz każdego zbioru jednoelementowego jest
   a) jednoelementowy,
   b) dwuelementowy,
   c) nieskończony.

Praca domowa

Zadania 79 i 116 ze zbioru zadań.

Ćwiczenia 4: iloczyn kartezjański, funkcje

Zadania

1. Kiedy \(A \times B = B \times A\)?
2. Czy dla dowolnych niepustych rodzin \(\mathcal{A}\) i \(\mathcal{B}\) zachodzi \(\bigcap \mathcal{A} \times  \bigcap \mathcal{B} = \bigcap \{ \alpha \times \beta \mid \alpha \in  \mathcal{A}, \beta \in  \mathcal{B}\}\),
3. Ile jest funkcji, funkcji częściowych, funkcji różnowartościowych, funkcji na
   a) \(\emptyset \to \emptyset\),
   b) \(\emptyset \to \{ \cdot \}\),
   c) \(\{ \cdot \}\to \emptyset\),
   d) \(\{ \cdot \}\to \{ \cdot \}\),
   e) \(\{ \cdot, \square \}\to \{ \cdot \}\),
   f) \(\{ \cdot \}\to \{ \cdot, \square \}\)?
4. Niech \(f:A\to B\). Pokazać, że f jest różnowartościowa wtedy i tylko wtedy, gdy dla każdego C i dla każdych \(g,h: C \to A\) zachodzi \(f \circ g = f\circ h \to g=h\).
5. Podać przykład \(f : A \to B\), \(X \subseteq A\), \(Y \subseteq B\) takich, że
   a) \(f^{-1}(f(X)) \neq X\),
   b) \(f(f^{-1}(Y)) \neq Y\).
6. Niech \(F : \NN^{\NN} \to P(\NN)\) będzie taka, że \(F(f) = f^{-1}(\{1\})\).
   a) Czy \(F\) jest różnowartościowa?
   b) Czy \(F\) jest na \(P(\NN)\)?
   c) Znaleźć obraz zbioru funkcji stałych.

 Praca domowa

Zadania 82 i 110 ze zbioru zadań.

Ćwiczenia 3: suma i iloczyn uogólniony

Zadania

1.  Które z poniższych implikaci są prawdziwe dla dowolnych zbiorów X, Y:
   a) jeśli \( P(Y) \subseteq X \), to \(Y \subseteq \bigcup X\),
   b) jeśli \(Y \subseteq \bigcup X\), to \( P(Y) \subseteq X \).
2. a) Czy jeśli \(\mathcal{A} \subseteq \mathcal{B}\), to \(\bigcap \mathcal{A} \subseteq \bigcap \mathcal{B}\)?
   b) Czy jeśli \(\mathcal{A} \subseteq \mathcal{B}\), to \(\bigcap \mathcal{B} \subseteq \bigcap \mathcal{A}\)?
3. Czy dla dowolnych niepustych A, B takich, że \(A \cap B \neq \emptyset\) zachodzi:
   a) \(\bigcup A \cup\bigcup B = \bigcup (A \cup B)\)
   b) \(\bigcap A \cap\bigcap B = \bigcap (A \cap B)\),
   c) \(\bigcap A \cap\bigcap B = \bigcap (A \cup B)\)?
4. Które z równości zachodzą dla dowolnego A:
   a) \(\bigcap \{P(B) \mid B \subseteq A \} = \{ \bigcap P(B) \mid B \subseteq A \} \),
   b) \(\bigcup \{P(B) \mid B \subseteq A \} = \{ \bigcup P(B) \mid B \subseteq A \} \)?
5. Znaleźć \( \bigcup_{t \in \RR_+} A_t \) i \( \bigcap_{t \in \RR_+} A_t \), gdzie \(A_t = (1-\frac{1}{t}, 2 + \sqrt{t})\) dla \(t \in \RR_+\).

Praca domowa

Zadania 38 d,e i 43 ze zbioru zadań.

Ćwiczenia 2: rachunek zbiorów, zbiór potęgowy

Zadania

1. Przypuśćmy, że zbiór A ma n elementów, a zbiór B ma n elementów. Ile elementów mają zbiory \(A \cup B\), \(A \cap B\), \(A - B\)?
2. Czy dla dowolnych zbiorów \(A\), \(B\), \(C\) zachodzą równości:
   a) \(A - (B \cup C) = (A - B) - C\),
   b) \(A - (B - C) = (A - B) \cup C\),
   c) \((A \cup B \cup C) - (A \cup B) = C\),
   d) \( A \cap (B \cup C) = (A \cap B) \cup (A \cap C) \)?
3. Sprawdzić, czy dla dowolnych zbiorów w \(A\), \(B\), \(C\) zachodzi następująca implikacja:
   a) jeśli \(C - B \subseteq C - A\), to \(A \subseteq B\),
   b) jeśli \( A - B = B - A \), to \( A = B\).
   
4. Zbadać, czy dla dowolnych \(A\), \(B\) zachodzi:
   a) \(P (A \cup B) = P(A) \cup P(B)\),
   b) \(P (A \cap B) = P(A) \cap P(B)\).
5. a) Czy jeśli \(\mathcal{A} \subseteq \mathcal{B}\), to \(\bigcup \mathcal{A} \subseteq \bigcup\mathcal{B}\)?
   b) Czy jeśli \(\bigcup \mathcal{A} \subseteq \bigcup \mathcal{B}\), to \(\mathcal{A} \subseteq \mathcal{B}\)?
6. Udowodnić, że \(\bigcup P(A) = A\) dla dowolnego A.

Praca domowa

Zadania 25 i 29 ze zbioru zadań.

Oferta pracy: Asystent ds. Marketingu Technicznego w Vertabelo Academy

Firma, w której pracuję szuka studentów do pomocy w promocji naszego produktu, Vertabelo. 

Vertabelo to usługa pozwalająca na wizualne projektowanie baz danych w chmurze bezpośrednio przez przeglądarkę internetową. Na naszej stronie prowadzimy blog o bazach danych, który dziennie odwiedza ponad 3 tysiące osób. Ponadto tworzymy interaktywne kursy języka SQL w serwisie Vertabelo Academy.

Szukamy osób władających językiem angielskim, które pomogą nam w prowadzeniu bloga technicznego Vertabelo oraz w innych działaniach marketingowych.

Zakres obowiązków

• Pomoc w przygotowaniu nowych kursów w Vertabelo Academy (formatowanie przygotowanych treści w HTML, testowanie nowych kursów).
• Wsparcie w procesie przygotowania artykułów na blog (komunikacja z autorami bloga, edytorami i innymi osobami zaangażowanymi w przygotowanie treści bloga).
• Aktualizacja treści opublikowanych na blogu.
• Redagowanie krótkich ogłoszeń o nowych funkcjonalnościach aplikacji.

Wymagane kwalifikacje

• Znajomość zagadnień związanych z wykorzystaniem baz danych.
• Podstawowa znajomość języka HTML.
• Podstawowa znajomość narzędzi deweloperskich.
• Podstawowa znajomość systemu Linux od strony użytkownika.
• Dobra znajomość języka angielskiego.

Dodatkowym atutem będzie:

• Prowadzenie własnego bloga.
• Aktywność w serwisach społecznościowych dla programistów (np. Twitter, Stackoverflow, Github).

Warunki zatrudnienia

• Umowa-zlecenie.
• Wynagrodzenie: 4000 zł brutto za pełny etat.
• Minimum pół etatu.
• Miejsce pracy: Warszawa, okolice metra Wierzbno.

Oferty prosimy przesłać na adres career@vertabelo.com z dopiskiem: Asystent ds. Marketingu Technicznego

Na zgłoszeniu proszę umieścić klauzulę o następującej treści: „Wyrażam zgodę na przetwarzanie moich danych osobowych dla potrzeb niezbędnych do realizacji procesu rekrutacji (podstawa prawna DZ. U. Nr 133, poz. 883)”.

Szczegółowe ogłoszenie.

Tydzień 1: powtórzenie z logiki i indukcji matematycznej

Zadania

1.  Zaznaczyć na rysunku zbiory:
   a) \(\{\langle x, y\rangle \in \mathbb{R}^2 \mid x^2 + y^2 >1  \to y+x > 0\}\),
   b) \[\{\langle x, y\rangle \in \mathbb{R}^2 \mid(x^2 + y^2 >1 ) \to ((x^2 + y^2 \leq 2) \wedge ( \neg (x \cdot y = 0) \to |y| = |x|) ) \}\]
   c) \(\{\langle x, y\rangle \in \mathbb{R}^2 \mid  (\forall z(z+y < 0)) \to y+x<0 \}\),
   d) \(\{\langle x, y\rangle \in \mathbb{R}^2 \mid  (\forall x(x+y < 0)) \to y+x<0 \}\),
   e) \(\{\langle x, y\rangle \in \mathbb{R}^2 \mid  x^2 + y^2 >1  \to \exists z (x^2 + (y-z)^2 \leq \frac{1}{4})\}\).
2. Zaznaczyć na rysunku zbiory:
   a) \( \{z \in \mathbb{R} \mid \forall x \exists x (x=1)\} \),
   b) \( \{z \in \mathbb{R} \mid \exists x \forall x (x=1)\} \),
   c) \( \{x \in \mathbb{R} \mid \forall x \exists x (x=1)\} \).
3. Udowodnić, że \(1 + 2 + 4 + \ldots + 2^n = 2^{n+1} -1\).
4. Udowodnić, że każda liczba naturalna postaci \(4^{2n+1}+3^{2n+1}\) dzieli się przez 7.
5. Udowodnić, że każda liczba naturalna większa lub równa 2 jest iloczynem liczb pierwszych lub sama jest pierwsza.

Praca domowa

Zadanie 4bi 7c ze zbioru zadań.