Four inequalities that cannot all hold

STATEMENT

Prove that no perceptron computes XOR on $\{0,1\}^2$, by writing the four requirements as inequalities in $(w_1, w_2, b)$ and showing they are jointly inconsistent.

GIVEN

The XOR function:

A perceptron predicts $1$ when $w_1x_1 + w_2x_2 + b > 0$ and $0$ otherwise.

FIND

Either parameters that work, or a proof that none exist.

STRATEGY

Substitute each of the four inputs to turn the truth table into four linear inequalities. Then add pairs of them to derive a contradiction — the point being that this is ordinary algebra, not an appeal to geometry or intuition.

SOLUTION

Step 1 — write the four requirements. Substituting each row:

Step 2 — add (2) and (3). Adding two strict inequalities of the same direction is legal and preserves strictness:

$w_1 + w_2 + 2b > 0 \qquad (5)$

Step 3 — combine with (4). From (4), $w_1 + w_2 \le -b$. Substituting that upper bound into (5):

$0 < w_1 + w_2 + 2b \le (-b) + 2b = b$

so $b > 0$.

Step 4 — the contradiction. Step 3 concludes $b > 0$. Requirement (1) says $b \le 0$. Both cannot hold. Therefore no $(w_1, w_2, b)$ satisfies all four, and no perceptron computes XOR. $\blacksquare$

Why this is stronger than “training fails”. Nothing here mentions an algorithm, an initialisation, a learning rate, or a quantity of data. The inequalities describe every perceptron that could ever exist. The failure is a property of the hypothesis class $\mathcal{F}$ of Definition 3 in Chapter I.1 — XOR is simply not in it.

The geometric reading. The two positive points $(0,1)$ and $(1,0)$ lie on one diagonal of the unit square; the two negatives $(0,0)$ and $(1,1)$ lie on the other. The diagonals cross. Any straight line separating one diagonal’s endpoints must pass between them, and therefore also separates the other diagonal’s endpoints — putting one negative on each side. The algebra above is that picture with the geometry removed.

Check — sanity

The proposed three-dimensional solution works. With the extra feature $x_3 = x_1x_2$ and $(1, 1, -2, -0.5)$:

All four correct. So the impossibility really is about the representation and not about XOR being hard.

Three of the four are satisfiable. Drop requirement (4) and $(w_1,w_2,b) = (1,1,-0.5)$ satisfies (1), (2), (3). This confirms the contradiction genuinely needs all four rows, rather than arising from a slip in transcribing one of them.

AND and OR are fine. AND: $(1,1,-1.5)$. OR: $(1,1,-0.5)$. So the perceptron is not simply weak — it computes fourteen of the sixteen Boolean functions of two variables. XOR and its negation are the exceptions.