Minimization of Boolean functions in the basis OR-NOT (AND-NOT) (Q2556312)

The paper presents an algorithm that transforms an arbitrary formula on the basis of AND-OR-NOT to one of the basis of OR-NOT, while preserving the optimality of the formulas. In other words, the algorithm permits the transformation from a minimal (irredundant) formula on the basis of AND-OR-NOT to a minimal (irredundant) one, within a constant, on the basis of OR-NOT. It also establishes a correspondence between the minimal realization of a tree-type circuit of the elements AND, OR, NOT and one of the elements OR and NOT with any number of inputs and for a given Boolean function.