Informatyka MIMUW

1. Skonstruuj przykłady dwóch nieizomorficznych nieskończonych grafów \(\mathbb{A}\) i \(\mathbb{B}\) takich, że istnieją różnowartościowe homomorfizmy grafów \(g:\mathbb{B} \to \mathbb{A}\) i \(\mathbb{A} \cong \mathbb{B}.\)

   Funkcja \(h:A\to\ B\) jest homomorfizmem grafów \(\mathbb{A}\) i \(\mathbb{B},\) gdy dla wszystkich \(a,a^{{\prime}}\in A\), \(\langle a,a^{{\prime}}\rangle\in E^{\mathbb{A}}\) implikuje \(\langle h(a),h(a^{{\prime}})\rangle\in E^{\mathbb{B}}\).

2. Niech \(\varphi _{0}\equiv\exists x\exists y(x\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 _{0},\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. Klasa \(\mathcal{A}\) jest złożona z wszystkich nieskierowanych grafów (skończonych lub nie) \(\mathbb{A}=\langle A,E^{\mathbb{A}}\rangle\) (nad sygnaturą składającą się z jednego dwuargumentowego symbolu relacyjnego \(E\)) o następującej własności: każda składowa spójna \(\mathbb{A}\) jest skończona.

   Udowodnić, że klasa \(\mathcal{A}\) nie jest aksjomatyzowalna, tj., że nie istnieje zbiór \(T\) zdań taki, że \(\mathcal{A}=Mod(T).\)

4. Niech \(\Sigma\) będzie zwykłą sygnaturą ciał z porządkiem, wzbogaconą o jeden jednoargumentowy symbol funkcyjny \(f.\) Rozpatrujemy struktury postaci

   \(\mathbb{A}=\langle R,+^{\mathbb{A}},*^{\mathbb{A}},-^{\mathbb{A}},0^{\mathbb{A}},1^{\mathbb{A}},\leq^{\mathbb{A}},f^{\mathbb{A}}\rangle,\)

   gdzie \(R\) to zbiór liczb rzeczywistych, \(+,*,-,0,1,\leq\) mają zwykłe interpretacje (takie, jak w liczbach rzeczywistych), zaś \(f^{\mathbb{A}}:R\to R\) jest dowolną funkcją.

   Napisać zdanie pierwszego rzędu \(\varphi\) nad \(\Sigma\) takie, że \(\mathbb{A}\models\varphi\) wtw \(f^{\mathbb{A}}\) jest funkcją okresową o najmniejszym okresie \(1.\)

Z powyższych zadań należy wybrać i rozwiązać dwa. 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ć. Wykryte przypadki ściągania (także na etapie sprawdzania prac) będziemy karać.
Zadania są oceniane w skali 0-1-2-3 punkty, przy czym ważne jest uzasadnienie odpowiedzi. Do zaliczenia potrzeba 4 punktów. Osobie, kóra odda więcej niż dwa zadania, do wyniku zostaną policzone najsłabsze dwa sposród nich, czyli nie opłaca się oddawać więcej niż dwóch zadań.
Każde zadanie proszę napisać na osobnej kartce, podpisanej imieniem, nazwiskiem, grupą (nazwisko prowadzącego i termin zajęć) i adresem poczty elektronicznej, na który ma być wysłany wynik kolokwium.