\documentclass[a4paper]{article}
\usepackage{progm}
\analpacks
\analoldal{3. zárthelyi dolgozat}
\pagestyle{empty}
\begin{document}
\noindent

``Simplicity is prerequisite for reliability.''\\
--- Edsger Dijkstra

\begin{center}Bevezetés a programozáshoz 1., 3. zárthelyi dolgozat\\2006. december 12.\end{center}

Az alábbi feladatok megoldása során állításaidat indokold!  Az
indoklások triviális tényekre, a tanult definíciókra és a kimondott
tétetelekre hivatkozhatnak.  Az elõadáson vagy gyakorlaton szerepelt
bármely állítás felhasználható, azonban az el nem hangzottakat
szintén indokolni kell!

\emph{1. Feladat}\\Írjuk fel az $A\times B, A\times C, (C\times B)\times A$ és $B\times C\times A$ halmazok elemeit, ha $A=\{\alpha, \varphi\}, B=\{1,2,3\}, C=\{x,y\}$. (5 pont)

\emph{Megoldás:}\\$A\times B=\{(\alpha, 1), (\alpha, 2), (\alpha, 3), (\varphi, 1), (\varphi, 2), (\varphi, 3)\}$,\\
$A\times C=\{(\alpha, x), (\alpha, y), (\varphi, x), (\varphi, y)\}$,\\
$(C\times B)\times A = \{((x, 1), \alpha), ((x, 2), \alpha), ((x, 3), \alpha), ((y, 1), \alpha), ((y, 2), \alpha), ((y, 3), \alpha), ((x, 1), \varphi), ((x, 2), \varphi), ((x, 3), \varphi), ((y, 1), \varphi),$\\$((y, 2), \varphi), ((y, 3), \varphi)\}$,\\
$B\times C\times A = \{(1, x, \alpha), (2, x, \alpha), (3, x, \alpha), (1, y, \alpha), (2, y, \alpha), (3, y, \alpha), (1, x, \varphi), (2, x, \varphi), (3, x, \varphi), (1, y, \varphi), (2, y, \varphi), (3, y, \varphi)\}$.

\emph{2. Feladat}\\$R\subseteq A\times A$.  Igaz-e, hogy $(R^{(-1)})^2 = (R^2)^{(-1)}$? (7 pont)

\emph{Megoldás:}\\Igaz, ui.: $(a,c)\in (R^{(-1)})^2 \ekv \exists b\in A: (a,b)\in R^{(-1)} \ni (b,c) \ekv (b,a)\in R \ni (c,b) \ekv (c,a)\in R^2 \ekv (a,c)\in (R^2)^{(-1)}$.

\emph{3. Feladat}\\$R\subseteq \N_0\times\N_0$.
\begin{displaymath}
R(a)=\left\{
\begin{array}{ll}
\{a-3\}, & \text{ha } a>2 \\
\{3*k|k\in\N\}, & \text{ha } a=1 \\
\end{array}
\right.
\end{displaymath}
Mi az $R$ reláció lezártja és korlátos lezártja? (10 pont)

\emph{Megoldás:}\\$\{0, 2\}\subset\D_{\overset{-}R}$, hiszen ebben a
két pontban nincs értelmezve $R$. Látható, hogy minden olyan pozitív
számból, ami nem ad 1 maradékot hárommal osztva a reláció (a számnál
nem több lépés alatt) ebbe a részhalmazba jut, tehát ezek a számok is
elemei $\D_{\overset{-}R}$-nek.  Gondolkodni az egy maradékot adó elemmekkel
kapcsolatban kell.  Ezek az $1$-re vezetnek, amihez a reláció
tetszõleges nagy, de hárommal osztva 0 maradékot adó számokat rendel.
Tehát a korlátos lezárt definiciója által követelt felsõ korlát
ilyenkor nem adható, de biztos, hogy véges bármilyen sorozat, ami az
1-et tartalmazza és ``végigköveti'' a relációt.  Ezért:\\
$\N_0 = \D_{\overset{-}R} \subset \D_{\overset{=}R} = \N_{0} \setminus \{x\in \N|x\text{ }3\text{-mal osztva } 1\text{ maradékot ad}\}$.\\
$\forall a\in\D_{\overset{=}R}: {\overset{=}R}(a)={\overset{-}R}(a)$.\\
$\forall a\in\N_0:\overset{-}{R}(a)=\left\{
\begin{array}{ll}
0, & \text{ha } a\text{ }3\text{-mal osztva }0\text{ maradékot ad} \\
2, & \text{ha } a\text{ }3\text{-mal osztva }2\text{ maradékot ad} \\
0, & \text{ha } a\text{ }3\text{-mal osztva }1\text{ maradékot ad} \\
\end{array}
\right.
$.


\emph{4. Feladat}\\$A=\alatt{\N}{x} \times \alatt{\N}{k} \times \alatt{\L}{l}$\\
$S=((DO(x>k, x:=x-k);IF(x=k:l:=\text{igaz}, x\ne k:l:=\text{hamis}))$

\begin{itemize}
\item Rajzold fel a program stuktogramját! (5 pont)

\emph{Megoldás:}
\begin{stuki}[6cm]
  \begin{WHILE}{1}{\stm{x>k}}
    \stm{x:=x-k}
  \end{WHILE}
  \begin{IF}{1}{\stm{x=k}}
    \stm{l:=\igaz}
    \ELSE
    \stm{l:=\hamis}
  \end{IF}
\end{stuki}

\item Milyen pontokat rendel a program a $(5,3,\text{igaz})$ és $(6,2,\text{hamis})$ pontokhoz? (10 pont)

\emph{Megoldás:}\\
$S(5,3,\igaz)=\{<(5,3,\igaz), (2,3,\igaz), (2,3,\hamis)>\}$,\\
$S(6,2,\hamis)=\{<(6,2,\hamis), (4,2,\hamis), (2,2,\hamis), (2,2,\igaz)>\}$.

\end{itemize}

\emph{5. Feladat}\\Igaz-e, ha $S\subseteq B\times B^{**}$, $A$ altere $B$-nek, akkor
\begin{itemize}
\item $\D_{\pr_A(p(S))} = \pr_A(\D_{p(S)})?$ (8 pont)

\emph{Megoldás:}\\
Ez tetszõleges $R\in B\times B$ relációra igaz, nem csak $p(S)$-re, ui.:\\
$a\in\D_{\pr_A(R)} \ekv \exists a'\in A: (a,a')\in \pr_A(R) \ekv \exists a'\in A: \exists b,b'\in B: (b,b')\in R \es \pr(b)=a \es \pr(b')=a' \ekv$\\$\ekv \exists b\in B: \pr(b)=a \es  b\in\D_R\ekv a\in \D_\pr(R)$.
\item $S$ $A$-ra történõ projekciójának programként való kiterjesztése $B$-re azonos $S$-sel? (8 pont)

\emph{Megoldás:}\\
Nem igaz, ellenpélda:\\
$A=\{1,2\}$\\
$B=\{1,2\}\times\{1,2\}$\\
$S$ legyen olyan program, amire: $S\ni((1,1),<(1,1),(2,2)>)$, ekkor
$pr_A(S)\ni(1,<1,2>)$ és emiatt biztosan
$pr_A(S)'\ni((1,1),<(1,1),(2,1))$, ami nem szükséges, hogy benne
legyen $S$-ben, ahhoz, hogy $S$ program legyen.

\end{itemize}

\emph{6. Feladat}\\$A=\N\times\N\times\N. S\subseteq A\times A^{**}.$
$S$ az $(1,1,2)$ pontból kiindulva elõállítja a 10. Fibonacci számot
az $u(n)=u(n-1)+u(n-2)$ rekurzív összefüggés alapján.  A koordináták
rendre $u(n-2)$-nek, $u(n-1)$-nek és $u(n)$-nek felelnek meg.  Írd fel
azt a sorozatot, amelyet $S$ az $(1,1,2)$ ponthoz rendel!  Mit rendel
$p(S)$ az $(1,1,2)$ ponthoz? (7 pont)

$S(1,1,2)=\{<(1,1,2),(1,2,3),(2,3,5),(3,5,8),(5,8,13),(8,13,21),(13,21,34),(21,34,55)>\}$, tehát \\
$p(S)(1,1,2)=\{(21,34,55)\}$.
\end{document}
