Logika dla informatyków/Ćwiczenia 2

Ćwiczenie 1

Niech $\mathfrak{=}<\mathbb{\mathbb{N}},p^{\mathfrak{𝔄}},q^{\mathfrak{𝔄}}>$, gdzie:

$<a,b>\in p^{\mathfrak{𝔄}}$ wtedy i tylko wtedy, gdy $a+b\ge 6$; Parser nie mógł rozpoznać (błąd składni): {\displaystyle \<a,b\>\in q^\mathfrak A} wtedy i tylko wtedy, gdy $b=a+2$

.

Zbadać czy formuły

1. 1. $\mathrm{\forall }xp(x,y)\to \mathrm{\exists }xq(x,y)$;
   2. $\mathrm{\forall }xp(x,y)\to \mathrm{\forall }xq(x,y)$;
   3. $\mathrm{\forall }xp(x,y)\to \mathrm{\exists }xq(x,z)$;

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

Ćwiczenie 2
Niech Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathfrak A = \<\mathbb Z, f^\mathfrak A, r^\mathfrak A >} i Parser nie mógł rozpoznać (błąd składni): {\displaystyle \mathfrak B = \< \mathbb Z, f^\mathfrak b, r^\mathfrak b >} , gdzie

$f^{\mathfrak{𝔄}}(m,n)=min(m,n)$, dla $m,n\in \mathbb{\mathbb{Z}}Z$, a $r^{\mathfrak{𝔄}}$ jest

relacją $\ge$;
$f^{\mathfrak{𝔟}}(m,n)=m^2+n^2$, dla $m,n\in \mathbb{\mathbb{Z}}$, a $r^{\mathfrak{𝔟}}$ jest relacją $\le$.

Zbadać czy formuły

1. $\mathrm{\forall }y(\mathrm{\forall }x(r(z,f(x,y))\to r(z,y)))$;
2. $\mathrm{\forall }y(\mathrm{\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{𝔄}$ i $\mathfrak{𝔅}$.

Ćwiczenia 3

\item Czy formuła $\mathrm{\forall }x(\mathrm{\neg }r(x,y)\to \mathrm{\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 Parser nie mógł rozpoznać (nieznana funkcja „\strA”): {\displaystyle \strA = \<\NN, r^\strA\>} , gdzie Parser nie mógł rozpoznać (nieznana funkcja „\strA”): {\displaystyle r^\strA} jest

relacją podzielności?

1. [(b)] w strukturze Parser nie mógł rozpoznać (nieznana funkcja „\B”): {\displaystyle \B = \<\NN, r^\strB\>} , gdzie Parser nie mógł rozpoznać (nieznana funkcja „\strB”): {\displaystyle r^\strB} jest

relacją przystawania modulo 7?

\item W jakich strukturach prawdziwa jest formuła $\mathrm{\exists }y(y\ne x)$? A formuła $\mathrm{\exists }y(y\ne y)$ otrzymana przez ,,naiwne podstawienie $y$ na $x$?

\item Podaj przykład modelu i wartościowania, przy którym formuła

\hfil $p(x,f(x))\to \mathrm{\forall }x\mathrm{\exists }yp(f(y),x)$

jest:\quad a) spełniona;\quad b) nie spełniona.

\item Zbadać, czy następujące formuły są tautologiami i czy są spełnialne: %%Rozwiazanie: %84%97bc

$\mathrm{\exists }x\mathrm{\forall }y(p(x)\vee q(y))\to \mathrm{\forall }y(p(f(y))\vee q(y))$;

1. $\mathrm{\forall }y(p(f(y))\vee q(y))\to \mathrm{\exists }x\mathrm{\forall }y(p(x)\vee q(y))$;
2. %97b

$\mathrm{\exists }x(\mathrm{\forall }yq(y)\to p(x))\to \mathrm{\exists }x\mathrm{\forall }y(q(y)\to p(x))$;

1. %97c

$\mathrm{\exists }x(\mathrm{\forall }yq(y)\to p(x))\to \mathrm{\exists }x(q(x)\to p(x))$.

\item Niech $f$ będzie jednoargumentowym symbolem funkcyjnym, który nie występuje w formule Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi} . Pokazać, że formuła Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \forall x\exists y \var\varphi} jest spełnialna wtedy i tylko wtedy gdy formuła Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \forall x \var\varphi[f(x)/y]} jest spełnialna.

\item Udowodnić, że zdanie

\hfil </math>\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))</math>.

ma tylko modele nieskończone.

\item Dla każdego $n$ napisać takie zdanie Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi_n} , że Parser nie mógł rozpoznać (nieznana funkcja „\strA”): {\displaystyle \strA\models\var\varphi_n} zachodzi \wtw, gdy Parser nie mógł rozpoznać (nieznana funkcja „\strA”): {\displaystyle \strA} ma dokładnie $n$elementów.

\item Czy jeśli Parser nie mógł rozpoznać (nieznana funkcja „\strA”): {\displaystyle \strA \models \exists x\,\var\varphi} , to także Parser nie mógł rozpoznać (nieznana funkcja „\strA”): {\displaystyle \strA \models \var\varphi[t/x]} , dla pewnego termu $t$?