Using analog values with Algebraic Normal Form?

Question

Algebraic normal form (ANF) is a way of describing digital circuits made up of AND and XOR gates.

The below is an example of an ANF expression which evaluates to true if two or more of it's three inputs are true ($\oplus$ being XOR, implicit multiplication being AND)

$x_0x_1 \oplus x_0x_2 \oplus x_1x_2$

When a digital circuit is expressed this way, you can evaluate it as a polynomial, taking 1 or 0 as inputs for the variables, doing a multiplication for an AND gate, addition for an XOR gate, and doing a modulus by 2 on the final result.

$y = x_0x_1 + x_0x_2 + x_1x_2$

you can verify a truth table by plugging in 0s and 1s for the various $x$ parameters and seeing that it comes out to the correct values.

What I'm curious about is what if we don't use whole numbers? I'm sure that's a well studied thing but I haven't been able to find any information about it.

it seems sort of like fuzzy logic, but fuzzy logic is a well defined thing with different operations.

Here's some values plugged in and their output.

\begin{array}{|c|c|c|c|} \hline x_0 & x_1 & x_2 & output & output \% 2 \\ \hline 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 3 & 1 \\ 0.5 & 0.5 & 0 & 0.25 & 0.25\\ 0.9 & 0.9 & 0.9 & 2.43 & 0.43 \\ 1.0 & 1.0 & 0.5 & 2.0 & 0.0 \\ \hline \end{array}

The analog value input gives output that seems especially wrong in the last two rows.

It seems like maybe this just "doesn't work", but it also feels like maybe it does work, or does do something interesting, perhaps with some modifications?

Has anyone come across non digital values used in ANF or similar?

Thanks!

Answer 1

Perhaps the most appropriate way of thinking of algebraic normal form is as the following statement:

Every function from $\mathbb{Z}_2^n$ to $\mathbb{Z}_2$ can be represented uniquely as a multilinear polynomial.

Here $\mathbb{Z}_2$ is the field with two elements, and a polynomial is multilinear if all monomials are products of distinct variables (so you can't have $x_i^2$ in a monomial).

The upshot is that the modulo 2 operation is not the most natural way of understanding the computation involved in algebraic normal form; rather, addition is done over the field $\mathbb{Z}_2$. It seems rather unnatural to apply the modulo 2 operation to real numbers in this context.

One generalization of algebraic normal form to real numbers is the Fourier expansion over the Boolean cube:

Every function from $\{-1,1\}^n$ to $\mathbb{R}$ can be represented uniquely as a multilinear polynomial (with real coefficients).

Here $\mathbb{R}$ is the field of real numbers.

Another generalization is the Hermite expansion in Gaussian space:

Every function from $\mathbb{R}^n$ to $\mathbb{R}$ can be approximated arbitrarily well by a polynomial (with real coefficients).

Here arbitrarily well means up to $\epsilon$ distance in $L^2$ with respect to Gaussian measure (e.g., see this Wikipedia article).