Informatyka MIMUW

Zadanie 1
Napisz formułę pierwszego rzędu \(\varphi(x,y)\) z dwoma zmiennymi wolnymi \(x, y\) taką, że \((\mathfrak{G},x:a,y:b)\models\varphi\) wtedy i tylko wtedy, gdy \(a\) i \(b\) są przeciwległymi wierzchołkami jednego z oczek sześciokątnej siatki. Na przykład powinno to zachodzić dla \(x\) i \(y\) będacych dwoma kółkami, a nie powinno zachodzić dla żadnej z par zawierających gwiazdki.

Zadanie 2
Rozszerzamy sygnaturę grafów o dodatkowe symbole stałych \(\circ\) i \(\star\). Tworzymy dwie kopie \(\mathfrak{G}\), oznaczone \(\mathfrak{G}_1\) i \(\mathfrak{G}_2\), w których interpretacjami nowych symboli stałych są: w \(\mathfrak{G}_1\) czarne kółko i czarna gwiazdka; w \(\mathfrak{G}_2\) białe kółko i biała gwiazdka, w tej właśnie kolejności.

Proszę wskazać strategię dla gracza I w grze Ehrenfeuchta-Fra\"{\i}ss\'e \(G_2(\mathfrak{G}_1,\mathfrak{G}_2)\) oraz napisać zdanie o randze kwantyfikatorowej 2, rozróżniające te dwie struktury.

Zadanie 3
Pracujemy ze strukturami-słowami nad alfabetem \(\{a,b\}\), tj. mamy ustaloną sygnaturę \(\{\leq, a(\cdot), b(\cdot)\}\) i rozważamy jedynie skończone struktury, w których \(\leq\) jest interpretowany jako liniowy porządek, a \(a(\cdot)\) i \(b(\cdot)\) jako dwa rozłączne podzbiory w sumie dające całe uniwersum.

Czy język zdefiniowany zdaniem pełnej logiki drugiego rzędu

\(\exists R [\forall x\forall y (R(x,y)\to (R(y,x) \land (a(x)\leftrightarrow
b(y))))\land \forall x \exists! y R(x,y)]\)

jest definiowalny w logice MSO? (\(\exists!\) oznacza ``istnieje dokładnie jeden'' i jest skrótem znanej formuły pierwszego rzędu.)

Zadanie 4

Mamy dany skończony skierowany graf \(\mathfrak{H}=(\{1,\ldots,n\},E).\) Zakładamy, że zawiera on dla każdego wierzchołka \(i\) krawędź \((i,i)\in E\). Zakodowujemy go jako zbiór \(\Delta_\mathfrak{H}\) formuł klasycznej logiki zdaniowej: dla każdego wierzchołka \(i\in\{1,\ldots,n\}\) tworzymy zmienną zdaniową \(p_i\). Teraz kładziemy

\(\Delta_\mathfrak{H}=\{p_i\to p_j~|~(i,j)\in E\}.\)

Udowodnij, że \(\Delta_\mathfrak{H}\cup\{\lnot( p_i\leftrightarrow p_j)\}\) jest spełnialne wtedy i tylko wtedy, gdy \(i\) i \(j\) nie należą do tej samej silnej składowej \(\mathfrak{H}.\)

TEST

1.
Używamy grafu \(\mathfrak{G}\) z zadania 1. Czy istnieje formuła pierwszego rzędu \(\varphi(x,y)\) z dwoma zmiennymi wolnymi, która w \(\mathfrak{G}\) definiuje porządek liniowy?

Twierdzenie Klasa wszystkich relacji równoważności \(\sim\), których wszystkie klasy abstrakcji są skończone, nie jest aksjomatyzowalna żadnym zbiorem zdań logiki pierwszego rzędu.

Dowód: Przypuśćmy wbrew tezie, że \(\Delta\) jest taką aksjomatyzacją. Niech

\(\bar{\Delta}=\Delta\cup\{\exists x_1\ldots\exists x_n\bigwedge_{1\leq i < j\leq
n}(x_i\neq x_j \land x_i\sim x_j)~|~n\in\mathbb{N}\}.\)

Każdy skończony podzbiór \(\bar{\Delta}\) jest spełnialny, bo zawarte w nim skończenie wiele ``dodanych'' zdań nie wymaga istnienia nieskończonych klas abstrakcji. Zatem z Twierdzenia o zwartości cały \(\bar{\Delta}\) jest spełnialny. To prowadzi do sprzeczności, bo dołączone zdania wymagają istnienia nieskończonych klas abstrakcji, a \(\Delta\) zabrania ich istnienia.

Dane: Formuła bezkwantyfikatorowa \(\varphi(x)\) z jedną zmienną wolną, logiki pierwszego rzędu nad sygnaturą \(+,*,0,1\)

Pytanie: Czy istnieje \(a\in\mathbb{N}\) takie, że \((\langle \mathbb{N},+,*,0,1\rangle,x:a)\models\varphi\)?