Egzamin 2012/2013 | Informatyka MIMUW

Zadanie 1 (10 punktów) Niech sygnatura \(\Sigma\) składa
się tylko z symboli relacyjnych: dwuargumentowego \(E\) i
jednoargumentowego \(P.\) Dla każdej z podanych poniżej klas struktur
określ, czy jest ona (i) aksjomatyzowalna jednym zdaniem logiki
pierwszego rzędu, (ii) aksjomatyzowalna zbiorem zdań logiki pierwszego
rzędu, ale nie pojedynczym zdaniem, (iii) nieaksjomatyzowalna żadnym
zbiorem zdań pierwszego rzędu.

Klasa struktur \(\mathfrak{A}=(A, E^{\mathfrak{A}}, P^{\mathfrak{A}})\) nad sygnaturą \(\Sigma\), w
których \(E^{\mathfrak{A}}\) jest symetryczna i takich, że:

w każdej spójnej składowej \((A,E^{\mathfrak{A}})\) każdy wierzchołek
spełnia \(P^{\mathfrak{A}}\).
istnieje spójna składowa \((A,E^{\mathfrak{A}})\), w której pewien
wierzchołek spełnia \(P^{\mathfrak{A}}\).
istnieje spójna składowa \((A,E^{\mathfrak{A}})\), w której każdy
wierzchołek spełnia \(P^{\mathfrak{A}}\).

Uwaga: czwarty element tego zestawu jest pytaniem w teście, a trzy
powyższe podpunkty nie są mają równych wag w łącznej punktacji zadania.

Rozwiązanie

Aksjomatyzowalna zdaniem \(\forall x P(x)\)
Aksjomatyzowalna zdaniem \(\exists x P(x)\)
Nie jest aksjomatyzowalna żadnym zbiorem zdań. Wskażemy dwie elementarnie równoważne struktury, z których w jednej istnieje spójna składowa \((A,E^{\mathfrak{A}})\), w której każdy
wierzchołek spełnia \(P^{\mathfrak{A}}\), a w drugiej takiej składowej nie ma.

Poniżej * to element spełniający \(P^{\mathfrak{A}}\), a o to niespełniający.

Pierwsza struktura (ma taką składową):
```
   ...-*-*-*-*-...     ...-*-*-o-o-...   ...-o-o-o-o-...
```
Druga struktura (nie ma takiej składowej):
```
   ...-*-*-*-*-...     ...-*-*-o-o-o-o-o-o-o-o-o-o-...
```
Teraz ustalamy dowolne \(m\) i gramy w grę Ehrenfeuchta-Fraissego o \(m\) rundach na tych dwóch strukturach. Strategia II gracza to imitować w dolnej strukturze istnienie trzeciej, brakującej składowej za pomoca ruchów daleko od punktu przejścia *-o.

Zadanie 2 (10 punktów) Rozważmy strukturę
\(\mathfrak{R}=\langle\mathbb{R},+,*,0,1\rangle\), gdzie nośnik to zbiór
liczb rzeczywistych, ze standardową interpretacją symboli z
sygnatury. Napisz formułę \(\varphi(x)\) monadycznej logiki drugiego rzędu
MSO, z jedną zmienną wolną (pierwszego rzędu) taką, że

\((\mathfrak{R},x:a)\models\varphi~~\text{wtw}~~a\in\mathbb{Q}.\)

Rozwiązanie

Sednem rozwiązania jest odwołanie się do zbioru liczb całkowitych. Niech \(Cls(X)\) oznacza formułę

\(0\in X\land \forall n(n\in X\to (n+1)\in X\land \exists m (n=m+1\land m\in X))\)

Formuła ta oznacza, że \(X\) zawiera 0 i jest zamknięta na następnik i poprzednik. Jest wiele takich zbiorów, na przykład \(\mathbb{Z},\ \mathbb{R}\) i inne.

Teraz formuła

\(\exists X (Cls(X)\land(\forall Y Cls(Y)\to \forall u (u\in X\to u\in Y))\land (\exists p\exists q p\in X\land q\in X\land p\neq0\land x*q=p))\)

orzeka, że istnieje \(X\), który spełnia \(Cls(X)\), jest zawarty w każdym \(Y\) spełniającym \(Cls(Y)\) (czyli jest prawdziwym zbiorem liczb całkowitych) i \(x\) jest ilorazem dwóch elementów \(X\). Zatem właśnie tej formuły poszukiwaliśmy.

Alternatywnie można napisać

\(\forall X (Cls(X)\to (\exists p\exists q p\in X\land q\in X\land p\neq0\land x*q=p))\)

orzekając, że \(x\) jest można wyrazić jako iloraz dwóch elementów każdego zbioru spełniającego \(Cls(X)\), zatem także jako iloraz dwóch liczb całkowitych.

Zadanie 3 (10 punktów) Udowodnij, że dla każdego
\(n\)-argumentowego wyrażenia \(E\) algebry relacyjnej, dla dowolnych

\(1\leq i_1\le \cdots\le i_m\leq n\) i dla dowolnego ustalonego
\(k\in\mathbb{N}\), wyrażenie

\(
{\tt group}\ E\ {\tt by}\ i_1,\ldots, i_m\ {\tt having~count(*)}>k
\)
także jest definiowalne w algebrze relacyjnej.

Powyższe wyrażenie jest \(m\)-argumentowe, a jego semantyką jest
zdefiniowana przez:

\(\{ (a_{i_1},\ldots,a_{i_m}) \mid \text{istnieje \(>k\) krotek
\(\langle b_1,\ldots,b_n\rangle\in[\![E]\!]\) t. że}~a_{i_1}=b_{i_1},\ldots,a_{i_m}=b_{i_m} \}
\)

Zadanie 4 (10 punktów) Rozważamy monadyczną logikę drugiego
rzędu (MSO) nad skończonymi modelami-słowami.

Każdemu elementowi \(a\) uniwersum modelu-słowa można przypisać
liczbę \(\bar{a}\in\mathbb{N}\) równą jego pozycji w słowie (pozycje
numerujemy od \(1\)).

Udowodnij, że nie istnieje formuła \(\varphi(x,y,z)\) logiki MSO taka, że
dla każdego modelu-słowa \(\mathfrak{A}(w)\) i dowolnych \(a,b,c\in A\)

\(
(\mathfrak{A}(w),x:a,y:b,z:c)\models\varphi~~\text{wtw}~~\bar{a}+\bar{b}\equiv\bar{c} \pmod {|w|}.
\)

Rozwiązanie

Przypuśćmy, że takie \(\varphi\) istnieje. Dojdziemy do sprzeczności, pokazując, że wówczas w MSO można by było zdefiniować język nieregularny, wbrew tw. Buechi-Elgota.

Rozważmy formułę \(mid(z)\)

\(\exists x (\forall y y\leq x)\land (z\neq x \land \varphi(z,z,x))\)

która orzeka, że \(z\) jest położone w połowie długości danego słowa. Teraz

\(\exists z mid(z)\land \forall y (y\leq z\to X(y))\land(y>z\to \lnot X(y))\)

mówi, że istnieje \(z\) położony w połowie długości słowa, na lewo od niego \(X\) wszędzie zachodzi, na prawo \(X\) nigdzie nie zachodzi. Zatem to zdanie definiuje język typu \(\{a^nb^n~|~n\in\mathbb{N}\}\)
który jest oczywiście nieregularny.

TEST

Pytanie 1 (2 punkty) Niech dla zdania \(\varphi\) logiki pierwszego rzędu
\(
Spec(\varphi) = \{n\in\mathbb{N}^+ \mid \mbox{ istnieje \(\mathcal{A}\) o mocy \(n\) takie że } \mathcal{A}\models\varphi\}.
\)
Czy następujący problem jest rozstrzygalny:

Dane: zdanie \(\varphi\)

Pytanie: czy \(Spec(\varphi)\cup Spec(\neg\varphi)=\mathbb{N}_+\)?

Odpowiedź

TAK. Wypisana równość zachodzi zawsze, dla każdego zdania \(\varphi\).

Pytanie 2 (2 punkty) W sytuacji z Zadania 1, czy własność
w każdej spójnej składowej \((A,E^{\mathfrak{A}})\) istnieje wierzchołek
spełniający \(P^{\mathfrak{A}}\) jest aksjomatyzowalna zbiorem zdań logiki
pierwszego rzędu?

Odpowiedź

NIE.

Dowód przez tw. o zwartości. Załóżmy, że taki zbiór \(\Delta\) istnieje.

Niech zdanie \(away_k\) oznacza, że w odległości \(k\) od stałej \(c\) nie ma elementu spełniającego \(P\).
Można je napisać tak:

\(\forall x_1\ldots \forall x_k ((E(c,x_1)\land E(x_1,x_2)\land\ldots\land E(x_{n-1},x_n))\to(\bigwedge_{i=1}^k\lnot P(x_i))).\)

Rozważmy \(\bar{\Delta}=\Delta\cup\{away_k~|~k\in \mathbb{N}\}\).

Łatwo wykazać, że każdy skończony podzbiór \(\bar{\Delta}\), ma model, bo wystarczy brać grafy złożone z jednej składowej w postaci długiego łańcucha, gdzie \(c\) jest na jednym jego końcu, a drugi koniec spełnia \(P\).

Zatem z tw. o zwartości \(\bar{\Delta}\) ma model. Jednak w tym modelu składowa \(c\) nie zawiera żadnego elementu spełniającego \(P\) - sprzeczność.

Pytanie 3 (2 punkty) Czy gracz I ma strategię wygrywającą w grze
Ehrenrfeuchta-Fra\"{\i}ss\'e o 3 rundach na dwóch poniższych
nieskierowanych grafach 8-wierzchołkowych?
\[
\xymatrix@=10pt{
\bullet & & \bullet \\
\bullet\ar@{-}[u]\ar@{-}[d] & \bullet & \bullet\ar@{-}[u]\ar@{-}[d]\ar@{-}[l]\ar@{-}[r] & \bullet \\
\bullet & & \bullet
} \qquad \qquad
\xymatrix@=10pt{
\bullet & & \bullet \\
\bullet\ar@{-}[u]\ar@{-}[d]\ar@{-}[r] & \bullet & \bullet\ar@{-}[u]\ar@{-}[d]\ar@{-}[r] & \bullet \\
\bullet & & \bullet
}
\]

Pytanie 4 (2 punkty) Czy dla każdej formuły \(\varphi\) logiki
pierwszego rzędu istnieją: liczba naturalna \(k\), ciąg kwantyfikatorów
\(Q_1,\ldots,Q_k\in\{\forall,\exists\}\) i zmiennych \(x_1,\ldots, x_k\)
oraz formuła \(\psi\), w której nie występują kwantyfikatory, takie że
tautologią jest

\(
\varphi \leftrightarrow Q_1x_1\cdots Q_kx_k\psi \qquad ?
\)

Odpowiedź

TAK. Było na wykładzie.

Pytanie 5 (2 punkty) Czy w logice pierwszego rzędu istnieje
tautologia, która nie ma dowodu w systemie Hilberta?

Odpowiedź

NIE. Twierdzenie Goedla o pełności orzeka, że każda tautologia pierwszego rzędu ma dowód w systemie Hilberta.