1
$\begingroup$

I am a little confused when it comes to linear boolean functions. According to this post:

What is a simple way of explaining what a linear boolean function means in boolean algebra and relating it to the standard definition of linearity?

We have that a function is linear if: $$f(x \oplus y) = f(x) \oplus f(y)$$

which (again according to the comments in the previously mentioned post) is equivalent to:

$$f(x_1, x_2, ... x_n) = c_0 \oplus c_1x_1 \oplus ... \oplus c_nx_n $$

where multiplication is defined as the logical AND (since wie operate mod 2). Now assume I define the function f as addition with 1, thus:

$$ f(x) = 1 \oplus x $$

This can easily be written in the above mentioned way, namely having $$c_0 = c_1 = 1$$, and thus:

$$ f(x) = 1 \oplus (1 \wedge x_1)$$

Quick double-check: If x = 1:

$$ f(1) = 1 \oplus (1 \wedge 1) = 1 \oplus 1 = 0$$

and if x = 0:

$$ f(0) = 1 \oplus (1 \wedge 0) = 1 \oplus 0 = 1$$

However, if we try to apply the above mentioned definition of linearity, and we set x to 1 and y to 1, we have: $$f(x \oplus y) = f(1 \oplus 1) = f(0) = 1$$ which is NOT the same as: $$f(x) \oplus f(y) = f(1) \oplus f(1) = 0 \oplus 0 = 0$$

Can someone clarify or explain where I am wrong in my thinking?

Thanks :)

Improve this question
$\endgroup$
2
  • $\begingroup$ If a function is linear, then $c_0=0$. The more general solution is for the identity $f(x\oplus y\oplus z)=f(x)\oplus f(y)\oplus f(z)$. $\endgroup$
    – Yuval Filmus
    May 11, 2022 at 13:19
  • $\begingroup$ As is often the case, there is a confusion between linear and affine. $\endgroup$
    – user16034
    May 12, 2022 at 6:40

2 Answers 2

Reset to default
4
$\begingroup$

A function satisfies $f(x \oplus y) = f(x) \oplus f(y)$ for all $x,y$ iff it is of the form $$ f(x) = c_1 x_1 \oplus \cdots \oplus c_n x_n. $$ Indeed, all functions of this form satisfy the identity. Conversely, suppose that $f(x \oplus y) = f(x) \oplus f(y)$. Then $f(0) = f(0 \oplus 0) = f(0) \oplus f(0)$. Now let $e_i$ be the vector $(0,\ldots,0,1,0,\ldots,0)$, where the unique $1$ is in the $i$'th position. Then $$ f(x) = f(x_1 e_1 \oplus \cdots \oplus x_n e_n) = f(x_1 e_1) \oplus \cdots \oplus f(x_n e_n) = x_1 f(e_1) \oplus \cdots \oplus x_n f(e_n), $$ where $f(x_i e_i) = x_i f(e_i)$ holds since if $x_i = 0$ then $f(x_i e_i) = f(0) = 0 = 0 f(e_i)$, and if $x_i = 1$ then $f(x_1 e_i) = f(e_i) = x_i f(e_i)$.

A function satisfies $f(x \oplus y \oplus z) = f(x) \oplus f(y) \oplus f(z)$ for all $x,y,z$ iff it is of the form $$ f(x) = c_0 \oplus c_1 x_1 \oplus \cdots \oplus c_n x_n. $$ Indeed, all functions of this form satisfy the identity. Conversely, let $g(x) = f(x) \oplus f(0)$. Then $$ g(x \oplus y) = f(x \oplus y \oplus 0) \oplus f(0) = f(x) \oplus f(y) \oplus f(0) \oplus f(0) = g(x) \oplus g(y). $$ Thus $g(x) = c_1 x_1 \oplus \cdots \oplus c_n x_n$, and so $f(x)$ is of the required form, with $c_0 = f(0)$.

More generally, if a function satisfies $f(x^{(1)} \oplus \cdots \oplus x^{(m)}) = f(x^{(1)}) \oplus \cdots \oplus f(x^{(m)})$ for even $m \geq 1$, then $f$ is linear; if $m \geq 1$ is odd then $f$ is affine. You can see this by taking $x^{(2)} = \cdots = x^{(m)}$ when $m$ is even, and $x^{(3)} = \cdots = x^{(m)}$ when $m$ is odd.

Improve this answer
$\endgroup$
3
$\begingroup$

From the definition, for any univariate linear function $$f(0)=f(0\oplus 0)=f(0)\oplus f(0)=0.$$

Hence the function $1\oplus a$ is not linear. (In fact, it is affine.)

Improve this answer
$\endgroup$

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.

Not the answer you're looking for? Browse other questions tagged or ask your own question.