Re: A Simple Notation

David Cressey wrote:
> In Boolean algebra, you could, if you wanted to, express everything by just
> using brackets, as follows:
>
> [A B] means NOT (A AND B)
>
> This notation can be extended to 3 or more operands, as follows:
>
> [A B C] means NOT (A AND B AND C)
>
> "AND" is associative, so there's no confusion.
>
> You can reduce the notation to 1 operand as follows:
>
> [A] means NOT (A)
>
> And to zero operands as follows:
>
> [] means TRUE
> [[]] means FALSE
>
> You can build up everything else from there. For example,
>
> [[A B]] = A AND B
> [[A] [B]] = A OR B
>
> Now my question is, can you do the corresponding thing in the RA, using
> <NOT> and <AND>? I don't see why not.
>
> So you would get (for example)
>
> [[A B]] = A <AND> B
> [[A] [B]] = A <OR> B
>
> As written text, this notation is rather unwieldy, but you can represent it
> fairly tightly in internal data structures. And its simplicity does make
> some things easier.
>

To me, it suggests an algebra that is based solely on NAND (ignoring projection for the moment).

Just playing with eg., De Morgan:
<NOT> (A <AND> B) = (<NOT> A) <OR> (<NOT> B) ->
[[[A B]]] = [[A] [B]].

Mixing things up a bit, if [] is TRUE, it is the identity value for <AND>, so:

A = A <AND> [] ->
A = A [] ->
A = [[A []]].

Have to admit I like brackets because on my keyboard, I can type them without a shift key. At first glance, I imagine that a practical engine operating on "tuples" could simply reverse its tests whenever it encountered a leading bracket, eg. test 'not equal' instead of 'equal', assume <OR> whenever a leading bracket immediately follows a trailing bracket and so forth. I know that the electronic engineers like NAND because transistor-like circuit devices emulate it precisely. Does a language like Lisp make the same emulation easy? Another thing I wonder is what a debugging traceback of intermediate results would look like! Also, is it the case that one would never need more than three leading or trailing brackets in succession?

(I think this kind of topic is always interesting. Personally, I was thinking of making a fairly sophisticated memory engine to test some of my "opinions" regarding view updating, transactions and so forth but I think I would like to also make a very sub-optimal parallel engine to validate the more sophisticated one, so the idea of using a different algebra to test an implementation appeals to me as it might have less chance of echoing the same bugs in the other one! Should mention I didn't have Lisp in mind but IIRC it is a favourite of David C.)

p Received on Thu Jul 05 2007 - 16:36:33 CEST