Informatyka MIMUW

Exercise 1

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

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

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

Check if formulas

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

are satisfied under the valuation \(v(y) = 7\), \(v(z) = 1\) in structure \({\mathfrak A}\).

Exercise 2

Let \({\mathfrak A} = \langle {\mathbb Z}, f^{\mathfrak A}, r^{\mathfrak A}\rangle \) and \({\mathfrak B} = \langle {\mathbb Z}, f^{\mathfrak B}, r^{\mathfrak B}\rangle \), where \(f^{\mathfrak A}(m,n) = \min(m,n)\) for \(m,n\in{\mathbb Z}\), and \(r^{\mathfrak A}\) is the relation \(\geq\);

\(f^{\mathfrak B}(m,n) = m^2+n^2\) for \(m,n\in{\mathbb Z}\), and \(r^{\mathfrak B}\) is the relation \(\leq\).

Check if formulas

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

are satisfied under the valuation \(v(z) =5\), \(v(y)=7\) in structures \({\mathfrak A}\) and \({\mathfrak B}\).

Exercise 3

Is formula \(\forall x(\lnot r(x,y)\to\exists z(r(f(x,z),g(y))))\) satisfied under the valuation \(v(x) =3\), \(w(x) = 6\) and \(u(x) = 14\)

1. in the structure \({\mathfrak A} = \langle {\mathbb N}, r^{\mathfrak A}\rangle \), where \(r^{\mathfrak A}\) is the divisibility relation?
2. in the structure \({\mathfrak B} = \langle {\mathbb N}, r^{\mathfrak B}\rangle \), where \(r^{\mathfrak B}\) is the congruency modulo 7?

Exercise 4

In which structures is the formula \(\exists y (y\neq x)\) satisfied?
And the formula \(\exists y (y\neq y)\) obtained by naive substitution of \(y\) to \(x\)?

Exercise 5

Give examples of models and valuations such that the formula
\(p(x,f(x)) \to \forall x\exists y\, p(f(y),x)\)

is:
a) satisfied;
b) not satisfied.

Exercise 6

Check if the following formulas are tautologies an if they are satisfiable:

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

Exercise 7

Let \(f\) be a function symbol of arity two, that is not used in the formula \(\varphi\).
Show that the formula \(\forall x\exists y \varphi\) is satisfiable if and only if the formula \(\forall x \varphi(f(x)/y)\) is satisfiable.

Exercise 8

Show that the formula \(\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))\) has only infinite models.

Exercise 9

For each \(n\) give a closed formula \(\varphi_n\) such that \({\mathfrak A}\models\varphi_n\) iff \({\mathfrak A}\) has exactly \(n\) elements.

Exercise 10

Show that for each finite structure \({\mathfrak A}\) over a finite signature there exists a set of first order formulas \(\Delta\) such that \({\mathfrak A}\models\Delta\) and for all structures satisfying \({\mathfrak B}\models\Delta\) it holds that \({\mathfrak B}\cong{\mathfrak A}.\)

Exercise 11

Is it true that \({\mathfrak A} \models \exists x\,\varphi\) implies existence of a term \(t\) such that \({\mathfrak A} \models \varphi[t/x]\)?

Exercise 12

Let \(\varphi = \forall x\forall y\,(y=f(g(x))\to(\exists u\,(u=f(x)\land y=g(u))))\) and \(\psi = \forall x\,[f(g(f(x)))=g(f(f(x)))]\). Does it hold that
\(\{\psi\}\models\varphi\)?

Exercise 13

Show that the set of axioms of equivalence relation

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

is independent.

Exercise14

Show that the set of axioms of linear orders

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

is independent.

Exercise 15

Show that the set of axioms of of group theory (in multiplicative notation, over signature
\(\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\}\)

is independent.

Exercise 16

Show that the formula \((\forall x\exists y\ Exy)\to(\exists x\forall y\ Exy)\) is not a tautology.

Exercise 17

Show that the formula

\((\forall x\forall y((f(x)=f(y))\to(x=y)))\to(\forall x\exists y(f(y)=x))\)

is not a tautology. Does its negation have a finite model?

Exercise18

Show that the formula \(\exists x\exists y\exists u\exists v((\lnot u=x)\lor(\lnot v=y))\land(f(x,y)=f(u,v))\) is not a tautology. How many non-isomorphic finite models does this formula have?

Exercise 19

Show that the following formulas are tautologies:

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

Exercise 20

Does it hold that
\(
\{\forall x\underbrace{f\ldots f}_n(x)= x~|~n=2,3,5,7\}\models\forall x
\underbrace{f\ldots f}_{11}(x)= x
\)?