Zadanie 1 (10 punktów) Rozważamy klasę grafów, czyli symetrycznych struktur (skończonych lub nieskończonych) bez pętli nad sygnaturą złożoną z jednego dwuargumentowego symbolu relacyjnego \(E.\) Graf \(\mathfrak{G}=\langle V,E\rangle\) jest dwudzielny gdy istnieją niepuste rozłączne podzbiory \(A,B\subseteq V\) takie, że \(E\subseteq (A\times B)\cup(B\times A)\).
Dla każdej z poniższych klas grafów
określ, czy jest ona
Zadanie 2 (10 punktów)
Relacja \(E\subseteq A\times A\) ma \textit{własność Churcha-Rossera} jeśli dla każdych \(a,b,c\) takich, że istnieją ścieżki od \(a\) do \(b\) i od \(a\) do \(c,\) istnieje \(d\), osiągalne ścieżkami zarówno z \(b\) jak i z \(c\). (Takie relacje są istotne w badaniach rachunku \(\lambda.\))
Udowodnij, że istnieje zdanie logiki MSO \(\varphi\) takie, że \(\langle A,E\rangle\models\varphi\) wtedy i tylko wtedy, gdy relacja \(E\) ma własność Churcha-Rossera.
Zadanie 3 (10 punktów)
Dla przypomnienia, spektrum \(\mathit{Spec}(\varphi)\) zdania \(\varphi\) to zbiór \(\{n\in\mathbb{N}~|\)istnieje model zdania \(\varphi\) mocy \(n\}.\)
Niech z zdaniu \(\varphi\) występują wyłącznie jednoragumentowe symbole relacyjne. Udowodnij, że \(\mathit{Spec}(\varphi)\) jest albo skończony, albo jego dopełnienie jest skończone.
Zadanie 4 (10 punktów)
Udowodnić, że struktury \(\langle\mathbb{Q}\times\mathbb{Z},\leq\rangle\) i \(\langle\mathbb{R}\times\mathbb{Z},\leq\rangle\), uporządkowane leksykograficznie z użyciem naturalnych porządków na \(\mathbb{Z}\), \(\mathbb{Q}\) i \(\mathbb{R},\) są elementarnie równoważne.
TEST
1.
Dana jest struktura \(\mathfrak{A}=\langle \{a,b\}^*,\cdot,a,b,\varepsilon\rangle\) słów nad alafabetem \(\{a,b\}\) z operacją konkatenacji oraz słowami jednoliterowymi \(a\) i \(b\) i słowem pustym jako stałymi. Czy istnieje formuła \(\varphi(x)\) logiki pierwszego rzędu z jedną zmienną wolną \(x\) taka, że język \(\{w~|~(\mathfrak{A},x:w)\models\varphi\}\) nie jest regularny?
2. Logikę \(L\) nazywamy \textit{monotoniczną}, jeśli z tego, że \(\Delta\models\varphi\) oraz \(\Gamma\supseteq\Delta\) wynika, że \(\Gamma\models\varphi.\)
Dla logiki trójwartościowej Sobocińskiego określamy, że \(\Delta\models\varphi\), gdy dla każdego wartościowania zmiennych zdaniowych wartościami ze zbioru \(\{0,\frac12,1\}\), jeśli wartości wszystkich zdań z \(\Delta\) wynoszą 1, to także wartość \(\varphi\) wynosi 1.
Czy logika trójwartościowa Sobocińskiego jest monotoniczna?
3. Czy gracz II ma strategię wygrywającą w standardowej grze Ehrenfeuchta-Fraisse o 4 rundach na następujących dwóch grafach nieskierowanych o 10 wierzchołkach:
* *
| |
* - * - * * - * - *
|
*
* *
| |
* - * - * * - * - *
/ \ |
* * *4. Czy sekwent \(\{p,q\to p,\lnot q\}\vdash\{p,q\}\) jest dowodliwy w systemie Gentzena dla logiki zdaniowej?
5. Czy sekwent \(\vdash(\forall x P(x) \to \exists y \forall z R(y, z) ) \to \exists x \forall z (\lnot P(x) \lor R(x, z))\) jest dowodliwy w systemie Hilberta dla logiki pierwszego rzędu?