Informatyka MIMUW

1. Dla ustalonego \(k\in\mathbb{N},\) podać przykład zdania \(\varphi\) (sygnatura jest do wyboru i może zależeć od \(k\)) takiego, że dla każdego naturalnego \(n,\) \(\varphi\) ma dokładnie \({n \choose k}\) nieizomorficznych modeli mocy \(n.\)
2. Niech \(\mathcal{C}\) będzie klasą wszystkich grafów (nieskierowanych), skończonych i nieskończonych, których wszystkie składowe spójne są skończone. Udowodnić, że klasa \(\mathcal{C}\) nie jest definiowalna.
3. Niech \(\mathbb{N}\) będzie standardowym modelem arytmetyki, nad standardową sygnaturą, składającą się z symboli \(+,*,0,1,\leq.\)
   Napisać formułę \(\varphi(x,y,z)\) nad sygnaturą arytmetyki definiującą funkcję \(y=\lfloor\sqrt[z]{x}\rfloor,\) tzn. taką, że dla wszystkich wartościowań \(v:X\to\omega\)

   \(\mathbb{N}\models\varphi[v]\ \ \text{wtw}\ \ v(y)=\lfloor(v(x))^{{\frac{1}{v(z)}}}\rfloor.\)

4. Niech \(\mathbb{Z}_{n}=\langle\{ 0,1,\dots,n-1\},+^{{\mathbb{Z}_{n}}}\rangle,\) gdzie \(+\in\Sigma^{F}_{2}\), a \(+^{{\mathbb{Z}_{n}}}\) jest operacją dodawania modulo \(n.\)

   Ile jest różnych funkcji dwóch argumentów \(x\) i \(y\), definiowalnych za pomocą termów \(t(x,y)\) w algebrze \(\mathbb{Z}_{n}?\)

5. Niech \(FINSAT_{\Sigma}\) będzie zbiorem wszystkich tych zdań logiki pierwszego rzędu nad pewną skończoną sygnaturą \(\Sigma,\) które są spełnialne w pewnej skończonej strukturze nad \(\Sigma.\)

   Udowodnić, że zbiór \(FINSAT_{\Sigma}\) jest algorytmicznie generowalny.

6. Niech \(\Sigma\) będzie sygnaturą składającą się z jednego dwuargumentowego symbolu relacyjnego \(E.\)

   Niech \(\varphi\) będzie zdaniem \(\forall x\forall y\forall z[R(x,y)\land R(x,z))\to y=z],\) zaś \(\psi\) zdaniem \(\forall x\exists y[R(x,y)\land\forall z\,(R(x,z)\to y=z)].\) Rozstrzygnąć, czy \(\varphi\models\psi\) oraz czy \(\psi\models\varphi.\)

Czas na rozwiązanie zadań to 2 godziny 30 minut od chwili ich rozdania. Wolno używać dowolnych notatek i podręczników, natomiast nie wolno ściągać.
Z zadań należy wybrać dowolne trzy i je rozwiązać. Wszystkie zadania są oceniane w skali 0-1-2-3 punkty, przy czym ważne jest uzasadnienie odpowiedzi. Na piątkę trzeba 7 punktów (w tym 3 zadania na co najmniej 2 punkty), na czwórkę 5 punktów (w tym co najmniej 2 zadania na co najmniej 2 punkty), a na trójkę 3 punktów (w tym co najmniej 1 zadanie na co najmniej 2 punkty). Każdej osobie, która odda więcej niż trzy zadania, do wyniku zostaną policzone najsłabsze trzy spośród nich.
Można jednak oddać także czwarte zadanie, specjalnie oznaczone jako dodatkowe, którego wynik 3 pkt. będzie umożliwiał dostanie szóstki (oczywiście tylko tym, którzy z pozostałych trzech zadań dostali piątkę).
Każde zadanie proszę napisać na osobnej, podpisanej kartce.