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.