Ć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}}\).