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

\begin{center}Bevezetés a programozáshoz 1., 1. zárthelyi dolgozat (megoldás)\\2005. október 26.\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}\\Bizonyítsuk be, hogy $H\subseteq A\times B$ esetén
\begin{itemize}
  \item $(\forall(a,b),(c,d)\in H: (a,d)\in H) \ekv (\exists K\subseteq A: \exists L\subseteq B: H = K\times L)$, (12 pont)
  \item ha $H$ nem üres, akkor $K$ és $L$ egyértelmű. (5 pont)
\end{itemize}

\emph{Megoldás:} Ha $H$ üres, akkor $K=\emptyset$ választással az $L$ tetszőleges részhalmaza lehet $B$-nek.

Ha $H$ nem üres, akkor:

\kov:\\
$K::=\D_H, L::=\mathcal{R}_H$, tehát $H{\overset{\mbox{\scriptsize\textrm{?}}}=}\D_H\times\mathcal{R}_H$.\\
$H\subseteq \D_H\times\mathcal{R}_H$: $(a,b)\in H \kov (a,b)\in \D_H\times\mathcal{R}_H$, hiszen $a\in\D_H$ és $b\in\mathcal{R}_H$.\\
$H \supseteq \D_H\times\mathcal{R}_H$: $(a,d)\in \D_H\times\mathcal{R}_H \kov \exists b\in B:\exists c\in A: (a,b)\in H \es (c,d)\in H \kov (a,d)\in H$.

\bkov:\\
$(a,b)\in H \kov a\in K, (c,d)\in H \kov d\in L$, és így, mivel $H=K\times L$, $(a,d)\in H$.

Egyértelműség: tegyük fel, hogy $K\times L\ne \D_H\times\mathcal{R}_H$.  Ez két módon teljesülhet:
\begin{itemize}
\item $K\ne \D_H$
  \begin{itemize}
    \item $K \subset \D_H$, azaz $\exists a\in D_H: a\not\in K$, ami ellentmond $H=K\times L$-nek.
    \item $K \supset \D_H$, azaz $\exists a\in K: a\not\in D_H$, ami ellentmond $H=K\times L$-nek.
    \end{itemize}
\item $L\ne \mathcal{R}_H$: hasonlóan.
\end{itemize}

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

\emph{Megoldás:} Igaz, két irányú tartalmazással látható be:

\kov:

$(a,b)\in (R^{(-1)})^2 \kov \exists c: (a,c)\in R^{(-1)} \es (c,b)\in R^{(-1)} \kov (c,a)\in R \es (b,c)\in R \kov (b,a)\in R^2 \kov (a,b)\in (R^2)^{(-1)}$

\bkov:

$(a,b)\in (R^2)^{(-1)} \kov (b,a)\in R^2 \kov \exists c: (b,c)\in R\es (c,a)\in R \kov (c,b)\in R^{(-1)} \es (a,c)\in R^{(-1)} \kov (a,b)\in (R^{(-1)})^2$

\emph{3. Feladat}\\$R\subseteq \N_0\times\N_0$.
\begin{displaymath}
R(a)=\left\{
\begin{array}{ll}
\{a-2\}, & \text{ha } a>1 \\
\{2^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:}  Először adjuk meg a lezárt értelmezési tartományát!

Azok az $N_0$-beliek, amik nincsenek benne a reláció értelmezési
tartományában (a 0), biztos benne vannak a lezárt értelmezési
tartományában is.  A páros számok is benne vannak, hiszen előbb-utóbb
a szükséges végetelen sorozatnak olyan eleme kellene hogy legyen, ami
$R(0)$-nak eleme, de ilyen nem létezik.  A páratlan számok viszont
párosra ``vezetnek'', hiszen minden kettő hatvány páros.  Továbbá
minden a lezárt által értelmezett pontban a lezárt értéke csak a
$\{0\}$ lehet, hiszen ez az egyetlen $R$ által nem értelmezett elem.

$\D_{\overset{-}R} = N_0 \es \forall a\in N_0: \overset{-}R(a)=\{0\}.$

A korlátos lezárt értelmezési tartományából a páratlan számok kiesnek,
mivel nem lehet előre megmondani egy olyan lépésszám korlátot ami
mellett kettesével csökkentve egy kettő hatvány értékét eljutunk a
nullához azon korláton belül.  (Hiszen vannak tetszőlegesen nagy kettő hatványok is.)

$\D_{\overset{=}R} = N_0 \setminus \{x\in N|x\textrm{ páratlan}\} \es \forall x\in D_{\overset{=}R}: \overset{=}R(x)=\{0\}.$

\emph{4. Feladat}\\Igaz-e, hogy a programfüggvény értelmezési tartománya éppen $A^*$ ősképe a programra nézve? (4 pont)

\emph{Megoldás:} A programfüggvény és az őskép definíciója pont ezt az állítást tartalmazza:

$D_{p(S)} = \{a\in A | S(a)\subseteq A^{*}\}$

$R\subseteq A\times A: R^{-1}(H) = \{a\in D_S| R(a)\subseteq H\}$

És tudjuk, hogy $D_S = A$, mivel programról beszélünk.

\emph{5. 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)

\emph{Megoldás:} $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)>\}$\\
$p(S)((1,1,2)) = \{ (21,34,55)\}$.

\emph{6. Feladat}\\$\lceil H_1\rceil, \lceil H_2\rceil \subseteq A$.
Igaz-e, hogy ha minden $S\subseteq A\times A^{**}$ programra
$\lceil\lf(S, H_1)\rceil = \lceil\lf(S, H_2)\rceil$, akkor $\lceil H_1
\rceil = \lceil H_2 \rceil$? (10 pont)

\emph{Megoldás:} Az állítás igaz, indirekt bizonyítás: tegyük fel,
hogy a feltételek mellett $\lceil H_1 \rceil \ne \lceil H_2 \rceil$,
azaz pl. $\exists a\in \lceil H_1\rceil: a\not\in \lceil H_2\rceil$.
Válasszuk ekkor $S$-et a következő módon: $\forall b\in
A\setminus\{a\}: S(b)=\{<b...>\}$, míg $S(a)=\{<a>\}$.  Ezzel
$\D_{p(S)}=\{a\} \es p(S)(a)=\{a\}$.  Azonban ebből már látszik, hogy
$\{a\}=\lf(S, H_1)\ne \lf(S, H_2)=\emptyset$, ami ellentmond annak,
hogy tetszőlegesen választott programra a leggyengébb előfeltételeknek
egyeznie kellene.  A halmazok persze úgyis különbözhetnek, hogy
$\exists a\in\lceil H_2\rceil: a\not\in\lceil H_1\rceil$, azonban
ekkor a bizonyítás teljesen hasonló, mivel az eset szimmetrikus.

\emph{7. Feladat}\\Állapítsuk meg, hogy mennyi valódi osztója van egy
természetes számnak.  Specifikáld a feladatot! (Felhasználható a
$\chi:\L\nyil\{0,1\}$ függvény, ami az igaz helyeken 1.)  (5 pont)

\emph{Megoldás:}\\
$A=\alatt{N}{x} \times \alatt{N_0}{d}$\\
$B=\alatt{N}{x'}$\\
$Q=(x=x')$\\
$R=(Q \es d=\sum\limits_{i=2}^{x-1}\chi(i|x))$

\end{document}