I recently came across an oral exam where the candidates were asked to find a logical circuit than can negate 3 inputs A,B,C using only two NOT gates.

The question also specified that such a circuit is unique up to removal of useless gates and reordering inputs/outputs. The candidates were asked to prove this assertion by writing a piece of code that generates all such circuits.


No inputs whatsoever are given.

The program must output all logical circuits using unlimited AND and OR gates but only two NOT gates which take in three inputs which map to three outputs. The outputs should be the negation of each input.

The outputted circuits should not have any redundant/trivial gates (gates that always output the same thing) or unused gates (whose output doesn't influence the outcome).

The program should use no precalculated or cached data.

Output format is left up to the coders.

The winner will be determined by the fastest algorithm. Since input doesn't scale, whoever has the least loops and calculations wins. Please remember your code must not cache or use any precalculated data.

Example Input and Output




R    = (A & B) | (A & C) | (B & C)
notR = !R
S    = (notR & (A | B | C)) | (A & B & C)
notS = !S

notA = (notR & notS) | (notR & S & (B | C)) | (R & notS & (B & C))
notB = (notR & notS) | (notR & S & (A | C)) | (R & notS & (A & C))
notC = (notR & notS) | (notR & S & (A | B)) | (R & notS & (A & B))
  • 1
    \$\begingroup\$ I like your challenge but you should probably add an objective criterion (e.g. fastest-code as mentioned in your post). How would you define "code elegance" to choose a winner? Subjective winning criteria are generally disliked. \$\endgroup\$
    – Adyrem
    Commented Jun 18, 2018 at 12:30
  • 4
    \$\begingroup\$ Hi, welcome to PPCG! Challenges must always have a clear winning condition tag. Since you've stated the winner is determined by overal simplicity, low runtime, and code-elegance, this is currently a bit vague. May I suggest using the tag [atomic-code-golf] (least amount of operations), where in this case the operations are arithmetic and bitwise ones, including up to 2 NOT, and lowest amount of OR, AND, XOR, etc.? EDIT: @Adyrem beat me to it.. \$\endgroup\$ Commented Jun 18, 2018 at 12:31
  • \$\begingroup\$ The issue is that due to the uniqueness of the machine, everyone will have the same amount of gates. I'll think of it a bit more. \$\endgroup\$
    – John Do
    Commented Jun 19, 2018 at 13:17
  • \$\begingroup\$ I believe I have corrected my question @KevinCruijssen, how do I get it reopened? \$\endgroup\$
    – John Do
    Commented Jun 26, 2018 at 13:05


Browse other questions tagged or ask your own question.