zbMATH — the first resource for mathematics

On preworst bases in \(P_ 2\). (Russian) Zbl 0805.06015
For every Boolean formula \(F\) let \(L(F)\) be the number of occurrences of variables in \(F\). For every basis \(B\) of Boolean functions and every Boolean function \(f\) let \(L_ B(f)\) denote the least value of \(L(F)\) as \(F\) runs over all formulas in \(B\) that realize \(f\). The set of all bases of Boolean functions is endowed with the preorder \(\leq\) defined as follows: \(B_ 1\leq B_ 2\) if and only if there is a constant \(c>0\) such that \(L_{B_ 1}(f)\leq cL_{B_ 2}(f)\) for every Boolean function \(f\). Lupanov has proved that \(B_ 0= \{\&,\lor,-\}\) is the worst basis, in the sense that \(B\leq B_ 0\) for every basis \(B\). By a preworst basis is meant any maximal element of the set of all bases \(B\) such that \(B_ 0\not\leq B\).
The author proves that every preworst basis is equivalent to a basis of the form \(B= B_ 0\cup\{T^{\sigma_ 0\sigma_ 1\cdots\sigma_ n}_ \pi g\}\), where \(g\) is one of the functions \(x_ 1 x_ 2\cdots x_ n\lor \bar x_ 1\bar x_ 2\cdots \bar x_ n\), \(n\geq 2\), \(x_ 1(x_ 2\lor\cdots\lor x_ n)\lor x_ 2\cdots x_ n\), \(n\geq 3\), \(x_ 1(x_ 2\lor x_ 3\cdots x_ n)\lor x_ 2\bar x_ 3\cdots\bar x_ n\), \(n\geq 3\), \(x_ 1(x_ 2\lor x_ 3)\lor x_ 3 x_ 4\), \(x_ 1(x_ 3 x_ 4\lor x_ 5)\lor x_ 2(x_ 3\lor x_ 4 x_ 5)\), and \((T^{\sigma_ 0 \sigma_ 1\cdots \sigma_ n}_ \pi g)(x_ 1,\dots,x_ n)= g^{\sigma_ 0}(x^{\sigma_ 1}_{\pi(1)},\dots, x^{\sigma_ n}_{\pi(n)})\), for \(\sigma_ 0,\sigma_ 1,\dots,\sigma_ n\in \{0,1\}\) and \(\pi\) a permutation of \(\{1,\dots,n\}\).
The proof goes through 36 lemmas. It is not known whether every basis of the above form is necessarily preworst.

06E30 Boolean functions
03G05 Logical aspects of Boolean algebras
94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)