Xor Not

Hmm....funny how time goes by. Also, I had wrote down my solution to the boolean problem from last time, but then I lost it, and I kept on putting off working it out agian.

Anyway, lets work it out here. First, let us assume that we have managed to construct a series of boolean objects T₀, T₁, T₀₁, T₂₃, and so on, where T₀ is true if exactly 0 of (A,B,C) are true, and T₁₂ is true if exactly 1 or 2 of (A,B,C) are true and so on for the other T's. So there are in principle 16 such objects, we won't be needing them all, but I just wanted to define the general notation.

If we had these objects then we could easily express NOT A as follows:

NOT A = T₀ OR (T₁ AND (B OR C)) OR (T₂ AND B AND C)

We can see this because exactly 1 of T₀, T₁, T₂, T₃ will be true. If T₀ is true, NOT A must be true. If T₁ is true, NOT A will be true if B or C is true, and false otherwise. If T₂ is true, NOT A will only be true if both B and C are true. Finally if T₃ is true, then NOT A is just false. Note also that we can make similar expressions for NOT B and NOT C just by permutation.

Alright, how do we go about constructing as many of these T's as possible without using more than 2 NOT gates? Well, we have some of them for free, namely:

T₃ = A AND B AND C
T₂₃ = (A AND B) OR (A AND C) OR (B AND C)
T₁₂₃ = A OR B OR C

Next, we can make T₀₁, costing us 1 NOT gate:

T₀₁ = NOT T₂₃

T₁ and T₀₁₃ are now available:

T₁ = T₁₂₃ AND T₀₁
T₀₁₃ = T₀₁ OR T₃

and T₁₃

T₁₃ = T₀₁₃ AND T₁₂₃

Finally we can bring out our other NOT gate

T₀₂ = NOT T₁₃

At last we construct T₀ and T₂:

T₀ = T₀₂ AND T₀₁₃
T₂ = T₀₂ AND T₂₃

This completes the construction of T₀, T₁, and T₂, finishing the problem.