Strona główna › Logika dla informatyków › Ćwiczenia

Logika pierwszego rzędu: formalizowanie własności

pon., 10/18/2010 - 12:14 — ciebie

Zad. 1

Dla każdej z par struktur:

  • \(\langle {\mathbb N},\leq\rangle\) i \(\langle \{m-{1\over n}\ |\ m,n\in{\mathbb N}-\{0\}\}, \leq\rangle\);
  • \(\langle {\mathbb N}, +\rangle\) i \(\langle {\mathbb Z}, +\rangle\);
  • \(\langle {\mathbb N}, \leq\rangle\) i \(\langle {\mathbb Z}, \leq\rangle\),

    wskaż zdanie prawdziwe w jednej z nich a w drugiej nie.

    Zad. 2

    Napisać takie zdania \(\varphi\) i \(\psi\), że:

    • zdanie \(\varphi\) jest prawdziwe w modelu \({\mathfrak A} = \langle {\mathbb Z}, +, 0 \rangle\), ale nie w modelu \({\mathfrak B} = \langle {\mathbb N}, +, 0 \rangle\);
    • zdanie \(\psi\) jest prawdziwe w modelu \({\mathfrak B} = \langle {\mathbb Z}, +, 0 \rangle\), ale nie w modelu \({\mathfrak C} = \langle {\mathbb Q}, +, 0 \rangle\).

    Zad. 3

    Wskazać formułę pierwszego rzędu:

    • spełnialną w ciele liczb rzeczywistych ale nie w ciele liczb wymiernych;
    • spełnialną w algebrze \({\mathbb N}\) z mnożeniem, ale nie w algebrze \({\mathbb N}\) z dodawaniem;
    • spełnialną w \(\langle \{a,b\}^*,\cdot,\varepsilon\rangle\) ale nie w \(\langle \{a,b,c\}^*,\cdot,\varepsilon\rangle\).

    • Definicje pomocnicze
    Spektrum \(Spec(\varphi)\) zdania \(\varphi\) to zbiór wszystkich liczb naturalnych \(n\) takich, ze \(\varphi\) ma model o mocy \(n.\)

    Standardowy model arytmetyki to struktura \(\mathfrak{N}=\langle\mathbb{N},*^{\mathfrak{N}},+^{\mathfrak{N}},0^{\mathfrak{N}},1^{\mathfrak{N}},\leq^{\mathfrak{N}}\rangle.\)

    Zad. 4

    Podać przykład zdania \(\varphi\) (sygnatura też jest do wyboru) takiego, że \(Spec(\varphi)=Spec(\lnot\varphi).\)

    Zad. 5

    Podać przykład zdania \(\varphi\) (sygnatura też jest do wyboru) takiego, że \(Spec(\varphi)=\{ n^{2}~/~n\in\mathbb{N}\}.\)

    Zad. 6

    Podać przykład zdania \(\varphi\) (sygnatura też jest do wyboru) takiego, że \(Spec(\varphi)=\{ 2*n~/~n\in\mathbb{N}\}.\)

    Zad. 7

    Podać przykład zdania \(\varphi\) (sygnatura też jest do wyboru) takiego, że \(Spec(\varphi)=\{ n~/~n\in\mathbb{N}\ n\) jest liczbą złożoną\(\}\).

    Zad. 8

    Podać przykład zdania \(\varphi\) (sygnatura też jest do wyboru) takiego, że \(Spec(\varphi)=\{ 2^{n}~/~n\in\mathbb{N}\}.\)

    Zad. 9

    Podać przykład zdania \(\varphi\) (sygnatura też jest do wyboru) takiego, że dla każdego naturalnego \(n,\) \(\varphi\) ma dokładnie \(n\) nieizomorficznych modeli mocy \(n.\)

    Zad. 10

    Podać przykład zdania \(\varphi\) (sygnatura też jest do wyboru) takiego, że dla każdego naturalnego \(n,\) \(\varphi\) ma dokładnie \(2^{n}\) nieizomorficznych modeli mocy \(n.\)

    Zad. 11

    Podać przykład zdania \(\varphi\) (sygnatura też jest do wyboru) takiego, że dla każdego naturalnego \(n,\) \(\varphi\) ma dokładnie \(n!\) nieizomorficznych modeli mocy \(n.\)

    Zad. 12

    Dla ustalonego \(k\in\mathbb{N},\) podać przykład zdania \(\varphi\) (sygnatura też jest do wyboru) takiego, że dla każdego naturalnego \(n,\) \(\varphi\) ma dokładnie \({n \choose k}\) nieizomorficznych modeli mocy \(n.\)

    Zad. 13

    Dla ustalonego \(k\in\mathbb{N},\) podać przykład zdania \(\varphi\) (sygnatura też jest do wyboru) takiego, że dla każdego naturalnego \(n,\) \(\varphi\) ma dokładnie \(n^{k}\) nieizomorficznych modeli mocy \(n.\)

    Zad. 14

    Znaleźć formułę \(\varphi(x,y)\) stwierdzającą w standardowym modelu arytmetyki, że \(x\) jest względnie pierwsze z \(y.\)

    Zad. 15

    Znaleźć formułę \(\varphi(x,y,z)\) stwierdzającą w standardowym modelu arytmetyki, że \(z\) jest największym wspólnym dzielnikiem \(x\) i \(y.\)

    Zad. 16

    Znaleźć formułę \(\varphi(x,y,z)\) stwierdzającą w standardowym modelu arytmetyki, że \(y\) jest największą liczbą, będącą potęgą liczby pierwszej, która dzieli \(x.\)

    Zad. 17

    Rozważamy skończone skierowane cykle \(\mathfrak{C}\) (ta litera to gotyckie C, w rozwiązaniu można pisać zwykłe C) nad sygnaturą składającą się z jednego dwuargumentowego symbolu relacyjnego \(E\).

    Udowodnić, że dla każdego naturalnego \(n\) istnieje formuła \(\varphi_n(x,y,z)\) logiki pierwszego rzędu, w której występują tylko trzy zmienne (które można rekwantyfikować tak często jak potrzeba), takie że dla każdego skończonego cyklu \(\mathfrak{C}\) zachodzi równoważność: \(\mathfrak{C},x:a,y:b,z:c\models\varphi_n(x,y,z)\) wtw \(\mathfrak{C}\) ma \(3n\) krawędzi, a skierowane odległości z \(a\) do \(b\), z \(b\) do \(c\) i z \(c\) do \(a\) wszystkie wynoszą po \(n\).

    Zad. 18

    Rozważamy skończone drzewa binarne \(\mathfrak{T}\) (ta litera to gotyckie T, w rozwiązaniu można pisać zwykłe T) nad sygnaturą składającą się z dwóch dwuargumentowych symboli relacyjnych \(L\) i \(P\), przy czym \(L(x,y)\) oznacza że \(y\) to lewy syn ojca \(x\), podobnie dla \(P\) oznaczającego prawego syna. Każdy wiechołek może mieć 0, 1 lub 2 synów, zawsze najwyżej jednego lewego jednego prawego.

    Udowodnić, że dla każdego naturalnego \(n\) istnieje zdanie \(\varphi _{n}\) logiki pierwszego rzędu, w którym występują tylko dwie zmienne (które można rekwantyfikować tak często jak potrzeba), takie że dla każdego skończonego drzewa binarnego \(\mathfrak{T}\) zachodzi równoważność: \(\mathfrak{T}\models\varphi _{n}\) wtw \(\mathfrak{T}\) jest pełnym drzewem binarnym o głębokości \(n\).