In today's world, we increasingly use a variety of cars and gadgets. And not only when it is necessary to apply literally inhuman strength: move the load, lift it to a height, dig a long and deep trench, etc. Cars today are assembled by robots, food is prepared by multicookers, and elementary arithmetic calculations are performed by calculators. More and more often we hear the expression "Boolean algebra". Perhaps it's time to understand the role of man in creating robots and the ability of machines to solve not only mathematical, but also logical problems.
Logic
Translated from Greek, logic is an ordered system of thinking that creates relationships between given conditions and allows you to draw conclusions based on premises and assumptions. Quite often we ask each other: "Is it logical?" The received answer confirms our assumptions or criticizes the train of thought. But the process does not stop: we continue to reason.
Sometimes the number of conditions (introductory) is so great, and the relationships between them are so intricate and complex that the human brain is not able to "digest" everything at once. It may take more than one month (week, year) to understand what is happening. Butmodern life does not give us such time intervals for making decisions. And we resort to the help of computers. And this is where the algebra of logic appears, with its own laws and properties. By downloading all the initial data, we allow the computer to recognize all the relationships, eliminate contradictions and find a satisfactory solution.
Math and Logic
The famous Gottfried Wilhelm Leibniz formulated the concept of "mathematical logic", the problems of which were understandable only to a narrow circle of scientists. This direction did not arouse particular interest, and until the middle of the 19th century, few people knew about mathematical logic.
Great interest in the scientific community caused a dispute in which the Englishman George Boole announced his intention to create a branch of mathematics that has absolutely no practical application. As we remember from history, industrial production was actively developing at that time, all kinds of auxiliary machines and machine tools were being developed, that is, all scientific discoveries had a practical focus.
Looking ahead, let's say that Boolean algebra is the most used part of mathematics in the modern world. So Bull lost his argument.
George Buhl
The very personality of the author deserves special attention. Even considering that in the past people grew up before us, it is still impossible not to note that at the age of 16, J. Buhl taught at a village school, and by the age of 20 he opened his own school in Lincoln. The mathematician was fluent in five foreign languages, and in his spare time he read worksNewton and Lagrange. And all this is about the son of a simple worker!
In 1839 Boole first submitted his scientific work to the Cambridge Mathematical Journal. The scientist is 24 years old. Boole's work so interested members of the Royal Society that in 1844 he received a medal for his contribution to the development of mathematical analysis. Several more published works, which described the elements of mathematical logic, allowed the young mathematician to take the post of professor at the College of Cork. Recall that Buhl himself had no education.
Idea
In principle, Boolean algebra is very simple. There are statements (logical expressions) that, from the point of view of mathematics, can be defined only by two words: “true” or “false”. For example, in the spring the trees bloom - true, in the summer it snows - a lie. The beauty of this math is that there is no strict need to use only numbers. For the algebra of judgments, any statements with an unambiguous meaning are quite suitable.
Thus, the algebra of logic can be used literally everywhere: in scheduling and writing instructions, analyzing conflicting information about events, and determining the sequence of actions. The most important thing is to understand that it is completely unimportant how we determine the truth or falsity of a statement. These "hows" and "whys" need to be abstracted away. Only the statement of fact matters: true-false.
Of course, for programming, the functions of the algebra of logic are important, which are written by the correspondingsigns and symbols. And to learn them means to master a new foreign language. Nothing is impossible.
Basic concepts and definitions
Without going into depth, let's deal with the terminology. So Boolean algebra assumes:
- statements;
- logical operations;
- functions and laws.
Statements are any affirmative expressions that cannot be interpreted ambiguously. They are written as numbers (5 > 3) or formulated in familiar words (elephant is the largest mammal). At the same time, the phrase “the giraffe has no neck” also has the right to exist, only Boolean algebra will define it as “false.”
All statements must be unambiguous, but they can be elementary and compound. The latter use logical connectives. That is, in the algebra of judgments, compound statements are formed by adding elementary statements by means of logical operations.
Boolean algebra operations
We already remember that operations in the algebra of judgments are logical. Just as number algebra uses arithmetic to add, subtract, or compare numbers, elements of mathematical logic allow you to make complex statements, negate, or calculate the final result.
Logical operations for formalization and simplicity are written by formulas familiar to us in arithmetic. The properties of Boolean algebra make it possible to write equations and calculate unknowns. Logical operations are usually written using a truth table. Its columnsdefine the elements of the calculation and the operation that is performed on them, and the lines show the result of the calculation.
Basic logical actions
The most common operations in Boolean algebra are negation (NOT) and logical AND and OR. Almost all actions in the algebra of judgments can be described in this way. Let's study each of the three operations in more detail.
Negation (not) applies to only one element (operand). Therefore, the negation operation is called unary. To write the concept of "not A" use the following symbols: ¬A, A¯¯¯ or !A. In tabular form it looks like this:
The negation function is characterized by the following statement: if A is true, then B is false. For example, the Moon revolves around the Earth - true; The earth revolves around the moon - false.
Logical multiplication and addition
The logical AND is called the conjunction operation. What does it mean? Firstly, that it can be applied to two operands, i.e. And is a binary operation. Secondly, that only in the case of the truth of both operands (both A and B) is the expression itself true. The proverb "Patience and work will grind everything" suggests that only both factors will help a person cope with difficulties.
Symbols used for writing: A∧B, A⋅B or A&&B.
Conjunction is similar to multiplication in arithmetic. Sometimes they say that - logical multiplication. If we multiply the elements of the table row by row, we get a result similar to logical reasoning.
Disjunction is a logical OR operation. It takes the value of truthwhen at least one of the statements is true (either A or B). It is written like this: A∨B, A+B or A||B. The truth tables for these operations are:
Disjunction is like arithmetic addition. The logical addition operation has only one limitation: 1+1=1. But we remember that in digital format, mathematical logic is limited to 0 and 1 (where 1 is true, 0 is false). For example, the statement “in a museum you can see a masterpiece or meet an interesting interlocutor” means that you can see works of art, or you can meet an interesting person. At the same time, the possibility of both events occurring simultaneously is not ruled out.
Functions and laws
So we already know what boolean algebra uses. Functions describe all the properties of elements of mathematical logic and allow you to simplify complex compound conditions of problems. The most understandable and simple property seems to be the rejection of derived operations. Derivatives are XOR, implication and equivalence. Since we have studied only the basic operations, we will also consider the properties only of them.
Associativity means that in statements like “and A, and B, and C”, the order of the operands does not matter. The formula is written like this:
(A∧B)∧V=A∧(B∧V)=A∧B∧V, (A∨B)∨C=A∨(B∨C)=A∨B∨C.
As you can see, this is characteristic not only of conjunction, but also of disjunction.
Commutativity states that the resultconjunction or disjunction does not depend on which element was considered first:
A∧B=B∧A; A∨B=B∨A.
Distributivity allows expanding parentheses in complex logical expressions. The rules are similar to opening brackets in multiplication and addition in algebra:
A∧(B∨C)=A∧B∨A∧B; A∨B∧B=(A∨B)∧(A∨B).
The properties of one and zero, which can be one of the operands, are also similar to algebraic multiplication by zero or one and addition with one:
A∧0=0, A∧1=A; A∨0=A, A∨1=1.
Idempotency tells us that if, with respect to two equal operands, the result of an operation turns out to be similar, then we can “throw away” the extra operands that complicate the course of reasoning. Both conjunction and disjunction are idempotent operations.
B∧B=B; B∨B=B.
Absorption also allows us to simplify equations. Absorption states that when another operation with the same element is applied to an expression with one operand, the result is the operand from the absorbing operation.
A∧B∨B=B; (A∨B)∧B=B.
Sequence of operations
The sequence of operations is of no small importance. Actually, as for algebra, there is a priority of functions that Boolean algebra uses. Formulas can be simplified only if the significance of the operations is observed. Ranking from the most significant to the least, we get the following sequence:
1. Denial.
2. Conjunction.
3. Disjunction, exclusiveOR.
4. Implication, equivalence.
As you can see, only negation and conjunction do not have equal precedence. And the priority of disjunction and XOR are equal, as well as the priorities of implication and equivalence.
Implication and equivalence functions
As we have already said, in addition to the basic logical operations, mathematical logic and the theory of algorithms use derivatives. The most commonly used are implication and equivalence.
Implication, or logical consequence, is a statement in which one action is a condition, and the other is a consequence of its implementation. In other words, this is a sentence with prepositions "if … then." "If you like to ride, love to carry sleds." That is, for skiing, you need to tighten the sled up the hill. If there is no desire to move down the mountain, then you don’t have to carry the sled. It is written like this: A→B or A⇒B.
Equivalence assumes that the resulting action occurs only when both operands are true. For example, night turns into day when (and only when) the sun rises over the horizon. In the language of mathematical logic, this statement is written as follows: A≡B, A⇔B, A==B.
Other laws of Boolean algebra
The algebra of judgments is developing, and many interested scientists have formulated new laws. The postulates of the Scottish mathematician O. de Morgan are considered the most famous. He noticed and defined such properties as close negation, complement and double negation.
Close negation means that there is no negation before the parenthesis:not (A or B)=not A or NOT B.
When an operand is negated, regardless of its value, one speaks of a complement:
B∧¬B=0; B∨¬B=1.
And finally, the double negation compensates for itself. Those. either the negation disappears before the operand, or only one remains.
How to solve tests
Mathematical logic implies the simplification of given equations. Just like in algebra, you must first ease the condition as much as possible (get rid of complex inputs and operations with them), and then start looking for the right answer.
What can be done to simplify? Convert all derived operations to simple ones. Then open all the brackets (or vice versa, take it out of brackets to shorten this element). The next step should be to apply the properties of Boolean algebra in practice (absorption, properties of zero and one, etc.).
Ultimately, the equation should consist of the minimum number of unknowns combined by simple operations. The easiest way to find a solution is to achieve a large number of close negatives. Then the answer will pop up as if by itself.
