Ponder This Challenge - August 2009 - Implement 3 nots using only 2

This month's challenge is a joint problem with UyHiP site and is about Boolean functions.

We use the following notation:

The input to the function is given in variables ("a", "b", etc).
Each Boolean gate gets two inputs and stores its output in the next consecutive letter.
We denote an AND gate by putting its inputs in lexicographical order; and an OR gate by reversing the order.
We assume that a capital letter represents the negation of its lower case.

For example "abAced" is an implementation of the multiplexer function:

mux(a,b,c) = b if a is true, c otherwise.

Explanation:

d <=- a AND b; it is an AND gate since a<b
e <=- (NOT a) AND c; A means (NOT a) and AND since a<c
f <=- d or e; it is an OR gate since e>d

We want to compute the negation of three variables, but, unfortunately, we have only two NOT gates.

The answer should be given as sequence of letters according to the notation above; "a" "b" and "c" contains the input and the last three pairs should compute NOT(a); NOT(b); and NOT(c).

Since we allow for only two inverters (NOT gates), only two different letters can appear as capital.

One can generalize this question by asking, for example, how many inverters are needed to implement n inversions; more follow-ups questions can be found at UyHiP (link resides outside of ibm.com).

Solution

• Click here to view the solution

  The way to compute three inverters with only two is to first compute the majority function:
  maj(a,b,c) = (a AND b) or (a AND c) or (b AND c);

  then compute the xor function using the first NOT:
  xor(a,b,c) = (a AND b AND c) or (NOT(maj(a,b,c)) AND (a OR b OR c));

  and lastly we can compute NOT(a) without additional NOT gates by multiplexing on the two computed functions maj and xor (shorthand for maj(a,b,c) and xor(a,b,c) respectively):
  NOT(a) = (NOT(maj) AND NOT(xor)) OR (NOT(maj) AND xor AND (b OR c)) OR (maj AND NOT(xor) AND b AND c); and similarly compute the other two NOT(b) and NOT(c).

  After some optimization this can all fit into 23 gates:
  bcacabcbcabaeffdkeLdLeLfgLhLiLqpsjmTnToTupvqwr

Solvers

• J. Kennedy (08/03/2009 05:26 PM EDT)
• Adam Daire (08/03/2009 05:57 PM EDT)
• Eli Biham (08/03/2009 06:29 PM EDT)
• Andreas Eisele (08/03/2009 07:43 PM EDT)
• Michael Quist (08/04/2009 05:16 PM EDT)
• Andrew Holster (08/04/2009 11:06 PM EDT)
• Mark Mixer (08/05/2009 08:21 AM EDT)
• Daniel Chong Jyh Tar (08/05/2009 09:49 AM EDT)
• Steffen Wolf (08/05/2009 10:46 AM EDT)
• Lukasz Bolikowski (08/05/2009 10:50 AM EDT)
• Daniel Bitin (08/05/2009 11:58 AM EDT)
• Matej Kollar (08/05/2009 04:45 PM EDT)
• Chungmin Lee (08/05/2009 05:45 PM EDT)
• Yuval Filmus (08/05/2009 07:49 PM EDT)
• Nyles Heise (08/06/2009 01:40 PM EDT)
• Chuck Carroll (08/06/2009 04:39 PM EDT)
• Sevag Papazian (08/07/2009 03:43 AM EDT)
• Jonathan Campbell (08/07/2009 11:47 AM EDT)
• Lachezar Christov (08/09/2009 05:14 AM EDT)
• Hongcheng Zhu (08/09/2009 05:43 AM EDT)
• Harold Gutch and Peter Gruber (08/09/2009 07:31 PM EDT)
• Alan Murray (08/10/2009 11:44 PM EDT)
• Andrei Laza (08/11/2009 02:19 AM EDT)
• Subramanian C. A (08/11/2009 06:00 AM EDT)
• Harald Boegeholz (08/11/2009 05:52 PM EDT)
• Dan Dima (08/12/2009 09:40 AM EDT)
• Michael Schaaf (08/12/2009 09:46 AM EDT)
• John Ritson (08/13/2009 02:30 AM EDT)
• John T. Robinson (08/13/2009 11:35 AM EDT)
• Clive Tong (08/14/2009 03:21 PM EDT)
• Corey Cerovsek (08/15/2009 10:12 AM EDT)
• Christian Blatter (08/17/2009 07:39 AM EDT)
• Ionel Santa (08/18/2009 03:42 AM EDT)
• Albert Stadler (08/18/2009 01:15 PM EDT)
• Steven Langerwerf (08/19/2009 03:57 PM EDT)
• Bobby Brennan (08/19/2009 09:47 PM EDT)
• Mithil Ramteke & S. Ramakrishnan (08/20/2009 10:17 AM EDT)
• Bojan Basic (08/21/2009 03:39 PM EDT)
• Joseph DeVincentis (08/27/2009 12:03 PM EDT)
• Jason L. (08/28/2009 11:43 AM EDT)