IBM Ponder This #136 · 2009 年 8 月

本题与 UyHiP 联合提出。布尔输入依次记为 a、b、c 等。每个双输入门的输出按字母顺序占用下一个变量；两个输入按字母升序书写表示 AND，降序表示 OR，大写字母表示对应小写变量取反。

例如字符串 abAced 表示：d=a AND b，e=(NOT a) AND c，f=d OR e，因此实现 mux(a,b,c)：a 为真时输出 b，否则输出 c。

现在要同时求 NOT(a)、NOT(b)、NOT(c)，却只允许使用两个 NOT 门。构造由上述记号组成的字母字符串，使最后三个输入对分别计算这三个输出。只允许两种不同的字母以大写形式出现，对应两个反相器。

关于实现 n 次取反所需反相器数量等推广，参见 UyHiP。

解答

认真尝试后再打开

待补充。