NOT Puzzle Solution

Edited 2012/08/16: Updated problem attribution.

Last week, I closed with a puzzle: "Invert three inputs using only two NOT gates." I should start off by pointing out that I cannot take credit for this problem; it dates back to at least the 70s and was featured in HAKMEM by Richard Schroeppel. I myself learned about it via Clive Maxfield. I'm also told that Guy Steele beat me to the generalization to n case, however I cannot verify this, and the solution presented here is entirely my own.

The solutions that follow are just two of many possible ways of looking at this. Structurally, they are by no means the simplest solutions, but I find them to be conceptually the simplest. If you haven't tried to solve the puzzle yet I heartily recommend it; it makes knowing the solution so much more rewarding if you have.

Solution for 3 inputs

My solution to this puzzle involves reasoning on the number of inputs with value '1'. If none of the inputs are 1s, then all the outputs must be, and vice versa. To do this, we create a set of temporary variables with the goal of knowing exactly how many inputs were 1.

3 := A ∧ B ∧ C
2or3 := (A ∧ B) ∨ (B ∧ C) ∨ (A ∧ C)
0or1 := ¬ 2or3
1 := 0or1 ∧ (A ∨ B ∨ C)
0or2 := ¬ (1 ∨ 3)
0 := 0or1 ∧ 0or2
2 := 0or2 ∧ 2or3

From here we can just build our outputs directly:

X = 0 ∨ (1 ∧ (B ∨ C)) ∨ (2 ∧ (B ∧ C))
Y = 0 ∨ (1 ∧ (A ∨ C)) ∨ (2 ∧ (A ∧ C))
Z = 0 ∨ (1 ∧ (A ∨ B)) ∨ (2 ∧ (A ∧ B))

Solution for n inputs

This proof sketch is for odd n. If n is even, just invert the last input directly with a NOT, and use this pattern for the first n-1.

As before, we are going to reason on how many inputs (I₁ to I_n) were 1. For this we will use a bit more syntax: {a-b} means anywhere from a to b inputs (inclusive) were 1, and {a, b} means either a or b inputs were 1, with no other possibilities allowed. First, we can generate all the ranges ending in n directly:

{1-n} := (I₁ ∨ I₂ ∨ … ∨ I_n)
{2-n} := ((I₁ ∧ I₂) ∨ (I₁ ∧ I₃) ∨ … ∨ (I_n-1 ∧ I_n))
…
{n-n} := (I₁ ∧ I₂ ∧ … ∧ I_n)

Clearly, this doesn't need any NOTs. Next, we are going to make all the ranges starting in 0 and ending in an odd number:

{0-1} := ¬ {2-n}
{0-3} := ¬ {4-n}
…
{0-(n-2)} := ¬{(n-1)-n}

This requires (n-1)/2 NOT gates. Using these together, we can have variables for all the odd numbers of inputs directly:

1 := {0-1} ∧ {1-n}
3 := {0-3} ∧ {3-n}
…
n-2 := {0-(n-2)} ∧ {(n-2)-n}
n := {n-n}

Again, this doesn't require any NOTs. Lastly, we use one more NOT to let us get all the even values:

{0,2,4,…,(n-1)} := ¬ (1 ∨ 3 ∨ … ∨ n)

0 := {0-1} ∧ {0,2,4,…,(n-1)}
2 := {0-3} ∧ {0,2,4,…,(n-1)} ∧ {2-n}
4 := {0-5} ∧ {0,2,4,…,(n-1)} ∧ {4-n}
…
n-1 := {0,2,4,…,(n-1)} ∧ {(n-1)-n}

There! Now we have a variable for each possible number of inputs with value 1, so we can just plug in all possibilities to get our outputs:

O₁ = 0 ∨ (1 ∧ (I₂ ∨ I₃ ∨ … ∨ I_n)) ∨ … ∨ (n-1 ∧ (I₂ ∧ I₃ ∧ … ∧ I_n))
O₂ = 0 ∨ (1 ∧ (I₁ ∨ I₃ ∨ … ∨ I_n)) ∨ … ∨ (n-1 ∧ (I₁ ∧ I₃ ∧ … ∧ I_n))
…
O_n = 0 ∨ (1 ∧ (I₁ ∨ I₂ ∨ … ∨ I_n-1)) ∨ … ∨ (n-1 ∧ (I₁ ∧ I₁ ∧ … ∧ I_n-1))

As you have seen, this took a total of (n-1)/2 + 1 NOT gates. Since n is odd, (n-1)/2 + 1 = ⌊n/2⌋ + 1, and we're done! Whew, I wouldn't want to implement that.