Informatyka MIMUW

Zad. 1 (3 punkty)

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

Napisać zdanie $\varphi$ logiki drugiego rzędu postaci $\exists R_{1}\ldots\exists R_{k}\psi(R_{1},\ldots,R_{k}),$ w którym $\psi$ jest zdaniem pierwszego rzędu takie, że dla każdego skończonego grafu $\mathfrak{G}$ zachodzi równoważność: $\mathfrak{G}\models\varphi$ wtw $\mathfrak{G}$ ma cykl Eulera.

Zad. 2 (3 punkty)

Pokazać, że nie istnieje zdanie $\varphi$ logiki pierwszego rzędu o tej własności, że dla każdego skończonego grafu $\mathfrak{G}$ zachodzi równoważność: $\mathfrak{G}\models\varphi$ wtw $\mathfrak{G}$ ma cykl Eulera.

Zad. 3 (3 punkty)

Niech $k\in\mathbb{N}$ będzie stałą. Wykazać, że jeśli $E$ jest wyrażeniem algebry relacyjnej i maksymalna liczba kolumn w podwyrażeniach $E$ wynosi $k$, to istnieje algorytm obliczający wartość $[\![E]\!]$ w każdej strukturze $\mathfrak{A}$ i działający w czasie $O(n^{k}\log n),$ gdzie $n$ to liczność dziedziny aktywnej $\mathfrak{A}$.

Przy projektowaniu algorytmu należy założyć, że dziedzina aktywna składa się z liczb całkowitych typu integer, a do dyspozycji są jednowymiarowe tablice indeksowane nieujemnymi liczbami całkowitymi i zawierające takież liczby. Dostęp do komórki tablicy jest wykonywany w czasie jednostkowym, podobnie jak operacje arytmetyczne i porównania na liczbach całkowitych. Relacje z $\mathfrak{A}$ są przekazywane do algorytmu właśnie w takich tablicach: relacja o $l$ kolumnach jest reprezentowana przez $l$ tablic, a dane zajmują początkowe indeksy. Wynik obliczenia zwraca się analogicznie.

Zad. 4 (3 punkty)

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$.

Zad. 5 (3 punkty)

Sygnatura składa się z dwuargumentowego symbolu funkcyjnego $\circ$, jednoargumentowego symbolu funkcyjnego $inv$ i symbolu stałej $id$. Model $\mathfrak{F}$ (ta litera to gotyckie F, w rozwiązaniu można pisać zwykłe F) nad tą sygnaturą nazywamy grupą bijekcji, gdy jego uniwersum stanowi zbiór wszystkich bijekcji $f:A\to A$ dla pewnego zbioru $A,$ a operacje mają następujące interpretacje: $\circ^{\mathfrak{F}}$ to operacja składania funkcji, $inv^{\mathfrak{F}}$ to operacja brania funkcji odwrotnej, a $id^{\mathfrak{F}}$ to fukcja indentycznościowa z $A$ w $A$.

Udowodnić, że nie istnieje zbiór $\Gamma$ zdań logiki pierwszego rzędu taki, że $\mathfrak{B}\models\Gamma$ wtedy i tylko wtedy, gdy $\mathfrak{B}$ jest izomorficzny do pewnej grupy bijekcji.