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.

Not Not

Blogging sure slows down when my life is consumed with marking.

Anyway, heres a new one that was told to me by some people in the math room on KGS:

You have 3 boolean inputs, A, B, and C. You are to set up a circut that has 3 outputs, D, E, and F. You may use as many AND and OR gates as you like, but only 2 NOT gates. Arrange it so that D has the value of NOT A, E has the value of NOT B, and F has the value of NOT C, for arbitrary inputs of A, B, and C.

To put that into a bit more "math" and less "circutry"...give me expressions for NOT A, NOT B, and NOT C, if you can only use NOT twice. You may store variables and use them freely, but you may only call the NOT operator a total of 2 times. For example, you could define P = NOT (A OR B) and then use P as much as you like and that would only count as 1 use of a NOT gate.

For a more general version of the problem, you have 2n+1 inputs to negate, and only n+1 uses of NOT. The general version is fairly tough though, and not very fun.