Kolokwia i egzaminy, układ chronologiczny

Kolokwium 2010/2011

Zad. 1

Niech \(f\) będzie jednoargumentowym symbolem funcji i niech
\(\mathcal{A}=\bigcup_{n\in \mathbb{N}}Mod(\forall x f^n(x) =x)\),
gdzie \(f^n(x)\) to \(n\)-krotne złożenie \(f(\ldots(f(x))\ldots)\).
Wykazać, że ani \(\mathcal{A}\) nie można zdefiniować żadnym zbiorem zdań logiki pierwszego rzędu, ani
dopełnienia \(\mathcal{A}\) nie można zdefiniować pojedynczym zdaniem logiki pierwszego rzędu.

Zad. 2

Niech dany będzie niesprzeczny, skończony zbióor zdań \(\Delta\) nad pewną ustaloną i również
skończoną sygnaturą \(\Sigma\). Wykazać, że istnieje zbiór \(\Delta_0\subseteq\Delta\) taki, że \(\Delta_0\models\Delta\), a ponadto zdania w \(\Delta_0\) są niezależne: dla każdego \(\varphi\in\Delta_0\) mamy \(\Delta_0\setminus\{\varphi\}\not\models\Delta_0\).

Zad. 3

Niech \(\mathfrak{H}^n\) to struktura której uniwersum to hiperkostka \(H^n=\{0,1\}^n\), a jednyna relacja dwuargumentowa \(E^{\mathfrak{H}^n}\) jest zdefiniowana tak:

\(E^{\mathfrak{H}^n}(x,y)\) wtw, gdy \(x\) i \(y\) różnią się dokładnie na jednej pozycji.

Jakie jest maksymalne \(m\) takie, że gracz II ma strategię wygrywającą w grze Ehrenfeuchta \(G_m(\mathfrak{H}^4,\mathfrak{H}^3)\)?

Egzamin 2010/2011

Zad. 1 (3 punkty)

Rozważamy modele dla PDL postaci skończonego łańcucha złożonego z dwóch programów atomowych: \(u\) i \(v\). Między każdymi dwoma kolejnymi stanami przechodzi jeden i tylko jeden z tych programów. Zmienne zdaniowe są dwie: \(p\) prawdziwa tylko w pierwszym stanie łańcucha i \(k\) prawdziwa tylko w ostatnim stanie. Innych zmiennych zdaniowych nie ma.

Każdą taką strukturę można naturalnie uważać również za strukturę pierwszego rzędu, wówczas \(u\) i \(v\) są relacjami dwuargumentowymi a \(p\) i \(k\) relacjami jednoargumentowymi.

Udowodnić, że dla każdego zdania \(\varphi\) logiki MSO istnieje zdanie \(\phi\) logiki PDL takie, że dla każdej struktury \(\mathfrak{A}\) jak powyżej, \(\varphi\) jest prawdziwe w stanie początkowym struktury \(\mathfrak{A}\) wtedy i tylko wtedy, gdy \(\mathfrak{A}\models\phi\).

Zad. 2 (3 punkty)

Algebrę relacyjną z liniowym porządkiem na danych można skonstruować na dwa sposoby. Załózmy, że \(\leq\) jest relacją liniowego porządku na wszystkich elementach, które mogą się pojawić w krotkach, a w sygnaturze nie ma stałych.

Pierwszy sposób polega na tym, że do każdej bazy danych wprowadzamy dodatkową tabelę \(LEQ\) o dwóch kolumnach, która zawiera wszystkie krotki \(\langle a,b\rangle\) dla \(a,b\) należacych do aktywnej dziedziny i takich, że \(a\leq b.\) Wówczas zwykłe wyrażenia algebry relacyjnej mogą wykorzystać \(LEQ\) jak każdą inną tabelę. Jednak \(LEQ\) uważamy za część składni zapytań, a nie zwykłą tabelę w bazie.

Drugi sposób polega na tym, że nie zwiększamy liczby tabel, ale poszerzamy składnię i w warunku \(\theta\) selekcji \(\sigma_\theta(E)\) dopuszczamy także nierówności postaci \(i\leq j\) dla \(i,j\) nie większych niż liczba kolumn w \(E\). Semantyka jest oczywista, np. \([\![\sigma_{i\leq j}(E)]\!]=\{\vec{a}\in [\![E]\!]:a_i\leq a_j\}.\)

Pokazać, że zbiory zapytań wyrażalnych w obu formalizmach są takie same.

Zad. 3 (3 punkty)

Wykazać, że dla każdego ustalonego skończonego grafu \(\mathfrak{G}\) (ta litera to gotyckie G) i każdego ustalonego \(m\in\mathbb{N}\), następujący problem decyzyjny może zostać rozstrzygnięty przez deterministyczną maszynę Turinga, która obok taśmy z danymi tylko do odczytu ma taśmę roboczą o długości \(O(\log n)\) (za \(n\) przyjmujemy długość danych wejściowych algorytmu):

Dany: kod skończonego grafu \(\mathfrak{H}\) (gotyckie H) w postaci macierzy incydencji podanej wierszami.
Pytanie: Czy gracz II ma strategię wygrywającą w grze \(G_m(\mathfrak{G},\mathfrak{H})\)?

Zad. 4 (3 punkty)

Czy następująca formuła logiki drugiego rzędu jest tautologią dla \(n>1\):
\(\forall E\left[\left(\begin{array}{c}\forall xE(x,x)\land\\ \forall xy(E(x,y)\to E(y,z))\land\\ \forall xyz((E(x,y)\land E(y,z))\to E(x,z)))\end{array}\right)\to\forall x_{1}\dots x_{n}\ \bigvee _{{0\leq i< j\leq n}}E(x_{i},x_{j}))\right]\) \(\to\) \((\exists y_{1}\ldots y_{{n-1}}\forall z\bigvee _{{i=1}}^{{n-1}}y_{i}=z)\)

Zad. 5 (1.5 punkta)

Odpowiedz TAK lub NIE na wybrane trzy spośród poniższych pytań. Każda poprawna odpowiedź daje \(0.5\) punkta, każda niepoprawna \(-0.5\) punkta. W razie udzielenia odpowiedzi na więcej pytań, do wyniku zaliczymy trzy najgorsze z nich. Odpowiedzi proszę pisać na tej kartce!

Czy teoria pierwszego rzędu ciała liczb zespolonych \(\mathfrak{C}=\langle\mathbb{C},+,\cdot,0,1\rangle\) jest rozstrzygalna?
Czy dla każdego zbioru zdań \(\Gamma\) istnieje minimalny ze względu na zawieranie podzbiór \(\Gamma^{{\prime}}\subseteq\Gamma\) spełniający \(\Gamma^{{\prime}}\models\Gamma\)?
Czy problem SAT dla zdaniowej logiki trójwartościowej Bochvara jest NP-zupełny?
Czy formuła \(p\lor(q\to\lnot p)\) jest tautologią zdaniowej logiki intuicjonistycznej?

Egzamin poprawkowy 2010/2011

Zad. 1 (3 punkty)

Rozważamy skończone grafy \(\mathfrak{G}\) (ta litera to gotyckie G, w rozwiązaniu można pisać zwykłe G) nad sygnaturą składającą się z jednego dwuargumentowego symbolu relacyjnego \(E\).

Napisać zdanie \(\varphi\) logiki egzystencjalnej drugiego rzędu (tzn. postaci \(\exists R_{1}\ldots\exists R_{k}\psi(R_{1},\ldots,R_{k}),\) w którym \(\psi\) jest zdaniem pierwszego rzędu) takie, że dla każdego skończonego grafu \(\mathfrak{G}\) zachodzi równoważność: \(\mathfrak{G}\models\varphi\) wtw \(\mathfrak{G}\) ma cykl Eulera.

Zad. 2 (3 punkty)

Pokazać, że żadne zdanie \(\varphi\) logiki pierwszego rzędu nie ma tej własności, że dla każdego skończonego grafu \(\mathfrak{G}\) zachodzi równoważność: \(\mathfrak{G}\models\varphi\) wtw \(\mathfrak{G}\) ma cykl Eulera.

Zad. 3 (3 punkty)

Niech wyrażenie \(E\) algebry relacyjnej ma taką właściwość, że żadne podwyrażenie \(E\) nie ma więcej niż \(k\) kolumn. Pokazać, że istnieje algorytm obliczający wartość \([\![E]\!]\) w bazie strukturze \(\mathfrak{A}\), który działa w czasie \(O(n^{k}\log n),\) gdzie \(n\) to liczność dziedziny aktywnej \(\mathfrak{A}\).

Przy projektowaniu algorytmu należy założyć, że dziedzina aktywna składa się z liczb całkowitych typu integer, a do dyspozycji są jednowymiarowe tablice indeksowane nieujemnymi liczbami całkowitymi i zawierające takież liczby. Dostęp do komórki tablicy jest wykonywany w czasie jednostkowym, podobnie jak operacje arytmetyczne i porównania na liczbach całkowitych. Relacje z \(\mathfrak{A}\) są przekazywane do algorytmu właśnie w takich tablicach: relacja o \(l\) kolumnach jest reprezentowana przez \(l\) tablic, a dane zajmują początkowe indeksy.

Zad. 4 (3 punkty)

Rozważamy skończone drzewa binarne \(\mathfrak{T}\) (ta litera to gotyckie T, w rozwiązaniu można pisać zwykłe T) nad sygnaturą składającą się z dwóch dwuargumentowych symboli relacyjnych \(L\) i \(P\), przy czym \(L(x,y)\) oznacza że \(y\) to lewy syn ojca \(x\), podobnie dla \(P\) oznaczającego prawego syna. Każdy wiechołek może mieć 0, 1 lub 2 synów, zawsze najwyżej jednego lewego jednego prawego.

Udowodnić, że dla każdego naturalnego \(n\) istnieje zdanie \(\varphi _{n}\) logiki pierwszego rzędu, w którym występują tylko dwie zmienne (które można rekwantyfikować tak często jak potrzeba), takie że dla każdego skończonego drzewa binarnego \(\mathfrak{T}\) zachodzi równoważność: \(\mathfrak{T}\models\varphi _{n}\) wtw \(\mathfrak{T}\) jest pełnym drzewem binarnym o głębokości \(n\).

Zad. 5 (3 punkty)

Sygnatura składa się z dwuargumentowego symbolu funkcyjnego \(\circ\), jednoargumentowego symbolu funkcyjnego \(inv\) i symbolu stałej \(id\). Model \(\mathfrak{F}\) (ta litera to gotyckie F, w rozwiązaniu można pisać zwykłe F) nad tą sygnaturą nazywamy grupą bijekcji, gdy jego uniwersum stanowi zbiór wszystkich bijekcji \(f:A\to A\) dla pewnego zbioru \(A,\) a operacje mają następujące interpretacje: \(\circ^{\mathfrak{F}}\) to operacja składania funkcji, \(inv^{\mathfrak{F}}\) to operacja brania funkcji odwrotnej, a \(id^{\mathfrak{F}}\) to funkcja indentycznościowa z \(A\) w \(A\).

Udowodnić, że nie istnieje zbiór \(\Gamma\) zdań logiki pierwszego rzędu taki, że \(\mathfrak{B}\models\Gamma\) wtedy i tylko wtedy, gdy \(\mathfrak{B}\) jest izomorficzny do pewnej grupy bijekcji.

Egzamin po-poprawkowy 2010/2011 (dla osób z przedłużeniem sesji)

Zad. 1 (3 punkty)

Rozważamy skończone grafy nieskierowane \(\mathfrak{G}\) (ta litera to gotyckie G, w rozwiązaniu
można pisać zwykłe G) nad sygnaturą składającą się z jednego dwuargumentowego
symbolu relacyjnegoE.
Napisć zdanie logiki MSO postaci \(\forall X_1\ldots\forall X_k\psi(X_1,\ldots,X_k)\), w którym \(\psi\) jest
zdaniem pierwszego rzędu takie,że dla każdego skończonego grafu \(\mathfrak{G}\) zachodzi równoważność:
\(\mathfrak{G}\models\varphi\) wtw \(\mathfrak{G}\) jest drzewem (nieskierowanym).

Zad. 2 (3 punkty)

Pokazć, że nie istnieje zdanie \(\varphi\) logiki pierwszego rzędu o tej własności, że dla
każdego nieskierowanego (skończonego lub nie) grafu \(\mathfrak{G}\) zachodzi równoważność:
\(\mathfrak{G}\models\varphi\) wtw każdy wierzchołek \(\mathfrak{G}\) należy do pewnego cyklu w tym grafie.

Zad. 3 (3 punkty)

Dane są dwie tabele \(A\) i \(B\) o dwóch kolumnach każda. Ta pierwsza składa się z \(n_A\)
wierszy.
Zaprojektowć algorytm wyliczenia wartości wyrażenia algebry relacyjnej

\(A\setminus\pi_{12}(\sigma_{1=3}(A\times B))\).

Przy projektowaniu algorytmu należy założyć, że dziedzina aktywna składa się z liczb
całkowitych typu integer, a do dyspozycji są dwukolumnowe tablice, których wiersze
indeksowane są nieujemnymi liczbami całkowitymi i zawierają takież liczby.
W algorytmie należy użyć dokładnie jednej takiej tablicy o rozmiarze \(n_A\) wierszy i
kilku dodatkowych zmiennych typu integer. Oznacza to,że wykorzystujemy dokładnie
tyle pamięci, ile zajmie wynik. Proszę nie używć wskaźników, rekursji i innych metod
ukrytego alokowania dodatkowej pamięci.

Tabele \(A\) i \(B\) są tylko do odczytu, przy czym można założyć, że są one posortowane.
Jeśli rozwiązanie będzie z tego korzystć, proszę o tym założeniu wspomnieć.

Zad. 4 (3 punkty)

Rozważamy skończone skierowane cykle \(\mathfrak{C}\) (ta litera to gotyckie C, w rozwiązaniu
można pisć zwykłe C) nad sygnaturą składającą się z jednego dwuargumentowego
symbolu relacyjnego \(E\).

Udowodnić, że dla każdego naturalnego \(n\) istnieje formuła
\(\varphi_n(x,y,z)\) logiki pierwszego rzędu, w której występują tylko trzy zmienne (które można rekwantyfikowć
tak często jak potrzeba), takie że dla każdego skończonego cyklu \(\mathfrak{C}\) zachodzi równoważność:
\((\mathfrak{C}, x : a, y : b, z : c)\models\varphi_n(x,y,z)\) wtw \(\mathfrak{C}\) ma \(3n\) krawędzi, a skierowane
odległości z \(a\) do \(b\), z \(b\) do \(c\) i z \(c\) do \(a\) wszystkie wynoszą po \(n\).

Zad. 5 (3 punkty)

Niech \(\varphi\) będzie zdaniem \(\forall x\forall y(y =f(g(x)) \to(\exists u(u=f(x)\land y =g(u))))\) oraz
niech \(\psi\) będzie zdaniem
\(\forall x[f(g(f(x))) =g(f(f(x)))]\). Czy \(\{\psi\}\models\varphi\)?

Kolokwium 2011/2012

Zadanie 1A

Niech sygnatura \(\Sigma=\{+, s, f, 0\}\) składa się tylko z symboli funkcyjnych i niech + będzie dwuargumentowy, \(s\) i \(f\) jednoargumentowe a 0 niech będzie stałą. W algebrze \(\mathfrak{A}=\langle A, +^\mathfrak{A}, s^\mathfrak{A},f^\mathfrak{A}, 0^\mathfrak{A}\rangle\) powiemy, że funkcja \(f^\mathfrak{A}\) jest okresowa, jeśli istnieje \(k \in A\), \(k \not =0^\mathfrak{A}\) takie, że dla każdego \(x\in A\) zachodzi \(f^\mathfrak{A}(x+k)=f^\mathfrak{A}(x)\). Powiemy, że funkcja \(f^\mathfrak{A}\) jest zwyczajnie okresowa, jeśli istnieje \(k=s^\mathfrak{A}(\ldots s^\mathfrak{A}(0^\mathfrak{A})\ldots)\) takie, że dla każdego \(x\in A\) zachodzi \(f^\mathfrak{A}(x+k)=f^\mathfrak{A}(x)\).

Dla każdej z podanych poniżej klas struktur określ, czy jest ona:
i) aksjomatyzowalna pojedynczym zdaniem logiki pierwszego rzędu,
ii) jestaksomatyzowalna zbiorem zdań logiki pierwszego rzędu, ale nie pojedynczym zdaniem
iii) nie jest aksjomatyzowalna żadnym zbiorem zdań pierwszego rzędu.

1. Klasa struktur \(\mathfrak{A}=\langle A, +^\mathfrak{A}, s^\mathfrak{A}, f^\mathfrak{A}, 0^\mathfrak{A}\rangle\) nad sygnaturą \(\Sigma\)
w których \(f^\mathfrak{A}\) jest okresowa.

2. Klasa struktur \(\mathfrak{A}=\langle A, +^\mathfrak{A}, s^\mathfrak{A}, f^\mathfrak{A}, 0^\mathfrak{A}\rangle\) nad sygnaturą \(\Sigma\)
w których \(f^\mathfrak{A}\) jest zwyczajnie okresowa.

3. Klasa struktur \(\mathfrak{A}=\langle A, +^\mathfrak{A}, s^\mathfrak{A}, f^\mathfrak{A}, 0^\mathfrak{A}\rangle\) nad sygnaturą \(\Sigma\)
w których \(f^\mathfrak{A}\) nie jest zwyczajnie okresowa.

Zadanie 1B
Niech sygnatura \(\Sigma=\{+, s, f, 0\}\) składa się tylko z symboli funkcyjnych i niech + i \(f\) będą dwuargumentowe, \(s\) jednoargumentowy a 0 niech będzie stałą. W algebrze \(\mathfrak{A}=\langle A, +^\mathfrak{A}, s^\mathfrak{A}, f^\mathfrak{A}, 0^\mathfrak{A}\rangle\) powiemy, że funkcja \(f^\mathfrak{A}\) jest okresowa, jeśli istnieją \(k,\ell \in A\), \(k,\ell \not =0^\mathfrak{A}\) takie, że dla każdych \(x,y\in A\) zachodzi \(f^\mathfrak{A}(x+k,y+\ell)=f^\mathfrak{A}(x,y)\). Powiemy, że funkcja \(f^\mathfrak{A}\) jest zwyczajnie okresowa, jeśli
istnieją \(k=s^\mathfrak{A}(\ldots s^\mathfrak{A}(0^\mathfrak{A})\ldots)\) i \(\ell=s^\mathfrak{A}(\ldots s^\mathfrak{A}(0^\mathfrak{A})\ldots)\) takie, że dla każdych \(x,y\in A\) zachodzi \(f^\mathfrak{A}(x+k,y+\ell)=f^\mathfrak{A}(x,y)\).

Dla każdej z podanych poniżej klas struktur określ, czy jest ona:
i) aksjomatyzowalna pojedynczym zdaniem logiki pierwszego rzędu,
ii) jest aksomatyzowalna zbiorem zdań logiki pierwszego rzędu, ale nie pojedynczym zdaniem
iii) nie jest aksjomatyzowalna żadnym zbiorem zdań pierwszego rzędu.

1. Klasa struktur \(\mathfrak{A}=\langle A, +^\mathfrak{A}, s^\mathfrak{A}, f^\mathfrak{A}, 0^\mathfrak{A}\rangle\) nad sygnaturą \(\Sigma\)
w których \(f^\mathfrak{A}\) jest okresowa.

2. Klasa struktur \(\mathfrak{A}=\langle A, +^\mathfrak{A}, s^\mathfrak{A}, f^\mathfrak{A}, 0^\mathfrak{A}\rangle\) nad sygnaturą \(\Sigma\)
w których \(f^\mathfrak{A}\) jest zwyczajnie okresowa.

Szkic rozwiązania zadań 1A i 1B

Rozwiązujemy zadanie 2B, 2A jest bardzo podobne.

1. Ta klasa jest aksjomatyzowalna zdaniem
\(\exists k\exists \ell (k\neq 0 \land \ell\neq 0 \land (\forall x\forall y f(x+k,y+\ell)=f(x,y))).\)

2. Przypuśćmy, że klasa z tego punktu jest aksjomatyzowalna zbiorem zdań \(\Delta\).
Niech
\(\Gamma =\{\exists x\exists y f(x+s^k(0),y+s^\ell(0))\neq f(x,y))~|~k,\ell\in\mathbb{N}\}\)
oraz niech
\(\overline{\Delta}=\Delta\cup\Gamma\).
Pokazujemy, że każdy skończony podzbiór \(\Delta_0\) zbioru \(\overline{\Delta}\) ma model. Istotnie, każdy taki skończony podzbiór zawiera tylko skończenie wiele zdań ze zbioru \(\Gamma\) i łatwo można skonstruować algebrę \(\mathfrak{A}\), w której funkcja \(f^\mathfrak{A}\) jest zwyczajnie okresowa, mimo że żadna para elementów postaci \(\langle s^k(0),s^\ell(0)\rangle\) wspomnianych w \(\Delta_0\) nie jest okresem.

Zatem z Twierdzenia o Zwartości \(\overline{\Delta}\) ma model, jednak funkcja \(f\) w tym modelu nie może być zwyczajnie okresowa wobec faktu, że model ten spełnia \(\Gamma\). Zatem \(\Delta\) ma model, w którym funkcja \(f\) nie jest zwyczajnie okresowa.

Uzyskana sprzeczność dowodzi, że zbioru zdań \(\Delta\) aksjomatyzującego klasę z tego punktu nie ma.

3. Zbiór \(\Gamma\) z poprzedniego punktu tego zadania aksjomatyzuje klasę z punktu 3. Pozostaje pokazać, że nie można tego zrobić jednym zdaniem. Gdyby jednak takie zdanie \(\varphi\) istniało, to jego negacja \(\lnot\varphi\) aksjomatyzowałaby klasę z punktu 2. Tymczasem jednak takiej aksjomatyzacji nie ma. Zatem klasa z niniejszego punktu nie jest aksjomatyzowalna jednym zdaniem, choć jest aksjomatyzowalna zbiorem zdań.

Zadanie 2A

Zajmujemy się klasą grafów (skierowanych, pętle są dopuszczalne). Skonstruować przykład dwóch grafów \(\mathfrak{G}_1\) i \(\mathfrak{G}_2\) takich, że:

1. dla każdego grafu \(\mathfrak{H}\) o co najwyżej 7 wierzchołkach \(\mathfrak{G}_1\) zawiera indukowany podgraf izomorficzny z \(\mathfrak{H}\) wtedy i tylko wtedy, gdy \(\mathfrak{G}_2\) zawiera indukowany podgraf izomorficzny z \(\mathfrak{H}\).
2. Gracz 1 ma strategię wygrywającą w grze \(G_7(\mathfrak{G}_1,\mathfrak{G}_2).\)

Zadanie 2B

Zajmujemy się klasą grafów (skierowanych, pętle są dopuszczalne). Skonstruować przykład dwóch grafów \(\mathfrak{G}_1\) i \(\mathfrak{G}_2\) takich, że:
1. dla każdego grafu \(\mathfrak{H}\) o co najwyżej 6 wierzchołkach \(\mathfrak{G}_1\) zawiera indukowany podgraf izomorficzny z \(\mathfrak{H}\) wtedy i tylko wtedy, gdy \(\mathfrak{G}_2\) zawiera indukowany podgraf izomorficzny z \(\mathfrak{H}\).
2. Gracz 1 ma strategię wygrywającą w grze \(G_6(\mathfrak{G}_1,\mathfrak{G}_2).\)

Szkic rozwiązania zadań 2A i 2B

Generalnie to zadanie ma bardzo dużo poprawnych rozwiązań.

Łatwym przykładem na grafy \(\mathfrak{G}_1\) i \(\mathfrak{G}_2\) takie, że 1. graczy ma strategię w grze \(G_n(\mathfrak{G}_1,\mathfrak{G}_2)\) mimo tego, że oba grafy zawierają dokładnie te same podgrafy indukowane o co najwyżej \(n\) wierzchołkach, są liniowe porządki o mocach \(2^n-1\) i \(2^n\), odpowiednio.

Gracz 1. może w celu zwycięstwa stosować strategię poszukiwania binarnego. W pierwszym ruchu zaznacza środkowy (albo jeden z dwóch środkowych) elementów jednego z porządków, a na odpowiedź gracza 2. reaguje połowiąc ten z powstałych odcinków, który ma długość inną niż odpowiedni odcinek powstały po odpowiedzi gracza 2.

Zawieranie identycznie tych samych podgrafów do \(n\) wierzchołków włącznie jest oczywiste.

Zadanie 3A
Rozważamy strukturę
\(\mathfrak{P}=\langle \mathbb{R}^3,B^\mathfrak{P}\rangle\), gdzie relacja \(B^\mathfrak{P}\) jest trzyargumentowa i określona następująco:
\(B^\mathfrak{P}(a,b,c)\) zachodzi wtedy i tylko wtedy, gdy punkty \(a,b,c\) są parami
różne, współliniowe i ponadto \(b\) leży na odcinku łączącym \(a\) i \(c\).

Proszę napisać formułę \(\varphi\) logiki pierwszego rzędu, dla
której

\((\mathfrak{P},x_1:a_1,x_2:a_2,x_3:a_3,x_4:a_4)\models\varphi\) wtedy i
tylko wtedy, gdy punkty \(a_1,a_2,a_3,a_4\) leżą na jednej płaszczyźnie.

Zadanie 3B
Rozważamy strukturę
\(\mathfrak{P}=\langle \mathbb{R}^3,B^\mathfrak{P}\rangle\), gdzie relacja \(B^\mathfrak{P}\) jest trzyargumentowa i określonae następująco:
\(B^\mathfrak{P}(a,b,c)\) zachodzi wtedy i tylko wtedy, gdy punkty \(a,b,c\) są parami
różne, współliniowe i ponadto \(b\) leży na odcinku łączącym \(a\) i \(c\).

Proszę napisać formułę \(\varphi\) logiki pierwszego rzędu, dla
której

\((\mathfrak{P},x_1:a_1,x_2:a_2,x_3:a_3,x_4:a_4)\models\varphi\) wtedy i
tylko wtedy, gdy punkty \(a_1,a_2,a_3,a_4\) nie leżą na jednej płaszczyźnie.

Szkic rozwiązania zadań 3A i 3B

Rozwiążemy zadanie 3A, a rozwiązanie 3B otrzymuje się przez jego zanegowanie.

Niech \(L(x,y,z)\) oznacza formułę \(x=y\lor y=z\lor x=z \lor B(x,y,z)\lor B(y,x,z)\lor B(x,z,y)\), która orzeka, że \(x,y,z\) są współliniowe (co zachodzi także zawsze wtedy, gdy któreś dwa z tych punktów są równe).
Cztery punkty w przestrzeni sa współpłaszczyznowe, gdy istnieje punkt współliniowy jednocześnie z dwoma parami punktów utworzonymi z \(x_1,x_2,x_3\) i \(x_4\).
Zatem szukana formuła ma postać
\(\exists z ((L(x_1,x_2,z)\land(L(x_3,x_4,z))\lor(L(x_1,x_3,z)\land(L(x_2,x_4,z))\lor(L(x_1,x_4,z)\land(L(x_2,x_3,z)))\).

Mid-term test 2011/2012

Problem 1A

Let signature \(\Sigma=\{+, s, f, 0\}\) consist only of function symbols, and let + be binary, \(s\) and \(f\) unary, 0 constant. In the algebra \(\mathfrak{A}=\langle A, +^\mathfrak{A}, s^\mathfrak{A},f^\mathfrak{A}, 0^\mathfrak{A}\rangle\) the function \(f^\mathfrak{A}\) is said to be periodic, if there exists\(k \in A\), \(k \not =0^\mathfrak{A}\) such tha tfor every \(x\in A\) holds \(f^\mathfrak{A}(x+k)=f^\mathfrak{A}(x)\).
\(f^\mathfrak{A}\) is standard periodic, if there exists \(k=s^\mathfrak{A}(\ldots s^\mathfrak{A}(0^\mathfrak{A})\ldots)\) such that for each \(x\in A\) holds \(f^\mathfrak{A}(x+k)=f^\mathfrak{A}(x)\).

For each of the following classes of structures determine, if it is
i) axiomatisable by a single sentence
ii) axiomatisable by a set of sentences, but not by a single sentence
iii) is not axiomatisable by any set of sentences

1. The class of structures \(\mathfrak{A}=\langle A, +^\mathfrak{A}, s^\mathfrak{A}, f^\mathfrak{A}, 0^\mathfrak{A}\rangle\) over \(\Sigma\), in which \(f^\mathfrak{A}\) is periodic

2. The class of structures \(\mathfrak{A}=\langle A, +^\mathfrak{A}, s^\mathfrak{A}, f^\mathfrak{A}, 0^\mathfrak{A}\rangle\) over \(\Sigma\), in which \(f^\mathfrak{A}\) is standard periodic

3. The class of structures \(\mathfrak{A}=\langle A, +^\mathfrak{A}, s^\mathfrak{A}, f^\mathfrak{A}, 0^\mathfrak{A}\rangle\) over \(\Sigma\), in which \(f^\mathfrak{A}\) is not standard periodic

Problem 2A

We work with the class of directed graphs (self-loops are permitted). Give an example of two such graphs \(\mathfrak{G}_1\) and \(\mathfrak{G}_2\) such that:

1. For each graph \(\mathfrak{H}\) with at most 7 vertices, \(\mathfrak{G}_1\) contains an induced subgraph isomorphic to \(\mathfrak{H}\) if and only if \(\mathfrak{G}_2\) contains an induced subgraph isomorphic to \(\mathfrak{H}\).
2. Player I has a winning strategy in the game \(G_7(\mathfrak{G}_1,\mathfrak{G}_2).\)

Problem 3A
We consider the structure
\(\mathfrak{P}=\langle \mathbb{R}^3,B^\mathfrak{P}\rangle\), where the relation \(B^\mathfrak{P}\) is 3-ary and defined as follows:

\(B^\mathfrak{P}(a,b,c)\) holds if and only if \(a,b,c\) are all different and collinear, and moreover \(b\) belongs to the line segment connecting \(a\) and \(c\).

Write a first-order formula \(\varphi\) such that

\((\mathfrak{P},x_1:a_1,x_2:a_2,x_3:a_3,x_4:a_4)\models\varphi\) if and only of the points \(a_1,a_2,a_3,a_4\) lay on a common plane.

Egzamin 2011/2012

Zadanie 1 (15 punktów)

Napisać formułę \(\varphi(x,y)\) w języku arytmetyki taką, że \((\mathfrak{N},x:r,y:k)\models \varphi\) wtw w ćwierćkole \(\{(x,y)\in \mathbb{R}^2~:~x,y\geq 0,~x^2+y^2\leq r\}\) na płaszczyźnie euklidesowej jest dokładnie \(k\) punktów kratowych (tzn. punktów o obu współrzędnych całkowitych).

Rozwiązanie

Wykorzystamy formułę \(\chi\), definiującą funkcję \(\beta\) Goedla, aby powiedzieć, że istnieje ciąg \(y\) parami różnych par liczb naturalnych \((u,v)\) spełniających \(u^2+v^2\leq x\) i że każda para liczb spełniająca ten warunek w tym ciągu występuje.

\(\exists t\exists p
[\forall i(i\le y-1\to(\exists u\exists v\chi(t,p,2*i,u)\land\chi(t,p,2*1+1,v)\land u*u+v*v\leq x)\land\)
\((\forall u\forall u(u*u+v*v\leq x\to\exists! i(i\le y-1\land \chi(t,p,2*i,u)\land\chi(t,p,2*1+1,v))]\).

Zadanie 2 (15 punktów)

W pewnej bazie danych znajduje się dwukolumnowa tabela \(R\), zawierająca w sobie relację liniowego porządku na wszystkich elementach dziedziny aktywnej tej bazy danych. Dane jest także wyrażenie \(E\) algebry relacji

\(R\setminus (\pi_{1,4}(\sigma_{2=3}(R\times R)\setminus(\sigma_{1=2}(R\times R)\cup\sigma_{3=4}(R\times R)))).\)

Zaprojektować algorytm obliczający \([\![E]\!]\), którego złożoność czasowa wynosi \(O(n)\), gdzie \(n=|R|.\) Można korzystać z tablicy haszującej dla elementów dziedziny aktywnej, o dostępie w czasie jednostkowym i zapewniającej brak kolizji.

Rozwiązanie

Wyrażenie \(E\) opisuje sumę relacji bezpośredniego następnika na dziedzinie aktywnej i relacji identycznościowej na dziedzinie aktywnej, zgodnie z porządkiem zadanym przez \(R\). Obliczenie relacji identycznościowej jest banalne, problemem jest tylko następnik.

Jeśli \(|R|=n\), to rozmiar dziedziny aktywnej wynosi \(m=O(\sqrt{n})\).

W celu obliczenia następnika można użyć tablicy haszującej \(T\), używając ją do zliczania ile razy każdy z elementów dziedziny aktywnej występuje po lewej stronie par w relacji \(R\). Wymaga to liniowego przejścia \(R\) w czasie \(O(n)\). Po zakończeniu tego procesu można \(T\) posortować po wartościach zliczeń w czasie \(O(m\log m)=O(n)\) i wypisać pary kolejnych elementów, albo wykorzystać \(T\) do rozstrzygania w czasie stałym o porządku par poszczególnych elementów (przez porównanie ich zliczeń w \(T\)), co pozwala po prostu posortować dziedzinę aktywną.

Zadanie 3 (15 punktów)

Rozważamy logikę LTL nad skończonymi strukturami-słowami.
Jak wiadomo z tw. Gabbaya, każde zdanie \(\varphi\) logiki LTL można wyrazić równoważnie w postaci zdania będącego boolowską kombinacją zdań czasu przyszłego i zdań czasu przeszłego.

Podać przykład zdania \(\varphi\) logiki LTL którego nie można wyrazić równoważnie w postaci koniunkcji jednego zdania czasu przyszłego i jednego zdania czasu przeszłego.

Rozwiązanie

Roważmy zdanie \(\varphi=Yp\lor Xp\).

Przypuśćmy, że \(\varphi\) jest równoważne formule \(\alpha\land\beta\), gdzie \(\alpha\) jest czasu przeszłego a \(\beta\) jest czasu przyszłego. Rozważmy teraz dwa modele o trzech stanach, zapisane jako ciągi prawdziwości \(p\) w kolejnych stanach. Te modele to \(100\) i \(001\). W obu stan środkowy oznaczmy \(*\).

Mamy zatem \((100,*)\models\varphi\) i \((001,*)\models\varphi\).

Ponieważ \(varphi\) jest równoważne \(\alpha\land\beta\), to \((100,*)\models\beta\) i \((001,*)\models\alpha\).

Zatem \((000,*)\models\beta\) bo \(\beta\) jest czasu przyszłego a \(000\) różni się od \(100\) tylko w przeszłości względem \(*\)
oraz \((000,*)\models\alpha\) bo \(\alpha\) jest czasu przeszłego a \(000\) różni się od \(001\) tylko w przyszłości względem \(*\).

Stąd \((000,*)\models\alpha\land\beta\) wbrew założeniu, że ta formuła jest równoważna \(Yp\lor Xp\).

Zadanie 4 (15 punktów: 5 za podpunkt 1 i 10 za podpunkt 2)

Zajmujemy się skończonymi grafami nieskierowanymi. W obu podpunktach należy napisać zdanie \(\varphi\) logiki drugiego rzędu takie, że dla każdego grafu \(\mathfrak{G}\) zachodzi

\(\mathfrak{G}\models\varphi\) wtw \(\mathfrak{G}\) jest spójny}.

\(\varphi\) ma mieć postać \(\forall R\varphi',\) gdzie \(\varphi'\) jest formułą pierwszego rzędu.
\(\varphi\) ma mieć postać \(\exists R\varphi',\) gdzie \(\varphi'\) jest formułą pierwszego rzędu.

Rozwiązanie

Niech \(E\) to relacja krawędzi.

Wyrażamy Dla każdego podziału \(\mathfrak{G}\) na dwa niepuste podzbiory, istnieje krawędź łacząca wierzchołek w jednej z tych części z wierzchołkiem w drugiej części.
\(\forall R((\exists x\exists y R(x)\land\lnot R(y)) \to(\exists x\exists y R(x)\land\lnot R(y)\land E(x,y)))\)
Najpierw napiszemy zdanie postaci \(\forall x\forall y \exists R\varphi\) wyrażające spójność. Będzie ono formalizowało
\(\forall x\forall y \) istnieje ścieżka od \(x\) do \(y\).
Ma ono postać

\(\forall x\forall y \exists R(x=y\lor \) "\(R\) jest liniowym porządkiem, \(x\) jest pierwszy w tym porządku, między każdymi dwoma kolejnymi wierchołkami \(z,t\) położonymi pomiędzy \(x\) i \(y\) jest krawędź").

\(\forall x\forall y \exists R\varphi(x=y\lor\)
\( ((\forall u R(u,u))\land(\forall u\forall v R(u,v)\lor R(v,u))\land(\forall u\forall v (R(u,v)\land R(v,u))\to u=v)\land(\forall u \forall v\forall w (R(u,v)\land R(v,w))\to R(u,w)))\land\)
\((\forall z R(x,z))\land \)
\( \forall z\forall t [[R(z,y)\land R(t,y)\land(\forall u ((R(z,u)\land R(u,t)))\to(u=z\lor u=t))]\to E(z,t)]\)

Teraz mając zdanie \(\forall x\forall y \exists R\varphi\) przerabiamy je na żądaną postać przez zamianę \(R\) z dwuargumentowego na czteroargumentowy:

\(\exists R\forall x\forall y \varphi[R(x,y,*,*)/R(*,*)]\), co ma ten efekt, że nowa relacja \(R\) dla każdego wyboru \(x,y\) ma w sobie zapisany odpowiedni porządek, opisujący ścieżkę od \(x\) do \(y\).

TEST

1. Niech dla zdania \(\varphi\) logiki pierwszego rzędu

\({spec}(\varphi)=\{n\in\mathbb{N}_+\) istnieje \(\mathfrak{A}\) o mocy \(n\) takie, że \(\mathfrak{A}\models\varphi\}.\)

Czy następujący problem jest rozstrzygalny:
Dane: Dwa zdania \(\varphi,\psi\) logiki pierwszego rzędu.
Pytanie: Czy \(spec(\varphi)=spec(\psi)\)?

Odpowiedź

NIE, bo gdyby był, to można by sprawdzać czy dane zdanie \(\varphi\) ma skończony model pytając czy \(spec(\varphi)=spec(\bot)\). Tymczasem jest to niemożliwe na mocy tw. Trachtenbrota.

2. Czy następująca formuła logiki drugiego rzędu SO jest jest tautologią?

\([\forall R \exists Q_1 \exists Q_2 \forall x \forall y (R(x,y) \leftrightarrow
(Q_1(x) \land Q_2(y)))]\)

\(\to\)

\([\exists Q_1 \exists Q_2 \forall R \forall x \forall y ((R(x,y) \leftrightarrow
Q_1(x,y)) \lor (R(x,y) \leftrightarrow Q_2(x,y)))]\)

Odpowiedź

TAK.

Zdanie w pierwszej linijce orzeka, że każda relacja dwuargumentowa (czyli zbiór par elementów) jest produktem kartezjańskim dwóch zbiorów elementów. Jest to możliwe wtedy i tylko wtedy gdy uniwersum modelu ma dokładnie jeden element.

W takim model z kolei istnieją dwie relacje dwuragumentowe (a konkretnie pusta i pełna) takie, że każda relacja relacja dwuargumentowa jest jedną z nich (bo innych na uniwersum jednoelementowym nie ma).

3. Czy gracz II ma strategię wygrywającą w grze Ehrenfeuchta-Fra\"{\i}ss\'ego o 4 rundach \(G_4(\mathfrak{A},\mathfrak{B}),\) gdzie \(\mathfrak{A}\) i \(\mathfrak{B}\) są poniższymi grafami nieskierowanymi (\(\mathfrak{A}\) po lewej, \(\mathfrak{B}\) po prawej):

   *      *      *      *                        *      *      *    
   |      |      |      |                        |      |      |    
 *-*-*  *-*-*  *-*-*  *-*-*                    *-*-*  *-*-*  *-*-*  
   |      |      |      |                        |      |      |    
   *      *      *      *                        *      *      *

Odpowiedź

NIE. Oto strategia dla gracza I: w trzech ruchach kolejno zaznacza centra krzyży po prawej stronie, po czym w czwartym zaznacza dowolny element tego krzyża po lewej, w którym gracz II nie zaznaczył dotąd żadnego elementu.

4. Ustalamy alfabet \(A_k\) i rozpatrujemy modele-słowa postaci \(\mathfrak{A}(w)\) dla słów \(w\in A_k^+.\) Niech dla zdania \(\varphi\) logiki monadycznej drugiego rzędu MSO
\(\bar{spec}(\varphi)=\{n\in\mathbb{N}_+ :\) istnieje \(w\in A_k^n\) takie, że \(\mathfrak{A}(w)\models\varphi\}.\)

Czy dla każdego zdania \(\varphi\) w MSO istnieje zdanie \(\psi\) w MSO takie, że \(\mathbb{N}_+\setminus\bar{spec}(\varphi)=\bar{spec}(\psi)\)?

Odpowiedź

TAK. Wystarczy wziąć zdanie \(\lnot \exists X_1\ldots\exists X_k\varphi\), gdzie \(X_1\ldots X_k\) to wszystkie relacje unarne w sygnaturze \(\varphi\).

5. Czy w logice LTL da się wyrazić formułą następującą własność modelu-słowa \(\mathfrak{A}(w)\):
jest dokładnie tyle samo stanów w których zmienna zdaniowa \(p\) jest prawdziwa i stanów w których zmienna zdaniowa \(p\) jest fałszywa.

Odpowiedź

NIE. Opisana własnośc nie jest regularna, więc nie da się jej wyrazić nawet w logice MSO (tw. Buchi-Elgota), a tym bardziej w FO, która jest równoważna LTL (tw. Kampa).

Egzamin poprawkowy 2011/2012

Zadanie 1 (20 punktów) Rozważamy struktury \(\mathfrak{A}\) nad sygnaturą złożoną z dwuargumentowych symboli operacji \(+,-,*\) stałych \(0,1\) oraz jednoragumentowego symbolu operacji \(f.\)

Powiemy, że \(f^\mathfrak{A}\) jest opisana termem arytmetycznym jeśli istnieje term \(\tau(x)\) z jedną zmienną wolną \(x\), nie zawierający symbolu \(f\) oraz taki, że dla każdego wartościowania \(\rho\) w \(\mathfrak{A}\) zachodzi
\([\![f(x)]\!]_\rho=[\![\tau(x)]\!]_\rho.\)

Przykładowo, jeśli \(A=\mathbb{R}\) oraz działania \(+,-,*\) i stałe \(0,1\) mają swoje zwykłe interpretacje znane z ciała liczb rzeczywistych, to \(f^\mathfrak{A}\) jest opisana termem arytmetycznym wtedy i tylko wtedy, gdy \(f^\mathfrak{A}\) jest wielomianem jednej zmiennej o współczynnikach całkowitych.

Udowodnić, że nie istnieje zbiór zdań \(\Delta\) logiki pierwszego rzędu nad powyższą sygnaturą taki, że \(\mathfrak{A}\models\Delta\) wtedy i tylko wtedy, gdy \(f^\mathfrak{A}\) jest opisana termem arytmetycznym.

Szkic rozwiązania

Warunek, że \([\![f(x)]\!]_\rho=[\![\tau(x)]\!]_\rho\) dla każdego \(\rho\) oznacza tyle, że \(\mathfrak{A}\models\forall x f(x)=\tau(x).\)

Przypuśćmy, że zbiór \(\Delta\) opisany w zadaniu istnieje.

Niech \(\tau_1(x),\tau_2(x),\ldots\) będzie listą wszystkich termów arytmetycznych, tzn. nie używających symbolu \(f\).

Stwórzmy nowy zbiór \(\bar{\Delta}=\Delta\cup\{\exists x f(x)\neq \tau_i(x)~|~i\in\mathbb{N}\}\).

Używamy twierdzenia o zwartości, żeby pokazać, że \(\bar{\Delta}\) ma model. Istotnie, niech \(\Delta_0\subseteq\bar{\Delta}\) będzie skończony. Zawiera zatem skończenie wiele formuł postaci \(\exists x f(x)\neq \tau_i(x)\). Chcemy pokazać, że \(\Delta_0\) ma model. Modelem będzie zbiór liczb rzeczywsitych ze standardowo określonymi działaniami arytmetycznymi. Symbol funkcji \(f\) interpretujemy jako wielomian (a zatem funkcję opisaną termem) o stopniu wyższym, niż wszystkie wielomiany opisane termami występującymi w formułach postaci \(\exists x f(x)\neq \tau_i(x)\) należących do \(\Delta_0\).

Przy takim wyborze modelu widać, że spełnia on \(\Delta_0\).

Z dowolności \(\Delta_0\) wynika, że założnia twierdzenia o zwartości są spełnione, a zatem cały zbiór \(\Delta\) też ma model. Jest to jednak sprzeczność, bo w tym modelu interpretacja \(f\) nie jest opisana żadnym termem arytmetycznym.

Zadanie 2 (20 punktów) W pewnej bazie danych znajduje się dwukolumnowa tabela \(G\), zawierająca w sobie zbiór krawędzi pewnego grafu (który dla uproszczenia nazwiemy również \(G\)); w schemacie jest też stała \(a\). Napisać wyrażenie \(E\) algebry relacyjnej nie zawierające żadnego podwyrażenia o więcej niż 3 kolumnach o następującej semantyce:

\([\![E]\!]=\{\langle b\rangle~|~\) odległość od \(b\) do \(a\) w \(G\) nie przekracza 3\(\}.\)

Szkic rozwiązania

Zapytanie \(E_0\) określone jako \(\pi_1(\sigma_{1=a}(G))\cup\pi_1(\sigma_{1=a}(G))\) zwraca wszystkie elementy w odległości 0 od \(a\).

Zapytanie \(E_{1}\) określone jako \(\pi_1(\sigma_{2=3}(G\times E_0))\) zwraca wszystkie elementy połączone z \(a\) ścieżkami o długości 1 i jego żadne podwyrażenie nie ma więcej niż 3 kolumny.

Zapytanie \(E_{2}\) określone jako \(\pi_1(\sigma_{2=3}(G\times E_1))\) zwraca wszystkie elementy połączone z \(a\) ścieżkami o długości 2 i jego żadne podwyrażenie nie ma więcej niż 3 kolumny.

Zapytanie \(E_{3}\) określone jako \(\pi_1(\sigma_{2=3}(G\times E_2))\) zwraca wszystkie elementy połączone z \(a\) ścieżkami o długości 3 i jego żadne podwyrażenie nie ma więcej niż 3 kolumny.

Poszukiwanym wyrażeniem jest \(E_0\cup E_1\cup E_2\cup E_3\).

Zadanie 3 (20 punktów)
Rozważamy nieskończone pełne drzewo binarne z dodatkową relacją unarną \(\mathfrak{T}_U=\langle T,L,P,U\rangle\) (ta dziwna litera to gotyckie T, w rozwiązaniu można pisać zwykłe T). Sygnatura zawiera dwa dwuargumentowe symbole relacyjne \(L\) i \(P\), przy czym \(L(x,y)\) oznacza że \(y\) to lewy syn ojca \(x\), podobnie dla \(P\) oznaczającego prawego syna. Każdy wiechołek zawsze ma 2 synów: jednego lewego i jednego prawego. W sygnaturze znajduje się ponadto jeden symbol jednoargumentowej relacji \(U\), o którego interpretacji nic szczególnego nie zakładamy.

Skonstruować zdanie \(\varphi\) monadycznej logiki drugiego rzędu MSO o następującej własności:

\(\mathfrak{T}_U\models\varphi\) wtw na pewnej scieżce w drzewie \(\mathfrak{T}_U\) jest nieskończenie wiele elementów zbioru \(U\).

Prawdziwość zdania \(\varphi\) w strukturach innych niż te o postaci \(\mathfrak{T}_U\) jest nieistotna.

Szkic rozwiązania

Zdefiniujmy pomocnicze formuły:
\(Root(x)\) jako \(\lnot \exists y L(y,x)\lor P(y,x)\).

\(Path(x,X)\) (\(X\) jest ścieżką zaczynającą się w \(x\)) jako
\(X(x)\land \forall y(X(y)\to(\exists z(L(y,z)\land X(z))\leftrightarrow\lnot(P(y,z)\land X(z)))\land\forall y((X(y)\land y\neq x)\to\exists z(X(z)\land (L(z,y)\lor P(z,y)))))\)

Teraz wyrażamy żadaną własność jak następuje:

\(\exists x (Root(x)\land\exists X (Path(x,X))\land \forall y(X(y)\to (\exists Y\exists z Path(y,Y)\land U(z)\land X(z)\land Y(z))))\).

Zadanie 4 (20 punktów)
Spektrum \(Spec(\varphi)\) zdania \(\varphi\) to zbiór wszystkich liczb naturalnych \(n\) takich, ze \(\varphi\) ma model o mocy \(n.\)

Niech dana będzie zdanie \(\varphi\) logiki pierwszego rzędu. Skonstruować zdanie \(\psi\) logiki pierwszego rzędu (sygnatura jest do wyboru) takie, że \(Spec(\psi)=\{ 2\cdot n~/~n\in Spec(\varphi)\}.\)

Szkic rozwiązania

Wybieramy jednoragumentowy symbol relacyjny \(U\) i jednoragumentowy symbol funkcyjny \(f\) nie występujące w \(\varphi\).

Najpierw tworzymy z \(\varphi\) jej realtywizację \(\varphi_U\): kwantyfikatory \(\forall x\xi\) zastępujemy przez \(\forall x(U(x)\to\xi)\), a \(\exists x\xi\) przez \(\exists x(U(x)\land\xi)\). W razie gdyby w \(\varphi\) były symbole funkcyjne lub stałych, zastępujemy je uprzednio symbolami relacyjnymi w znany sposób.

Teraz żądane zdanie \(\psi\) wygląda tak:

\(\forall x (f(f(x))=x \land U(x)\leftrightarrow\lnot U(f(x)))\land \varphi_U\).

W tym zdaniu pierwsza częśc wyraża fakt, że \(f\) jest permutacją, ma cykle długości dwa i w każdym cyklu dokładnie jeden element należy do \(U\). Teraz \(\varphi_U\) orzeka, że podstruktura składająca się z elementów należących do \(U\) spełnia \(\varphi\), czyli liczba jej elementów należy do \(Spec(\varphi)\). Natomiast cały model ma dwa razy więcej elementów.

Zadanie 5 (20 punktów)
Gracz II ma strategię wygrywającą w grze Ehrenfeuchta-Fraissego o 4 rundach \(G_4(\mathfrak{A},\mathfrak{B})\), gdzie \(\mathfrak{A}\) jest poniższym grafem nieskierowanym:

    *        *        *    
    |        |        |    
 *--*--*  *--*--*  *--*--*

zaś \(\mathfrak{B}\) jest grafem nieskierowanym mającym \(n\) wierzchołków.
Ile krawędzi może mieć graf \(\mathfrak{B}\)?

Szkic rozwiązania

Skoro gracz II wygrywa grę \(G_4(\mathfrak{A},\mathfrak{B})\), to \(\mathfrak{A}\equiv_4\mathfrak{B}\). Poniżej wypisane są zdania o randze kwantyfikatorowej nie przekraczającej 4, które są prawdziwe w \(\mathfrak{A}\), zatem muszą być także prawdziwe w \(\mathfrak{B}\).

\(\exists x_1\exists x_2\exists x_3(\bigwedge_{i\le j}x_i\neq x_j\land\forall y(E(x_1,y)\lor E(x_2,y)\lor E(x_3,y)\lor x_1=y\lor x_2=y\lor x_3=y))\)
zatem są trzy wierzchołki w \(\mathfrak{B}\) takie, że każdy inny wierzchołek jest incydentny do jednego z nich...

\(\lnot\exists x_1\exists x_2(\bigwedge_{i\le j}x_i\neq x_j\land\forall y(E(x_1,y)\lor E(x_2,y)\lor x_1=y\lor x_2=y))\)

... ale nie ma dwóch takich wierzchołków. Zatem \(\mathfrak{B}\) składa się z trzech "centralnych" wierzchołków i połączonych z nimi w gwiazdę pozostałych wierzchołków, z ew. dodatkowymi krawędziami.

\(\lnot\exists x_1\exists x_2\exists x_3(\bigwedge_{i\le j}x_i\neq x_j\land E(x_1,x_2)\land E(x_2,x_3)\land E(x_3,x_1))\)
czyli nie ma trójkąta. Zatem wierzchołki będące promieniami tej samej gwiazdy są ze sobą niepołączone.

\(\lnot\exists x_1\exists x_2\exists x_3\exists x_4(\bigwedge_{i\le j}x_i\neq x_j\land E(x_1,x_2)\land E(x_2,x_3)\land E(x_3,x_4))\)
czyli nie ma ścieżek z trzech krawędzi. Zatem wierzchołki będące promieniami różnych gwiazd są ze sobą niepołączone krawędziami.

\(\forall x \exists y E(x,y)\)
czyli nie ma izolowanych wierzchołków...

\(\forall x \forall y (E(x,y)\to\exists z (z\neq x\land z\neq y\land (E(z,y)\lor E(z,x))\)
ani izolowanych krawędzi...

\(\forall x_1\forall x_2\forall x_3((\bigwedge_{i\le j}x_i\neq x_j\land E(x_1,x_2)\land E(x_2,x_3))\to (\exists x_4\bigwedge_{i}x_i\neq x_4 \land E(x_2,x_4))\)
oraz nie ma wierzchołków stopnia 2. Zatem promienie różnych gwiazd nie są tożsame, bo dawałyby z innymi promieniami ścieżki długości 3, ani też centra gwiazd nie sa połączone ze sobą ani z promieniami gwiazd innych niż własna.

Zatem \(\mathfrak{B}\) jest sumą trzech rozłącznych gwiazd, mających w sumie \(n\) wierzchołków. Na podstawie danych o grze nie da się dokładnie wyznaczyć rozkładu liczb promieni w gwiazdach, ale na pewno można powiedzieć, że wszystkich krawędzi jest \(n-3\).

Kolowium 2012/2013

Monoid to struktura \(\mathfrak{M}=\langle M,\circ,e\rangle\), w której
dwuargumentowa operacja \(\circ\) jest łączna, a stała \(e\) jest jej
elementem neutralnym.

Monoid \(\mathfrak{M}\) jest skończenie generowany, jeśli istnieje
skończenie wiele elementów \(a_1,\ldots,a_n\in M\) takich, że każde
\(a\in M\) można wyrazić za pomocą \(\circ\) stosowanej do tych
elementów. Na przykład monoid \(\langle
A^*,\cdot,\varepsilon\rangle\) słów nad alfabetem \(A\) z konkatenacją i
słowem pustym jest skończenie generowany wtedy i tylko wtedy, gdy \(A\)
jest skończony.

Monoid \(\mathfrak M=\langle M,\circ,e\rangle\) jest definiowany w
\(\mathfrak{N}\) formułami \(\mu(x), \ \nu(x,y,z)\) i \(\epsilon(x)\) nad
sygnaturą arytmetyki, jeśli
\(M=\{a\in\mathbb{N}~|~(\mathfrak{N},x:a)\models\mu\}\), dla
dowolnych \(a,b,c\in M\) zachodzi: \(a\circ b=c\) wtedy i tylko wtedy, gdy
\((\mathfrak{N},x:a,y:b,z:c)\models\ \nu\) oraz \(e\) jest jedynym elementem
\(M\) dla którego \((\mathfrak{N},x:e)\models\epsilon.\)

Zad. 1

Wykaż, ze klasa monoidów skończenie generowanych nie jest
aksjomatyzowalna żadnym zbiorem zdań.

Zad. 2

Dla danych \(\mu(x),\ \nu(x,y,z)\) i \(\epsilon(x)\) nad sygnaturą arytmetyki, które
definiują monoid w \(\mathfrak{N}\), napisz zdanie \(\gamma\) nad sygnaturą
arytmetyki, używające ich jako podformuł, takie że

\(\mathfrak{N}\models \gamma\) wtedy i tylko wtedy, gdy monoid definiowany
przez \(\mu,\ \nu\) i \(\epsilon\) jest skończnie generowany.

Zad. 3

Rozważamy dwa grafy \(\mathfrak{T}_1=\langle T_1,E_1\rangle\) i
\(\mathfrak{T}_2=\langle T_2,E_2\rangle\) określone jak następuje:

\(T_1=\{1,2,\ldots,15\},\) \(E_1=\{\langle n,2n+1\rangle~|~n,2n+1\in T_1\}\)

\(T_2=\{1,2,\ldots,11\},\) \(E_2=\{\langle n,2n+1\rangle~|~n,2n+1\in T_2\}\)

Napisz zdanie o minimalnej randze kwantyfikatorowej, które rozróżnia
\(\mathfrak{T}_1\) i \(\mathfrak{T}_2\). Należy uzasadnić poprawność
zdania, można nie uzasadniać jego minimalności.

Mid-term test 2012/2013

A {\em monoid} is a structure \(\mathfrak{M}=\langle M,\circ,e\rangle\),
where binary operation \(\circ\) is associative and constant \(e\) is its
neutral element.

Monoid \(\mathfrak{M}\) is finitely generated, if there exist
finitely many elements \(a_1,\ldots,a_n\in M\) such that every \(a\in M\) can be
expressed using those elements and \(\circ\). For example, the monoid
\(\langle A^*,\cdot,\varepsilon\rangle\) of words over an alphabet \(A\) with
concatenation and empty word is a finitely generated iff \(A\) is finite.

Monoid \(\mathfrak M=\langle M,\circ,e\rangle\) is defined in
\(\mathfrak N\) by formulas \(\mu(x),\ \nu(x,y,z)\) and \(\epsilon(x)\) over the
signature of arithmetics, if
\(M=\{a\in\mathbb{N}~|~(\mathfrak{N},x:a)\models\mu\}\), for every
\(a,b,c\in M\) the equality \(a\circ b=c\) holds if and only if
\((\mathfrak{N},x:a,y:b,z:c)\models\nu\) and \(e\) is the only element of
\(M\) such that \((\mathfrak{N},x:e)\models\epsilon.\)

Problem 1

Prove that the class of finitely generated monoids is not
axiomatizable by any set od sentences of FO.

Problem 2

For given \(\mu(x),\ \nu(x,y,z)\) and \(\epsilon(x)\) over the signature
of arithmetics, which define a monoid in \(\mathfrak{N}\), write a
sentence \(\gamma\) over the signature of arithmetics, which may use
them as subformulas, and such that

\(\mathfrak{N}\models \gamma\) if and only if the monoid defined by
\(\mu,\ \nu\) and \(\epsilon\) is finitely generated.

Problem 3

We consider two graphs \(\mathfrak{T}_1=\langle T_1,E_1\rangle\) and
\(\mathfrak{T}_2=\langle T_2,E_2\rangle\) defined as follows:

\(T_1=\{1,2,\ldots,15\},\) \(E_1=\{\langle n,2n+1\rangle~|~n,2n+1\in T_1\}\)

\(T_2=\{1,2,\ldots,11\},\) \(E_2=\{\langle n,2n+1\rangle~|~n,2n+1\in T_2\}\)

Write a sentence of minimal possible quantifier rank, which
distinguishes \(\mathfrak{T}_1\) and \(\mathfrak{T}_2\). You should prove
the correcntess of your sentence, but you do not have to prove its
minimality.

Egzamin 2012/2013

Zadanie 1 (10 punktów) Niech sygnatura \(\Sigma\) składa
się tylko z symboli relacyjnych: dwuargumentowego \(E\) i
jednoargumentowego \(P.\) Dla każdej z podanych poniżej klas struktur
określ, czy jest ona (i) aksjomatyzowalna jednym zdaniem logiki
pierwszego rzędu, (ii) aksjomatyzowalna zbiorem zdań logiki pierwszego
rzędu, ale nie pojedynczym zdaniem, (iii) nieaksjomatyzowalna żadnym
zbiorem zdań pierwszego rzędu.

Klasa struktur \(\mathfrak{A}=(A, E^{\mathfrak{A}}, P^{\mathfrak{A}})\) nad sygnaturą \(\Sigma\), w
których \(E^{\mathfrak{A}}\) jest symetryczna i takich, że:

w każdej spójnej składowej \((A,E^{\mathfrak{A}})\) każdy wierzchołek
spełnia \(P^{\mathfrak{A}}\).
istnieje spójna składowa \((A,E^{\mathfrak{A}})\), w której pewien
wierzchołek spełnia \(P^{\mathfrak{A}}\).
istnieje spójna składowa \((A,E^{\mathfrak{A}})\), w której każdy
wierzchołek spełnia \(P^{\mathfrak{A}}\).

Uwaga: czwarty element tego zestawu jest pytaniem w teście, a trzy
powyższe podpunkty nie są mają równych wag w łącznej punktacji zadania.

Rozwiązanie

Aksjomatyzowalna zdaniem \(\forall x P(x)\)
Aksjomatyzowalna zdaniem \(\exists x P(x)\)
Nie jest aksjomatyzowalna żadnym zbiorem zdań. Wskażemy dwie elementarnie równoważne struktury, z których w jednej istnieje spójna składowa \((A,E^{\mathfrak{A}})\), w której każdy
wierzchołek spełnia \(P^{\mathfrak{A}}\), a w drugiej takiej składowej nie ma.

Poniżej * to element spełniający \(P^{\mathfrak{A}}\), a o to niespełniający.

Pierwsza struktura (ma taką składową):
```
   ...-*-*-*-*-...     ...-*-*-o-o-...   ...-o-o-o-o-...
```
Druga struktura (nie ma takiej składowej):
```
   ...-*-*-*-*-...     ...-*-*-o-o-o-o-o-o-o-o-o-o-...
```
Teraz ustalamy dowolne \(m\) i gramy w grę Ehrenfeuchta-Fraissego o \(m\) rundach na tych dwóch strukturach. Strategia II gracza to imitować w dolnej strukturze istnienie trzeciej, brakującej składowej za pomoca ruchów daleko od punktu przejścia *-o.

Zadanie 2 (10 punktów) Rozważmy strukturę
\(\mathfrak{R}=\langle\mathbb{R},+,*,0,1\rangle\), gdzie nośnik to zbiór
liczb rzeczywistych, ze standardową interpretacją symboli z
sygnatury. Napisz formułę \(\varphi(x)\) monadycznej logiki drugiego rzędu
MSO, z jedną zmienną wolną (pierwszego rzędu) taką, że

\((\mathfrak{R},x:a)\models\varphi~~\text{wtw}~~a\in\mathbb{Q}.\)

Rozwiązanie

Sednem rozwiązania jest odwołanie się do zbioru liczb całkowitych. Niech \(Cls(X)\) oznacza formułę

\(0\in X\land \forall n(n\in X\to (n+1)\in X\land \exists m (n=m+1\land m\in X))\)

Formuła ta oznacza, że \(X\) zawiera 0 i jest zamknięta na następnik i poprzednik. Jest wiele takich zbiorów, na przykład \(\mathbb{Z},\ \mathbb{R}\) i inne.

Teraz formuła

\(\exists X (Cls(X)\land(\forall Y Cls(Y)\to \forall u (u\in X\to u\in Y))\land (\exists p\exists q p\in X\land q\in X\land p\neq0\land x*q=p))\)

orzeka, że istnieje \(X\), który spełnia \(Cls(X)\), jest zawarty w każdym \(Y\) spełniającym \(Cls(Y)\) (czyli jest prawdziwym zbiorem liczb całkowitych) i \(x\) jest ilorazem dwóch elementów \(X\). Zatem właśnie tej formuły poszukiwaliśmy.

Alternatywnie można napisać

\(\forall X (Cls(X)\to (\exists p\exists q p\in X\land q\in X\land p\neq0\land x*q=p))\)

orzekając, że \(x\) jest można wyrazić jako iloraz dwóch elementów każdego zbioru spełniającego \(Cls(X)\), zatem także jako iloraz dwóch liczb całkowitych.

Zadanie 3 (10 punktów) Udowodnij, że dla każdego
\(n\)-argumentowego wyrażenia \(E\) algebry relacyjnej, dla dowolnych

\(1\leq i_1\le \cdots\le i_m\leq n\) i dla dowolnego ustalonego
\(k\in\mathbb{N}\), wyrażenie

\(
{\tt group}\ E\ {\tt by}\ i_1,\ldots, i_m\ {\tt having~count(*)}>k
\)
także jest definiowalne w algebrze relacyjnej.

Powyższe wyrażenie jest \(m\)-argumentowe, a jego semantyką jest
zdefiniowana przez:

\(\{ (a_{i_1},\ldots,a_{i_m}) \mid \text{istnieje \(>k\) krotek
\(\langle b_1,\ldots,b_n\rangle\in[\![E]\!]\) t. że}~a_{i_1}=b_{i_1},\ldots,a_{i_m}=b_{i_m} \}
\)

Zadanie 4 (10 punktów) Rozważamy monadyczną logikę drugiego
rzędu (MSO) nad skończonymi modelami-słowami.

Każdemu elementowi \(a\) uniwersum modelu-słowa można przypisać
liczbę \(\bar{a}\in\mathbb{N}\) równą jego pozycji w słowie (pozycje
numerujemy od \(1\)).

Udowodnij, że nie istnieje formuła \(\varphi(x,y,z)\) logiki MSO taka, że
dla każdego modelu-słowa \(\mathfrak{A}(w)\) i dowolnych \(a,b,c\in A\)

\(
(\mathfrak{A}(w),x:a,y:b,z:c)\models\varphi~~\text{wtw}~~\bar{a}+\bar{b}\equiv\bar{c} \pmod {|w|}.
\)

Rozwiązanie

Przypuśćmy, że takie \(\varphi\) istnieje. Dojdziemy do sprzeczności, pokazując, że wówczas w MSO można by było zdefiniować język nieregularny, wbrew tw. Buechi-Elgota.

Rozważmy formułę \(mid(z)\)

\(\exists x (\forall y y\leq x)\land (z\neq x \land \varphi(z,z,x))\)

która orzeka, że \(z\) jest położone w połowie długości danego słowa. Teraz

\(\exists z mid(z)\land \forall y (y\leq z\to X(y))\land(y>z\to \lnot X(y))\)

mówi, że istnieje \(z\) położony w połowie długości słowa, na lewo od niego \(X\) wszędzie zachodzi, na prawo \(X\) nigdzie nie zachodzi. Zatem to zdanie definiuje język typu \(\{a^nb^n~|~n\in\mathbb{N}\}\)
który jest oczywiście nieregularny.

TEST

Pytanie 1 (2 punkty) Niech dla zdania \(\varphi\) logiki pierwszego rzędu
\(
Spec(\varphi) = \{n\in\mathbb{N}^+ \mid \mbox{ istnieje \(\mathcal{A}\) o mocy \(n\) takie że } \mathcal{A}\models\varphi\}.
\)
Czy następujący problem jest rozstrzygalny:

Dane: zdanie \(\varphi\)

Pytanie: czy \(Spec(\varphi)\cup Spec(\neg\varphi)=\mathbb{N}_+\)?

Odpowiedź

TAK. Wypisana równość zachodzi zawsze, dla każdego zdania \(\varphi\).

Pytanie 2 (2 punkty) W sytuacji z Zadania 1, czy własność
w każdej spójnej składowej \((A,E^{\mathfrak{A}})\) istnieje wierzchołek
spełniający \(P^{\mathfrak{A}}\) jest aksjomatyzowalna zbiorem zdań logiki
pierwszego rzędu?

Odpowiedź

NIE.

Dowód przez tw. o zwartości. Załóżmy, że taki zbiór \(\Delta\) istnieje.

Niech zdanie \(away_k\) oznacza, że w odległości \(k\) od stałej \(c\) nie ma elementu spełniającego \(P\).
Można je napisać tak:

\(\forall x_1\ldots \forall x_k ((E(c,x_1)\land E(x_1,x_2)\land\ldots\land E(x_{n-1},x_n))\to(\bigwedge_{i=1}^k\lnot P(x_i))).\)

Rozważmy \(\bar{\Delta}=\Delta\cup\{away_k~|~k\in \mathbb{N}\}\).

Łatwo wykazać, że każdy skończony podzbiór \(\bar{\Delta}\), ma model, bo wystarczy brać grafy złożone z jednej składowej w postaci długiego łańcucha, gdzie \(c\) jest na jednym jego końcu, a drugi koniec spełnia \(P\).

Zatem z tw. o zwartości \(\bar{\Delta}\) ma model. Jednak w tym modelu składowa \(c\) nie zawiera żadnego elementu spełniającego \(P\) - sprzeczność.

Pytanie 3 (2 punkty) Czy gracz I ma strategię wygrywającą w grze
Ehrenrfeuchta-Fra\"{\i}ss\'e o 3 rundach na dwóch poniższych
nieskierowanych grafach 8-wierzchołkowych?
\[
\xymatrix@=10pt{
\bullet & & \bullet \\
\bullet\ar@{-}[u]\ar@{-}[d] & \bullet & \bullet\ar@{-}[u]\ar@{-}[d]\ar@{-}[l]\ar@{-}[r] & \bullet \\
\bullet & & \bullet
} \qquad \qquad
\xymatrix@=10pt{
\bullet & & \bullet \\
\bullet\ar@{-}[u]\ar@{-}[d]\ar@{-}[r] & \bullet & \bullet\ar@{-}[u]\ar@{-}[d]\ar@{-}[r] & \bullet \\
\bullet & & \bullet
}
\]

Pytanie 4 (2 punkty) Czy dla każdej formuły \(\varphi\) logiki
pierwszego rzędu istnieją: liczba naturalna \(k\), ciąg kwantyfikatorów
\(Q_1,\ldots,Q_k\in\{\forall,\exists\}\) i zmiennych \(x_1,\ldots, x_k\)
oraz formuła \(\psi\), w której nie występują kwantyfikatory, takie że
tautologią jest

\(
\varphi \leftrightarrow Q_1x_1\cdots Q_kx_k\psi \qquad ?
\)

Odpowiedź

TAK. Było na wykładzie.

Pytanie 5 (2 punkty) Czy w logice pierwszego rzędu istnieje
tautologia, która nie ma dowodu w systemie Hilberta?

Odpowiedź

NIE. Twierdzenie Goedla o pełności orzeka, że każda tautologia pierwszego rzędu ma dowód w systemie Hilberta.

Egzamin poprawkowy 2012/2013

Zadanie 1 (10 punktów) Niech sygnatura \(\Sigma\) składa
się tylko z symboli relacyjnych: dwuargumentowego \(E\) i jednoargumentowego \(P\). Rozważmy klasę \(\mathcal{A}\) struktur \(\mathfrak{A}=(A, E^{\mathfrak{A}}, P^{\mathfrak{A}})\) nad sygnaturą \(\Sigma\), w których \(E^{\mathfrak{A}}\) jest symetryczna i takich, że w każdej spójnej składowej \((A,E^{\mathfrak{A}})\) istnieje wierzchołek spełniający \(P^{\mathfrak{A}}\).

Określ, czy klasa \(\mathcal{A}\) jest (i) aksjomatyzowalna jednym zdaniem logiki pierwszego rzędu, (ii) aksjomatyzowalna zbiorem zdań logiki pierwszego rzędu, ale nie pojedynczym zdaniem, (iii) nieaksjomatyzowalna żadnym zbiorem zdań pierwszego rzędu.

Zadanie 2 (10 punktów) Prosty graf nieskierowany (zwany dalej grafem) to struktura \(\mathfrak{G}\) nad
sygnaturą z jednym dwuargumentowym symbolem relacyjnym \(E\), taka że relacja \(E^{\mathfrak{G}}\) jest symetryczna (tzn. jeśli \((x,y)\in E^{\mathfrak{G}}\) to \((y,x)\in E^{\mathfrak{G}}\)) i antyzwrotna (tzn. nie ma takich \(x\) że \((x,x)\in E^{\mathfrak{G}}\)). Dopełnieniem grafu \(\mathfrak{G}\) jest graf \(\overline{\mathfrak{G}}\) o tym samym zbiorze wierzchołków co \(\mathfrak{G}\), w którym występują dokładnie te krawędzie, które nie występują w \(\mathfrak{G}\).

Dla (i) \(n=5\) oraz dla (ii) \(n=6\) narysuj taki graf \(\mathfrak{G}\) o \(n\) wierzchołkach, żeby Gracz II miał strategię wygrywającą w grze Ehrenfeuchta-Fra\"{\i}ss\'e o możliwie wielu rundach na grafie \(\mathfrak{G}\) i jego dopełnieniu \(\overline{\mathfrak{G}}\). Im więcej rund uzyskasz, tym lepsze rozwiązanie. Napisz ile rund uzyskałeś/aś i, o ile to możliwe, podaj formułę logiczną o możliwie małej głębokości kwantyfikatorowej, która rozróżnia \(\mathfrak{G}\) i \(\overline{\mathfrak{G}}\).

Zadanie 3 (10 punktów) Napisz zdanie w monadycznej logice drugiego rzędu MSO, które definiuje klasę \(\mathcal{A}\) z zadania 1.

Zadanie 4 (10 punktów) Niech \(\mathfrak{A}=\langle \mathbb{Z}\times\mathbb{Z},E^\mathfrak{A},U^\mathfrak{A}\rangle,\) gdzie \(E\) jest symbolem relacji dwuargumentowej a \(U\) jest symbolem relacji jednoargumentowej. \(\langle x,y\rangle E^\mathfrak{A}\langle x',y'\rangle\) zachodzi wtedy i tylko wtedy, gdy (\(x=x'\) i \(|y-y'|=1\)) lub (\(|x-x'|=1\) i \(y=y'\)). Zatem \(\langle \mathbb{Z}\times\mathbb{Z},E^\mathfrak{A}\rangle\) to przeliczalny graf nieskierowany w kształcie kraty.

(i) Napisz zdanie \(\varphi\) logiki pierwszego rzędu wyrażające własność, że \(U^\mathfrak{A}\) jest sumą pewnego zbioru pełnych wierszy lub pewnego zbioru pełnych kolumn kraty \(E^\mathfrak{A}\).

(ii) Udowodnij, że nie istnieje zdanie \(\varphi\) logiki pierwszego rzędu wyrażające własność, że \(U^\mathfrak{A}\) jest sumą pewnego zbioru pełnych kolumn kraty \(E^\mathfrak{A}\).

TEST

Pytanie 1 (2 punkty) Czy istnieje liczba \(k\) taka, że dla każdego zdania \(\varphi\) logiki
pierwszego rzędu istnieje formuła \(\psi\) w której nie występują
kwantyfikatory, ciąg kwantyfikatorów
\(Q_1,\ldots,Q_k\in\{\forall,\exists\}\) i ciąg zmiennych \(x_1,\ldots,
x_k\) taki że tautologią jest
\[
\varphi \leftrightarrow Q_1x_1\cdots Q_kx_k\psi \qquad ?
\]

Pytanie 2 (2 punkty) Czy następujące zdanie logiki drugiego rzędu SO, nad sygnaturą z jednym dwuargumentowym symbolem relacyjnym \(E\), jest tautologią?
\begin{align*}
\exists R &[\forall x\forall y(E(x,y)\to R(x,y))
\ \land\ \forall x\forall y\forall z(R(x,y)\land R(y,z)\to R(x,z))
\ \land\ \exists x\exists y\neg R(x,y)] \\
\rightarrow \\
\exists P &[\exists x P(x)\ \land\ \exists x\neg P(x)
\ \land\ \forall x\forall y(P(x)\land E(y,x)\to P(y))]
\end{align*}

Pytanie 3 (2 punkty) Czy rozstrzygalny jest następujący problem:

Dane: zdanie \(\varphi\) logiki drugiego rzędu SO oraz skończony model \(\mathfrak{A}\) nad tą samą sygnaturą.

Pytanie: czy \(\mathfrak{A} \models \varphi\)?

Pytanie 4 (2 punkty) Czy dla każdej sygnatury \(\Sigma\) i każdej struktury \(\mathfrak{A}\) mocy \(\mathfrak{c}\) nad \(\Sigma\) istnieje przeliczalna struktura \(\mathfrak{B}\) nad \(\Sigma\) taka, że \(\mathfrak{A}\equiv\mathfrak{B}\)?

Pytanie 5 (2 punkty) Czy język słów nad alfabetem \(\{0,1\}\), które są palindromami jest definiowalny w logice pierwszego rzędu nad sygnaturą modeli-słów, w tym wypadku złożoną z binarnego \(\leq\) i unarnego \(X\)? Zakładamy, że prawdziwość \(X\) oznacza literę 1, a fałszywość literę 0.

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

Egzamin 2013/2014

Zadanie 1 (10 punktów) Dana jest struktura \(\mathfrak{A}=\langle \{a,b\}^*,\cdot,a,b,\varepsilon\rangle\) słów nad alfabetem \(\{a,b\}\) z operacją konkatenacji oraz słowami jednoliterowymi \(a\) i \(b\) i słowem pustym jako stałymi. Udowodnij, że dla każdego regularnego języka \(L\subseteq\{a,b\}^*\) istnieje formuła \(\varphi(x)\) logiki MSO z jedną zmienną wolną \(x\) taka, że \(L=\{w~|~(\mathfrak{A},x:w)\models\varphi\}.\)

Szkic rozwiązania

Tłumaczymy dane wyrażenie regularne \(r\) na zdanie MSO.
Dla \(r=a\) and \(r=b\) teza jest oczywista.
Dla \(r=s\cup t\) używamy \(\varphi_s\lor \varphi_t.\)
Dla \(r=st\) używamy \(\exists y\exists z (x=yz\land \varphi_s(y)\land\varphi_t(z)).\)
Dla \(r=s^*\) musimy użyć kwantyfikatora po zbiorach:
Nieformalnie, wyrażamy
"\(\exists X\) (\(X\) jest minimalnym zbiorem takim, że \(((\varepsilon\in X\land\forall y \forall z (y\in X\land \varphi_s(z)\to yz\in X))\land x\in X\)".

Zadanie 2 (10 punktów)
Relacja \(E\subseteq A\times A\) ma 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 nie istnieje zbiór zdań logiki pierwszego rzędu \(\Delta\) taki, że \(\langle A,E\rangle\models\Delta\) wtedy i tylko wtedy, gdy relacja \(E\) ma własność Churcha-Rossera.

Szkic rozwiązania

Rozwiązanie 1. Gra Ehrenfeuchta-Fraisse.
Gramy na dwóch strukturach

  *        *-*       *-*-*
 / \      /   \     /     \
*   *    *     *   *       *   ...
 \ /      \   /     \     /
  *        *-*       *-*-*

  *        *-*       *-*-*                  *-*-*-*-*...
 / \      /   \     /     \                /     
*   *    *     *   *       *   ...        *
 \ /      \   /     \     /                \
  *        *-*       *-*-*                  *-*-*-*-*...

w kórych wszystkie krawędzie są skierowane na prawo. Górna struktura ma własność Churcha-Rossera, dolna nie.

Gracz II ma strategię wygrywającą w grze o dowolnej liczbie rund. Ruchy gracza I w nieskończonym komponencie w dolnej strukturze naśladuje w dostatecznie dużym komponencie struktury górnej.

Rozwiązanie 2. Twierdzenie o zwartości.

Załóżmy, że \(\Delta\) jest aksjomatyzacją własności Churcha-Rossera.
Dodajemy do sygnatury trzy stałe \(a,b,c\) oraz do \(\Delta\) zdania \(\{E(a,b),E(a,c),\varphi_n~|~n\in\mathbb{N}\}\), gdzie \(\varphi_n\) mówi, że nie istnieje \(d\), które jest z \(b\) i \(c\) osiągalne w odelgłości mniej niż \(n\) krawędzi. W ten sposób dostajemy \(\bar\Delta\).

Każdy skończony podzbiór \(\bar\Delta\) jest spełnialny: wystarczy w górnej strukturze użytej w rozwiązaniu za pomocą gry stałe \(a,b,c\) zinterpretować jako trzy pierwsze od lewej wierzchołki składowej o wystrczająco dużej długości.

Z tw. o zwartości całe \(\bar\Delta\) jest spełnialne. ale to sprzeczność: z \(a\) można przejść do \(b\) i \(c\), ale w żadnej skończonej liczbie kroków nie można od nich "zejść się" do wspólnego wiezchołka.

Zadanie 3 (10 punktów)
Słaba monadyczna logika drugiego rzędu (Weak Monadic Second Order Logic, w skrócie WMSO) ma tę samą składnię co logika MSO. Pod względem semantyki, kwantyfikatory po zbiorach/relacjach unarnych \(\forall X\) i \(\exists X\) znaczą odpowiednio dla każdego skończonego podzbioru uniwersum i istnieje skończony podzbiór uniwersum.

Udowodnić, że dla każdej formuły \(\varphi(\vec{x})\) logiki WMSO nad sygnaturą arytmetyki (czyli bez wolnych zmiennych drugiego rzędu) istnieje formuła \(\psi(\vec{x})\) logiki pierwszego rzędu nad sygnaturą arytmetyki taka, że \(\mathfrak{N}\models\forall \vec{x}(\varphi(\vec{x})\leftrightarrow\psi(\vec{x})).\)

Szkic rozwiązania

Każdy kwantyfikator drugiego rzędu \(\exists X\) zastępujemy przez \(\exists t_X\exists p_X\exists m_X\). Intencja jest taka, że \(t_X\) i \(p_X\) kodują ciąg elementów tworzących zbiór \(X\), a \(m_X\) jest jego długością. Wówczas każdą formułę atomową \(x\in X\) występującą w zasięgu tego kwantyfikatora zastępujemy przez \(\exists i( i\lt m_X \land\chi(t_X,p_X,i,x))\).

Zadanie 4 (10 punktów)
Jednostronna gra Ehrenfeuchta-Fra\"{\i}ss\'e o \(k\) rundach na strukturach \(\mathfrak{A}_0\) i \(\mathfrak{A}_1\) to zmodyfikowana gra standardowa, w której gracz I po wybraniu w pierwszej rundzie elementu struktury \(\mathfrak{A}_i\) musi już do końca wybierać elementy \(\mathfrak{A}_i\), a gracz II odpowiada w standardowy sposób ciągle w \(\mathfrak{A}_{1-i}\).

Podać przykład dwóch struktur \(\mathfrak{A}_0\) i \(\mathfrak{A}_1\) takich, że gracz II ma dla każdego \(k\) strategię wygrywającą w jednostronnej grze Ehrenfeuchta-Fra\"{\i}ss\'e o \(k\) rundach na strukturach \(\mathfrak{A}_0\) i \(\mathfrak{A}_1\), mimo tego, że dla pewnego \(m\) gracz I ma strategię wygrywającą w standardowej grze Ehrenfeuchta-Fra\"{\i}ss\'e o \(m\) rundach na strukturach \(\mathfrak{A}_0\) i \(\mathfrak{A}_1\).

Rozwiązania będą oceniane także przez pryzmat osiągniętej wartości \(m,\) maksimum można dostać tylko za \(m=2.\)

Szkic rozwiązania

Niech naszymi strukturami będą \(\langle\mathbb{Z},succ\rangle\) i \(\langle\mathbb{N},succ\rangle\).

W zwykłej grze gracz I wygrywa w dwóch rundach: najpierw zaznacza 0 w \(\mathbb{N}\), a w drugiej rundzie zaznacza w \(\mathbb{Z}\) poprzednik elementu wskazanego przez gracza II jako odpowiedź na 0.

Rozważmy teraz grę jednostronną o \(m\) rundach.

Jeśli w pierwszej rundzie gracz I zagra w \(\mathbb{N}\), to gracz II ma oczywistą strategię polegającą na kopiowaniu w \(\mathbb{Z}\) ruchów gracza I.

Jeśli w pierwszej rundzie gracz I zagra w \(\mathbb{Z}\), to gracz II musi odpowiedzieć daleko od 0 w \(\mathbb{N}\), przy czym daleko oznacza "dalej niż \(2^m\)". Dalej na ruchy gracza I na lewo od pierwszego wybranego punktu odpowiada w myśl strategii pozwalającej wygrać na łańcuchu o długości \(2^m\) i łańcuchu o dowolnej większej długości. Ruchy gracza I na prawo od pierwszego wybranego punktu gracz II po prostu kopiuje.

TEST

Za każdą trafną odpowiedź przyznajemy 2 punkty, za każdą nietrafną -2 punkty. Brak odpowiedzi to 0 punktów.

1. Niech \(\varphi\) będzie zdaniem logiki pierwszego rzędu i niech \(\mathit{Spec}(\varphi)=\{n\in\mathbb{N}~|\) istnieje model \(\mathfrak{A}\) mocy \(n\) taki, że \(\mathfrak{A}\models\varphi\}.\)
Czy rozstrzygalny jest następujący problem decyzyjny: Dane: zdanie \(\varphi\) logiki pierwszego rzędu; Pytanie: Czy \(\mathit{Spec}(\varphi)=\emptyset\)?

Szkic rozwiązania

NIE. Warunek \(\mathit{Spec}(\varphi)=\emptyset\) oznacza dokładnie to samo, co "\(\varphi\) nie ma żadnego skończonego modelu."
Ten ostatni problem jest nierozstrzygalny na mocy tw. Trachtenbrota.

2. Czy istnieje zbiór zdań logiki pierwszego rzędu nad skończoną sygnaturą, który ma skończone modele każdej mocy parzystej, ale nie ma modelu mocy \(\mathfrak{c}\)?

Szkic rozwiązania

NIE. Tak opisany zbiór musi mieć model nieskończony, co wynika z standardowego zastosowanie tw. o zwartości. Wówczas, na mocy tw. Skolema-Loewenheima, ma on także model mocy \(\mathfrak{c}\).

3. Niech \(\varphi\) będzie zdaniem logiki MSO nad sygnaturą modeli-słów i niech \(\mathit{Spec}_0(\varphi)=\{n\in\mathbb{N}~|\) istnieje model-słowo \(\mathfrak{A}(w)\) mocy \(n\) taki, że \(\mathfrak{A}(w)\models\varphi\}.\)

Czy rozstrzygalny jest następujący problem decyzyjny: Dane: zdanie \(\varphi\) logiki MSO nad sygnaturą modeli-słów; Pytanie: Czy \(\mathit{Spec}_0(\varphi)=\emptyset\)?

Szkic rozwiązania

TAK. Warunek \(\mathit{Spec}_0(\varphi)=\emptyset\) oznacza dokładnie to samo, co "\(\varphi\) nie ma żadnego modelu-słowa."

Wystarczy teraz, zgodnie z tw. Buechi-Elgota, przetłumaczyć zdanie MSO na równoważny automat, następnie go zdeterminizować i zminimalizowac. Jeśli wyjdzie jednoelementowy automat ze stanem nieakceptującym, to spektrum jest puste, w przeciwnym razie jest niepuste.

4. Czy \(\langle\mathbb{Q},<\rangle\equiv\langle\mathbb{R},<\rangle\)? (Porządek w obu strukturach jest naturalny.)

Szkic rozwiązania

TAK. Był sformułowany i udowodniony na wykładzie fakt, że każde dwa liniowe porządki gęste, bez elementu maksymalnego i bez minimalnego sa elementarnie rónoważne. \(\langle\mathbb{Q},<\rangle\) i \(\langle\mathbb{R},<\rangle\) spełniają te założenia.

5. Czy gracz II ma strategię wygrywającą w standardowej grze Ehrenfeuchta-Fraisse o dwóch rundach na następujących dwóch grafach nieskierowanych o 4 wierzchołkach:

 * - *                     * - *   
 |   |                     | \ |
 * - *                     * - *

Szkic rozwiązania

NIE. Gracz I może w pierwszym ruchu wybrać jeden z wierzchołków o stopniu 3 w drugim grafie. Jakkolwiek gracz II odpowie, gracz I w następnym ruchu wybiera w grafie pierwszym wierzchołek po przekątnej od tego wybranego w rundzie pierwszej, który jest z nim niepołączony krawędzią. Gracz II nie ma jak odpowiedzieć na to w grafie drugim.

Egzamin poprawkowy 2013/2014

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

grafy dwudzielne
grafy nie-dwudzielne

określ, czy jest ona

aksjomatyzowalna jednym zdaniem logiki pierwszego rzędu
aksjomatyzowalna zbiorem zdań logiki pierwszego rzędu, ale nie pojedynczym zdaniem
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?

Kolokwium 2014/2015

Zadanie 1

Rozważamy klasę \(\mathcal{A}\) wszystkich grafów \(\mathfrak{G}\) (gotyckie G), skończonych i nieskończonych, których wierzchołki można pokolorować pewną skończoną liczbą kolorów tak, że każdy trójkąt zawarty w \(\mathfrak{G}\) ma wierzchołki 3 różnych kolorów.

Udowodnij że \(\mathcal{A}\) nie jest aksjomatyzowalne żadnym zbiorem zdań logiki pierwszego rzędu nad sygnaturą składającą się wyłącznie z relacji krawędzi \(E\).

Szkic rozwiązania

Ogólna uwaga: Każda klika musi być pokolorowana tyloma kolorami ile ma elementów, żeby każdy trójkąt w niej zawarty był trójkolorowy.

Rozwiązanie I.

Przypuśćmy,że \(\Delta\) to żądana aksjomatyzacja. Niech

\(\bar\Delta=\Delta\cup\{\exists x_1\ldots\exists
x_n\bigwedge_{i,j}E(x_i,x_j)\}\).

Pokazujemy, że \(\bar\Delta\) spełnia założenia twierdzenia o zwartości: niech \(\Delta_0\subseteq\bar\Delta\) będzie dowolny, skończony.
Niech \(N\) to maksymalna liczna kwantyfikatorów w zdaniach z \(\Delta_0\) pochodzących spoza \(\Delta\). Wówczas klika mocy \(N\) spełnia \(\Delta_0\), bo daje się pokolorować skończoną liczbą kolorów bez powtarzania kolorów.

Na mocy twierdzenia o zwartości \(\bar\Delta\) ma model. Zawiera on kliki każdej skończonej mocy, więc żadna skończona liczba kolorów nie wystarcza do odpowiedniego pokolorowania modelu \(\bar\Delta\). Sprzeczność.

Rozwiązanie II.

Niech \(\mathfrak{A}\) to struktura składająca się z przeliczalnie wielu przeliczalnych klik jako składowych spójnych.

Pokazujemy, że dla każdego \(m\) istnieje struktura \(\mathfrak{B}\in\mathcal{A}\) taka, że dla każdego \(m\) istnieje struktura \(\mathfrak{B}_m\) tkaza, że gracz II ma strategię w grze Ehrenfeuchta-Fraisse o \(m\) rundach, granej na \(\mathfrak{A}\) i \(\mathfrak{B}_m\).

\(\mathfrak{B}_m\) to struktura składająca się z przeliczalnie wielu klik mocy \(m\) jako składowych spójnych.

Strategia gracza II jest banalna. Jej istnienie wskazuje, że nie istnieje zdanie o randze kwantyfikatorowej \(m\) lub mniejszej, które byłoby fałszywe w \(\mathfrak{A}\) a jednocześnie prawdziwe w każdej strukturze z \(\mathcal{A}\).

Zadanie 2

Niech dane będą dwa grafy: \(\mathfrak{G}\) (gotyckie G) będący szkieletem sześcianu (8 wierzchołków, 12 krawędzi) i \(\mathfrak{H}\) (gotyckie H) będący kopią \(\mathfrak{G}\) pozbawioną jednej krawędzi.

Napisz zdanie o minimalnym zagnieżdżeniu kwantyfikatorów, rozróżniające \(\mathfrak{G}\) i \(\mathfrak{H}\). Uzasadnij poprawność zdania, nie uzasadniaj minimalności zagnieżdżenia.

Szkic rozwiązania

Strategia gracza I na trzy rundy:

1. Jeden z wierzchołków o stopniu 2 w \(\mathfrak{H}\).
Odpowiedź gracza II dowolna.

2. Wierzchołek w \(\mathfrak{G}\) po przeciwnej stronie długiej przekątnej od wierzchołka wybranego przez II w poprzedniej rundzie.
Odpowiedź gracza II dowolna.

3. W \(\mathfrak{H}\) pierwszy wybrany wierzchołek ma stopień 2, drugi wybrany wierzchołek ma stopień najwyżej 3. Łącznie wybranych i incydentnych do wybranych jest co najwyżej 7 wierzchołków, podczas gdy wszystkich wierzchołków jest 8. Gracz I wybiera teraz wierzchołek, który nie
był dotąd wybrany ani nie jest incydentny z żadnym z wybranych wierzchołków.
Gracz II nie ma odpowiedzi, bo w \(\mathfrak{G}\) wszystkie wierzchołki sa albo wybrane albo incydentne z jednym z wybranych.

Strategia ta przekłada się na zdanie
\(\forall x\exists y\forall z (z=x\lor z=y\lor E(z,x) \lor E(z,y)),\)
które jest prawdziwe w \(\mathfrak{G}\) i fałszywe w \(\mathfrak{H}\).

Zadanie 3

Rozstrzygnij, czy następująca formuła jest twierdzeniem logiki intuicjonistycznej:

\((p\to q)\to((r\to q)\to(r\to p)).\)

Szkic rozwiązania

To zdanie nie jest nawet tautologią logiki klasycznej (wartościowanie \(r=1, p=0, q=1\)), więc tym bardziej nie jest twierdzeniem logiki intuicjonistycznej.

Egzamin 2014/2015

Zadanie 1 (10 punktów)
Słowo \(w \in \{0,1\}^+\) nazwiemy cyklicznym jeśli istnieje słowo \(v\), takie że \(w=v^nu\), gdzie \(u\) jest prefiksem \(v\) i \(n\geq 2\). Niech \(\Sigma=\{\leq, X\}\) i rozważmy zbiór modeli-słów nad \(\Sigma\). Napisz zdanie \(\varphi\) pełnej logiki drugiego rzędu SO, które jest prawdziwe dokładnie w tych modelach-słowach które odpowiadają słowom cyklicznym.

Rozwiązanie

Używamy oczywistych skrótów \(y=S(x)\) na to, że "y jest następnikiem x", oraz \(\exists!\) na "istnieje dokładnie jedno".
\(\exists F\)
\(\forall x\exists!y F(x,y)\) F jest częściową funkcją
\(\forall y\forall x\forall x'(F(x,y)\land F(x',y))\to x=x'\) F jest różnowartościowe
\(\forall x\forall y (x\leq x'\land \exists y F(x,y))\to(\exists y' F(x',y')\land y\leq y')\) F jest rosnące
\(\forall x\forall y\forall x'\forall y'((F(x,y)\land F(x',y'))\to (x'=s(x)\leftrightarrow y'=s(y))\) F zachwuje następniki.
\(\exists y\exists x (\forall z z\leq y)\land F(x,y)\) ostatni element jest wartością F.
Zatem F "przekopiowuje" pierwszy element na pewną pozycję (to będzie początek drugiej kopii \(v\)), a wszystkie dalsze po kolei za niego; na końcu słowa pewna liczba elementów nie ma określonej wartości F: dokładnie te nie mają wartości, dla których brakuje już miejsca na końcu słowa.
\(\forall y (\lnot\exists x F(x,y))\to\exists z F(y,z)\) Elementy na początku nie będące wartościami F same mają wartości - dzięki temu F przenosi pierwszą kopię \(v\) w całości.
\(\bigwedge_i\forall x\forall y(F(x,y)\to (X_i(x)\leftrightarrow X_i(y))\) literki są kopiowane wiernie.

Zadanie 2 (10 punktów)
Mówimy, że graf skończony \(\mathfrak{G}\) (gotyckie G) (nad sygnaturą złożoną z jednego dwuargumentowego symbolu relacyjnego \(E\) da się pokryć sumą rozłącznych krawędzi, gdy jest utworzony jako suma pewnej liczby rozłącznych wierzchołkowo krawędzi, z dodanymi w dowolny sposób dodatkowymi krawędziami pomiędzy już istniejącymi wierzchołkami.

Udowodnij, że nie istnieje zdanie \(\psi\) logiki pierwszego rzędu takie, że \(\mathfrak{G}\models\psi\) wtedy i tylko wtedy gdy \(\mathfrak{G}\) da się pokryć sumą rozłącznych krawędzi.

Rozwiązanie

Wystarczy dla każdego \(m\in\mathbb{N}\) wskazać dwa grafy \(\mathfrak{G}_1\) i \(\mathfrak{G}_2\), z których \(\mathfrak{G}_1\) da się pokryć sumą rozłącznych krawędzi, a \(\mathfrak{G}_2\) sie nie da, oraz \(\mathfrak{G}_1\equiv_m\mathfrak{G}_2\).

Niech \(\mathfrak{G}_1\) to ścieżka długości \(2^m\). Jej pokryciem są krawędzie między wierzchołkami \(2k+1\) a \(2k+2\), uzupełnione o krawędzie pomiędzy pozostałymi kolejnymi wierzchołkami, dotąd niepołącznymi.
Niech \(\mathfrak{G}_2\) to ścieżka długości \(2^m+1\). Jej pokrycie nie istnieje, bo każdy graf dający się pokryć rozłącznymi krawędziami musi mieć parzystą liczbę wierzchołków.
To, że \(\mathfrak{G}_1\equiv_m\mathfrak{G}_2\) było udowodnione na wykładzie.

Zadanie 3 (10 punktów)
Proszę napisać zdanie logiki pierwszego rzędu nad sygnaturą arytmetyki, które jest prawdziwe w standardowym modelu arytmetyki wtedy i tylko wtedy, gdy dla każdego dodatniego \(n\in\mathbb{N}\) istnieje dodatnie rozwiązanie równania \(x^n+y^n+z^n=t^n\) złożone z liczb naturalnych.

Rozwiązanie

Niech \(Pow(a,n,b)\) wyraża za pomocą formuły \(\chi\) definiującej funkcję \(\beta\) Goedla, że \(a^n=b\) w następujący sposób:
\(\exists t(\chi(t,0,1)\land \forall i((0\leq i < n)\to\exists y(\chi(t,i,y)\land\chi(t,i+1,y\cdot a)))\land \chi(t,n,b)\).

Wówczas żądane zdanie ma postać
\(\forall n (n>0\to(\exists x\exists y\exists z\exists t\exists x'\exists y'\exists z'\exists t'\)
\(x>0\lor y>0\lor z>0\lor t>0\land Pow(x,n,x')\land Pow(y,n,y')\land Pow(z,n,z')\land Pow(t,n,t')\land\)
\(x'+y'+z'=t'\)

Zadanie 4 (10 punktów)
Skonstruuj ciąg formuł \((\varphi_n)_{n\in\mathbb{N}}\) klasycznej logiki zdaniowej, taki, że \(|\varphi_n|=O(n)\) i istnieje dokładnie \(n^2\) różnych wartościowań \(\varrho:FV(\varphi_n)\to\{0,1\}\), które spełniają \(\varphi_n\).

Rozwiązanie

Żądana formuła \(\varphi_n\) może mieć postać
\((p_1\to p_2)\land(p_2\to p_3)\land\ldots\land(p_{n-2}\to p_{n-1})\land\)
\((q_1\to q_2)\land(q_2\to q_3)\land\ldots\land(q_{n-1}\to q_{n-1})\).

Wartościowania spełniające całą formułę to dokładnie te, dla których ciąg wartości przypisanych zmiennym \(p_i\) jest niemalejący oraz ciąg wartości przypisanych zmiennym \(q_i\) jest niemalejący. Takich ciągów jest \(n^2\).

TEST

1. Czy istnieje formuła MSO definiująca własność opisaną w Zadaniu 1?

Rozwiązanie

Nie. Własność ta definiuje język nieregularny, a zatem, na mocy tw. Buechi-Elgota, nie może być wyrażona za pomocą zdania MSO.

2. Czy \(\langle\mathbb{Q},+,*\rangle\equiv\langle\mathbb{R},+,*\rangle\)? (Działania algebraiczne w obu strukturach są naturalne, \(\equiv\) oznacza elementarną równoważność.)

Rozwiązanie

Nie.
Zdanie \(\exists x((\forall y x*y=y)\land (\exists y y*y=x+x))\)
wyraża fakt istnienia liczby \(\sqrt{1+1}\), czyli jest prawdziwe w \(\langle\mathbb{R},+,*\rangle\) i fałszywe w \(\langle\mathbb{Q},+,*\rangle\). Zatem te dwie struktury nie są elementarnie równoważne.

3. Czy teoria pierwszego rzędu struktury \(\langle\mathbb{N},\leq\rangle\) (porządek jest naturalny) jest rozstrzygalna?

Rozwiązanie

Tak, rozstrzygalna jest nawet teoria MSO tej struktury, o czym mówi tw. Buechiego, podane na wykładzie.

4. Założeniem w jednej z implikacji twierdzenia Codda jest to, że uniwersum struktury (nad skończoną sygnaturą) jest równe jej dziedzinie aktywnej. Czy ta własność da się sformalizować zdaniem logiki pierwszego rzędu?

Rozwiązanie

Tak. W dowodzie tw. Codda na wykładzie pojawiło się wyrażenie \(AD\) opisujące dziedzinę aktywną. Zgodnie z tw. Codda, istnieje formuła pierwszego rzędu \(\varphi_{AD}(x)\) równoważna (bez żadnych warunków) temu wyrażeniu. Zatem żądane zadnie ma postać \(\forall x\varphi_{AD}(x)\).

5. Przypuśćmy, że \(\models\varphi\to\psi\), przy czym obie formuły logiki pierwszego rzędu nie zawierają kwantyfikatorów. Czy istnieje interpolant \(\xi\) spełniający \(\models\varphi\to\xi\) i \(\models\xi\to\psi,\) oraz \(FV(\xi)=FV(\varphi)\cap\ FV(\psi)\)?

Rozwiązanie

Tak. Gdyby nie było w formułach równości, to każda formuła atomowa \(R(x)\) zachowuje się jak zmienna zdaniowa, jej wartość logiczna może być ustalana niezależnie od innych formuł atomowych i istnienie interpolanta wynika z twierdzenia o interpolacji dla logiki zadaniowej (było na wykładzie). Jeśli równości i nierówności są, to do formuł należy dopisac równoważności formuł atomowych wynikające z równości między zmiennymi i dopiero wytworzyć interpolanta.

Egzamin poprawkowy 2014/2015

Dwa z zadań są osnute wokół Lematu Koeniga w następującym sformułowaniu:
Założenie: Graf \(\mathfrak{T}\) (gotyckie T) jest nieskończonym drzewem skierowanym, w którym stopień każdego wierzchołka jest skończony.
Teza: W drzewie \(\mathfrak{T}\) istnieje nieskończona ścieżka.

Zadanie 1 (10 punktów)

Sformalizuj jednym zdaniem pełnej logiki drugiego rzędu SO założenie Lematu Koeniga: napisz zdanie \(\varphi\) takie, że jeśli graf skierowany \(\mathfrak{T}\models\varphi,\) to \(\mathfrak{T}\) jest nieskończonym drzewem skierowanym, w którym stopień każdego wierzchołka jest skończony.

Zadanie 2 (10 punktów)

Udowodnij, że nie istnieje zbiór zdań \(\Delta\) logiki pierwszego rzędu formalizujący negację tezy Lematu Koeniga, czyli taki, że dla każdego grafu skierowanego \(\mathfrak{T}\), jeśli \(\mathfrak{T}\models\Delta\) to albo \(\mathfrak{T}\) nie jest drzewem, albo nie zawiera nieskończonej ścieżki.

Zadanie 3 (10 punktów, po 5 za każdą z części)

Kwadrat kartezjański \(\mathfrak{G}^2\) grafu \(\mathfrak{G}=\langle G,E^\mathfrak{G}\rangle\) to struktura
\(\langle G\times G,E\rangle\), w której \(\langle(g,h),(g',h')\rangle \in E\) zachodzi wtedy i tylko wtedy, gdy \(\langle g,g'\rangle \in E^\mathfrak{G}\) i \(\langle h,h'\rangle \in E^\mathfrak{G}\).

1. Wykaż, że dla każdego skończonego grafu \(\mathfrak{G}\) o \(n > 1\) wierzchołkach zachodzi \(\mathfrak{G}^2\not\equiv_{n+1}\mathfrak{G}.\)
2. Podaj przykład skończonego grafu \(\mathfrak{G}\) o \(n > 1\) wierzchołkach spełniającego \(\mathfrak{G}^2\equiv_n\mathfrak{G}.\)

Zadanie 4 (10 punktów)

Niech zbiór \(X\) będzie spektrum zdania \(\varphi\) nad sygnaturą \(\Sigma\), tzn., niech \(X=\{ n\in\mathbb{N}~/~\)istnieje struktura \(\mathfrak{A}\) mocy \(n\) spełniająca \(\varphi\}.\)

Udowodnij, że zbiór \(\{ m+n~|~m,n\in X\}\) też jest spektrum pewnego zdania \(\psi\) (w konstrukcji wolno powiększyć sygnaturę o nowe symbole).

Zadanie 5 (10 punktów)

Dla danej formuły \(\varphi(x)\) w języku arytmetyki skonstruuj formułę \(\#\varphi(x)\), również w języku arytmetyki, o następującej własności:

\((\mathbb{N},x:n)\models \#\varphi(x)\) wtw \(|\{m\in\mathbb{N}~|~(\mathbb{N},x:m)\models\varphi(x)\}|=n.\)

Kolokwium 2015/2016

Zadanie 1

Liniowy porządek (ścisły) \(\mathfrak{A}=\langle A, < \rangle\) nazwiemy całkiem niegęstym, jeśli dla każdych dwóch elementów \(x,y\in A\) takich że \(x < y\), istnieje tylko skończenie wiele elementów \(z\in A\) spełniających warunek \(x < z < y\).

Udowodnij, że nie istnieje żaden zbiór \(\Delta\) zdań logiki pierwszego rzędu nad sygnaturą składającą się wyłącznie z symbolu \( < \), taki, że \(\mathfrak{A}\models\Delta\) wtedy i tylko wtedy, gdy \(\mathfrak{A}\) jest całkiem niegęstym porządkiem liniowym.

Szkic rozwiązania

Uwaga ogólna: \(\langle\mathbb{Z}, < \rangle\) jest całkiem niegęstym porządkiem.

Rozwiązanie I.

Przypuśćmy,że \(\Delta\) to żądana aksjomatyzacja. Do sygnatury dodajemy dwie nowe stałe \(c,d\). Niech

\(\bar\Delta=\Delta\cup\{\exists x_1\ldots\exists
x_n\bigwedge_{i\neq j}x_i\neq x_j)\land \bigwedge_{i}c < x_i < d\}\).

Pokazujemy, że \(\bar\Delta\) spełnia założenia twierdzenia o zwartości: niech \(\Delta_0\subseteq\bar\Delta\) będzie dowolny, skończony.

Niech \(N\) to maksymalna liczna kwantyfikatorów w zdaniach z \(\Delta_0\), pochodzących spoza \(\Delta\). Wówczas interpretujemy \(c\) i \(d\) jako dwa elementy \(\langle\mathbb{Z}, < \rangle\) odległe od siebie o więcej niż \(N\), np. \(0\) i \(N+1\). Tak rozszerzony model \(\langle\mathbb{Z}, < \rangle\) spełnia \(\Delta_0\), bo między interpretacjami nowych stałych jest dostatecznie wiele elementów.

Na mocy twierdzenia o zwartości \(\bar\Delta\) ma model. Zawiera on nieskończenie wiele elementów pomiędzy interpretacjami \(c\) i \(d\), czyli nie jest całkiem niegęsty. Sprzeczność.

Rozwiązanie II.

Niech \(\mathfrak{A}=\langle A, < \rangle\) będzie dowolnym całkiem niegęstym porządkiem i niech \(a\in A\). Niech \(d(x,y)\) dla \(x,y\in A\) oznacza \(1+|\{z\in A~|~x < z < y~lub~y < z < x\}|\).

Wówczas \(A=\bigcup_{n\in\mathbb{N}}\{x\in A~|~d(x,a)\leq n\}\). Rzeczywiście, gdyby pewne \(b\in A\) nie należało do zbioru po prawej, to liczba elementów między nim a \(a\) byłaby niekończona, co jest niemożliwe w porządku całkiem niegęstym.

Zatem \(A\) jest zbiorem skończonym lub przeliczalnym, jako przeliczlna suma zbiorów skończonych.

Stąd wynika, że nie istnieje nieprzliczalny porządek całkiem niegęsty, oraz istnieje taki porządek mocy \(\aleph_0\). Tymczasem z twierdzenia Skolema-Loewenheima wynika, że gdyby istniał zbiór zdań \(\Delta\) z treści zadania, to, mając model nieskończony, musiałby mieć także modele nieprzeliczalne. Sprzeczność.

Zadanie 2

Dla danego zdania \(\varphi\) logiki pierwszego rzędu niech \(spec(\varphi)=\{n\in\mathbb{N}~|~\)istnieje model \(\varphi\) mocy \(n\}\).

Dla danego zbioru \(A\subseteq\mathbb{N}\) niech \(A^\Sigma=\{\sum^r_{i=1}a_i~|~r\geq1,~a_1,\ldots,a_r\in A\}.\)

Dla danego zdania \(\varphi,\) skonstruuj zdanie \(\psi\) takie, że \(spec(\psi)=spec(\varphi)^\Sigma.\) Można przy tym założyć, że \(\varphi\) nie zawiera symboli funkcyjnych oraz rozszerzyć sygnaturę.

Szkic rozwiązania

Niech \(E\) będzie nowym symbolem relacji dwuargumentowej oraz \(x\) nową zmienną, dotąd nie występującą w \(\varphi\).

Niech \(\alpha\) będzie koniunkcją wszystkich trzech standardowych aksjomatów, orzekających, że \(E\) jest relacją równoważności.

Napiszemy teraz zdanie \(\psi\) orzekające, że podstruktura indukowana przez każdą z klas abstrakcji \(E\) jest modelem \(\varphi\), co powoduje, że moc każdego skończonego modelu \(\psi\) musi być sumą mocy pewnej skończonej liczby modeli \(\varphi\), oraz, że każda taka suma da się zrealizować jako moc modelu \(\psi\).

Zdanie to ma postać \(\forall x\varphi_{[x]}\), gdzie \(\varphi_{[x]}\) jest zdaniem \(\varphi\) zrelatywizowanym do klasy abstrakcji \(x\). Polega to na zastąpieniu każdej podformuły postaci \(\forall y\,\gamma\) podformułą \(\forall y(E(x,y)\to\gamma)\) oraz każdej podformuły postaci \(\exists y\,\gamma\) podformułą \(\exists y(E(x,y)\land\gamma)\).

Zadanie 3

Zadanie dotyczy klasycznej logiki zdaniowej. Niech \(\Delta,\Gamma\) będą dwoma zbiorami formuł spełniającymi \(\Gamma\models\Delta\). Udowodnij następujące nieskończone rozszerzenie Twierdzenia o interpolacji.

Istnieje zbiór \(\Theta\) taki, który zawiera wyłącznie zmienne zdaniowe, które występują zarówno w \(\Gamma\) jak i w \(\Delta\), oraz spełniający \(\Gamma\models\Theta\) i \(\Theta\models\Delta.\)

Szkic rozwiązania

Rozwiązanie I.

Niech \(\Delta=\{\varphi_1,\varphi_2,\ldots\}\).

Dla każdego \(i\) mamy zatem \(\Gamma\models\varphi_i\). Z twierdzenia o zwartości istnieje skończony podzbiór \(\Gamma_i\subseteq\Gamma\) taki, że \(\Gamma_i\models\varphi_i.\)

\(\bigwedge\Gamma_i\) jest jednym zdaniem i spełnia \(\bigwedge\Gamma_i\models\varphi_i\).

Ze standardowego twierdzenia o interpolacji wynika, że istnieje zdanie \(\vartheta_i\), zawierające tylko wspólne zmienne zdaniowe \(\Gamma_i\) i \(\varphi_i\), dla którego \(\Gamma_i\models\vartheta_i\) i \(\vartheta_i\models\varphi_i\).

Żądanym zbiorem jest \(\Theta=\{\vartheta_1,\vartheta_2,\ldots\}\).

Rozwiązanie II.

Naśladujemy dowód twierdzenia o interpolacji dla pojedynczych formuł spełniających \(\models\varphi\to\psi\). Interpolant był konstruowany przez sekwencję eliminacji zbędnych zmiennych z \(\varphi\), przy czym krok eliminacji zmiennej \(q\) opierał się na tym, że w powyższej sytuacji zachodzą implikacje

\(\models(\varphi[\bot/q]\lor\varphi[\top/q])\to\psi\)
i
\(\models\varphi\to (\varphi[\bot/q]\lor\varphi[\top/q])\).

Zatem krokiem w konstrukcji interpolantu jest zastąpnie \(\varphi\) przez \(\varphi[\bot/q]\lor\varphi[\top/q])\). Ten krok można lekko zmodyfikować, deklarując, że jeśli \(q\) nie występuje w \(\varphi\), to efektem kroku jest niezmienione \(\varphi\), zamiast formalnie wynikającej formuły \(\varphi\lor\varphi\).

Mając do czynienia ze zbiorami, musimy wykonać każdy taki (zmodyfikowany) krok na wszystkich formułach z \(\Gamma\) jednocześnie, oraz musimy wykonać (w pesymistycznym przypadku) nieskończenie wiele takich kroków. Każda z formuł w \(\Gamma\) zawiera jednak tylko skończenie wiele zmiennych, więc po skończenie wielu krokach stabilizuje się, bo późniejsze kroki jej już nie modyfikują. Zatem zbiór \(\Gamma\) po wykonaniu wszystkich nieskończenie wielu kroków jest dobrze zdefiniowany, a rozumowanie identyczne jak w dowodzie zwykłego twierdzenia o interpolacji pokazuje, że otrzymany zbiór jest pożądanym \(\Theta\).

Egzamin 2015/2016

Dla danego zdania \(\varphi\) logiki pierwszego lub drugiego rzędu jego spektrum to zbiór
\(spec(\varphi)=\{n\in\mathbb{N}~|\) istnieje model \(\varphi\) mocy \(n\}.\)

Zadanie 1 (10 punktów)
Napisz formułę \(\varphi(x,y)\) w języku arytmetyki, dla której zachodzi

\((\mathbb{N},x:n,y:m) \models \varphi(x,y)\) wtedy i tylko wtedy, gdy \(m=\sum_{i=1}^n i^n\)

Szkic rozwiązania

Zadanie 2 (10 punktów)

Graf \(\mathfrak{G}\) (gotyckie G) (nad sygnaturą złożoną z jednego dwuargumentowego symbolu relacyjnego \(E\)) jest przedstawiony na poniższym rysunku (ma 5 wierzchołków i 8 krawędzi):

*---*
|\ /|
| * |
|/ \|
*---*

Udowodnij, że każdy graf \(\mathfrak{H}\) (gotyckie H) taki, że \(\mathfrak{H}\equiv_3\mathfrak{G}\), ma nieparzystą liczbę wierzchołków większą od 3.

Szkic rozwiązania

Wygodnie jest się posłużyć grą Ehrenfeuchta-Fraisse o 3 rundach. Zauważmy, że ta gra między dwoma grafami jest identyczna jak gra rozgrywana między dopełnieniami tych grafów (w dopełnieniach krawędzie są dokładnie tam, gdzie ich w oryginalnych grafach nie ma). Istotnie, częściowe izomorfizmy w obu przypadkach są te same, więc i strategie graczy są identyczne.

Dopełnienie \(\mathfrak{G}\) to

*   *   *
|   |
*   *

W tym momencie jest jasne, że dopełnienie dowolnego grafu \(\mathfrak{H}\) spełniającego \(\mathfrak{H}\equiv_3\mathfrak{G}\) musi składać się z izolowanego wierzchołka i pewnej liczby (ale co najmniej dwóch) izolowanych krawędzi. Z tej obserwacji wynika teza.

Zadanie 3 (10 punktów)

Udowodnij, że dla każdej klasy \(\mathcal{A}\) skończonych grafów, która jest zamknięta na izomorfizmy, istnieje
zbiór \(\Delta\) zdań logiki pierwszego rzędu taki, że dla każdego skończonego grafu \(\mathfrak{A}\) zachodzi
równoważność: \(\mathfrak{A}\in\mathcal{A}\) wtedy i tylko wtedy, gdy \(\mathfrak{A}\models\Delta\). Czy i jakie modele
nieskończone ma \(\Delta\) jest tu bez znaczenia.

Szkic rozwiązania

Dla każdego skończonego grafu \(\mathfrak{A}\) można napisać zdanie \(\varphi_{\mathfrak{A}}\), które jest prawdziwe dokładnie w tych grafach, które są izomorficzne do \(\mathfrak{A}\) i fałszywe we wszystkich pozostałych.

Wówczas żądany zbiór zdań to
\(\Delta=\{\lnot\varphi_{\mathfrak{A}}~|~\mathfrak{A}\not\in\mathcal{A}\}\).

Istotnie, wszystkie zdania z \(\Delta\) są prawdziwe w pewnym grafie wtedy i tylko wtedy, gdy nie jest on izomorficzny do żadnego grafu nienależącego do \(\mathcal{A}\), czyli sam należy do \(\mathcal{A}\).

Zadanie 4 (10 punktów)

Napisać zdanie \(\varphi\) logiki ESO, które jest prawdziwe w grafie \(G\) wtedy i tylko wtedy, gdy \(G\) ma pokrycie wierzchołkowe zawierające nie więcej niż połowę wierzchołków.

Logika ESO to egzystencjalny fragment logiki drugiego rzędu (SO) - logika ta zwiera formuły postaci
\(\exists_{R_1}\ldots\exists_{R_n}\ \varphi\), gdzie podane kwantyfikatory to kwantyfikatory drugiego rzędu, a \(\varphi\) jest formułą pierwszego rzędu.

Zbiór wierzchołków jest pokryciem wierzchołkowym, jeśli zawiera przynajmniej jeden koniec każdej krawędzi grafu.

Szkic rozwiązania

TEST

1.
Czy klasa grafów dwudzielnych jest definiowalna (wśród grafów skończonych) zdaniem logiki pierwszego
rzędu (nad sygnaturą zawierającą wyłącznie binarny symbol relacyjny \(E\))?

Szkic rozwiązania

Przypuśćmy, że takie zdanie istnieje i ma rangę kwantyfikatorową \(n\). Wówczas rozważamy dwa cykle, jeden mocy parzystej a drugi nieparzystej, odpowiednio duże (większe, niż \(2^n\)). Jeden z nich jest dwudzielny, drugi nie, a zdaniem o randze kwantyfikatorowej \(n\) nie da się ich rozróżnić.

2.
Czy \(\langle\mathbb{R},\oplus\rangle\equiv\langle\mathbb{R_+},\oplus\rangle\)? W pierwszej strukturze interpretacja dwuargumentowego symbolu funkcyjnego \(\oplus\) to naturalne dodawanie, a w drugiej naturalne mnożenie, \(\equiv\) oznacza elementarną równoważność.

Szkic rozwiązania

Tak - te dwie struktury są nawet izomorficzne. Izomorfizmem jest funkcja wykładnicza \(\lambda x.a^x\), dla dowolnego \(a>0\).

3.
Czy dla danych zdań \(\varphi\), \(\psi\) logiki pierwszego rzędu zawsze istnieje zdanie logiki pierwszego rzędu \(\xi\) (nad dowolną sygnaturą) takie, że \(spec(\xi)=spec(\varphi)\cap spec(\psi)\)?

Szkic rozwiązania

Tak. Niech \(\varphi'\) to będzie zdanie otrzymane z \(\varphi\) przez taką zamianę nazw symboli funkcyjnych i relacyjnych, żeby \(\varphi'\) i \(\psi\) nie miały żadnych wspólnych elementów sygnatury. Wówczas można przyjąć za \(\xi\) zdanie \(\varphi'\land\psi\).

4.
Niech \(\mathbb{R}\) to liczby rzeczywiste z dodawaniem i mnożeniem. Niech \(\Delta\) będzie zbiorem zdań prawdziwych w
\(\mathbb{R}\). Czy \(\Delta\) ma model przeliczalny?

Szkic rozwiązania

Tak - na mocy tw. Skolema-Loewenheima.

5.
Niech \(R\) będzie relacją binarną na elementach dziedziny aktywnej. Czy domknięcie przechodnie relacji \(R\) można zdefiniować wyrażeniem algebry relacji?

Szkic rozwiązania

Nie - nie da się tego zrobić w logice pierwszego rzędu, więc w równoważnej jej (tw. Codda) algebrze relacyjnej też nie.

Egzamin poprawkowy 2015/2016

Egzamin poprawkowy z Logiki dla informatyków, 22/02/2016

Zadanie 1 (10 punktów)
Relacja \(E\subseteq A\times A\) ma własność silnej normalizacji jeśli dla każdego \(a\in A\) każda ścieżka zaczynająca się od \(a\) jest skończonej długości. (Takie relacje są istotne w badaniach systemów przepisywania termów i rachunku \(\lambda\).)

Udowodnij, że nie istnieje zdanie logiki pierwszego rzędu \(\varphi\) takie, że \(\langle A,E\rangle\models\varphi\) wtedy i tylko wtedy, gdy relacja \(E\) ma własność silnej normalizacji.

Zadanie 2 (10 punktów)
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ść silnej normalizacji (zdefiniowaną w Zadaniu 1).

Zadanie 3 (10 punktów)
Zadanie dotyczy klasycznej logiki zdaniowej. Wykaż, że istnieją interpolanty \(\varphi_n\) zawierające wyłącznie zmienne zdaniowe \(p_1,\ldots,p_n\) oraz długości \(O(n),\), takie, że tautologiami są formuły
\(\left((p_1\lor z_1)\land(\lnot z_1\lor p_2\lor z_2)\land(\lnot z_2\lor p_3\lor z_3)\land\ldots\land(\lnot z_{n-2}\lor p_{n-1}\lor z_{n-1})\land(\lnot z_{n-1}\lor p_n)\right)\to\varphi_n\)
oraz
\(\varphi_n\to\left[\left((p_1\to x_1)\land((x_1\lor p_2)\to x_2)\land((x_2\lor p_3)\to x_3)\land\ldots\land((x_{n-1}\lor p_{n})\to x_n)\right)\to x_n\right].\)

Zadanie 4 (10 punktów)
To zadanie dotyczy algebry relacji. Antyzłączenie (ang. antijoin) dwóch wyrażeń \(E\) i \(F\) o odpowiednio \(m\) i \(n \) kolumnach, oznaczane \(E \triangleright_{i=j} F\), ma następującą semantykę:

\([[E \triangleright_{i=j} F]]=\{\vec{a}\in[[E]]~|~\)nie istnieje \(\vec{b}\in[[F]]\) takie, że \(a_i=b_j\}\).

Napisz wyrażenie standardowej algebry relacji, które jest równoważne \(E \triangleright_{i=j} F\).

TEST

1.
Czy dla każdej klasy \(\mathcal{A}\) skończonych grafów, która jest zamknięta na izomorfizmy, istnieje zbiór \(\Delta\) uniwersalnych zdań logiki pierwszego rzędu taki, że dla każdego skończonego grafu \(\mathfrak{A}\) zachodzi równoważność: \(\mathfrak{A}\in\mathcal{A}\) wtedy i tylko wtedy, gdy \(\mathfrak{A}\models\Delta.\) Czy i jakie modele nieskończone ma \(\Delta\) jest tu bez znaczenia.

Zdanie jest uniwersalne, gdy ma postać \(\forall x_1\ldots\forall x_n\varphi,\) gdzie \(\varphi\) nie zawiera kwantyfikatorów.

2.
Dla przypomnienia, spektrum \(\mathit{Spec}(\varphi)\) zdania \(\varphi\) to zbiór \(\{n\in\mathbb{N}~|\)istnieje model zdania \(\varphi\) mocy \(n\}.\) Wiadomo, że jeśli w zdaniu \(\varphi\) występują wyłącznie jednoragumentowe symbole relacyjne, to \(\mathit{Spec}(\varphi)\) jest albo skończony, albo jego dopełnienie jest skończone.

Czy istnieje zdanie \(\varphi\), w którym występuje wyłącznie jeden jednoragumentowy symbol funkcyjny, oraz \(\mathit{Spec}(\varphi)\) nie jest ani skończony, ani jego dopełnienie nie jest skończone?

3.
Czy poniższa formuła poprawnie formalizuje własność: "istnieje dokładnie jeden element, który spełnia formułę \(\varphi(x)\)":
\[\exists x\forall y(\forall z((z=x \lor z=y)\to\varphi(z))\to x=y).\]

4.
Formuła Peirce'a \(((p\to q)\to p)\to p\) nie jest twierdzeniem zdaniowej logiki intuicjonistycznej. Czy istnieje model Kripkego o jednym stanie, w którym ta formuła nie jest wymuszona?

5.
Czy istnieje formuła \(\varphi(n,m)\) w języku arytmetyki taka, która orzeka w standardowym modelu arytmetyki, że \(m\)-tą cyfrą rozwinięcia dziesiętnego liczby \(\pi=3.14\ldots\) jest \(n.\) Na przykład miałyby zachodzić
\((\mathfrak{N},m:1,n:3)\models\varphi\), \((\mathfrak{N},m:2,n:1)\models\varphi\), \((\mathfrak{N},m:3,n:2)\not\models\varphi\).

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.

Egzamin 2016/2017

Zadanie 1

Niech dana będzie sygnatura \(\Sigma.\) Struktura \(\mathfrak{A}\) nad \(\Sigma\) ma własność \(F\) gdy dla każdych dwóch termów \(t,s\) nad \(\Sigma\) o (łącznie) jednej zmiennej wolnej \(x\), zbiór elementów \(a\in A\) spełniających \((\mathfrak{A},x:a)\models t=s\) jest albo skończony, albo jest całym zbiorem \(A.\) Na przykład, ciało liczb rzeczywistych \(\langle \mathbb{R},+,*,1\rangle\) ma własność \(F.\)

Udowodnij, że

a) Jeśli \(\Sigma\) zawiera jeden symbol \(f\) jednoargumentowej funkcji, to nie istnieje zbiór zdań \(\Delta\) nad \(\Sigma\) taki, że \(\mathfrak{A}\models\Delta\) wtedy i tylko wtedy, gdy \(\mathfrak{A}\) ma własność \(F\).
b) Jeśli \(\Sigma\) zawiera wyłącznie symbole stałych i relacji, to istnieje zbiór zdań \(\Delta\) nad \(\Sigma\) taki, że \(\mathfrak{A}\models\Delta\) wtedy i tylko wtedy, gdy \(\mathfrak{A}\) ma własność \(F\).

Zadanie 2

Zajmujemy się częściowymi porządkami postaci \(\langle A,\leq\rangle\) nad sygnaturą złożoną z jednego dwuargumentowego symbolu relacyjnego \(\leq\). Niech wówczas \(\langle \tilde{A},\tilde\leq\rangle\) oznacza częściowy porządek uzyskany z \(\langle A,\leq\rangle\) przez dodanie nowego elementu największego i nowego elementu najmniejszego.

Udowodnij, że dla każdego \(n\) i dowolnych \(\langle A,\leq_A\rangle\), \(\langle
B,\leq_B\rangle\), jeśli \(\langle A,\leq_A\rangle\equiv_n\langle B,\leq_B\rangle\) to \(\langle \tilde{A},\tilde\leq_A\rangle\equiv_n \langle\tilde{B},\tilde\leq_B\rangle\).

Zadanie 3

Pracujemy ze słowami nad alfabetem \(\{a,b\}\), tj. mamy ustaloną sygnaturę \(\{\leq, a(\cdot), b(\cdot)\}\) i rozważamy jedynie skończone struktury, w których \(\leq\) jest interpretowany jako liniowy porządek, a \(a(\cdot)\) i \(b(\cdot)\) jako dwa rozłączne podzbiory w sumie dające całe uniwersum.

Zdefiniuj język regularny zadany wyrażeniem \((ab^*a)^+\) w logice MSO. Czy jest on definiowalny w logice pierwszego rzędu?

Zadanie 4

Rozważmy narysowany poniżej graf nieskierowany \(D_n\) kształtu drabiny, przy czym ``szczebli'' jest \(n\) a wierzchłków \(2n\):

  A                   A'
  *--*--*--...--*--*--*
  |  |  |       |  |  |
  |  |  |  ...  |  |  |
  |  |  |       |  |  |
  *--*--*--...--*--*--*
  B                   B'

Niech \(M_n\) (M od Möbius) to graf otrzymany z \(D_n\) przez dodanie krawędzi \((A,B')\) i \((B,A')\).

Niech \(W_n\) (W od Walec) to graf otrzymany z \(D_n\) przez dodanie krawędzi \((A,A')\) i \((B,B')\).

Napisać zdanie \(\varphi\) logiki MSO takie, że dla każdego \(n>5\) rozróżnia ono grafy \(W_n\) i \(M_n,\) tzn. \(W_n\models\varphi\) wtw. \(M_n\models\lnot\varphi.\)

Wskazówka: Rozważ kolorowania tych struktur dwoma kolorami.

TEST

1
Zakładamy notację z zadania 2. Czy dla każdego \(n\) i dowolnych \(\langle A,\leq_A\rangle\), \(\langle B,\leq_B\rangle\) zachodzi implikacja: jeśli \(\langle \tilde{A},\tilde\leq_A\rangle\equiv_n \langle\tilde{B},\tilde\leq_B\rangle\) to \(\langle A,\leq_A\rangle\equiv_n\langle B,\leq_B\rangle\)?

Szkic rozwiązania

NIE.
Rozważmy porządki liniowe. "Zdjęcie" tyldy oznacza zmniejszenie ich długości o 2. Weźmy zatem dwa porządki liniowe różnych długości \(>2^n\). One są w relacji \(\equiv_n\) (wykład). Gdyby teza zachodziła, to moglibyśmy zdejmować po dwa elementy nie zmieniając zachodzenia tej relacji, robiąc to tak długo, aż porządki zrobią się tak krótkie, że oczywiście dadzą się rozróżnić \(n\) kwantyfikatorami.

2
Czy istnieje formuła arytmetyczna \(\varphi(x,y,z)\) taka, że dla każdych trzech liczb naturalnych \(p,n,k\) zachodzi równoważność: \((\mathfrak{A},x:p,y:n,z:k)\models\varphi\) wtedy i tylko wtedy, gdy wielomian \(\sum_{i=1}^n\beta(p,i)x^i\) ma dokładnie \(k\) różnych pierwiastków naturalnych? (Przez \(\beta\) oznaczamy funkcję beta G\"odla.)

Szkic rozwiązania

TAK.
W artymetyce można zakodować dowolną funkcję częściowo obliczalną (wykład).

3
Czy obie poniższe formuły zdaniowe są tautologiami intuicjonistycznymi?

A \(\lnot\lnot( \lnot p \lor p)\)
B \(\lnot\lnot p \lor \lnot p\)

Szkic rozwiązania

NIE.
B nie jest tautologią intucjonistyczną, co można sprawdzić na nast. modelu Kripkego:

              * not(p)
            /
           /
not(p)*
          \
           \
             * p

not(p) oznacza brak wymuszenia p.

4
Zajmujemy się klasyczną logiką zdaniową. Mamy dane dwie formuły \(\varphi,\psi,\) które nie zawierają żadnych wspólnych zmiennych zdaniowych. Ponadto \(\not\models\lnot\varphi\) i \(\not\models\psi.\)

Czy możliwe jest, że \(\models\varphi\to\psi\)?

Szkic rozwiązania

NIE.
Wystarczy zmienne \(\varphi\) tak ustawić, by ta formuła była fałszywa, a zmienne \(\psi\) tak, by ona była prawdziwa. Zmiennych wspólnych nie ma, więc to się da zrobić. Przy tym wartościowaniu implikacja jest fałszywa.

5
Czy poniższy problem jest rozstrzygalny:

Dane: Formuła \(\varphi(x)\) z jedną zmienną wolną, logiki pierwszego rzędu nad sygnaturą \(+,*,0,1\)\\

Pytanie: Czy istnieje \(a\in\mathbb{N}\) takie, że \((\langle \mathbb{N},+,*,0,1\rangle,x:a)\models\varphi\)?

Szkic rozwiązania

NIE.
To jest to samo, co rozstrzyganie, czy dana formuła pierwszego rzędu jest spełniona w standardowym modelu arytmetyki, a to jest nierozstrzygalne (wykład).

Egzamin poprawkowy 2016/2017

Wiele z zadań odnosi się do nieskierowanego grafu \(\mathfrak{G}\) o 24 wierzchołkach z jedną symetryczną relacją krawędzi \(E\), narysowanego na obrazku pod linkiem http://smurf.mimuw.edu.pl/node/1861 (na egzaminie obrazek był wydrukowany).

Zadanie 1
Napisz formułę pierwszego rzędu \(\varphi(x,y)\) z dwoma zmiennymi wolnymi \(x, y\) taką, że \((\mathfrak{G},x:a,y:b)\models\varphi\) wtedy i tylko wtedy, gdy \(a\) i \(b\) są przeciwległymi wierzchołkami jednego z oczek sześciokątnej siatki. Na przykład powinno to zachodzić dla \(x\) i \(y\) będacych dwoma kółkami, a nie powinno zachodzić dla żadnej z par zawierających gwiazdki.

Zadanie 2
Rozszerzamy sygnaturę grafów o dodatkowe symbole stałych \(\circ\) i \(\star\). Tworzymy dwie kopie \(\mathfrak{G}\), oznaczone \(\mathfrak{G}_1\) i \(\mathfrak{G}_2\), w których interpretacjami nowych symboli stałych są: w \(\mathfrak{G}_1\) czarne kółko i czarna gwiazdka; w \(\mathfrak{G}_2\) białe kółko i biała gwiazdka, w tej właśnie kolejności.

Proszę wskazać strategię dla gracza I w grze Ehrenfeuchta-Fra\"{\i}ss\'e \(G_2(\mathfrak{G}_1,\mathfrak{G}_2)\) oraz napisać zdanie o randze kwantyfikatorowej 2, rozróżniające te dwie struktury.

Zadanie 3
Pracujemy ze strukturami-słowami nad alfabetem \(\{a,b\}\), tj. mamy ustaloną sygnaturę \(\{\leq, a(\cdot), b(\cdot)\}\) i rozważamy jedynie skończone struktury, w których \(\leq\) jest interpretowany jako liniowy porządek, a \(a(\cdot)\) i \(b(\cdot)\) jako dwa rozłączne podzbiory w sumie dające całe uniwersum.

Czy język zdefiniowany zdaniem pełnej logiki drugiego rzędu

\(\exists R [\forall x\forall y (R(x,y)\to (R(y,x) \land (a(x)\leftrightarrow
b(y))))\land \forall x \exists! y R(x,y)]\)

jest definiowalny w logice MSO? (\(\exists!\) oznacza ``istnieje dokładnie jeden'' i jest skrótem znanej formuły pierwszego rzędu.)

Zadanie 4

Mamy dany skończony skierowany graf \(\mathfrak{H}=(\{1,\ldots,n\},E).\) Zakładamy, że zawiera on dla każdego wierzchołka \(i\) krawędź \((i,i)\in E\). Zakodowujemy go jako zbiór \(\Delta_\mathfrak{H}\) formuł klasycznej logiki zdaniowej: dla każdego wierzchołka \(i\in\{1,\ldots,n\}\) tworzymy zmienną zdaniową \(p_i\). Teraz kładziemy

\(\Delta_\mathfrak{H}=\{p_i\to p_j~|~(i,j)\in E\}.\)

Udowodnij, że \(\Delta_\mathfrak{H}\cup\{\lnot( p_i\leftrightarrow p_j)\}\) jest spełnialne wtedy i tylko wtedy, gdy \(i\) i \(j\) nie należą do tej samej silnej składowej \(\mathfrak{H}.\)

TEST

1.
Używamy grafu \(\mathfrak{G}\) z zadania 1. Czy istnieje formuła pierwszego rzędu \(\varphi(x,y)\) z dwoma zmiennymi wolnymi, która w \(\mathfrak{G}\) definiuje porządek liniowy?

Szkic rozwiązania

Nie. Ten graf ma automorfizmy (symetrie) inne od identyczności, więc nie da się uporządkować.

2.
Czy istnieje formuła logiki pierwszego rzędu nad sygnaturą grafów, która jest prawdziwa w grafie \(\mathfrak{H}\) wtedy i tylko wtedy, gdy \(\mathfrak{H}\) jest izomorficzny z podgrafem indukowanym grafu \(\mathfrak{G}\) z zadania 1?

Szkic rozwiązania

Tak. Każdy skończony graf można opisać z dokłądnością do izomorfizmu w logice pierwszego rzędu, więc skończony zbiór grafów też się da.

3.
Czy możliwe jest, że pewnien zbiór zdań logiki pierwszego rzędu nad skończoną sygnaturą ma dwa modele nieskończone które nie są elementarnie równoważne, a jednocześnie wszystkie jego modele przeliczalne są izomorficzne?

Szkic rozwiązania

Nie. Pełne teorie tych nie-elementarnie równoważnych nieskończonych modeli muszą mieć, każdy do siebie, elementarnie rónoważne przeliczalne modele (tw. Skolema-Lowenheima). Zatem muszą być także dwa przeliczalne modele, które nie są elementarnie rónoważne (a zatem też nie-izomorficzne).

4.
Czy poniższy dowód jest poprawny?

Twierdzenie Klasa wszystkich relacji równoważności \(\sim\), których wszystkie klasy abstrakcji są skończone, nie jest aksjomatyzowalna żadnym zbiorem zdań logiki pierwszego rzędu.

Dowód: Przypuśćmy wbrew tezie, że \(\Delta\) jest taką aksjomatyzacją. Niech

\(\bar{\Delta}=\Delta\cup\{\exists x_1\ldots\exists x_n\bigwedge_{1\leq i < j\leq
n}(x_i\neq x_j \land x_i\sim x_j)~|~n\in\mathbb{N}\}.\)

Każdy skończony podzbiór \(\bar{\Delta}\) jest spełnialny, bo zawarte w nim skończenie wiele ``dodanych'' zdań nie wymaga istnienia nieskończonych klas abstrakcji. Zatem z Twierdzenia o zwartości cały \(\bar{\Delta}\) jest spełnialny. To prowadzi do sprzeczności, bo dołączone zdania wymagają istnienia nieskończonych klas abstrakcji, a \(\Delta\) zabrania ich istnienia.

Szkic rozwiązania

Nie. \(\Delta\) nie wymusza istnienia nieskończonych klas abstrakcji.

5.
Czy poniższy problem jest częściowo rozstrzygalny:\\

Dane: Formuła bezkwantyfikatorowa \(\varphi(x)\) z jedną zmienną wolną, logiki pierwszego rzędu nad sygnaturą \(+,*,0,1\)

Pytanie: Czy istnieje \(a\in\mathbb{N}\) takie, że \((\langle \mathbb{N},+,*,0,1\rangle,x:a)\models\varphi\)?

Szkic rozwiązania

Tak. Maszyna Turinga, dla danego \(\varphi\) po kolei sprawdza wszyskie możliwe \(a\). Sprawdzenie jest możliwe, bo formuła nie ma kwantyfikatorów. Jeśli znajdzie element spełniający, zatrzymuje się i odpowiada "Tak". Jeśli nie znajdzie, oblicza w nieskończoność, co jest formą odpowiedzi "Nie" w modelu częściowej obliczalności.