Original title:
Knihovna pro boolovské funkce v algebraické normální formě
Translated title:
Library for Boolean Functions in Algebraic Normal Form
Authors:
Vasilišin, Maroš ; Mrázek, Vojtěch (referee) ; Dobai, Roland (advisor) Document type: Bachelor's theses
Year:
2017
Language:
cze Publisher:
Vysoké učení technické v Brně. Fakulta informačních technologií Abstract:
[cze][eng]
Táto bakalárska práca sa zaoberá návrhom a implementáciou knižnice v jazyku C pre manipuláciu Boolovych funkcií v Algebraickej Normálnej Forme. Väčšina existujúcich reprezentácií Boolovych funkcií je založená na binárnych rozhodovacích diagramoch. Algebraická Normálna Forma poskytuje oproti binárnym rozhodovacím diagramom určité výhody, napríklad tú, že sa dá z nej v lineárnom čase určiť Boolova hodnota funkcie. Implementovaná knižnica za pomoci jednoduchých štruktúr poskytuje efektívnu reprezentáciu Boolovej funkcie v programe. Výskumom sme zistili, že reprezentácia pomocou Algebraickej Normálnej Formy má svoj využitie, a v určitých prípadoch dosahuje lepšie výsledky ako reprezentácia pomocou binárnych rozhodovacích diagramov.
This bachelor thesis focuses on design and implementation of library in C language for manipulation od Boolean functions in Algebraic Normal Form. Majority of existing libraries for representation of Boolean functions is based on binary decision diagrams. Algebraic Normal Form presents several advantages over binary decision diagrams, for example Boolean value of function can be determined in linear time. Implemented library uses simple structures to effectively represent Boolean function in program. After experiments we determined that representation in Algebraic Normal Form has its applications, and in some cases it provides better results than representation in binary decision diagrams.
Keywords:
algebraic normal form; binary decision diagram; Boolean Algebra; Boolean function; C; logical operations; normal form; algebraická normálna forma; binárny rozhodovací diagram; Boolova algebra; Boolova funkcia; C; logické operácie; normálna forma
Institution: Brno University of Technology
(web)
Document availability information: Fulltext is available in the Brno University of Technology Digital Library. Original record: http://hdl.handle.net/11012/69658