Informatyka MIMUW

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