コンピュータサイエンスの分野でかなり古くからあったというパズル「3 not 問題（ないし 2 not 問題とも）」の解説です。
パズルですから、この解説はいわゆるスポイラー（興を削ぐネタばらし）にあたります。パズルを楽しみたい方は、この解説は絶対に読まないでください。
問題そのものについての説明は和田先生のブログエントリ http://parametron.blogspot.jp/2008/07/3-not-problem.html を参照してください。
和田先生が書かれている「3は2ビットで表現できる」「閾値素子」というのが大きなヒントなのですが、なんの説明もなくそれだけ言われても、ちょっとわかりません。総当たりなど何らかの方法で解を得てみれば、どういう意味なのかわかってくると思います。
では、解説の入っている zip ファイルです → 3not_kaisetsu_v2.zip
「否定数限定反転回路の複雑さについて」という文献を見つけました（ http://ci.nii.ac.jp/naid/110003191722 ）。この解説よりさらに踏み込んだ内容があります（詳細未読）。
2016/Oct/20 解説中のSVGによる図を更新しました。