Informatyka MIMUW

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.