zbMATH — the first resource for mathematics

On the premaximal Boolean bases. (English. Russian original) Zbl 0969.06012
Discrete Math. Appl. 9, No. 3, 295-342 (1999); translation from Diskret. Mat. 11, No. 2, 118-160 (1999).
In this paper the complexity \(L(F)\) of a formula \(F\) is said to be the total number of occurrences of all variables in the formula \(F\), and the complexity \(L_{B}(f)\) of a function \(f\) over a basis \(B\) is the minimum of the complexities of formulas over the basis \(B\) which realize the function \(f\). The method of comparison of bases proposed by O. B. Lupanov is based on the following order relations over the set of bases: (a) \(B_{1}\) is said to precede \(B_{2}\) if there exists a positive constant \(C\) such that for any function \(f\), \(L_{B_{1}}(f)\leq C L_{B_{2}}(f)\); (b) \(B_{1}\) strictly precedes \(B_{2}\) if \(B_{1}\) precedes \(B_{2}\) while the converse is not true. A basis \(B\) is called premaximal if \(B\) strictly precedes the basis \(B_{0}\) and there exists no basis \(B'\) such that \(B\) strictly precedes \(B'\) and \(B'\) strictly precedes \(B_{0}\), where \(B_{0}\) consists of conjunction, disjunction and negation. The notion of premaximal basis was introduced by V. A. Stetsenko [Mat. Vopr. Kibern. 4, 139-177 (1992; Zbl 0805.06015)]. In the same paper a necessary condition of premaximality for an arbitrary basis is given, and also all possible candidates for premaximal bases are listed. Stetsenko conjectured that his necessary condition is also sufficient, that is, all the bases that he described are premaximal.
In this paper this conjecture is proved and a classification of the premaximal bases up to equivalence is presented.
06E30 Boolean functions
Full Text: DOI