IBM Ponder This #053 · 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.

Solution

Best opened after a real attempt

To be added.