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.

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.

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