Egzamin poprawkowy 2011/2012 | Informatyka MIMUW

Zadanie 1 (20 punktów) Rozważamy struktury \(\mathfrak{A}\) nad sygnaturą złożoną z dwuargumentowych symboli operacji \(+,-,*\) stałych \(0,1\) oraz jednoragumentowego symbolu operacji \(f.\)

Powiemy, że \(f^\mathfrak{A}\) jest opisana termem arytmetycznym jeśli istnieje term \(\tau(x)\) z jedną zmienną wolną \(x\), nie zawierający symbolu \(f\) oraz taki, że dla każdego wartościowania \(\rho\) w \(\mathfrak{A}\) zachodzi
\([\![f(x)]\!]_\rho=[\![\tau(x)]\!]_\rho.\)

Przykładowo, jeśli \(A=\mathbb{R}\) oraz działania \(+,-,*\) i stałe \(0,1\) mają swoje zwykłe interpretacje znane z ciała liczb rzeczywistych, to \(f^\mathfrak{A}\) jest opisana termem arytmetycznym wtedy i tylko wtedy, gdy \(f^\mathfrak{A}\) jest wielomianem jednej zmiennej o współczynnikach całkowitych.

Udowodnić, że nie istnieje zbiór zdań \(\Delta\) logiki pierwszego rzędu nad powyższą sygnaturą taki, że \(\mathfrak{A}\models\Delta\) wtedy i tylko wtedy, gdy \(f^\mathfrak{A}\) jest opisana termem arytmetycznym.

Szkic rozwiązania

Warunek, że \([\![f(x)]\!]_\rho=[\![\tau(x)]\!]_\rho\) dla każdego \(\rho\) oznacza tyle, że \(\mathfrak{A}\models\forall x f(x)=\tau(x).\)

Przypuśćmy, że zbiór \(\Delta\) opisany w zadaniu istnieje.

Niech \(\tau_1(x),\tau_2(x),\ldots\) będzie listą wszystkich termów arytmetycznych, tzn. nie używających symbolu \(f\).

Stwórzmy nowy zbiór \(\bar{\Delta}=\Delta\cup\{\exists x f(x)\neq \tau_i(x)~|~i\in\mathbb{N}\}\).

Używamy twierdzenia o zwartości, żeby pokazać, że \(\bar{\Delta}\) ma model. Istotnie, niech \(\Delta_0\subseteq\bar{\Delta}\) będzie skończony. Zawiera zatem skończenie wiele formuł postaci \(\exists x f(x)\neq \tau_i(x)\). Chcemy pokazać, że \(\Delta_0\) ma model. Modelem będzie zbiór liczb rzeczywsitych ze standardowo określonymi działaniami arytmetycznymi. Symbol funkcji \(f\) interpretujemy jako wielomian (a zatem funkcję opisaną termem) o stopniu wyższym, niż wszystkie wielomiany opisane termami występującymi w formułach postaci \(\exists x f(x)\neq \tau_i(x)\) należących do \(\Delta_0\).

Przy takim wyborze modelu widać, że spełnia on \(\Delta_0\).

Z dowolności \(\Delta_0\) wynika, że założnia twierdzenia o zwartości są spełnione, a zatem cały zbiór \(\Delta\) też ma model. Jest to jednak sprzeczność, bo w tym modelu interpretacja \(f\) nie jest opisana żadnym termem arytmetycznym.

Zadanie 2 (20 punktów) W pewnej bazie danych znajduje się dwukolumnowa tabela \(G\), zawierająca w sobie zbiór krawędzi pewnego grafu (który dla uproszczenia nazwiemy również \(G\)); w schemacie jest też stała \(a\). Napisać wyrażenie \(E\) algebry relacyjnej nie zawierające żadnego podwyrażenia o więcej niż 3 kolumnach o następującej semantyce:

\([\![E]\!]=\{\langle b\rangle~|~\) odległość od \(b\) do \(a\) w \(G\) nie przekracza 3\(\}.\)

Szkic rozwiązania

Zapytanie \(E_0\) określone jako \(\pi_1(\sigma_{1=a}(G))\cup\pi_1(\sigma_{1=a}(G))\) zwraca wszystkie elementy w odległości 0 od \(a\).

Zapytanie \(E_{1}\) określone jako \(\pi_1(\sigma_{2=3}(G\times E_0))\) zwraca wszystkie elementy połączone z \(a\) ścieżkami o długości 1 i jego żadne podwyrażenie nie ma więcej niż 3 kolumny.

Zapytanie \(E_{2}\) określone jako \(\pi_1(\sigma_{2=3}(G\times E_1))\) zwraca wszystkie elementy połączone z \(a\) ścieżkami o długości 2 i jego żadne podwyrażenie nie ma więcej niż 3 kolumny.

Zapytanie \(E_{3}\) określone jako \(\pi_1(\sigma_{2=3}(G\times E_2))\) zwraca wszystkie elementy połączone z \(a\) ścieżkami o długości 3 i jego żadne podwyrażenie nie ma więcej niż 3 kolumny.

Poszukiwanym wyrażeniem jest \(E_0\cup E_1\cup E_2\cup E_3\).

Zadanie 3 (20 punktów)
Rozważamy nieskończone pełne drzewo binarne z dodatkową relacją unarną \(\mathfrak{T}_U=\langle T,L,P,U\rangle\) (ta dziwna litera to gotyckie T, w rozwiązaniu można pisać zwykłe T). Sygnatura zawiera dwa dwuargumentowe symbole relacyjne \(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 zawsze ma 2 synów: jednego lewego i jednego prawego. W sygnaturze znajduje się ponadto jeden symbol jednoargumentowej relacji \(U\), o którego interpretacji nic szczególnego nie zakładamy.

Skonstruować zdanie \(\varphi\) monadycznej logiki drugiego rzędu MSO o następującej własności:

\(\mathfrak{T}_U\models\varphi\) wtw na pewnej scieżce w drzewie \(\mathfrak{T}_U\) jest nieskończenie wiele elementów zbioru \(U\).

Prawdziwość zdania \(\varphi\) w strukturach innych niż te o postaci \(\mathfrak{T}_U\) jest nieistotna.

Szkic rozwiązania

Zdefiniujmy pomocnicze formuły:
\(Root(x)\) jako \(\lnot \exists y L(y,x)\lor P(y,x)\).

\(Path(x,X)\) (\(X\) jest ścieżką zaczynającą się w \(x\)) jako
\(X(x)\land \forall y(X(y)\to(\exists z(L(y,z)\land X(z))\leftrightarrow\lnot(P(y,z)\land X(z)))\land\forall y((X(y)\land y\neq x)\to\exists z(X(z)\land (L(z,y)\lor P(z,y)))))\)

Teraz wyrażamy żadaną własność jak następuje:

\(\exists x (Root(x)\land\exists X (Path(x,X))\land \forall y(X(y)\to (\exists Y\exists z Path(y,Y)\land U(z)\land X(z)\land Y(z))))\).

Zadanie 4 (20 punktów)
Spektrum \(Spec(\varphi)\) zdania \(\varphi\) to zbiór wszystkich liczb naturalnych \(n\) takich, ze \(\varphi\) ma model o mocy \(n.\)

Niech dana będzie zdanie \(\varphi\) logiki pierwszego rzędu. Skonstruować zdanie \(\psi\) logiki pierwszego rzędu (sygnatura jest do wyboru) takie, że \(Spec(\psi)=\{ 2\cdot n~/~n\in Spec(\varphi)\}.\)

Szkic rozwiązania

Wybieramy jednoragumentowy symbol relacyjny \(U\) i jednoragumentowy symbol funkcyjny \(f\) nie występujące w \(\varphi\).

Najpierw tworzymy z \(\varphi\) jej realtywizację \(\varphi_U\): kwantyfikatory \(\forall x\xi\) zastępujemy przez \(\forall x(U(x)\to\xi)\), a \(\exists x\xi\) przez \(\exists x(U(x)\land\xi)\). W razie gdyby w \(\varphi\) były symbole funkcyjne lub stałych, zastępujemy je uprzednio symbolami relacyjnymi w znany sposób.

Teraz żądane zdanie \(\psi\) wygląda tak:

\(\forall x (f(f(x))=x \land U(x)\leftrightarrow\lnot U(f(x)))\land \varphi_U\).

W tym zdaniu pierwsza częśc wyraża fakt, że \(f\) jest permutacją, ma cykle długości dwa i w każdym cyklu dokładnie jeden element należy do \(U\). Teraz \(\varphi_U\) orzeka, że podstruktura składająca się z elementów należących do \(U\) spełnia \(\varphi\), czyli liczba jej elementów należy do \(Spec(\varphi)\). Natomiast cały model ma dwa razy więcej elementów.

Zadanie 5 (20 punktów)
Gracz II ma strategię wygrywającą w grze Ehrenfeuchta-Fraissego o 4 rundach \(G_4(\mathfrak{A},\mathfrak{B})\), gdzie \(\mathfrak{A}\) jest poniższym grafem nieskierowanym:

    *        *        *    
    |        |        |    
 *--*--*  *--*--*  *--*--*

zaś \(\mathfrak{B}\) jest grafem nieskierowanym mającym \(n\) wierzchołków.
Ile krawędzi może mieć graf \(\mathfrak{B}\)?

Szkic rozwiązania

Skoro gracz II wygrywa grę \(G_4(\mathfrak{A},\mathfrak{B})\), to \(\mathfrak{A}\equiv_4\mathfrak{B}\). Poniżej wypisane są zdania o randze kwantyfikatorowej nie przekraczającej 4, które są prawdziwe w \(\mathfrak{A}\), zatem muszą być także prawdziwe w \(\mathfrak{B}\).

\(\exists x_1\exists x_2\exists x_3(\bigwedge_{i\le j}x_i\neq x_j\land\forall y(E(x_1,y)\lor E(x_2,y)\lor E(x_3,y)\lor x_1=y\lor x_2=y\lor x_3=y))\)
zatem są trzy wierzchołki w \(\mathfrak{B}\) takie, że każdy inny wierzchołek jest incydentny do jednego z nich...

\(\lnot\exists x_1\exists x_2(\bigwedge_{i\le j}x_i\neq x_j\land\forall y(E(x_1,y)\lor E(x_2,y)\lor x_1=y\lor x_2=y))\)

... ale nie ma dwóch takich wierzchołków. Zatem \(\mathfrak{B}\) składa się z trzech "centralnych" wierzchołków i połączonych z nimi w gwiazdę pozostałych wierzchołków, z ew. dodatkowymi krawędziami.

\(\lnot\exists x_1\exists x_2\exists x_3(\bigwedge_{i\le j}x_i\neq x_j\land E(x_1,x_2)\land E(x_2,x_3)\land E(x_3,x_1))\)
czyli nie ma trójkąta. Zatem wierzchołki będące promieniami tej samej gwiazdy są ze sobą niepołączone.

\(\lnot\exists x_1\exists x_2\exists x_3\exists x_4(\bigwedge_{i\le j}x_i\neq x_j\land E(x_1,x_2)\land E(x_2,x_3)\land E(x_3,x_4))\)
czyli nie ma ścieżek z trzech krawędzi. Zatem wierzchołki będące promieniami różnych gwiazd są ze sobą niepołączone krawędziami.

\(\forall x \exists y E(x,y)\)
czyli nie ma izolowanych wierzchołków...

\(\forall x \forall y (E(x,y)\to\exists z (z\neq x\land z\neq y\land (E(z,y)\lor E(z,x))\)
ani izolowanych krawędzi...

\(\forall x_1\forall x_2\forall x_3((\bigwedge_{i\le j}x_i\neq x_j\land E(x_1,x_2)\land E(x_2,x_3))\to (\exists x_4\bigwedge_{i}x_i\neq x_4 \land E(x_2,x_4))\)
oraz nie ma wierzchołków stopnia 2. Zatem promienie różnych gwiazd nie są tożsame, bo dawałyby z innymi promieniami ścieżki długości 3, ani też centra gwiazd nie sa połączone ze sobą ani z promieniami gwiazd innych niż własna.

Zatem \(\mathfrak{B}\) jest sumą trzech rozłącznych gwiazd, mających w sumie \(n\) wierzchołków. Na podstawie danych o grze nie da się dokładnie wyznaczyć rozkładu liczb promieni w gwiazdach, ale na pewno można powiedzieć, że wszystkich krawędzi jest \(n-3\).