Informatyka MIMUW

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?