zbMATH — the first resource for mathematics

On the comparison of Boolean bases. (English. Russian original) Zbl 0958.06009
Dokl. Math. 60, No. 1, 118-119 (1999); translation from Dokl. Akad. Nauk, Ross. Akad. Nauk 367, No. 6, 742-745 (1999).
From the text: This paper deals with the comparison of Boolean bases (namely, finite complete systems of Boolean functions) with respect to the complexity of implementing Boolean functions by formulas over these bases. The complexity of a formula is the number of symbols of variables it contains. The complexity of a function \(f\) (hereafter, Boolean function) over a basis \(B\) is defined as the least complexity of formulas over \(B\) that implement \(f\).

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