# Is there a proof to explain why XOR cannot be linearly separable?

Can someone explain to me with a proof or example why you can't linearly separate XOR (and therefore need a neural network, the context I'm looking at it in)?

I understand why it's not linearly separable if you draw it graphically (e.g. here), but I can't seem to find a formal proof somewhere, I wanted to try and understand it with either an equation or example written down. I'm wondering if one exists (I guess it has to do with contradictions?), but I can't seem to find it? I have seen this, but it's more a reason than a proof.

Before proving that XOR cannot be linearly separable, we first need to prove a lemma:

## Lemma 1

Lemma: If 3 points are collinear and the middle point has a different label than the other two, then these 3 points cannot be linearly separable.

Proof: Let us label the points as point $$A$$, $$B$$, and $$C$$. $$A$$ and $$C$$ have the same label, and $$B$$ has a different label. They are all collinear with line $$\mathcal{L}$$.

Assume the contradiction, so a line can linearly separate $$A$$, $$B$$, and $$C$$. This means a line must cross between segment $$AB$$, and segment $$BC$$ to linearly separate these three points (by definition of linear separability). Let us label the point where the line crosses segment $$AB$$ and point $$Y$$, and the point where the line corsses segment $$BC$$ and point $$Z$$.

However, since segments $$AB$$ and $$BC$$ are collinear to line $$\mathcal{L}$$, points $$Y$$ and $$Z$$ also falls on line $$\mathcal{L}$$. Since only one unique line can cross 2 points, it must be that the only line that passes segments $$AB$$ and $$BC$$ and (therefore separates points $$A$$, $$B$$, and $$C$$) is line $$\mathcal{L}$$.

However, line $$\mathcal{L}$$ cannot linearly separate $$A$$, $$B$$, and $$C$$, since line $$\mathcal{L}$$ also crosses them. Therefore, no line exists can separate $$A$$, $$B$$, and $$C$$.

## Main proof

Consider these 4 points that represent a XOR table. Let us label them clock-wise, so the top-left point as $$A$$, top-right point as $$B$$, bottom-right point as $$C$$, and bottom-left point as $$D$$. So $$A$$ and $$C$$ have the same label, and $$B$$ and $$D$$ have the same label. We want to show that points $$A, B, C$$ and $$D$$ cannot be linearly separable.

Assume the contradiction, and that there is a line that can separate these 4 points.

Imagine a fifth point that lies in the center, and let us label this as point $$E$$.

Since $$E$$ lies in the center, the three points $$A, E$$ and $$C$$ are collinear. Similarly, since $$E$$ lies in the center, the three points $$B, E$$ and $$D$$ are collinear.

Because we assume a line can linearly separate $$A, B, C$$ and $$D$$, then this line must label point $$E$$ as some label. If $$E$$ shares the same label as $$A$$ and $$C$$, then the points $$B, E$$ and $$D$$ will become "collinear points where the middle point has a different label", which by Lemma 1 cannot be linearly separable. Likewise, if $$E$$ shares the same label as $$B$$ and $$D$$, then the points $$A, E$$ and $$C$$ will become "collinear points where the middle point has a different label", which by Lemma 1 cannot be linearly separable.

Therefore it is impossible to give a label to $$E$$ while satisfying linear separability. As a result, our assumption must be false, and the four points $$A, B, C$$ and $$D$$ cannot be linearly separable.

• It may be worth mentioning the perceptron and how it relates to your proof (i.e. is the perceptron only a linear model, i.e. a line?). The original post contained the word "perceptron" in the title, so I guess we're talking about the perceptron here.
– nbro
Dec 17 '20 at 11:38

Is there a proof to explain why $$XOR$$ cannot be linearly separable?
Let us suppose, if possible, that the $$XOR$$ function, given by following table, is linearly separable. $$\begin{array}{|c|c|c|} \hline x& y & x \text{ xor } y\\ \hline 0&0&0\\ \hline 0&1&1\\ \hline 1&0&1\\ \hline 1&1&0\\ \hline \end{array}$$ This ensures the existence of a line $$L:ax+by+c=0$$ such that the points $$(0,0)$$ $$\&$$ $$(1,1)$$ both lie on the same side of $$L$$ and the points $$(0,1)$$ $$\&$$ $$(1,0)$$ also lie on same side of $$L$$ but opposite to that of $$(0,0)$$ $$\&$$ $$(1,1).$$
Also from basic coordinate geometry, we know that if the points $$(x_1,y_1)$$ $$\&$$ $$(x_2,y_2)$$ lie on same side of a line given by $$px+qy+r=0$$ then, $$(px_1+qy_1+r)\cdot(px_2+qy_2+r)>0$$ and if they are on opposite sides of the line then, $$(px_1+qy_1+r)\cdot(px_2+qy_2+r)<0$$ Since $$(0,0)$$ and $$(1,1)$$ lie on same side of $$L$$, so $$$$c\cdot(a+b+c)>0 \tag{1}$$$$ And, as $$(1,0)$$ and $$(1,1)$$ lie on different sides of $$L$$, so $$$$(a+c)\cdot(a+b+c)<0. \tag{2}$$$$ Similarly as $$(0,1)$$ and $$(1,1)$$ lie on different sides of $$L$$, $$$$(b+c)\cdot(a+b+c)<0 \tag{3}$$$$ On adding equations $$(2)$$ and $$(3)$$ we get, $$(a+b+2c)\cdot(a+b+c)<0$$ $$\implies (a+b+c)\cdot(a+b+c)+c\cdot(a+b+c)<0$$ $$\implies (a+b+c)^2+c\cdot(a+b+c)<0$$ Since $$(a+b+c)^2\geq0$$ for any choice of numbers $$a,b,c,$$ so $$c\cdot(a+b+c)<-(a+b+c)^2\leq0$$ $$c\cdot(a+b+c)<0$$ which is a contradiction of equation $$(1)$$, proving the non-existence any such line $$L.$$
The $$XOR$$ function is not linearly separable.