XOR Using NAND

Create an XOR gate using only NAND gates.
Solution

By definition:

a XOR b = (a OR b) AND NOT(a AND B)

The key is to apply De Morgan's rule repeatedly:

NOT(x OR y) = (NOT x) AND (NOT y)
NOT(x AND y) = (NOT x) OR (NOT y)

and the fact that:

NOT(x AND y) = x NAND y
NOT x = x NAND x

until XOR can be expressed entirely as NOT and NAND operations:

a XOR b
= (a OR b) AND (a NAND b)
= (NOT(NOT(a OR b))) AND (a NAND b)
= (NOT((NOT a) AND (NOT b))) AND (a NAND b)
= ((NOT a) NAND (NOT b)) AND (a NAND b)
= NOT(((NOT a) NAND (NOT b)) NAND (a NAND b))

Chameleons

An isolated population of chameleons was initially divided as follows:

• 13 red chameleons
• 15 green chameleons
• 17 blue chameleons

Each time two different colored chameleons would meet, they would change their color to the third one. For example, if green meets red, they both change their color to blue. Is it ever possible for all chameleons to become the same color? Why or why not?

Solution

To get all the same color, two of the colors must first have the exact same number of chameleons. Then the chameleons would just pair up and eventually all turn into the same color. So for example, we'd have x of color A, x of color B, and y of color C. Going back another step, in order to get x A's and x B's, it would have to be preceded by one of the following:

• x+1 A's, x+1 B's, y-2 C's
  
• x+1 A's, x-2 B's, y+1 C's
• x-2 A's, x+1 B's, y+1 C's

That is, in the step before, there were either the same number of A's and B's, or the difference between A's and B's changed by +/- 3. Since these are all the possible preceeding steps, we can generalize and say that on each step the difference between A's and B's either changes by 0 or 3. So in order to reach equal numbers, we must be able to have:

(C₁ - C₂) mod 3 = [0]

for any two colors C₁ and C₂. Initially, we have:

(A - B) mod 3 = (13 - 15) mod 3 = [1]
(A - C) mod 3 = (13 - 17) mod 3 = [2]
(B - C) mod 3 = (15 - 17) mod 3 = [1]

If any of these can be turned into [0], then we have a way to get all chameleons the same color. However, consider the case where an A and B meet and both change into C:

((A-1) - (B-1)) mod 3 = (A - B) mod 3 = [1]
((A-1) - (C+2)) mod 3 = (A - C - 3) mod 3 = [2]
((B-1) - (C+2)) mod 3 = (B - C - 3) mod 3 = [1]

None of the equations changed! Now what about when B and C meet and change into A:

((A+2) - (B-1)) mod 3 = (A - B + 3) mod 3 = [1]
((A+2) - (C-1)) mod 3 = (A - C + 3) mod 3 = [2]
((B-1) - (C-1)) mod 3 = (B - C) mod 3 = [1]

Still no change! And finally when A and C meet and change into B:

((A-1) - (B+2)) mod 3 = (A - B - 3) mod 3 = [1]
((A-1) - (C-1)) mod 3 = (A - C) mod 3 = [2]
((B+2) - (C-1)) mod 3 = (B - C + 3) mod 3 = [1]

So regardless of what step is taken, all three "(C₁-C₂) mod 3" equations continue to be either [1]or [2]. There is no step that causes any of the equations to be [0], and therefore there is no way to end up with the same number of chameleons.