Zadanie 1 (10 punktów)
Relacja \(E\subseteq A\times A\) ma własność silnej normalizacji jeśli dla każdego \(a\in A\) każda ścieżka zaczynająca się od \(a\) jest skończonej długości. (Takie relacje są istotne w badaniach systemów przepisywania termów i rachunku \(\lambda\).)
Udowodnij, że nie istnieje zdanie logiki pierwszego rzędu \(\varphi\) takie, że \(\langle A,E\rangle\models\varphi\) wtedy i tylko wtedy, gdy relacja \(E\) ma własność silnej normalizacji.
Zadanie 2 (10 punktów)
Udowodnij, że istnieje zdanie logiki MSO \(\varphi\) takie, że \(\langle A,E\rangle\models\varphi\) wtedy i tylko wtedy, gdy relacja \(E\) ma własność silnej normalizacji (zdefiniowaną w Zadaniu 1).
Zadanie 3 (10 punktów)
Zadanie dotyczy klasycznej logiki zdaniowej. Wykaż, że istnieją interpolanty \(\varphi_n\) zawierające wyłącznie zmienne zdaniowe \(p_1,\ldots,p_n\) oraz długości \(O(n),\), takie, że tautologiami są formuły
\(\left((p_1\lor z_1)\land(\lnot z_1\lor p_2\lor z_2)\land(\lnot z_2\lor p_3\lor z_3)\land\ldots\land(\lnot z_{n-2}\lor p_{n-1}\lor z_{n-1})\land(\lnot z_{n-1}\lor p_n)\right)\to\varphi_n\)
oraz
\(\varphi_n\to\left[\left((p_1\to x_1)\land((x_1\lor p_2)\to x_2)\land((x_2\lor p_3)\to x_3)\land\ldots\land((x_{n-1}\lor p_{n})\to x_n)\right)\to x_n\right].\)
Zadanie 4 (10 punktów)
To zadanie dotyczy algebry relacji. Antyzłączenie (ang. antijoin) dwóch wyrażeń \(E\) i \(F\) o odpowiednio \(m\) i \(n \) kolumnach, oznaczane \(E \triangleright_{i=j} F\), ma następującą semantykę:
\([[E \triangleright_{i=j} F]]=\{\vec{a}\in[[E]]~|~\)nie istnieje \(\vec{b}\in[[F]]\) takie, że \(a_i=b_j\}\).
Napisz wyrażenie standardowej algebry relacji, które jest równoważne \(E \triangleright_{i=j} F\).
1.
Czy dla każdej klasy \(\mathcal{A}\) skończonych grafów, która jest zamknięta na izomorfizmy, istnieje zbiór \(\Delta\) uniwersalnych zdań logiki pierwszego rzędu taki, że dla każdego skończonego grafu \(\mathfrak{A}\) zachodzi równoważność: \(\mathfrak{A}\in\mathcal{A}\) wtedy i tylko wtedy, gdy \(\mathfrak{A}\models\Delta.\) Czy i jakie modele nieskończone ma \(\Delta\) jest tu bez znaczenia.
Zdanie jest uniwersalne, gdy ma postać \(\forall x_1\ldots\forall x_n\varphi,\) gdzie \(\varphi\) nie zawiera kwantyfikatorów.
2.
Dla przypomnienia, spektrum \(\mathit{Spec}(\varphi)\) zdania \(\varphi\) to zbiór \(\{n\in\mathbb{N}~|\)istnieje model zdania \(\varphi\) mocy \(n\}.\) Wiadomo, że jeśli w zdaniu \(\varphi\) występują wyłącznie jednoragumentowe symbole relacyjne, to \(\mathit{Spec}(\varphi)\) jest albo skończony, albo jego dopełnienie jest skończone.
Czy istnieje zdanie \(\varphi\), w którym występuje wyłącznie jeden jednoragumentowy symbol funkcyjny, oraz \(\mathit{Spec}(\varphi)\) nie jest ani skończony, ani jego dopełnienie nie jest skończone?
3.
Czy poniższa formuła poprawnie formalizuje własność: "istnieje dokładnie jeden element, który spełnia formułę \(\varphi(x)\)":
\[\exists x\forall y(\forall z((z=x \lor z=y)\to\varphi(z))\to x=y).\]
4.
Formuła Peirce'a \(((p\to q)\to p)\to p\) nie jest twierdzeniem zdaniowej logiki intuicjonistycznej. Czy istnieje model Kripkego o jednym stanie, w którym ta formuła nie jest wymuszona?
5.
Czy istnieje formuła \(\varphi(n,m)\) w języku arytmetyki taka, która orzeka w standardowym modelu arytmetyki, że \(m\)-tą cyfrą rozwinięcia dziesiętnego liczby \(\pi=3.14\ldots\) jest \(n.\) Na przykład miałyby zachodzić
\((\mathfrak{N},m:1,n:3)\models\varphi\), \((\mathfrak{N},m:2,n:1)\models\varphi\), \((\mathfrak{N},m:3,n:2)\not\models\varphi\).