zbMATH — the first resource for mathematics

An algorithmic criterion for the comparison of Boolean bases. (Russian) Zbl 1201.94150
A precedence relation \(\preceq\) has been introduced for bases (i.e., functionally complete systems of Boolean functions) by B. A. Subbotovskaya [Sov. Math., Dokl. 4, 478–481 (1963); translation from Dokl. Akad. Nauk SSSR 149, 784–787 (1963; Zbl 0154.25903)]. The relation \(\preceq\) is reflexive and transitive but not antisymmetric. A lexicographical ordering \(\lambda\) is considered between the \(n\)-ary Boolean functions, and the \(\lambda\)-smallest function in the equivalence class (for mutual \(\preceq\)-precedence) containing \(f\) is denoted by \(\hat f\). For a base \(B\), we denote by \(\text{Ker}(B)\) the set of functions \(\hat f\) where \(f\) runs through the elements of \(B\).
The main theorem of the article extends a result of Lupanov. The equivalence of three conditions is asserted for the bases \(B_1\) and \(B_2\): (a) \(B_1\preceq B_2\), (b) any element of \(B_2\) may be expressed by a non-repeating formula over \(B_1\), (c) \(\text{Ker}(B_2)\subseteq\text{Ker}(B_1)\). In addition, it is stated that the precedence \(B_1\preceq B_2\) is immediate exactly if the condition (c) holds and the difference set \(\text{Ker}(B_1)\subset\text{Ker}(B_2)\) has a single element.
The verification of these results is worked out over forty pages. In the course of the proof procedure, (i) the functions \(f^{(2)},f^{(3)},\dots,\) obtained by the iteration of \(f\), are studied, (ii) certain universal functions are introduced by use of independent function systems where the dependence of two functions is defined in terms of substitution of constants for some variables, (iii) complicated manipulations with formulae are performed, (iv) the most economical superpositional representation of a function is considered such that each inner function is linear, (v) a complexity result about the sequence \(f,f^{(2)},f^{(3)},\dots\) is stated.

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