Kolokwium 2013/2014

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\)