Kolokwium 2014/2015 | Informatyka MIMUW

Zadanie 1

Rozważamy klasę \(\mathcal{A}\) wszystkich grafów \(\mathfrak{G}\) (gotyckie G), skończonych i nieskończonych, których wierzchołki można pokolorować pewną skończoną liczbą kolorów tak, że każdy trójkąt zawarty w \(\mathfrak{G}\) ma wierzchołki 3 różnych kolorów.

Udowodnij że \(\mathcal{A}\) nie jest aksjomatyzowalne żadnym zbiorem zdań logiki pierwszego rzędu nad sygnaturą składającą się wyłącznie z relacji krawędzi \(E\).

Szkic rozwiązania

Ogólna uwaga: Każda klika musi być pokolorowana tyloma kolorami ile ma elementów, żeby każdy trójkąt w niej zawarty był trójkolorowy.

Rozwiązanie I.

Przypuśćmy,że \(\Delta\) to żądana aksjomatyzacja. Niech

\(\bar\Delta=\Delta\cup\{\exists x_1\ldots\exists
x_n\bigwedge_{i,j}E(x_i,x_j)\}\).

Pokazujemy, że \(\bar\Delta\) spełnia założenia twierdzenia o zwartości: niech \(\Delta_0\subseteq\bar\Delta\) będzie dowolny, skończony.
Niech \(N\) to maksymalna liczna kwantyfikatorów w zdaniach z \(\Delta_0\) pochodzących spoza \(\Delta\). Wówczas klika mocy \(N\) spełnia \(\Delta_0\), bo daje się pokolorować skończoną liczbą kolorów bez powtarzania kolorów.

Na mocy twierdzenia o zwartości \(\bar\Delta\) ma model. Zawiera on kliki każdej skończonej mocy, więc żadna skończona liczba kolorów nie wystarcza do odpowiedniego pokolorowania modelu \(\bar\Delta\). Sprzeczność.

Rozwiązanie II.

Niech \(\mathfrak{A}\) to struktura składająca się z przeliczalnie wielu przeliczalnych klik jako składowych spójnych.

Pokazujemy, że dla każdego \(m\) istnieje struktura \(\mathfrak{B}\in\mathcal{A}\) taka, że dla każdego \(m\) istnieje struktura \(\mathfrak{B}_m\) tkaza, że gracz II ma strategię w grze Ehrenfeuchta-Fraisse o \(m\) rundach, granej na \(\mathfrak{A}\) i \(\mathfrak{B}_m\).

\(\mathfrak{B}_m\) to struktura składająca się z przeliczalnie wielu klik mocy \(m\) jako składowych spójnych.

Strategia gracza II jest banalna. Jej istnienie wskazuje, że nie istnieje zdanie o randze kwantyfikatorowej \(m\) lub mniejszej, które byłoby fałszywe w \(\mathfrak{A}\) a jednocześnie prawdziwe w każdej strukturze z \(\mathcal{A}\).

Zadanie 2

Niech dane będą dwa grafy: \(\mathfrak{G}\) (gotyckie G) będący szkieletem sześcianu (8 wierzchołków, 12 krawędzi) i \(\mathfrak{H}\) (gotyckie H) będący kopią \(\mathfrak{G}\) pozbawioną jednej krawędzi.

Napisz zdanie o minimalnym zagnieżdżeniu kwantyfikatorów, rozróżniające \(\mathfrak{G}\) i \(\mathfrak{H}\). Uzasadnij poprawność zdania, nie uzasadniaj minimalności zagnieżdżenia.

Szkic rozwiązania

Strategia gracza I na trzy rundy:

1. Jeden z wierzchołków o stopniu 2 w \(\mathfrak{H}\).
Odpowiedź gracza II dowolna.

2. Wierzchołek w \(\mathfrak{G}\) po przeciwnej stronie długiej przekątnej od wierzchołka wybranego przez II w poprzedniej rundzie.
Odpowiedź gracza II dowolna.

3. W \(\mathfrak{H}\) pierwszy wybrany wierzchołek ma stopień 2, drugi wybrany wierzchołek ma stopień najwyżej 3. Łącznie wybranych i incydentnych do wybranych jest co najwyżej 7 wierzchołków, podczas gdy wszystkich wierzchołków jest 8. Gracz I wybiera teraz wierzchołek, który nie
był dotąd wybrany ani nie jest incydentny z żadnym z wybranych wierzchołków.
Gracz II nie ma odpowiedzi, bo w \(\mathfrak{G}\) wszystkie wierzchołki sa albo wybrane albo incydentne z jednym z wybranych.

Strategia ta przekłada się na zdanie
\(\forall x\exists y\forall z (z=x\lor z=y\lor E(z,x) \lor E(z,y)),\)
które jest prawdziwe w \(\mathfrak{G}\) i fałszywe w \(\mathfrak{H}\).

Zadanie 3

Rozstrzygnij, czy następująca formuła jest twierdzeniem logiki intuicjonistycznej:

\((p\to q)\to((r\to q)\to(r\to p)).\)

Szkic rozwiązania

To zdanie nie jest nawet tautologią logiki klasycznej (wartościowanie \(r=1, p=0, q=1\)), więc tym bardziej nie jest twierdzeniem logiki intuicjonistycznej.