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$?