Programming puzzle with boolean circuits

Johannes Bauer dfnsonfsduifb at gmx.de
Mon Dec 9 12:49:46 CET 2013

```Hi group,

it's somewhat OT here, but I have a puzzle to which I would like a
solution -- but I'm unsure how I should tackle the problem with Python.
But it's a fun puzzle, so maybe it'll be appreciated here.

The question is: How do you design a boolean circuit that contains at
most 2 NOT gates, but may contain as many AND or OR gates that inverts
three inputs? IOW: Build three inverters by using only two inverters
(and an infinite amount of AND/OR).

Surprisingly, this is possible (and I even know the solution, but won't
give it away just yet).

I found this puzzle again and was thinking about: How would I code a
brute-force approach to this problem in Python? And to my surprise, it
isn't as easy as I thought. So I'm looking for some advice from you guys
(never huts to improve ones coding skills).

Best regards,
Johannes

--
>> Wo hattest Du das Beben nochmal GENAU vorhergesagt?
> Zumindest nicht öffentlich!
Ah, der neueste und bis heute genialste Streich unsere großen
Kosmologen: Die Geheim-Vorhersage.
- Karl Kaos über Rüdiger Thomas in dsa <hidbv3\$om2\$1 at speranza.aioe.org>

```