Zad. 1
Niech A=⟨N,pA,qA⟩, gdzie:
⟨a,b⟩∈pA wtw, gdy a+b≥6;
⟨a,b⟩∈qA wtw, gdy b=a+2.
Zbadać czy formuły
- ∀xp(x,y)→∃xq(x,y);
- ∀xp(x,y)→∀xq(x,y);
- ∀xp(x,y)→∃xq(x,z);
są spełnione przy wartościowaniu v(y)=7, v(z)=1 w strukturze A.
Zad. 2
Niech A=⟨Z,fA,rA⟩ i B=⟨Z,fB,rB⟩, gdzie fA(m,n)=min, dla m,n\in{\mathbb Z}, a r^{\mathfrak A} jest relacją \geq;
f^{\mathfrak B}(m,n) = m^2+n^2, dla m,n\in{\mathbb Z}, a r^{\mathfrak B} jest relacją \leq.
Zbadać czy formuły
- \forall y(\forall x(r(z,f(x,y))\to r(z,y)));
- \forall y(\forall x(r(z,f(x,y)))\to r(z,y)),
są spełnione przy wartościowaniu v(z) =5, v(y)=7 w strukturach {\mathfrak A} i {\mathfrak B}.
Zad. 3
Czy formuła \forall x(\lnot r(x,y)\to\exists z(r(f(x,z),g(y)))) jest spełniona przy wartościowaniu v(x) =3, w(x) = 6 i u(x) = 14
- w strukturze {\mathfrak A} = \langle {\mathbb N}, r^{\mathfrak A}\rangle , gdzie r^{\mathfrak A} jest relacją podzielności?
- w strukturze {\mathfrak B} = \langle {\mathbb N}, r^{\mathfrak B}\rangle , gdzie r^{\mathfrak B} jest relacją przystawania modulo 7?
Zad. 4
W jakich strukturach prawdziwa jest formuła \exists y (y\neq x)?
A formuła \exists y (y\neq y) otrzymana przez ,,naiwne'' podstawienie y na x?
Zad. 5
Podaj przykład modelu i wartościowania, przy którym formuła
p(x,f(x)) \to \forall x\exists y\, p(f(y),x)
jest:
a) spełniona;
b) nie spełniona.
Zad. 6
Zbadać, czy następujące formuły są tautologiami i czy są spełnialne:
-
\exists x\forall y(p(x) \vee q(y)) \to \forall y(p(f(y))\vee q(y));
- \forall y(p(f(y))\vee q(y)) \to \exists x\forall y(p(x) \vee 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)).
Zad. 7
Niech f będzie jednoargumentowym symbolem funkcyjnym, który nie występuje w formule \varphi.
Pokazać, że formuła \forall x\exists y \varphi jest spełnialna wtedy i tylko wtedy gdy formuła \forall x \varphi(f(x)/y) jest spełnialna.
Zad. 8
Udowodnić, że zdanie \forall x\exists y\,p(x,y)\wedge \forall x\neg p(x,x)
\wedge \forall x\forall y\forall z(p(x,y)\wedge p(y,z)\to p(x,z)) ma tylko modele nieskończone.
Zad. 9
Dla każdego n napisać takie zdanie \varphi_n, że {\mathfrak A}\models\varphi_n zachodzi \wtw, gdy {\mathfrak A} ma dokładnie n elementów.
Zad. 10
Udowodnić, że dla każdej struktury skończonej {\mathfrak A} nad skończoną sygnaturą istnieje taki zbiór \Delta zdań pierwszego rzędu, że {\mathfrak A}\models\Delta i dla każdej struktury {\mathfrak B}\models\Delta zachodzi {\mathfrak B}\cong{\mathfrak A}.
Zad. 11
Czy jeśli {\mathfrak A} \models \exists x\,\varphi, to także {\mathfrak A} \models \varphi[t/x], dla pewnego termu t?
Zad. 12
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?
Zad. 13
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.
Zad. 14
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.
Zad. 15
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.
Zad. 16
Pokazać, że zdanie (\forall x\exists y\ Exy)\to(\exists x\forall y\ Exy) nie jest tautologią.
Zad. 17
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?
Zad. 18
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?
Zad. 19
Pokazać, że następujące formuły są tautologiami:
- (\exists y p(y) \to \forall z q(z)) \to
\forall y\forall z(p(y)\to q(z));
- (\forall x\exists y r(x,y) \to \exists x\forall y r(y,x))\to
\exists x\forall y(r(x,y) \to r(y,x));
- \forall x\exists y((p(x)\to q(y))\to r(y))
\to ((\forall x p(x)\to \forall y q(y))\to \exists y r(y));
- \forall x(p(x)\to \exists y q(y))\to
\exists y(\exists x p(x)\to q(y)).
Zad. 20
Czy
\{\forall x\underbrace{f\ldots f}_n(x)= x~|~n=2,3,5,7\}\models\forall x
\underbrace{f\ldots f}_{11}(x)= x
?