# How many distinct subsets of binary boolean operators are closed under composition?

Question:

There are $$2^4=16$$ distinct binary boolean operators. Two operators are regarded the same if one can be obtained from the other by exchanging the operands (input). It is easy to see only $$12$$ operators remain. How many distinct subsets of the $$12$$ are closed under composition?

I think the $$12$$ operators are {$$T,F$$, Identity, Not, And, Nand, Or, Nor, Implies, Non-implies, Equivalent, Xor (Non-equivalent)} respectively, where $$T$$ and $$F$$ are $$0$$-ary, Identity and Not are unary and the rest are truly binary. It's not hard to apply brute force as the number of cases is sufficiently small ($$2^{11}=2048$$ cases, since the identity must be included, which is the compositions of $$0$$ operators). But I would like to see 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. Many thanks.

Bonus: It will be much more appreciated if additional interpretations of the restricted range of logic represented by each closed subset are provided.

• Identity and Not are unary operators. – learner Mar 2 at 10:06
• @learner They can be regarded as binary boolean operators which take only the first input. The ones that take the second input are regarded the same. That's why $12$ remain. – YuiTo Cheng Mar 2 at 10:07
• What exactly do you mean by "composition" here? – Paul Sinclair Mar 2 at 20:45
• Why not starting with brute force and then finding an elegant argument for the result? I think it can be done with pencil and paper because the number of closed subsets is much less than $2048$. – mbjoe Mar 2 at 22:17
• @PaulSinclair Any composition is treated as a binary operator by assigning one of two independent boolean values to each of the available operands, e.g. (x And y) Or y – YuiTo Cheng Mar 3 at 1:39