Logika dla informatyków/Ćwiczenia 2

Ćwiczenie 1

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

$<a,b>\in p^{\mathfrak {A}}$ wtedy i tylko wtedy, gdy $a+b\geq 6$; $<a,b>\in q^{\mathfrak {A}}$ wtedy i tylko wtedy, gdy $b=a+2$.

Zbadać, czy formuły

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

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

Ć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 {A}}(m,n)=min(m,n)$, dla $m,n\in \mathbb {Z} 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}}$.

Ćwiczenie 3

Czy formuła $\forall x(\neg 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}}=<\mathbb {N} ,r^{\mathfrak {A}}>$, gdzie $r^{\mathfrak {A}}$ jest relacją podzielności?
2. w strukturze ${\mathfrak {B}}=<\mathbb {N} ,r^{\mathfrak {B}}>$, gdzie $r^{\mathfrak {B}}$ jest relacją przystawania modulo 7?

Ćwiczenie 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 Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle x} ?

Ćwiczenie 5

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

Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle p(x,f(x)) \to \forall x\exists y p(f(y),x)}

jest: a) spełniona b) nie spełniona.

Ćwiczenie 6

Zbadać, czy następujące formuły są tautologiami i czy są spełnialne:

1. Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \exists x\forall y(p(x) \vee q(y)) \to \forall y(p(f(y))\vee q(y))} ;
2. Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \forall y(p(f(y))\vee q(y)) \to \exists x\forall y(p(x) \vee q(y))} ;
3. Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \exists x(\forall y q(y)\to p(x))\to \exists x\forall y(q(y)\to p(x))} ;
4. Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \exists x(\forall y q(y)\to p(x)) \to\exists x(q(x)\to p(x))} .

Ćwiczenie 7

Niech Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle f} będzie jednoargumentowym symbolem funkcyjnym, który nie występuje w formule Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \var\varphi} . Pokazać, że formuła Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \forall x\exists y \var\varphi} jest spełnialna wtedy i tylko wtedy gdy formuła Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \forall x \var\varphi(f(x)/y)} jest spełnialna.

Ćwiczenie 8

Udowodnić, że zdanie

Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \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.

Ćwiczenie 9

Dla każdego Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle n} napisać takie zdanie Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \var\varphi_n} , że Parser nie mógł rozpoznać (nieznana funkcja „\var”): {\displaystyle \mathfrak A\models\var\varphi_n} zachodzi \wtw, gdy ${\mathfrak {A}}$ ma dokładnie $n$elementów.

Ćwiczenie 10

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