On a quasi-ordering on Boolean functions (Q924135): Difference between revisions

The set \(\Omega=\bigcup_{n\geq1}B^{B^n}\) of all Boolean functions is quasi-ordered by the following relation: the functions \(f\in B^{B^n}\) and \(g\in B^{B^n}\) satisfy \(g\leq f\) iff \(g=f(p_1,\dots,p_n)\) for some \(m\)-ary projections \(p_1,\dots,p_n\). Let \((\widetilde{\Omega},\sqsubseteq)\) denote the partially ordered set associated with the quasi-ordered set \((\Omega,\leq)\). It is proved that \((\widetilde{\Omega},\sqsubseteq)\) is equimorphic to the poset \(([\omega]^{<\omega},\subseteq)\) of all finite posets of the set \(\omega\) of integers, where two posets are called equimorphic if each of them is isomorphic to a subset of the other. The authors also provide functional equations which characterize the class \(E^k\) of Boolean functions with at most \(k\) essential variables and the subclass \(L^k\) of those functions in \(E^k\) which satisfy \(f({\mathbf z}_1+{\mathbf z}_2)= f({\mathbf z}_1)+f({\mathbf z}_2)+f(\mathbf 0)\). There are many other results in this paper, which is higly technical but self-contained. It also contains numerous references to papers which study the qoset \(\widetilde{\Omega}\).