Re: Notions of Type

paul c wrote:
> Vadim Tropashko wrote:
> > paul c wrote:
> >> D&D claim their algebra can also
> >> be reduced to two operators as well, take your choice, NAND and REMOVE
> >> or NOR and REMOVE.
> >
> > I doubt it. Can you please supply reference, or better yet write
> > expressions for all 6 classic relational operators in terms of NOR and
> > REMOVE?
> > ...
>
> Second point on page 8, http://www.dcs.warwick.ac.uk/~hugh/TTM/APPXA.pdf.
>
> I assume the six classical ops are select/restrict, union, product,
> join, divide (plus project), don't know if it's necessary to write them
> all out, as D&D do the same in the above and many other sources show how
> their ops can be replaced with nor or nand, eg.,
> http://en.wikipedia.org/wiki/NAND

I'm quite surprised that De Morgan's law is valid in D&D algebra...

One more element of surprise is that AFAIK neither of Tarski's algebras: algebra of binary relations, nor cylindric sets algebra were shown to be reduced to a small set of basic operations...

As for algebraic properties in reduced D&D algebra, then NOR doesn't seem to be especially pretty algebraic operator. It's not idempotent, nor associative. I'm not aware undergraduate boolean algebra courses which hinge on NOR operation either. Anyway, this (admittedly quite unexpected) competition is welcome.

> It's been a long time since I read about circuit theory, but their claim
> seems to be well-known in that field and both were pre-dated long
> before.

Once again D&D algebra is not a boolean algebra. Therefore, the results from boolean circuit theory can't be applied blindly. Received on Sun Aug 20 2006 - 21:31:55 CEST