Informatyka MIMUW

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)

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?