zbMATH — the first resource for mathematics

On a classification of Post classes. (Russian) Zbl 0671.06009
Let \(B_ 1\) and \(B_ 2\) be two bases of a closed class K of Boolean functions. One defines \(B_ 1\leq B_ 2\) by the existence of a constant \(c>0\) such that \(L_{B_ 1}(f)\leq cL_{B_ 2}(f)\) for every \(f\in K\), where \(L_ B(f)\) denotes the least number of functions in B generating f. The class K is said to be elementary provided \(B_ 1\leq B_ 2\) and \(B_ 2\leq B_ 1\) for every two bases \(B_ 1\) and \(B_ 2\) of K. The author determines all elementary classes in the Post classification.
Reviewer: S.Rudeanu

06E30 Boolean functions
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
Full Text: EuDML