Zadanie 1 (10 punktów) Niech sygnatura \(\Sigma\) składa
się tylko z symboli relacyjnych: dwuargumentowego \(E\) i jednoargumentowego \(P\). Rozważmy klasę \(\mathcal{A}\) struktur \(\mathfrak{A}=(A, E^{\mathfrak{A}}, P^{\mathfrak{A}})\) nad sygnaturą \(\Sigma\), w których \(E^{\mathfrak{A}}\) jest symetryczna i takich, że w każdej spójnej składowej \((A,E^{\mathfrak{A}})\) istnieje wierzchołek spełniający \(P^{\mathfrak{A}}\).
Określ, czy klasa \(\mathcal{A}\) jest (i) aksjomatyzowalna jednym zdaniem logiki pierwszego rzędu, (ii) aksjomatyzowalna zbiorem zdań logiki pierwszego rzędu, ale nie pojedynczym zdaniem, (iii) nieaksjomatyzowalna żadnym zbiorem zdań pierwszego rzędu.
Zadanie 2 (10 punktów) Prosty graf nieskierowany (zwany dalej grafem) to struktura \(\mathfrak{G}\) nad
sygnaturą z jednym dwuargumentowym symbolem relacyjnym \(E\), taka że relacja \(E^{\mathfrak{G}}\) jest symetryczna (tzn. jeśli \((x,y)\in E^{\mathfrak{G}}\) to \((y,x)\in E^{\mathfrak{G}}\)) i antyzwrotna (tzn. nie ma takich \(x\) że \((x,x)\in E^{\mathfrak{G}}\)). Dopełnieniem grafu \(\mathfrak{G}\) jest graf \(\overline{\mathfrak{G}}\) o tym samym zbiorze wierzchołków co \(\mathfrak{G}\), w którym występują dokładnie te krawędzie, które nie występują w \(\mathfrak{G}\).
Dla (i) \(n=5\) oraz dla (ii) \(n=6\) narysuj taki graf \(\mathfrak{G}\) o \(n\) wierzchołkach, żeby Gracz II miał strategię wygrywającą w grze Ehrenfeuchta-Fra\"{\i}ss\'e o możliwie wielu rundach na grafie \(\mathfrak{G}\) i jego dopełnieniu \(\overline{\mathfrak{G}}\). Im więcej rund uzyskasz, tym lepsze rozwiązanie. Napisz ile rund uzyskałeś/aś i, o ile to możliwe, podaj formułę logiczną o możliwie małej głębokości kwantyfikatorowej, która rozróżnia \(\mathfrak{G}\) i \(\overline{\mathfrak{G}}\).
Zadanie 3 (10 punktów) Napisz zdanie w monadycznej logice drugiego rzędu MSO, które definiuje klasę \(\mathcal{A}\) z zadania 1.
Zadanie 4 (10 punktów) Niech \(\mathfrak{A}=\langle \mathbb{Z}\times\mathbb{Z},E^\mathfrak{A},U^\mathfrak{A}\rangle,\) gdzie \(E\) jest symbolem relacji dwuargumentowej a \(U\) jest symbolem relacji jednoargumentowej. \(\langle x,y\rangle E^\mathfrak{A}\langle x',y'\rangle\) zachodzi wtedy i tylko wtedy, gdy (\(x=x'\) i \(|y-y'|=1\)) lub (\(|x-x'|=1\) i \(y=y'\)). Zatem \(\langle \mathbb{Z}\times\mathbb{Z},E^\mathfrak{A}\rangle\) to przeliczalny graf nieskierowany w kształcie kraty.
(i) Napisz zdanie \(\varphi\) logiki pierwszego rzędu wyrażające własność, że \(U^\mathfrak{A}\) jest sumą pewnego zbioru pełnych wierszy lub pewnego zbioru pełnych kolumn kraty \(E^\mathfrak{A}\).
(ii) Udowodnij, że nie istnieje zdanie \(\varphi\) logiki pierwszego rzędu wyrażające własność, że \(U^\mathfrak{A}\) jest sumą pewnego zbioru pełnych kolumn kraty \(E^\mathfrak{A}\).
TEST
Pytanie 1 (2 punkty) Czy istnieje liczba \(k\) taka, że dla każdego zdania \(\varphi\) logiki
pierwszego rzędu istnieje formuła \(\psi\) w której nie występują
kwantyfikatory, ciąg kwantyfikatorów
\(Q_1,\ldots,Q_k\in\{\forall,\exists\}\) i ciąg zmiennych \(x_1,\ldots,
x_k\) taki że tautologią jest
\[
\varphi \leftrightarrow Q_1x_1\cdots Q_kx_k\psi \qquad ?
\]
Pytanie 2 (2 punkty) Czy następujące zdanie logiki drugiego rzędu SO, nad sygnaturą z jednym dwuargumentowym symbolem relacyjnym \(E\), jest tautologią?
\begin{align*}
\exists R &[\forall x\forall y(E(x,y)\to R(x,y))
\ \land\ \forall x\forall y\forall z(R(x,y)\land R(y,z)\to R(x,z))
\ \land\ \exists x\exists y\neg R(x,y)] \\
\rightarrow \\
\exists P &[\exists x P(x)\ \land\ \exists x\neg P(x)
\ \land\ \forall x\forall y(P(x)\land E(y,x)\to P(y))]
\end{align*}
Pytanie 3 (2 punkty) Czy rozstrzygalny jest następujący problem:
Dane: zdanie \(\varphi\) logiki drugiego rzędu SO oraz skończony model \(\mathfrak{A}\) nad tą samą sygnaturą.
Pytanie: czy \(\mathfrak{A} \models \varphi\)?
Pytanie 4 (2 punkty) Czy dla każdej sygnatury \(\Sigma\) i każdej struktury \(\mathfrak{A}\) mocy \(\mathfrak{c}\) nad \(\Sigma\) istnieje przeliczalna struktura \(\mathfrak{B}\) nad \(\Sigma\) taka, że \(\mathfrak{A}\equiv\mathfrak{B}\)?
Pytanie 5 (2 punkty) Czy język słów nad alfabetem \(\{0,1\}\), które są palindromami jest definiowalny w logice pierwszego rzędu nad sygnaturą modeli-słów, w tym wypadku złożoną z binarnego \(\leq\) i unarnego \(X\)? Zakładamy, że prawdziwość \(X\) oznacza literę 1, a fałszywość literę 0.