\documentclass[b5paper,10pt]{book}
\usepackage{KnuthMarcius20}
\usepackage{mycolortbl}
\usepackage{arabtex}
\usepackage[nocatcodes]{devanagari}


\makeindex

\renewcommand{\sfdefault}{ufu}

\setcounter{chapter}{6}
\setcounter{tocdepth}{4}
\setcounter{section}{5}
\setcounter{subsection}{1}
\setcounter{subsubsection}{3}
\setcounter{figure}{0}
\setcounter{equation}{0}
\setcounter{page}{1}
\font\dnten=dvng8 at 10pt
\font\grkten=kdgr8 at 10pt
\font\arabten=nash14 at 10pt
\font\arab=nash14
  
\begin{document}
\renewcommand\sz[1]{[\textit{#1}]}
\def\figdir{abrak} % ábrakönyvtár átnevezése
\def\CEE/{{\mc C\spacefactor1000}}% the C programming language
\def\MF{{\manfnt META}\-{\manfnt FONT}}%
\def\bool#1{\mathbin{\catcode`\.=12\vcenter{\hbox{$#1$}}}}
\def\nbool#1{\mathbin{\catcode`\.=12     \mkern1.5mu\overline{\mkern-1.5mu#1\mkern-1.5mu}\mkern1.5mu}}
\def\contra{\bool{\bot}} %%% rendben
\def\nimp{\nbool\supset}   %%% rendben
\def\quant{\lower.23ex\hbox{epsfbox{\figdir/v4a.9}}}   %%% ábra kell
\def\lproj{\bool{\epsfbox{\figdir/v4a.10}}}   %%% ábra kell
\def\cnimp{\nbool\subset}    %%% rendben
\def\rproj{\bool{\epsfbox{\figdir/v4a.11}}} %%% ábra kell
\def\xor{\oplus}       %%% rendben
\def\nor{\nbool\lor}   %%% rendben
\def\leqv{\bool\equiv}    %%% rendben
\def\rcomp{\nbool{\rproj}}   %%% ábra kell
\def\cimpl{\bool\subset}   %%% rendben
\def\lcomp{\nbool{\lproj}}   %%% ábra kell
\def\impl{\bool\supset} %%% rendben
\def\nand{\nbool{\land}}  %%% rendben
\def\affirm{\bool{\top}}  %%% rendben
\def\vtiny{\vskip.2pt}    %%% rendben
\def\orie{\rlap{$\,\vec{}$}} % oriented graph modifier
\def\rest{\mathbin{\mid}}

\hyphenation{}

%\newpage
\tableofcontents
  
\hyphenation{
függ-vény-nek
függ-vényt
mély-ség-re
}

\def\band{\:\&\:}
\def\bor{\:|\:}

%%% 1
\ujgyak \label{megold712-1}
$\left(\left(x_1\lor x_4\right)\land x_2\right) \leqv \left(x_1\lor x_3\right)$.
%%% 2
\ujgyak \label{megold712-2}
(a) $\left(w\xor\left(x\land y\right)\right)\xor\left(\left(x\xor y\right)\land z\right)$;
(b) $\left(w\land\left(x\lor y\right)\right)\land\left(\left(x\land y\right)\lor z\right)$.
%%% 3
\ujgyak \label{megold712-3} {\cite{Finikov1957}}
Tekintsünk egy $k\times n$-es mátrixot, melynek sorait azon $x$ vektorok alkotják, melyekre $f(x)=1$.
A változók permutálásával és/vagy negálásával feltételezhetjük, hogy az elsõ sor az $1\ldots 1$ és az oszlopok rendezve vannak.
Tegyük fel, hogy $l$ különbözõ oszlopunk van. Ekkor $f=g\land h$, 
 melyben $g$ az összes $(x_{j-1}\leqv x_j)$ kifejezés konjunkciója, 
  ahol $1<j\leq n$, és a $j-1$.\ oszlop megegyezik a $j$.\ oszloppal,
 míg $h$ jelöli a $k$ darab $l$ hosszúságú minterm diszjunkcióját,
  ahol az azonos oszlopok közül mindig csak egyet használunk.
Például, ha $n=8$ és $f$ a következõ $k=3$ pontban igaz: $11111111$, $00001111$, $00110111$, akkor $l=4$, míg $f(x)$ megegyezik 
 $\left(x_1\leqv x_2\right)\land \left(x_3\leqv x_4\right)\land 
  \left(x_6\leqv x_7\right)\land \left(x_7\leqv x_8\right)\land
  \left(\left(x_1\land x_3\land x_5\land x_6\right) 
  \lor \left(\bar x_1\land \bar x_3\land x_5\land x_6\right)
  \lor \left(\bar x_1\land x_3\land \bar x_5\land x_6\right)\right)$
  formulával.
Az így kapott formula hossza $2n+\left(k-2\right)l-1$, ahol $l\leq 2^{k-1}$.

Figyeljük meg, hogy ha $k$ nagy, akkor rövidebb formulát kapunk, 
 ha $f(x)$-et $f_1(x)\lor \ldots \lor f_r(x)$ alakban írjuk fel, 
 ahol minden $f_j$ legfeljebb $\left\lceil k/r\right\rceil$ 1-est tartalmaz.
Ekkor
\[
L(f) \leq \min_{r\geq 1}\left(r-1+\left(2n+\left\lceil k/r-2\right\rceil 2^{\left\lceil k/r-1\right\rceil}\right)r\right).
\]
%%% 4
\ujgyak \label{megold712-4}
Az elsõ egyenlõtlenség közvetlen következménye annak, hogy egy $d$ mélységû bináris fa legfeljebb 
$1+2+\ldots +2^{d-1} = 2^d-1$ belsõ csúcsot tartalmazhat.

Az utalás rendben van, hiszen létezik legkisebb részfa, melynek mérete $\geq \left\lfloor r/3\right\rfloor$. Ennek mérete $s$ legfeljebb $1+2\left(\left\lfloor r/3\right\rfloor -1\right)$. Ez alapján $f=\left(g?\ f_1:\ f_0\right)$, ahol $g$ egy $s$ méretû részformula, míg $f_0$ és $f_1$ olyan $r-s-1$ méretû formulák, melyeket $f$-bõl a $g$ helyére rendre $0$ illetve $1$ helyettesítésével kapunk.

Legyen $d(r)=\max\left\{D(f)\rest L(f)=r\right\}$. Mivel a mux\index{mux = mux}%^{mux}
függvény mélysége~2, és $\max(s,r-s-1)<\left\lceil \frac{2r}{3}\right\rceil$, ezért $r\geq 3$ esetén $d(r)\leq 2+d\left(\left\lceil \frac{2r}{3}\right\rceil-1\right)$, 
melybõl az eredmény $r$ szerinti indukcióval következik \cite{Spira1971}.
%%% 5
\ujgyak \label{megold712-5}
Legyen $g_0=0$, $g_1=x_1$, és $g_j=x_j\land(x_{j-1}\lor g_{j-2})$, ahol $j\geq 2$. Ekkor $F_n=g_n\lor g_{n-1}$, 
melynek költsége $2n-2$, mélysége pedig $n$. [Ezek a $g_j$ függvények fontos szerepet játszanak a bináris összeadásnál is. 
A \ref{gyak712-42}-es, illetve \ref{gyak712-44}-es gyakorlatoknál bemutatjuk, hogyan lehet õket $O(\lg n)$ mélységû 
fügvényekkel meghatározni.]
%%% 6
\ujgyak \label{megold712-6}
Igaz: vizsgálja meg az $y=0$ valamint az $y=1$ esetet.
%%% 7
\ujgyak \label{megold712-7}
$\hat x_5=x_1\lor x_4$, $\hat x_6=x_2\land \hat x_5$, $\hat x_7=x_1\lor x_3$, $\hat x_8=\hat x_6\xor\hat x_7$.
(Az eredeti lánc a (\ref{keplet712-6})-os \idez{random}\index{pí = pi}%^^{pi}
függvényt számítja; lásd az \ref{gyak712-1}.\ gyakorlatot. Az új lánc ennek a függvénynek a normalizáltját,
\index{normalizálás = normalization} nevezetesen a negáltját számítja.)
%%% 8
\ujgyak \label{megold712-8}
Az $x_k$ igazságtáblájában $2^{n-k}$ darab 0-t, valamint $2^{n-k}$ darab 1-est tartalmazó blokkok váltakoznak, 
 amint az a (\ref{keplet712-7})-ben is megfigyelhetõ.
így ha megszorozzuk $2^{2^{n-k}}+1$-gyel, az eredményül kapott $x_k+\left(x_k \ll 2^{n-k}\right)$ csupa 1-esbõl fog állni.
%%% 9
\ujgyak \label{megold712-9}
Az L6-os lépésben, amikor $L(f)=\infty$, tároljuk el $g$-t és $h$-t egy $f$-hez rendelt rekordban.
Ekkor $f$-hez egy rekurzív eljárás\index{rekurzív eljárás = recursive procedure}%^{recursive procedure}
segítségével, a megfelelõ $g$ és $h$ felhasználásával elõállítható egy minimum hosszúságú formula.
%%% 10
\ujgyak \label{megold712-10}
Az L3-as lépésben írjunk $k=r-1-j$ helyére $k=r-1$-et, valamint írjuk át mindenhol az $L$-et $D$-re.
%%% 11
\ujgyak \label{megold712-11}
Az egyetlen probléma az, hogy az U3 lépésben \emph{csökkenteni} kell $j$-t. 
Ekkor $j=0$ esetén $\phi(g) \band \phi(h) \ne 0$, 
így az összes $r-1$ költségû esetet megtaláljuk, még mielõtt nekifognánk az $r-1$. listának.
\par\algindentset{\hskip\parindent U1}
\algstep U1. [Kezdeti beállítás.] Legyen $U(0)\gets\phi(0)\gets0$ míg
$U(f)\gets\infty$ minden $1\le f<2^{2^n-1}$ esetén.
Ekkor legyen $U(x_k)\gets\phi(x_k)\gets 0$ és fûzzük $x_k$-t a 0.~listához, ahogy azt az L1 lépésben tettük.
Ugyanakkor legyen $U(x_j\circ x_k)\gets 1$, és rendeljük $\phi(x_j\circ x_k)$-hoz a neki megfelelõ 1~súlyú bit vektort, 
és fûzzük $x_j\circ x_k$-t az 1.~listához, minden $1\le j<k\le n$ és mind az öt $\circ$ normál operátor esetén.
Végül legyen $c\gets 2^{2^n-1}-5{n\choose2}-n-1$.

\algstep U2. [Ciklus $r$-re.] Ismételjük az U3 lépést $r=2,\ 3,\ \dots$ esetén, amíg $c>0$.

\algstep U3. [Ciklus $j$-re és $k$-ra.] Ismételjük az U4 lépést $j=\lfloor(r-1)/2\rfloor,\ 
\lfloor(r-1)/2\rfloor-1,\ \dots$, valamint $k=r-1-j$ esetén, amíg $j\ge0$.

\algstep U4. [Ciklus $g$-re és $h$-ra.] Ismételjük az U5 lépést a $j$.~lista minden $g$ és a $k$.~lista minden $h$ elemére.
Amennyiben $j=k$, csak azon $h$ elemeket tekintsük, melyek a $g$ \emph{után következnek} a $k$.~listán.

\algstep U5. [Ciklus $f$-re.] 
Ha $\phi(g)\band\phi(h)\ne0$, akkor legyen $u\gets r-1$ és $v\gets\phi(g)\band\phi(h)$,
különben pedig legyen $u\gets r$ és $v\gets\phi(g)\bor\phi(h)$. 
Ekkor végezzük el az U6 lépést 
$f=g\band h$,
$f=\bar g\band h$,
$f=g\band\bar h$,
$f=g\bor h$, illetve
$f=g\xor h$ esetén.

\algstep U6. [$U(f)$ és $\phi(f)$ aktualizálása.] 
Ha $U(f)=\infty$, akkor legyen $c\gets c-1$, $\phi(f)\gets v$, és fûzzük $f$-et az $u$.~listához.
Különben, ha $U(f)>u$, akkor legyen $\phi(f)\gets v$, és helyezzük át $f$-et az $U(f)$.~listáról az $u$.~listára.
Ha pedig $U(f)=u$, akkor legyen $\phi(f)\gets\phi(f)\bor v$.\quad\slug 
%%% 12
\ujgyak \label{megold712-12}
$x_4=x_1\xor x_2$, $x_5=x_3\land x_2$, $x_6=x_2\land\bar x_4$, $x_7=x_5\lor x_6$.
%%% 13
\ujgyak \label{megold712-13}
$f_5=01010101$ ($x_3$);
$f_4=01110111$ ($x_2\lor x_3$);
$f_3=01110101$ ($(\bar x_1\land x_2)\lor x_3$);
$f_2=00110101$ ($x_1{?}\ x_3{:}\ x_2$);
$f_1=00010111$ ($\langle x_1 x_2 x_3\rangle$).
%%% 14
\ujgyak \label{megold712-14}
Tetszõleges $1\le j\le n$ esetén számítsuk ki $t\gets (g\xor(g\gg2^{n-j}))\band x_j$, $t\gets t\xor(t\ll2^{n-j})$, 
ahol $x_j$ a (\ref{keplet712-11})-es igazságtábla. 
Ekkor $1\le k\le n$ és $k\ne j$ esetén az $x_j\gets x_j\circ x_k$
mûveletnek megfelelõ igazságtábla a $g\xor(t\band((x_j\circ x_k)\xor x_j))$ képlettel számítható.
(Mivel az $(x_j\circ x_k)\xor x_j$ által leírt $5n(n-1)$ különbözõ mûvelet $g$-tõl független, azok elõre kiszámíthatóak.
Ugyanez az ötlet mûködik az ennél általánosabb $x_{j(i)}\gets x_{k(i)}\circ_i x_{l(i)}$ alakú számításokra,
és a neki megfelelõ $(x_k\circ x_l)\xor x_j$ által leírt $5n^2(n-1)$ féle mûveletre is.)
%%% 15
\ujgyak \label{megold712-15}
Valódi aszimmetrikus módszerek szimmetrikus függvények kiszámítására:
$$
\openup-1\jot
\begin{aligned}
	{\rm(a)}\enspace 
	x_1&\gets x_1\xor x_2,\cr
	x_3&\gets x_3\xor x_4,\cr
	x_1&\gets x_1\xor x_3,\cr
	x_2&\gets x_2\xor x_4,\cr
	x_3&\gets x_3\lor x_2,\cr
	x_3&\gets x_3\land\bar x_1.\cr
	&\phantom{x_3\land\bar x_1}\cr
\end{aligned}
\qquad
\begin{aligned}
	{\rm(b)}\enspace 
	x_1&\gets x_1\xor x_2,\cr
	x_2&\gets x_2\land\bar x_1,\cr
	x_3&\gets x_3\xor x_4,\cr
	x_4&\gets x_4\land x_1,\cr
	x_2&\gets\bar x_2\land x_3,\cr
	x_2&\gets x_2\xor x_1,\cr
	x_2&\gets x_2\land\bar x_4.\cr
\end{aligned}
\qquad
\begin{aligned}
	{\rm(c)}\enspace 
	x_1&\gets x_1\xor x_2,\cr
	x_2&\gets x_2\xor x_3,\cr
	x_2&\gets x_2\lor x_1,\cr
	x_1&\gets x_1\xor x_4,\cr
	x_1&\gets x_1\land x_3,\cr
	x_2&\gets x_2\land\bar x_1,\cr
	x_2&\gets x_2\xor x_4.\cr
\end{aligned}
\qquad\qquad
$$

 
\bibliography{KnuthMarcius26}
\bibliographystyle{infalg}
\begin{printindex}
\end{printindex}
\begin{printangolnevindex}
\end{printangolnevindex}
\end{document}
