Story
Definition 1
Leonhard Euler was asked the question: is it possible, while walking around Koenigsberg, to bypass all the bridges of the city without passing through any of them twice. A plan of the city with seven bridges was attached.
In a letter to an Italian mathematician he knew, Euler gave a short and beautiful solution to the problem of Königsberg bridges: with such an arrangement, the problem is unsolvable. At the same time, he indicated that the question seemed interesting to him, because. "Neither geometry nor algebra is sufficient for its solution...".
When solving many problems, L. Euler depicted sets using circles, which is why they were called "Euler circles". This method was used even earlier by the German philosopher and mathematician Gottfried Leibniz, who used them to geometrically explain the logical relationships between concepts, but more often used linear diagrams. Euler, on the other hand, developed the method quite thoroughly. Graphical methods became especially famous thanks to the English logician and philosopher John Venn, who introduced Venn diagrams and similar schemes are often called Euler-Venn diagrams. They are used in many areas, for example, in set theory, probability theory, logic, statistics and computer science.
Diagramming principle
Until now, Euler-Venn diagrams are widely used to schematically depict all possible intersections of several sets. The diagrams show all $2^n$ combinations of n properties. For example, if $n=3$, the diagram shows three circles with centers at the vertices of an equilateral triangle and the same radius, which is approximately equal to the length of the side of the triangle.
Logical operations define truth tables. The diagram shows a circle with the name of the set it represents, for example, $A$. The area in the middle of the circle $A$ will display the truth of the expression $A$, and the area outside the circle - false. To display a logical operation, only those areas are shaded in which the values of the logical operation for the sets $A$ and $B$ are true.
For example, the conjunction of two sets $A$ and $B$ is true only if both sets are true. In this case, on the diagram, the result of the conjunction of $A$ and $B$ will be the area in the middle of the circles, which simultaneously belongs to the set $A$ and the set $B$ (the intersection of sets).
Figure 1. Conjunction of sets $A$ and $B$
Using Euler-Venn diagrams to prove logical equalities
Consider how the method of constructing Euler-Venn diagrams is used to prove logical equalities.
Let us prove the de Morgan law, which is described by the equality:
Proof:
Figure 4. $A$ inversion
Figure 5. $B$ inversion
Figure 6. Conjunction of $A$ and $B$ inversions
After comparing the area for displaying the left and right parts, we see that they are equal. From this follows the validity of logical equality. De Morgan's law is proven using Euler-Venn diagrams.
Solving the problem of searching for information on the Internet using Euler-Venn diagrams
To search for information on the Internet, it is convenient to use search queries with logical connectives similar in meaning to the conjunctions "and", "or" of the Russian language. The meaning of logical connectives becomes clearer if we illustrate them with the help of Euler-Venn diagrams.
Example 1
The table shows examples of queries to the search server. Each request has its own code - a letter from $A$ to $B$. You need to arrange the request codes in descending order of the number of pages found for each request.
Figure 7
Decision:
Let's build an Euler-Venn diagram for each query:
Figure 8
Answer: BVA.
Solving a logical meaningful problem using Euler-Venn diagrams
Example 2
During the winter holidays, out of the $36$ students in the $2$ class, they did not go to the cinema, the theater, or the circus. $25$ people went to the cinema, $11$ to the theater, $17$ to the circus; both in the cinema and in the theater - $6$; and in the cinema and in the circus - $10$; and to the theater and to the circus - $4$.
How many people have visited the cinema, the theater, and the circus?
Decision:
Let's denote the number of guys who have been to the cinema, the theater, and the circus - $x$.
Let's build a diagram and find out the number of guys in each area:
Figure 9
Were not in the theater, nor in the cinema, nor in the circus - $2$ per person.
So $36 - 2 = $34 people. attended events.
$6$ people went to the cinema and the theater, which means that only ($6 - x)$ people went to the cinema and the theater.
$10$ people went to the cinema and the circus, so only to the cinema and the circus ($10 - x$) people.
$4$ people went to the theater and the circus, which means that only the theater and the circus ($4 - x$) people went to the theater and the circus.
$25$ people went to the cinema, which means that only $25 - (10 - x) - (6 - x) - x = (9+x)$ went to the cinema.
Similarly, only ($1+x$) people went to the theater.
Only ($3+x$) people went to the circus.
So, we went to the theater, cinema and circus:
$(9+x)+(1+x)+(3+x)+(10-x)+(6-x)+(4-x)+x = 34$;
Those. only one person went to the theater, and to the cinema, and to the circus.
VENN DIAGRAM - a graphical way to set and analyze logical-mathematical theories and their formulas. They are built by dividing a part of the plane into cells (subsets) by closed contours (Jordan curves). The cells provide information that characterizes the theory or formula under consideration. The purpose of constructing diagrams is not only illustrative, but also operator - algorithmic processing of information. The apparatus of Venn diagrams is usually used in conjunction with the analytical one.
The method of partitioning, the number of cells, as well as the problems of writing information in them depend on the theory under consideration, which can also be introduced (described) graphically - by some Venn diagrams, given initially, in particular, together with their transformation algorithms, when some diagrams can act as operators acting on other diagrams. For example, in the case of classical propositional logic for formulas composed of n different propositional variables, a part of the plane (universe) is divided into 2 "cells corresponding to constituents (in conjunctive or disjunctive form). The Venn diagram of each formula is such a plane, in the cells of which an asterisk is placed (or not placed) * So, the formula
(¬a& ¬b&c) V (a&¬b&c) V (¬a&b&¬c)
with three propositional variables a, b and c defines the diagram shown in the figure, where the asterisks in the cells correspond to the conjunctive components of this perfect normal disjunctive formula. If there are no starred cells, then the Venn diagram is associated, for example, with an identically false formula, say (a&¬ a).
The inductive method of splitting a plane into 2 "cells goes back to the works of the English logician J. Venn, is called the Venn method and consists of the following:
1. For n = 1, 2, 3 circles are used in an obvious way. (In the figure, n = 3.)
2. Assume that for n = k (k ≥ 3), such arrangement of k figures is indicated that the plane is divided into 2k cells.
Then, to place k + 1 figures on this plane, it is sufficient, first, to choose an open curve (cp without self-intersection points, i.e., an open Jordan curve that belongs to the boundaries of all 2k cells and has only one common piece with each of these boundaries. Second, circle φ closed Jordan curve Ψ k+1 so that the curve Ψ k+1 passed through all 2k cells and crossed the border of each cell only twice. This will result in an arrangement of n= k+1 figures such that the plane is divided into 2k+1 cells.
To represent other logico-mathematical theories, the method of Venn diagrams is extended. The theory itself is written in such a way as to highlight the elements of its language in a form suitable for graphic representation. For example, atomic formulas of classical predicate logic are written as words of the form P(Y1..Yr), where P is predicate and Y1,..., Yr are object variables, not necessarily distinct; the word Y1,..., Yr is a subject infix. The obvious set-theoretic nature of Venn diagrams makes it possible to represent and study with their help, in particular, set-theoretic calculi, for example, the ZF calculus of Zermelo-Fraenkel set theory. Graphical methods in logic and mathematics have been developed for a long time. Such, in particular, are the logical square, Euler's circles and the original diagrams of L. Carroll. However, the method of Venn diagrams differs significantly from the well-known method of Euler circles used in traditional syllogistics. Venn diagrams are based on the idea of decomposing a Boolean function into constituents - the central idea in the algebra of logic, which determines their operational nature. Venn used his diagrams primarily to solve problems of class logic. Its diagrams can also be effectively used for solving propositional and predicate logic problems, reviewing consequences from premises, solving logical equations, and other issues, up to the solvability problem. The apparatus of Venn diagrams is used in applications of mathematical logic and automata theory, in particular, in solving problems related to neural circuits and the problem of synthesizing reliable circuits from relatively unreliable elements.
A. S. Kuzichev
New Philosophical Encyclopedia. In four volumes. / Institute of Philosophy RAS. Scientific ed. advice: V.S. Stepin, A.A. Huseynov, G.Yu. Semigin. M., Thought, 2010, vol. I, A - D, p. 645.
Literature:
Venn J. Symbolic logic. L., 1881. Ed. 2, rev. L., 1894;
Kuzichev A. S. Venn diagrams. History and applications. M., 1968;
He is. Solving some problems of mathematical logic using Venn diagrams. - In the book: The study of logical systems. M., 1970.
Set equality.
Sets BUT and AT are considered equal if they are from the same elements.
Set equality is defined as follows: A = B.
If the sets are not equal, then write A ¹ B.
Recording the equality of two sets A = B is equivalent to writing BUTÌ AT, or ATÌ BUT.
For example, the set of solutions to the equation x 2 - 5x+ 6 = 0 contains the same elements (the numbers 2 and 3) as the set of primes less than five. These two sets are equal. (A prime number is a natural number that is only divisible without remainder by 1 and itself; moreover, 1 is not a prime number.)
Intersection (multiplication) of sets.
A bunch of D, consisting of all elements belonging to and set A and set B, is called the intersection of the sets BUT and AT and denoted D = A AT.
Consider two sets: X= (0, 1, 3, 5) and Y= (1, 2, 3, 4). Numbers 1 and 3 and only they belong simultaneously to both sets X and Y. The set (1, 3) composed of them contains all the common for sets X and Y elements. Thus, the set (1, 3) is the intersection of the considered sets X and Y:
{1, 3} = {0, 1, 3, 5} {1, 2, 3, 4}.
For the segment [-1; 1] and interval ]0; 3[ the intersection, i.e., the set consisting of common elements, is the interval ]0; 1] (Fig. 1).
Rice. 1. Intersection of the segment [-1; 1] and interval ]0; 3[ is the interval ]0; one]
The intersection of a set of rectangles and a set of rhombuses is a set of squares.
The intersection of a set of eighth grade students of a given school and a set of members of the chemistry circle of the same school is a set of eighth grade students who are members of the chemistry circle.
The intersection of sets (and other operations - see below) is well illustrated by a visual representation of sets on a plane. Euler suggested using circles for this. Image of the intersection (highlighted in gray) of sets BUT and AT using Euler circles is shown in Fig. 2.
Rice. 3. Euler-Venn diagram of the intersection (highlighted in gray) of sets BUT and AT, which are subsets of some universe depicted as a rectangle
If the sets BUT and AT do not have common elements, then they say that these sets do not intersect or that their intersection is an empty set, and write BUT AT = Æ.
For example, the intersection of the set of even numbers with the set of odd numbers is empty.
The intersection of numerical intervals ]-1 is also empty; 0] and -1; 0] and )
