Re: Boolean algebra "2 nots" problem

From: Dennis Ritchie (dmr_at_bell-labs.com)
Date: 06/25/04 

Date: Fri, 25 Jun 2004 01:45:18 -0000

"Brad Johnson" <bradley.f.johnson@seagate.com> wrote in message
news:6fc3692b.0406241038.4dc348c@posting.google.com...
> 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.
 ...

The puzzle is in the rec.puzzles archive. I first saw it, I think,
in Minsky's Finite and Infinite State Machines as an exercise.
Someone later asked for clarification--the original referred to
logic gates in a circuit, but it can be formulated (perhaps
clumsily) in terms of Boolean expressions.

To solve it, think about symmetry. Also think about
generalizations (what if you have 3 inverters instead of 2?

    Dennis