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 \(h:\mathbb{A}\to\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((x\neq y)\to\exists z(E(x,z)\land E(y,z))).\)

   Jaka jest najmniejsza możliwa liczba krawędzi w grafie \(\mathbb{A}=\langle A,E^{\mathbb{A}}\rangle,\) który jest modelem zbioru \(\{\varphi _{0},\varphi _{1},\varphi _{2}\}?\)

3. Klasa \(\mathcal{A}\) jest złożona z wszystkich częściowych porządków o tej własności, że żaden zawarty w nich skończony łańcuch nie jest maksymalny.

   Skonstruować zbiór zdań \(T\) nad zwykłą sygnaturą porządków \(\Sigma,\) 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, symbole \(+,*,-,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 dodatnim 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ęć).