なつたんさんの
ブログで「
3 not problem」という話題が取り上げられていました。元は和田先生の
ブログの記事「
3 not problem」だそうです。答が分かったのでさらしてしまいます。
↓↓↓以下にネタバレあり↓↓↓
x, y, zを入力変数、x', y', z'を出力変数、{c, s} = x + y + zとします。{c, s}はverilogの記法で2bitの変数の上位がc下位がsという意味です。
仮にx + y + zが分かったとします。つまりcとsが分かったとします。このとき、x = 0となる条件を考えてみます。
x + y + z = 0のときは、常にx = 0です。
x + y + z = 1のときは、y = 1またはz = 1のときx = 0となります。
x + y + z = 2のときは、y = z = 1のときにx = 0となります。
x + y + z = 3のときは、x = 0となることはありません。
ここからは論理式を次のように表現します。x and y → xy, x or y → x + y, not x → ~x。
さて、上の条件をcとsを使って整理してみると
x' = ~x = ~c~s + ~cs(y + z) + c~syz
となります。yとzについても同様です。
y' = ~y = ~c~s + ~cs(x + z) + c~sxz
z' = ~z = ~c~s + ~cs(x + y) + c~sxy
この段階で元の問題が、「x, y, zからnot 2つを使ってc, s, c', s'を求める」という問題に変形できたことになります。ただしc' = ~c, s' = ~sです。和なのでs = x xor y xor z、c = major(x, y, z)です。FA(Full Adder)の出力と一緒ですね。以下のようにnot 2つでc, c', s, s'を作ることができます。
c = major(x, y, z) = xy + yz + zx
c' = ~c
s = x xor y xor z = (x + y + z)(xyz + c')
s' = ~s
sはs = c'(x + y + z) + xyzでもいけます。cはc = (x + y)(y + z)(z + x)でもいいです。
以上