The Scarpaz.
The Scarpaz Site
:: Your unreliable online reference documentation on the Scarpaz. ::
:: Via malfidinda reta dokumento de referenco pri la Skarpac. ::
Counter image

The 3not2 problem



I first heard about this riddle when I was at the third year of Computer Science Engineering, at Politecnico in Milan. I don't know whether it has some official name; i just call it the 3not2 problem.

The problem itself is very simple in its formulation, in fact it can be expressed in just a couple of sentences. At first the problem seems either impossible or trivial but then, when you actually try to find a solution, things get really complicated.

This is the text of the problem:

Given three logic inputs, A, B and C, design a logic circuit which gives as an output the three signals NOT(A), NOT(B) and NOT(C). Your circuit may contain any number of AND and OR gates, but no more than 2 NOT gates.


This formulation is sufficient to describe the problem. Nevertheless I report here some additional answers to those questions that people most frequently ask me when I tell them about this problem personally:

  • Can I use feedback in my logic circuit?

    No, you must design a combinatorial network. No feedback, no state, no technological parameters. No flip-flops. Think in terms of ideal logic gates, not silicon.

  • Can I use AND and OR gates with more than 2 inputs ?

    Sure. But nothing changes. Gates with more than 2 inputs can be easily expressed in terms of simple circuits with gates having 2 inputs.

  • ''The problem has no solution! You cannot negate 3 signals with 2 not gates! It's self-evident!''

    No, you are wrong. I have a solution. Moreover, to be more precise I have all the solutions. I am not going to tell how many distinct solutions I have because I'm not in the mood for writing an algorithm to reveal structural differences between circuits. Sorry, I'm not providing solutions to this problem because I want to spoil you the opportunity of finding it by yourself.

MajaMaja is powered by the Tcl Language. [jump to top of page]

Above document last modified on 2006-09-30 03:23:14; page last updated on 2006-09-30 at 04:04:01.
Document size: 2640 bytes, plus related data up to 215 kbytes (more precisely, 221101 bytes).


MajaMaja is powered by the Tcl Language. [jump to top of page]
This page was last updated on 2006-09-30 at 04:04:01.
This site was automagically generated by MajaMaja version 0.298, a simple and easy to use web content manager written in Tcl by scarpaz <>.