W poniższych zadaniach proszę rozstrzygnąć, czy podana formuła jest tautologią czy nie, oraz czy jest spełnialna czy nie. W czasie odpowiedzi wymagane będzie uzasadnienie.
Spektrum \(Spec(\varphi)\) zdania \(\varphi\) to zbiór wszystkich liczb naturalnych \(n\) takich, ze \(\varphi\) ma model o mocy \(n.\)
Standardowy model arytmetyki to struktura \(\mathbb{N}=\langle\omega,*^{\mathbb}{N},+^{\mathbb}{N},0^{\mathbb}{N},1^{\mathbb}{N},\leq^{\mathbb}{N}\rangle.\)
\(\mathrm{nwd}^{\mathbb{A}}(m,n)=\text{najwi"ekszy wsp"olny dzielnik $m$ i $n$.}\)\(m\) i \(n\).
Napisać formułę \(\varphi(x)\) nad \(\Sigma\) definiującą własność ,,być liczbą pierwszą”, tj., taką, że dla wszystkich wartościowań \(v:X\to\omega\)
\(\mathbb{X}\models\varphi[v]\ \ \text{wtw}\ \ \text{$v(x)$ jest liczb"a pierwsz"a.}\)\(v(x)\) jest liczbą pierwszą.
\(\displaystyle S^{\mathbb{Y}}(n) =n+1\) S Y n = + n 1 \(\displaystyle \beta^{\mathbb{Y}}(t,p,i) =\text{$\beta$}(t,p,i),\)\(\beta\) t p i β Y t p i = β t p i
gdzie \(\beta\) to funkcja beta Gödla, znana z wykładu, zaś \(\leq^{\mathbb{Y}}\) to zwykła nierówność.
Napisać formułę \(\varphi(x,y,z)\) nad \(\Sigma\) definiującą dodawanie, tj., taką, że dla wszystkich wartościowań \(v:X\to\omega\)
\(\mathbb{Y}\models\varphi[v]\ \ \text{wtw}\ \ v(x)+v(y)=v(z).\)
Podać taki przykład aksjomatyzowalnej klasy \(\mathcal{A}\) nad sygnaturą \(\Sigma\) (którą też można sobie wybrać), że \(Mod(\Sigma)\setminus\mathcal{A}\) nie jest aksjomatyzowalna.
Przypuśćmy, że \(E\) jest zbiorem równości normalnych, oraz że \(E\vdash _{{eq}}s=t.\) Udowodnić, że \(s=t\) też jest równością normalną.
\(\forall x\forall y\,(y=f(g(x))\to(\exists u\,(u=f(x)\land y=g(u))))\)
oraz niech \(\psi\) będzie zdaniem
\(\forall x\,[f(g(f(x)))=g(f(f(x)))].\)
Czy \(\{\psi\}\models\varphi?\)
Wykorzystując przestrzenie liniowe nad ciałem \(\mathbb{R}\) jako przykład, udowodnić, że może istnieć wiele różnych kongruencji \(\bar{r},\) rozszerzających daną relację równoważności \(r\) w \(G.\)
Czas na rozwiązanie zadań to 3 godziny od chwili ich rozdania. Wolno używać dowolnych notatek i podręczników, natomiast nie wolno ściągać. Osoby złapane na ściąganiu będziemy usuwać z egzaminu.
Wszystkie zadania są oceniane w skali 0-1-2-3 punkty, przy czym ważne jest uzasadnienie odpowiedzi. Na piątkę trzeba 10 punktów (w tym 4 zadania na co najmniej 2 punkty), na czwórkę 7 punktów (w tym co najmniej 2 zadania na co najmniej 2 punkty), a na trójkę 5 punktów (w tym co najmniej 2 zadania na co najmniej 2 punkty lub jedno zadanie na 3 punkty). Każdej osobie, kóra odda więcej niż cztery zadania, do wyniku zostaną policzone najsłabsze cztery spośród nich, tak więc nie opłaca się oddawać więcej niż czterech zadań.
Każde zadanie proszę napisać na osobnej kartce, podpianej imieniem, nazwiskiem i numerem indeksu.
Oceny z egzaminu zostaną wpisane tylko tym studentom, którzy dostarczą indeks z wpisanym zaliczeniem z ćwiczeń.
Mówimy, że funkcja \(F:\omega\to\omega\) jest definiowalna, gdy istnieje formuła \(\varphi(x,y)\) nad sygnaturą arytmetyki taka, że każdego wartościowania \(v:X\to\omega\) zachodzi
\(\mathbb{N}\models\varphi[v]\ \ \text{wtw}\ \ v(y)=F(v(x)).\)
Udowodnić, że jeśli funkcja \(F:\omega\to\omega\) jest definiowalna, to jest też definiowalna funkcja \(G:\omega\to\omega\) dana wzorem
\(G(n)=\begin{cases}0&\text{gdy $n=0,$}\\ F(G(n-1))&\text{gdy $n>0.$}\end{cases}\)
Udowodnić, że jeśli \(\mathcal{A}\) jest rozmaitością algebr, to \(Spec(\mathcal{A})\) jest zamknięte na mnożenie: jeśli \(m,n\in Spec(\mathcal{A}),\) to \(m\cdot n\in Spec(\mathcal{A}).\)
Podać przykład takiej klasy algebr \(\mathcal{A}\) nad sygnaturą \(\Sigma\) (która też jest do wyboru), która jest definiowalna, ale jej spektrum nie jest zamknięte na mnożenie.
\(f(x,y)=\begin{cases}x^{{2\cdot y}}&\text{gdy $x\neq 0$ lub $y\neq 0$,}\\ 0&\text{gdy $x=0$ i $y=0$.}\end{cases}\).
Napisać taką formułę pierwszego rzędu \(\varphi(x)\) nad \(\Sigma,\) z jedną zmienną wolną \(x\), która definiuje liczbę \(1,\) t.j., taką, że dla każdego wartościowania \(v:X\to\omega\) zachodzi \(\mathbb{E}\models\varphi[v]\) wtw \(v(x)=1.\)
Dla każdej sygnatury \(\Sigma\) i każdej klasy \(\mathcal{A}\) struktur nad \(\Sigma,\) jeśli klasa \(\mathcal{A}\) jest aksjomatyzowalna, to jest też aksjomatyzowalna podklasa \(\mathcal{A}\), składająca się ze struktur mocy nie większej niż \(\mathfrak{n}.\)
Przypuśćmy, że \(E\) jest zbiorem wszystkich równości dziwnych nad \(\Sigma,\) oraz że \(\mathbb{A}\) jest algebrą nad \(\Sigma\) taką, że \(\mathbb{A}\models E.\) Udowodnić, że dla każdego \(n\in\omega\) i każdego \(f\in\Sigma^{F}_{n},\) \(f^{\mathbb{A}}\) jest funkcją stałą. Czy z powyższych założeń wynika też, że \(|A|=1?\)
\(\bigl(\forall x\, f(a_{1}(x),a_{2}(x))=x\bigr)\land\bigl(\forall x\forall y\, a_{1}(f(x,y))=x\land a_{2}(f(x,y))=y\bigr).\)
Czy \(\varphi\) ma model o co najmniej dwóch elementach?
Czas na rozwiązanie zadań to 3 godziny od chwili ich rozdania. Wolno używać dowolnych notatek i podręczników, natomiast nie wolno ściągać. Osoby złapane na ściąganiu będziemy usuwać z egzaminu.
Wszystkie zadania są oceniane w skali 0-1-2-3 punkty, przy czym ważne jest uzasadnienie odpowiedzi. Na piątkę trzeba 10 punktów (w tym 4 zadania na co najmniej 2 punkty), na czwórkę 7 punktów (w tym co najmniej 3 zadania na co najmniej 2 punkty), a na trójkę 5 punktów (w tym co najmniej 2 zadania na co najmniej 2 punkty lub jedno zadanie na 3 punkty). Każdej osobie, kóra odda więcej niż cztery zadania, do wyniku zostaną policzone najsłabsze cztery spośród nich, tak więc nie opłaca się oddawać więcej niż czterech zadań.
Każde zadanie proszę napisać na osobnej kartce, podpisanej imieniem, nazwiskiem i numerem indeksu.
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.
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.
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.
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)\)
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!
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 drugiego rzędu 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.
Pokazać, że nie istnieje zdanie \(\varphi\) logiki pierwszego rzędu o 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.
Niech \(k\in\mathbb{N}\) będzie stałą. Wykazać, że jeśli \(E\) jest wyrażeniem algebry relacyjnej i maksymalna liczba kolumn w podwyrażeniach \(E\) wynosi \(k\), to istnieje algorytm obliczający wartość \([\![E]\!]\) w każdej strukturze \(\mathfrak{A}\) i działający 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. Wynik obliczenia zwraca się analogicznie.
Rozważamy skończone drzewa binarne \(\mathfrak{T}\) (ta litera to gotyckie T, w rozwiązaniu można pisać zwykłe T) nad sygnaturą składającą się z dwóch dwuargumentowych symboli relacyjnych \(L\) i \(P\), przy czym \(L(x,y)\) oznacza że \(y\) to lewy syn ojca \(x\), podobnie dla \(P\) oznaczającego prawego syna. Każdy wiechołek może mieć 0, 1 lub 2 synów, zawsze najwyżej jednego lewego jednego prawego.
Udowodnić, że dla każdego naturalnego \(n\) istnieje zdanie \(\varphi _{n}\) logiki pierwszego rzędu, w którym występują tylko dwie zmienne (które można rekwantyfikować tak często jak potrzeba), takie że dla każdego skończonego drzewa binarnego \(\mathfrak{T}\) zachodzi równoważność: \(\mathfrak{T}\models\varphi _{n}\) wtw \(\mathfrak{T}\) jest pełnym drzewem binarnym o głębokości \(n\).
Sygnatura składa się z dwuargumentowego symbolu funkcyjnego \(\circ\), jednoargumentowego symbolu funkcyjnego \(inv\) i symbolu stałej \(id\). Model \(\mathfrak{F}\) (ta litera to gotyckie F, w rozwiązaniu można pisać zwykłe F) nad tą sygnaturą nazywamy grupą bijekcji, gdy jego uniwersum stanowi zbiór wszystkich bijekcji \(f:A\to A\) dla pewnego zbioru \(A,\) a operacje mają następujące interpretacje: \(\circ^{\mathfrak{F}}\) to operacja składania funkcji, \(inv^{\mathfrak{F}}\) to operacja brania funkcji odwrotnej, a \(id^{\mathfrak{F}}\) to fukcja indentycznościowa z \(A\) w \(A\).
Udowodnić, że nie istnieje zbiór \(\Gamma\) zdań logiki pierwszego rzędu taki, że \(\mathfrak{B}\models\Gamma\) wtedy i tylko wtedy, gdy \(\mathfrak{B}\) jest izomorficzny do pewnej grupy bijekcji.
\(\mathrm{nwd}^{\mathbb{A}}(m,n)=\text{najwi"ekszy wsp"olny dzielnik $m$ i $n$,}\)\(m\) i \(n\),
zaś \(1^{\mathbb{A}}\) to zwykła jedynka.
Napisać formułę \(\varphi(x)\) nad \(\Sigma\) definiującą własność ,,być kwadratem liczby pierwszej”, tj., taką, że dla wszystkich wartościowań \(v:X\to\omega\)
\(\mathbb{X}\models\varphi[v]\ \ \text{wtw}\ \ \text{$v(x)$ jest kwadratem liczby pierwszej.}\)\(v(x)\) jest kwadratem liczby pierwszej.
\(\beta^{\mathbb{X}}(t,p)=\text{$\beta$}(t,p),\)
gdzie \(\beta\) to funkcja beta Gödla, znana z wykładu, zaś \(+^{\mathbb{X}},0^{\mathbb{X}},1^{\mathbb{X}}\) to zwykłe dodawanie, 0 i 1.
Napisać formułę \(\varphi(x,y,z)\) nad \(\Sigma\) definiującą mnożenie, tj., taką, że dla wszystkich wartościowań \(v:X\to\omega\)
\(\mathbb{X}\models\varphi[v]\ \ \text{wtw}\ \ v(x)*v(y)=v(z).\)
\(\displaystyle S^{\mathbb{Y}}(n) =n+1\) S Y n = + n 1 \(\displaystyle \beta^{\mathbb{Y}}(t,p) =\text{$\beta$}(t,p),\)\(\beta\) t p β Y t p = β t p
gdzie \(\beta\) to funkcja beta Gödla, znana z wykładu.
Napisać formułę \(\varphi(x,y,z)\) nad \(\Sigma\) definiującą dodawanie, tj., taką, że dla wszystkich wartościowań \(v:X\to\omega\)
\(\mathbb{Y}\models\varphi[v]\ \ \text{wtw}\ \ v(x)+v(y)=v(z).\)
Napisać zdanie pierwszego rzędu \(\varphi\) nad \(\Sigma\) takie, że \(\mathbb{R}_{A}\models\varphi\) wtw \(A\) jest zbiorem domkniętym.
Podać taki przykład aksjomatyzowalnej klasy \(\mathcal{A}\) nad sygnaturą \(\Sigma\) (którą też można sobie wybrać), że \(Mod(\Sigma)\setminus\mathcal{A}\) nie jest aksjomatyzowalna.
Przypuśćmy, że \(E\) jest zbiorem równości normalnych, oraz że \(E\vdash _{{eq}}s=t.\) Udowodnić, że \(s=t\) też jest równością normalną.
\(\forall x\forall y\,(y=f(g(x))\to(\exists u\,(u=f(x)\land y=g(u))))\)
oraz niech \(\psi\) będzie zdaniem
\(\forall x\,[f(g(f(x)))=g(f(f(x)))].\)
Czy \(\{\psi\}\models\varphi?\)
\(f^{\mathbb{A}}(m,n)=m\;\;(\textrm{mod}n)=\text{reszta z dzielenia $m$ przez $n$},\)\(m\) przez \(n\)
przy czym przyjmujemy, że \(m\;\;(\textrm{mod}0)=m\) dla każdego \(m.\)
Udowodnić, że w tej algebrze są tylko dwie kongruencje.
[Szkic dowodu: Niech \(\sim\) będzie kongruencją.
(*) Jeśli \(m\sim n\) dla pewnych \(0< m< n,\) to wtedy \(m=m\;\;(\textrm{mod}n)\sim n\;\;(\textrm{mod}n)=0,\) więc \(m,n\) są kongruentne z \(0.\)
(**) Jeśli \(m\sim 0\) dla pewnego \(m>0,\) to dla każdego \(0< i< m\) mamy \(i=(m+i)\;\;(\textrm{mod}m)\sim m+i\;\;(\textrm{mod}0)=m+i,\) więc \(i\sim 0\) na mocy (*).
(***) Jeśli \(m\sim 0\) dla pewnego \(m>0,\) to dla każdego \(n>m\) mamy \(n=n\;\;(\textrm{mod}0)\sim n\;\;(\textrm{mod}m)< m< n,\) więc \(n\sim 0\) na mocy (*).
(****) Jeśli teraz \(m\sim n\) dla pewnych \(m\neq n,\) to albo jedno z \(m,n\) jest zerem i na mocy (**) i (***) wszystkie liczby są kongruentne z \(0,\) albo \(m,n\) są niezerowe, ale wtedy na mocy (*) \(m\sim 0\) i znowu jesteśmy w przypadku poprzednim.
Szkoda by mi było wyrzucić to zadanie, ale chyba jest za trudne.]
Wykorzystując przestrzenie liniowe nad ciałem \(\mathbb{R}\) jako przykład, udowodnić, że może istnieć wiele różnych kongruencji P\(\bar{r},\) rozszerzających daną relację równoważności \(r\) w \(G.\)
Czas na rozwiązanie zadań to 3 godziny od chwili ich rozdania. Wolno używać dowolnych notatek i podręczników, natomiast nie wolno ściągać. Osoby złapane na ściąganiu będziemy usuwać z egzaminu.
Wszystkie zadania są oceniane w skali 0-1-2 punkty. Na piątkę wystarcza 7 punktów, na czwórkę 5 punktów, a na trójkę 4 punkty. Każdej osobie, kóra odda więcej niż cztery zadania, do wyniku zostaną policzone najsłabsze cztery spośród nich, tak więc nie opłaca się oddawać więcej niż czterech zadań.
Każde zadanie proszę napisać na osobnej kartce, podpianej imieniem, nazwiskiem i numerem indeksu.
Oceny z egzaminu zostaną wpisane tylko tym studentom, którzy dostarczą indeks z wpisanym zaliczeniem z ćwiczeń.
\(\{\varphi _{2}\to\varphi _{1},\varphi _{3}\to(\varphi _{1}\land\varphi _{2}),\varphi _{4}\to(\varphi _{1}\land\varphi _{2}\land\varphi _{3}),\dots\}.\)
Czy musi istnieć \(n\) takie, że dla każdego \(\psi\), \(T\models\psi\) implikuje \(\varphi _{n}\models\psi\)?
Napisać formułę \(\varphi(x,y)\) nad sygnaturą arytmetyki definiującą funkcję \(y=\lfloor\log _{2}x\rfloor,\) tzn. taką, że dla wszystkich wartościowań \(v:X\to\omega\)
\(\mathbb{N}\models\varphi[v]\ \ \text{wtw}\ \ v(y)=\lfloor\log _{2}v(x)\rfloor.\)
Ile jest różnych funkcji dwóch argumentów \(x\) i \(y\), definiowalnych za pomocą termów \(t(x,y)\) w algebrze \(\mathbb{Z}_{n}?\)
Udowodnić, że zbiór \(FINSAT_{\Sigma}\) jest algorytmicznie generowalny.
\(\xymatrix{&*+{A\times A}&\\ *+{r_{1}}\ar[ur]&&*+{r_{2}}\ar[ul]\\ &*+{\mathrm{id}_{A}}\ar[ul]\ar[ur]}\) \xymatrix Align Align \ar Align Align \ar Align \ar \ar
Udowodnić, że algebra \(\mathbb{A}/r_{1}\) ma tylko dwie kongruencje: relację totalną i identyczność.
Udowodnić, że
\(\mathbb{F}\models\forall f([\exists g\, g\circ f=\mathrm{id}]\to[\forall g_{1}\forall g_{2}\,((f\circ g_{1}=f\circ g_{2})\to g_{1}=g_{2})]).\)
Czas na rozwiązanie zadań to 3 godziny od chwili ich rozdania. Wolno używać dowolnych notatek i podręczników, natomiast nie wolno ściągać.
Wszystkie zadania są oceniane w skali 0-1-2-3 punkty, przy czym ważne jest uzasadnienie odpowiedzi. Na piątkę trzeba 10 punktów (w tym 4 zadania na co najmniej 2 punkty), na czwórkę 8 punktów (w tym co najmniej 3 zadania na co najmniej 2 punkty), a na trójkę 5 punktów (w tym co najmniej 2 zadania na co najmniej 2 punkty lub jedno zadanie na 3 punkty). Każdej osobie, która odda więcej niż cztery zadania, do wyniku zostaną policzone najsłabsze cztery spośród nich, tak więc nie opłaca się oddawać więcej niż czterech zadań.
Każde zadanie proszę napisać na osobnej kartce, podpisanej imieniem, nazwiskiem i numerem indeksu.
\(\mathbb{N}\models\varphi[v]\ \ \text{wtw}\ \ v(y)=\lfloor(v(x))^{{\frac{1}{v(z)}}}\rfloor.\)
Ile jest różnych funkcji dwóch argumentów \(x\) i \(y\), definiowalnych za pomocą termów \(t(x,y)\) w algebrze \(\mathbb{Z}_{n}?\)
Udowodnić, że zbiór \(FINSAT_{\Sigma}\) jest algorytmicznie generowalny.
Niech \(\varphi\) będzie zdaniem \(\forall x\forall y\forall z[R(x,y)\land R(x,z))\to y=z],\) zaś \(\psi\) zdaniem \(\forall x\exists y[R(x,y)\land\forall z\,(R(x,z)\to y=z)].\) Rozstrzygnąć, czy \(\varphi\models\psi\) oraz czy \(\psi\models\varphi.\)
Czas na rozwiązanie zadań to 2 godziny 30 minut od chwili ich rozdania. Wolno używać dowolnych notatek i podręczników, natomiast nie wolno ściągać.
Z zadań należy wybrać dowolne trzy i je rozwiązać. Wszystkie zadania są oceniane w skali 0-1-2-3 punkty, przy czym ważne jest uzasadnienie odpowiedzi. Na piątkę trzeba 7 punktów (w tym 3 zadania na co najmniej 2 punkty), na czwórkę 5 punktów (w tym co najmniej 2 zadania na co najmniej 2 punkty), a na trójkę 3 punktów (w tym co najmniej 1 zadanie na co najmniej 2 punkty). Każdej osobie, która odda więcej niż trzy zadania, do wyniku zostaną policzone najsłabsze trzy spośród nich.
Można jednak oddać także czwarte zadanie, specjalnie oznaczone jako dodatkowe, którego wynik 3 pkt. będzie umożliwiał dostanie szóstki (oczywiście tylko tym, którzy z pozostałych trzech zadań dostali piątkę).
Każde zadanie proszę napisać na osobnej, podpisanej kartce.
Zasady punktacji i wystawiania ocen są następujące:
Z całości egzaminu można otrzymac następujące oceny: bardzo dobrą, bardzo dobrą minus, dobrą plus, dobrą, dobrą minus, dostateczną plus, dostateczną lub niedostateczną.
Za każde zadanie można otrzymac maksymalnie jeden punkt (oceny wystawiane są z dokładnością do 0.1 punkta). Policzone zostaną trzy najlepiej rozwiązane zadania - dwóch pozostałych nie będziemy brać pod uwagę.
Uzyskanie łącznie 2.9 punktów daje ocenę dobrą plus, 2.5 punkta daje ocenę dobrą, 2.1 punkta ocenę dostateczną plus oraz 1.6 punkta ocenę dostateczną. Na życzenie studenta oceny te zostaną wpisane do indeksu. Każdą ocenę (także niedostateczną) można będzie podnieść o maksymalnie dwa poziomy (aż do piątki włącznie) na ustnym egzaminie z teorii, który będzie się odbywać w przyszłym tygodniu. W wypadku niezadowalających odpowiedzi ocena z egzaminu pisemnego może się obniżyć o maksymalnie jeden poziom.
Osoby, które z kolokwium uzyskały minimum 1.5 punkta, mogą zamiast rozwiązań zadań 1 i 2 oddać kartkę z życzeniem, żeby za te zadania przyznane zostały punkty uzyskane na kolokwium. Jeśli jednak oddadzą rozwiązania któregoś z tych zadań, to zostaną one sprawdzone i dostaną za nie na egzaminie tyle punktów na ile te rozwiązania ocenimy, bez względu na to, ile punktów dostały na kolokwium.
W poniższych zadaniach odpowiedzi należy uzasadniać. Odpowiedź bez uzasadnienia nie liczy się w ogóle jako rozwiązanie.
\((\forall x\forall y\forall z\ (R(x,z)\land R(z,y))\to R(x,y))\ \to\ (\exists x\exists y\exists z\ R(x,y)\land R(y,z)\land R(z,x)).\)
Proszę napisać formułę \(\varphi(x,y)\) taką, że \(\mathbb{N}\models\varphi[o_{1},o_{2}]\) wtedy i tylko wtedy, gdy odległość pomiędzy środkami okręgów \(o_{1}\) i \(o_{2}\) jest większa niż 4.
Proszę podać przez ile rund może się bronić drugi gracz w grze Ehrenfeuchta–Fraïssé'go rozgrywanej na tych strukturach, jeśli gracz pierwszy gra optymalnie dla siebie.
\(\forall x\exists y(R(x)\to S(y))\vdash(\exists xR(x))\to(\exists yS(y)).\)
HKL=Heyting-Kleene-Łukasiewicz
S= Sobociński
\(\begin{array}[]{|c|ccc|}\hline\omit\span\omit\span\omit\span\omit x\land _{{S}}y\\ \hline\hline x\diagdown y&0&1&\bot\\ \hline 0&0&0&0\\ 1&0&1&1\\ \bot&0&1&\bot\\ \hline\end{array}\ \ \ \ \begin{array}[]{|c|c|}\hline\omit\span\omit\sim x\\ \hline\hline x&\sim x\\ \hline 0&1\\ \hline 1&0\\ \hline\bot&\bot\\ \hline\end{array}\ \ \ \ \begin{array}[]{|c|ccc|}\hline\omit\span\omit\span\omit\span\omit x\lor _{{S}}y\\ \hline\hline x\diagdown y&0&1&\bot\\ \hline 0&0&1&0\\ 1&1&1&1\\ \bot&0&1&\bot\\ \hline\end{array}\ \ \ \ \begin{array}[]{|c|ccc|}\hline\omit\span\omit\span\omit\span\omit x\lor _{{HKL}}y\\ \hline\hline x\diagdown y&0&1&\bot\\ \hline 0&0&1&\bot\\ 1&1&1&1\\ \bot&\bot&1&\bot\\ \hline\end{array}\ \ \ \ \)
Udowodnić, że zbiór \(\{ m+n~/~m,n\in X\}\) też jest spektrum pewnego zdania \(\psi\) (w konstrukcji wolno powiększyć sygnaturę o nowe symbole).
Udowodnić, że klasa \(\mathcal{C}\) nie jest definiowalna.
Udowodnić, że
\(\mathbb{W}\models\forall x([\exists y_{1}\exists y_{2}\exists y_{3}\, x=(y_{1}\circ y_{2})\circ y_{3}]\to\\ .\)
Napisać formułę \(\varphi(x)\) nad sygnaturą arytmetyki definiującą relację ,,\(x\) ma nieparzystą ilość cyfr w rozwinięciu dziesiętnym”, tzn. taką, że dla wszystkich wartościowań \(v:X\to\omega\) zachodzi równoważność \(\mathbb{N}\models\varphi[v]\) wtw \(v(x)\) ma nieparzystą ilość cyfr w rozwinięciu dziesiętnym.
Proszę opisać wszystkie kongruencje algebry \(\mathbb{Z}_{{8}}.\)
Udowodnić, że jeśli zbiór równości \(E\) nad \(\Sigma\) jest symetryczny, to zbiór\(\{ t=s~/~E\models t=s\}\) też jest symetryczny.
Rozstrzygnąć, czy \(\{\varphi _{1},\varphi _{2},\varphi _{3}\}\models\{\psi _{1},\psi _{2}\}.\)
\(\displaystyle \varphi _{1}: ~~~\forall x_{1}\forall x_{2}\, E(x_{1},x_{2})\to E(x_{2},x_{1})\) φ 1 : → ∀ x 1 ∀ x 2 E x 1 x 2 E x 2 x 1 \(\displaystyle \varphi _{2}: ~~~\forall x\,\lnot E(x,x)\) φ 2 : ∀ x ¬ E x x \(\displaystyle \varphi _{3}: ~~~\exists x_{1}\exists x_{2}\exists x_{3}\exists x_{4}\exists x_{5}\,\bigwedge _{{1\leq i< j\leq 5}}x_{i}\neq x_{j}\) φ 3 : ≠ ∃ x 1 ∃ x 2 ∃ x 3 ∃ x 4 ∃ x 5 ⋀ 1 ≤ i < j ≤ 5 x i x j \(\displaystyle \psi _{1}: ~~~\exists x_{1}\exists x_{2}\exists x_{3}\, E(x_{1},x_{2})\land E(x_{2},x_{3})\land E(x_{3},x_{1})\) ψ 1 : ∧ ∃ x 1 ∃ x 2 ∃ x 3 E x 1 x 2 E x 2 x 3 E x 3 x 1 \(\displaystyle \psi _{2}: ~~~\exists x_{1}\exists x_{2}\exists x_{3}\,\lnot(E(x_{1},x_{2})\lor E(x_{2},x_{3})\lor E(x_{3},x_{1}))\) ψ 2 : ∃ x 1 ∃ x 2 ∃ x 3 ¬ ∨ E x 1 x 2 E x 2 x 3 E x 3 x 1
Czas na rozwiązanie zadań to 3 godziny od chwili ich rozdania. Wolno używać dowolnych notatek i podręczników, natomiast nie wolno ściągać.
Wszystkie zadania są oceniane w skali 0-1-2-3 punkty, przy czym ważne jest uzasadnienie odpowiedzi. Na piątkę trzeba 10 punktów (w tym 4 zadania na co najmniej 2 punkty), na czwórkę 8 punktów (w tym co najmniej 3 zadania na co najmniej 2 punkty), a na trójkę 5 punktów (w tym co najmniej 2 zadania na co najmniej 2 punkty lub jedno zadanie na 3 punkty). Każdej osobie, która odda więcej niż cztery zadania, do wyniku zostaną policzone najsłabsze cztery spośród nich, tak więc nie opłaca się oddawać więcej niż czterech zadań.
Każde zadanie proszę napisać na osobnej kartce, podpisanej imieniem, nazwiskiem i numerem indeksu.
Funkcja \(h:A\to\ B\) jest homomorfizmem grafów \(\mathbb{A}\) i \(\mathbb{B},\) gdy dla wszystkich \(a,a^{{\prime}}\in A\), \(\langle a,a^{{\prime}}\rangle\in E^{\mathbb{A}}\) implikuje \(\langle h(a),h(a^{{\prime}})\rangle\in E^{\mathbb{B}}\).
Udowodnić, że klasa \(\mathcal{A}\) nie jest aksjomatyzowalna, tj., że nie istnieje zbiór \(T\) zdań taki, że \(\mathcal{A}=Mod(T).\)
\(\mathbb{A}=\langle R,+^{\mathbb{A}},*^{\mathbb{A}},-^{\mathbb{A}},0^{\mathbb{A}},1^{\mathbb{A}},\leq^{\mathbb{A}},f^{\mathbb{A}}\rangle,\)
gdzie \(R\) to zbiór liczb rzeczywistych, \(+,*,-,0,1,\leq\) mają zwykłe interpretacje (takie, jak w liczbach rzeczywistych), zaś \(f^{\mathbb{A}}:R\to R\) jest dowolną funkcją.
Napisać zdanie pierwszego rzędu \(\varphi\) nad \(\Sigma\) takie, że \(\mathbb{A}\models\varphi\) wtw \(f^{\mathbb{A}}\) jest funkcją okresową o najmniejszym okresie \(1.\)
Z powyższych zadań należy wybrać i rozwiązać dwa. Czas na rozwiązanie zadań to 90 minut od chwili ich rozdania. Wolno używać dowolnych notatek i podręczników, natomiast nie wolno ściągać. Wykryte przypadki ściągania (także na etapie sprawdzania prac) będziemy karać.
Zadania są oceniane w skali 0-1-2-3 punkty, przy czym ważne jest uzasadnienie odpowiedzi. Do zaliczenia potrzeba 4 punktów. Osobie, kóra odda więcej niż dwa zadania, do wyniku zostaną policzone najsłabsze dwa sposród nich, czyli nie opłaca się oddawać więcej niż dwóch zadań.
Każde zadanie proszę napisać na osobnej kartce, podpisanej imieniem, nazwiskiem, grupą (nazwisko prowadzącego i termin zajęć) i adresem poczty elektronicznej, na który ma być wysłany wynik kolokwium.
Funkcja \(h:A\to\ B\) jest homomorfizmem grafów \(\mathbb{A}\) i \(\mathbb{B},\) gdy dla wszystkich \(a,a^{{\prime}}\in A\), \(\langle a,a^{{\prime}}\rangle\in E^{\mathbb{A}}\) implikuje \(\langle h(a),h(a^{{\prime}})\rangle\in E^{\mathbb{B}}\).
Jaka jest najmniejsza możliwa liczba krawędzi w grafie \(\mathbb{A}=\langle A,E^{\mathbb{A}}\rangle,\) który jest modelem zbioru \(\{\varphi _{0},\varphi _{1},\varphi _{2}\}?\)
Skonstruować zbiór zdań \(T\) nad zwykłą sygnaturą porządków \(\Sigma,\) taki, że \(\mathcal{A}=Mod(T).\)
\(\mathbb{A}=\langle R,+^{\mathbb{A}},*^{\mathbb{A}},-^{\mathbb{A}},0^{\mathbb{A}},1^{\mathbb{A}},\leq^{\mathbb{A}},f^{\mathbb{A}}\rangle,\)
gdzie \(R\) to zbiór liczb rzeczywistych, symbole \(+,*,-,0,1,\leq\) mają zwykłe interpretacje (takie, jak w liczbach rzeczywistych), zaś \(f^{\mathbb{A}}:R\to R\) jest dowolną funkcją.
Napisać zdanie pierwszego rzędu \(\varphi\) nad \(\Sigma\) takie, że \(\mathbb{A}\models\varphi\) wtw \(f^{\mathbb{A}}\) jest funkcją okresową o najmniejszym dodatnim okresie \(1.\)
Z powyższych zadań należy wybrać i rozwiązać dwa. Czas na rozwiązanie zadań to 90 minut od chwili ich rozdania. Wolno używać dowolnych notatek i podręczników, natomiast nie wolno ściągać. Wykryte przypadki ściągania (także na etapie sprawdzania prac) będziemy karać.
Zadania są oceniane w skali 0-1-2-3 punkty, przy czym ważne jest uzasadnienie odpowiedzi. Do zaliczenia potrzeba 4 punktów. Osobie, kóra odda więcej niż dwa zadania, do wyniku zostaną policzone najsłabsze dwa sposród nich, czyli nie opłaca się oddawać więcej niż dwóch zadań.
Każde zadanie proszę napisać na osobnej kartce, podpisanej imieniem, nazwiskiem, grupą (nazwisko prowadzącego i termin zajęć).
Czy \(\{\varphi _{)},\varphi _{1},\varphi _{2},\varphi _{3}\}\models\exists x\exists y\exists z(E(x,y)\land E(x,z)\land E(z,y)).\)
Napisać zdanie pierwszego rzędu \(\varphi\) nad \(\Sigma\) takie, że \(\mathbb{R}_{f}\models\varphi\) wtw \(f\) jest funkcją różniczkowalą w \(0.\)
Czas na rozwiązanie zadań to 90 minut od chwili ich rozdania. Wolno używać dowolnych notatek i podręczników, natomiast nie wolno ściągać. Osoby złapane na ściąganiu (także na etapie sprawdzania prac) będziemy karać.
Wszystkie zadania są oceniane w skali 0-1-2-3 punkty, przy czym ważne jest uzasadnienie odpowiedzi. Do zaliczenia potrzeba 5 punktów (w tym 2 zadania na co najmniej 2 punkty). Każdej osobie, kóra odda więcej niż trzy zadania, do wyniku zostaną policzone najsłabsze cztery spośród nich, tak więc nie opłaca się oddawać więcej niż trzech zadań.
Każde zadanie proszę napisać na osobnej kartce, podpisanej imieniem, nazwiskiem i adresem poczty elektronicznej, pod który ma być wysłany wynik.
Udowodnić, że \(\{\varphi _{)},\varphi _{1},\varphi _{2},\varphi _{3}\}\models\exists x\exists y\exists z(E(x,y)\land E(x,z)\land E(z,y)).\)
Napisać zdanie pierwszego rzędu \(\varphi\) nad \(\Sigma\) takie, że \(\mathbb{R}_{f}\models\varphi\) wtw \(f\) jest funkcją różniczkowalą w \(0.\)
Czas na rozwiązanie zadań to 90 minut od chwili ich rozdania. Wolno używać dowolnych notatek i podręczników, natomiast nie wolno ściągać. Osoby złapane na ściąganiu (także na etapie sprawdzania prac) będziemy karać.
Wszystkie zadania są oceniane w skali 0-1-2-3 punkty, przy czym ważne jest uzasadnienie odpowiedzi. Do zaliczenia potrzeba 5 punktów (w tym 2 zadania na co najmniej 2 punkty). Każdej osobie, kóra odda więcej niż trzy zadania, do wyniku zostaną policzone najsłabsze cztery spośród nich, tak więc nie opłaca się oddawać więcej niż trzech zadań.
Każde zadanie proszę napisać na osobnej kartce, podpisanej imieniem, nazwiskiem i adresem poczty elektronicznej, pod który ma być wysłany wynik.
O zadaniach. Zadania są podzielone na kilka grup. Niektóre zadania są dosyć trudne. Pewne zadania powtarzają się w kilku grupach, aby zachęcić studentów do rozwiązania ich różnymi metodami.
Przy niektórych zadaniach (z działów ,,Tw. o zwartości” i ,,Tw. Skolema-Löwenheima”) należy się posłużyć pełną wersją twierdzenia Skolema-Löwenheima poniżej, która zostanie podana na najbliższym wykładzie:
Jeśli \(\Delta\) jest zbiorem zdań nad sygnaturą \(\Sigma\) który ma nieskończony model, to \(\Delta\) ma model dowolnej mocy \(\mathfrak{m}\geq|\Sigma|.\)
Formalizowanie zadanych własności. Spektrum \(Spec(\varphi)\) zdania \(\varphi\) to zbiór wszystkich liczb naturalnych \(n\) takich, ze \(\varphi\) ma model o mocy \(n.\) Standardowy model arytmetyki to struktura \(\mathbb{N}=\langle\omega,*^{\mathbb{N}},+^{\mathbb{N}},0^{\mathbb{N}},1^{\mathbb{N}},\leq^{\mathbb{N}}\rangle.\)
Szukanie modeli dla zadanych formuł. W zadaniach ,,Pokazać, że zbiór zdań \(\Delta\) jest niezależny”, należy za każdym razem udowodnić, że dla każdego \(\varphi\in\Delta,\) \(\Delta\setminus\{\varphi\}\not\models\varphi,\) poprzez wskazanie modelu \(\Delta\setminus\{\varphi\},\) który nie jest modelem \(\varphi.\)
\(\left\{\begin{array}[]{c}\forall x\forall y(Exy\to Eyx)\\ \forall x\ Exx\\ \forall x\forall y\forall z((Exy\land Eyz)\to Exz)\end{array}\right\}\)
jest niezależny.
\(\left\{\begin{array}[]{c}\forall x\forall y((x\leq y)\lor(y\leq x))\\ \forall x\forall y((x\leq y\land y\leq x)\to x=y)\\ \forall x\forall y\forall z((x\leq y\land y\leq z)\to x\leq z)\end{array}\right\}\)
jest niezależny.
\(\Sigma^{F}_{{2}}=\{*\},\Sigma^{F}_{0}=\{ 1\}\))
\(\left\{\begin{array}[]{c}\forall x((1*x=x)\land(x*1=x))\\ \forall x\forall y\forall z((x*y)*z=x*(y*z))\\ \forall x\exists y((x*y=1)\land(y*x=1))\end{array}\right\}\)
jest niezależny.
\((\forall x\forall y((f(x)=f(y))\to(x=y)))\to(\forall x\exists y(f(y)=x))\)
nie jest tautologią. Czy jego negacja ma model skończony?
Tw. Fraïssé, gra Ehrenfeuchta.
Tw. o zwartości.
Wskazówka: Założyć, że pierwsza klasa jest aksjomatyzowalna przez \(\Delta\), a druga przez \(\Delta^{{\prime}},\) ale żaden skończony podzbiór \(\Delta\) nie jest aksjomatyzacją \(\mathcal{A}.\) Pokazać, że \(\Delta\cup\Delta^{{\prime}}\) spełnia założenia tw. o zwartości.
Wskazówka: Założyć, że dla każdego \(\varphi\) takiego, że \(\Delta\models\varphi\) zachodzi \(\Delta^{{\prime}}\not\models\lnot\varphi.\) Pokazć, że w tej sytuacji \(\Delta^{{\prime}}\cup\{\varphi\}\) jest spełnialny, a stąd, że \(\Delta\cup\Delta^{{\prime}}\) spełnia zalożenia tw. o zwartości.
Tw. Skolema-Löwenheima.
Wskazówka: Napisać zdanie pierwszego rzędu, z którego wynika, że uniwersum modelu jest mocy nie mniejszej niż moc jego kartezjańskiego kwadratu. Pokazać, że zdanie to ma model nieskończony i skorzystać z tw. Skolema-Löwenheima.
\(\mathrm{nwd}^{\mathbb{A}}(m,n)=\text{najwi"ekszy wsp"olny dzielnik $m$ i $n$.}\)\(m\) i \(n\).
Napisać formułę \(\varphi(x)\) nad \(\Sigma\) definiującą własność ,,być liczbą pierwszą”, tj., taką, że dla wszystkich wartościowań \(v:X\to\omega\)
\(\mathbb{X}\models\varphi[v]\ \ \text{wtw}\ \ \text{$v(x)$ jest liczb"a pierwsz"a.}\)\(v(x)\) jest liczbą pierwszą.
\(\displaystyle S^{\mathbb{Y}}(n) =n+1\) S Y n = + n 1 \(\displaystyle \beta^{\mathbb{Y}}(t,p,i) =\text{$\beta$}(t,p,i),\)\(\beta\) t p i β Y t p i = β t p i
gdzie \(\beta\) to funkcja beta Gödla, znana z wykładu, zaś \(\leq^{\mathbb{Y}}\) to zwykła nierówność.
Napisać formułę \(\varphi(x,y,z)\) nad \(\Sigma\) definiującą dodawanie, tj., taką, że dla wszystkich wartościowań \(v:X\to\omega\)
\(\mathbb{Y}\models\varphi[v]\ \ \text{wtw}\ \ v(x)+v(y)=v(z).\)
Podać taki przykład aksjomatyzowalnej klasy \(\mathcal{A}\) nad sygnaturą \(\Sigma\) (którą też można sobie wybrać), że \(Mod(\Sigma)\setminus\mathcal{A}\) nie jest aksjomatyzowalna.
Przypuśćmy, że \(E\) jest zbiorem równości normalnych, oraz że \(E\vdash _{{eq}}s=t.\) Udowodnić, że \(s=t\) też jest równością normalną.
\(\forall x\forall y\,(y=f(g(x))\to(\exists u\,(u=f(x)\land y=g(u))))\)
oraz niech \(\psi\) będzie zdaniem
\(\forall x\,[f(g(f(x)))=g(f(f(x)))].\)
Czy \(\{\psi\}\models\varphi?\)
Wykorzystując przestrzenie liniowe nad ciałem \(\mathbb{R}\) jako przykład, udowodnić, że może istnieć wiele różnych kongruencji \(\bar{r},\) rozszerzających daną relację równoważności \(r\) w \(G.\)