September 2002
This month's challenge comes from John G. Fletcher:
There are 16 distinct binary boolean operators (or gates) that map ordered pairs of boolean operands (or inputs) into single boolean results (or outputs). However, for present purposes two operators can be treated as the same if they differ only in that one is obtained from the other by exchanging the operands. Since there are four such pairs of operators, there essentially are only 12 binary boolean operators. Two of these are really the boolean constants ("T" and "F"), because the result does not depend on either operand, and two are really unary operators ("Identity" and "Not"), because the result depends on only one of the operands, while the remaining eight are truly binary ("And", "Or", "Nand", "Nor", "Equivalent", "Xor", "Implies", and "Non-implies").
A (possibly improper) subset of these operators is said to be "closed" if and only if all compositions of operators in the set yield only operators that also are in the set. Each closed subset includes the Identity, which is the composition of no operators at all. Any composition is treated as a binary operator by assigning one of two independent boolean values (e.g., p or q) to each of the available operands -- e.g., [p Nand p] is [Not p]; [(p Nand p) Nand p] is T; both [(p Nand p) Nand q] and [(p Nand q) Nand q] are [q Implies p] -- so any closed set that contains "Nand" must also contain "T", "Not", and "Implies").
The question is: How many distinct closed subsets are there, and which operators are in each?
The number of cases to be considered is sufficiently small that the answer can be obtained by "brute force", that is, by exhaustively considering all cases, either by hand or with a computer. So what we prefer is a more elegant argument, one that may provide some insight into why the closed subsets are what they are and why there are no others. Also of interest are interpretations of the restricted range of logic represented by each closed subset.
We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!
We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.
If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com
Challenge:
09/04/2002 @ 10:00 AM EST
Solution:
10/01/2002 @ 1:00 PM EST
List Updated:
09/25/2002 @ 5:15 PM EST
People who answered correctly:
Alex Wagner (9.17.2002 @ 12:34 PM EDT)
Michael Swart (9.17.2002 @ 3:03 PM EDT)
Christopher Howe (9.17.2002 @ 4:28 PM EDT)
Dave Biggar (9.24.2002 @ 8:33 AM EDT)
Attention: If your name is posted here and you wish it removed please send email to the ponder@il.ibm.com.