4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ sorry I'm still confused. If things are exactly the same wouldn't the definition of linearity of boolean functions just be $f(x \oplus y) = f(x) \oplus f(y)$ ? Or a I missing something? I also don't understand where the $c_i$'s are coming from in your definition of linearity. It seems really strange to me. Sorry if its obvious to you. $\endgroup$ – Charlie Parker Mar 15 '17 at 23:43
  • $\begingroup$ @CharlieParker, that is a valid definition. It's equivalent to the other definition shown in my answer: those are two alternative definitions that are equivalent. Where are the $c$'s coming from? They are the elements of the matrix. That's why I mentioned that every linear function can be expressed as multiplication by a matrix. Those are two equivalent definitions of a linear function: (1) defn 1: a function $f$ is linear if $f(x \oplus y) = f(x \oplus y)$; (2) defn 2: a function $f$ is linear if there's a matrix $M$ such that $f(x)=Mx$. $f$ satisfies (1) iff it satisfies (2). $\endgroup$ – D.W. Mar 16 '17 at 5:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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