Ć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ń.