====== Teoretyczne podstawy jeżyków programowania - Lista 2 ======
===== Zadanie 1 =====
Na $\color{green}{zielono}$ zmienne wolne, na $\color{red}{czerwono}$ zmienne związane. Zakres występowania czerwonych to do końca nawiasu, jeżeli jesteśmy już w jakimś nawiasie lub do końca wyrażenia, jeżeli nie jesteśmy.\\
a) $(\forall \color{red}{x}.\exists \color{red}{y}. P(\color{red}{x},\color{red}{y})) \rightarrow ( ( \forall \color{red}{y} . Q ( \color{green}{x}, \color{red}{y} ) ) \vee \exists \color{red}{x}. R(\color{red}{x},\color{green}{y}))$\\
b) $(\forall \color{red}{x}. P(\color{green}{x},\color{green}{y},\color{red}{z})) \rightarrow \exists \color{red}{z} . \exists \color{red}{y}. Q(\color{green}{x},\color{red}{y},\color{red}{z}) \wedge \forall \color{red}{z}. R(\color{green}{x},\color{green}{y},\color{red}{z})$\\
===== Zadanie 2 =====
$\forall z . (\forall x . P(x,y,z) ) \rightarrow \exists y . Q(x,y)$\\ 
a) $\forall z . (\forall x . P(x,y,z) ) \rightarrow \exists y . Q(x,y)$\\ 
b) $\forall z . (\forall x . P(x,y,z) ) \rightarrow \exists y . Q(x,y)$\\ 
c) $\forall z . (\forall x . P(x,y,z) ) \rightarrow \exists w . Q(y+x,w)$\\ 
d) $\forall z . (\forall x . P(x,b,z) ) \rightarrow \exists y . Q(z+x,y)$\\ 
===== Zadanie 3 =====
a) $|x| \geq 1$ czyli $W = (-\infty, -1]\cup [1, \infty )$\\
b) $ W = [0,1]$\\
c) $ W = \emptyset $\\
===== Zadanie 4 =====
a) \\ def $\exists w . \exists v . x = w*w + v*v $\\
b) \\ def $\forall n .\exists p . p > n \wedge 2*n > p \wedge P(p)$ na wykladzie zdefiniowaliśmy $P(x)$ oraz $>$.\\
c) \\ def $\forall n . \exists o . o > n$\\

===== Zadanie 5 =====
a) nie\\
Istnieją takie $x,y$, konkretnie $x=b,y=c$, że $\exists z .P(x,y) \rightarrow P(y,z)$ jest nie prawdziwe, bo $P(x,y)$ jest prawdziwe, a nie istnieje takie $z$, żeby spełnić tą formułę.\\
b) tak\\
Bo dla każdego możliwego drugiego argumentu $P$, dla których $P$ jest prawdziwe, istnieje taki argument, że jak drugi argument przestawimy na pierwsze miejsce, to formuła będzie spełniona.

===== Zadanie 6 =====
a) tautologia\\
b) tautologia\\
c)\\ $P(x) \leftrightarrow x \geq 0$\\
$Q(x) \leftrightarrow x < 0$\\
d)\\
$P(x,y) \leftrightarrow y = 2$\\
===== Zadanie 7 =====
Nie chce mi sie w TeXu na wiki, bez styli, jeszcze nie zwariowałem.

===== Zadanie 8 =====
$hexd( 0 ) = 0$\\
$hexd( 1 ) = 1$\\
$hexd( 2 ) = 2$\\
$hexd( 3 ) = 3$\\
$hexd( 4 ) = 4$\\
$hexd( 5 ) = 5$\\
$hexd( 6 ) = 6$\\
$hexd( 7 ) = 7$\\
$hexd( 8 ) = 8$\\
$hexd( 9 ) = 9$\\
$hexd( A ) = 10$\\
$hexd( B ) = 11$\\
$hexd( C ) = 12$\\
$hexd( D ) = 13$\\
$hexd( E ) = 14$\\
$hexd( F ) = 15$\\

$hex( 0xhexdig ) = hexd( hexdig )$\\
$hex( hexnum\; hexdig ) = 16*hex( hexnum) + hexd( hexdig )$\\

===== Zadanie 9 =====
$S \rightarrow aAa$\\
$A \rightarrow B | aAa $\\
$B \rightarrow \epsilon | Bb$\\
===== Zadanie 10 =====
$F_1( S ) = 2 + F_1( A )$\\
$F_1( A ) = F_1( B )$ jeśli $A \rightarrow B$\\
$F_1( A ) = 2 + F_1( A_2 ))$ jeśli $A \rightarrow aA_2a$\\
$F_1( B ) = 0$ jeśli $B \rightarrow \epsilon$\\
$F_1( B ) = 1 + F_1( B_2) $ jeśli $B \rightarrow B_2b$\\

$F_2( S ) = aaF_2( A )$\\
$F_2( A ) = F_2( B )$ jeśli $A \rightarrow B$\\
$F_2( A ) = aaF_2( A_2 )$ jeśli $A \rightarrow aA_2a$\\
$F_2( B ) = \epsilon$ jeśli $B \rightarrow \epsilon$\\
$F_2( B ) = aaF_2( B_2 ) $ jeśli $B \rightarrow B_2b$\\