Kolokwium 2016/2017

Zadanie 1
Częściowy porządek \(\mathfrak{A}=\langle A,\leq\rangle\) należy do klasy \(\mathcal{A}\) wtedy i tylko wtedy, gdy:

(a) zawiera nieskończenie wiele elementów minimalnych;

(b) każdy nie-minimalny element \(a\in A\) jest supremum pewnego skończonego zbioru elementów minimalnych w \(\mathfrak{A}\).

Czy klasa \(\mathcal{A}\) jest aksjomatyzowalna jednym zdaniem, aksjomatyzowalna zbiorem zdań ale nie jednym zdaniem, bądź nieaksjomatyzowalna nawet zbiorem zdań?

Zadanie 2
Gra w życie toczy się na nieskończonej planszy \(\mathbb{Z}\times\mathbb{Z}\). Sąsiadami komórki \((x,y)\) jest osiem komórek \((x',y')\neq (x,y)\) dla których \(|x-x'|\leq 1\) i \(|y-y'|\leq 1.\)

Każda komórka może znajdować się w jednym z dwóch stanów: może być albo żywa, albo martwa. Czas jest dyskretny, stany komórek zmieniają się synchronicznie wedle następujących reguł: martwa komórka, która ma dokładnie 3 żywych sąsiadów, staje się w następnym kroku żywa, a żywa komórka z 2 albo 3 żywymi sąsiadami pozostaje nadal żywa, w przeciwnym przypadku umiera.

Dana jest struktura \(\mathfrak{A}=\langle\mathbb{Z}\times\mathbb{Z},\leq_1,\leq_2,U\rangle,\) gdzie \((x_1,x_2)\leq_i(y_1,y_2)\) wtw \(x_i\leq y_i\). \(U\) jest relacją unarną, którą traktujemy jako wkazanie żywych komórek na planszy do gry w życie. Wykaż, że dla każdego \(k\) istnieje formuła \(\varphi_k(x)\) z jedną zmienną wolną, dla której zachodzi:

\((\mathfrak{A},x:a)\models\varphi\) wtw komórka \(a\) jest żywa po \(k\)-tym kroku gry w życie, startującej z pozycji opisanej przez \(U.\)

Zadanie 3
Zadanie dotyczy klasycznej logiki zdaniowej nad zbiorem zmiennych zdaniowych \(\{p_0,p_1,\ldots\}.\)

Skonstruować bądź udowodnić że nie istnieje zbiór \(\Delta\) zdań logiki zdaniowej taki, że wartościowania \(v\) spełniające zbiór \(\Delta\) to dokładnie takie, dla których zbiór \(\{i\in\mathbb{N}~|~v(p_i)=1\}\) jest skończony.