- Proszę zdefiniować relację izomorfizmu.
- Proszę zdefiniować relację \(m\)-izomorfizmu i omówić jej związek z grą Ehrenfeuchta-Fraïsségo.
- Proszę opisać grę Ehrenfeuchta-Fraïsségo i omówić jej związek z \(m\)-izomorfizmem.
- Proszę zdefiniować pojęcie podstruktury indukowanej.
- Proszę zdefiniować pojęcie podalgebry generowanej.
- Proszę zdefiniować zbiór formuł logiki pierwszego rzędu i pojęcie zmiennych wolnych danej formuły.
- Proszę zdefiniować zbiór formuł logiki pierwszego rzędu i pojęcie rangi kwantyfikatorowej danej formuły.
- Proszę zdefiniować relację \(\mathbb{A}\models\varphi[s].\)
- Proszę zdefiniować sekwent.
- Proszę zdefiniować pojęcie sekwentu wyprowadzalnego (nie trzeba znać wszystkich reguł systemu Gentzena, tylko mieć orientację o ich postaci).
- Proszę zdefiniować relację \(\Gamma\models\varphi,\) gdzie \(\Gamma\) to zbiór zdań.
- Proszę zdefiniować pojęcie tautologii.
- Proszę zdefiniować pojęcie twierdzenia.
- Proszę sformułować twierdzenie o pełności.
- Proszę sformułować twierdzenie o zwartości.
- Proszę sformułować twierdzenie Skolema-Löwenheima.
- 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.\)
- \((\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})).\)
- \((\forall x\ f(f(x))=x)\to(\forall x\forall y\ x\neq y\to f(x)\neq f(y)).\)
- \((\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).\)
- \(\forall x\forall y\exists z\ f(x,z)=y.\)
- \(\forall x\forall y\exists z\ f(x,y)=z.\)
- \((\forall x\forall y\exists z\ f(x,z)=y)\to(\exists x\ f(x,x)=x)\).
- \(\exists x\exists y\ (f(x)=x\to f(y)=y).\)
- \(\exists x\forall y\ (f(x)=x\to f(y)=y).\)
- \((\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)))).\)
- \((\exists x\ f(x)\neq x)\to(\exists x\exists y\ x\neq y)\).
- \((\forall x(\forall y\ f(x)\neq y)\to(f(x)\neq x)).\)
- \((\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))).\)
- \(\forall x\forall y\ f(x)=y.\)
- \((\forall x\exists y\ \lnot(r(x,y)\leftrightarrow r(y,x)))\land(\forall y\ \lnot r(y,y)).\)
- \((\forall x(\exists y\ \lnot(r(x,y)\leftrightarrow r(y,x))\land(\forall y\ \lnot r(y,y)))).\)
- \((\exists x(p(x)\to(\forall y\ q(y))))\to(\exists x\forall y\ p(x)\to q(y))\).
- \((\exists x(\forall y\ q(y))\to p(x))\to(\exists x\forall y\ q(y)\to p(x))\).
- \((\exists x(\forall y\ q(y))\to p(x))\to(\exists x\ q(x)\to p(x))\).
- \((\forall x\forall y((f(x)=f(y))\to(x=y)))\to(\forall x\exists y(f(y)=x))\).
- \(\exists x\exists y\exists u\exists v((\lnot u=x)\lor(\lnot v=y))\land(f(x,y)=f(u,v))\).
- Podać przykład zdania \(\varphi\) (sygnatura też jest do wyboru) takiego, że \(Spec(\varphi)=Spec(\lnot\varphi).\)
- Podać przykład zdania \(\varphi\) (sygnatura też jest do wyboru) takiego, że \(Spec(\varphi)=\{ n^{2}~/~n\in\mathbb{N}\}.\)\mathbb
- Podać przykład zdania \(\varphi\) (sygnatura też jest do wyboru) takiego, że \(Spec(\varphi)=\{ 2*n~/~n\in\mathbb{N}\}.\)\mathbb
- Znale”zć formułę \(\varphi(x,y)\) stwierdzającą w standardowym modelu arytmetyki, że \(x\) jest względnie pierwsze z \(y.\)
- Znale”zć formułę \(\varphi(x,y,z)\) stwierdzającą w standardowym modelu arytmetyki, że \(z\) jest największym wspólnym dzielnikiem \(x\) i \(y.\)
- 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.\)