Solution to "invert three signals with two not gates" puzzle

two_nots.py

# Solution to the following puzzle:
# Invert three boolean signals Using only two NOT gates,
# and as many AND or OR gates as needed,
#
# Tobin Fricke 2020-09-03

for x in [True, False]:
    for y in [True, False]:
        for z in [True, False]:
            # If we assume that there is only one solution, then, when searching for the input
            # to the first NOT gate, we must find an expression that is symmetric with respect
            # to exchange of any of the inputs - none of the inputs is individually special. There
            # are only three options: xyz, xy + yz + xz, and x + y + z. Of these, xy + yz + xz seems
            # the most promising because it is true for exactly half of the eight possible input
            # patterns. Thinking more abstractly, the expressions that are symmetric with respect to
            # exchange of the input variables are the ones that "count" the number of 1's in the input,
            # or compute its parity. The expression xy + yz +xz is true when there are "two or more
            # ones" in the input. Its complement, of course, is true when there are exactly one or zero
            # ones in the input.
            w = not ((x and y) or (y and z) or (x and z))
            
            # For the input to the second inverter, if there is a unique solution then we have the same
            # requirements as for the first inverter: the expression must be symmetric with respect to exchange
            # of the arguments x, y, and z. But now we have the additional argument w that we can add into the
            # mix (without any additional symmetrization requirements). So the input to the second inverter must
            # be of the form:
            #
            #  u = not( (w and ____) + ((not w) and ______)
            #
            # where we can fill the blanks with the expressions "x+y+z", "xy+yz+xz", or "xyz", as before. Of these,
            # the middle one is immediately disqualified because it's equal to not(w) already and would make the
            # expression u true in all cases (not useful). Similarly, "xyz" isn't the right coefficient for w, because
            # wxyz is always false. This leaves "x+y+z", or potentially no coefficient at all. Similar arguments can be
            # applied to the second blank. This leaves us with a small number of choices of expressions to look into.
            
            # Although the answer is now practically staring us in the face, I took a detour at this point.
            # I ended up writing out the truth table of the function I wanted to have, and then
            # solved for that function. If N is the number of ones in the input, then the truth table I
            # already have for w, and the truth table I want for u, is:
            #
            #    N | w | u 
            #   ---+---+---
            #    0 | 1 | 1
            #    1 | 1 | 0
            #    2 | 0 | 1
            #    3 | 0 | 0
            #
            #  This would let me write the following expression:
            #
            #    x_not = uw + w(y + z) + uyz
            #
            #  The term "uw" is true when there are zero ones in the input. In this case, every output
            #  (x_not, y_not, z_not) should be high.
            #
            #  The next term is active when there are zero or one ones in the input. Here we have to check
            #  whether the one of the OTHER inputs is high. If so, OUR input muts be zero. So out output
            #  should be high.
            #
            #  Finally, the third term checks for the case where exactly two inputs are high. If so, then,            
            #  as long as y and z are high, we know our input must be low, so our output should be high.
            #
            #  Having decided that this was the desired truth table for u, I could write down the folllowing
            #  definition for it, by inspection:
            #
            #  u = w((not x)(not y)(not z)) + (not w)(not (x and y and z)))
            #
            #  where the first term describes what to do if w is high and the second describes what to do
            #  when w is low.
            #
            #  From there I negated u and then applied DeMorgan's laws to get it into the desired form:
            u = not ((w and (x or y or z)) or (x and y and z))
            
            x_bar = (u and w) or (w and (y or z)) or (u and y and z)
            y_bar = (u and w) or (w and (x or z)) or (u and x and z)
            z_bar = (u and w) or (w and (x or y)) or (u and x and y)
            
            assert x_bar == (not x)
            assert y_bar == (not y)
            assert z_bar == (not z)