Egzamin 2013/2014 | Informatyka MIMUW

Zadanie 1 (10 punktów) Dana jest struktura

$\mathfrak{A}=\langle \{a,b\}^*,\cdot,a,b,\varepsilon\rangle$ słów nad alfabetem

$\{a,b\}$ z operacją konkatenacji oraz słowami jednoliterowymi

$a$ i

$b$ i słowem pustym jako stałymi. Udowodnij, że dla każdego regularnego języka

$L\subseteq\{a,b\}^*$ istnieje formuła

$\varphi(x)$ logiki MSO z jedną zmienną wolną

$x$ taka, że

$L=\{w~|~(\mathfrak{A},x:w)\models\varphi\}.$

Szkic rozwiązania

Tłumaczymy dane wyrażenie regularne

$r$ na zdanie MSO.
Dla

$r=a$ and

$r=b$ teza jest oczywista.
Dla

$r=s\cup t$ używamy

$\varphi_s\lor \varphi_t.$
Dla

$r=st$ używamy

$\exists y\exists z (x=yz\land \varphi_s(y)\land\varphi_t(z)).$
Dla

$r=s^*$ musimy użyć kwantyfikatora po zbiorach:
Nieformalnie, wyrażamy
"

$\exists X$ (

$X$ jest minimalnym zbiorem takim, że

$((\varepsilon\in X\land\forall y \forall z (y\in X\land \varphi_s(z)\to yz\in X))\land x\in X$ ".

Zadanie 2 (10 punktów)
Relacja $E\subseteq A\times A$ ma własność Churcha-Rossera jeśli dla każdych $a,b,c$ takich, że istnieją ścieżki od $a$ do $b$ i od $a$ do $c,$ istnieje $d$ , osiągalne ścieżkami zarówno z $b$ jak i z $c$ . (Takie relacje są istotne w badaniach rachunku $\lambda.$ )

Udowodnij, że nie istnieje zbiór zdań logiki pierwszego rzędu $\Delta$ taki, że $\langle A,E\rangle\models\Delta$ wtedy i tylko wtedy, gdy relacja $E$ ma własność Churcha-Rossera.

Szkic rozwiązania

Rozwiązanie 1. Gra Ehrenfeuchta-Fraisse.
Gramy na dwóch strukturach

  *        *-*       *-*-*
 / \      /   \     /     \
*   *    *     *   *       *   ...
 \ /      \   /     \     /
  *        *-*       *-*-*

  *        *-*       *-*-*                  *-*-*-*-*...
 / \      /   \     /     \                /     
*   *    *     *   *       *   ...        *
 \ /      \   /     \     /                \
  *        *-*       *-*-*                  *-*-*-*-*...

w kórych wszystkie krawędzie są skierowane na prawo. Górna struktura ma własność Churcha-Rossera, dolna nie.

Gracz II ma strategię wygrywającą w grze o dowolnej liczbie rund. Ruchy gracza I w nieskończonym komponencie w dolnej strukturze naśladuje w dostatecznie dużym komponencie struktury górnej.

Rozwiązanie 2. Twierdzenie o zwartości.

Załóżmy, że $\Delta$ jest aksjomatyzacją własności Churcha-Rossera.
Dodajemy do sygnatury trzy stałe $a,b,c$ oraz do $\Delta$ zdania $\{E(a,b),E(a,c),\varphi_n~|~n\in\mathbb{N}\}$ , gdzie $\varphi_n$ mówi, że nie istnieje $d$ , które jest z $b$ i $c$ osiągalne w odelgłości mniej niż $n$ krawędzi. W ten sposób dostajemy $\bar\Delta$ .

Każdy skończony podzbiór $\bar\Delta$ jest spełnialny: wystarczy w górnej strukturze użytej w rozwiązaniu za pomocą gry stałe $a,b,c$ zinterpretować jako trzy pierwsze od lewej wierzchołki składowej o wystrczająco dużej długości.

Z tw. o zwartości całe $\bar\Delta$ jest spełnialne. ale to sprzeczność: z $a$ można przejść do $b$ i $c$ , ale w żadnej skończonej liczbie kroków nie można od nich "zejść się" do wspólnego wiezchołka.

Zadanie 3 (10 punktów)
Słaba monadyczna logika drugiego rzędu (Weak Monadic Second Order Logic, w skrócie WMSO) ma tę samą składnię co logika MSO. Pod względem semantyki, kwantyfikatory po zbiorach/relacjach unarnych $\forall X$ i $\exists X$ znaczą odpowiednio dla każdego skończonego podzbioru uniwersum i istnieje skończony podzbiór uniwersum.

Udowodnić, że dla każdej formuły $\varphi(\vec{x})$ logiki WMSO nad sygnaturą arytmetyki (czyli bez wolnych zmiennych drugiego rzędu) istnieje formuła $\psi(\vec{x})$ logiki pierwszego rzędu nad sygnaturą arytmetyki taka, że $\mathfrak{N}\models\forall \vec{x}(\varphi(\vec{x})\leftrightarrow\psi(\vec{x})).$

Szkic rozwiązania

Każdy kwantyfikator drugiego rzędu

$\exists X$ zastępujemy przez

$\exists t_X\exists p_X\exists m_X$ . Intencja jest taka, że

$t_X$ i

$p_X$ kodują ciąg elementów tworzących zbiór

$X$ , a

$m_X$ jest jego długością. Wówczas każdą formułę atomową

$x\in X$ występującą w zasięgu tego kwantyfikatora zastępujemy przez

$\exists i( i\lt m_X \land\chi(t_X,p_X,i,x))$ .

Zadanie 4 (10 punktów)
Jednostronna gra Ehrenfeuchta-Fra\"{\i}ss\'e o $k$ rundach na strukturach $\mathfrak{A}_0$ i $\mathfrak{A}_1$ to zmodyfikowana gra standardowa, w której gracz I po wybraniu w pierwszej rundzie elementu struktury $\mathfrak{A}_i$ musi już do końca wybierać elementy $\mathfrak{A}_i$ , a gracz II odpowiada w standardowy sposób ciągle w $\mathfrak{A}_{1-i}$ .

Podać przykład dwóch struktur $\mathfrak{A}_0$ i $\mathfrak{A}_1$ takich, że gracz II ma dla każdego $k$ strategię wygrywającą w jednostronnej grze Ehrenfeuchta-Fra\"{\i}ss\'e o $k$ rundach na strukturach $\mathfrak{A}_0$ i $\mathfrak{A}_1$ , mimo tego, że dla pewnego $m$ gracz I ma strategię wygrywającą w standardowej grze Ehrenfeuchta-Fra\"{\i}ss\'e o $m$ rundach na strukturach $\mathfrak{A}_0$ i $\mathfrak{A}_1$ .

Rozwiązania będą oceniane także przez pryzmat osiągniętej wartości $m,$ maksimum można dostać tylko za $m=2.$

Szkic rozwiązania

Niech naszymi strukturami będą

$\langle\mathbb{Z},succ\rangle$ i

$\langle\mathbb{N},succ\rangle$ .

W zwykłej grze gracz I wygrywa w dwóch rundach: najpierw zaznacza 0 w $\mathbb{N}$ , a w drugiej rundzie zaznacza w $\mathbb{Z}$ poprzednik elementu wskazanego przez gracza II jako odpowiedź na 0.

Rozważmy teraz grę jednostronną o $m$ rundach.

Jeśli w pierwszej rundzie gracz I zagra w $\mathbb{N}$ , to gracz II ma oczywistą strategię polegającą na kopiowaniu w $\mathbb{Z}$ ruchów gracza I.

Jeśli w pierwszej rundzie gracz I zagra w $\mathbb{Z}$ , to gracz II musi odpowiedzieć daleko od 0 w $\mathbb{N}$ , przy czym daleko oznacza "dalej niż $2^m$ ". Dalej na ruchy gracza I na lewo od pierwszego wybranego punktu odpowiada w myśl strategii pozwalającej wygrać na łańcuchu o długości $2^m$ i łańcuchu o dowolnej większej długości. Ruchy gracza I na prawo od pierwszego wybranego punktu gracz II po prostu kopiuje.

TEST

Za każdą trafną odpowiedź przyznajemy 2 punkty, za każdą nietrafną -2 punkty. Brak odpowiedzi to 0 punktów.

1. Niech $\varphi$ będzie zdaniem logiki pierwszego rzędu i niech $\mathit{Spec}(\varphi)=\{n\in\mathbb{N}~|$ istnieje model $\mathfrak{A}$ mocy $n$ taki, że $\mathfrak{A}\models\varphi\}.$
Czy rozstrzygalny jest następujący problem decyzyjny: Dane: zdanie $\varphi$ logiki pierwszego rzędu; Pytanie: Czy $\mathit{Spec}(\varphi)=\emptyset$ ?

Szkic rozwiązania

NIE. Warunek

$\mathit{Spec}(\varphi)=\emptyset$ oznacza dokładnie to samo, co "

$\varphi$ nie ma żadnego skończonego modelu."
Ten ostatni problem jest nierozstrzygalny na mocy tw. Trachtenbrota.

2. Czy istnieje zbiór zdań logiki pierwszego rzędu nad skończoną sygnaturą, który ma skończone modele każdej mocy parzystej, ale nie ma modelu mocy $\mathfrak{c}$ ?

Szkic rozwiązania

NIE. Tak opisany zbiór musi mieć model nieskończony, co wynika z standardowego zastosowanie tw. o zwartości. Wówczas, na mocy tw. Skolema-Loewenheima, ma on także model mocy

$\mathfrak{c}$ .

3. Niech $\varphi$ będzie zdaniem logiki MSO nad sygnaturą modeli-słów i niech $\mathit{Spec}_0(\varphi)=\{n\in\mathbb{N}~|$ istnieje model-słowo $\mathfrak{A}(w)$ mocy $n$ taki, że $\mathfrak{A}(w)\models\varphi\}.$

Czy rozstrzygalny jest następujący problem decyzyjny: Dane: zdanie $\varphi$ logiki MSO nad sygnaturą modeli-słów; Pytanie: Czy $\mathit{Spec}_0(\varphi)=\emptyset$ ?

Szkic rozwiązania

TAK. Warunek

$\mathit{Spec}_0(\varphi)=\emptyset$ oznacza dokładnie to samo, co "

$\varphi$ nie ma żadnego modelu-słowa."

Wystarczy teraz, zgodnie z tw. Buechi-Elgota, przetłumaczyć zdanie MSO na równoważny automat, następnie go zdeterminizować i zminimalizowac. Jeśli wyjdzie jednoelementowy automat ze stanem nieakceptującym, to spektrum jest puste, w przeciwnym razie jest niepuste.

4. Czy $\langle\mathbb{Q},<\rangle\equiv\langle\mathbb{R},<\rangle$ ? (Porządek w obu strukturach jest naturalny.)

Szkic rozwiązania

TAK. Był sformułowany i udowodniony na wykładzie fakt, że każde dwa liniowe porządki gęste, bez elementu maksymalnego i bez minimalnego sa elementarnie rónoważne.

$\langle\mathbb{Q},<\rangle$ i

$\langle\mathbb{R},<\rangle$ spełniają te założenia.

5. Czy gracz II ma strategię wygrywającą w standardowej grze Ehrenfeuchta-Fraisse o dwóch rundach na następujących dwóch grafach nieskierowanych o 4 wierzchołkach:

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

Szkic rozwiązania

NIE. Gracz I może w pierwszym ruchu wybrać jeden z wierzchołków o stopniu 3 w drugim grafie. Jakkolwiek gracz II odpowie, gracz I w następnym ruchu wybiera w grafie pierwszym wierzchołek po przekątnej od tego wybranego w rundzie pierwszej, który jest z nim niepołączony krawędzią. Gracz II nie ma jak odpowiedzieć na to w grafie drugim.