Monday, November 2, 2009

The Mathematics of Reason: The First Principles According To Boole.

In 1853, George Boole published his treatise, ”An Investigation of the Laws of Thought”, and gave the world “Boolean Algebra”, the mathematics of logic that ultimately made digital electronics and digital computing possible. To me, the most remarkable aspect of Boole’s work is his ability to resolve rational processes into simple equation form, even into tables for determining propositional truths.

His algebra varies only slightly from classical (numeric) algebra. It is necessary to envision sets, their intersection or non- intersection, rather than multiplication or division. For example, xy is the set that contains both x’s and y’s; this might not include all x’s or all y’s... but it could.

While there are other considerations, that one principle leads off to a remarkable conclusion. Here’s how it works:

If two entities are equal sets (identical), where y = x, then,
xy = x. (The intersection of the sets x and y are identical to the set x.)

This is the Principle of Identity.

And if y = x, then,

xx = x,

or
x2 = x.

next,

0 = x – x2,
0 = x ( 1 – x).

The sole solutions are x = 1 and 0, where 1 is a full set, and 0 is an empty or null set. Also, (1 – x) is the contrary set to x, where x is not a universal set.

This equation demonstrates several important things.

First, it represents the conjunction of both x and “not x”, making it a universal description. For example it could mean “truth” and “not truth”, covering the entire universe of possible validities. So it is a “universal” equation.

Second, it has only two solutions, 0 and 1. So in the case of “truth” and “not truth”, there is no intermediate value, meaning that only “true” and “not true” exist. This is the Principle of Excluded Middle. (Also called the Law of Duality, the principle of dichotomy in analytical thought.)

Third, it can be seen that x cannot be both 0 and 1 at the same time. This is the Principle of Non-Contradiction.

From just one equation, Boole demonstrates mathematically the axioms that underlie all rational thought.

Further, in order to demonstrate that dichotomy is the limit of human comprehension, Boole writes a trichotomy:

x = y = z (identical sets);

xyz = x;

then,

x3 = x ;

This factors into

x ( 1 – x )(1 + x) = 0;

The solutions are 0, 1, and –1. To illustrate the cognitive disconnect: If x = “all men”, and (1 – x) = everything that is not “all men”, then what does (1 + x) represent? Boole points out that this is surely beyond the comprehension of human minds. So trichotomies are outside the realm of rational thought, at least in this universe, and for human faculties.

As beautiful and remarkable as this is, it occupies only the first three chapters of Boole’s work. He goes on to analyze propositions, including if/then, and then it’s off into probability theory.

Sunday, November 1, 2009

Solved: Homer Simpson's Mysterious Equation: P = NP.

Today I solved the Mysterious Homer Simpson Equation.

The Homer Simpson mystery is described in an article by Larry Hardesty at physorg.com:

“In the 1995 Halloween episode of The Simpsons, Homer Simpson finds a portal to the mysterious Third Dimension behind a bookcase, and desperate to escape his in-laws, he plunges through. He finds himself wandering across a dark surface etched with green gridlines and strewn with geometric shapes, above which hover strange equations. One of these is the deceptively simple assertion that P = NP. [emphasis original]

“In fact, in a 2002 poll, 61 mathematicians and computer scientists said that they thought P probably didn’t equal NP, to only nine who thought it did — and of those nine, several told the pollster that they took the position just to be contrary. But so far, no one’s been able to decisively answer the question one way or the other. Frequently called the most important outstanding question in theoretical computer science, the equivalency of P and NP is one of the seven problems that the Clay Mathematics Institute will give you a million dollars for proving — or disproving.”
The article pursues a proposed computing aspect of the equation, and says,

“A mathematical expression that involves N’s and N2s and N’s raised to other powers is called a polynomial, and that’s what the “P” in “P = NP” stands for. P is the set of problems whose solution times are proportional to polynomials involving N's.”

But the proposed solution is actually saying that N is fully contained within P, i.e. a subset of P (wholly owned subsidiary?). That makes the solution trivial on its face, and tautological on inspection. Because if the intersection of N and P is less than P, it cannot equal P; the equation is only valid if N = P. This makes the equation an identity or definition of N = P, merely a tautology without overall meaning. So the solution proposed by the article is less than philosophically robust, and without any dramatic meaning that can be derived from it.

The real answer to Homer’s Mystery Equation comes directly from George Boole (note 1), who mathematically codified human reason in his Boolean algebra. Boole gave us the following definition (note 2):

x2 = x

This is the mathematical definition of a universal set. Here’s why:

Factoring, x ( 1 - x) = 0 ;

If x is the set of “x things”, then 1-x is the set of ALL “non-x things”; the union of these sets is the universal set.

So for P=NP, the universal set occurs when N=P: P=PP, or P=P2.

Now the relationship N=P has meaning, because as Boole shows, this equation has only two solutions, 1 and 0, and the impact of this is that all three of the First Principles of Rational thought are confirmed mathematically. Tautology / identity has been produced; Non-contradiction is shown (either one or zero but not both); and Excluded Middle is shown (there is no intermediated solution between 0 and 1).

Thus Homer’s Mystery Equation, P=NP, is the universal axiom equation for rational thought and logic, when P=N, and when P does not equal N, the equation is either trivial (N < P) or nonviable (N > P).

What did you do with your day today?


Note 1: A History of Mathematics, 1968; Carl B. Boyer; pages 577 - 581.

Note 2: An Investigation of The Laws of Thought, 1853; George Boole; Ch II, page 22.