Doublemix: A new start

Today is January 1, 2018.

Day 1 of Doublemix.

And maybe a new start, perhaps.

2018, if you’ll allow me to start a paragraph with a number, factors as the product of the two primes 2 and 1009.   Both are special in their own way.

2 has been special for millennia, as the number motivating the whole idea of counting.  If whenever you counted a collection you never got past 1, no one would have invented counting.

They would have invented Boolean algebra, the arithmetic of 0 and 1.  Boolean algebra was invented by George Boole and first published by him in a little pamphlet in 1847.    In Boolean algebra counting reduces to yes (1) or no (0) as the answer to the age-old question, is there anyone there?

Surely if you added 1 and 1 you’d get 2, right?  Wrong.  Boolean algebra doesn’t have 2.  The only possible result of adding 1 and 1 is either 0 or 1.  Without 2 those are the only counting numbers.

And in fact there are two operations, two ways of adding Boolean numbers.  When 1 and 1 is 1, the operation is called disjunction, the OR operation.  Perfectly clear, but when being even more perfectly clear one would call it inclusive OR or IOR.

This was the operation that Boole regarded as the counterpart of addition in his new arithmetic, and he wrote it as +.  So in Boole’s arithmetic 0 + 0 = 0, and 0 + 1 = 1 + 0 = 1. Boole was fine with that, as were his contemporaries.

What was new about Boole’s arithmetic was 1 + 1 = 1.   This was fine with Boole, but it took his contemporaries aback.

Boole also defined conjunction, namely as the operation xy, ordinary multiplication.  This is 1 when both x and y are 1, and 0 in all three other cases.  No one had any problem with taking multiplication to mean logical conjunction.

What about the other possibility for addition?  That’s the operation in which 1 and 1 is 0.  That operation is called exclusive OR, XOR.  Today we write it as x y

Boole himself knew and wrote about XOR, but he did not regard it as a basic operation.  He explained it instead as the compound operation  x + y − xy : when x and y are both 1, subtract it from the result of x + y so as to not to count the case when both are true.

But what is subtraction x − y in Boole’s system?  Is it another basic operation?  Boole glossed over this, but the answer he should have given if anyone was to make sense of his system is that it requires one more basic operation besides x + y and xy, namely ¬x, definable on 0 and 1 at least as 1 − x.  With only the two operations x + y and xy, there is no way to construct 0 when x and y are both 1.   With ¬x we can define x − y  as the conjunction x(¬y) which is 1 just when x = 1 and y = 0.

So that’s Boolean algebra.  It has various laws that are the same as in ordinary algebra, like x + y = y + x, commutativity of addition, xyyx,  likewise for multiplication, and x(y + z) = xy + xz, distributivity of multiplication over addition.  But it also has laws not found in ordinary algebra, like x + xx, idempotence of addition, x² = x, likewise of multiplication, and x + yz = (xy + xz), distributivity of addition over multiplication.

While these strange new laws didn’t bother Boole they bothered his contemporaries so much that they decided Boole’s system was not an arithmetic of the numbers 0 and 1 at all but the logic of truth values T and F, true and false.  With that distinction there is no reason to expect the algebra of truth values to mimic the algebra of numbers except superficially.

And that’s the way the world viewed Boolean algebra until 1927, eighty years after its introduction, when the Russian mathematician Ivan Ivanovich Zhegalkin pointed out that Boolean algebra was equivalent to arithmetic mod 2.  While keeping xy as a basic operation, he took x y as the other basic operation.  Whereas in Boole’s system xy is a compound or derived operation definable in terms of basic operations as x + y − xy, in Zhegalkin’s system x + y is a derived operation definable in terms of basic operations as  x yxy.

In this way Zhegalkin conferred legitimacy on Boole’s original concept, that truth values can be understood as numbers, by identifying arithmetic addition with XOR instead of OR and reducing all numbers to just their parity, namely their remainder mod 2, their least significant bit or LSB when represented as binary numerals instead of decimal.

 

This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s