Kolokwia i egzaminy z okresu przed 2007 (stary program)

zadania 2003

  1. Proszę zdefiniować relację izomorfizmu.
  2. Proszę zdefiniować relację \(m\)-izomorfizmu i omówić jej związek z grą Ehrenfeuchta-Fraïsségo.
  3. Proszę opisać grę Ehrenfeuchta-Fraïsségo i omówić jej związek z \(m\)-izomorfizmem.
  4. Proszę zdefiniować pojęcie podstruktury indukowanej.
  5. Proszę zdefiniować pojęcie podalgebry generowanej.
  6. Proszę zdefiniować zbiór formuł logiki pierwszego rzędu i pojęcie zmiennych wolnych danej formuły.
  7. Proszę zdefiniować zbiór formuł logiki pierwszego rzędu i pojęcie rangi kwantyfikatorowej danej formuły.
  8. Proszę zdefiniować relację \(\mathbb{A}\models\varphi[s].\)
  9. Proszę zdefiniować sekwent.
  10. Proszę zdefiniować pojęcie sekwentu wyprowadzalnego (nie trzeba znać wszystkich reguł systemu Gentzena, tylko mieć orientację o ich postaci).
  11. Proszę zdefiniować relację \(\Gamma\models\varphi,\) gdzie \(\Gamma\) to zbiór zdań.
  12. Proszę zdefiniować pojęcie tautologii.
  13. Proszę zdefiniować pojęcie twierdzenia.
  14. Proszę sformułować twierdzenie o pełności.
  15. Proszę sformułować twierdzenie o zwartości.
  16. Proszę sformułować twierdzenie Skolema-Löwenheima.
  17. Proszę sformułować twierdzenie o niezupełności.

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

  1. \((\forall x\exists y\ r(x,y))\to(\exists y_{1}\exists y_{2}\forall x\ r(x,y_{1})\lor r(x,y_{1})).\)
  2. \((\forall x\ f(f(x))=x)\to(\forall x\forall y\ x\neq y\to f(x)\neq f(y)).\)
  3. \((\forall x_{1}\forall x_{2}\forall x_{3}(x_{1}=x_{3}\lor(x_{2}=x_{3}\lor x_{1}=x_{2})))\to(\forall x\exists y\ x\neq y).\)
  4. \(\forall x\forall y\exists z\ f(x,z)=y.\)
  5. \(\forall x\forall y\exists z\ f(x,y)=z.\)
  6. \((\forall x\forall y\exists z\ f(x,z)=y)\to(\exists x\ f(x,x)=x)\).
  7. \(\exists x\exists y\ (f(x)=x\to f(y)=y).\)
  8. \(\exists x\forall y\ (f(x)=x\to f(y)=y).\)
  9. \((\forall x_{1}\forall x_{2}\forall x_{3}(x_{1}=x_{3}\lor(x_{2}=x_{3}\lor x_{1}=x_{2})))\to\)\(((\forall y\exists x\ f(y)=x)\to(\forall x\forall y((x\neq y)\to f(x)\neq f(y)))).\)
  10. \((\exists x\ f(x)\neq x)\to(\exists x\exists y\ x\neq y)\).
  11. \((\forall x(\forall y\ f(x)\neq y)\to(f(x)\neq x)).\)
  12. \((\forall x\forall y\ f(x,y)=f(y,x))\to(\forall x\ f(x,f(f(x,x),x))=f(f(x,x),f(x,x))).\)
  13. \(\forall x\forall y\ f(x)=y.\)
  14. \((\forall x\exists y\ \lnot(r(x,y)\leftrightarrow r(y,x)))\land(\forall y\ \lnot r(y,y)).\)
  15. \((\forall x(\exists y\ \lnot(r(x,y)\leftrightarrow r(y,x))\land(\forall y\ \lnot r(y,y)))).\)
  16. \((\exists x(p(x)\to(\forall y\ q(y))))\to(\exists x\forall y\ p(x)\to q(y))\).
  17. \((\exists x(\forall y\ q(y))\to p(x))\to(\exists x\forall y\ q(y)\to p(x))\).
  18. \((\exists x(\forall y\ q(y))\to p(x))\to(\exists x\ q(x)\to p(x))\).
  19. \((\forall x\forall y((f(x)=f(y))\to(x=y)))\to(\forall x\exists y(f(y)=x))\).
  20. \(\exists x\exists y\exists u\exists v((\lnot u=x)\lor(\lnot v=y))\land(f(x,y)=f(u,v))\).
  21. Podać przykład zdania \(\varphi\) (sygnatura też jest do wyboru) takiego, że \(Spec(\varphi)=Spec(\lnot\varphi).\)
  22. Podać przykład zdania \(\varphi\) (sygnatura też jest do wyboru) takiego, że \(Spec(\varphi)=\{ n^{2}~/~n\in\mathbb{N}\}.\)\mathbb
  23. Podać przykład zdania \(\varphi\) (sygnatura też jest do wyboru) takiego, że \(Spec(\varphi)=\{ 2*n~/~n\in\mathbb{N}\}.\)\mathbb
  24. Znale”zć formułę \(\varphi(x,y)\) stwierdzającą w standardowym modelu arytmetyki, że \(x\) jest względnie pierwsze z \(y.\)
  25. Znale”zć formułę \(\varphi(x,y,z)\) stwierdzającą w standardowym modelu arytmetyki, że \(z\) jest największym wspólnym dzielnikiem \(x\) i \(y.\)
  26. Znale”zć formułę \(\varphi(x,y,z)\) stwierdzającą w standardowym modelu arytmetyki, że \(y\) jest największą liczbą, będącą potęgą liczby pierwszej, która dzieli \(x.\)

e

  1. Niech \(\mathbb{A}=\langle\omega\setminus\{ 0\},\mathrm{nwd}^{\mathbb{A}}\rangle\) będzie algebrą, gdzie \(\mathrm{nwd}\in\Sigma^{F}_{2},\) przy czym dla wszystkich \(m,n\in\omega\)

    \(\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ą.

  2. Niech \(\mathbb{Y}=\langle\omega,S^{\mathbb{Y}},\beta^{\mathbb{Y}},\leq^{\mathbb{Y}}\rangle\) będzie strukturą nad sygnaturą \(\Sigma,\) która składa się z symboli \(S\in\Sigma^{F}_{1},\) \(\beta\in\Sigma^{F}_{3}\) oraz \(\leq\in\Sigma^{R}_{2},\) przy czym dla każdych \(n,t,p,i\in\omega\)

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

  3. Wykazać, że jeśli klasa \(\mathcal{A}\) struktur pewnej ustalonej sygnatury \(\Sigma\) nie jest aksjomatyzowalna, to klasa \(Mod(\Sigma)\setminus\mathcal{A},\) złożona z wszystkich tych struktur sygnatury \(\Sigma,\) które nie należą do \(\mathcal{A},\) nie jest definiowalna.

    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.

  4. Przypuśćmy, że \(\Delta\) jest zbiorem zdań nad sygnaturą \(\Sigma,\) który ma tylko modele nieskończone, oraz, że każde dwa przeliczalne modele \(\Delta\) są izomorficzne (o takich \(\Delta\) mówi się, że są \(\aleph _{0}\)-kategoryczne). Udowodnić, że dla każdego zdania \(\varphi\) nad \(\Sigma,\) albo \(\Delta\models\varphi\) albo \(\Delta\models\lnot\varphi\) (innymi słowy, \(\Delta\) jest zupełny).
  5. Równość \(s=t\) nazywamy normalną, gdy \(FV(s)=FV(t),\) tj., w \(s\) i \(t\) występują dokładnie te same zmienne.

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

  6. Niech \(\varphi\) będzie zdaniem

    \(\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?\)

  7. Udowodnić, że klasa wszystkich struktur \(\mathbb{A}=\langle A,E^{\mathbb{A}}\rangle\) nad sygnaturą składającą się z jednego dwuargumentowego symbolu relacyjnego \(E\) i takich, że \(E^{\mathbb{A}}\) jest relacją równoważności, która ma wyłącznie klasy abstrakcji parzystej mocy, nie jest definiowalna.
  8. Niech \(\mathbb{A}\) będzie algebrą wolną ze zbiorem wolnych generatorów \(G\), w pewnej klasie \(\mathcal{A}.\) Udowodnić, że dla każdej relacji równoważności \(r\subseteq G\times G\) istnieje kongruencja \(\bar{r}\subseteq A\times A\) taka, że \(\bar{r}\cap(G\times G)=r.\) (Można to wyrazić stwierdzeniem, że \(r\) roszerza się do kongruencji w \(\mathbb{A}.\))

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

  9. Opisać wszystkie kongruencje algebry \(\mathbb{A}=\langle\{ 0,1,2,3\},\min^{\mathbb{A}},\max^{\mathbb{A}}\rangle,\) gdzie \(\min,\max\in\Sigma^{F}_{2}\), a \(\min^{\mathbb{A}},\max^{\mathbb{A}}\) są odpowiednio operacjami maksimum i minimum.
  10. Niech \(\mathbb{P}=\langle\mathcal{P}(\omega),\cap^{\mathbb{P}},\cup^{\mathbb{P}}\rangle\) będzie kratą podzbiorów \(\omega\) ze zwykłymi działaniami teoriomnogościowymi. Udowodnić, że \(\mathbb{P}\times\mathbb{P}\cong\mathbb{P}.\)

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

Egzamin z logiki, 04/09/2000

  1. Niech \(\mathbb{N}\) będzie standardowym modelem arytmetyki, nad standardową sygnaturą, składającą się z symboli \(+,*,0,1,\leq.\)

    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}\)

  2. Niech \(\mathcal{A}\) będzie klasą algebr nad pewną algebraiczną sygnaturą \(\Sigma.\) Niech \(Spec(\mathcal{A})\) oznacza, tak jak niegdyś na kolokwium, spektrum \(\mathcal{A},\) czyli zbiór \(\{ n\in\omega~/~\text{istnieje $\mathbb{A}\in\mathcal{A}$ takie, \.{z}e $|A|=n.$}\}.\)\(\mathbb{A}\in\mathcal{A}\) takie, że \(|A|=n.\)

    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.

  3. Niech \(\Sigma\) będzie sygnaturą algebraiczną, składającą się z jednego symbolu \(f\in\Sigma^{F}_{2}.\) Rozpatrujemy algebrę \(\mathbb{E}=\langle\omega,f^{\mathbb{E}}\rangle,\) gdzie

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

  4. Niech dany będzie niesprzeczny, skończony zbiór zdań \(\Delta\) nad pewną ustaloną i również skończoną sygnaturą \(\Sigma.\) Wykazać, że istnieje zbiór \(\Delta _{0}\subseteq\Delta\) taki, że \(\Delta _{0}\models\Delta,\) a ponadto zdania w \(\Delta _{0}\) są niezależne: dla każdego \(\varphi\in\Delta _{0}\) mamy \(\Delta _{0}\setminus\{\varphi\}\not\models\varphi.\)
  5. Podać charakteryzację zbioru wszystkich liczb kardynalnych (mocy) \(\mathfrak{n}\) takich, że zachodzi następująca własność:

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

  6. Równość \(s=t\) nad sygnaturą algebraiczną \(\Sigma\) nazywamy dziwną, gdy \(FV(s)\cap FV(t)=\emptyset,\) a ponadto żaden z termów \(s,t\) nie jest zmienną.

    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?\)

  7. Niech \(\varphi\) będzie zdaniem

    \(\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?

  8. Udowodnić, że klasa wszystkich struktur \(\mathbb{A}=\langle A,E^{\mathbb{A}}\rangle\) nad sygnaturą składającą się z jednego dwuargumentowego symbolu relacyjnego \(E\) i takich, że \(E^{\mathbb{A}}\) jest relacją równoważności, która nie zawiera dwóch klas abstrakcji równej mocy, nie jest aksjomatyzowalna.
  9. Niech \(\mathbb{B}\) będzie wolną algebrą Boole'a (t.j., algebrą wolną w klasie wszystkich algebr Boole'a) ze zbiorem wolnych generatorów \(G\) o mocy \(\mathfrak{c}\). Jakiej mocy jest zbiór wszystkich podalgebr \(\mathbb{B}?\)
  10. Niech sygnatura algebraiczna \(\Sigma\) zawiera wyłącznie jeden symbol \(f\) operacji jedoargumentowej. Zakładamy, że \(3\)-elementowa algebra \(\mathbb{A}\) nad \(\Sigma\) ma dokładnie dwie kongruencje. Udowodnić, że istnieje pojedynczy element \(x\in A\) taki, który generuje całą algebrę \(\mathbb{A},\) t.j., \([x]=\mathbb{A}.\)

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.

Egzamin poprawkowy z Logiki dla Informatyków, 2010

Zad. 1 (3 punkty)

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.

Zad. 2 (3 punkty)

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.

Zad. 3 (3 punkty)

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.

Zad. 4 (3 punkty)

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

Zad. 5 (1.5 punkta)

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!

  • Czy teoria pierwszego rzędu ciała liczb zespolonych \(\mathfrak{C}=\langle\mathbb{C},+,\cdot,0,1\rangle\) jest rozstrzygalna?
  • Czy dla każdego zbioru zdań \(\Gamma\) istnieje minimalny ze względu na zawieranie podzbiór \(\Gamma^{{\prime}}\subseteq\Gamma\) spełniający \(\Gamma^{{\prime}}\models\Gamma\)?
  • Czy problem SAT dla zdaniowej logiki trójwartościowej Bochvara jest NP-zupełny?
  • Czy formuła \(p\lor(q\to\lnot p)\) jest tautologią zdaniowej logiki intuicjonistycznej?

Egzamin poprawkowy z Logiki dla Informatyków, 2010 popr

Zad. 1 (3 punkty)

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.

Zad. 2 (3 punkty)

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.

Zad. 3 (3 punkty)

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.

Zad. 4 (3 punkty)

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

Zad. 5 (3 punkty)

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.

egzamin

  1. Niech \(\mathbb{A}=\langle\omega\setminus\{ 0\},\mathrm{nwd}^{\mathbb{A}},1^{\mathbb{A}}\rangle\) będzie algebrą, gdzie \(\mathrm{nwd}\in\Sigma^{F}_{2}\) oraz \(1\in\Sigma^{F}_{0},\) przy czym dla wszystkich \(m,n\in\omega\)

    \(\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.

  2. Niech \(\mathbb{X}=\langle\omega,+^{\mathbb{X}}, beta^{\mathbb{X}},0^{\mathbb{X}},1^{\mathbb{X}}\rangle\) będzie strukturą nad sygnaturą \(\Sigma,\) która składa się z symboli \(0,1\in\Sigma^{F}_{0}\) i \(+,\beta\in\Sigma^{F}_{2},\) przy czym dla każdych \(t,p\in\omega\)

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

  3. Niech \(\mathbb{Y}=\langle\omega,S^{\mathbb{Y}},\beta^{\mathbb{Y}}\rangle\) będzie strukturą nad sygnaturą \(\Sigma,\) która składa się z dwóch symboli \(S\in\Sigma^{F}_{1}\) i \(\beta\in\Sigma^{F}_{2},\) przy czym dla każdych \(n,t,p\in\omega\)

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

  4. Niech \(\mathbb{P}=\langle\mathcal{P}(\omega),\cap^{\mathbb{P}},\cup^{\mathbb{P}}\rangle\) będzie kratą podzbiorów \(\omega\) ze zwykłymi działaniami teoriomnogościowymi. Udowodnić, że \(\mathbb{P}\times\mathbb{P}\cong\mathbb{P}.\)
  5. Niech \(\Sigma\) będzie zwykłą sygnaturą ciał, wzbogaconą o jeden jednoargumentowy symbol relacyjny \(A.\) Rozpatrujemy struktury postaci \(\mathbb{R}_{A}=\langle R,+^{\mathbb{R}},*^{\mathbb{R}},-^{\mathbb{R}},0^{\mathbb{R}},1^{\mathbb{R}},A\rangle,\) gdzie \(R\) to zbiór liczb rzeczywistych, wszystkie operacje mają zwykłe interpretacje, zaś \(A\subseteq R\) jest dowolny.

    Napisać zdanie pierwszego rzędu \(\varphi\) nad \(\Sigma\) takie, że \(\mathbb{R}_{A}\models\varphi\) wtw \(A\) jest zbiorem domkniętym.

  6. Wykazać, że jeśli klasa \(\mathcal{A}\) struktur pewnej ustalonej sygnatury \(\Sigma\) nie jest aksjomatyzowalna, to klasa \(Mod(\Sigma)\setminus\mathcal{A},\) złożona z wszystkich tych struktur sygnatury \(\Sigma,\) które nie należą do \(\mathcal{A},\) nie jest definiowalna.

    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.

  7. Przypuśćmy, że \(\Delta\) jest zbiorem zdań nad sygnaturą \(\Sigma,\) który ma model nieskończony, oraz, że każde dwa przeliczalne modele \(\Delta\) są izomorficzne (o takich \(\Delta\) mówi się, że są \(\aleph _{0}\)-kategoryczne). Udowodnić, że dla każdego zdania \(\varphi\) nad \(\Sigma,\) albo \(\Delta\models\varphi\) albo \(\Delta\models\lnot\varphi\) (innymi słowy, \(\Delta\) jest zupełny).
  8. Równość \(s=t\) nazywamy normalną, gdy \(FV(s)=FV(t),\) tj., w \(s\) i \(t\) występują dokładnie te same zmienne.

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

  9. Niech \(\varphi\) będzie zdaniem

    \(\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?\)

  10. Rozważmy algebrę \(\mathbb{A}=\langle\omega,f^{\mathbb{A}},\rangle,\) gdzie \(f\in\Sigma^{F}_{2}\) oraz

    \(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.]

  11. Opisać wszystkie kongruencje grupy \(\mathbb{Z}_{4}.\)
  12. Udowodnić, że klasa wszystkich struktur \(\mathbb{A}=\langle A,E^{\mathbb{A}}\rangle\) nad sygnaturą składającą się z jednego dwuargumentowego symbolu relacyjnego \(E\) i takich, że \(E^{\mathbb{A}}\) jest relacją równoważności, która ma wyłącznie klasy abstrakcji parzystej mocy, nie jest definiowalna.
  13. Niech \(\mathbb{A}\) będzie algebrą wolną ze zbiorem wolnych generatorów \(G\), w pewnej klasie \(\mathcal{A}.\) Udowodnić, że dla każdej relacji równoważności \(r\subseteq G\times G\) istnieje kongruencja \(\bar{r}\subseteq A\times A\) taka, że \(\bar{r}\cap(G\times G)=r.\) (Można to wyrazić stwierdzeniem, że \(r\) roszerza się do kongruencji w \(\mathbb{A}.\))

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

  14. Opisać wszystkie kongruencje algebry \(\mathbb{A}=\langle\{ 0,1,2,3\},\min^{\mathbb{A}},\max^{\mathbb{A}}\rangle,\) gdzie \(\min,\max\in\Sigma^{F}_{2}\), a \(\min^{\mathbb{A}},\max^{\mathbb{A}}\) są odpowiednio operacjami maksimum i minimum.
  15. 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ń.

Egzamin z logiki, 13/06/2001

  1. Niech \(\Sigma\) będzie sygnaturą składającą się z jednego jednoargumentowego symbolu funkcyjnego \(f.\) Czy klasa wszystkich algebr \(\mathbb{A}\) nad \(\Sigma\) takich, że \(f^{\mathbb{A}}\) jest bijekcją, jest rozmaitością algebr?
  2. Niech \(\mathbb{Z}=\langle Z,+^{\mathbb{Z}},*^{\mathbb{Z}},-^{{\mathbb{Z}}},0^{\mathbb{Z}},1^{\mathbb{Z}}\rangle\) będzie zwykłym pierścieniem liczb całkowitych, oraz niech \(\mathcal{Z}\) będzie najmniejszą rozmaitością algebr zawierającą \(\mathbb{Z}.\) W jaki sposób należy określić operacje w zbiorze \(\mathbb{Z}[X]\) wielomianów jednej zmiennej \(X\) nad \(\mathbb{Z},\) aby tak otrzymana algebra była wolna w \(\mathcal{Z}\) nad pewnym jednoelementowym zbiorem wolnych generatorów? (Wystarczy podać jeden sposób.)
  3. Niech \(\mathbb{Q}=\langle Q,+^{\mathbb{Q}},*^{\mathbb{Q}},0^{\mathbb{Q}},1^{\mathbb{Q}}\rangle\) będzie pierścieniem liczb wymiernych, przy czym wszystkie operacje i stałe mają swoje zwykłe znaczenie. Udowodnić, że jeśli \(h:\mathbb{Q}\to\mathbb{Q}\) jest homomorfizmem, to \(h=\mathrm{id}.\)
  4. Niech \(\varphi _{1},\varphi _{2},\dots\) oraz \(\psi\) będą zdaniami na pewną ustaloną sygnaturą. Niech \(T\) będzie zbiorem zdań

    \(\{\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\)?

  5. Niech \(\mathcal{C}\) będzie klasą wszystkich grafów, skończonych i nieskończonych, które zawierają cykl. Udowodnić, że klasa \(\mathcal{C}\) nie jest definiowalna.
  6. Niech \(\mathbb{N}\) będzie standardowym modelem arytmetyki, nad standardową sygnaturą, składającą się z symboli \(+,*,0,1,\leq.\)

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

  7. Niech \(\mathbb{Z}_{n}=\langle\{ 0,1,\dots,n-1\},+^{{\mathbb{Z}_{n}}}\rangle,\) gdzie \(+\in\Sigma^{F}_{2}\), a \(+^{{\mathbb{Z}_{n}}}\) jest operacją dodawania modulo \(n.\)

    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}?\)

  8. Niech \(FINSAT_{\Sigma}\) będzie zbiorem wszystkich tych zdań logiki pierwszego rzędu nad pewną skończoną sygnaturą \(\Sigma,\) które są spełnialne w pewnej skończonej strukturze nad \(\Sigma.\)

    Udowodnić, że zbiór \(FINSAT_{\Sigma}\) jest algorytmicznie generowalny.

  9. Niech \(\mathbb{A}\) będzie algebrą, której krata kongruencji ma następującą postać:

    \(\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ść.

  10. Niech \(\mathbb{F}=\langle\omega^{\omega},\circ,\mathrm{id}\rangle\) będzie algebrą, w której \(\omega^{\omega}\) to zbiór wszystkich funkcji z liczb naturalnych w liczby naturalne, \(\circ\) to operacja składania funkcji (dla przypomnienia: \((f\circ g)(x)=f(g(x))\)), zaś \(\mathrm{id}\) to funkcja identycznościowa.

    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})]).\)

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

Egzamin z logiki dla MSUI, 27/06/2001

  1. Dla ustalonego \(k\in\mathbb{N},\) podać przykład zdania \(\varphi\) (sygnatura jest do wyboru i może zależeć od \(k\)) takiego, że dla każdego naturalnego \(n,\) \(\varphi\) ma dokładnie \({n \choose k}\) nieizomorficznych modeli mocy \(n.\)
  2. Niech \(\mathcal{C}\) będzie klasą wszystkich grafów (nieskierowanych), skończonych i nieskończonych, których wszystkie składowe spójne są skończone. Udowodnić, że klasa \(\mathcal{C}\) nie jest definiowalna.
  3. Niech \(\mathbb{N}\) będzie standardowym modelem arytmetyki, nad standardową sygnaturą, składającą się z symboli \(+,*,0,1,\leq.\)
    Napisać formułę \(\varphi(x,y,z)\) nad sygnaturą arytmetyki definiującą funkcję \(y=\lfloor\sqrt[z]{x}\rfloor,\) tzn. taką, że dla wszystkich wartościowań \(v:X\to\omega\)

    \(\mathbb{N}\models\varphi[v]\ \ \text{wtw}\ \ v(y)=\lfloor(v(x))^{{\frac{1}{v(z)}}}\rfloor.\)

  4. Niech \(\mathbb{Z}_{n}=\langle\{ 0,1,\dots,n-1\},+^{{\mathbb{Z}_{n}}}\rangle,\) gdzie \(+\in\Sigma^{F}_{2}\), a \(+^{{\mathbb{Z}_{n}}}\) jest operacją dodawania modulo \(n.\)

    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}?\)

  5. Niech \(FINSAT_{\Sigma}\) będzie zbiorem wszystkich tych zdań logiki pierwszego rzędu nad pewną skończoną sygnaturą \(\Sigma,\) które są spełnialne w pewnej skończonej strukturze nad \(\Sigma.\)

    Udowodnić, że zbiór \(FINSAT_{\Sigma}\) jest algorytmicznie generowalny.

  6. Niech \(\Sigma\) będzie sygnaturą składającą się z jednego dwuargumentowego symbolu relacyjnego \(E.\)

    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.

Egzamin ze wstępu do logiki, ZSI, 2005/2006.

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.

  1. Proszę rozstrzygnąć, czy następujące zdanie jest tautologią i czy jest spełnialne:

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

  2. Dana jest struktura \(\mathbb{P}=\langle P,r^{\mathbb{P}}\rangle,\) której uniwersum \(P\) stanowi zbiór wszystkich okręgów o promieniu 1 na płaszczyźnie, a dwuargumentowa relacja \(r^{\mathbb{P}}\) jest określona w ten sposób, że \(r^{\mathbb{P}}(o_{1},o_{2})\) wtw \(o_{1}\) i \(o_{2}\) są styczne zewnętrznie.

    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.

  3. Dane są dwie struktury relacyjne \(\mathbb{A}=\langle A,r^{\mathbb{A}}\rangle\) i \(\mathbb{B}=\langle B,r^{\mathbb{B}}\rangle\) nad sygnaturą złożoną z jednego dwuargumentowego symbolu relacyjnego. \(A=\{ 0,1,2,\dots,6\}\) oraz \(B=\{ 1,2,\dots,6\}\), a relacje określone są jak następuje:
    \(r^{\mathbb{A}}(x,y)\) wtw \(x\equiv y-1\;\;(\textrm{mod}3),\)
    \(r^{\mathbb{B}}(x,y)\) wtw \(x\equiv y-1\;\;(\textrm{mod}3).\)

    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.

  4. Proszę wyprowadzić w systemie Gentzena sekwent

    \(\forall x\exists y(R(x)\to S(y))\vdash(\exists xR(x))\to(\exists yS(y)).\)

  5. Pokazać, że w logice Sobocińskiego nie można za pomocą alternatywy, koniunkcji i negacji zdefiniować alternatywy z logiki Heytinga-Kleene-Łukasiewicza.
  6. 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}\ \ \ \ \)

Egzamin z logiki, 06/09/2001

  1. Niech \(\Sigma\) będzie sygnaturą składającą się z jednego jednoargumentowego symbolu funkcyjnego \(f.\) Udowodnić, że każda algebra \(\mathbb{A}\) sygnatury \(\Sigma\) o więcej niż jednym elemencie ma nietrywialny (tzn. różny od identyczności) homomorfizm \(h:\mathbb{A}\to\mathbb{A}\).
  2. Niech zbiór \(X\) będzie spektrum zdania \(\varphi\) sygnatury \(\Sigma\), tzn., niech \(X=\{ n\in\mathbb{N}~/~\text{istnieje struktura $\mathbb{A}$ nad $\Sigma$ t.że $|A|=n$ i $\mathbb{A}\models\varphi$}\}.\)\(\mathbb{A}\) nad \(\Sigma\) t.że \(|A|=n\) i \(\mathbb{A}\models\varphi\)}.

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

    1. Skonstruować algebrę \(\mathbb{A}\) i klasę algebr \(\mathcal{A}\) takie, że \(\mathbb{A}\) jest wolna w \(\mathcal{A}\) nad dwoma różnymi niepustymi zbiorami wolnych generatorów \(G_{1},G_{2}\) takimi, że \(G_{1}\cap G_{2}=\emptyset.\)
    2. Skonstruować algebrę \(\mathbb{A}\) i klasę algebr \(\mathcal{A}\) takie, że \(\mathbb{A}\) jest wolna w \(\mathcal{A}\) nad dokładnie jednym niepustym zbiorem wolnych generatorów.
  3. Niech \(\mathcal{C}\) będzie klasą wszystkich grafów, skończonych i nieskończonych, które są \(n\)-dzielne, dla pewnego \(n\in\mathbb{N}.\) Graf \(\mathbb{G}\) jest \(n\)-dzielny jeśli istnieje podział jego zbioru wierzchołków \(G\) na niepuste i rozłączne podzbiory \(G_{1},\dots,G_{n}\) tak, że każda z podstruktur indukowanych \(\mathbb{G}_{{|G_{i}}}\) nie zawiera żadnych krawędzi. Przykładowo, graf pełny o \(n\) wierzchołkach \(\mathbb{K}_{n}\) jest \(n\)-dzielny, ale nie \(m\)-dzielny dla \(m< n.\)

    Udowodnić, że klasa \(\mathcal{C}\) nie jest definiowalna.

  4. Niech \(\mathbb{W}=\langle\{ 0,1\}^{+},\circ^{\mathbb{W}},0^{\mathbb{W}},1^{\mathbb{W}},r^{\mathbb{W}}\rangle\) będzie strukturą, w której \(\{ 0,1\}^{+}\) to zbiór wszystkich niepustych skończonych ciągów zerojedynkowych, \(\circ^{\mathbb{W}}\) to operacja konkatenacji ciągów (\(\langle x_{1}\dots x_{n}\rangle\circ^{\mathbb{W}}\langle y_{1}\dots y_{m}\rangle=\langle x_{1}\dots x_{n}y_{1}\dots y_{m}\rangle,\) \(0^{\mathbb{W}}\) i \(1^{\mathbb{W}}\) to ciągi jednoelementowe \(\langle 0\rangle\) i \(\langle 1\rangle\), zaś \(r^{\mathbb{W}}\) jest relacją jednoargumentową określoną przez \(r^{\mathbb{W}}(w)\) wtw. gdy każdy prefiks \(w\) zawiera nie więcej jedynek niż zer, a w całym ciągu \(w\) ilość jednek i zer jest jednakowa.

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

  5. Niech \(\mathbb{N}\) będzie standardowym modelem arytmetyki, nad standardową sygnaturą, składającą się z symboli \(+,*,0,1,\leq.\)

    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.

  6. Niech \(\mathbb{Z}_{{8}}=\langle\{ 0,1,\dots,7\},S^{{\mathbb{Z}_{{8}}}},0^{{\mathbb{Z}_{{8}}}}\rangle,\) gdzie \(S^{{\mathbb{Z}_{{8}}}}\) jest operacją następnika modulo \(8,\) zaś \(0^{{\mathbb{Z}_{{8}}}}\) to \(0.\)

    Proszę opisać wszystkie kongruencje algebry \(\mathbb{Z}_{{8}}.\)

  7. Niech sygnatura algebraiczna \(\Sigma\) składa się z symboli stałych \(a,b,c\) i nie zawiera innych symboli. Niech \(\mathbb{A}\) i \(\mathbb{B}\) będą dwuelementowymi algebrami sygnatury \(\Sigma\) takimi, że \(a^{\mathbb{A}}=b^{\mathbb{A}}\neq c^{\mathbb{A}},\) zaś \(a^{\mathbb{B}}\neq b^{\mathbb{B}}=c^{\mathbb{B}}.\) Udowodnić, że każda rozmaitość algebr nad \(\Sigma\) zawierająca jednocześnie \(\mathbb{A}\) i \(\mathbb{B}\) zawiera wszystkie algebry nad \(\Sigma.\)
  8. Niech \(c,d\) będą dwoma symbolami pewnej sygnatury algebraicznej \(\Sigma,\) która poza tym może zawierać także inne symbole funkcyjne, o różnych ilościach argumentów. Zbiór \(E\) równości nad \(\Sigma\) nazwiemy symetrycznym, gdy każda równość \(t=s\) należy do \(E\) wtedy i tylo wtedy, gdy równość otrzymana z \(t=s\) przez (jednoczesną) zamianę wystąpień \(c\) na \(d\) oraz \(d\) na \(c,\) też należy do \(E.\)

    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.

  9. PDF wygląda inaczej

    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.

Kolokwium poprawkowe z logiki, 31/05/2001

  1. Skonstruuj przykłady dwóch nieizomorficznych nieskończonych grafów \(\mathbb{A}\) i \(\mathbb{B}\) takich, że istnieją różnowartościowe homomorfizmy grafów \(g:\mathbb{B} \to \mathbb{A}\) i \(\mathbb{A} \cong \mathbb{B}.\)

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

  2. Niech \(\varphi _{0}\equiv\exists x\exists y(x\neq y),\)
    \(\varphi _{1}\equiv\forall x(\lnot E(x,x))\),
    \(\varphi _{2}\equiv\forall x\forall y(E(x,y)\to E(y,x)),\)
    \(\varphi _{3}\equiv\forall x\forall y((x\neq y)\to\exists z(E(x,z)\land E(y,z))).\)
    Udowodnić, że \(\{\varphi _{0},\varphi _{1},\varphi _{2},\varphi _{3}\}\models\exists x\exists y\exists z(E(x,y)\land E(x,z)\land E(z,y)).\)
  3. Klasa \(\mathcal{A}\) jest złożona z wszystkich nieskierowanych grafów (skończonych lub nie) \(\mathbb{A}=\langle A,E^{\mathbb{A}}\rangle\) (nad sygnaturą składającą się z jednego dwuargumentowego symbolu relacyjnego \(E\)) o następującej własności: każda składowa spójna \(\mathbb{A}\) jest skończona.

    Udowodnić, że klasa \(\mathcal{A}\) nie jest aksjomatyzowalna, tj., że nie istnieje zbiór \(T\) zdań taki, że \(\mathcal{A}=Mod(T).\)

  4. Niech \(\Sigma\) będzie zwykłą sygnaturą ciał z porządkiem, wzbogaconą o jeden jednoargumentowy symbol funkcyjny \(f.\) Rozpatrujemy struktury postaci

    \(\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.

KP_PDF - Kolokwium poprawkowe z logiki, 31/05/2001

  1. Skonstruuj przykłady dwóch nieizomorficznych nieskończonych grafów \(\mathbb{A}\) i \(\mathbb{B}\) takich, że istnieją różnowartościowe homomorfizmy grafów \(g:\mathbb{B}\to\mathbb{A}\) i \(h:\mathbb{A}\to\mathbb{B}.\)

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

  2. Niech \(\varphi _{0}\equiv\exists x\exists y(x\neq y),\)\(\varphi _{1}\equiv\forall x(\lnot E(x,x))\),\(\varphi _{2}\equiv\forall x\forall y((x\neq y)\to\exists z(E(x,z)\land E(y,z))).\)

    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}\}?\)

  3. Klasa \(\mathcal{A}\) jest złożona z wszystkich częściowych porządków o tej własności, że żaden zawarty w nich skończony łańcuch nie jest maksymalny.

    Skonstruować zbiór zdań \(T\) nad zwykłą sygnaturą porządków \(\Sigma,\) taki, że \(\mathcal{A}=Mod(T).\)

  4. Niech \(\Sigma\) będzie zwykłą sygnaturą ciał z porządkiem, wzbogaconą o jeden jednoargumentowy symbol funkcyjny \(f.\) Rozpatrujemy struktury postaci

    \(\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ęć).

Kolokwium poprawkowe z logiki, 31/05/200

  1. Udowodnij, że istnieją nieskończone nieizomorficzne grafy \(\mathbb{A}\not\cong\mathbb{B}\) takie, że istnieją przekształcenia \(h:\mathbb{A}\to\mathbb{B}\) i \(g:\mathbb{B}\to\mathbb{A},\) które są różnowartościowymi homomorfizmami grafów.
  2. Niech \(\varphi _{0}\equiv\exists x\exists yx\neq y,\) \(\varphi _{1}\equiv\forall x\lnot E(x,x)\), \(\varphi _{2}\equiv\forall x\forall y(x\neq y)\to\exists z(E(x,z)\land E(z,y)).\)

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

  3. Udowodnij, że klasa \(\mathcal{A}\) złożona z wszystkich (być może nieskończonych) grafów regularnych, tj., grafów których wszystkie wierzchołki mają ten sam stopień, nie jest definiowalna.
  4. Niech \(\Sigma\) będzie zwykłą sygnaturą ciał, wzbogaconą o jeden jednoargumentowy symbol funkcyjny \(f.\) Rozpatrujemy struktury postaci \(\mathbb{R}_{f}=\langle R,+^{\mathbb{R}},*^{\mathbb{R}},-^{\mathbb{R}},0^{\mathbb{R}},1^{\mathbb{R}},f\rangle,\) gdzie \(R\) to zbiór liczb rzeczywistych, wszystkie operacje mają zwykłe interpretacje, zaś \(f:R\to R\) jest dowolną funkcją.

    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.

Kolokwium z logiki, 19/04/2001

  1. Udowodnij, że jeżeli przekształcenia \(h:\mathbb{A}\to\mathbb{B}\) i \(g:\mathbb{B}\to\mathbb{A}\) są różnowartościowymi homomorfizmami grafów, to \(\mathbb{A}\cong\mathbb{B}.\)
  2. Niech \(\varphi _{0}\equiv\exists x\exists yx\neq y,\) \(\varphi _{1}\equiv\forall x\lnot E(x,x)\), \(\varphi _{2}\equiv\forall x\forall y(E(x,y)\to E(y,x)),\) \(\varphi _{3}\equiv\forall x\forall y(x\neq y)\to\exists z(E(x,z)\land E(y,z)).\)

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

  3. Udowodnij, że klasa \(\mathcal{A}\) złożona z wszystkich (być może nieskończonych) grafów regularnych, tj., grafów których wszystkie wierzchołki mają ten sam stopień, nie jest definiowalna.
  4. Niech \(\Sigma\) będzie zwykłą sygnaturą ciał, wzbogaconą o jeden jednoargumentowy symbol funkcyjny \(f.\) Rozpatrujemy struktury postaci \(\mathbb{R}_{f}=\langle R,+^{\mathbb{R}},*^{\mathbb{R}},-^{\mathbb{R}},0^{\mathbb{R}},1^{\mathbb{R}},f\rangle,\) gdzie \(R\) to zbiór liczb rzeczywistych, wszystkie operacje mają zwykłe interpretacje, zaś \(f:R\to R\) jest dowolną funkcją.

    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.

Zadania przygotowawcze z logiki Wersja 2.

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

  1. Podać przykład zdania \(\varphi\) (sygnatura też jest do wyboru) takiego, że \(Spec(\varphi)=Spec(\lnot\varphi).\)
  2. Podać przykład zdania \(\varphi\) (sygnatura też jest do wyboru) takiego, że \(Spec(\varphi)=\{ n^{2}~/~n\in\mathbb{N}\}.\)
  3. Podać przykład zdania \(\varphi\) (sygnatura też jest do wyboru) takiego, że \(Spec(\varphi)=\{ 2*n~/~n\in\mathbb{N}\}.\)
  4. Podać przykład zdania \(\varphi\) (sygnatura też jest do wyboru) takiego, że \(Spec(\varphi)=\{ n~/~n\in\mathbb{N}\ \text{i $n$ jest liczb"a z"lo"ron"a}\}.\)\(n\) jest liczbą złożoną}.
  5. Podać przykład zdania \(\varphi\) (sygnatura też jest do wyboru) takiego, że \(Spec(\varphi)=\{ 2^{n}~/~n\in\mathbb{N}\}.\)
  6. Podać przykład zdania \(\varphi\) (sygnatura też jest do wyboru) takiego, że dla każdego naturalnego \(n,\) \(\varphi\) ma dokładnie \(n\) nieizomorficznych modeli mocy \(n.\)
  7. Podać przykład zdania \(\varphi\) (sygnatura też jest do wyboru) takiego, że dla każdego naturalnego \(n,\) \(\varphi\) ma dokładnie \(2^{n}\) nieizomorficznych modeli mocy \(n.\)
  8. Podać przykład zdania \(\varphi\) (sygnatura też jest do wyboru) takiego, że dla każdego naturalnego \(n,\) \(\varphi\) ma dokładnie \(n!\) nieizomorficznych modeli mocy \(n.\)
  9. Dla ustalonego \(k\in\mathbb{N},\) podać przykład zdania \(\varphi\) (sygnatura też jest do wyboru) takiego, że dla każdego naturalnego \(n,\) \(\varphi\) ma dokładnie \({n \choose k}\) nieizomorficznych modeli mocy \(n.\)
  10. Dla ustalonego \(k\in\mathbb{N},\) podać przykład zdania \(\varphi\) (sygnatura też jest do wyboru) takiego, że dla każdego naturalnego \(n,\) \(\varphi\) ma dokładnie \(n^{k}\) nieizomorficznych modeli mocy \(n.\)
  11. Znaleźć formułę \(\varphi(x,y)\) stwierdzającą w standardowym modelu arytmetyki, że \(x\) jest względnie pierwsze z \(y.\)
  12. Znaleźć formułę \(\varphi(x,y,z)\) stwierdzającą w standardowym modelu arytmetyki, że \(z\) jest największym wspólnym dzielnikiem \(x\) i \(y.\)
  13. Znaleźć formułę \(\varphi(x,y,z)\) stwierdzającą w standardowym modelu arytmetyki, że \(y\) jest największą liczbą, będącą potęgą liczby pierwszej, która dzieli \(x.\)

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

  1. Pokazać, że zbiór aksjomatów relacji równoważności

    \(\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.

  2. Pokazać, że zbiór aksjomatów liniowych porządków

    \(\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.

  3. Pokazać, że zbiór aksjomatów teorii grup (w zapisie multiplikatywnym, nad sygnaturą

    \(\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.

  4. Pokazać, że zdanie \((\forall x\exists y\ Exy)\to(\exists x\forall y\ Exy)\) nie jest tautologią.
  5. Pokazać, że zdanie

    \((\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?

  6. Pokazać, że zdanie \(\exists x\exists y\exists u\exists v((\lnot u=x)\lor(\lnot v=y))\land(f(x,y)=f(u,v))\) nie jest tautologią. Ile nieizomorficznych modeli skończonych ma to zdanie?

Tw. Fraïssé, gra Ehrenfeuchta.

  1. Udowodnić, że klasa wszystkich struktur \(\mathbb{A}=\langle A,r^{\mathbb{A}}\rangle,\) gdzie \(r\in\Sigma^{R}_{1}\) oraz takich, że \(|r^{\mathbb{A}}|=|A\setminus r^{\mathbb{A}}|\) nie jest aksjomatyzowalna.
  2. Udowodnić, że klasa wszystkich struktur \(\mathbb{A}=\langle A,E^{\mathbb{A}}\rangle\) nad sygnaturą składającą się z jednego dwuargumentowego symbolu relacyjnego \(E\) i takich, że \(|\{(a,b)\in A\times A~/~(a,b)\in E^{\mathbb{A}}\}|< |\{(a,b)\in A\times A~/~(a,b)\notin E^{\mathbb{A}}\}|,\) nie jest aksjomatyzowalna.
  3. Udowodnić, że klasa wszystkich struktur \(\mathbb{A}=\langle A,E^{\mathbb{A}}\rangle\) nad sygnaturą składającą się z jednego dwuargumentowego symbolu relacyjnego \(E\) i takich, że \(E^{\mathbb{A}}\) jest zbiorem skończonym, nie jest definiowalna.
  4. Pokazać, że klasa wszystkich relacji równoważności, które mają skończenie wiele klas abstrakcji, nie jest aksjomatyzowalna.

Tw. o zwartości.

  1. Pokazać, że jeśli klasa \(\mathcal{A}\) struktur nad sygnaturą \(\Sigma\) jest aksjomatyzowalna i jej dopełnienie \(Mod(\Sigma)\setminus\mathcal{A}\) struktur sygnatury \(\Sigma,\) ktore nie nalezą do \(\mathcal{A},\) jest aksjomatyzowalne, to obie klasy są w istocie definiowalne.

    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.

  2. Pokazać następujące tw. Robinsona: Jeśli \(\Delta,\Delta^{{\prime}}\) są spełnialnymi zbiorami zdań nad pewną sygnaturą \(\Sigma,\) zaś \(\Delta\cup\Delta^{{\prime}}\) nie jest spełnialny, to istnieje zdanie \(\varphi\) takie, że \(\Delta\models\varphi\) oraz \(\Delta^{{\prime}}\models\lnot\varphi.\)

    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.

  3. Pokazać, że jeśli \(\Delta\) jest pewnym zbiorem zdań \(\varphi\) takich, że \(Spec(\lnot\varphi)\) jest skończone, oraz \(\Delta\models\psi,\) to także \(Spec(\lnot\psi)\) jest skończone.
  4. Pokazać, że klasa wszystkich relacji równoważności, które mają skończenie wiele klas abstrakcji, nie jest aksjomatyzowalna.
  5. Udowodnić, że klasa wszystkich struktur \(\mathbb{A}=\langle A,E^{\mathbb{A}}\rangle\) nad sygnaturą składającą się z jednego dwuargumentowego symbolu relacyjnego \(E\) i takich, że \(E^{\mathbb{A}}\) jest zbiorem skończonym, nie jest aksjomatyzowalna.
  6. Pokazać, że klasa wszystkich algebr \(\mathbb{A}=\langle A,f^{\mathbb{A}}\rangle,\) gdzie \(f\) jest symbolem jednoragumentowej funkcji, oraz takich, że \(|\vec{f}(A)|< |A|\) nie jest aksjomatyzowalna.
  7. Udowodnić, że klasa wszystkich struktur \(\mathbb{A}=\langle A,E^{\mathbb{A}}\rangle\) nad sygnaturą składającą się z jednego dwuargumentowego symbolu relacyjnego \(E\) i takich, że \(|\{(a,b)\in A\times A~/~(a,b)\in E^{\mathbb{A}}\}|< |\{(a,b)\in A\times A~/~(a,b)\notin E^{\mathbb{A}}\}|,\) nie jest aksjomatyzowalna.
  8. Udowodnić, że klasa wszystkich struktur \(\mathbb{A}=\langle A,r^{\mathbb{A}}\rangle,\) gdzie \(r\in\Sigma^{R}_{1}\) oraz takich, że \(|r^{\mathbb{A}}|=|A\setminus r^{\mathbb{A}}|\) nie jest aksjomatyzowalna.

Tw. Skolema-Löwenheima.

  1. Udowodnić, że klasa wszystkich struktur \(\mathbb{A}=\langle A,r^{\mathbb{A}}\rangle,\) gdzie \(r\in\Sigma^{R}_{1}\) oraz takich, że \(|r^{\mathbb{A}}|=2^{{|A\setminus r^{\mathbb{A}}|}}\) nie jest aksjomatyzowalna.
  2. Udowodnić, że klasa wszystkich struktur izomorficznych do struktury postaci \(\mathbb{A}=\langle\mathcal{P}(A),\cup^{\mathbb{A}},\cap^{\mathbb{A}},\subseteq^{\mathbb{A}}\rangle,\) gdzie \(\cup^{\mathbb{A}},\cap^{\mathbb{A}}\) oraz \(\subseteq^{\mathbb{A}}\) są odpowiednio prawdziwymi sumą, przecięciem i zawieraniem zbiorów, nie jest aksjomatyzowalna.
  3. Udowodnić następujące tw. Hessenberga: Dla każdej nieskończonej mocy \(\mathfrak{m}\) zachodzi \(\mathfrak{m}^{2}=\mathfrak{m}.\)

    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.

zadania_egz

  1. Niech \(\mathbb{A}=\langle\omega\setminus\{ 0\},\mathrm{nwd}^{\mathbb{A}}\rangle\) będzie algebrą, gdzie \(\mathrm{nwd}\in\Sigma^{F}_{2},\) przy czym dla wszystkich \(m,n\in\omega\)

    \(\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ą.

  2. Niech \(\mathbb{Y}=\langle\omega,S^{\mathbb{Y}},\beta^{\mathbb{Y}},\leq^{\mathbb{Y}}\rangle\) będzie strukturą nad sygnaturą \(\Sigma,\) która składa się z symboli \(S\in\Sigma^{F}_{1},\) \(\beta\in\Sigma^{F}_{3}\) oraz \(\leq\in\Sigma^{R}_{2},\) przy czym dla każdych \(n,t,p,i\in\omega\)

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

  3. Wykazać, że jeśli klasa \(\mathcal{A}\) struktur pewnej ustalonej sygnatury \(\Sigma\) nie jest aksjomatyzowalna, to klasa \(Mod(\Sigma)\setminus\mathcal{A},\) złożona z wszystkich tych struktur sygnatury \(\Sigma,\) które nie należą do \(\mathcal{A},\) nie jest definiowalna.

    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.

  4. Przypuśćmy, że \(\Delta\) jest zbiorem zdań nad sygnaturą \(\Sigma,\) który ma model nieskończony, oraz, że każde dwa przeliczalne modele \(\Delta\) są izomorficzne (o takich \(\Delta\) mówi się, że są \(\aleph _{0}\)-kategoryczne). Udowodnić, że dla każdego zdania \(\varphi\) nad \(\Sigma,\) albo \(\Delta\models\varphi\) albo \(\Delta\models\lnot\varphi\) (innymi słowy, \(\Delta\) jest zupełny).
  5. Równość \(s=t\) nazywamy normalną, gdy \(FV(s)=FV(t),\) tj., w \(s\) i \(t\) występują dokładnie te same zmienne.

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

  6. Niech \(\varphi\) będzie zdaniem

    \(\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?\)

  7. Udowodnić, że klasa wszystkich struktur \(\mathbb{A}=\langle A,E^{\mathbb{A}}\rangle\) nad sygnaturą składającą się z jednego dwuargumentowego symbolu relacyjnego \(E\) i takich, że \(E^{\mathbb{A}}\) jest relacją równoważności, która ma wyłącznie klasy abstrakcji parzystej mocy, nie jest definiowalna.
  8. Niech \(\mathbb{A}\) będzie algebrą wolną ze zbiorem wolnych generatorów \(G\), w pewnej klasie \(\mathcal{A}.\) Udowodnić, że dla każdej relacji równoważności \(r\subseteq G\times G\) istnieje kongruencja \(\bar{r}\subseteq A\times A\) taka, że \(\bar{r}\cap(G\times G)=r.\) (Można to wyrazić stwierdzeniem, że \(r\) roszerza się do kongruencji w \(\mathbb{A}.\))

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

  9. Opisać wszystkie kongruencje algebry \(\mathbb{A}=\langle\{ 0,1,2,3\},\min^{\mathbb{A}},\max^{\mathbb{A}}\rangle,\) gdzie \(\min,\max\in\Sigma^{F}_{2}\), a \(\min^{\mathbb{A}},\max^{\mathbb{A}}\) są odpowiednio operacjami maksimum i minimum.
  10. Niech \(\mathbb{P}=\langle\mathcal{P}(\omega),\cap^{\mathbb{P}},\cup^{\mathbb{P}}\rangle\) będzie kratą podzbiorów \(\omega\) ze zwykłymi działaniami teoriomnogościowymi. Udowodnić, że \(\mathbb{P}\times\mathbb{P}\cong\mathbb{P}.\)