Egzamin po-poprawkowy 2010/2011 (dla osób z przedłużeniem sesji)

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