Informatyka MIMUW

Zad. 1 (3 punkty)

Rozważamy skończone grafy nieskierowane $\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 relacyjnegoE.
Napisć zdanie logiki MSO postaci $\forall X_1\ldots\forall X_k\psi(X_1,\ldots,X_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}$ jest drzewem (nieskierowanym).

Zad. 2 (3 punkty)

Pokazć, że nie istnieje zdanie $\varphi$ logiki pierwszego rzędu o tej własności, że dla
każdego nieskierowanego (skończonego lub nie) grafu $\mathfrak{G}$ zachodzi równoważność:
$\mathfrak{G}\models\varphi$ wtw każdy wierzchołek $\mathfrak{G}$ należy do pewnego cyklu w tym grafie.

Zad. 3 (3 punkty)

Dane są dwie tabele $A$ i $B$ o dwóch kolumnach każda. Ta pierwsza składa się z $n_A$
wierszy.
Zaprojektowć algorytm wyliczenia wartości wyrażenia algebry relacyjnej

$A\setminus\pi_{12}(\sigma_{1=3}(A\times B))$.

Przy projektowaniu algorytmu należy założyć, że dziedzina aktywna składa się z liczb
całkowitych typu integer, a do dyspozycji są dwukolumnowe tablice, których wiersze
indeksowane są nieujemnymi liczbami całkowitymi i zawierają takież liczby.
W algorytmie należy użyć dokładnie jednej takiej tablicy o rozmiarze $n_A$ wierszy i
kilku dodatkowych zmiennych typu integer. Oznacza to,że wykorzystujemy dokładnie
tyle pamięci, ile zajmie wynik. Proszę nie używć wskaźników, rekursji i innych metod
ukrytego alokowania dodatkowej pamięci.

Tabele $A$ i $B$ są tylko do odczytu, przy czym można założyć, że są one posortowane.
Jeśli rozwiązanie będzie z tego korzystć, proszę o tym założeniu wspomnieć.

Zad. 4 (3 punkty)

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

Udowodnić, że dla każdego naturalnego $n$ istnieje formuła
$\varphi_n(x,y,z)$ logiki pierwszego rzędu, w której występują tylko trzy zmienne (które można rekwantyfikowć
tak często jak potrzeba), takie że dla każdego skończonego cyklu $\mathfrak{C}$ zachodzi równoważność:
$(\mathfrak{C}, x : a, y : b, z : c)\models\varphi_n(x,y,z)$ wtw $\mathfrak{C}$ ma $3n$ krawędzi, a skierowane
odległości z $a$ do $b$, z $b$ do $c$ i z $c$ do $a$ wszystkie wynoszą po $n$.

Zad. 5 (3 punkty)

Niech $\varphi$ będzie zdaniem $\forall x\forall y(y =f(g(x)) \to(\exists u(u=f(x)\land y =g(u))))$ oraz
niech $\psi$ będzie zdaniem
$\forall x[f(g(f(x))) =g(f(f(x)))]$. Czy $\{\psi\}\models\varphi$?