Logic Gates Solution

Look at the third diagram. The top and bottom paths are the same, but they lead to different outputs going in to the XOR gate. The two purple inputs are therefore different (without loss of generality, 0 and 1). So we may mark:

Importantly, this means blue disagrees on inputs 0,0 and 1,1 (as it sends the former to X and the latter to 1–X), while similarly green sends X,X to Y and 1–X,1–X to 1–Y. In particular, both blue and green are “preservation gates”: they cannot be XOR, EQ, ZERO or ONE.

Now, consider the second diagram. The top and bottom paths both end with a 0, as the OR gate outputs a 0. Since green is a preservation gate, the two red gates take different inputs. Thus we have:

Notice that red sends both Z,Z and 1–Z,1–Z to 0, and that the only gates with this property are XOR and ZERO. Per the fourth diagram, red is not identically 0, and so red is in fact XOR.

Turn to the fourth and fifth diagrams. The green and blue gates agree on some pair of inputs (from the fifth diagram), so they are neither an OR/NOR pair nor an AND/NAND pair. They disagree on some input (from the fourth diagram), so they are not the same gate. In the fifth diagram, the inputs must be distinct (otherwise we recover the fourth diagram). We therefore have:

In fact, the fourth diagram tells us something stronger: the green and blue gates disagree on 0,0 or 1,1. This is not true of the OR/AND pairs, nor is it true of NOR/NAND. This leaves the table:

We may now test the four remaining combinations against the first diagram.

Only one of these combinations works, so this must be our solution: the red gate is XOR, green is NAND, and blue is OR!