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.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.