Informatyka MIMUW

Zad. 1

Niech \({\mathfrak A} =\langle{\mathbb N}, p^{\mathfrak A}, q^{\mathfrak A}\rangle\), gdzie:

\(\langle a,b\rangle \in p^{\mathfrak A}\) wtw, gdy \(a+b\geq 6\);

\(\langle a,b\rangle \in q^{\mathfrak A}\) wtw, gdy \(b=a+2\).

Zbadać czy formuły

1. \(\forall x p(x,y) \to \exists x q(x,y)\);
2. \(\forall x p(x,y) \to \forall x q(x,y)\);
3. \(\forall x p(x,y) \to \exists x q(x,z)\);

są spełnione przy wartościowaniu \(v(y) = 7\), \(v(z) = 1\) w strukturze \({\mathfrak A}\).

Zad. 2

Niech \({\mathfrak A} = \langle {\mathbb Z}, f^{\mathfrak A}, r^{\mathfrak A}\rangle \) i \({\mathfrak B} = \langle {\mathbb Z}, f^{\mathfrak B}, r^{\mathfrak B}\rangle \), gdzie \(f^{\mathfrak A}(m,n) = \min(m,n)\), 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

1. \(\forall y(\forall x(r(z,f(x,y))\to r(z,y)))\);
2. \(\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\)

1. w strukturze \({\mathfrak A} = \langle {\mathbb N}, r^{\mathfrak A}\rangle \), gdzie \(r^{\mathfrak A}\) jest relacją podzielności?
2. 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:

1. \(\exists x\forall y(p(x) \vee q(y)) \to \forall y(p(f(y))\vee q(y))\);
2. \(\forall y(p(f(y))\vee q(y)) \to \exists x\forall y(p(x) \vee q(y))\);
3. \(\exists x(\forall y q(y)\to p(x))\to \exists x\forall y(q(y)\to p(x))\);
4. \(\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
\)?