Informatyka MIMUW

Kolokwium z logiki dla informatyków 2013/2014

Zadanie 1 Rozważamy klasę $\mathcal{A}$ wszystkich struktur, które są izomorficzne do struktury postaci $\langle A^\mathbb{N},R\rangle$, gdzie $A$ jest dowolnym niepustym zbiorem, $A^\mathbb{N}$ jest zbiorem wszystkich nieskończonych ciągów elementów $A$, zaś $xRy$ zachodzi wtedy i tylko wtedy, gdy zbiór pozycji na których $x$ i $y$ się różnią, jest skończony.

Udowodnij że $\mathcal{A}$ nie jest akjomatyzowalne żadnym zbiorem zdań logiki pierwszego rzędu nad sygnaturą składającą się wyłącznie z $R$.

Zadanie 2 Niech struktura $\mathfrak{A}=\langle A,<^\mathfrak{A}\rangle$ będzie liniowym porządkiem na $A$ takim, że $\mathfrak{A}$ jest 2-elementarnie równoważne strukturze $\mathfrak{N}=\langle \mathbb{N}, <\rangle$. Czy z tego wynika, że

* $A$ jest nieskończone;
* $A$ ma element najmniejszy;
* Każdy element $A$ ma tylko skończenie wiele elementów mniejszych od siebie?

Odpowiedzi uzasadnij.

Zadanie 3 Rozstrzygnij, czy następujące formuły mają dowód w systemie Gentzena dla logiki zdaniowej:

* $(p\to q) \lor (q\to p)$
* $(p\to ( q \to p)) \to p$