# Equivalent-symmetric (E-symmetric) variables check for Boolean functions

In [1], it states that checking $$f(..., x_i, ..., \bar{x}_j, ...) = f(..., \bar{x}_j, ..., x_i, ...)$$ (variables $$x_i$$ and $$x_j$$ are E-symmetric) is equivalent to checking $$f_{x_ix_j} = f_{\bar{x}_i\bar{x}_j}$$. I am having trouble proving this statement.

Using Boole's expansion theorem, we can write Boolean function $$f$$ in $$n$$ variables as:

$$f(..., x_i, ..., x_j, ...) = x_ix_jf_{x_ix_j} + x_i\bar{x}_jf_{x_i\bar{x}_j} + \bar{x}_ix_jf_{\bar{x}_ix_j} + \bar{x}_i\bar{x}_jf_{\bar{x}_i\bar{x}_j}$$

Negating variable $$x_j$$ results in:

\begin{align} f(..., x_i, ..., \bar{x}_j, ...) &= x_i\bar{x}_jf_{x_ix_j} + x_ix_jf_{x_i\bar{x}_j} + \bar{x}_i\bar{x}_jf_{\bar{x}_ix_j} + \bar{x}_ix_jf_{\bar{x}_i\bar{x}_j} &(1) \end{align}

Defining $$f(..., \bar{x}_j, ..., x_i, ...)$$ as the permutation of variable indices $$i$$ and $$j$$ in the above expression (1) results in: \begin{align} f(..., \bar{x}_j, ..., x_i, ...) &= x_j\bar{x}_if_{x_ix_j} + x_jx_if_{x_i\bar{x}_j} + \bar{x}_j\bar{x}_if_{\bar{x}_ix_j} + \bar{x}_jx_if_{\bar{x}_i\bar{x}_j} &(2) \end{align}

which shows that checking $$f(..., x_i, ..., \bar{x}_j, ...) = f(..., \bar{x}_j, ..., x_i, ...)$$ is equivalent to checking $$f_{x_ix_j} = f_{\bar{x}_i\bar{x}_j}$$.

However, following Definition 1 in [1], they define $$f(..., \bar{x}_j, ..., x_i, ...)$$ as $$\bar{x}_j$$ being substituted for $$x_i$$, and $$x_j$$ being substituted for $$x_i$$. This would give:

\begin{align} f(..., \bar{x}_j, ..., x_i, ...) &= \bar{x}_jx_if_{x_ix_j} + \bar{x}_j\bar{x}_if_{x_i\bar{x}_j} + x_jx_if_{\bar{x}_ix_j} + x_j\bar{x}_if_{\bar{x}_i\bar{x}_j} &(3) \end{align}

This causes a problem. As checking $$f(..., x_i, ..., \bar{x}_j, ...) = f(..., \bar{x}_j, ..., x_i, ...)$$ is NOT equivalent to checking $$f_{x_ix_j} = f_{\bar{x}_i\bar{x}_j}$$, as the terms in (1) and (3) containing those cofactors are equal. Instead it is equivalent to checking $$f_{x_i\bar{x}_j} = f_{\bar{x}_ix_j}$$, which is the check for NE-equivalence.

Any guidance would be much appretiated.

Additional clarification on difference. Following Definition 1 in [1], they state:

For example, applying transformation $$\tau=(\bar{x}_2, x_1, x_3, \bar{z})$$ to function $$f(x_1, x_2, x_3) = x_1x_2 + x_2x_3$$ results in a new function $$f\circ\tau=\overline{\bar{x}_2x_1+x_1x_3}$$, which replaces $$x_1$$ with $$\bar{x}_2$$, and $$x_2$$ with $$x_1$$ respectively, while also negating the output.

However, if I follow the rules that were used to get (2) above, the function would be $$f\circ\tau=\overline{x_2\bar{x}_1+\bar{x}_1x_3}$$.

[1] X. Zhou, L. Wang, P. Zhao and A. Mishchenko, "Fast Adjustable NPN Classification using Generalized Symmetries," 2018 28th International Conference on Field Programmable Logic and Applications (FPL), Dublin, Ireland, 2018, pp. 1-16, doi: 10.1109/FPL.2018.00008.