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?

Question

I was reading notes on computability theory when I came across the term "Linearity" which I was not familiar with, in the context of boolean functions. I am quite comfortable what linear maps mean in Vector Spaces (say in the context of linear algebra and functional analysis) but I had never seen this term being used in the context of boolean functions. In those other contexts it roughly means the following equation is true:

$$ f(x+y) = f(x) + f(y) $$

however, when I went to wikipedia to find out what linearity means for boolean functions I came across a weird paragraph that seem to define it but didn't seem to have a clear succinct way to define linear functions or its relations to the more standard way of defining linearity.

Can someone explain to me how the definition from wikipedia relates to the more traditional way of defining linearity over Vector Spaces? In other words, why is the detailed definition on wikipedia the way it is?

---

For ease, here is wikipedia's definition:

In Boolean algebra, a linear function is a function ${\displaystyle f}$ for which there exist $ {\displaystyle a_{0},a_{1},\ldots ,a_{n}\in\{0,1\}} a_0, a_1, \ldots, a_n \in \{0,1\} $ such that:

$$ f(b_1, \ldots, b_n) = a_0 \oplus (a_1 \land b_1) \oplus \cdots \oplus (a_n \land b_n), \text{ where } {\displaystyle b_{1},\ldots ,b_{n}\in \{0,1\}.} b_1, \ldots, b_n \in \{0,1\}. $$

A Boolean function is linear if one of the following holds for the function's truth table:

-> In every row in which the truth value of the function is 'T', there are an odd number of 'T's assigned to the arguments and in every row in which the function is 'F' there is an even number of 'T's assigned to arguments. Specifically, f('F', 'F', ..., 'F') = 'F', and these functions correspond to linear maps over the Boolean vector space.

-> In every row in which the value of the function is 'T', there is an even number of 'T's assigned to the arguments of the function; and in every row in which the truth value of the function is 'F', there are an odd number of 'T's assigned to arguments. In this case, f('F', 'F', ..., 'F') = 'T'. Another way to express this is that each variable always makes a difference in the truth-value of the operation or it never makes a difference.

Answer 1

Linearity for boolean functions means exactly linearity over a vector space.

Consider the field $\mathbb{F}_2$, i.e., the field with two elements $\{0,1\}$. Here the "addition" is addition modulo 2, i.e., exclusive xor (xor).

A vector space $V$ over this field is basically a vector of $n$ elements of $\mathbb{F}_2$. The "sum" of two vectors $v+w$ is obtained by taking the component-wise "sum", i.e., the xor of these two vectors. In this way you can think of the space $\{0,1\}^n$ as a vector space over $\mathbb{F}_2$: just identify $\{0,1\}^n$ as the set of $n$-vectors over $\mathbb{F}_2$, so it becomes a $n$-dimensional vector space.

Now a boolean function $f:\{0,1\}^n\to \{0,1\}$ is considered linear iff it is a linear function from the vector space $\{0,1\}^n$ to the vector space $\{0,1\}$. This amounts to saying that

$$f(x_1,\dots,x_n) = c_1 x_1 \oplus c_2 x_2 \oplus \cdots \oplus c_n x_n.$$

Here $\oplus$ represents the xor operation.

Why is this equivalent to the usual definition over vector spaces? Recall from linear algebra that if $f:V \to W$ from vector space $V$ to vector space $W$, then it can be represented as multiplication by a $k \times \ell$ matrix, where $k = \dim V$ and $\ell = \dim W$. Here we have a map $f: \{0,1\}^n \to \{0,1\}$, and $\dim \{0,1\}^n = n$, so $f$ can be represented as multiplication by a $n \times 1$ matrix. Here everything is over the field $\mathbb{F}_2$, so you have to replace the usual addition and multiplication with addition and multiplication modulo 2. Multiplication by the matrix $[c_1 c_2 \cdots c_n]$ is equivalent to the definition above, so we obtain the equivalence.

Caveat: linear vs affine. If we have $f:V \to W$, a linear function is one that can be represented as

$$f(x) = Mx$$

where $M$ is some matrix. An affine function is one that can be represented as

$$f(x) = Mx+c$$

where $M$ is some matrix and $c$ is some vector. A linear function has the property that $f(x)+f(y)=f(x+y)$. An affine function does not; but it does satisfy the property that $f(x-y+z)=f(x)-f(y)+f(z)$.

Wikipedia's definition claims to be a definition of a linear function, but it's really a definition of an affine function. Sometimes people don't distinguish between linear vs affine (they consider both of them to be linear functions). That can be a bit confusing, especially if you're just learning these concepts. Unfortunately, Wikipedia seems to be one of those places that has lumped both concepts under the name "affine".

In your context, a boolean function $f:\{0,1\}^n\to \{0,1\}$ is affine iff it is a linear function from the vector space $\{0,1\}^n$ to the vector space $\{0,1\}$. This amounts to saying that

$$f(x_1,\dots,x_n) = c_1 x_1 \oplus c_2 x_2 \oplus \cdots \oplus c_n x_n \oplus c_0.$$

The difference between linear vs affine is the extra constant term ($\oplus c_0$) that can appear in an affine function. When Wikipedia provides its definition of a linear function, it is really providing a definition of an affine function. I guess that implicitly Wikipedia is using the word "linear" to include both concepts. Anyway, as long as you understand this little detail, all of the standard machinery of linear algebra applies.

See also https://en.wikipedia.org/wiki/Affine_transformation#Over_a_finite_field.