Boolean algebra "2 nots" problem

From: Brad Johnson (bradley.f.johnson_at_seagate.com)
Date: 06/24/04 

Date: 24 Jun 2004 11:38:06 -0700

Has anyone seen the following Boolean algebra problem before?

Given three inputs A, B, C, generate three outputs A', B', C' using
any number of AND and OR operations, but a maximum of 2 NOTs.

It's not clear to me that it's possible to solve this. The problem
was given to me by someone known to be a practical joker, so I'm
wondering if this is just a waste of time.

If the problem has no solution, it seems that it should be relatively
straightforward to prove that fact - perhaps based on the number of
decreases present, etc.

On the other hand, if the problem does have a solution, then it also
seems that a proof that a solution exists (other than the solution
itself) ought to be straighforward.

Unfortunately, I lack the discrete math background to approach this
theoretically... I'm not necessarily looking for a solution, just
some indication that it's either solvable or not solvable.

Thanks!

Loading