zbMATH — the first resource for mathematics

Polynomial expansions of Boolean functions with respect to nondegenerate functions. (English. Russian original) Zbl 0773.06018
Algebra Logic 30, No. 6, 411-416 (1991); translation from Algebra Logika 30, No. 6, 631-637 (1991).
The derivative of a Boolean function $$f(x_ 1,\dots,x_ n)$$ with respect to variables $$x_{i_ 1},\dots,x_{i_ m}$$ $$(m\leq n)$$ is defined by $f^{(m)}_{x_{i_ 1}\cdots x_{i_ m}}(x_ 1,\dots,x_ n)=\oplus f(x_ 1,\dots,\sigma_{i_ 1},\dots,\sigma_{i_ m},\dots,x_ n),$ where the sum on the right hand side is taken over all the binary strings $$(\sigma_{i_ 1},\dots,\sigma_{i_ m})$$. A function $$g$$ is nondegenerate if $$f^{(n)}_{x_ 1\cdots x_ n}(x_ 1,\dots,x_ n)\neq 0$$. A Boolean function $$f(x_ 1,\dots,x_ n)$$ has a polynomial expansion with respect to function $$g(x_ 1,\dots,x_ m,y)$$, $$m\leq n$$, if $f(x_ 1,\dots,x_ n)=\oplus g\bigl(x^{\tau_ 1}_ 1,\dots,x^{\tau_ m}_ m,\;f^ \tau(\sigma_ 1,\dots,\sigma_ m,x_{m+1},\dots,x_ n)\bigr),$ where $$\tau=g^{(m)}_{x_ 1\cdots x_ m}(x_ 1,\dots,x_ m,1)$$ and the sum is taken over all the binary strings $$(\sigma_ 1,\dots,\sigma_ m)$$, $$(\tau_ 1,\dots,\tau_ m)$$ for which $$g_ y'(\sigma^{\tau_ 1}_ 1,\dots,\sigma^{\tau_ m}_ m,y)=1$$.
It is proved that a function $$f(x_ 1,\dots,x_ n)$$ has a polynomial expansion with respect to function $$g(x_ 1,\dots,x_ m,y)$$ iff the function $$g$$ is nondegenerate. A canonical form presentation over the set $$\{\neg,\land,\lor,\to\}$$ of nondegenerate binary functions follows.
Reviewer: J.Henno (Naasa)

MSC:
 06E30 Boolean functions 03G05 Logical aspects of Boolean algebras
Full Text:
References:
  S. V. Yablonskii, G. P. Gavrilov, and V. B. Kudryavtsev, Functions of Algebra of Logic and Post Classes [in Russian], Nauka, Moscow (1966).  É. K. Machikenas and V. P. Suprun, On the Polynomial Expansion of Boolean Functions [in Russian], Deposited in the All-Union Institute of Scientific and Technical Information at No. 1899-V88 on March 9, 1988.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.