Polynomial expansions of Boolean functions with respect to nondegenerate functions (Q2366362): Difference between revisions

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.