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.

  • $\begingroup$ Identity and Not are unary operators. $\endgroup$ – learner Mar 2 at 10:06
  • 1
    $\begingroup$ @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. $\endgroup$ – YuiTo Cheng Mar 2 at 10:07
  • $\begingroup$ What exactly do you mean by "composition" here? $\endgroup$ – Paul Sinclair Mar 2 at 20:45
  • $\begingroup$ 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$. $\endgroup$ – mbjoe Mar 2 at 22:17
  • $\begingroup$ @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 $\endgroup$ – YuiTo Cheng Mar 3 at 1:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.