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.