Technische Universität München Robotics and Embedded Systems
 

Boolean Expression Simplifier

 
Type BA, SA
Supervisor Prof. Dr.-Ing. Alois Knoll
Advisor Markus Weißmann, M.Sc.
Research Area Boolean Algebra, Optimization
Programming Language OCaml
Required Skills OCaml API design
Required Knowledge Boolean Algebra
Language English or German

Description

Boolean algebra expressions are used in a phletora of fields. Often it is desired that these expressions take a minimal form, e.g. in For example the expression A and (B or A) is equivalent to just A, the expression A and (not A) is equivalent to false, etc. As the problem itself is NP-complete, there are no efficient algorithms for it. There exist different algorithms to find an optimal solution (e.g. Karnaugh-Veitch-diagramms, Quine McCluskey) as well as heuristic based ones (e.g. Espresso).

bdd.png

The goal of this project is to create a library that provides multiple algorithms to reduce boolean algebra expressions. The library should have a common interface for all implemented algorithms so that the concrete algorithm can be changed very easily. This will make it easy to chose an appropriate algorithm for the concrete problem.

For more information, contact Markus Weißmann.

Literature