Egzamin 2014/2015 | Informatyka MIMUW

Zadanie 1 (10 punktów)
Słowo \(w \in \{0,1\}^+\) nazwiemy cyklicznym jeśli istnieje słowo \(v\), takie że \(w=v^nu\), gdzie \(u\) jest prefiksem \(v\) i \(n\geq 2\). Niech \(\Sigma=\{\leq, X\}\) i rozważmy zbiór modeli-słów nad \(\Sigma\). Napisz zdanie \(\varphi\) pełnej logiki drugiego rzędu SO, które jest prawdziwe dokładnie w tych modelach-słowach które odpowiadają słowom cyklicznym.

Rozwiązanie

Używamy oczywistych skrótów \(y=S(x)\) na to, że "y jest następnikiem x", oraz \(\exists!\) na "istnieje dokładnie jedno".
\(\exists F\)
\(\forall x\exists!y F(x,y)\) F jest częściową funkcją
\(\forall y\forall x\forall x'(F(x,y)\land F(x',y))\to x=x'\) F jest różnowartościowe
\(\forall x\forall y (x\leq x'\land \exists y F(x,y))\to(\exists y' F(x',y')\land y\leq y')\) F jest rosnące
\(\forall x\forall y\forall x'\forall y'((F(x,y)\land F(x',y'))\to (x'=s(x)\leftrightarrow y'=s(y))\) F zachwuje następniki.
\(\exists y\exists x (\forall z z\leq y)\land F(x,y)\) ostatni element jest wartością F.
Zatem F "przekopiowuje" pierwszy element na pewną pozycję (to będzie początek drugiej kopii \(v\)), a wszystkie dalsze po kolei za niego; na końcu słowa pewna liczba elementów nie ma określonej wartości F: dokładnie te nie mają wartości, dla których brakuje już miejsca na końcu słowa.
\(\forall y (\lnot\exists x F(x,y))\to\exists z F(y,z)\) Elementy na początku nie będące wartościami F same mają wartości - dzięki temu F przenosi pierwszą kopię \(v\) w całości.
\(\bigwedge_i\forall x\forall y(F(x,y)\to (X_i(x)\leftrightarrow X_i(y))\) literki są kopiowane wiernie.

Zadanie 2 (10 punktów)
Mówimy, że graf skończony \(\mathfrak{G}\) (gotyckie G) (nad sygnaturą złożoną z jednego dwuargumentowego symbolu relacyjnego \(E\) da się pokryć sumą rozłącznych krawędzi, gdy jest utworzony jako suma pewnej liczby rozłącznych wierzchołkowo krawędzi, z dodanymi w dowolny sposób dodatkowymi krawędziami pomiędzy już istniejącymi wierzchołkami.

Udowodnij, że nie istnieje zdanie \(\psi\) logiki pierwszego rzędu takie, że \(\mathfrak{G}\models\psi\) wtedy i tylko wtedy gdy \(\mathfrak{G}\) da się pokryć sumą rozłącznych krawędzi.

Rozwiązanie

Wystarczy dla każdego \(m\in\mathbb{N}\) wskazać dwa grafy \(\mathfrak{G}_1\) i \(\mathfrak{G}_2\), z których \(\mathfrak{G}_1\) da się pokryć sumą rozłącznych krawędzi, a \(\mathfrak{G}_2\) sie nie da, oraz \(\mathfrak{G}_1\equiv_m\mathfrak{G}_2\).

Niech \(\mathfrak{G}_1\) to ścieżka długości \(2^m\). Jej pokryciem są krawędzie między wierzchołkami \(2k+1\) a \(2k+2\), uzupełnione o krawędzie pomiędzy pozostałymi kolejnymi wierzchołkami, dotąd niepołącznymi.
Niech \(\mathfrak{G}_2\) to ścieżka długości \(2^m+1\). Jej pokrycie nie istnieje, bo każdy graf dający się pokryć rozłącznymi krawędziami musi mieć parzystą liczbę wierzchołków.
To, że \(\mathfrak{G}_1\equiv_m\mathfrak{G}_2\) było udowodnione na wykładzie.

Zadanie 3 (10 punktów)
Proszę napisać zdanie logiki pierwszego rzędu nad sygnaturą arytmetyki, które jest prawdziwe w standardowym modelu arytmetyki wtedy i tylko wtedy, gdy dla każdego dodatniego \(n\in\mathbb{N}\) istnieje dodatnie rozwiązanie równania \(x^n+y^n+z^n=t^n\) złożone z liczb naturalnych.

Rozwiązanie

Niech \(Pow(a,n,b)\) wyraża za pomocą formuły \(\chi\) definiującej funkcję \(\beta\) Goedla, że \(a^n=b\) w następujący sposób:
\(\exists t(\chi(t,0,1)\land \forall i((0\leq i < n)\to\exists y(\chi(t,i,y)\land\chi(t,i+1,y\cdot a)))\land \chi(t,n,b)\).

Wówczas żądane zdanie ma postać
\(\forall n (n>0\to(\exists x\exists y\exists z\exists t\exists x'\exists y'\exists z'\exists t'\)
\(x>0\lor y>0\lor z>0\lor t>0\land Pow(x,n,x')\land Pow(y,n,y')\land Pow(z,n,z')\land Pow(t,n,t')\land\)
\(x'+y'+z'=t'\)

Zadanie 4 (10 punktów)
Skonstruuj ciąg formuł \((\varphi_n)_{n\in\mathbb{N}}\) klasycznej logiki zdaniowej, taki, że \(|\varphi_n|=O(n)\) i istnieje dokładnie \(n^2\) różnych wartościowań \(\varrho:FV(\varphi_n)\to\{0,1\}\), które spełniają \(\varphi_n\).

Rozwiązanie

Żądana formuła \(\varphi_n\) może mieć postać
\((p_1\to p_2)\land(p_2\to p_3)\land\ldots\land(p_{n-2}\to p_{n-1})\land\)
\((q_1\to q_2)\land(q_2\to q_3)\land\ldots\land(q_{n-1}\to q_{n-1})\).

Wartościowania spełniające całą formułę to dokładnie te, dla których ciąg wartości przypisanych zmiennym \(p_i\) jest niemalejący oraz ciąg wartości przypisanych zmiennym \(q_i\) jest niemalejący. Takich ciągów jest \(n^2\).

TEST

1. Czy istnieje formuła MSO definiująca własność opisaną w Zadaniu 1?

Rozwiązanie

Nie. Własność ta definiuje język nieregularny, a zatem, na mocy tw. Buechi-Elgota, nie może być wyrażona za pomocą zdania MSO.

2. Czy \(\langle\mathbb{Q},+,*\rangle\equiv\langle\mathbb{R},+,*\rangle\)? (Działania algebraiczne w obu strukturach są naturalne, \(\equiv\) oznacza elementarną równoważność.)

Rozwiązanie

Nie.
Zdanie \(\exists x((\forall y x*y=y)\land (\exists y y*y=x+x))\)
wyraża fakt istnienia liczby \(\sqrt{1+1}\), czyli jest prawdziwe w \(\langle\mathbb{R},+,*\rangle\) i fałszywe w \(\langle\mathbb{Q},+,*\rangle\). Zatem te dwie struktury nie są elementarnie równoważne.

3. Czy teoria pierwszego rzędu struktury \(\langle\mathbb{N},\leq\rangle\) (porządek jest naturalny) jest rozstrzygalna?

Rozwiązanie

Tak, rozstrzygalna jest nawet teoria MSO tej struktury, o czym mówi tw. Buechiego, podane na wykładzie.

4. Założeniem w jednej z implikacji twierdzenia Codda jest to, że uniwersum struktury (nad skończoną sygnaturą) jest równe jej dziedzinie aktywnej. Czy ta własność da się sformalizować zdaniem logiki pierwszego rzędu?

Rozwiązanie

Tak. W dowodzie tw. Codda na wykładzie pojawiło się wyrażenie \(AD\) opisujące dziedzinę aktywną. Zgodnie z tw. Codda, istnieje formuła pierwszego rzędu \(\varphi_{AD}(x)\) równoważna (bez żadnych warunków) temu wyrażeniu. Zatem żądane zadnie ma postać \(\forall x\varphi_{AD}(x)\).

5. Przypuśćmy, że \(\models\varphi\to\psi\), przy czym obie formuły logiki pierwszego rzędu nie zawierają kwantyfikatorów. Czy istnieje interpolant \(\xi\) spełniający \(\models\varphi\to\xi\) i \(\models\xi\to\psi,\) oraz \(FV(\xi)=FV(\varphi)\cap\ FV(\psi)\)?

Rozwiązanie

Tak. Gdyby nie było w formułach równości, to każda formuła atomowa \(R(x)\) zachowuje się jak zmienna zdaniowa, jej wartość logiczna może być ustalana niezależnie od innych formuł atomowych i istnienie interpolanta wynika z twierdzenia o interpolacji dla logiki zadaniowej (było na wykładzie). Jeśli równości i nierówności są, to do formuł należy dopisac równoważności formuł atomowych wynikające z równości między zmiennymi i dopiero wytworzyć interpolanta.