Publication at Faculty of Mathematics and Physics |
2016
Abstract
A Boolean function of n variables is a mapping from {0;1}^n to {0;1}. Boolean functions naturally appear in many areas of mathematics and computer science and constitute a key concept in complexity theory.
In this paper we shall study an important problem connected to Boolean functions, a so called Boolean minimization problem, which aims at finding a shortest possible representation of a given Boolean function. The formal statement of the Boolean minimization problem (BM) of course depends on how the input function is represented, and how the size of the output is measured.