Why is XOR not linearly separable? Let the function $XOR:\{0,1\} \times \{0,1\} \to \{0,1\}$ be the function defined by
$$\begin{align}
XOR(0,0) &= 0, \\[6pt]
XOR(0,1) &= 1, \\[6pt]
XOR(1,0) &= 1, \\[6pt]
XOR(1,1) &= 0. \\[6pt]
\end{align}$$
Let $\mathcal{H}$ be the set of all linear classifiers on $\Bbb R^2$, where
\begin{align*}
h(x_1,x_2) = 
\begin{cases}
1 & & \text{if} \ ax_1+bx_2+c < 0, \\[6pt]
0 & & \text{if} \ ax_1+bx_2+c \ge  0, \\[6pt]
\end{cases}
\end{align*}
for all $h\in \mathcal{H}$ and for some $a,b,c \in \Bbb R$.

*

*Show that there is no $h \in \mathcal{H}$ such that $h(x_1,x_2)=XOR(x_1,x_2)$ for any $(x_1,x_2) \in \{0,1\} \times \{0,1\}$.


*Show that there are exactly $16$ distinct functions $f:\{0,1\} \times \{0,1\} \to \{0,1\}$.
I have no idea how to start with this problem. Any ideas?
 A: Draw a picture.

The question asks you to show it is not possible to find a half-plane and its complement that separate the blue points where XOR is zero from the red points where XOR is one (in the sense that the former lie in the half-plane and the latter lie in its complement).
One (flawed) attempt is shown here, where the half-plane is shaded in contrast to its complement.  This particular example doesn't work because both the half-plane and its complement each contain one blue point and one red point.
After pondering this a little, you might be inspired to attempt a proof by contradiction: suppose there were numbers $(a,b,c)$ for which the sign of $ax_1 + bx_2 +c$ agreed with the posted values of XOR.  Plugging in all four possibilities for $(x_1,x_2)$ leads to this table.
$$\begin{array}{lcccr}
\text{Location} & x_1 & x_2 & \operatorname{XOR}(x_1,x_2) & a x_1 + b x_2 + c \lt 0? \\
\hline
\text{Bottom left} & 0 & 0 & \color{blue}0 & c \ge 0 \\
\text{Top left} &0 & 1 & \color{red}1 & b + c  \lt 0\\
\text{Bottom right} &1 & 0 & \color{red}1 & a + c  \lt 0\\
\text{Top right} &1 & 1 & \color{blue}0 & a + b + c \ge 0
\end{array}$$
The stated values of XOR determine what the inequalities in the right hand column must be.
If we were to sum the first three inequalities, after rewriting the first as $-c \le 0,$ we would obtain $$a + b + c = (-c) + (b+c) + (a+c) \lt 0,$$ exactly the opposite of the last inequality: there's the contradiction.  It's a simple algebraic way of showing that if the bottom left point were separated from the upper left and bottom right points, then it would also have to be separated from the top right point--but that's exactly the opposite of what we need to separate the values of XOR.

The second question is a simple (and mathematically unrelated) counting problem.  The possible values of $(x_1,x_2)$ designate four points, each of which may take on one of the two values $0$ or $1,$ giving $2^4=16$ possibilities.
If this isn't completely obvious, then it's a worthwhile exercise to write down all sixteen functions.  You can do it with a table of four rows and 18 columns: one column for $x_1,$ another for $x_2,$ and the remaining 16 for the distinct functions.  If you do this systematically, you will notice that those 16 columns correspond to the 16 four-digit binary numbers 0000, 0001, ..., 1111.
You can also depict all 16 functions in the manner of the figure above: take out your crayons; choose two of them; and color the four points in as many distinct ways as possible.

The titles in this figure give some standard names for the functions.  The background shading depicts separating half-planes wherever they exist.
A: *

*Xor(0,0) == 0 implies c >= 0


*Xor(1,1) == 0 implies a+b+c >=0


*Adding these implies that a+b+2c >=0


*Xor(0,1) == 1 implies a + c < 0


*Xor(1,0) == 1 implies b + c < 0


*Adding these implies that a+b+2c <0
So it both has to be >=0 and <0 which is not possible.
PS. The same argument is stated in the accepted answer.
