Reed–Muller expansion

In Boolean logic, a Reed–Muller expansion (or Davio expansion) is a decomposition of a Boolean function.

For a Boolean function ${\displaystyle f(x_{1},\ldots ,x_{n}):\mathbb {B} ^{n}\to \mathbb {B} }$ we call

${\displaystyle {\begin{aligned}f_{x_{i}}(x)&=f(x_{1},\ldots ,x_{i-1},1,x_{i+1},\ldots ,x_{n})\\f_{{\overline {x}}_{i}}(x)&=f(x_{1},\ldots ,x_{i-1},0,x_{i+1},\ldots ,x_{n})\end{aligned}}}$

the positive and negative cofactors of ${\displaystyle f}$ with respect to ${\displaystyle x_{i}}$, and

${\displaystyle {\begin{aligned}{\frac {\partial f}{\partial x_{i}}}&=f_{x_{i}}(x)\oplus f_{{\overline {x}}_{i}}(x)\end{aligned}}}$

the boolean derivation of ${\displaystyle f}$ with respect to ${\displaystyle x_{i}}$, where ${\displaystyle {\oplus }}$ denotes the XOR operator.

Then we have for the Reed–Muller or positive Davio expansion:

${\displaystyle f=f_{{\overline {x}}_{i}}\oplus x_{i}{\frac {\partial f}{\partial x_{i}}}.}$