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?

*

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