When 1+1 equals 1 (part 1)

November 2 marks the 209th birthday George Booleone of the founders of mathematical logic, and this material is part of a large work dedicated to him and his legacy.

Today I'll explain what the equation 1 + 1 = 1 means in Boolean arithmetic and how it became a tool for designing complex digital circuits. Two people made the greatest contribution to this state of affairs: George Boole and Claude Shannon.

So let's start chronologically with George Boole.

In 1833, a young teacher Lincoln Mechanical Institute George Boole had the epiphany that it was his duty and destiny to explain the logic of human thought. At this time, his father was the curator of this educational institution. In Victorian Britain and its colonies, these were the names of educational institutions that we would today call “evening schools.” They were originally created to provide education to working men, most often in technical subjects. The main reason for the creation of institutes of mechanics was industrial revolution. They were often funded by local industrialists on the basis that they would ultimately benefit greatly from having more educated and skilled employees. Mechanics Institutes often included libraries for working-class adults as an alternative to gambling and drinking in pubs.

Boole worked in various areas of mathematics, but among the general public he is best known for his pioneering work on symbolic logic. In two works, “Mathematical analysis of logic” And “A study of the laws of thinking on which mathematical theories of logic and probability are based”Boole reworked algebraic notation for the needs of logic. Classes of things were represented by letters, and addition and multiplication symbols were used to represent operations on these classes, although in practice Boole's algebra omitted multiplication symbols, as is done in ordinary algebra. If x – the class of all cats, and y – the class of all dogs, then (x+y) is a class consisting of all cats and dogs, whereas xy – the class of animals that are both cats and dogs is empty because catdog exists only in the series by animator Peter Hannan.

Nowadays we call Boole classes sets, so for example the empty class is called the empty set, but for now let's stick to Boole's original terminology.

The picture below showing four Venn diagramstwo overlapping circles are used. The one on the left represents the class xand the one on the right is the class y. Imagine that each diagram circle is filled with objects belonging to the corresponding class. The class of elements belonging to both classes is called the intersection of the two classes. Elements that do not belong to any class are outside the circles. Class of elements belonging to x, y or both, is called a union of two classes (shown schematically in the lower right corner). I will write about the question mark in the lower right diagram below, and it is associated with Boole's big mistake.

Let's take a classic syllogism in the style of Aristotle – “All men are mortal, Socrates is a man, therefore Socrates is mortal” – and let's see how Boole could deal with it algebraically, using his way of “multiplying” classes. If h – a class of people, and m – a class of mortal beings, then hm = h. To understand why, remember that hmm denotes the class of all beings who are both human and mortal; and since all men are mortal, the expression “man is mortal” is simply a verbal way of saying “man.” Likewise, every being who is both Socrates and a man is Socrates, therefore sh = s (Where s – a class consisting of Socrates and no one else). Now we can write the proof sm = sthat is, “Socrates is mortal,” which does not use words at all:

Louis Couture in the book “Algebra of Logic” Boole described his achievement this way: “Symbolic logic is essentially Aristotle’s logic given new life and power by wearing the wonderful, almost magical armor and equipment of algebra.”.

Of course, some may argue that Boole should not have used addition and multiplication for non-numerical purposes. After all, one of the basic rules of Boole algebra was that every class x must satisfy the formula x × x = xsince, for example, “a cat that is a cat” is just a verbal way of saying “cat”. But the formula x × x = x does not hold for ordinary algebra (unless x is not equal to 0 or 1 – I'll come back to this point shortly).

Another reason why Boole perhaps should not have used algebraic notation is that it was contrary to the practices of non-mathematical logicians of his time. John Venn, one of the first supporters of Boole's innovations, wrote: “On the part of those logicians who can without offense be called anti-mathematicians, there is certainly a prejudice against any work purporting to be a work on logic in which the symbols of the simplest arithmetical operations are freely used.”. But Boole's inspiration was precisely algebraic, and he did not want to hide the source of his inspiration. And, as we saw with the mortal Socrates, thoughtfully chosen notation can simplify some part of the thinking process.

Boole saw that 0 and 1, two numerical solutions x × x = xmust have analogues in the class area. He reasoned that the class 0, as an analogue of the number 0, should have the property that x × 0 And 0×x are always 0, no matter what the class is x. The only class with this property is the empty class. On the other hand, class 1, in order to be an analogue of the number 1, must have the property that x × 1 And 1×x always equal xand the only class with this property is the class consisting of all the things Boole called Universe. Empty class (you could say Null universe) and the Universe were the original 0 and 1 of Boole's theory.

“Wait, what nonsense. 1 is True and 0 is False in Boolean logic!”

This is not true, in fact these were only secondary values ​​of 1 and 0 in the Boole system. He used his class algebra to create a sentence algebra like the one I used to prove the Socratic syllogism, and in this context 1 refers to sentences that are always true and 0 refers to true sentences that are always false.

Later, Boole was happy to discover that the idea of ​​substantiating logic on the dichotomy of zero and one had been put forward a century and a half before him G.V. Leibniz (he represented conjunction of sentences using matching of related symbols, although to my knowledge he never associated logical conjunction with multiplication of numbers or variables). Leibniz was also delighted when he learned in 1689 that binary arithmetic, which he had invented earlier that year, fit perfectly into the binary world system I Chinginvented in China several thousand years earlier.

Speaking of Asia, it seems likely that Indian thought also influenced Boole. A well-known member of Boole's social circle was George Everestwho at one time was inspector general Great Trigonometric Survey of India. Now he is remembered for the fact that he unwittingly gave his name to the peak, which he more modestly called Peak XV. Everest himself would have hated the peak's modern name, as he believed that local names should be used for geographical features.

Everest was a student of Indian culture and passed on this interest to others, including Boole. Boole subsequently married Everest's niece Mary, who was also a mathematics teacher. She later wrote that Boole was heavily influenced by Indian logic, which Everest taught him, and she wrote: “Consider what the influence of the intense Hinduization of three such men as Babbage, De Morgan and George Boole must have been on the mathematical atmosphere of the years 1830-65.”. By the way, a very interesting woman, but about her read here.

Although Boole's work was respected among logicians and mathematicians, Mary later wrote that he was disappointed by the inability of readers to fully appreciate what his work was really about. “Investigation of the Laws of Thought”. Even though the name alone should have clearly indicated the scale of his ambitions.

“Almost all logicians and mathematicians have ignored the assertion that the book was intended to throw light on the nature of the human mind; and treated the formula exclusively as a remarkable new method of bringing into logical order the mass of evidence about external facts.”

To the last day of his life, Boole insisted that in his class arithmetic the attempt to add 1 and 1 was meaningless. Boule came from “law of thinking” x × x = x and came to the conclusion that in some sense classes must behave like variables that can only take the values ​​0 or 1. But for him, one was the class of everything (the Universe), and he did not think that it made sense to add classes if they initially had some common elements. For Boole, a prerequisite for being able to write down (x+y) knew in advance that x And y do not intersect, that is, they do not have common elements. And in the case when x And y both are the Universe, this is as far from the truth as it can be: everything belongs as xso yWhen x And y both contain everything.

Logician William Jevonsdespite all his admiration for Boole, believed that he was simply mistaken about this. He saw no philosophical problem in combining two classes that had common elements, and believed that addition was the ideal way to represent the resulting larger class. In particular, Jevons was clear that if you add any class to itself, the result will be the same class again. In symbols x + x = xwhich in the special case when x – The Universe gives us 1 + 1 = 1. In his letter, Jevons warned Boole that his system, with its unjustifiably limited concept of addition, could be considered “the most remarkable combination of truth and error”. But Boole could not accept the equation 1 + 1 = 1because he was still captive to the rules of ordinary algebra. Indeed, if Boole accepted that 1 + 1 = 1he would have to accept 1 + 1 = 1 + 0but then, by eliminating one on both sides of the equation, he would get one equal to zero, which equates Universe To Null Universethereby destroying everything.

Here we see how Peacock's principle of constancyinterpreted in its broadest sense (preserve all algebraic laws whenever possible), does not provide clear guidance to mathematicians.

What does “whenever possible” mean? Here's the rub. Boole and Jevons both saw that in class algebra there was a tension between two principles of algebra that were true for numbers: the principle of cancellation for addition and the principle that any two quantities can be added. What principle had to give way? The principle of constancy does not tell us this. Perhaps the best way to resolve such conflict is to alternately discard assumptions and compare the resulting solutions. George Boole was not so flexible.

One of the reasons he stood his ground was his concept of addition. It allowed him to express Jevons' notion of unlimited class associations in a roundabout way: if classes x And y overlapped, Boole could write their union as x + (1−x)y. A class consisting of everything that is in xalong with everything that is not in xbut there is in y. But he couldn't apply the usual rules of algebra to rewrite it as x + y − xy. Based on his concepts, Boole would have already said at this moment, after the first two terms: “Okay, stop!” It’s a pity, if he had tackled this type of equation, he could have been a little earlier than the Portuguese da Silva publish inclusion-exclusion principle and apply it to the study of probability theory.

At the end of 1864, a tragic contradiction occurred when Boole's active nature collided with his poor health and a period of disgusting weather. He walked three miles to the university in pouring rain, gave a lecture in wet clothes, soon contracted pneumonia and died on December 8 of that year at 49.

Later that year, Jevons published his own book “Pure Logic” (Pure Logic: Or, The Logic of Quality Apart from Quantity), with remarks about the Boole system and the connection between logic and mathematics. In the Jevons system, any two classes can be added. For example, if we take h And mas before, then h+m is the class consisting of all men and all mortal beings, which is the same as the class of all mortal beings. Thus, h+m equals m.

To get an idea of ​​how this expansion of Boole's definition of addition increased the power of his system, there is a different way than the one I described earlier to prove the Socratic syllogism. Since all men are mortal, h + m = mand since Socrates is a man, s + h = h. Now, as Leibniz would say, let's do the math!

We calculated that s + m = m. Since this tells us that the class containing Socrates along with all mortals is nothing other than the class of all mortals, we can conclude that Socrates is a mortal.

This proof was available to Jevons, but not to Boole, since for Boole the amounts that appear in the proof were meaningless. The added flexibility and power of Jevons' system rendered Boole's doubts moot. Jevons won, and no one except historians of mathematics and philosophy has Boole's logic in mind when he speaks of “Boolean logic”.

Boolean logic after Boolean

As Boole's followers simplified and improved the symbolic logic bequeathed to them by Boole, three logical operations came to the fore: conjunction, disjunction And negation.

The conjunction matches the word “AND”and is represented by the sign ∧; If p is the sentence “grass is green”, and q is the sentence “cows are purple”, then p∧q is a compound sentence: “grass is green and cows are purple.” This sentence is false, though p true because q false. Here is an operation table showing how the true value p∧q depends on the true value p and true meaning q:

Disjunction matches the word “OR” and is represented by the sign ∨; If p is the sentence “grass is green”, and q is the sentence “cows are purple”, then p ∨ q is the compound sentence “the grass is green or the cows are purple.” Here “OR” should be understood in its inclusive sense, sometimes called “AND/OR”So p ∨ q is true whenever at least one of the constituent sentences is true. This operation table shows how the true value p ∨ q depends on the true value p and true meaning q:

These days, when you search a database with a complex search term that combines primitive search terms using Boolean connectives “AND”, “OR” And “NOT”you're doing what's called a boolean search.

American philosopher and logician Charles Pierce considered the reformed Boolean system of doing logic congenial and used Boole's ideas to extend propositional logic from the study of the properties of individual objects to the study of relations between objects, anticipating the modern approach that models relationships as Boolean matrices. For example, if our discourse consists of Terah, Abraham, Sarah and Isaac (biblical characters), then the matrix shown below on the left encodes the relationship “gave birth”.

If we square this matrix, we get the matrix on the right. The two corresponds to the fact that Terah, the father of Abraham and Sarah, was twice the grandfather of Isaac. The new matrix is ​​not a Boolean matrix because of this two, but if we round the two to one, we get a Boolean matrix that encodes the relation “gave birth to the one who gave birth”that is “is the biological progenitor”. As an alternative to the matrix product, one can replace every positive integer that results in one, or, equivalently, replace ordinary arithmetic throughout with arithmetic 1 + 1 = 1. This is called the product of Boolean matrices.

In 1886, Peirce went so far as to suggest that logical operations could be performed by electrical switching circuits. He even commissioned one of his students, Allan Marquand, to create circuits for electrical logic machines. But neither Peirce nor Marquand built such a machine or published their ideas or sketches, and the idea was lost in dusty archives until Claude Shannon came on the scene and rethought Peirce's brilliant but abandoned idea. And I will write about this in the next part.

The UFO flew in and left a promotional code here for our blog readers:
— 15% on all VDS tariffs (except for the Warm-up tariff) — HABRFIRSTVDS