Answers.Body: <p>Here is a similar contradiction based answer using <strong>basic coordinate geometry</strong>.</p>
  <blockquote>
  <p>Is there a proof to explain why <span class="math-container">$XOR$</span> cannot be linearly separable?</p>
  </blockquote>
  <p>Let us suppose, if possible, that the <span class="math-container">$XOR$</span> function, given by following table, is linearly separable.
  <span class="math-container">\begin{array}{|c|c|c|}
  \hline
    x&amp; y &amp; x \text{ xor } y\\ 
  \hline
     0&amp;0&amp;0\\
  \hline
     0&amp;1&amp;1\\
  \hline
    1&amp;0&amp;1\\
  \hline
     1&amp;1&amp;0\\
  \hline
  \end{array}</span>
  This ensures the existence of a line <span class="math-container">$L:ax+by+c=0$</span> such that the points <span class="math-container">$(0,0)$</span> <span class="math-container">$\&amp;$</span> <span class="math-container">$(1,1)$</span> both lie on the same side of <span class="math-container">$L$</span> and the points <span class="math-container">$(0,1)$</span> <span class="math-container">$\&amp;$</span> <span class="math-container">$(1,0)$</span> also lie on same side of <span class="math-container">$L$</span> but opposite to that of <span class="math-container">$(0,0)$</span> <span class="math-container">$\&amp;$</span> <span class="math-container">$(1,1).$</span><br />
  Also from basic coordinate geometry, we know that if the points <span class="math-container">$(x_1,y_1)$</span> <span class="math-container">$\&amp;$</span> <span class="math-container">$(x_2,y_2)$</span> lie on same side of a line given by <span class="math-container">$px+qy+r=0$</span> then,
  <span class="math-container">$$(px_1+qy_1+r)\cdot(px_2+qy_2+r)&gt;0$$</span>
  and if they are on opposite sides of the line then,
  <span class="math-container">$$(px_1+qy_1+r)\cdot(px_2+qy_2+r)&lt;0$$</span>
  Since <span class="math-container">$(0,0)$</span> and <span class="math-container">$(1,1)$</span> lie on same side of <span class="math-container">$L$</span>, so
  <span class="math-container">\begin{equation}
  c\cdot(a+b+c)&gt;0
  \tag{1}
  \end{equation}</span>
  And, as <span class="math-container">$(1,0)$</span> and <span class="math-container">$(1,1)$</span> lie on different sides of <span class="math-container">$L$</span>, so
  <span class="math-container">\begin{equation}
  (a+c)\cdot(a+b+c)&lt;0.
  \tag{2}
  \end{equation}</span>
  Similarly as  <span class="math-container">$(0,1)$</span> and <span class="math-container">$(1,1)$</span> lie on different sides of <span class="math-container">$L$</span>,
  <span class="math-container">\begin{equation}
  (b+c)\cdot(a+b+c)&lt;0
  \tag{3}
  \end{equation}</span>
  On adding equations <span class="math-container">$(2)$</span> and <span class="math-container">$(3)$</span> we get,
  <span class="math-container">$$(a+b+2c)\cdot(a+b+c)&lt;0$$</span>
  <span class="math-container">$$\implies (a+b+c)\cdot(a+b+c)+c\cdot(a+b+c)&lt;0$$</span>
  <span class="math-container">$$\implies (a+b+c)^2+c\cdot(a+b+c)&lt;0$$</span>
  Since <span class="math-container">$(a+b+c)^2\geq0$</span> for any choice of numbers <span class="math-container">$a,b,c,$</span> so
  <span class="math-container">$$c\cdot(a+b+c)&lt;-(a+b+c)^2\leq0$$</span>
  <span class="math-container">$$c\cdot(a+b+c)&lt;0$$</span>
  which is a contradiction of equation <span class="math-container">$(1)$</span>, proving the non-existence any such line <span class="math-container">$L.$</span></p>
  <blockquote>
  <p>The <span class="math-container">$XOR$</span> function is not linearly separable.</p>
  </blockquote>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-06-07T14:02:20.013Z
Answers.LastActivityDate: 2021-10-02T20:58:05.527Z
Answers.LastEditDate: 2021-10-02T20:58:05.527Z
Answers.UserDisplayName: Toshant Narula
Answers.Body: <p>Before proving that XOR cannot be linearly separable, we first need to prove a  lemma:</p>
  <h2>Lemma 1</h2>
  <p><strong>Lemma:</strong> 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.</p>
  <p><a href="https://i.sstatic.net/0Uzig.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/0Uzig.png" alt="enter image description here" /></a></p>
  <p><strong>Proof:</strong> Let us label the points as point <span class="math-container">$A$</span>, <span class="math-container">$B$</span>, and <span class="math-container">$C$</span>. <span class="math-container">$A$</span> and <span class="math-container">$C$</span> have the same label, and <span class="math-container">$B$</span> has a different label. They are all collinear with line <span class="math-container">$\mathcal{L}$</span>.</p>
  <p>Assume the contradiction, so a line can linearly separate <span class="math-container">$A$</span>, <span class="math-container">$B$</span>, and <span class="math-container">$C$</span>. This means a line must cross between segment <span class="math-container">$AB$</span>, and segment <span class="math-container">$BC$</span> to linearly separate these three points (by definition of linear separability). Let us label the point where the line crosses segment <span class="math-container">$AB$</span> and point <span class="math-container">$Y$</span>, and the point where the line corsses segment <span class="math-container">$BC$</span> and point <span class="math-container">$Z$</span>.</p>
  <p>However, since segments <span class="math-container">$AB$</span> and <span class="math-container">$BC$</span> are collinear to line <span class="math-container">$\mathcal{L}$</span>, points <span class="math-container">$Y$</span> and <span class="math-container">$Z$</span> also falls on line <span class="math-container">$\mathcal{L}$</span>. Since only one unique line can cross 2 points, it must be that the only line that passes segments <span class="math-container">$AB$</span> and <span class="math-container">$BC$</span> and (therefore separates points <span class="math-container">$A$</span>, <span class="math-container">$B$</span>, and <span class="math-container">$C$</span>) is line <span class="math-container">$\mathcal{L}$</span>.</p>
  <p>However, line <span class="math-container">$\mathcal{L}$</span> cannot linearly separate <span class="math-container">$A$</span>, <span class="math-container">$B$</span>, and <span class="math-container">$C$</span>, since line <span class="math-container">$\mathcal{L}$</span> also crosses them. Therefore, no line exists can separate <span class="math-container">$A$</span>, <span class="math-container">$B$</span>, and <span class="math-container">$C$</span>.</p>
  <h2>Main proof</h2>
  <p><a href="https://i.sstatic.net/G7g23.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/G7g23.png" alt="enter image description here" /></a></p>
  <p>Consider these 4 points that represent a XOR table. Let us label them clock-wise, so the top-left point as <span class="math-container">$A$</span>, top-right point as <span class="math-container">$B$</span>, bottom-right point as <span class="math-container">$C$</span>, and bottom-left point as <span class="math-container">$D$</span>. So <span class="math-container">$A$</span> and <span class="math-container">$C$</span> have the same label, and <span class="math-container">$B$</span> and <span class="math-container">$D$</span> have the same label. We want to show that points <span class="math-container">$A, B, C$</span> and <span class="math-container">$D$</span> cannot be linearly separable.</p>
  <p>Assume the contradiction, and that there is a line that can separate these 4 points.</p>
  <p>Imagine a fifth point that lies in the center, and let us label this as point <span class="math-container">$E$</span>.</p>
  <p>Since <span class="math-container">$E$</span> lies in the center, the three points <span class="math-container">$A, E$</span> and <span class="math-container">$C$</span> are collinear. Similarly, since <span class="math-container">$E$</span> lies in the center, the three points <span class="math-container">$B, E$</span> and <span class="math-container">$D$</span> are collinear.</p>
  <p>Because we assume a line can linearly separate <span class="math-container">$A, B, C$</span> and <span class="math-container">$D$</span>, then this line must label point <span class="math-container">$E$</span> as some label. If <span class="math-container">$E$</span> shares the same label as <span class="math-container">$A$</span> and <span class="math-container">$C$</span>, then the points <span class="math-container">$B, E$</span> and <span class="math-container">$D$</span> will become &quot;collinear points where the middle point has a different label&quot;, which by Lemma 1 cannot be linearly separable. Likewise, if <span class="math-container">$E$</span> shares the same label as <span class="math-container">$B$</span> and <span class="math-container">$D$</span>, then the points <span class="math-container">$A, E$</span> and <span class="math-container">$C$</span> will become &quot;collinear points where the middle point has a different label&quot;, which by Lemma 1 cannot be linearly separable.</p>
  <p>Therefore it is impossible to give a label to <span class="math-container">$E$</span> while satisfying linear separability. As a result, our assumption must be false, and the four points <span class="math-container">$A, B, C$</span> and <span class="math-container">$D$</span> cannot be linearly separable.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-17T11:38:09.460Z
Answers.Text: 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.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-12-17T02:49:24.000Z
Answers.LastActivityDate: 2020-12-17T09:57:04.130Z
Answers.LastEditDate: 2020-12-17T09:57:04.130Z
Answers.UserDisplayName: user3667125
Body: <p>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)?</p>
  <p>I understand why it's not linearly separable if you draw it graphically (e.g. <a href="https://medium.com/@lucaspereira0612/solving-xor-with-a-single-perceptron-34539f395182" rel="noreferrer">here</a>), 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 <a href="https://ai.stackexchange.com/q/16291/2444">this</a>, but it's more a reason than a proof.</p>
  
Tags: <proofs><perceptron><xor-problem>
Title: Is there a proof to explain why XOR cannot be linearly separable?
UserDisplayName: Slowat_Kela
ThreadText: # Is there a proof to explain why XOR cannot be linearly separable?
  
  (Asked by: username_0 on 2020-12-16)
  
  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](https://medium.com/@lucaspereira0612/solving-xor-with-a-single-perceptron-34539f395182)), 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](https://ai.stackexchange.com/q/16291/2444), but it's more a reason than a proof.
  
  **Tags:** proofs, perceptron, xor-problem
  
  ---
  
  ## 2 answers
  
  ### Answer by username_2 on 2020-12-17. Score: 4 | Accepted answer
  
  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.
  
  [![enter image description here](https://i.sstatic.net/0Uzig.png)](https://i.sstatic.net/0Uzig.png)
  
  **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
  
  [![enter image description here](https://i.sstatic.net/G7g23.png)](https://i.sstatic.net/G7g23.png)
  
  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.
  
  > **Comments:**
  > **username_3**: 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.  
  
  ---
  
  ### Answer by username_1 on 2021-06-07. Score: 3
  
  Here is a similar contradiction based answer using **basic coordinate geometry**.
  
  > 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
  \begin{equation}
  c\cdot(a+b+c)>0
  \tag{1}
  \end{equation}
  And, as $(1,0)$ and $(1,1)$ lie on different sides of $L$, so
  \begin{equation}
  (a+c)\cdot(a+b+c)<0.
  \tag{2}
  \end{equation}
  Similarly as $(0,1)$ and $(1,1)$ lie on different sides of $L$,
  \begin{equation}
  (b+c)\cdot(a+b+c)<0
  \tag{3}
  \end{equation}
  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.
  
  
  ---
  
  