\documentclass[a4paper]{article}
\usepackage{progm}
\analpacks
\analoldal{1. zárthelyi dolgozat, 2007. október 24.}
\pagestyle{empty}
\begin{document}
\noindent

``Computer Science is no more about computers than astronomy is about telescopes.''\\
--- Edsger Dijkstra



\begin{center}Bevezetés a programozáshoz 1., 1. zárthelyi dolgozat\\2007. október 24.\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}\\
Legyen $F, G \subseteq \N\times \N$ úgy, hogy: \\
$F=\{(a,b)\in \N\times\N \mathop{\big|} b|a \es b\ne 1 \es b\ne a\}$,\\
$G=\{(a,b)\in \N\times\N \mathop{\big|} 2|a \es a=2b\}$.

Írd fel a következő halmazokat:

\begin{itemize}\vspace{-3ex}
\item $G\circ F$ (2 pont)
\item $G\odot F$ (2 pont)
\item $F^{(-1)}\circ G^{(-1)}$ (3 pont)
\item $F^{-1}(G^{-1}(\{1,2\}))$ (2 pont)
\item $(G\circ F)^{(-1)}$ (3 pont)
\end{itemize}

\emph{Megoldás:} az $F$ reláció az összes valódi osztót rendeli egy $a$-hoz, a $G$ pedig a kettővel osztható számokhoz a felüket.
\begin{itemize}\vspace{-3ex}
\item $G\circ F = \{(a,b)\in \N\times\N \mathop{\big|} \exists c\in \N: c|a \es c\ne 1 \es c\ne a \es c=2b\} = \{(a,b)\in\N\times\N\mathop{\big|} 2b|a \es 2b\ne a\}$

Tehát minden $a$ számhoz azon $b$-ket rendeli a $G\circ F$, amik kétszerese valódi osztói $a$-nak.

\item Tudjuk, hogy $G\odot F$ a $G\circ F$-nél értelmezési
  tartományában szűkebb.  $G$ csak a páros számokhoz tartalmaz
  hozzárendelést, azaz $G\odot F$ csak az olyan összetett $a$-kra van
  értelmezve, amely $a$-k minden valódi osztója páros.  Ezek az
  összetett kettőhatványok, azaz a $4$ vagy annál nagyobbak.  Minden
  olyan kettőhatványt hozzárendel ezekhez a számokhoz, amelyek
  kétszerese még valódi osztó, azaz olyan $b$-ket, amik önmaguk is
  kettőhatványok, de legfeljebb $a$ negyedei.

$\mathcal{D}_{G\odot F} = \{a\in \N\mathop{\big|} \exists k>1: a=2^k\}$

$\forall a\in\mathcal{D}_{G\odot F}: G\odot F(a)=\{b\in\N\mathop{\big|}\exists k\in\N_0: b=2^k \es 2b<a\}$

\item $(G\circ F)^{(-1)} = F^{(-1)}\circ G^{(-1)}$ tetszőleges
  relációkra, így most is, úgyhogy ld. utolsó feladat.

\item $F^{-1}(G^{-1}(\{1,2\}))$

$G^{-1}(\{1,2\})=\{2,4\}$, $F^{-1}(\{2,4\})=\{4,8\} =F^{-1}(G^{-1}(\{1,2\}))$

\item $(G\circ F)^{(-1)}$, az első feladat eredményének inverze csupán:

$(G\circ F)^{(-1)} = \{(a,b)\in\N\times\N\mathop{\big|} 2a|b \es 2a\ne b\}$

\end{itemize}

\pagebreak

\emph{2. Feladat}\\Legyen $Q, R, S \subseteq A\times A$.  Igaz-e, hogy
\begin{itemize}
\item $R\subseteq S \kov R\odot Q \subseteq S\odot Q$, (7 pont)
\item $R\subseteq S \kov Q\odot R \subseteq Q\odot S$? (3 pont)
\end{itemize}

\emph{Megoldás:} az első állítás igaz, míg a második hamis, ugyanis ha
az először alkalmazott relációt bővítjük, azzal új ``zsákutcákat''
hozhatunk létre, amit a szigorú kompozíció kiszűr és így összességében
szűkebb relációt kapunk, mintha szűkebb lett volna az először alkalmazott reláció.

Tehát:
\begin{itemize}\vspace{-3ex}
\item Igaz, ugyanis $(a,b)\in R\odot Q \kov
\exists c: (a,c)\in Q \es (c,b)\in R \es Q(a)\subseteq\mathcal{D}_R
\overset{R\subseteq S}\kov
\underbrace{\exists c: (a,c)\in Q \es (c,b)\in S \es Q(a)\subseteq\mathcal{D}_S}_{(a,c)\in S\odot Q}$

\item Hamis, ugyanis $Q:=\{(1,1)\}, R:=\{(1,1)\}\subseteq S:=\{(1,1),(1,2)\} \kov Q\odot R=\{(1,1)\}\not\subseteq\emptyset=Q\odot S$
\end{itemize}

\emph{3. Feladat} (8 pont)\\Adjunk példát olyan nem üres relációra, amelynek
lezártja üres halmaz, és van olyan $\pi$ feltétel, hogy a reláció
feltételre vonatkozó lezártjának értelmezési tartománya megegyezik az
eredeti reláció értelmezési tartományával!

\emph{Megoldás:}

$A:=\{1\}, A\times A \supseteq R:=\{(1,1)\}, \pi:=\text{HAMIS}$, azaz $\pi(1)=\hamis$.

Ekkor az $\overline R = \emptyset$, ugyanis az egyetlen $A$-beli pontból elindulva a reláció végtelen sokszor ``végrehajtható''.

Ugyanakkor $R|\pi = \emptyset$, hiszen $\pi$ a konstans hamis és így
$\overline{R|\pi} = \{(1,1)\}$, mivel tudjuk, hogy egy reláció által
nem értelmezett pontok mindig benne vannak önmagukkal a reláció
lezártjában és így $\mathcal{D}_{\overline{R|\pi}} = \{1\} = \mathcal{D}_R$, tehát a példa helyes.

\emph{4. Feladat} (10 pont)\\$F\subseteq A\times A$ feladat. $S_1, S_2$ programok $A$-n.
Az $S_1$ és az $S_2$ is megoldja az $F$ feladatot. \\ Igaz-e, hogy az
$S=(S_1 \cup S_2)$ program is megoldja az $F$ feladatot?

\emph{Megoldás:} igaz, a megoldás két feltételét kell bebizonyítanunk:
\begin{itemize}
\item $\mathcal{D}_F\subseteq\mathcal{D}_{p(S_1\cup S_2)}$:

  $(i)$ A programfüggvény értelmezési tartományának definíciója miatt
  $\mathcal{D}_{p(S_1\cup S_2)} = \mathcal{D}_{p(S_1)}\cap
  \mathcal{D}_{p(S_2)}$. Nyilván, a programok uniójának
  (egybeírásának) hatásrelációja csak ott lesz értelmezve, ahol
  mindkét program mentes volt a végtelen sorozatoktól, tehát a
  kettejük értelmezési tartományának metszetén.

  $(ii)$ Mivel $S_1$ és $S_2$ megoldják $F$-et, ezért
  $\D_F\subseteq\D_{p(S_1)}$ és $\D_F\subseteq\D_{p(S_2)}$. 

  Tehát
  $\D_F\overset{(ii)}\subseteq\D_{p(S_1}\cap\D_{p(S_2)}\overset{(i)}=\D_{p(S_1\cup
    S_2)}$.

\item $\forall a\in\mathcal{D}_F:p(S_1\cup S_2)(a)\subseteq F(a)$:

  $(i)$ A definícióból következik, hogy azokban a $b$ pontokban, ahol mindkét
  programfüggvény értelmezett (és mivel mindkét program megoldja a
  feladatot, minden most tekintett $a$ ilyen): $p(S_1\cup
  S_2)(b)=p(S_1)(b)\cup p(S_2)(b)$.

  $(ii)$ Azt is tudjuk, a megoldás definíciójából, hogy $p(S_1)(a)\subseteq
  F(a)$ és $p(S_2)(a)\subseteq F(a)$.

  Készen vagyunk, hiszen így: $\forall a \in\mathcal{D}_F: p(S_1\cup S_2)(a)\overset{(i)}=p(S_1)(a)\cup p(S_2)(a)\overset{(ii)}\subseteq F(a)$.
\end{itemize}

\emph{5. Feladat} (8 pont)\\
Igaz-e, hogy ha $\lf(S_1, R)=\lf(S_2, R)$, akkor
$\lf(S_1\cup S_2, R)=\lf(S_1,R)\vagy\lf(S_2, R)$?

\emph{Megoldás:} igaz, ui. \\$\lceil\lf(S_1\cup S_2, R)\rceil =
\{a\in\D_{p(S_1\cup S_2)}\mathop{\big|} p(S_1\cup S_2)(a)\subseteq
\lceil R\rceil\} \overset{\text{ld. előző feladat}} =
\{a\in\D_{p(S_1)}\cap\D_{p(S_2)}\mathop{\big|}(p(S_1)(a)\cup
p(S_2)(a))\subseteq \lceil R\rceil\} =$ \\ $=
\{a\in\D_{p(S_1)}\mathop{\big|}p(S_1)(a)\subseteq\lceil R\rceil\} \cap
\{a\in\D_{p(S_2)}\mathop{\big|}p(S_2)(a)\subseteq\lceil R\rceil\} =
\lceil\lf(S_1, R)\es\lf(S_2, R)\rceil\overset{\text{A két lf egyenlő.}}= 
\lceil\lf(S_1, R)\vagy\lf(S_2, R)\rceil$

\pagebreak

\emph{6. Feladat}\\
Keressük meg egy természetes szám legnagyobb prímosztóját.  Specifikáld
a feladatot! (8 pont)

\emph{Megoldás:}

$A=\alatt\N n\times\alatt\N o$\\
$B=\alatt\N {n'}$\\
$Q: (n=n')$\\
$R: (Q\es o|n \es o \text{ prím} \es \forall p\in\N: (p \text{ prím} \es p|n) \nyil p\le o)$

\emph{7. Feladat}\\
Keressük meg egy természetes szám egy osztóját.  Specifikáld
a feladatot! (4 pont)

\emph{Megoldás:}

$A=\alatt\N n\times\alatt\N o$\\
$B=\alatt\N {n'}$\\
$Q: (n=n')$\\
$R: (Q\es o|n)$

\end{document}