%\lstdefinelanguage{pla}%
%{keywords={.i,.o,.e,.p}, sensitive=false, morecomment=[l]{#} }

\lstdefinelanguage{pla} {keywords={.i,.o,.p,.e}, sensitive=false,
morecomment=[l]{\#}}

\lstset{
    language=pla,
    frame=,
    framesep=8pt,
    backgroundcolor=\color{VeryLightGray},
    basicstyle=\small,
    keywordstyle=\rmfamily\color{DarkGray}\bfseries,
    identifierstyle=\rmfamily \color{RealGray},
    commentstyle=\rmfamily\color{LightGray}\itshape,
    stringstyle=\rmfamily\color{RealGray}\itshape,
    showstringspaces=false,
    escapechar=\#
}

\chapter{Základní definice}%
\label{kap_definice}%
Jak napovídá název této kapitoly, následující řádky budou věnovány základním
definicím a~používaným termínům. Účelem tohoto souhrnu je seznámit čtenáře se
základními pojmy a~především \emph{přesně} vysvětlit, v jakém smyslu budou
používány v dalších kapitolách - nikoliv ho tuto látku naučit.

\section{Booleova algebra}%
Logické funkce, které využívají dvouhodnotovou logiku \footnote{Obor hodnot je
${0, 1}$ .} se označují jako \emph{Booleovy funkce}. Matematickým nástrojem k
práci s Booleovými funkcemi
je \emph{Booleova algebra}.\\
Booleova algebra B je definována jako distributivní a komplementární svaz,
který se skládá z:
\begin{itemize}
\item Konečné množiny logických proměnných ($a,b,c,d,...,x,y,z$),
\item Binárních operací logického součtu (označovaného $+$ nebo $\vee$)
a logického součinu ($.$ nebo $\wedge$),
\item Unární operace negace ( $\bar{}$ nebo $\neg$),
\item a dvou nulárních operací v podobě logických konstant $0$ a $1$.
\end{itemize}
Pro takto definovanou Booleovu algebru platí základní zákony zobrazené v
tabulce \ref{bool_laws}. Z nich se nechá odvodit řada dalších zákonů
\cite{Jan01} včetně \emph{Shannonova expanzního teorému}, o kterém bude řeč v
dalších kapitolách.

\btab \caption{Zákony Booleovy algebry}%
\label{bool_laws}%
\vskip 20pt
\begin{tabular}{lc}
\toprule
Zákon & Vztah\\
\midrule
\multirow{2}{*}{Komutativita} & $a+b=b+a$\\
                              & $a.b=b.a$\\[7pt]
\multirow{2}{*}{Asociativita} & $(a+b)+c=a+(b+c)$\\
                              & $(a.b).c=a.(b.c)$\\[7pt]
\multirow{2}{*}{Distributivita}& $a+(b.c)=(a+b).(a+c)$\\
                              & $a.(b+c)=(a.b)+(a.c)$\\[7pt]
\multirow{2}{*}{Neutralita 0 a 1}& $a+0=a$\\
                              & $a.1=a$\\[7pt]
\multirow{2}{*}{Vlastnosti komplementu}& $a+\bar{a}=1$\\
                              &$a.\bar{a}=0$\\
\bottomrule
\end{tabular}
\etab

Z předchozích řádků je víceméně patrné, jaký zápis logických operátorů byl v
této práci použit, pro úplnost je kompletní seznam možností zápisu jednotlivých
logických operací uveden v tabulce \ref{bool_ops}.

\section{Vyjádření logických funkcí}%
Logická (Booleova) funkce $n$ proměnných je definována jako $f: B^n\rightarrow
B$, je-li $B$ Booleova algebra. Logickou funkci lze zapsat několika způsoby.
Dále v textu budeme hovořit o těchto:
\begin{itemize}
\item pravdivostní tabulka,
\item logický výraz,
\item mapa,
\item vícerozměrná jednotková krychle,
\item modifikované binární diagramy (MBD).
\end{itemize}

\noindent O mapách a krychlích zde bude zmínka jen okrajová. Hlavní pozornost
bude věnována logickým výrazům, pravdivostním tabulkám a pochopitelně hlavnímu
tématu této práce - MBD. Příklad jedné funkce zapsané pomocí pravdivostní
tabulky a logického výrazu je v \ref{truth_tab}. Následuje seznam používaných
výrazů a jejich význam.

\paragraph{literál} Název pro logickou proměnnou a její doplněk ($a$ a $\bar{a}$).
Jde o logický výraz tvořený pouze jednou proměnnou.



\paragraph{term} Term logický výraz tvořený pouze literály a jen jednou
binární logickou operací (např. $a+b+c$ nebo $abc$). \textbf{Pozor}: Bude-li v
dalším textu použit výraz \emph{term}, pak jím bude myšlen pouze term tvořený
proměnnými a logickými \emph{součiny}.

\btab \caption{Zápis Booleových operací}%
\label{bool_ops}%
\vskip 20pt
\begin{tabular}{lc}
\toprule
Operace & Zápis\\
\midrule
logický součet & $a+b$\\
logický součin & $a.b$ nebo je vynechán - $ab$)\\
negace         & $\bar{}$ ($\bar{a}$)\\
\bottomrule
\end{tabular}
\etab

\btab \caption{Pravdivostní tabulka pro logický výraz
$f(a,b,c)=abc+\bar{a}bc+a\bar{b}\bar{c}$} \label{truth_tab}%
\vskip 20pt
\begin{tabular}{cccc}
\toprule
\multicolumn{3}{c}{Vstupy}  & Výstup\\
a&b&c&f(a,b,c)\\
\midrule
0&0&0&0\\
1&0&0&1\\
0&1&0&0\\
1&1&0&0\\
0&0&1&0\\
1&0&1&0\\
0&1&1&1\\
1&1&1&1\\
\bottomrule
\end{tabular}
\etab


\paragraph{logický výraz} Bude-li řeč o logické funkci (nebo výrazu), vždy tím bude myšlena funkce (výraz), ve které se logické součiny
vyskytují ve dvou úrovních. Jde o tzv. \emph{dvouúrovňovou logiku}. Příklad: $$ab+\bar{b}c+\bar{a}c$$%
Logický výraz může být zapsán řadou způsobů, z nichž v této práci bude
nejpoužívanější tzv. \emph{disjunktivní normální forma} (DNF). Pod tímto
termínem se skrývá logický výraz tvořený logickými součty termů logických
součinů (viz předchozí příklad).

\paragraph{logické proměnné} V dalším textu budou používány výhradně logické proměnné
s písmenem $x$ a odlišené kladnými indexy od $0$ do $n$ - tedy: $x_0, x_1,
x_2,..., x_{n-1}, x_{n}$.

\paragraph{ONset, OFFset, DCset} \emph{ONsetem}, \emph{OFFsetem}, \emph{DCsetem} jsou myšleny
množiny termů logické funkce, jejichž výstupem je logická $1$ (ONset), $0$ (OFFset)
nebo jejichž výstup není určen (DCset). Tyto množiny se pro danou logickou
funkci $f$ značí jako $f_{on}$, $f_{off}$ a $f_{dc}$.

\paragraph{implikant logické funkce} Součinový term, který definuje logickou
funkci. Každý term z~množiny ONset je implikantem logické funkce.

\paragraph{přímý implikant} Takový \emph{implikant} logické funkce, který už není
možné více zjednodušit, např. odebráním redundantního literálu.

\paragraph{Shannonův expanzní teorém} Stojí na myšlence, že každá logická
funkce $f$ může být rekurzivně rozložena (expandována) následujícím způsobem:
$$f(x_0, x_1,...x_n) =  x_0.f_{high}(1, x_1,...x_n) + \bar{x_0}.f_{low}(0, x_1,...x_n)$$
V každém kroku se funkce rozpadne na dvě podfunkce $f_{high}$ a $f_{low}$. Z
každé z nich je vyloučena vybraná proměnná $x_i$ a nahrazena 1 ($f_{high}$)
nebo 0 ($f_{low}$). Výsledná funkce je pak určena součtem násobků těchto
podfunkcí s literálem nahrazené proměnné - $x_i$ pro $f_{high}$ a $\bar{x_i}$
pro $f_{low}$.

\paragraph{if-then-else normálová forma} Pokud se logický výraz úplně rozloží
pomocí Shannonova expanzního teorému, pak je v takzvané \uv{if-then-else
normálové formě}. Z toho vyplývá i existence \emph{if-then-else} operátoru
(zkráceně \emph{ite}), pomocí něhož lze vyjádřit všechny logické operace.
Například logický součin funkcí $f$ a $g$ se vyjádří jako $ite(f, g, 0)$ a
logický součet jako $ite(f, 1, g)$.



\section{Formát PLA}
Formát PLA byl použit na načítání a ukládání MBD. Jde o velmi jednoduchý a
přímý způsob dvouúrovňové logické funkce. Zde budou popsány jen jeho
nejdůležitější použité vlastnosti. Více je možné najít v \cite{boompla06}.\\
\indent Funkce uložená pomocí PLA formátu je zapsána textovém souboru s
koncovkou pla. Soubor se načítá po jednotlivých řádcích a každý řádek souboru
pak reprezentuje určitý parametr nebo vlastnost logické funkce. Podporované
parametry jsou:

\paragraph{.i [číslo]} Číslo uvedené za parametrem \uv{.i} udává počet vstupních
proměnných.
\paragraph{.o [číslo]} Číslo uvedené za parametrem \uv{.u} udává počet výstupů logické
funkce.
\paragraph{.p [číslo]} Číslo uvedené za parametrem \uv{.p} udává počet termů.
\paragraph{.type [typ]} Typ definuje způsob definice logické funkce. V této
práci je podporován pouze typ \uv{fd}. Ten označuje funkci zadanou pomocí
ONsetu a DCsetu.
\paragraph{.e} Označuje konec definice funkce.
\\

\noindent Samotná funkce je definována pomocí seznamu termů, kde každý term je zadán
takto:
\begin{center}
-10-101~~1-0,
\end{center}
kde část před mezerou určuje vstupní proměnné funkce a část za mezerou určuje
výstup termu. Znak $-$ označuje neurčený vstup/výstup, $0$ ve vstupní části
označuje negovaný literál proměnné a $1$ označuje nenegovaný literál. $1$ ve
výstupní části určuje skutečnost, že daný term patří do ONsetu pro daný výstup.
$0$ ve výstupní části naopak říká, že term patří do OFFsetu daného výstup - s
touto informací se však nijak nepracuje, jelikož program pracuje s~množinami
ONset a DCset. Příklad pla souboru je na obrázku \ref{pla_ex}.

\bfig
\begin{lstlisting}
.i 6
.o 1
.p 3
1--0-- 1-
-0--1- 01
--1--0 10
.e
\end{lstlisting}%
\caption[Příklad PLA souboru]{ \textbf{Příklad PLA souboru.} PLA soubor pro
logickou funkci $f$ se dvěma výstupy $f^0$ a~$f^1$. Kde $f^0_{on} =
(x_0\bar{x_3},x_2\bar{x_5})$, $f^0_{dc} = \emptyset$; $f^1_{on} =
(\bar{x_1}x_4)$, $f^1_{dc} = (x_0\bar{x_3})$.
}%
\label{pla_ex}%
\efig




%\section{Použité nástroje a technologie}
%dasdasda
