Is there a relation between the "single axiom for boolean algebra"
that Wolfram claims to have discovered and the fact that you can express all boolean operations with just NAND?
I was sort of puzzled by the meaning of "axiom for boolean algebra" as well, and I looked into this more.
The way I learned boolean algebra was by associating certain operations (AND, NOT, OR, etc) to truth tables. In this framework, proving a theorem of boolean algebra would just involve enumerating all possible truth assignments to each variable and computing that the equation holds.
There is another framework for boolean algebra that does not involve truth tables. This is the axiomatic approach [1]. It puts forth a set of axioms (eg "a OR b = b OR a"). The symbol "OR" is not imbued with any special meaning except that it satisfies the specified axioms. These axioms, taken as a whole, implicitly define each operator. It then becomes possible to prove what the truth tables of each operator must be.
One can ask how many axioms are needed to pin down the truth table for NAND. As you know, this is enough to characterize boolean algebra, since we can define all other operators in terms of NAND. It turns out only one axiom is needed. It is unclear to me whether this was first discovered by Wolfram, or the team of William McCune, Branden Fitelson, and Larry Wos. [2]
Nice comment explaining the difference between two viewpoints.
The former one is set theoretic i.e. set of objects (eg. terms) and operations (eg. and/or/not) defined on those objects. The latter is an algebraic specification where a number of properties (expressed by logical formulas which can be axioms or theorems) are expected to be satisfied by the operations.
>
Is there a relation between the "single axiom for boolean algebra" that Wolfram claims to have discovered and the fact that you can express all boolean operations with just NAND?
The way I learned boolean algebra was by associating certain operations (AND, NOT, OR, etc) to truth tables. In this framework, proving a theorem of boolean algebra would just involve enumerating all possible truth assignments to each variable and computing that the equation holds.
There is another framework for boolean algebra that does not involve truth tables. This is the axiomatic approach [1]. It puts forth a set of axioms (eg "a OR b = b OR a"). The symbol "OR" is not imbued with any special meaning except that it satisfies the specified axioms. These axioms, taken as a whole, implicitly define each operator. It then becomes possible to prove what the truth tables of each operator must be.
One can ask how many axioms are needed to pin down the truth table for NAND. As you know, this is enough to characterize boolean algebra, since we can define all other operators in terms of NAND. It turns out only one axiom is needed. It is unclear to me whether this was first discovered by Wolfram, or the team of William McCune, Branden Fitelson, and Larry Wos. [2]
[1] https://en.wikipedia.org/wiki/Boolean_algebra_(structure)
[2] https://en.wikipedia.org/wiki/Minimal_axioms_for_Boolean_alg...,.