# 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.

##### MSC:
 06E30 Boolean functions 03G05 Logical aspects of Boolean algebras 94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
##### Keywords:
Boolean functions; preorder; preworst basis