OK wrong is the wrong word, I just don't like how it's described. It's killing me since we're going over boolean algebra and logic gates in class, so I'm going to explain what I think is a better basis to you fine folk.
Classical Boolean Algebra
Classical Boolean algebra is defined by 4 things: a set of elements, 2 binary operations (operations on 2 elements of the set; returns 1 element), and one unary operation (an operation on 1 element of the set; returns 1 element). The set is {0,1}: everything we ever work with in boolean algebra will either be 0 or 1. The two binary operations are OR and AND. The unary operation is NOT. They are defined as follows:
OR: True IFF any one input is True; 1 iff any one input is 1.
AND: True IFF all inputs are True; 1 iff both inputs are 1.
NOT: True IFF the input is false; 1 iff the input is 0.
A |
B |
A OR B |
A AND B |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
I talked a fair bit about identities
in another math-y thread, and the concept carries over. OR has an identity of 0: for every possible value of A, A OR 0 = A. AND has an identity of 1: for every possible value of A, A AND 1 = A.
There's an obviously analogy to be made, here: OR is somewhat additive. It has the same identity as addition. AND is multiplicative: it has the same identity as multiplication. For this reason, A OR B is often represented as A + B, and AND is often represented by A x B, or AB.
Think of the multiplication property where 0 swallows everything: no matter what, any chain of multiplication that contains at least one 0 will evaluate to 0. The same is true of AND. No matter how many AND operations you chain together, as long as one input somewhere along the chain is false, the whole thing evaluates to false, or 0. AND is very multiplicative. It's actually identical to normal multiplication on the set {0,1}.
OR isn't quite so additive. It has the same identity, sure, and 0 OR 1 = 1 much like 0 + 1 = 1, but 1 OR 1 = 1. In that above post I linked, I talk about inverses, and OR isn't fully invertable on the set {0,1}. There's no element A such that 1 OR A = 0. You can't "undue" A OR 1 operation to find A. 1 is to OR what 0 is to AND: if you have at least one 1 in your chain of ORs, the whole thing evaluates to 1, no matter the rest (N.B. there's a term for elements that swallow all other elements when used as part of a certain operation, but I can't remember it). It's not quite as additive as AND is multiplicative.
That brings us to NOT (NOT is usually represented as an overhead bar, I'm using a ' to represent it instead):
NOT doesn't really have any analogy in normal algebra. It's not a binary operation so it has no identity.
Now each of these operations have a bunch of properties that come along with them. AND and OR are commutative; they're associative; they're distributive (which is unique for OR: additive operations usually aren't distributive the same way multiplicative operations are), etc. From these properties you can derive a bunch of theorems about Boolean algebra. For example (using + and x to represent OR and AND):
A + A' = 1 (at least one of A or A' must be 1)
A x A' = 0 (at least one of A or A' must be 0)
(A')' = A
(A + B)' = A' x B'
(A x B)' = A' + B'
Those last two are called DeMorgan's Laws, or DeMorgan's theorem, and basically they establish that you can define OR in terms of AND and NOT, and you can define AND in terms of OR and NOT. If you take NOT of both sides:
A + B = (A' x B')'
A x B = (A' + B')'
Now this is slightly odd: OR and AND are supposed to be the basis of our algebra; they're supposed to be fundamental units of it. If I can describe one in terms of the other, they're not really that fundamental. We can define our algebra with just one, along with NOT. It kinda makes one wonder which one is REALLY fundamental, which one we should base everything on if we were to reduce our basis to as few axioms as possible.
(HINT: OR should be tossed as a fundamental operation)
MOD 2 Arithmetic
There's another form of algebra that works on the set {0,1}: it's called MOD 2 arithmetic. Under MOD 2 arithmetic, every number gets replaced with it's remainder after dividing by 2. Essentially, ever even number becomes 0 and every odd number becomes 1. Addition and multiplication work the same way, except you take MOD 2 of the results. So 1 x 1 = 1, 1 + 0 = 1, 0 + 0 = 0, all as expected. The only odd case is 1 + 1. Under normal arithmetic, that'd be 2, but if we take MOD 2 after adding, the result is 0. 1 + 1 = 0 under MOD 2 arithmetic. The tables describing multiplication and addition are as follows:
A |
B |
A + B |
A x B |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
Multiplication behaves exactly as expected, so there's nothing new to consider here. The real question is about addition: does it have an identity, and is it fully invertable like standard addition? Here again, MOD 2 addition has an identity of 0: for all A, A + 0 = A. But MOD 2 addition is also fully invertable: the inverse of 1 is 1. For all A, A + A = 0 (1 + 1 = 0, and 0 + 0 = 0, the latter of which is trivial since identities are always invertable by themselves). Despite the slight oddity of 1 + 1 = 0, MOD 2 addition is much closer to regular addition than the classical boolean OR operation.
Bringing it home
MOD 2 addition is identical to boolean XOR:
XOR: True IFF only 1 input is true; 1 iff only one input is 1
If you build the truth table for XOR, it's exactly the same as the table for MOD 2 addition. If we make an analogy between MOD 2 arithmetic and the sort of algebraic structure we want for boolean algebra, it implies two basic operations: XOR and AND, represented by + and x. But boolean algebra is defined around AND, OR, and NOT: how do we get the latter 2 from XOR and AND?
NOT, under XOR, is XOR 1, or + 1:
A' = A + 1 (0 + 1 = 1; 1 + 1 = 0).
Any time we want to take NOT of something, just add 1.
OR is slightly more complicated. Now that we have a NOT operation, we can use DeMorgan's Laws to derive OR:
A OR B = (A' x B')'
A OR B = (A + 1)(B + 1) + 1
A OR B = AB + A + B + 1 + 1
A OR B = AB + A + B
Using XOR as our additive basis, OR is somewhat more complicated to express using arithmetic notation. But remember that OR has a bunch of properties that normal addition doesn't: it's distributive, and isn't fully invertable. That's to be expected.
Using XOR and AND as our additive and multiplicative basis, we can derive any function or operation you can imagine in boolean algebra. The entirety of boolean algebra is contained within MOD 2 arithmetic. Every thereom about AND, OR, and NOT under boolean algebra remains true as they are defined here. MOD 2 arithmetic (by analogy, XOR and AND) makes a better basis for boolean algebra, being functionally identical, having no redundant axioms, and being fully analogous to classical algebra, even the NOT operation as a simple +1.