A polynomial decomposition of Boolean functions
type: Item
instance of: scholarly article
title: A polynomial decomposition of Boolean functions
zbMATH Open document ID: 0801.94029
DOI: 10.1007/BF01208315
published in: Mathematical Notes
publication date: 1994-07-13T00:00:00Z
review text: Some results on polynomial decompositions of Boolean functions with respect to various systems of Boolean functions are deduced. For example, if \(\{g_ \tau (x,y)\}\) is a system of Boolean functions such that the matrix \((\alpha_{\sigma\tau})\) is nondegenerate, where \(\alpha_{\sigma\tau}=(g_ \tau (\sigma,y))'_ y\) (the derivative of a Boolean function \(f(x,y)\) with respect to the variable \(y\) is, by definition, \(f'_ y (x,y)= f(x,0) \oplus f(x,1))\), then any Boolean function \(f(x,z)\) can be represented in the form \[ f(x,z)= \sum_ \sigma \sum_ \tau \beta_{\sigma\tau} (g_ \tau (x,f(\sigma, z))\oplus g_ \tau(x,0)), \] where \((\beta_{\sigma\tau})^ t= (\alpha_{\sigma\tau})^{-1}\), the vectors \(x\), \(\tau\), \(\sigma\), 0 are one-dimensional, and \(z\) has an arbitrary dimension. Other simplified decompositions are obtained whenever the functions \(g_ \tau (x,y)\) are nondegenerate (this notion implies a differential Boolean operator defined inductively in the paper).
Mathematics Subject Classification ID: 94C10
zbMATH DE Number: 567869
zbMATH Keywords: Boolean functions
zbMATH Keywords: derivative
author: Sergeĭ Fedorovich Vinokurov
author: Nikolay A. Peryazev
reviewed by: Ioan Tomescu
MaRDI profile type: Publication
cites work: Q3898440
cites work: On a Theory of Boolean Functions
description: scientific article; zbMATH DE number 567869