Egzamin 2016/2017 | Informatyka MIMUW

Zadanie 1

Niech dana będzie sygnatura $\Sigma.$ Struktura $\mathfrak{A}$ nad $\Sigma$ ma własność $F$ gdy dla każdych dwóch termów $t,s$ nad $\Sigma$ o (łącznie) jednej zmiennej wolnej $x$ , zbiór elementów $a\in A$ spełniających $(\mathfrak{A},x:a)\models t=s$ jest albo skończony, albo jest całym zbiorem $A.$ Na przykład, ciało liczb rzeczywistych $\langle \mathbb{R},+,*,1\rangle$ ma własność $F.$

Udowodnij, że

a) Jeśli $\Sigma$ zawiera jeden symbol $f$ jednoargumentowej funkcji, to nie istnieje zbiór zdań $\Delta$ nad $\Sigma$ taki, że $\mathfrak{A}\models\Delta$ wtedy i tylko wtedy, gdy $\mathfrak{A}$ ma własność $F$ .
b) Jeśli $\Sigma$ zawiera wyłącznie symbole stałych i relacji, to istnieje zbiór zdań $\Delta$ nad $\Sigma$ taki, że $\mathfrak{A}\models\Delta$ wtedy i tylko wtedy, gdy $\mathfrak{A}$ ma własność $F$ .

Zadanie 2

Zajmujemy się częściowymi porządkami postaci $\langle A,\leq\rangle$ nad sygnaturą złożoną z jednego dwuargumentowego symbolu relacyjnego $\leq$ . Niech wówczas $\langle \tilde{A},\tilde\leq\rangle$ oznacza częściowy porządek uzyskany z $\langle A,\leq\rangle$ przez dodanie nowego elementu największego i nowego elementu najmniejszego.

Udowodnij, że dla każdego $n$ i dowolnych $\langle A,\leq_A\rangle$ , $\langle B,\leq_B\rangle$ , jeśli $\langle A,\leq_A\rangle\equiv_n\langle B,\leq_B\rangle$ to $\langle \tilde{A},\tilde\leq_A\rangle\equiv_n \langle\tilde{B},\tilde\leq_B\rangle$ .

Zadanie 3

Pracujemy ze słowami nad alfabetem $\{a,b\}$ , tj. mamy ustaloną sygnaturę $\{\leq, a(\cdot), b(\cdot)\}$ i rozważamy jedynie skończone struktury, w których $\leq$ jest interpretowany jako liniowy porządek, a $a(\cdot)$ i $b(\cdot)$ jako dwa rozłączne podzbiory w sumie dające całe uniwersum.

Zdefiniuj język regularny zadany wyrażeniem $(ab^*a)^+$ w logice MSO. Czy jest on definiowalny w logice pierwszego rzędu?

Zadanie 4

Rozważmy narysowany poniżej graf nieskierowany $D_n$ kształtu drabiny, przy czym ``szczebli'' jest $n$ a wierzchłków $2n$ :

  A                   A'
  *--*--*--...--*--*--*
  |  |  |       |  |  |
  |  |  |  ...  |  |  |
  |  |  |       |  |  |
  *--*--*--...--*--*--*
  B                   B'

Niech $M_n$ (M od Möbius) to graf otrzymany z $D_n$ przez dodanie krawędzi $(A,B')$ i $(B,A')$ .

Niech $W_n$ (W od Walec) to graf otrzymany z $D_n$ przez dodanie krawędzi $(A,A')$ i $(B,B')$ .

Napisać zdanie $\varphi$ logiki MSO takie, że dla każdego $n>5$ rozróżnia ono grafy $W_n$ i $M_n,$ tzn. $W_n\models\varphi$ wtw. $M_n\models\lnot\varphi.$

Wskazówka: Rozważ kolorowania tych struktur dwoma kolorami.

TEST

1
Zakładamy notację z zadania 2. Czy dla każdego $n$ i dowolnych $\langle A,\leq_A\rangle$ , $\langle B,\leq_B\rangle$ zachodzi implikacja: jeśli $\langle \tilde{A},\tilde\leq_A\rangle\equiv_n \langle\tilde{B},\tilde\leq_B\rangle$ to $\langle A,\leq_A\rangle\equiv_n\langle B,\leq_B\rangle$ ?

Szkic rozwiązania

NIE.
Rozważmy porządki liniowe. "Zdjęcie" tyldy oznacza zmniejszenie ich długości o 2. Weźmy zatem dwa porządki liniowe różnych długości

$>2^n$ . One są w relacji

$\equiv_n$ (wykład). Gdyby teza zachodziła, to moglibyśmy zdejmować po dwa elementy nie zmieniając zachodzenia tej relacji, robiąc to tak długo, aż porządki zrobią się tak krótkie, że oczywiście dadzą się rozróżnić

$n$ kwantyfikatorami.

2
Czy istnieje formuła arytmetyczna

$\varphi(x,y,z)$ taka, że dla każdych trzech liczb naturalnych

$p,n,k$ zachodzi równoważność:

$(\mathfrak{A},x:p,y:n,z:k)\models\varphi$ wtedy i tylko wtedy, gdy wielomian

$\sum_{i=1}^n\beta(p,i)x^i$ ma dokładnie

$k$ różnych pierwiastków naturalnych? (Przez

$\beta$ oznaczamy funkcję beta G\"odla.)

Szkic rozwiązania

TAK.
W artymetyce można zakodować dowolną funkcję częściowo obliczalną (wykład).

3
Czy obie poniższe formuły zdaniowe są tautologiami intuicjonistycznymi?

A $\lnot\lnot( \lnot p \lor p)$
B $\lnot\lnot p \lor \lnot p$

Szkic rozwiązania

NIE.
B nie jest tautologią intucjonistyczną, co można sprawdzić na nast. modelu Kripkego:

              * not(p)
            /
           /
not(p)*
          \
           \
             * p

not(p) oznacza brak wymuszenia p.

4
Zajmujemy się klasyczną logiką zdaniową. Mamy dane dwie formuły

$\varphi,\psi,$ które nie zawierają żadnych wspólnych zmiennych zdaniowych. Ponadto

$\not\models\lnot\varphi$ i

$\not\models\psi.$

Czy możliwe jest, że $\models\varphi\to\psi$ ?

Szkic rozwiązania

NIE.
Wystarczy zmienne

$\varphi$ tak ustawić, by ta formuła była fałszywa, a zmienne

$\psi$ tak, by ona była prawdziwa. Zmiennych wspólnych nie ma, więc to się da zrobić. Przy tym wartościowaniu implikacja jest fałszywa.

5
Czy poniższy problem jest rozstrzygalny:

Dane: Formuła $\varphi(x)$ z jedną zmienną wolną, logiki pierwszego rzędu nad sygnaturą $+,*,0,1$ \\

Pytanie: Czy istnieje $a\in\mathbb{N}$ takie, że $(\langle \mathbb{N},+,*,0,1\rangle,x:a)\models\varphi$ ?

Szkic rozwiązania

NIE.
To jest to samo, co rozstrzyganie, czy dana formuła pierwszego rzędu jest spełniona w standardowym modelu arytmetyki, a to jest nierozstrzygalne (wykład).