Informatyka MIMUW

1. Udowodnij, że jeżeli przekształcenia \(h:\mathbb{A}\to\mathbb{B}\) i \(g:\mathbb{B}\to\mathbb{A}\) są różnowartościowymi homomorfizmami grafów, to \(\mathbb{A}\cong\mathbb{B}.\)
2. Niech \(\varphi _{0}\equiv\exists x\exists yx\neq y,\) \(\varphi _{1}\equiv\forall x\lnot E(x,x)\), \(\varphi _{2}\equiv\forall x\forall y(E(x,y)\to E(y,x)),\) \(\varphi _{3}\equiv\forall x\forall y(x\neq y)\to\exists z(E(x,z)\land E(y,z)).\)

   Udowodnić, że \(\{\varphi _{)},\varphi _{1},\varphi _{2},\varphi _{3}\}\models\exists x\exists y\exists z(E(x,y)\land E(x,z)\land E(z,y)).\)

3. Udowodnij, że klasa \(\mathcal{A}\) złożona z wszystkich (być może nieskończonych) grafów regularnych, tj., grafów których wszystkie wierzchołki mają ten sam stopień, nie jest definiowalna.
4. Niech \(\Sigma\) będzie zwykłą sygnaturą ciał, wzbogaconą o jeden jednoargumentowy symbol funkcyjny \(f.\) Rozpatrujemy struktury postaci \(\mathbb{R}_{f}=\langle R,+^{\mathbb{R}},*^{\mathbb{R}},-^{\mathbb{R}},0^{\mathbb{R}},1^{\mathbb{R}},f\rangle,\) gdzie \(R\) to zbiór liczb rzeczywistych, wszystkie operacje mają zwykłe interpretacje, zaś \(f:R\to R\) jest dowolną funkcją.

   Napisać zdanie pierwszego rzędu \(\varphi\) nad \(\Sigma\) takie, że \(\mathbb{R}_{f}\models\varphi\) wtw \(f\) jest funkcją różniczkowalą w \(0.\)

Czas na rozwiązanie zadań to 90 minut od chwili ich rozdania. Wolno używać dowolnych notatek i podręczników, natomiast nie wolno ściągać. Osoby złapane na ściąganiu (także na etapie sprawdzania prac) będziemy karać.
Wszystkie zadania są oceniane w skali 0-1-2-3 punkty, przy czym ważne jest uzasadnienie odpowiedzi. Do zaliczenia potrzeba 5 punktów (w tym 2 zadania na co najmniej 2 punkty). Każdej osobie, kóra odda więcej niż trzy zadania, do wyniku zostaną policzone najsłabsze cztery spośród nich, tak więc nie opłaca się oddawać więcej niż trzech zadań.
Każde zadanie proszę napisać na osobnej kartce, podpisanej imieniem, nazwiskiem i adresem poczty elektronicznej, pod który ma być wysłany wynik.