Subject: FOM: Boolean algebra vs Boolean ring
Vaughan Pratt
pratt at cs.Stanford.EDU
Thu Mar 12 19:00:41 EST 1998
From: Steve Simpson
>OK. But do you accept my claim that U is a derived operation of
>Boolean rings, not a basic operation of Boolean rings?
Since the language of Boolean rings has as many bases as the language
of Boolean algebras, this is clearly a basis-dependent question: U is
a basic operation just when it is in the chosen basis. For the basis
standardly associated to the name "Boolean ring", U is of course not
a basic Boolean ring operation. And if one defined "Boolean algebra"
in terms of the AND,NOT basis, U would not be a basic Boolean algebra
operation either.
The AND,NOT basis is made particularly attractive by permitting the
following simple three-equation axiomatization, due to Robbins c.1933.
Its completeness was not established until 1996, by a computer program,
EQP, that had given up on getting humans to solve it automatically and
had done it by hand.
x(yz) = (xy)z
xy = yx
((xy)'(xy')')' = x
Vaughan Pratt
More information about the FOM
mailing list