Zadanie 1
Częściowy porządek A=⟨A,≤⟩ należy do klasy A wtedy i tylko wtedy, gdy:
(a) zawiera nieskończenie wiele elementów minimalnych;
(b) każdy nie-minimalny element a∈A jest supremum pewnego skończonego zbioru elementów minimalnych w A.
Czy klasa 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 Z×Z. Sąsiadami komórki (x,y) jest osiem komórek (x′,y′)≠(x,y) dla których |x−x′|≤1 i |y−y′|≤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 A=⟨Z×Z,≤1,≤2,U⟩, gdzie (x1,x2)≤i(y1,y2) wtw xi≤yi. 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 φk(x) z jedną zmienną wolną, dla której zachodzi:
(A,x:a)⊨φ 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 {p0,p1,…}.
Skonstruować bądź udowodnić że nie istnieje zbiór Δ zdań logiki zdaniowej taki, że wartościowania v spełniające zbiór Δ to dokładnie takie, dla których zbiór {i∈N | v(pi)=1} jest skończony.