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 \neg x_2) \lor (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.