# Clarification regarding linear boolean functions!

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 :)

• 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)$. May 11, 2022 at 13:19
• As is often the case, there is a confusion between linear and affine.
– user16034
May 12, 2022 at 6:40

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.
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.)