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