0
$\begingroup$

What are all the functions $f:\{0,1\}^n\rightarrow\{0,1\}$ that can be expressed as a product of affine Boolean functions? For example, if $x_1,x_2,x_3\in\{0,1\}$ then $x_1x_2x_3\oplus x_2x_3 \oplus x_2=(x_1\oplus x_2)(x_1\oplus 1)(x_3\oplus 1)$. Here $\oplus$ denotes the XOR operation.

I would guess that not any function can be written this way. Has this been worked out? Is there any normal form other than algebraic normal form that uses the XOR (not counting the Fourier transform)?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Well, more-or-less by definition, $f$ is expressible in this form iff $f^{-1}(1)$ (or $f^{-1}(0)$, doesn’t matter) is an affine subspace of $\mathbb F_2^n$. $\endgroup$
    – Emil Jeřábek
    Commented Sep 17, 2021 at 4:20
  • 1
    $\begingroup$ No, sorry, it does matter: $f^{-1}(1)$, not $f^{-1}(0)$. $\endgroup$
    – Emil Jeřábek
    Commented Sep 17, 2021 at 4:29

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.