Egzamin poprawkowy 2011/2012

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.

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

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.

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

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}\)?