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