Re: Question about Date & Darwen <OR> operator

Mikito Harakiri wrote:
> Marshall Spight wrote:
>
> My reply that your expression { (x, y) | x = 1 or y = a } is formal
> enough is lost somewhere in Google groops:-)

Ha! That's happened to me before as well.

> Well, the formal definition of <OR> and <AND> seems to be very
> consistent with boolean logic.
> [...]
> Therefore, the D&D algebra
> intuitively looks like boolean algebra, but it is certainly not.
> Absorption, doesn't hold: relation headers monothonically increase, so
> that there is no way for headers to match. Therefore, this nice boolean
> logic must break somewhere. Where?

My understanding of the classical definition is that an algebra is boolean iff:
for binary operators +, *, unary operator ', and elements 1, 0

1) +, * are commutative
2) +, * are distributive
3) for all A, A+0=A, A*1=A  (identity)
4) for all A, A+A'=1, A*A'=0  (complement)

It seems to me that compliment is the problem. The algebra is obviously commutative. Elsewhere you've said it's distributive (which seems right.) If we define 0=dum and 1=dee (or what we've elsewhere called 00 and 01) we get identity, but it breaks down at complement over <OR>.

A+A'= universal set for header(A)
A*A'=10

Both of these fail to satisfy 4).

Now, we could choose the 1 element to be a+a', and the 0 element to be A*A'. Then identity and complement work. But it means that the 1 and 0 elements are specific to some header(A), so you could say it's a boolean algebra schema, rather than a boolean algebra. (That is, for every header, you can construct a boolean algebra for it, but it's not bollean in general.)

I have recently learned that there's an alternative way to specify a boolean algebra. It is much simpler but I find it harder to understand.

A "Robbins Algebra" is an algebra that satisfies these equations:

1. commutative
2. associative
3. Robbins Equation: n(n(A+B)+n(A+n(B))) = A.

where n() is the compliment function.

It turns out that every Boolean Algebra is a Robbins Algebra, and vice versa. Which IIUC means that satisfying the Roobbins Equation is sufficient to prove distributivity.

Anyway, it's all very complicated.

Oh, one last thought: I understand that every boolean algebra will be defined over a set that has a cardinality that is a power of two. This suggests power sets to me, which in turn reminds me of the fact that we keep running into these algebras as being specific to a given header.

Marshall Received on Fri Sep 02 2005 - 23:07:22 CDT