This puzzle would apply more for electrical engineers or computer science geeks - I apologize for this:

you are a designer of cheap printed circuit boards (PCB).
those PCBs have only a single layer of connectivity - imagine wires glued on the board itself. these 'printed' wires connect the outputs or boolean gates, like OR, AND and NOT.

somebody gives you a drawing of a complex boolean function, made of tons of logic gates (AND OR and NOT), all the inputs to this function are on the left side of the PCB and the outputs are on the right side.

now, the original drawing on paper has different wires criss crossing each other like crazy. your job is to move gates around, maybe adding some or removing some, but without changing the overall function - and lay it out on the board. remember you have only one layer to work with, so crossing wires are not allowed - they will 'short' and this is not wanted.

can ANY boolean function be laid out on such a board? or is there a limitation?

N.

hoping this one will keep ThomasB and stanalger a bit busier... since the last puzzle was solved in a blink of an eye by them...

Solved by TomasB

man, a puzzle here can't hold more than a day unsolved. maybe I should post the Goldbach conjecture next time...

Below you can see my solution. Don't click if you want to ponder it some more.

http://hem.bredband.net/tomasblomberg/UncrossingWires.JPG

/Tomas

Wow! (I clicked on Tomas's solution.)