Egzamin 2015/2016 | Informatyka MIMUW

Dla danego zdania \(\varphi\) logiki pierwszego lub drugiego rzędu jego spektrum to zbiór
\(spec(\varphi)=\{n\in\mathbb{N}~|\) istnieje model \(\varphi\) mocy \(n\}.\)

Zadanie 1 (10 punktów)
Napisz formułę \(\varphi(x,y)\) w języku arytmetyki, dla której zachodzi

\((\mathbb{N},x:n,y:m) \models \varphi(x,y)\) wtedy i tylko wtedy, gdy \(m=\sum_{i=1}^n i^n\)

Szkic rozwiązania

Zadanie 2 (10 punktów)

Graf \(\mathfrak{G}\) (gotyckie G) (nad sygnaturą złożoną z jednego dwuargumentowego symbolu relacyjnego \(E\)) jest przedstawiony na poniższym rysunku (ma 5 wierzchołków i 8 krawędzi):

*---*
|\ /|
| * |
|/ \|
*---*

Udowodnij, że każdy graf \(\mathfrak{H}\) (gotyckie H) taki, że \(\mathfrak{H}\equiv_3\mathfrak{G}\), ma nieparzystą liczbę wierzchołków większą od 3.

Szkic rozwiązania

Wygodnie jest się posłużyć grą Ehrenfeuchta-Fraisse o 3 rundach. Zauważmy, że ta gra między dwoma grafami jest identyczna jak gra rozgrywana między dopełnieniami tych grafów (w dopełnieniach krawędzie są dokładnie tam, gdzie ich w oryginalnych grafach nie ma). Istotnie, częściowe izomorfizmy w obu przypadkach są te same, więc i strategie graczy są identyczne.

Dopełnienie \(\mathfrak{G}\) to

*   *   *
|   |
*   *

W tym momencie jest jasne, że dopełnienie dowolnego grafu \(\mathfrak{H}\) spełniającego \(\mathfrak{H}\equiv_3\mathfrak{G}\) musi składać się z izolowanego wierzchołka i pewnej liczby (ale co najmniej dwóch) izolowanych krawędzi. Z tej obserwacji wynika teza.

Zadanie 3 (10 punktów)

Udowodnij, że dla każdej klasy \(\mathcal{A}\) skończonych grafów, która jest zamknięta na izomorfizmy, istnieje
zbiór \(\Delta\) zdań logiki pierwszego rzędu taki, że dla każdego skończonego grafu \(\mathfrak{A}\) zachodzi
równoważność: \(\mathfrak{A}\in\mathcal{A}\) wtedy i tylko wtedy, gdy \(\mathfrak{A}\models\Delta\). Czy i jakie modele
nieskończone ma \(\Delta\) jest tu bez znaczenia.

Szkic rozwiązania

Dla każdego skończonego grafu \(\mathfrak{A}\) można napisać zdanie \(\varphi_{\mathfrak{A}}\), które jest prawdziwe dokładnie w tych grafach, które są izomorficzne do \(\mathfrak{A}\) i fałszywe we wszystkich pozostałych.

Wówczas żądany zbiór zdań to
\(\Delta=\{\lnot\varphi_{\mathfrak{A}}~|~\mathfrak{A}\not\in\mathcal{A}\}\).

Istotnie, wszystkie zdania z \(\Delta\) są prawdziwe w pewnym grafie wtedy i tylko wtedy, gdy nie jest on izomorficzny do żadnego grafu nienależącego do \(\mathcal{A}\), czyli sam należy do \(\mathcal{A}\).

Zadanie 4 (10 punktów)

Napisać zdanie \(\varphi\) logiki ESO, które jest prawdziwe w grafie \(G\) wtedy i tylko wtedy, gdy \(G\) ma pokrycie wierzchołkowe zawierające nie więcej niż połowę wierzchołków.

Logika ESO to egzystencjalny fragment logiki drugiego rzędu (SO) - logika ta zwiera formuły postaci
\(\exists_{R_1}\ldots\exists_{R_n}\ \varphi\), gdzie podane kwantyfikatory to kwantyfikatory drugiego rzędu, a \(\varphi\) jest formułą pierwszego rzędu.

Zbiór wierzchołków jest pokryciem wierzchołkowym, jeśli zawiera przynajmniej jeden koniec każdej krawędzi grafu.

Szkic rozwiązania

TEST

1.
Czy klasa grafów dwudzielnych jest definiowalna (wśród grafów skończonych) zdaniem logiki pierwszego
rzędu (nad sygnaturą zawierającą wyłącznie binarny symbol relacyjny \(E\))?

Szkic rozwiązania

Przypuśćmy, że takie zdanie istnieje i ma rangę kwantyfikatorową \(n\). Wówczas rozważamy dwa cykle, jeden mocy parzystej a drugi nieparzystej, odpowiednio duże (większe, niż \(2^n\)). Jeden z nich jest dwudzielny, drugi nie, a zdaniem o randze kwantyfikatorowej \(n\) nie da się ich rozróżnić.

2.
Czy \(\langle\mathbb{R},\oplus\rangle\equiv\langle\mathbb{R_+},\oplus\rangle\)? W pierwszej strukturze interpretacja dwuargumentowego symbolu funkcyjnego \(\oplus\) to naturalne dodawanie, a w drugiej naturalne mnożenie, \(\equiv\) oznacza elementarną równoważność.

Szkic rozwiązania

Tak - te dwie struktury są nawet izomorficzne. Izomorfizmem jest funkcja wykładnicza \(\lambda x.a^x\), dla dowolnego \(a>0\).

3.
Czy dla danych zdań \(\varphi\), \(\psi\) logiki pierwszego rzędu zawsze istnieje zdanie logiki pierwszego rzędu \(\xi\) (nad dowolną sygnaturą) takie, że \(spec(\xi)=spec(\varphi)\cap spec(\psi)\)?

Szkic rozwiązania

Tak. Niech \(\varphi'\) to będzie zdanie otrzymane z \(\varphi\) przez taką zamianę nazw symboli funkcyjnych i relacyjnych, żeby \(\varphi'\) i \(\psi\) nie miały żadnych wspólnych elementów sygnatury. Wówczas można przyjąć za \(\xi\) zdanie \(\varphi'\land\psi\).

4.
Niech \(\mathbb{R}\) to liczby rzeczywiste z dodawaniem i mnożeniem. Niech \(\Delta\) będzie zbiorem zdań prawdziwych w
\(\mathbb{R}\). Czy \(\Delta\) ma model przeliczalny?

Szkic rozwiązania

Tak - na mocy tw. Skolema-Loewenheima.

5.
Niech \(R\) będzie relacją binarną na elementach dziedziny aktywnej. Czy domknięcie przechodnie relacji \(R\) można zdefiniować wyrażeniem algebry relacji?

Szkic rozwiązania

Nie - nie da się tego zrobić w logice pierwszego rzędu, więc w równoważnej jej (tw. Codda) algebrze relacyjnej też nie.