\chapter{Úvod}
\label{kap_uvod}%
Základním tématem následujících stránek jsou logické funkce a jejich
reprezentace pomocí modifikovaných binárních diagramů (MBD). Úkolem bylo
vytvořit vlastní softwarový balík, který bude pracovat s MBD a implementovat
funkce, které by využily specifických vlastností MBD k minimalizaci logických
funkcí.

\section{Účel projektu a jeho pozadí}%
Minimalizace logických funkcí je obor, který se rozvinul s prvním praktickým
uplatněním Booleovy algebry v praxi. Z algebraicky zadaných logických funkcí se
přímo vychází nejen při návrhu číslicových obvodů, ale i v řadě jiných oborů,
které s elektronikou, s níž jsou nejčastěji dávány do souvislosti logické
funkce, nemají příliš mnoho společného. Prakticky všechny tyto obory mají
požadavek, aby vyjádření logické funkce bylo co nejúspornější. Na tvaru logické
funkce jsou přímo závislé velikosti struktur, které z ní vycházejí. Čím je její
zápis menší, tím je menší i číslicový obvod nebo MBD.\\
\indent Existuje řada různých \emph{klasických} vyjádření logických funkcí jako
je algebraický zápis, pravdivostní tabulka nebo mapy. V posledních dvaceti
letech se s rozmachem výpočetní techniky začínají prosazovat tzv. \emph{Binární
rozhodovací diagramy}, z nichž vychází i předmět této práce - MBD. Využití
tohoto způsobu vyjádření logických funkcí
je nepřeberné, nicméně minimalizace nepatří mezi ty nejčastěji používané.\\
\indent Úkolem této práce je nejen prozkoumat možnosti minimalizace pomocí MBD,
ale také zjistit více o samotných MBD, které jsou v oblasti binárních
rozhodovacích diagramů rovněž na okraji zájmu. Existuje řada programových
balíků, které pracují s BDD jako CUDD \cite{Som06} nebo BuDDy \cite{Bud06},
ovšem ani jeden z nich přímo nepracuje s neúplně určenými funkcemi. Samozřejmě,
že s těmito produkty je možné také neúplně určené funkce vyjádřit, ovšem pouze
za použití méně efektivních postupů. V této práci je naopak zvolena přímá
forma reprezentace neúplně určených funkcí, kterou představuje MBD.\\
\indent Vytvářet úplně nový softwarový balík implementující MBD není triviální
záležitostí, tudíž je vhodné předem upozornit, že snahou této práce není
konkurovat výše zmiňovaným knihovnám. Při práci na MBD knihovně s podporou
minimalizace logických funkcí bylo nutné vyřešit řadu poměrně složitých úkolů,
jako je načítání MBD a jeho redukce, statické a dynamic-ké řazení proměnných
nebo například nahrazování uzlů. Vyřešit takový úkol za půl roku na 100\% je
pro jednoho člověka nemožné, proto nebylo u řady dílčích problémů zvoleno úplně
nejlepší možné řešení\footnote{ \emph{Nejlepší} z pohledu časové složitosti
nebo kvality výstupu.}, ale řešení, které se snáze implementuje. Díky takovým
úlevám není pak možné tuto implementaci plně porovnávát s ostatními BDD balíky.
I přesto, že je tato implementace MBD na půl cesty ke kompletnímu řešení
minimalizace logických funkcí pomocí MBD, se podařilo dosáhnout řady velmi
zajímavých nebo překvapivých výsledků - a to jak v~oblasti řazení proměnných,
tak i u minimalizace logických funkcí. Při práci na tomto balíku byla dokonce
objevena nová, dosud nikde nepopsaná metoda statického řazení proměnných - STAT.\\
\indent Závěrem je nutné zdůraznit, že tento text vychází z teoretických
základů položených v~\cite{Jac93}, kde byl MBD poprvé popsán důkladně MBD a kde
byly řešeny a teoreticky zpracovány problémy jako minimalizace logických či
řazení vstupních proměnných v MBD. Celá implementace MBD, o které je celá tato
práce, je však vytvořena autorem naprosto samostatně a bez použití jakýchkoliv
jiných knihoven nebo spolupracovníků.
