There are many equivalent ways to describe Boolean algebras. There are a number of different ways to "minimize" the description. We can:
- Minimize the number of function symbols.
- Minimize the arity of the function symbols.
- Minimize the number of variables needed in the defining identities.
- Minimize the number of defining identities.
- Minimize the total length of the defining identities.
It is well known that only one function symbol of arity $2$ is needed, and that at least one function symbol must have arity $\geq 2$.
The minimum number of variables is $3$, and one defining equation suffices. As shown in the paper Short single axioms for Boolean algebra, using the Sheffer stroke, then a single defining identity of length 15 suffices, and no shorter single identity using the Sheffer stroke exists.
By allowing more variables, or more defining equations, or more function symbols, it might be possible to have a shorter total length among the defining identities. For instance, the 2-basis $$ x|y=y|x $$ and $$ (x|y)|(x|(y|z))=x $$ has total length 18 (after writing it in reverse Polish notation and removing unnecessary parentheses). Technically, we don't need the equality symbols either, so we could reduce this to a string of 16 symbols. This is very close to the current minimum known length (of 14, if we remove equality symbols).
Question: Is the minimized total length of any possible collection of defining identities for Boolean algebra achieved when there is only one binary function symbol, only 3 variables, and only one identity?
(As a side question, in the paper linked above, they give two examples of 1-base defining identities of length 15, and provide sixteen more possibilities. Has anyone done the work of figuring out which of those sixteen possibilities actually work?)
