Skip to content

Instantly share code, notes, and snippets.

@tobin
Last active September 4, 2020 04:57
Show Gist options
  • Save tobin/dd05276975729bc5b6269cb5ff8639d0 to your computer and use it in GitHub Desktop.
Save tobin/dd05276975729bc5b6269cb5ff8639d0 to your computer and use it in GitHub Desktop.
Solution to "invert three signals with two not gates" puzzle
# 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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment