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