用两个非门和任意的与、或门构造三个非门

计算机科学中有很多有趣的 puzzle，他们可能出现在那些自命清高的企业的笔试题中，也可能来源于在网路上不经意的一瞥。后者比如我在无意中访问到的 Jamie Zawinski 的个人主页：http://www.jwz.org/，他即是在著名的 Teach Yourself Programming in Ten Years 一文中，Peter Norvig 提到的那位：

One of the best programmers I ever hired had only a High School degree; he's produced a lot of great software, has his own news group, and made enough in stock options to buy his own nightclub.

Jamie Zawinski 的个人主页看起来就像是 hexdump 的结果，而且以某种规律变化着，比较奇怪的是其中埋藏的一些超级链接并不发生变化。Jamie Zawinski 在网页的源代码中这样写道：

<!-- mail me if you find the secret -->
<!--   (no, you can't have a hint)  -->

我徒劳无功地搜索了一下，没有找到任何明确的解答。如果您通过我这篇文章了解到这个 puzzle，并且解答了它的话，非常希望您也 mail 给我一份解答。

说了那么多，其实本文的主题 puzzle 却是来源于前者。这个问题更详细的阐述是：

假设有一个逻辑黑盒，三个布尔型变量 x, y, z 作为输入，输出三个布尔变量 X, Y, Z，其中：
X = ~x; Y = ~y; Z = ~z;
注意，~ 符号代表一个非门。请用两个非门和任意多个与、或门实现这个黑盒。

这个问题大概是在计算机硬件设计中提出来的，所以看起来貌似很“电子”，但是其基础却是计算机科学中的布尔代数运算。下面代码的注释中已经包含详细的算法和分析，这里我就不再解释了。（当然，这个问题的答案不是我想出来的，我只是实现并分析了一下，作为我算法学习的笔记记录在此。）

/* ===========================================================================

* Problem:
*   Construct 3 NOT gates from only 2 NOT gates(and *no* XOR gates).
*
*   Assume that a logical blackbox has three Boolean inputs x, y, z and
*   three Boolean outputs X, Y, Z where the outputs are defined as:
*     X = ~x
*     Y = ~y
*     Z = ~z
*   Note that ~ stands for a NOT gate. Please realize this blackbox using
*   only two NOT gates, and as many as possible AND and OR gates.
*
* Algorithm I:
*   Internal Nodes:
*   r = (x & y) | (x & z) | (y & z);
*   R = ~r;
*   s = (R & (x | y | z)) | (x & y & z);
*   S = ~s;
*
*   Equations for Outputs:
*   X = (R & S) | (R & s & (y | z)) | (r & S & (y & z));
*   Y = (R & S) | (R & s & (x | z)) | (r & S & (x & z));
*   Z = (R & S) | (R & s & (x | y)) | (r & S & (x & y));
*
* Analysis I:
*   We create 4 internal signals first: r, R, s and S. What equations above
*   say is that signal `r' will be 1 if two or three of the inputs are 1.
*   Meanwhile, signal `s' will be 1 if only one input is 1 or if all three
*   inputs are 1. The end result is that the two-bit word formed from `r'
*   and `s' tells us how many 1's we have[1]:
*   | r s | Means  |    | x y z | r s |    | x y z | r s |
*   |++++++++++++++|    |+++++++++++++|    |+++++++++++++|
*   | 0 0 | 0 Ones |    | 0 0 0 | 0 0 |    | 1 0 0 | 0 1 |
*   | 0 1 | 1 One  |    | 0 0 1 | 0 1 |    | 1 0 1 | 1 0 |
*   | 1 0 | 2 Ones |    | 0 1 0 | 0 1 |    | 1 1 0 | 1 0 |
*   | 1 1 | 3 Ones |    | 0 1 1 | 1 0 |    | 1 1 1 | 1 1 |
*
*   Thus now that we have the signals r and s (and their inverse
*   counterparts R and S), it's easy to construct any Boolean function of
*   x, y, and z, using only AND and OR gates:
*     X = (R & S) | (R & s & (y | z)) | (r & S & (y & z))
*   Proof:
*    1> x, y, z are all 0s, (R & S) = ~(r | s) = 1, obviously X=Y=Z=1, X = ~x;
*    2> (x, y, z) has at least one 1, R & S = 0, will be ignored, hence we
*       have:
*         X = (R & s & (y | z)) | (r & S & (y & z))
*    2.1> (x, y, z) has two or three 1s, R = ~r = 0, (R & s & (y | z)) = 0,
*         will be ignored, then we get:
*           X = S & (y & z)
*    2.1.1> (x, y, z) has three 1s, S = ~s = 0, obviously X=Y=Z=0, X = ~x;
*    2.1.2> (x, y, z) has two 1s, S = ~s = 1, will be ignored, hence we have:
*             X = y & z
*    2.1.2.1> (y, z) has one 1, x = 1, X = y & z = 1 & 0 = 0, X = ~x;
*    2.1.2.2> (y, z) has two 1s, x = 0, X = y & z = 1 & 1 = 1, X = ~x;
*    2.2> (x, y, z) has one 1, r = 0, (r & S & (y & z)) = 0, will be ignored,
*         we have:
*           X = y | z
*    2.2.1> (y, z) has one 1, x = 0, X = y | z = 1 | 0 = 1, X = ~x;
*    2.2.2> (y, z) has no 1s, x = 1, X = y | z = 0 | 0 = 0, X = ~x.
*    In conclusion, X = ~x for all cases.
*   QED.
*
* Algorithm II:
*   Internal Nodes:
*   _2or3_1s = ((x & y) | (x & z) | (y & z));
*   _0or1_1s = !(_2or3_1s);
*   _1_1     = _0or1_1s & (x | y | z);
*   _1or3_1s = _1_1 | (x & y & z);
*   _0or2_1s = !(_1or3_1s);
*   _0_1s    = _0or2_1s & _0or1_1s;
*   _2_1s    = _0or2_1s & _2or3_1s;
*
*   Equations for Outputs:
*   X = _0_1s | (_1_1 & (y | z)) | (_2_1s & (y & z));
*   Y = _0_1s | (_1_1 & (x | z)) | (_2_1s & (x & z));
*   Z = _0_1s | (_1_1 & (x | y)) | (_2_1s & (x & y));
*
* Analysis II:
*   Almost the same as Analysis I.
*
* [1] http://www.edadesignline.com/howto/191600992
* ===========================================================================
*/

#include <stdio.h>

typedef unsigned int BOOL;

int main()
{
  int i, fail;
  BOOL x, y, z, X, Y, Z;
  BOOL r, R, s, S;
  BOOL _2or3_1s, _0or1_1s, _1_1,  _1or3_1s, _0or2_1s, _0_1s, _2_1s;

  /* ==================== Algorithm I ==================== */
  printf("Algorithm I:n");
  fail = 0;
  for (i=0; i<8; i++) {
    /* Init x, y, z. */
    x = i & 1;
    y = (i>>1) & 1;
    z = (i>>2) & 1;
    /* Internal nodes. */
    r = (x & y) | (x & z) | (y & z);
    //R = !r;                               /* #1 NOT gate. */
    R = ~r & 1;                             /* #1 NOT gate. */
    s = (R & (x | y | z)) | (x & y & z);
    //S = !s;                               /* #2 NOT gate. */
    S = ~s & 1;                             /* #2 NOT gate. */
    /* Output. */
    X = (R & S) | (R & s & (y | z)) | (r & S & (y & z));
    Y = (R & S) | (R & s & (x | z)) | (r & S & (x & z));
    Z = (R & S) | (R & s & (x | y)) | (r & S & (x & y));

    if ((x == X) | (y == Y) | (z == Z)){
      fail ++;
      printf("FAIL: ");
    } else {
      printf("PASS: ");
    }
    printf("xyz = %u%u%u, XYZ = %u%u%un", x, y, z, X, Y, Z);
  }
  if (fail != 0) {
    printf("%d TEST FAILED!n", fail);
  } else if (!fail) {
    printf("ALL TEST PASSED!n");
  }

  /* ==================== Algorithm II ==================== */
  printf("Algorithm II:n");
  fail = 0;
  for (i=0; i<8; i++) {
    /* Init x, y, z. */
    x = i & 1;
    y = (i>>1) & 1;
    z = (i>>2) & 1;
    /* Internal nodes. */
    _2or3_1s = ((x & y) | (x & z) | (y & z));
    //_0or1_1s = !(_2or3_1s);               /* #1 NOT gate. */
    _0or1_1s = ~(_2or3_1s) & 1;             /* #1 NOT gate. */
    _1_1     = _0or1_1s & (x | y | z);
    _1or3_1s = _1_1 | (x & y & z);
    //_0or2_1s = !(_1or3_1s);               /* #2 NOT gate. */
    _0or2_1s = ~(_1or3_1s) & 1;             /* #2 NOT gate. */
    _0_1s    = _0or2_1s & _0or1_1s;
    _2_1s    = _0or2_1s & _2or3_1s;
    /* Output. */
    X = _0_1s | (_1_1 & (y | z)) | (_2_1s & (y & z));
    Y = _0_1s | (_1_1 & (x | z)) | (_2_1s & (x & z));
    Z = _0_1s | (_1_1 & (x | y)) | (_2_1s & (x & y));

    if ((x == X) | (y == Y) | (z == Z)){
      fail ++;
      printf("FAIL: ");
    } else {
      printf("PASS: ");
    }
    printf("xyz = %u%u%u, XYZ = %u%u%un", x, y, z, X, Y, Z);
  }
  if (fail != 0) {
    printf("%d TEST FAILED!n", fail);
  } else if (!fail) {
    printf("ALL TEST PASSED!n");
  }
  return 0;
}