Reconstruct a Boolean function from its partial derivatives

Question

If I have a Boolean function is there a way for me to reconstruct given it’s partial derivative? What if I have the second order derivatives? This is for discrete functions.

I am struggling to find literature related to this.

Answer 1

Until you make explicit what you mean by boolean function I will try to guess it based on the most obvious premise.

We could form a boolean algebra of sorts by defining AND by multiplication so $x \text{and} y$ becomes $x*y$ and similarly the NOT by the $1-x$ operator... (Here $0$ means false and $1$ means true)

So then

$$A \ \text{and} \ B = AB, \neg A = (1-A), A \ \text{or} \ B = \neg (\neg A\ \text{and}\ \neg B) = (1 - (1-A)(1-B)) $$

So now we can take a boolean circuit $\lbrace 0, 1\rbrace^{n} \rightarrow \lbrace 0, 1\rbrace$ and intepret it as a multivaraite polynomial $P(x_1, x_2 ... x_n)$.

Now the question makes sense. If we know the REAL derivatives of this polynomial with respect to each variable $x_i$ can we recover the polynomial?

So In general, no we cannot recover the exact polynomial if it were a real polynomial since we will only know it up to a constant BUT, since we are looking of Boolean polynomials, then we actually probably still can! We can check for which constants is the resultant polynomial STILL a boolean circuit namely from the derivatives we might find the form of the polynomial to be

$$ P(x_1 , ... x_n ) + C$$

Now we fix an $x_1 ... x_n$ then there are two values of $C$ possible to either make this $0$ or $1$ call them $C_1^x , C_2^x$. But we can fix another pattern $y_1 ... y_n$ and find $C_1^y, C_2^y$. Now a valid $C$ needs to be an intersection of these sets. I suspect in practice that by repeatedly finding such pairs and intersecting them you will quickly be left with not a pair of $C$ but a singular possible $C$. Lets see this in practice.

The circuit can be just the good old $(A,B) \rightarrow A \text{and} B$. So its polynomial is $P(x,y) = xy$

So then

$$ \frac{\partial P}{\partial x} = y, \frac{\partial P}{\partial y} = x$$

So then we conclude that $P_{\text{implied from derivative}} = xy + C$

We let $x = 0, y=0$. Clearly $C$ can be either $0,1$. We let $x=1,y=1$. Again $C$ can either be $0, -1$ to keep this binary. Thus we conclude that $C$ must be 0.