Kolokwium 2011/2012 | Informatyka MIMUW

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