Recently I came across an interesting puzzle from MIT Tech Review March/April 2013:

Howard Cohen has plenty of AND and OR gates but just two inverters. How can he invert three signals a, b, and c?

More generally, he wonders if the ratio I/S can ever be less than 2/3, where I is the number of inverters and S is the number of signals to invert (once again, unlimited AND and OR gates are available).

I couldn’t quickly solve the first part of the puzzle with a pen and paper, so I decided to write a brute force solver. And to make it a bit more fun I did it in Haskell (any suggestions for improving the code are welcome, by the way!).

It turned out that there is only one principal solution which I described here (spoiler alert!). It makes sense in retrospect, so I encourage you to figure it out yourself.

To answer the second part of the puzzle note that the obtained circuit is functionally nothing else than just three inverters. That is, having an unlimited number of ANDs and ORs we can get three inverters from two inverters. But then nothing prevents us from applying the same step again resulting in four inverters, etc. Hence, rather surprisingly two inverters are enough to invert as many signals as we need! Or, in other words, we can compute any Boolean function using only monotone logic blocks (like ANDs and ORs) and two inverters.

P.S.: To be honest, I expected a brute force solver written in Haskell to be rather ugly. But I think the code I finally got is quite good-looking 🙂