Examples and Intuitions II — Building XNOR with a Hidden Layer

Complex Logical Gates with Neural Networks

Implementing XNOR

The logical XNOR operator outputs 1 when:

• $x_1 = 0$ and $x_2 = 0$, or
• $x_1 = 1$ and $x_2 = 1$

In other words, when both inputs are the same.

$$(x_1 \land x_2) \lor (\neg x_1 \land \neg x_2)$$

A single neuron cannot represent XNOR.
We need a hidden layer.

$x_1$	$x_2$	Result
0	0	1
1	0	0
0	1	0
1	1	1

Network Architecture

$$\begin{bmatrix} x_0 \\ x_1 \\ x_2 \end{bmatrix} \rightarrow \begin{bmatrix} a^{(2)}_1 \\ a^{(2)}_2 \end{bmatrix} \rightarrow a^{(3)} \rightarrow h_\Theta(x)$$

Where:

• Hidden unit 1 implements AND
• Hidden unit 2 implements NOR
• Output layer implements OR

First Layer (AND + NOR)

We combine AND and NOR into one matrix:

$$\Theta^{(1)} = \begin{bmatrix} -30 & 20 & 20 \\ 10 & -20 & -20 \end{bmatrix}$$

This gives:

$$a^{(2)} = g(\Theta^{(1)} x)$$

So the hidden layer computes:

• $a^{(2)}_1$ behaves like AND
• $a^{(2)}_2$ behaves like NOR

Second Layer (OR)

The output layer computes: $\text{OR}(\text{AND}, \text{NOR})$

Now we combine the hidden outputs using OR:

$$\Theta^{(2)} = \begin{bmatrix} -10 & 20 & 20 \end{bmatrix}$$

This gives:

$$a^{(3)} = g(\Theta^{(2)} a^{(2)})$$

Final hypothesis:

$$h_\Theta(x) = a^{(3)}$$

Full Computation

The forward propagation is:

$$a^{(2)} = g(\Theta^{(1)} x)$$ $$a^{(3)} = g(\Theta^{(2)} a^{(2)})$$ $$h_\Theta(x) = a^{(3)}$$

---

Key Insight

• Single logistic neuron → can model AND, OR, NOR
• Cannot model XOR or XNOR
• Adding one hidden layer enables nonlinear decision boundaries

This is the first concrete example of why hidden layers matter.

---

Modern Relevance

The XNOR example proves the critical point: a single neuron cannot model XOR/XNOR (non-linearly separable problems), but one hidden layer can. This is why deep networks exist.

Scaled to production:

• Depth = compositionality. GPT-4 uses 96+ transformer layers. Each layer transforms the representation of each token, progressively building from low-level patterns (word co-occurrence in early layers) to abstract semantics (reasoning over concepts in late layers). The hidden layer in XNOR is the toy version of this representation building.
• Why depth beats width. You can approximate any function with one wide hidden layer (universal approximation theorem) but you need exponentially more neurons than a deeper network. This is why modern LLMs are deep (80–128 layers) rather than just wide. The XNOR proof hints at this — the two-layer solution is more parameter-efficient than any single-layer alternative.
• ReLU and non-linearity. The sigmoid used here is replaced by GeLU in modern transformers. The shape is different but the role is identical: introduce non-linearity between affine transformations. Without any activation function, stacking layers collapses to a single linear transformation — the key mathematical reason non-linearity is not optional.

The Θ matrices with their carefully chosen integer weights here become 4096×4096 weight matrices learned by gradient descent over trillions of tokens — but the role they play is the same: compute a non-linear decision function that no shallower architecture could represent.

---

Related Posts

• Examples and Intuitions I — the simpler single-layer gates this XNOR example builds on
• Multiclass Classification with Neural Networks — generalizing from binary XNOR to multiple output classes