Boolean Algebra is Wrong

[crayzz]

If that's our goal, we can chop it down to a single operator, NAND:

A	B	A NAND B
0	0	1
0	1	1
1	0	1
1	1	0

We can show this is complete by showing we can build NOT and OR out of it, as follows:

A' = A NAND A
A OR B = (A NAND A) NAND (B NAND B)


Note, however, that minimal axiomization is not the only goal we might reasonably have. One of the big values of Classical Boolean Algebra is how it maps into other spaces. Consider set theory: if we have a set S and all of its subsets, including the empty set E, there's a direct relationship between Union and OR, Intersection and AND, and Complement and NOT. In particular, if we set S=1 and E=0, we get exactly the same behaviors from these operators. As with so many things, the representation(and axiomization) we wish to use depends on our overall objectives.

That's actually cool, I didn't know that.

You're right, of course, that minimal axiomization isn't necessarily desireable: these frameworks are built to be useful, and their usefulness is the arbiter of their value.

The mapping from boolean algebra to operators on sets is a good point (e.g. DeMorgan's laws are actually laws about set operators, etc). Boolean algebra is practically just standard set operators on the set {{},{1}}, so we automatically get tools from set theory that way. We lose that if we ground our framework in modulus arithmetic.

Look up "clock math" for the most basic introduction to finite fields (I'm not sure it really counts as a "field", reed-solomon and ecc were a bit much for me). Then realize that RSA works pretty much on the same principles, only for rather large "clocks".

Clock math is actually what I'm talking about! It's the same idea (modulus arithmetic).

The fact that it's actually a field (e.g. fully invertable over addition) is the main advantage I feel MOD 2 arithmetic has over boolean algebra, on aesthetic grounds if nothing else (I do actually think inversion is a useful tool for manipulation of expressions). It behaves more like the sort of algebra you're probably already used to. Being able to express NOT in terms of addition alone is also pretty useful IMO.

PS: I'd recommend fixing the title. Considering that binary numbers have been known to China since at least the I-Ching, that typo is pretty inappropriate.

I just noticed the typo. Unfortunately, I don't know how to fix it for the thread in general (though I fixed it for my reply here).

A forum called "Mad Science and Grumpy Technology" is as good a place as any for this sort of thing. It's unfair to accuse anyone of seeking attention in a post; by participating here, you (and I for that matter) are doing this as well.

Yeah, I mean: of course I'm looking for attention. I'm looking for engagement on a particular topic. Given the math focused threads in the past, and the general impression I have of how well versed various forum members are in math (not to mention the fact that I just like it here), this seemed like a good place for that sort of thing.

—

In the end, OR, AND, and NOT probably are better bases for boolean algebra: if nothing else, it's easier to build a physical OR gate (just let all the inputs go through the gate) than it is to build a XOR gate. OR is probably slightly easier to grasp at first, too. It's probably more practical to think of OR as a fundamental operation.