\chapter{Metody pro minimalizaci logických funkcí}
\label{chap:mini}

Tato kapitola popisuje metody pro~minimalizaci logických funkcí. Nejprve jsou uvedeny základní definice a
značení.  Poté je stručně popsána historie minimalizace a potom už následují dvě sekce, které popisují
vizualizační metody. Konkrétně se jedná o Booleovskou n-krychli a Karnaughovu mapu. Poslední dvě sekce popisují
algoritmy používané pro~minimalizaci. Konkrétně jde o~algoritmus Quine-McCluskey a sadu algoritmů Espresso.  

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  Základní definice a značení

\section{Základní definice a značení}
\label{sec:defs}
V~této sekci jsou uvedeny základní pojmy a značení, které se budou ve~zbytku práce užívat. Předpokládá se, že čtenář
je znalý základů matematické logiky a logických obvodů. Proto jsou nejzákladnější pojmy vynechány.

Pokud je zvoleno $\setname{B} = \{0,1\}$ a  $\setname{Y} = \{0,1,2\}$ je logická funkce $f$ definována jako
\begin{displaymath}
  f : \setname{B}^n \to \setname{Y}^m
\end{displaymath}
kde $x = [x_1,\ldots,x_n] \in \setname{B}^n$ je vstup, přičemž $n$ značí počet vstupních proměnných, \linebreak a~$y =
[y_1,\ldots,y_m] \in \setname{Y}^m$ je výstup. Zde je $m$ počet výstupních proměnných. Tato práce se omezuje pouze  
na~jednohodnotový výstup. Pak bude $m = 1$ a $y \equiv y_1$. Je třeba poznamenat, že hodnota $2$ v~$\setname{Y}$ značí 
neurčený nebo-li don't-care stav. 

Všechna $x$, pro~něž platí, že $f(x)=1$, náleží do~množiny \textbf{on-set} značené \onset{}. Dále všechna $x$, pro~něž
platí, že $f(x)=0$, náleží do~množiny \textbf{off-set} značené \offset{}. A nakonec všechna $x$, pro~něž platí, že
$f(x)=2$, náleží~do množiny \textbf{don't-care set} značené \dcset{}. Samotné $x$ bývá často nazýváno term nebo
cube. V~dalším textu bude používán název \textbf{term} a někdy pouze zkráceně \term{}. Obecná množina termů se nazývá
\textbf{pokrytí} a~často bude označována jako \cover{}. Operace $=$ pro dvě pokrytí bude značit logickou
ekvivalenci. Pro $i$-tý term \term{} v~pokrytí \cover{} bude používáno značení $\term{}^i$ nebo $\cover_i$, pokud nebude
z~kontextu jasné jakému pokrytí $t$ náleží. Počet termů v~\cover{} bude značen jako $|\cover|$. Hodnoty proměnných
$x_1,\ldots,x_n$ pro~určitý term \term{} budou nazývány \textbf{literály}. Literál na $j$-té pozici pak bude značen jako
$\term{}_j$ nebo $\cover_{i,j}$, pokud bude třeba zdůraznit, že se jedná o $j$-tý literál $i$-tého termu v pokrytí
\cover{}. Zároveň samozřejmě platí, že $i \in  \{1,\ldots,|\cover|\}$ a $j \in \{1,\ldots,n\}$. 

Definiční obor literálu bude ještě rozšířen tak, že $\term{}_j \in \{0,1,2\}$. Hodnota $2$ bude značit, že
se daný literál v~termu neobjevuje. Pokud se pak bude hovořit o~počtu literálu, nebude tedy literál nabývající hodnoty
$2$ do~tohoto součtu započítán. 

Z výše uvedeného vyplývá, že pokrytí $\onset \cup \dcset \cup \offset$ pokrývá všechny termy funkce $f$, což lze zapsat
jako $f = (\onset,\dcset,\offset)$. Pro libovolné pokrytí \cover{} existuje doplněk do~$\onset \cup \dcset \cup
\offset$. Ten se nazývá \textbf{komplement} a bude značen \ol{\cover}. Prázdné pokrytí bude značeno $\emptyset$, tedy
jako prázdná množina. Znak $\emptyset$ bude používán i ve~významu neexistujícího termu a někdy i neexistujícího
literálu. Tedy takového literálu, který nabývá hodnoty $2$.

Logická funkce, jenž pro~všechna $x$ je $f(x)= 1$, se nazývá \textbf{tautologie}. Naopak funkce, jenž pro všechna $x$ je
$f(x) = 0$, se nazývá \textbf{kontradikce}. Pro tautologii tak platí, že \linebreak $\onset = \onset \cup \dcset \cup
\offset$, a naopak pro~kontradikci platí, že $\offset = \onset \cup \dcset \cup \offset$.

Mezi operace nad termy, které je třeba popsat, patří \textbf{průnik} dvou termů. Průnik termů \tname{t} a \tname{u} bude
značen $\tname{t} \cap \tname{u}$. Výpočet se provádí pro~každý literál zvlášť a řídí následujícími pravidly
\begin{displaymath}
  \begin{array}{cc}
    \begin{array}{cc|ccc}
      & & & \tname{u}_j & \\ 
      & \cap & 0 & 1 & 2 \\ \hline
      & 0 & 0 & \emptyset & 0 \\
      \tname{t}_j & 1 & \emptyset & 1 & 1 \\
      & 2 & 0 & 1 & 2 \\
    \end{array}\;,& \;\; j \in  \{1,\ldots,n\} \\
  \end{array}
\end{displaymath}
Pokud některý z~literálů neexistuje, je produkt prázdný. V~opačném případě je výsledkem nový term. Někdy bude uváděn
průnik termu a pokrytí, tedy $\term \cap \cover$. Výsledkem této operace je nové pokrytí složené z~průniku každého termu
z~\cover{} s termem \term{}. Počet neexistující literálů bývá nazýván vzdáleností dvou termů a pro termy \tname{t} a
\tname{u} se značí jako $\delta(\tname{t},\tname{u})$. 

Další důležitou operací je \textbf{konsensus}. Konsensus \tname{e} termů \tname{t} a \tname{u} je značen jako $\tname{e}
= \tname{t} \odot \tname{u}$. Term $\tname{e}$ se určí na základě následujících pravidel
\begin{displaymath}
  \tname{e} = \left\{ 
    \begin{array}{c@{\quad:\quad}ll}
      \tname{t} \cap \tname{u} &  \delta(\tname{t},\tname{u}) = 0 \\
      \emptyset & \delta(\tname{t},\tname{u}) \ge 2
    \end{array} \right.
\end{displaymath}
pokud je $\delta(\tname{t},\tname{u}) = 1$, pak se každý literál určí jako
\begin{displaymath}
  \tname{e}_j = \left\{ 
    \begin{array}{c@{\quad:\quad}ll}
      2 & \tname{t}_j \cap \tname{u}_j = \emptyset \\
      \tname{t}_j \cap \tname{u}_j &  \tname{t}_j \cap \tname{u}_j \not= \emptyset
    \end{array} \right.
\end{displaymath}
kde $j \in \{1,\ldots,n\}$.


Logické funkce lze zapsat několika způsoby. Asi nejpřehlednější možný způsob představuje \textbf{pravdivostní
  tabulka}, která vypisuje všechny možné kombinace proměnných a výstupní hodnotu daných kombinací. Například funkci
o~třech proměnných znázorňuje pravdivostní tabulka zobrazená v~Tabulce \ref{fig:truth-table}.  \newpage

\begin{table}[hbt]
  \center
  \begin{tabular}{ccc||c}
    $x_1$ & $x_2$ & $x_3$ & $y$ \\
    \hline
    $0$ & $0$ & $0$ & $1$ \\
    $0$ & $0$ & $1$ & $2$ \\
    $0$ & $1$ & $0$ & $2$ \\
    $0$ & $1$ & $1$ & $0$ \\
    $1$ & $0$ & $0$ & $1$ \\
    $1$ & $0$ & $1$ & $0$ \\
    $1$ & $1$ & $0$ & $1$ \\
    $1$ & $1$ & $1$ & $0$ \\
  \end{tabular}
  \caption{Pravdivostní tabulka}
  \label{fig:truth-table}
\end{table}


Pravděpodobně nejčastějším způsobem zápisu je \textbf{algebraický tvar}. V~něm se používají dvě formy zápisu. První,
a~také používanější, je \textbf{DNF} (disjunktivní normální forma)\footnote{V angličtině Sum of Products}. Jedná se o
součet součinových termů. Příkladem může být funkce 
\begin{displaymath}
  f(x_1,x_2,x_3) \equiv \ol{x}_1\ol{x}_2\ol{x}_3 + x_1\ol{x}_2\ol{x}_3 + x_1x_2\ol{x}_3 + \ol{x}_1\ol{x}_2x_3 +
  x_1\ol{x}_2x_3 
\end{displaymath}
kde čára nad~$x_j$ značí negovanou hodnotu literálu, tedy $\ol{x}_j = 0$ a obráceně $x_j = 1$. Druhou formou je
\textbf{KNF} (konjunktivní normální forma)\footnote{V angličtině Product of Sums}. Jedná se součin součtových termů. Obě
formy lze vzájemně převádět, přičemž lze využít De~Morganových zákonů, které říkají, že 
\begin{displaymath}
  \ol{x_1x_2} = \ol{x}_1 + \ol{x}_2
\end{displaymath}
Předešlý příklad DNF by se tedy v~KNF zapsal jako
\begin{displaymath}
  f(x_1,x_2,x_3) \equiv (x_1 + \ol{x}_2 + x_3)(x_1 + \ol{x}_2 + \ol{x}_3)(\ol{x}_1 + \ol{x}_2 + \ol{x}_3)
\end{displaymath}

V~Obou předešlých příkladech byly funkce zapsány v~úplné formě. To znamená, že v~každém termu byly zastoupeny všechny
literály. V~DNF se takový term označuje \textbf{minterm} a v~KNF \textbf{maxterm}. Po~provedení minimalizace mohou být
některé termy expandovány a~počet literálů se tak v~daném termu sníží. Minimalizovaná forma funkce z~předešlého příkladu
vypadá v~DNF následovně 
\begin{displaymath}
  f(x_1,x_2,x_3) \equiv \ol{x}_2 + x_1\ol{x}_3
\end{displaymath}
a v~KNF následovně
\begin{displaymath}
  f(x_1,x_2,x_3) \equiv (x_1 + \ol{x}_2)(\ol{x}_2 + \ol{x}_3)
\end{displaymath}
V dalších sekcích se bude často hovořit o~mintermech. Je třeba si uvědomit, že vše by platilo obdobně i pro~maxtermy, i
když o~nich nebude zmínka.

Před uvedením dalšího možného zápisu je třeba poznamenat, že také mintermy a maxtermy lze zapsat několika
způsoby. Prvním je \textbf{algebraický} tvar, který je uveden výše. Dále je možný ještě \textbf{binární} a
\textbf{dekadický} zápis. Například všechny tři níže uvedené zápisy označují tentýž minterm
\begin{displaymath}
  x_1\ol{x}_2\ol{x}_3 \equiv 100 \equiv 4
\end{displaymath}
Stejné by to bylo i u~maxtermu, až na rozdílný algebraický zápis, který by byl $(\ol{x}_1 + x_2 + x_3)$.

Dalším typem zápisu funkce je tzv. \textbf{výčtový zápis}, který se uplatní v~dekadickém zápis mintermu
(resp. maxtermu). Znovu je třeba rozlišit, zda se jedná o~DNF či o~KNF. Pro~DNF se výčet zapisuje jako suma všech
mintermů z~\onset{} plus suma všech mintermů z~\dcset{}. Mintermy jsou zapisovány v~už zmíněném dekadickém
tvaru. Pro~přehlednost je vhodné obě sumy odlišit indexem, který zdůrazní, o~jakou sumu se jedná. Pokud by například
pro~funkci o~třech proměnných bylo $\onset = \{\ol{x}_1\ol{x}_2\ol{x}_3, x_1\ol{x}_2\ol{x}_3, x_1x_2\ol{x}_3\}$ a
$\dcset = \{\ol{x}_1\ol{x}_2x_3 + x_1\ol{x}_2x_3\}$, zapsal by se výčet následovně
\begin{displaymath}
  f(x_1,x_2,x_3) \equiv \fsum(0,4,6) + \dsum(1,2)
\end{displaymath}
V případě KNF se výčet zapisuje jako produkt všech maxtermů z~\offset{} krát produkt všech maxtermů
z~\dcset{}. Po~vypočítání $\offset = \{\ol{x}_1x_2x_3, x_1\ol{x}_2x_3, x_1x_2x_3\}$ jako komplement $\onset \cup \dcset$
z~předchozího příkladu bude zápis funkce vypadat následovně
\begin{displaymath}
  f(x_1,x_2,x_3) \equiv \rprod(3,5,7) \cdot \dprod(1,2)
\end{displaymath}    

Posledním zápisem logické funkce, který zde bude zmíněn je \textbf{maticový zápis}. Ten bude často používán především
při~popisu algoritmů Espressa. Je proto omezen pouze na~termy v~DNF. Pokrytí \cover{} se zapíše do~matice \mcover{},
jejíž počet řádků odpovídá počtu termů v~pokrytí \cover{} a jejíž počet sloupců odpovídá počtu proměnných. Hodnoty
v~matici jsou pak určeny podle následujícího pravidla
\begin{displaymath}
  \mcover{}_{i,j} =  \left\{ 
    \begin{array}{r@{\quad:\quad}ll}
      0 & \term_j^i = 0 & \mbox{\itshape ($x_j$ se objeví v $i$-tém termu v negované hodnotě)} \\
      1 & \term_j^i = 1 & \mbox{\itshape ($x_j$ se objeví v $i$-tém termu)}  \\
      2 & \term_j^i = 2 & \mbox{\itshape ($x_j$ se neobjeví v $i$-tém termu)} 
    \end{array} \right.
\end{displaymath}
Například algebraický zápis funkce
\begin{displaymath}
  f \equiv \ol{x}_4 + x_1\ol{x}_2 +  x_1\ol{x}_3 +  \ol{x}_1x_2x_3
\end{displaymath}
by v~maticovém tvaru vypadal následovně
\begin{displaymath}
  \mcover = 
  \bmat{4}
  2 & 2 & 2 & 0 \\
  1 & 0 & 2 & 2 \\
  1 & 2 & 0 & 2 \\
  0 & 1 & 1 & 2 \\
  \emat
\end{displaymath}

Pro další text je třeba zmínit důležité rozdělení termů. Pokud je dána logická funkce $f = (\onset,\dcset,\offset)$
v~DNF, tak \textbf{implikant} funkce $f$ je každý term, které má prázdný průnik se~všemi termy
z~\offset{}. \textbf{Přímý implikant} je pak takový implikant, který není pokryt žádným jiným implikantem. Pokud by $f$
byla v~KNF, měl by implikant funkce $f$ prázdný průnik se~všemi termy z~\onset. 

Na závěr této sekce bude popsána speciální třída logických funkcí, které se hodně využívá v~Espressu. Jedná se
o~tzv. \textbf{unátní funkce}. Pro jednohodnotové výstupní funkce je jejich popis velmi jednoduchý. Funkce, která je
daná minimálním pokrytím \cover{}, je unátní v~proměnné $x_j$ pokud platí, že $j$-tý sloupec v~\mcover{} neobsahuje
žádnou nulu (taková funkce se nazývá monotonně rostoucí v~$x_j$) nebo žádnou jedničku (taková funkce se nazývá monotonně
klesající v~$x_j$). Unátní funkce je pak taková funkce, která je unátní ve všech svých proměnných. Jinými slovy to
znamená, že průnik všech termů v~\cover{} je neprázdný. Příkladem takové funkce, kterou tvoří minimální pokrytí
\cover{}, je například 
\begin{displaymath}
  \mcover = 
  \bmat{3}
  1 & 2 & 1 \\
  1 & 0 & 2 \\
  \emat
\end{displaymath}

Pokud funkce není unátní, tak lze najít tzv. \textbf{binátní proměnnou}. Ta se zjistí tak, že se nejdříve vypočítá
pro~každý sloupec v~\mcover{} počet různých dvojic $[0_{i_1},1_{i_2}]$, kde $i_1$ a $i_2$ jsou čísla řádků a platí že
$i_1 \not= i_2$. Pak sloupec s~největším počtem těchto dvojic je označen jako $j$-tý sloupec a nejvíce binátní proměnnou
je $x_j$.


\vspace{4ex}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  History

\section{Trocha Historie}
\label{sec:history}

Základy pro syntézu logických obvodů položil George Boole \cite{boole}. Stěžejní byla zejména jeho práce \emph{The
  Laws of  Thought}\footnote{Celým názvem \textit{An Investigation of the Laws of Thought on Which are Founded
    the~Mathematical Theories of~Logic and~probabilities}} z~roku 1854 \cite{boole-laws}, v níž definoval novou algebru,
která po~něm zároveň byla pojmenována jako Booleova algebra. V roce 1938 pak Claude Shannon ukázal, že dvouhodnotová
Booleova algebra může popsat operace v~kombinačních obvodech. S~jejich postupným rozvojem nabralo toto odvětví
matematiky na~důležitosti. Pozornost byla zaměřena zejména na~minimalizace logických funkcích, protože umožnily použití
menšího počtu hradel a~tím i ušetření finančních prostředků a zrychlení obvodu. S~prvním řešením přišel Mourice Karnaugh
\cite{karnaugh} roku 1953. Ten za~použití Veitcheho diagramů vytvořil speciální mapu, jež umožňovala vizuální
minimalizaci. Dostala jméno Karnaughova mapa \cite{wiki-kmap}. Její přehlednost byla ale špatná už pro~šest proměnných,
a tak bylo třeba najít nějaké lepší řešení. S~tím přišli roku 1956 pánové Willard Van Orman Quine \cite{quine} a Edward
J. McCluskey \cite{mccluskey}. Algoritmus, který vymysleli, byl po nich pojmenován a dostal tak jméno algoritmus
Quine--McCluskey \cite{wiki-qm}. Dlouhou dobu byl de~facto standardem. Jeho výhodou byla snadná implementace na~počítači
a výsledná optimální minimální funkce. Jednalo se tak o~exaktní algoritmus, což mělo i své nevýhody. Jeho složitost byla
totiž exponenciální a pro~více jak 15 proměnných byl prakticky nepoužitelný. S~masivním příchodem PLA zařízení v~70.
letech bylo třeba minimalizovat funkce,  které měly typicky kolem 30 proměnných. Začalo tak vznikat mnoho heuristik,
které se optimálnímu řešení blížily. Asi nejznámější z~nich je sada algoritmů s~názvem Espresso \cite{espresso}. To
vzniklo počátkem 80. let minulého století a~jeho autory jsou pánové Robert K. Brayton, Gary D. Hatchel, Curtis
T. McMullen a Alberto L. Sangiovanni-Vincentelli. Espresso navazovalo na heuristiku MINI \cite{mini} vzniklou
v~IBM. Jeho výsledky však byly mnohem lepší a navíc mělo rozšíření pro~minimalizaci funkcí s~více výstupními
hodnotami. Výzkum těchto funkcí vedl k~mnoha novým heuristikám. Postupem času se vývoj v~oblasti minimalizace logických
funkcí přenesl do~komerčních EDA (Electronic design automation) nástrojů \cite{wiki-eda}, které celý proces syntézy
automatizují. Mezi největší firmy vytvářející tyto nástroje patří například Synopsys \cite{synopsys} nebo Cadence
\cite{cadence}. 

\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  Boolean n-Cube

\section{Booleovská n-krychle}
\label{sec:n-cube}

\textbf{Booleovská $n$-krychle} značená \ncube{} slouží k vizuálnímu vyjádření logické funkce. Jedná se o~$n$-rozměrnou
krychli, jejíž vrcholy představují mintermy\footnote{Je uvažována pouze DNF. U~KNF je vše stejné až na to, že místo
  o~mintermy se jedná   o~maxtermy.} a hrany představují změnu jedné proměnné z~$0$~na~$1$ resp. z~$1$~na~$0$. Sousedící
mintermy se tedy liší v~jedné proměnné. Pokud by tedy n-krychle byla pokládána za~graf, jednalo by se o graf s~$2^n$
uzly a $n \cdot 2^{n-1}$ hranami, přičemž každý uzel má stupeň rovný $n$. Nejpřehlednější je $n$-krychle pro~$n \le 3$,
v níž se každá proměnná mění s~prostorovými souřadnicemi. Tedy například $x_3$ se mění s~osou \texttt{x}, $x_2$ s~osou
\texttt{y} a~$x_1$ s~osou \texttt{z}. Obrázek \ref{fig:ncube} zobrazuje \ncube[3] pro~funkci
\begin{displaymath}
  f(x_1,x_2,x_3) \equiv \fsum(0,2,5) + \dsum(1,4)
\end{displaymath}
Je nutné poznamenat, že mintermy z~\onset{} jsou zobrazen \red{červenou barvou}, mintermy z~\offset{} \blue{modrou
  barvou} a mintermy z~\dcset{} \magenta{purpurovou barvou}.

\setlength{\unitlength}{1pt}
\begin{figure}[hbt]
  \centering
  \begin{picture}(200,200)
    \put(30,  30){\red{\circle*{8}}}
    \put(30, 130){\red{\circle*{8}}}
    \put(130,130){\blue{\circle*{8}}}
    \put(130, 30){\magenta{\circle*{8}}}
    \put(71,  62){\magenta{\circle*{8}}}
    \put(71, 162){\blue{\circle*{8}}}
    \put(171,162){\blue{\circle*{8}}}
    \put(171, 62){\red{\circle*{8}}}

    \put(33,  33){\line(4,3){35}}
    \put(133, 33){\line(4,3){35}}
    \put(33, 133){\line(4,3){35}}
    \put(133,133){\line(4,3){35}}

    \put(34,  30){\line(1,0){92}}
    \put(34, 130){\line(1,0){92}}    
    \put(75,  62){\line(1,0){92}}
    \put(75, 162){\line(1,0){92}}

    \put(30,  34){\line(0,1){92}}
    \put(130, 34){\line(0,1){92}}
    \put(71,  66){\line(0,1){92}}
    \put(171, 66){\line(0,1){92}}
    
    \thicklines
    \put(45, 15){\vector(1,0){65}}
    \put(15, 45){\vector(0,1){65}}
    \put(145, 25){\vector(4,3){32}}

    \put(70, 5){$\mathbf{x_3}$}
    \put(0, 74){$\mathbf{x_2}$}
    \put(162, 28){$\mathbf{x_1}$}
    
    \put(8, 17){$\mathbf{000}$}
    \put(174, 168){$\mathbf{111}$}
    
    
  \end{picture}
  \caption{Booleovská $n$-krychle pro tři proměnné}
  \label{fig:ncube}
\end{figure}

Částečně přehledná je ještě krychle pro čtyři proměnné, která se kreslí jako menší \ncube[3]{} ve~větší \ncube[3]{}.
přičemž jejich stejné mintermy jsou propojeny hranou, která představuje změnu čtvrté proměnné. Krychle pro~větší počet
proměnných se velice obtížně kreslí a je zároveň i velmi nepřehledná.

Term, který má počet literálů $m$ je tvořen podkrychlí \ncube[m]{}, přičemž $\ncube[m]{} \subseteq \ncube$. Tato
podkrychle pokrývá všechny mintermy, které daný term implikuje.


\newpage

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  Karnaugh Map

\section{Karnaughova mapa}
\label{sec:kmap}

\textbf{Karnaughova mapa} nebo zkráceně pouze K-mapa je v~podstatě maticový zápis výstupních hodnot všech mintermů
kompletně specifikované logické funkce. Tedy jakýsi přepis pravdivostní tabulky (konkrétně jejího sloupce s~výstupními
hodnotami) do~matice.  V~ní jsou mintermy uspořádány po~řádcích podle~Grayova kódu. 

Tabulka \ref{tab:kmap-grey} ukazuje strukturu K-mapy. Místo výstupních hodnot jsou v~ní uvedeny pozice mintermů.
Pro~přehlednost jsou její  sloupce a řádky číslovány od~nuly. Nultý sloupec a řádek slouží k~popisu toho, jakých hodnot
nabývají jednotlivé proměnné. Zde byl zvolen binární popis\footnote{Dalším popisem bývají tzv.~negační čáry, kde hodnota
  $0$ pro~danou proměnnou je znázorněna čárou a~hodnota $1$ je znázorněna vynecháním čáry.}, z~něhož je dobře patrné, že
proměnné jsou uspořádány podle Grayova kódu. Z toho vyplývá, že i jednotlivé mintermy jsou uspořádány podle Grayova
kódu, jak ukazují hodnoty v tabulce, které uvádějí dekadický zápis mintermu, tedy jeho pozici v~pravdivostní
tabulce. Hlavní výhodou tohoto rozmístění je, že spolu sousedí vždy dva mintermy, jenž se liší pouze v~jedné
proměnné. Sousednost však platí i~mezi některými mintermy, které nejsou přímo vedle sebe v~mapě. Kolik sousedů má každý
minterm závisí na počtu proměnných dané funkce. Například K-mapu pro~funkci o~třech proměnných si lze představit jako
válec, protože spolu sousedí proměnné v~prvním a posledním sloupci. K-mapa o~čtyřech proměnný tvoří torus
\cite{wiki-torus}, tedy útvar připomínající pneumatiku. Sousedící jsou zde i první a poslední řádek. U~většího počtu
proměnných se situace stává ještě komplikovanější. Pro~více než 6 proměnných už nemá smysl K-mapu kreslit, protože je
velmi nepřehledná.

\begin{table}[hbt]
  \centering
  \begin{tabular}{|c||c|c|c|c|}
    \hline
    $x_1x_2\symbol{92}x_3x_4$ & 00 & 01 & 11 & 10 \\
    \hline \hline
    00 & 0 & 1 & 3 & 2 \\ \hline
    01 & 4 & 5 & 7 & 6 \\ \hline
    11 & 12 & 13 & 15 & 14 \\ \hline
    10 & 8 & 9 & 11 & 10 \\ \hline
  \end{tabular}
  \caption{Rozmístění mintermů v Karnaughově mapě pro čtyři proměnné}
  \label{tab:kmap-grey}
\end{table}

Výhodou výše zmíněné sousednosti je možnost přehledně zobrazit termy s menším počtem literálů než je počet
proměnných. Ty pokrývají v K-mapě skupiny sousedních mintermů. Tyto skupiny se vždy rozkládají na ploše, jejíž šířka a
výška musí být mocninou čísla $2$, přičemž jednotkou je samozřejmě políčko v~K-mapě. Z toho vyplývá, že lze jednoduše
určit minimální pokrytí pro danou funkci tak, že se vyhledají největší možné plochy pokrývající mintermy s~výstupní
hodnotou 1 nebo 2 (v~případě KNF se pokrývají maxtermy s výstupní hodnotou 0 nebo 2).

Tabulka \ref{tab:kmap-prime} ukazuje mapu funkce
\begin{displaymath}
  f(x_1,x_2,x_3,x_4) \equiv \fsum(4,5,6,7,15) + \dsum(3,13)
\end{displaymath}
a zvýrazňuje v~ní přímý implikant $x_2x_4$. Druhým přímým implikantem je $\ol{x}_1x_2$, který rozkládá přes všechna
políčka ve~druhém řádku Tabulky. Výsledná minimální funkce je tedy
\begin{displaymath}
  f(x_1,x_2,x_3,x_4) \equiv x_2x_4 + \ol{x}_1x_2
\end{displaymath}

\begin{table}[hbt]
  \centering
  \begin{tabular}{|c||c|c|c|c|}
    \hline
    $x_1x_2\symbol{92}x_3x_4$ & $00$ & $01$ & $11$ & $10$ \\
    \hline \hline
    $00$ & $0$ & $0$ & $2$ & $0$ \\ \hline
    $01$ & $1$ & \textcolor{red}{$1$} & \textcolor{red}{$1$} & $1$ \\ \hline
    $11$ & $0$ & \textcolor{red}{$2$} & \textcolor{red}{$1$} & $0$ \\ \hline
    $10$ & $0$ & $0$ & $0$ & $0$ \\ \hline
  \end{tabular}
  \caption{Karnaughova mapa se zvýrazněním termu  $x_2x_4$}
  \label{tab:kmap-prime}
\end{table}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  Quine-McCluskey

\section{Quine--McCluskey}
\label{sec:qm}

Algoritmus \textbf{Quine--McCluskey} je jedním z prvních algoritmů pro~minimalizaci logických funkcí vhodným
k~implementaci na~počítači. Skládá se ze~dvou kroků:
\begin{enumerate}
\item Jsou nalezeny všechny přímé implikanty.
\item Z nalezených přímých implikantů je zjištěno minimální pokrytí.
\end{enumerate}
V~závislosti na~použité metodě pro~hledání nejmenšího pokrytí se jedná buď o exaktní algoritmus nebo o~heuristiku. 

V prvním kroku jsou tedy hledány všechny přímé implikanty. Nejprve je třeba získat všechny mintermy (zatím je uvažována
pouze DNF) z~pokrytí $\onset \cup \dcset$. Poté se vytvoří jakási matice seznamů. V~ní jsou mintermy rozřazeny v~řádcích
podle počtu jedniček a ve~sloupcích podle počtu literálů. V~každém seznamu jsou tedy termy se~stejným počtem jedniček a
stejným počtem literálů. Na začátku je samozřejmě zaplněn jen sloupec s~počtem literálů rovným počtu proměnných. Po~této
inicializační fázi následuje kombinování termů. Kombinují se vždy pouze seznamy termů, které jsou ve stejném sloupci
a~jejich řádky spolu sousedí. Tedy termy, jejichž počet jedniček se liší o~hodnotu jedna. Kombinování znamená, že každý
term z~jednoho seznamu vytvoří dvojici s~každým termem z~druhého seznamu a z~této dvojice se udělá konsensus. Pokud je
neprázdný, tak je zřejmé, že bude mít počet literálu o~jedna menší. Vloží se tedy do~následujícího sloupce na stejný
řádek jako je term s~menším počtem jedniček z~kombinované dvojice. Když se takto zkombinují všechny sousední řádky,
pokračuje se kombinováním řádku ve~sloupci pro termy s~o~jedna nižším počtem literálů. Hledání přímých implikantů končí,
když už není co kombinovat. Během průběhu algoritmu se udržuje speciální seznam se~všemi termy. Pokud při
kombinování nastane, že $\tname{e} = \tname{t} \odot \tname{u} \not= \emptyset$, tak jsou termy \tname{t} a \tname{u}
z~tohoto seznamu odstraněny a~je do~něj přidán term \tname{e}. Na konci tak zbudou pouze přímé implikanty. Těch muže být
velký počet. Dá se dokázat, že horní hranice je $O(\frac{3^n}{n})$, kde $n$ je počet proměnných.

Po~získání přímých implikantů následuje druhá část algoritmu. V~ní se nejprve vytvoří tabulka pokrytí mezi nalezenými
přímými implikanty a původními mintermy, které náleží do~\onset{}. Přímé implikanty, které pokrývají jako jediní
některý minterm, se nazývají nespornými přímými implikanty a musí být tedy ve~výsledném minimálním pokrytí. Ze~zbylých
přímých implikantů je nutné najít minimální množinu, která bude tvořit ekvivalentní pokrytí. Jedná se o~problém hledání
nejmenšího pokrytí \cite{wiki-cover}, který je NP úplný  \cite{wiki-np-complete}. Ten lze řešit buď pomocí zpětného
prohledávání (Backtracking \cite{wiki-backtracking}) nebo použít heuristiku, která se optimálnímu řešení blíží. Zde se
nejvíce nabízí vybrání termu, který pokrývá nejvíce doposud nepokrytých mintermů a poté ho vložit do~minimálního
prokrytí. To opakovat, dokud nejsou pokryty všechny mintermy.

Pro příklad funkce 
\begin{displaymath}
   f(x_1,x_2,x_3,x_4) \equiv \fsum(3,5,6,8,9,11,15) + \dsum(4,7,12)
\end{displaymath}
má průběh zobrazený v Tabulce \ref{tab:qm-prime}. K~ní je nutné poznamenat, že místo hodnoty 2 pro chybějící literál je
použita pomlčka. U~přímých implikantů je uvedena hvězdička. Tabulka pokrytí je zobrazena v Tabulce
\ref{tab:qm-cover}. V~ní jsou nesporné přímé implikanty označeni hvězdičkou.

\begin{table}[hbt]
  \centering
  \begin{tabular}{|l||ll|ll|ll|}
    \hline
    Počet jedniček &\multicolumn{2}{|c}{4 literály} &\multicolumn{2}{|c}{3 literály} &\multicolumn{2}{|c|}{2 literály}\\ 
    \hline\hline
    1 & m4  & 0100 & m(4,5)   & 010-  & m(4,5,6,7)   & 01-\--* \\
      & m8  & 1000 & m(4,6)   & 01-0  &              &         \\
      &     &      & m(4,12)  & -100* &              &         \\
      &     &      & m(8,9)   & 100-* &              &         \\
      &     &      & m(8,12)  & 1-00* &              &         \\
    \hline
    2 & m3  & 0011 & m(3,7)   & 0-11  & m(3,7,11,15) & -\--11* \\
      & m5  & 0101 & m(3,11)  & -011  &              &         \\
      & m6  & 0110 & m(5,7)   & 01-1  &              &         \\
      & m9  & 1001 & m(6,7)   & 011-  &              &         \\
      & m12 & 1100 & m(9,11)  & 10-1* &              &         \\
    \hline
    3 & m7  & 0111 & m(7,15)  & -111  &              &         \\
      & m11 & 1011 & m(11,15) & 1-11  &              &         \\
    \hline
    4 & m15 & 1111 &          &       &              &         \\
    \hline
  \end{tabular}
  \caption{Quine--McCluskey -- Hledání přímých implikantů}
  \label{tab:qm-prime}
\end{table}

\begin{table}[hbt]
  \centering
  \begin{tabular}{|l|*{7}{c|}}
    \hline
                  & m3 & m5 & m6 & m8 & m9 & m11 & m15\\ \hline
    m(3,7,11,15)* & $\times$ &   &   &   &   & $\times$ & $\times$ \\ \hline 
    m(4,5,6,7)*   &   & $\times$ & $\times$ &   &   &   &   \\ \hline
    m(4,12)       &   &   &   &   &   &   &   \\ \hline
    m(8,9)        &   &   &   & $\times$ & $\times$ &   &   \\ \hline
    m(8,12)       &   &   &   & $\times$ &   &   &   \\ \hline
    m(9,11)       &   &   &   &   & $\times$ & $\times$ &   \\ \hline
    
  \end{tabular}
  \caption{Quine--McCluskey -- Tabulka pokrytí}
  \label{tab:qm-cover}
\end{table}

Při~hledání pokrytí v~Tabulce \ref{tab:qm-cover} se nejprve odstraní nesporné přímé implikanty, kterými jsou
m(3,7,11,15) a m(4,5,6,7), a s~nimi všechny pokryté mintermy. Navíc se odstraní i term m(4,12), protože nepokrývá žádné
mintermy z~\onset{}. Zbývá tak pokrýt pouze mintermy m8 a m9. Ze~zbylých přímých implikantů se proto odstraní m(8,9),
protože je oba pokrývá. Výsledná minimální funkce je tedy
\begin{displaymath}
   f(x_1,x_2,x_3,x_4) \equiv  \ol{x}_1x_2 + x_3x_4 + x_1\ol{x}_2\ol{x}_3
\end{displaymath}

Celý předešlý popis se týká funkce v~DNF. Pro~KNF by vše bylo stejné, až na rozdíl, že by se jednalo o~maxtermy
a~hodnoty by byly rozřazeny do~řádků podle počtu nul.


\newpage
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  Espresso

\section{Espresso}
\label{sec:espresso}

Espresso je sada algoritmů pro~minimalizaci logických funkcí. Jedná se o heuristiku, což znamená, že výsledná
minimalizovaná funkce nemusí být optimální. Výhodou ale je, že doba minimalizace je mnohem kratší.

Minimalizace se skládá z~několika procedur, které se opakovaně provádějí v~hlavní smyčce algoritmu. Následující
podsekce podrobně popisují nejdůležitější procedury. Nejprve je však uvedena hlavní smyčka algoritmu.


%%%%%%%% MAIN LOOP

\subsection{Hlavní smyčka}
\label{sec:main-loop}
Tato sekce popisuje celý průběh algoritmu Espresso. Tedy v~jakém pořadí jsou volány jednotlivé procedury. Vše je pro~lepší
pochopení trochu zjednodušeno. Navíc je úplně vynechána procedura \eproc{MAKE-SPARSE}, která u~jednovýstupových funkcí
nemá význam. Celý průběh je zapsán v~pseudokódu na Obrázku \ref{fig:espresso}. 

Je třeba poznamenat, že procedura \texttt{COST} je tzv. cenová funkce pro~\onset{}. Cena je dána na~prvním místě počtem
termů a na druhém celkovým počtem všech literálů. 


\begin{figure}[hbt]
  \ttfamily\footnotesize
  \begin{tabular}{ll}
  ESPRESSO(\onset,\dcset) \{\\
  \mbox{\ \ }\offset{} $\gets$ COMPLEMENT(\onset{},\dcset{}) & // Vypočte komplement a uloží ho do~\offset{}.\\
  \mbox{\ \ }LOOP1:\\
  \mbox{\ \ \ \ }$c_1 \gets c_2 \gets c_3 \gets c_4 \gets$ COST(\onset) & // Inicializuje ceny.\\
  \mbox{\ \ \ \ }$\onset \gets$ EXPAND(\onset,\offset) & // Najde přímé implikanty. \\
  \mbox{\ \ \ \ }if (first-pass) & // V případě prvního průchodu \\
  \mbox{\ \ \ \ \ \ }(\onset,\dcset,$\mathcal{E}$) $\gets$ ESSENTIAL-PRIMES(\onset,\dcset) & // separuje nesporné přímé
  implikanty. \\
  \mbox{\ \ \ \ }if ($c_1 =$ COST(\onset)) & // Pokud se cena nezměnila \\
  \mbox{\ \ \ \ \ \ }goto OUT & // skočí na poslední fázi smyčky \\
  \mbox{\ \ \ \ }$c_1 \gets $ COST(\onset) & // jinak cenu uloží.\\
  \mbox{\ \ \ \ }$\onset \gets$ IRREDUNDANT(\onset,\dcset) & // Najde minimální pokrytí. \\
  \mbox{\ \ \ \ }if ($c_2 =$ COST(\onset)) \\
  \mbox{\ \ \ \ \ \ }goto OUT  \\
  \mbox{\ \ \ \ }$c_2 \gets $ COST(\onset) \\
  \mbox{\ \ }LOOP2:\\
  \mbox{\ \ \ \ }$\onset \gets$ REDUCE(\onset,\dcset) & // Dostává řešení z~lokálního optima.  \\
  \mbox{\ \ \ \ }if ($c_3 =$ COST(\onset)) \\
  \mbox{\ \ \ \ \ \ }goto OUT  \\
  \mbox{\ \ \ \ }$c_3 \gets $ COST(\onset) \\
  \mbox{\ \ }OUT:\\
  \mbox{\ \ \ \ }$c \gets$ COST(\onset) \\
  \mbox{\ \ \ \ }if ($c_4 = c$) \\
  \mbox{\ \ \ \ \ \ }goto QUIT  \\
  \mbox{\ \ \ \ }$\onset \gets$ LAST-GASP(\onset,\dcset,\offset) & // Poslední pokus o vylepšení řešení.\\
  \mbox{\ \ \ \ }if ($c =$ COST(\onset)) & // Pokud se cena během LAST-GASP nezměnila \\
  \mbox{\ \ \ \ \ \ }goto QUIT  & // cyklus je ukončen \\
  \mbox{\ \ \ \ }goto LOOP1 & // jinak skočí zpět na začátek. \\ 
  \mbox{\ \ }QUIT:\\
  \mbox{\ \ \ \ }$\onset \gets \onset \cup \mathcal{E}$ & // Vrátí zpět nesporné přímé implikanty. \\
  \mbox{\ \ \ \ }return \onset \\
  \}\\
  \end{tabular}
  \rmfamily
  \caption{Hlavní smyčka Espressa}
  \label{fig:espresso}
\end{figure}


%Hlavní smyčka je dvouúrovňová. Obsahuje tedy dva vnořené cykly. Vnější nebo-li hlavní cyklus začíná postupným
%provedením procedur \eproc{EXPAND}, \eproc{ESSENTIAL-PRIMES}, která se ale provádí pouze v~prvním kroku, a
%\eproc{IRREDUNDANT}. Pokud po~jejich vykonání cena zůstala stejná od~posledního , je cyklus ukončen. V~opačném případě
%se začne provádět vnitřní cyklus, který začíná procedurou \eproc{REDUCE}. Znovu se testuje cena, zda byla během
%\eproc{REDUCUE} změněna. Pokud ne, tak je vnitřní cyklus ukončen. Jinak jsou provedeny  procedury \eproc{EXPAND} a
%\eproc{IRREDUNDANT}. Vše se dělá tak dlouho, dokud se cena neustálí. Po skončení vnitřního cyklu se ještě zavolá
%procedura \eproc{LAST-GASP}. Pokud po~jejím vykonání je cena stejná, hlavní cyklus končí. V~opačném případě se
%pokračuje znovu od~začátku. Po skončení hlavního cyklu jsou připojeny zpět nesporné přímé implikanty a je vráceno
%minimální pokrytí \onset{}.

%%%%%%%% COFACTOR

\subsection{COFACTOR}
\label{sec:cofactor}

\eproc{COFACTOR} není přímo procedurou Espressa. Je to spíše metoda pro~výpočet kofaktoru. Nejedná se však přímo
o~kofaktor známý z~lineární algebry pro~výpočet determinantu \cite{wiki-cof}, i~když jeho význam je obdobný. Je to
jakýsi algebraický doplněk termu \cofterm{} v daném pokrytí \cover{}. Výsledné pokrytí se označuje jako \cofcover{}.
Kofaktor se počítá pro~každý term v~\cover{} zvlášť podle následujícího pravidla
\begin{displaymath}
  (\term_\cofterm^i)_j = \left\{ 
    \begin{array}{c@{\quad:\quad}l}
      \emptyset &  \term_j^i \cap \cofterm_j = \emptyset\\
      2 & (p_j = 0) \vee (p_j = 1) \\
      \term_j^k & p_j = 2
    \end{array} \right.
\end{displaymath}

Nejlépe vše bude vidět na~příkladu. Pokud je dáno pokrytí \cover{}, jehož zápis v maticovém tvaru vypadá následovně 
\begin{displaymath}
  \mcover =
  \bmat{4}
  1 & 1 & 0 & 2 \\
  0 & 1 & 2 & 0 \\
  1 & 1 & 1 & 1 \\
  \emat
\end{displaymath}
tak kofaktor \cofcover{}, kde 
\begin{displaymath}
  \mcover[\cofterm] = \bmat{4} 1 & 1 & 2 & 2 \emat
\end{displaymath}
je
\begin{displaymath}
  \mcover[\cofcover] = 
  \bmat{4}
  2 & 2 & 0 & 2 \\
  2 & 2 & 1 & 1 \\
  \emat
\end{displaymath}

Speciální význam má kofaktor pro~jednu proměnnou. Ten se značí pro~$i$-tou proměnou jako $\cover_{x_i}$, resp.
$\cover_{\ol{x}_i}$ pro negovanou hodnotu. Výpočet $\cover_{x_3}$, resp. $\cover_{\ol{x}_3}$, je stejný, jako výpočet
\cofcover{} pro  
\begin{displaymath}
  \mcover[\cofterm] = \bmat{4} 2 & 2 & 1 & 2 \emat
\end{displaymath}
resp.
\begin{displaymath}
  \mcover[\cofterm] = \bmat{4} 2 & 2 & 0 & 2 \emat
\end{displaymath}
Výsledek tedy je
\begin{displaymath}
  \begin{array}{cc}
    \mcover[\cover_{x_3}] = 
    \bmat{4}
    1 & 1 & 0 & 2 \\
    1 & 1 & 1 & 2 \\
    \emat ; &
    \mcover[\cover_{\ol{x}_3}] = 
    \bmat{4}
    1 & 1 & 0 & 2 \\
    0 & 1 & 2 & 2 \\
    \emat ;
  \end{array}
\end{displaymath}

\subsection{Shannonův rozklad}
\label{sec:shannon}

\textbf{Shannonův rozklad} stejně jako \eproc{COFACTOR} není procedurou Espressa.  Říká, že pro~jakoukoliv proměnou
platí, že 
\begin{displaymath}
  \cover = x_1\cover_{x_1} + \ol{x}_1\cover_{\ol{x}_1}
\end{displaymath}
To znamená, že obě strany rovnice jsou logicky ekvivalentní a že lze tedy funkci rekurzivně rozkládat. To se uplatní
například při~zjišťování tautologie, jak je popsáno v následující podsekci.

%%%%%%%% TAUTOLOGY

\subsection{TAUTOLOGY}
\label{sec:taut}

Zjišťování, zda je dané pokrytí tautologií, je v Espressu velmi časté. Hlavním důvodem je, že to umožňuje zjistit, zda je
určitý term pokryt daným pokrytím. Vše podstatné je uvedeno v následující větě\footnote{Její dokázání je mimo rozsah tohoto
  textu, zájemci jej mohou nalézt v \cite[str. 33]{espresso}}.

\newtheorem{theorem}{Věta}
\begin{theorem}
  Pokud platí, že pokrytí \cofcover{} je tautologie, tak pokrytí \cover{} pokrývá term \cofterm{}. 
\end{theorem}

Samotný dále popsaný algoritmus je velmi zjednodušen. Jedná o tzv. Vanilla Tautology, kde jsou vynechány testy unátnosti
a další rychlostní vylepšení. Jejich popis by si vyžadoval hlubší teoretické základy a to je mimo rozsah tohoto textu.

Pomocí Shannonova rozkladu se dá dokázat že platí následující věta 
\begin{theorem}
  Pokud pokrytí \cover{} je tautologie, tak musí být tautologie i $\cover_{x_i}$a  $\cover_{\ol{x}_i}$ pro libovolné
  \linebreak $i \in \{1,\ldots,n\}$
\end{theorem}

Tato věta umožňuje rekurzivní vykonávání algoritmus. Nejprve je však třeba vyhodnotit speciální případy. Ty lze
jednoduše určit z~\mcover{}, kde \cover{} je zkoumané pokrytí. Pokud v~\mcover{} je řádek obsahující samé dvojky, jedná
se o~tautologii. Pokud je v~\mcover{} sloupec se samými jedničkami nebo nulami o~tautologii se nejedná. To vyplývá
z~podmínky, že o~tautologii se nejedná v případě, že $\cover_{x_i}$ nebo $\cover_{\ol{x}_i}$ je prázdné. Pokud se
nejedná o~speciální případ, zavolá se algoritmus rekurzivně pro $\cover_{x_i}$ a $\cover_{\ol{x}_i}$. Pokud jedno z nich
není tautologie, tak není ani \cover{} tautologie. Proměnná $i$ se mění v každém patře rekurzivního
stromu. Nejjednodušeji se v prvním kroku nastaví na hodnotu $1$ a pak se postupně zvyšuje\footnote{Espresso využívá
  výběru nejvíce binátní   hodnoty. To má smysl, pokud je algoritmus rozšířen o~speciální vyhodnocení v případě unátního
  pokrytí.}. Příklad průběhu algoritmu pro~$\cover = \{x_1x_2\ol{x}_4, x_1x_2, x_4, \ol{x}_1\ol{x}_3\}$ ukazuje Obrázek
\ref{fig:taut}. Vzhledem k~tomu, že v~posledním potře zbylo pokrytí, kde je sloupec pouze s~jedničkou, tak pokrytí
\cover{} není tautologie.

\begin{figure}[hbt]
  \centering
  \begin{picture}(400,200)
    \put(20,160){\fbox{\shortstack{1 1 2 0\\1 1 2 2\\2 2 2 1\\0 2 0 2}}}
    \put(26,156){\vector(4,-1){160}}
    \put(26,156){\vector(0,-1){39}}
    
    \put(20,86){\fbox{\shortstack{2 1 2 0\\2 1 2 2\\2 2 2 1}}}
    \put(36,82){\vector(2,-1){52}}
    \put(36,82){\vector(0,-1){26}}    
    \put(186,96){\fbox{\shortstack{2 0 2 2\\2 2 0 2}}}
    \put(202,93){\vector(2,-1){74}}
    \put(202,93){\vector(0,-1){37}}
    
    \put(20,26){\fbox{\shortstack{2 2 2 0\\\textcolor{red}{2 2 2 2}\\2 2 2 1}}}
    \put(86,46){\fbox{\shortstack{2 2 2 \textcolor{red}{1}}}}

    \put(186,46){\fbox{\shortstack{2 2 \textcolor{red}{0} 2}}}
    \put(275,36){\fbox{\shortstack{\textcolor{red}{2 2 2 2}\\2 2 1 2}}}

    \put(14,137){$x_1$}
    \put(125,137){$\ol{x}_1$}
    \put(12,70){$x_1x_2$}
    \put(70,70){$x_1\ol{x}_2$}
    \put(178,70){$\ol{x}_1x_2$}
    \put(255,70){$\ol{x}_1\ol{x}_2$}
  \end{picture}
  \caption{Ukázka průběhu algoritmu \eproc{TAUTOLOGY}}
  \label{fig:taut}
\end{figure}


\newpage
%%%%%%%% EXPAND

\subsection{EXPAND}
\label{sec:expand}

Procedura \eproc{EXPAND} slouží k nalezení přímých implikantů. Toho je dosaženo tak, že se prochází přes~všechny termy
z~\onset{} a~každý je maximálně zvětšen, aby pokryl co nejvíce ostatních termů a počet jeho literálů byl co
nejmenší. Jedná se tedy v~podstatě o~hladový algoritmus v~němž je vážená funkce složena s~počtu pokrytých termů a~počtu 
literálů, u nichž má větší funkční hodnotu menší počet. Espresso používá heuristiku, která dává řešení blízké
optimu. Rychlost řešení je zde závislá na počátečním seřazení termů. Jako nejvýhodnější se ukazuje zpracovat nejdříve
termy, které jsou největší (mají nejmenší počet literálů).

Samotná expanze termu je prováděna pro~každý term, který nebyl ještě pokryt jiným termem. Nejprve se z~\offset{} a
expandovaného termu (dále označovaného jako \term{}) vytvoří tzv. blokovací matice (Blocking~matrix) \matname{B}. Ta je
vytvořena podle následujícího vzorce
\begin{displaymath}
  \matname{B}_{i,j} =  \left\{ 
    \begin{array}{r@{\quad:\quad}l}
      1 & ((\term_j = 1) \wedge (\offset_{i,j} = 0)) \vee ((\term_j = 0) \wedge (\offset_{i,j} = 1)) \\ 
      0 & \mbox{v ostatních případech}
    \end{array} \right.
\end{displaymath}
To znamená, že matice \matname{B} obsahuje jedničku na $i$-tém řádku a $j$-tém sloupci, pokud je zaručena disjunktnost 
$j$-té proměnné \term{} a $i$-tého termu z \offset{}. To zaručuje, že \term{} nebude pokrývat $i$-tý term z~\offset{}.
K~tomu aby byla zaručena úplná disjunktnost se~všemi termy z~\offset{} je třeba najít takové sloupcové pokrytí
\matname{B}, aby množina sloupců pokryla v každém řádku alespoň jednu jedničku. Tato množina sloupců se nazývá
Lowering~Set a dále bude označována jako \setname{L}. Název Lowering~Set značí, že každý $k$-tý literál z \term{}, kde 
$k \in \setname{L}$, si zachová svojí původní hodnotu a~nebude tedy expandován (zvětšen na hodnotu $2$). \setname{L}
dává zároveň finální podobu expanze \term{}. K dosažení největšího snížení počtu literálů je tedy třeba, aby \setname{L}
byla co nejmenší.

Jako příklad je zadáno \onset{}, \offset{} a $\term \equiv \onset_3$ v maticovém tvaru
\begin{displaymath}
  \begin{array}{c}
    \mcover[\onset]  =  \bmat{5}
    0 & 1 & 0 & 0 & 1 \\
    1 & 0 & 1 & 1 & 0 \\
    0 & 1 & 0 & 1 & 2 \\
    0 & 1 & 1 & 2 & 1 \\
    1 & 2 & 0 & 0 & 2 \\
    0 & 0 & 1 & 1 & 0 \\
    \emat \\ \\
    
    \mcover[\offset]  =  \bmat{5}
    1 & 1 & 1 & 1 & 1 \\
    2 & 1 & 1 & 0 & 0 \\
    0 & 0 & 0 & 1 & 0 \\
    0 & 0 & 2 & 2 & 1 \\    
    \emat \\ \\

    \mcover[t]  =  \bmat{5} 0 & 1 & 0 & 2 & 1 \emat
  \end{array}
\end{displaymath}
pak matice \matname{B} vypočítaná z \offset{} a \term{} bude vypadat následovně
\begin{displaymath}
  \matname{B} = \bmat{5}
  1 & 0 & 1 & 0 & 0 \\
  0 & 0 & 1 & 0 & 1 \\
  0 & 1 & 0 & 0 & 1 \\
  0 & 1 & 0 & 0 & 0 \\ 
  \emat
\end{displaymath}  

Snížení počtu literálů ale není jediný předpoklad. Tím druhým je pokrytí co možná největšího počtu termů. K~tomu je
třeba vytvořit tzv. matici pokrytí (Covering~Matrix) \matname{C}. Ta se vytváří z~\term{} a \onset{} 
podle následujícího vzorce
\begin{displaymath}
  \matname{C}_{i,j} =  \left\{ 
    \begin{array}{r@{\quad:\quad}l}
      1 & ((\term_j = 1) \wedge (\onset_{i,j} \not= 1)) \vee ((\term_j = 0) \wedge (\onset_{i,j} \not= 0)) \\ 
      0 & \mbox{v ostatních případech}
    \end{array} \right.
\end{displaymath}
To značí, že jednička v matici \matname{C} určuje, že \term{} nepokrývá $i$-tý term z \onset{}, protože existuje
proměnná, jejíž hodnota je pro oba termy rozdílná. K~tomu, aby byl pokryt $i$-tý term z~\onset{} je třeba, aby
pro~všechny $k \in \setname{L}$ bylo $\matname{C}_{i,k}=0$.

Matice \matname{C} získaná z \term{} a \onset{} z předchozího příkladu bude vypadat následovně
\begin{displaymath}
  \matname{C} = \bmat{5}
  0 & 0 & 0 & 0 & 0 \\
  1 & 1 & 1 & 0 & 1 \\
  0 & 0 & 0 & 0 & 1 \\
  0 & 0 & 1 & 0 & 0 \\ 
  1 & 1 & 0 & 0 & 1 \\ 
  0 & 1 & 1 & 0 & 1 \\ 
  \emat
\end{displaymath}  

Samotný průběh algoritmu začíná nalezením všech sloupců z \matname{B}, které musí být v~\setname{L}. Je zřejmé, že pokud
v~\matname{B} existuje řádek pouze s~jednou jedničkou, tak pozice této jedničku musí být v~\setname{L}, protože jinak by
daný řádek nemohl být pokryt. Nejprve jsou tedy nalezeny všechny řádky s~jednou jedničkou a~pozice této jedničky je
přidána do~\matname{L}. Jakmile je tak učiněno, mohou být všechny tyto sloupce a řádky, které jsou jimi pokryty,
odstraněny z~\matname{B} i~\matname{C}. Nyní je buď \matname{B} prázdná nebo jsou v~ní pouze řádky, jež mají dvě a více
jedniček. Lze tedy vybrat libovolný sloupec a ten odstranit. Je nejvýhodnější vybrat sloupec z~\matname{C}, který
pokrývá nejméně termů (obsahuje nejvíce jedniček). Tento sloupec se vloží do~množiny \setname{R}. Jedná se 
o~tzv. Raising~Set, což značí, že každý $k$-tý literál z~\term{}, kde $k \in \matname{R}$, bude expandován, tedy
$\term_k = 2$. Poté se ještě do~\setname{R} přidají sloupce se samými nulami v~\matname{B}. Celý proces se pak opakuje,
dokud nejsou odstraněny všechny sloupce, nebo dokud \matname{B} a \matname{C} jsou neprázdné. Pokud  \matname{B} je
po~skončení hlavního cyklu neprázdná, tak je třeba ještě najít minimální sloupcové pokrytí \matname{B}. K~tomu se
používá  speciální heuristika, která najde řešení blízké optimu. Její popis je však mimo rozsah tohoto textu.

V úplném závěru algoritmu se expanduje \term{} podle \setname{L}. Všem literálům, které nejsou v~\setname{L}, je hodnota
zvýšena na 2, což znamená, že jsou s~\term{} odstraněny. To lze matematicky zapsat takto (nově expandovaný term je
označen jako $\term^+$)
\begin{displaymath}
  \term^+_j = \left\{ 
    \begin{array}{c@{\quad:\quad}l}
      \term_j & j \in \matname{L}  \\
      2 & \mbox{v ostatních případech} \\
    \end{array} \right.
\end{displaymath}
Nakonec jsou z \onset{} odstraněny všechny termy, které \term{} pokrývá.

Celý postup bude ukázán na předchozím příkladu. Zde se nejprve vloží do~\setname{L} hodnota $2$, protože čtvrtý sloupec
obsahuje pouze jednu jedničku a ta je ve~druhém sloupci. Není se z~\matname{B} odstraní druhý sloupec a třetí a čtvrtý
řádek, které jsou jím pokryt. Z~\matname{C} se také odstraní druhý sloupec a první, třetí a čtvrtý řádek, který jsou jím
pokryty. To, že bude odstraněn třetí řádek je zcela zřejmé už před započetím algoritmu, protože je zkoumán třetí term
z~\onset{} a tím pádem je jasné, že bude vždy pokrývat sám sebe. Redukované matice vypadají nyní následovně
(pro~lepší pochopení jsou v~indexech uvedeny původní pozice v maticích)
\begin{displaymath}
  \begin{array}{c}
    \matname{B} = \bmat{5}
    1_{1,1} & 1_{1,3} & 0_{1,4} & 0_{1,4} \\
    0_{2,1} & 1_{2,3} & 0_{2,4} & 1_{2,5} \\
    \emat
    \\ \\
    \matname{C} = \bmat{5}
    1_{2,1} & 1_{2,3} & 0_{2,4} & 1_{2,5} \\
    1_{5,1} & 0_{5,3} & 0_{5,4} & 1_{5,5} \\ 
    0_{6,1} & 1_{6,3} & 0_{6,4} & 1_{6,5} \\ 
    \emat
  \end{array}
\end{displaymath}
V dalším kroku lze odstranit libovolný sloupec, který se přidá do \setname{R}. Vybere se tedy sloupec s~největším počtem
jedniček v~\matname{C}, což je pátý sloupec. Navíc se do~\setname{R} také přidá čtvrtý sloupec, protože je to sloupec
se~samými nulami v~\matname{B}. Do \setname{R} se tedy vloží hodnoty $4$ a $5$. Tyto sloupce se zároveň odstraní
a~v~\matname{B} i~\matname{C} zůstanou pouze dva sloupce. Nyní se znovu vybere sloupec, který musí být v \matname{L},
což  je beze sporu třetí sloupec, protože v~šestém řádku je nyní jen jedna jednička. Tento sloupec zároveň pokrývá oba
zbylé řádky v~\matname{B}, takže po~jejich odstranění je \matname{B} prázdná a cyklus je ukončen.

Po skončení cyklu je $\setname{L} = \{2,3\}$, což znamená, že se zkoumaný term expanduje následovně
\begin{displaymath}
  \bmat{5} 0 & 1 & 0 & 2 & 1 \emat \longrightarrow \bmat{5} 2 & 1 & 0 & 2 & 2 \emat
\end{displaymath}
Nakonec se ještě odstraní $\onset_1$ z \onset{}, který je jediný pokryt $\term^+$. Jako jediný má totiž v~druhém
a~třetím sloupci v~\matname{C} nuly.


%%%%%%%% IRREDUNDANT

\subsection{IRREDUNDANT}
\label{sec:irredund}

Smyslem procedury \eproc{IRREDUNDANT} je odstranit redundantní termy z~\onset{}, které byly získány procedurou
\eproc{EXPAND}. Celý průběh algoritmu se dá rozdělit na~tři subprocedury. Každá bude detailněji popsána v~následujících
podsekcích. Nyní bude uveden pouze jejich obecný význam a návaznost na další subprocedury.

První subprocedurou je \eproc{REDUNDANT}. Ta slouží k~rozdělení termů z~\onset{} na ty, po jejichž vynechání se pokrytí
nezmění (ty budou označovány \rset{} jako Redundantní) a na ty, po jejichž vynechání se pokrytí změní (ty budou
označeny \eset{} jako Essentials tedy nesporné\footnote{Pozor, nejedná se však o nesporné přímé implikanty, ale pouze
  o~relativně nesporné přímé implikanty}).

Druhá subprocedura \eproc{PARTIALY-REDUNDANT} dostane jako parametr \eset{}, \rset{} a \onset{}. Jejím účelem
je najít množinu $\rpset \subseteq \rset$ takovou, že \rpset{} neobsahuje žádné termy, které jsou pokryty \eset{}.

Třetí subprocedura \eproc{MINIMAL-IRREDUNDANT} najde minimální množinu $\rcset \subseteq \rcset$ takovou, aby pokrytí
$\rcset \cup \eset$ bylo ekvivalentní \onset{} a počet termů v~\rcset{} byl co nejmenší. Jedná se tedy o~problém hledání
nejmenšího pokrytí. $\rcset \cup \eset$ je zároveň výsledné pokrytí, které procedura \eproc{IRREDUNDANT} vrací.


\subsubsection{REDUNDANT}
\label{sec:redund}

Subprocedura \eproc{REDUNDANT} rozděluje \onset{} na dvě disjunktní podmnožiny \eset{} a \rset{}. To tedy znamená, že platí
$\eset \cup \rset = \onset$ a zároveň  $\eset \cap \rset = \emptyset$. V~množině \rset{} jsou všechny termy, po~jejichž
odebrání se pokrytí nezmění, takže musí platit, že
\begin{displaymath}
  \begin{array}{cc}
    \onset \cup \dcset - \{\term{}\} = \onset \cup \dcset, & \forall\term \in \rset
  \end{array}
\end{displaymath}
a pro~\eset{} musí tedy naopak platit, že
\begin{displaymath}
  \begin{array}{cc}
    \onset \cup \dcset - \{\term{}\} \not= \onset \cup \dcset, & \forall\term \in \eset
  \end{array}
\end{displaymath}

Pokud je tedy term \term{} v \rset{}, tak je zřejmé, že musí být pokryt pokrytím $\onset \cup \dcset -
\{\term\}$. Stačí tedy pouze zjistit, zda je kofaktor $(\onset \cup \dcset - \{\term\})_{\term}$ tautologií, což se
snadno zjistí pomocí procedury \eproc{TAUTOLOGY}. Pokud je tautologií, tak je term \term{} pokryt a vloží se 
do~\rset{}. V~opačném případě se přidá do~\eset{}. Takto se rozdělí všechny termy z~\onset{}.

 
\subsubsection{PARTIALY--REDUNDANT}
\label{sec:part-redund}
Subprocedura \eproc{PARTIALY-REDUNDANT} zjišťuje pro každý term z~\rset{}, zda je pokryt \eset{}. Pokud není je vložen
do množiny \rpset{}. Tedy jinak řečeno pro každý term $\term \in \rset$ je zjišťováno zda kofaktor $\eset_{\term}$ je
tautologie. Pokud není, je term \term{} vložen do \rpset{}. Ostatní termy, které jsou pokryty \eset{}, jsou přebytečné a
mohou být tedy odstraněny.


\subsubsection{MINIMAL--IRREDUNDANT}
\label{sec:min-irredund}
Subprocedura \eproc{MINIMAL-IRREDUNDANT} je pravděpodobně nejsložitější částí celého Espressa. Aplikuje speciální
heuristiku pro~získání minimálního pokrytí z~\rpset{}. K~jejímu bližšímu popsání by bylo třeba uvést mnoho nových
definic včetně rozšíření algoritmu pro zjištění tautologie. To je mimo rozsah tohoto textu.

Stručně by se \eproc{MINIMAL-IRREDUNDANT} dala popsat tak, že hledá nejmenší možné pokrytí \rcset{}, pro něž platí že
$\rcset \subseteq \rpset$  a zároveň 
\begin{displaymath}
  \onset = \rpset \cup \eset = \rcset \cup \eset
\end{displaymath}
Všechny tři pokrytí tedy musí být logicky ekvivalentní.


%%%%%%%% REDUCE

\subsection{REDUCE}
\label{sec:reduce}

Procedura \eproc{REDUCE} zkouší každý term $\term \in \onset{}$ nahradit menším termem, tedy termem s~větším počtem
literálů. Ten bude značen \termnew{} a musí platí, že je pokryt \term{}. Zároveň musí \onset{} po~nahrazení termu zůstat
zachováno. Z~toho je zřejmé, že některé termy nelze zmenšit a v~\onset{} zůstanou nezměněny. Důležité je, že nově 
vzniklé termy nemusí být přímé implikanty. Hlavní význam \eproc{REDUCE} je v~tom, že může dostat řešení z~lokálního
optima. Je to tedy krok, který významně vylepšuje celou heuristiku. 

Algoritmus začíná seřazením termů. To se dělá z~důvodu, že termy jsou postupně nahrazovány. Počáteční seřazení má
tedy vliv na konečný výsledek a~zároveň i na~rychlost provádění algoritmu. Jako nejvýhodnější se ukazuje vložit
na~počátek největší term a všechny zbylé termy seřadit podle delta vzdálenosti, kterou mají vzhledem k~počátečnímu, tedy
vybranému největšímu termu.

Hlavním cílem \eproc{REDUCE} je, jak už bylo uvedeno, co nejvíce zmenšit každý term z~\onset{}, přičemž pokrytí musí
zůstat zachováno. To znamená, že nově vzniklý term \termnew{} vznikne jako průnik původního termu \term{} s~termem
\termsccc{}, který je komplementem všech termů z~pokrytí $(\onset \cup \dcset - \{\term\})\: \cap \:\term$. Výpočet
\termsccc{} je podrobně popsán v~podsekci \ref{sec:sccc}. Pokud je \termsccc{} prázdný, tak $\termnew
=\term$. Algoritmus tedy funguje tak, že se projdou všechny termy z~\onset a každý term $\term^i$ je nahrazen nově 
vzniklým termem $\termnew^i$.


\subsubsection{SCCC: Smallest Cube Containing Complement}
\label{sec:sccc}

\eproc{SCCC} je subprocedura Espressa pro~výpočet termu \termsccc{} z~pokrytí  $\cover \equiv \onset \cup \dcset -
\{\term\}$. K~tomu je nejprve třeba spočítat kofaktor $\cover_\term$, který bude dále označen jako \cofactor{}. Pokud je
\cofactor{} tautologií, je $\termsccc = \emptyset$.  V~opačném případě je třeba zjistit, zda je \cofactor{} 
unátní. Pokud ano, tak \termsccc{} lze velmi snadno zjistit.  A to tak, že nejprve se najde term \tname{p}, který
je průnikem všech termů z~\cofactor{}, a~poté se testuje každý literál $\tname{p}_j \not= 2$, zda pro některý term
$\tname{c} \in \cofactor$ platí, že kofaktor $\tname{c}_{\tname{p}_j}$ je tautologií. Pokud je, tak to znamená, že
proměnná $x_j$ je kompletně pokryta pokrytím \cover{} a~literál komplementárního termu $\termsccc_j$ tak bude nabývat
inverzní hodnoty $\tname{p}_j$. Pokud $\tname{c}_{\tname{p}_j}$ není tautologií, tak proměnná $x_j$ není pokryta
\cover{} a~$\tname{p}_j = 2$.

Pokud funkce není unátní, lze použít rekurzivní rozklad. V případě, že je
\begin{displaymath}
  \mathrm{SCC}(\cofactor) = \mathrm{SCCC}(\ol{\cofactor})\;,
\end{displaymath}
tak platí, že
\begin{displaymath}
  \mathrm{SCCC}(\cofactor) = \mathrm{SCC}(x_j\,\mathrm{SCCC}(\cofactor_{x_j}) +
  \ol{x}_j\,\mathrm{SCCC}(\cofactor_{\ol{x}_j}))
\end{displaymath}
To vychází ze Shannonova kofaktoru.\footnote{Zájemci si mohou důkaz najít v~\cite[str. 119-120]{espresso}}.

Výsledný rozklad se udělá tak,  že se nejprve vybere nejvíce binátní proměnná, která bude dále označena jako
$x_j$. Výsledný term \termsccc{} je pak určen jako  
\begin{displaymath}
  \termsccc = x_j\,\mathrm{SCCC}(\cofactor_{x_j})\:\sqcup \:\ol{x}_j\,\mathrm{SCCC}(\cofactor_{\ol{x}_j})
\end{displaymath}
Operace $\sqcup$  znamená speciální sjednocení, které je pro~termy \tname{u} a \tname{v} definováno následovně
\begin{displaymath}
  \begin{array}{cc}
    \begin{array}{cc|cccc}
                  &           &   & \multicolumn{2}{c}{\tname{v}_j} & \\ 
                  & \sqcup    & 0 & 1 & 2 & \emptyset \\ \hline
                  & 0         & 0 & 2 & 2 & 0\\
                  & 1         & 2 & 1 & 2 & 1\\
      \mbox{\raisebox{1.8ex}[0pt]{$\tname{u}_j$}}
                  & 2         & 2 & 2 & 2 & 2\\
                  & \emptyset & 0 & 1 & 2 & \emptyset\\
    \end{array}\;,& \;\; j \in  \{1,\ldots,n\} \\
  \end{array}
\end{displaymath}


\subsubsection{Příklad}
\label{sec:reduce-exam}

Jako příklad je dána funkce o čtyřech proměnných, kde  $\onset = \{\ol{x}_2\ol{x}_4, \ol{x}_3\ol{x}_4,
x_1\ol{x}_2x_3\}$, $\dcset = \emptyset$ a~prvním zkoumaným termem je $\term = \onset_1 = \ol{x}_2\ol{x}_4$. Pak 
\begin{displaymath}
  \cover \equiv (\onset \cup \dcset - \{\term\} \cap \term = \{\ol{x}_3\ol{x}_4, x_1\ol{x}_2x_3\} \cap \ol{x}_2\ol{x}_4
  = \{\ol{x}_2\ol{x}_3\ol{x}_4, x_1\ol{x}_2x_3\ol{x}_4\}
\end{displaymath}
což v~maticovém zápisu vypadá následovně 
\begin{displaymath}
  \mcover = \bmat{4} 0 & 0 & 0 & 2 \\ 0 & 1 & 0 & 1 \emat 
\end{displaymath}
Kofaktor $\cofactor \equiv \cover_\term$ je pak
\begin{displaymath}
  \mcover[\cofactor] = \bmat{4} 2 & 0 & 2 & 2 \\ 2 & 1 & 2 & 1 \emat 
\end{displaymath}
Z maticového zápisu je dobře vidět, že \cofactor{} není unátní. Jedinou binátní proměnnou je $x_3$. Po rozkladu je
$\mcover[\cofactor_{\ol{x}_3}] = \bmat{4} 2 & 2 & 2 & 2 \emat$, tedy tautologie, a $\mcover[\cofactor_{x_3}] = \bmat{4}
2 & 2 & 2 & 1 \emat$, jež je unátní a~v~tomto kroku je tedy $\mcover[\termsccc_{x_3}] = \bmat{4} 2 & 2 & 2 & 0
\emat$. Výsledný rozklad tedy vypadá následovně
\begin{displaymath}
  \termsccc \;=\;\ol{x}_3 \cdot \emptyset\:\sqcup\:x_3\ol{x}_1 \;=\; \emptyset\:\sqcup\:\ol{x}_1x_3 \;=\; \ol{x}_1x_3
\end{displaymath}

Nahrazující term \termnew{} bude mít tvar
\begin{displaymath}
   \termnew \;=\; \term \cap \termsccc = \ol{x}_2\ol{x}_4 \cap \ol{x}_1x_3 = \ol{x}_1\ol{x}_2x_3\ol{x}_4
\end{displaymath}

Po jeho nahrazení jsou zároveň všechny termy v~\onset{} disjunktní a po~proběhnutí \eproc{REDUCE} je $\onset =
\{\ol{x}_1\ol{x}_2x_3\ol{x}_4, \ol{x}_3\ol{x}_4, x_1\ol{x}_2x_3\}$.


\newpage
%%%%%%%% LAST GASP

\subsection{LAST--GASP}
\label{sec:last-gasp}

Procedura \eproc{LAST-GASP} je posledním krokem heuristiky v~hlavní smyčce. Je to v~podstatě poslední pokus o~dostání se
z~lokálního optima. K~tomu používá upravenou proceduru \eproc{REDUCE}. Změna spočívá v~tom, že oproti klasické
\eproc{REDUCE} nejsou termy \termnew{} nahrazovány v~\onset{}, ale místo toho se pouze uloží do~nového pokrytí
\onsetnew{}. V~dalším provádění tak nově vzniklé termy nemají vliv~na redukci dalších termů z~\onset{}. To může vést
k~tomu, že pokrytí \onset{} a \onsetnew{} nemusí být ekvivalentní. Nápravu přinese volání procedury \eproc{EXPAND}
na~nově vzniklé termy. Nakonec je na~výsledné pokrytí zavolána procedura \eproc{IRREDUNDANT-COVERS}, která může snížit
výsledný počet termů.



%%%%%%%% THE OTHERS

\subsection{Ostatní procedury}
\label{sec:others}

Espresso obsahuje ještě některé další procedury, které zatím nebyly popsány. V této podsekci bude jenom stručně uveden
jejich význam. Většinou se totiž jedná pouze o~doplňkové procedury, které slouží ke zrychlení nebo k~drobnému vylepšení
celé heuristiky. Nejsou proto zcela zásadní.


\subsubsection{COMPLEMENT}
\label{sec:complement}
Procedura \eproc{COMPLEMENT} slouží k~výpočtu komplementu. Algoritmus je založen na tom, že výpočet komplementu
pro~unátní pokrytí je velmi snadný. Pokud pokrytí unátní není, lze použít Shannonův rozklad a výsledná pokrytí
spojit. Základ je tedy podobný jako při~výpočtu SCCC v~procedure \eproc{REDUCE} popsaném v~podsekci
\ref{sec:sccc}. Mimochodem stejný základ využívá i~vylepšený algoritmus pro~výpočet tautologie.

Procedura \eproc{COMPLEMENT} je však podle všeho použita pouze před začátkem hlavní smyčky pro~výpočet \offset{}. Pokud
však \onset{} a \dcset{} obsahuje pouze mintermy, lze pro~zjednodušení vypočítat \offset{} jako doplněk do~kompletně
specifikované funkce. 


\subsubsection{ESSENTIAL--PRIMES}
\label{sec:essentials}
Procedura \eproc{ESSENTIAL-PRIMES} může výrazně zrychlit celou heuristiku. Slouží k~nalezení nesporných přímých
implikantů. Ty pak uloží zvlášť a odstraní je z~\onset{}. Další procedury tedy s nimi nemusí počítat a mohou tak být
prováděny rychleji.


\subsubsection{MAKE--SPARSE}
\label{sec:make-sparse}
Procedura \eproc{MAKE-SPARSE} má význam jen pro~vícevýstupové funkce. Zde je uvedena pouze pro~doplnění, protože je součástí
Espressa.

