Informatyka MIMUW

Egzamin poprawkowy z Logiki dla informatyków, 22/02/2016

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

TEST

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