Boolean algebra. Algebra of logic. Elements of mathematical logic

In the modern world, we increasingly use a variety of machines and gadgets. And not only when it is necessary to apply a literally inhuman force: move the load, lift it to a height, dig a long and deep trench, etc. Cars today collect robots, food is prepared by multivarqua, and elementary calculating calculations are made by calculators. Increasingly, we hear the expression "Boolean algebra." Perhaps it's time to understand the role of man in the creation of robots and the ability of machines to solve not only mathematical, but also logical tasks.

Logics

In Greek, logic is an ordered system of thinking that creates interrelations between given conditions and allows you to make inferences based on assumptions and assumptions. Quite often we ask each other: "Is it logical?" The answer answers our assumptions or criticizes the course of thought. But the process does not stop: we continue to reason.

Sometimes the number of conditions (introductory) is so great, and the interrelations between them are so complicated and complex that the human brain is not able to "digest" everything at once. It may take more than a month (a week, a year) to understand what is happening. But modern life does not give us such time intervals for decision-making. And we resort to the help of computers. And this is where the algebra of logic appears, with its laws and properties. Having downloaded all the initial data, we allow the computer to recognize all the relationships, eliminate contradictions and find a satisfactory solution.

Mathematics and Logic

The most famous Gottfried Wilhelm Leibniz formulated the concept of "mathematical logic", whose tasks were accessible only to a narrow circle of scientists. A special interest in this direction did not cause, and until the middle of the XIX century few knew about mathematical logic.

Great interest in scientific communities was aroused by a dispute in which Englishman George Buhl announced his intention to create a section of mathematics that had absolutely no practical application. As we remember from history, at that time industrial production actively developed, all kinds of auxiliary machines and machines were developed, that is, all scientific discoveries had a practical orientation.

Looking ahead, we will say that Boolean algebra is the most used part of mathematics in the modern world. So the dispute lost his Boule.

George Boule

The very personality of the author deserves special attention. Even taking into account the fact that in the past people grew older than us, we still can not fail to note that at the age of 16, G.Boole taught at a village school, and by the age of 20 opened his own school in Lincoln. Mathematician perfectly mastered five foreign languages, and in his spare time read out the work of Newton and Lagrange. And all this is about the son of a simple worker!

In 1839, Boule first sent his scientific papers to the Cambridge Mathematical Journal. The scientist was 24 years old. Boole's work so interested members of the Royal Scientific Society that in 1844 he received a medal for his contribution to the development of mathematical analysis. Several other published works, in which elements of mathematical logic were described, enabled the young mathematician to take the post of professor at the Cork County College. Recall that the very Boole education was not.

Idea

In principle, the Boolean algebra is very simple. There are statements (logical expressions), which, in terms of mathematics, can only be defined by two words: "truth" or "lie." For example, in spring the trees bloom - the truth, in the summer it snows - lies. All the charm of this mathematics is that there is no strict need to use only numbers. Any propositions with unambiguous meaning are perfectly suitable for the algebra of propositions.

Thus, logic algebra 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 does not matter how we determine the truth or falsity of a statement. From these "how" and "why" should be abstracted. The only thing that matters is the statement of fact: true-false.

Of course, the functions of the algebra of logic are important for programming, which are written with the appropriate signs and symbols. And to learn them means to master a new foreign language. Nothing is impossible.

Basic concepts and definitions

Without going into the depths, we will understand the terminology. So, Boolean algebra assumes the presence of:

• Statements;
• Logical operations;
• Functions and laws.

Statements are any affirmative expressions that can not be interpreted double-valued. They are written in the form of numbers (5> 3) or formulated in the usual words (the elephant is the largest mammal). At the same time, the phrase "the giraffe does not have a neck" also has the right to exist, only Boolean algebra will define it as a "lie".

All statements must be unambiguous, but they can be elementary and composite. The latter use logical connectives. That is, in the propositional algebra compound statements are formed by adding elementary elements through logical operations.

Operations of Boolean algebra

We already remember that operations in the algebra of propositions are logical. Just as algebra of numbers uses arithmetic operations to add, subtract or compare numbers, the elements of mathematical logic make it possible to compose complex statements, to give a negative or to calculate the final result.

Logical operations for formalization and simplicity are written down by the formulas customary for us in arithmetic. Properties of Boolean algebra make it possible to write equations and calculate unknowns. Logical operations are usually written using a truth table. Its columns define the computation elements and the operation that is performed on them, and the lines show the result of the calculations.

Basic logical actions

The most common operations in Boolean algebra are negation (NOT) and logical AND and OR. So you can describe almost all the actions in the algebra of judgments. We will study in detail each of the three operations.

Negation (not) applies only to one element (operand). Therefore, the negation operation is called unary. To write the notion of "not A" use such symbols: ¬A, A¯¯¯ or! A. In tabular form it looks like this:

For the negation function, the following statement is typical: if A is true, then A is false. For example, the Moon revolves around the Earth - the truth; The earth revolves around the moon - a lie.

Logical multiplication and addition

A logical AND is called a conjunction operation. What does it mean? First, that it can be applied to two operands, that is, I is a binary operation. Secondly, that only in the case of the truth of both operands (and A, and B) is the expression itself true. The proverb "Patience and work will peretrut" assumes that only two factors will help a person cope with the difficulties.

Symbols are used for recording: A∧B, A⋅B or A && B.

Conjunction is analogous to multiplication in arithmetic. Sometimes they say so - logical multiplication. If we multiply the table elements by rows, we get a result similar to logical thinking.

Disjunction is called the logical OR operation. It takes on a truth value when at least one of the statements is true (or A, or B). It is written like this: A∨B, A + B or A || B. Truth tables for these operations are:

The disjunction is like an arithmetic addition. The operation of logical addition has only one restriction: 1 + 1 = 1. But we remember that in the digital format mathematical logic is limited to 0 and 1 (where 1 is true, 0 is false). For example, the statement "in the museum you can see a masterpiece or meet an interesting interlocutor" means that you can see works of art, and you can get acquainted with an interesting person. At the same time, it is not excluded the option of simultaneous completion of both events.

Functions and laws

So, we already know what logical operations Boolean algebra uses. Functions describe all the properties of elements of mathematical logic and allow you to simplify complex compound conditions of tasks. The most understandable and simple is the property of abandoning derivative operations. Derivatives are exclusive OR, implication, and equivalence. Since we have only familiarized ourselves with the basic operations, we will only consider the properties of them.

Associativity means that in statements like "and A, and B, and B," the enumeration of operands does not matter. The formula is this:

(A∧B) ∧ B = A∧ (Б∧В) = A∧Б∧В,

(A∨B) ∨B = A∨ (BBV) = A∨B∨B.

As we see, this is peculiar not only to conjunctions, but also disjunctions.

Commutativity asserts that the result of a conjunction or disjunction does not depend on which element was considered at the beginning:

A∧Б = Б∧A; A∨B = B∨A.

Distributivity allows you to open parentheses in complex logical expressions. The rules are similar to the disclosure of parentheses when multiplying and adding to algebra:

A∧ (Б∨В) = A∧Б∨A∧В; A∨B∧B = (A∨B) ∧ (A∨B).

The properties of a unit and a zero that can be one of the operands are also analogous to algebraic multiplication by zero or one and addition to one:

A∧0 = 0, A∧1 = A; A∨0 = A, A∨1 = 1.

Idempotency tells us that if the result of the operation turns out to be similar with respect to two equal operands, then you can "throw out" the extra operas that complicate the course of reasoning. Both the conjunction and the disjunction are idempotent operations.

БББ = Б; БББ = Б.

Absorption also allows us to simplify equations. Absorption states that when an 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

Sequence of operations is of no small importance. Actually, as for algebra, there is a priority of functions that uses the Boolean algebra. Formulas can be simplified only if the importance of operations is observed. Ranking from the most significant to minor, we get the following sequence:

1. Denial.

2. Conjunction.

3. Disjunction excluding OR.

4. Implication, equivalence.

As we see, only denial and conjunctions do not have equal priorities. And the priority of the disjunction and the exclusive OR 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 implication and equivalence.

Implication, or logical adherence, is a statement in which one action is a condition, and another is a consequence of its fulfillment. In other words, this sentence with the pretexts "if ... then." "You like to ride, love and sledge to carry." That is, for skating it is necessary to tighten the sleds to the slide. If there is no desire to leave the mountain, then you do not have to carry sleds. It is written like this: A → B or A⇒B.

Equivalence implies that the resulting action occurs only when both operands are true. For example, the night is replaced by the day then (and only then), when the sun rises from the horizon. In the language of mathematical logic, this statement is written as: A≡B, A⇔B, A == B.

Other laws of Boolean algebra

The judgment algebra develops, and many interested scientists have formulated new laws. The most famous are the postulates of the Scottish mathematician O. de Morgan. He noticed and defined such properties as close negation, addition and double negation.

A close negation suggests that there is not a single negation before the bracket: not (A or B) = not A or NOT B.

When the operand is denied, regardless of its value, they say about the addition :

Б¬¬Б = 0; Б¬¬Б = 1.

And, finally, double negation compensates for itself. Those. Before the operand, either the negation disappears, or only one remains.

How to solve tests

Mathematical logic implies simplification of the given equations. Just as in algebra, it is first necessary to make the condition as easy as possible (get rid of complex introductions and operations with them), and then proceed to find the right answer.

What can be done for simplification? Convert all derived operations to simple ones. Then open all the parentheses (or vice versa, render out parentheses to shorten this element). The next step is to apply the properties of Boolean algebra in practice (absorption, properties of zero and units, etc.).

Ultimately, the equation must consist of a minimum number of unknowns, united by simple operations. It is easiest to look for a solution if you achieve a large number of close negations. Then the answer will pop up as though by itself.