SO
Zad. 1
Pokazać, że dla każdego zdania \(\varphi\) logiki drugiego rzędu SO istnieje inne zdanie \(\varphi'\) tejże samej logiki takie, że
\(Spec(\varphi')=\mathbb{N}_+\setminus Spec(\varphi).\)
Zad. 2
Pokazać, że odpowiednik twierdzenia o zwartości nie zachodzi dla logiki drugiego rzędu.
Zad. 3
Napisać zdanie \(\Pi^1_1\), czyli uniwersalnego fragmentu logiki drugiego rzędu, którego wszystkimi modelami są dokładnie struktury skończone.
Zad. 4
Spróbować naszkicowac dowód tw. Fagina, że \(\Sigma^1_1=NP\) nad słowami (było sformułowane na wykładzie).
Zad. 5
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 drugiego rzędu 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.
MSO
Zad. 1
Na wykładzie podany został dowód, że dla każdego zdania \(\varphi\) logiki MSO istnieje automat, który akceptuje dokładnie te słowa, w których \(\varphi\) jest prawdziwe.
Oszacować, jaki jest stosunek rozmiaru minimalnego deterministycznego automatu do długości formuły.
Zad. 2
Udowodnić, że każde zdanie MSO nad słowami jest równoważne zdaniu z tylko jednym kwantyfikatorem egzystencjalnym po relacji unarnej, w dodatku umieszczonym na początku.
Zad. 3
Skonstruować zdanie logiki MSO, które ma wyłącznie modele mocy co najmniej \(\mathfrak{c}\).
Zad. 4
Skonstruować zdanie logiki MSO, które ma wyłącznie modele mocy co najmniej \(2^{\mathfrak{c}}\).
Zad. 5
Skonstruować zdanie logiki MSO, którego spektrum to zbiór wszystkich liczb pierwszych.
Zad. 6
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 relacyjnego \(E\).
Napisać zdanie \(\varphi\) logiki MSO postaci \(\forall R_1\ldots\forall 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}\) jest grafem acyklicznym.
Zad. 7
Napisać zdanie MSO, którego wszystkie skończone modele to dokładnie te grafy, które są 3-kolorowalne.
Zad. 8
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, \(\phi\) jest prawdziwe w stanie początkowym struktury \(\mathfrak{A}\) wtedy i tylko wtedy, gdy \(\mathfrak{A}\models\varphi\).