A method of optimizing Boolean functions


Mirko Stojaković




This is an attempt to find diagrams of the Venn type for simplifying Boolean functions of any number of variables. The method developed here has the advantage of being applicable to a greater number of variables than is usually possible by the existing methods ([1-5]). The diagrams drawn are completely symmetric so that the scheme obtained is not confusing to the eye as it is the case for other methods. Let $f(x_1,\ldots,x_n)$ be a function from $(0,1)^n$ to $(0,1)$. For each variable $x_i$, $i = 1,\ldots,n$ we draw a curve $(x_i)$ in the plane which is a ``parabola'' of even degree $2(i-1)$, $i = 1,\ldots,n$, so that a) the curve (in fact the straight line) $(x_1)$ is the axis of symmetry for all other curves $(x_2),\ldots,(x_n)$. b) Each curve $(x_i)$ bisects every part of the plane previously divided by the curves $(x_1),\ldots,(x_{i-1})$. Each part of the plane bisected by the curves $(x_i)$, $i=1,\ldots,n$ represents a conjunction of the variables xt or their negations corresponding to the place in which this part is situated (on the ``upper'' or in the ``lower'' side of the curve $(x_i)(.1a,b,c,d;2B)$. The function $f(x_1,\ldots,x_n)$ is then represented by the union of the conjunctions from the complete disjunctive normal form of that function. The paper also proposes a method of the canonical realization of Boolean functions in terms of two position relay circuits which are convenient for the ``self-simplification'' of the scheme (f.4; 5).