Re: Query (Q-algebras)

[Vaughan Pratt <pratt@CS.Stanford.EDU>]

>(So if Z is 3 then there are 27 = 3^3 "Boolean" operations in place of
>the familiar 4 = 2^2.)

There should have been a "unary" in there of course.

Another question about these Q-algebras that Oswald Wyler was asking
about: what is a necessary and sufficient condition for a complete basis
for finitary Q-algebras (the theory of Boolean algebras rather than CABAs)
having any given Z?  For Z = 2 one answer (at least for the version of the
problem which only considers nonzeroary operations) is that for each of the
following properties the basis must contain a counterexample to that property.
Necessity follows because each property is preserved under composition;
sufficiency takes more work.

  * selfdual (e.g. xy+yz+zx = (x+y)(y+z)(z+x))
  * monotone
  * affine (expressible as the XOR of its arguments, optionally plus 1)
  * strict (maps the all-zeros input to zero)
  * costrict (maps the all-ones input to one)

(NAND violates all five at once.)  Is there a fixed number of such properties
that works for all finite cardinalities of Z, or must the number of properties
of this kind grow with Z?

Vaughan Pratt