Anyway, lets work it out here. First, let us assume that we have managed to construct a series of boolean objects T

_{0}, T

_{1}, T

_{01}, T

_{23}, and so on, where T

_{0}is true if exactly 0 of (A,B,C) are true, and T

_{12}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_{0}OR (T_{1}AND (B OR C)) OR (T_{2}AND B AND C)

We can see this because exactly 1 of T

_{0}, T

_{1}, T

_{2}, T

_{3}will be true. If T

_{0}is true, NOT A must be true. If T

_{1}is true, NOT A will be true if B or C is true, and false otherwise. If T

_{2}is true, NOT A will only be true if both B and C are true. Finally if T

_{3}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_{3}= A AND B AND C

T_{23}= (A AND B) OR (A AND C) OR (B AND C)

T_{123}= A OR B OR C

Next, we can make T

_{01}, costing us 1 NOT gate:

T_{01}= NOT T_{23}

T

_{1}and T

_{013}are now available:

T_{1}= T_{123}AND T_{01}

T_{013}= T_{01}OR T_{3}

and T

_{13}

T_{13}= T_{013}AND T_{123}

Finally we can bring out our other NOT gate

T_{02}= NOT T_{13}

At last we construct T

_{0}and T

_{2}:

T_{0}= T_{02}AND T_{013}

T_{2}= T_{02}AND T_{23}

This completes the construction of T

_{0}, T

_{1}, and T

_{2}, finishing the problem.

## No comments:

Post a Comment