Informatyka MIMUW

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

1. grafy dwudzielne
2. grafy nie-dwudzielne

określ, czy jest ona

1. aksjomatyzowalna jednym zdaniem logiki pierwszego rzędu
2. aksjomatyzowalna zbiorem zdań logiki pierwszego rzędu, ale nie pojedynczym zdaniem
3. nieaksjomatyzowalna żadnym zbiorem zdań logiki pierwszego rzędu

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?