Basic operations on sets. Euler-Venn diagrams

Sections: Computer science

1. Introduction

In the course of Computer Science and ICT of the basic and senior school, such important topics as “Fundamentals of Logic” and “Searching for Information on the Internet” are discussed. When solving a certain type of problem, it is convenient to use Euler circles (Euler-Venn diagrams).

Mathematical reference. Euler-Venn diagrams are used primarily in set theory as a schematic representation of all possible intersections of several sets. In general, they represent all 2 n combinations of n properties. For example, with n=3, the Euler-Venn diagram is usually depicted as three circles with centers at the vertices of an equilateral triangle and the same radius, approximately equal to the length of the side of the triangle.

2. Representation of logical connectives in search queries

When studying the topic “Searching for information on the Internet”, examples of search queries using logical connectives, similar in meaning to the conjunctions “and”, “or” of the Russian language, are considered. The meaning of logical connectives becomes clearer if you illustrate them using a graphical diagram - Euler circles (Euler-Venn diagrams).

3. Connection of logical operations with set theory

Euler-Venn diagrams can be used to visualize the connection between logical operations and set theory. For demonstration, you can use the slides in Annex 1.

Logical operations are specified by their truth tables. IN Appendix 2 Graphic illustrations of logical operations along with their truth tables are discussed in detail. Let us explain the principle of constructing a diagram in the general case. In the diagram, the area of ​​the circle with the name A displays the truth of statement A (in set theory, circle A is the designation of all elements included in a given set). Accordingly, the area outside the circle displays the “false” value of the corresponding statement. To understand which area of ​​the diagram will display a logical operation, you need to shade only those areas in which the values ​​of the logical operation on sets A and B are equal to “true”.

For example, the implication value is true in three cases (00, 01, and 11). Let's shade sequentially: 1) the area outside the two intersecting circles, which corresponds to the values ​​A=0, B=0; 2) an area related only to circle B (crescent), which corresponds to the values ​​A=0, B=1; 3) the area related to both circle A and circle B (intersection) - corresponds to the values ​​A=1, B=1. The combination of these three areas will be a graphical representation of the logical operation of implication.

4. Use of Euler circles in proving logical equalities (laws)

In order to prove logical equalities, you can use the Euler-Venn diagram method. Let us prove the following equality ¬(АvВ) = ¬А&¬В (de Morgan's law).

To visually represent the left side of the equality, let’s do it sequentially: shade both circles (apply disjunction) with gray color, then to display the inversion, shade the area outside the circles with black color:

Fig.3 Fig.4

To visually represent the right side of the equality, let’s do it sequentially: shade the area for displaying the inversion (¬A) in gray and, similarly, the area ¬B also in gray; then to display the conjunction you need to take the intersection of these gray areas (the result of the overlay is represented in black):

Fig.5 Fig.6 Fig.7

We see that the areas for displaying the left and right parts are equal. Q.E.D.

5. Tasks in the State Examination and Unified State Exam format on the topic: “Searching for information on the Internet”

Problem No. 18 from the demo version of GIA 2013.

The table shows queries to the search server. For each request, its code is indicated - the corresponding letter from A to G. Arrange the request codes from left to right in order descending the number of pages that the search engine will find for each request.

For each query, we will build an Euler-Venn diagram:

Answer: VAGB.

Problem B12 from the demo version of the Unified State Exam 2013.

The table shows the queries and the number of pages found for a certain segment of the Internet.

How many pages (in thousands) will be found for the query? Destroyer?

It is believed that all queries were executed almost simultaneously, so that the set of pages containing all the searched words did not change during the execution of the queries.

Ф – number of pages (in thousands) on request Frigate;

E – number of pages (in thousands) on request Destroyer;

X – number of pages (in thousands) for a query that mentions Frigate And Not mentioned Destroyer;

Y – number of pages (in thousands) for a query that mentions Destroyer And Not mentioned Frigate.

Let's build Euler-Venn diagrams for each query:

According to the diagrams we have:

1. X + 900 + Y = F + Y = 2100 + Y = 3400. From here we find Y = 3400-2100 = 1300.
2. E = 900+U = 900+1300= 2200.

Answer: 2200.

6. Solving logical meaningful problems using the Euler-Venn diagram method

There are 36 people in the class. Pupils of this class attend mathematical, physics and chemical circles, with 18 people attending the mathematical circle, 14 people attending the physical circle, 10 people attending the chemical circle. In addition, it is known that 2 people attend all three circles, 8 people attend both mathematical and physical, 5 and mathematical and chemical, 3 - both physical and chemical.

How many students in the class do not attend any clubs?

To solve this problem, it is very convenient and intuitive to use Euler circles.

The largest circle is the set of all students in the class. Inside the circle there are three intersecting sets: members of the mathematical ( M), physical ( F), chemical ( X) circles.

Let MFC- a lot of guys, each of whom attends all three clubs. MF¬X- a lot of kids, each of whom attends math and physics clubs and Not visits chemical. ¬M¬FH- a lot of guys, each of whom attends the chemistry club and does not attend the physics and mathematics clubs.

We introduce sets similarly: ¬МФХ, М¬ФХ, М¬Ф¬Х, ¬МФ¬Х, ¬М¬Ф¬Х.

It is known that all three circles are attended by 2 people, therefore, in the region MFC Let's enter the number 2. Because 8 people attend both mathematical and physical circles, and among them there are already 2 people attending all three circles, then in the region MF¬X let's enter 6 people (8-2). Let us similarly determine the number of students in the remaining sets:

Let's sum up the number of people in all regions: 7+6+3+2+4+1+5=28. Consequently, 28 people from the class attend clubs.

This means 36-28 = 8 students do not attend clubs.

After the winter holidays, the class teacher asked which of the children went to the theater, cinema or circus. It turned out that out of 36 students in the class, two had never been to the cinema. neither in the theater nor in the circus. 25 people went to the cinema, 11 to the theater, 17 to the circus; both in cinema and theater - 6; both in the cinema and in the circus - 10; and in the theater and circus - 4.

How many people have been to the cinema, the theater, and the circus?

Let x be the number of children who have been to the cinema, the theater, and the circus.

Then you can build the following diagram and count the number of guys in each area:

Thus, Euler circles (Euler-Venn diagrams) find practical application in solving problems in the Unified State Examination and State Examination format and in solving meaningful logical problems.

Literature

1. V.Yu. Lyskova, E.A. Rakitina. Logic in computer science. M.: Informatics and Education, 2006. 155 p.
2. L.L. Bosova. Arithmetic and logical foundations of computers. M.: Informatics and Education, 2000. 207 p.
3. L.L. Bosova, A.Yu. Bosova. Textbook. Computer science and ICT for grade 8: BINOM. Knowledge Laboratory, 2012. 220 p.
4. L.L. Bosova, A.Yu. Bosova. Textbook. Computer science and ICT for grade 9: BINOM. Knowledge Laboratory, 2012. 244 p.
5. FIPI website: http://www.fipi.ru/

If you think you don't know anything about Euler circles, you're wrong. In fact, you've probably encountered them more than once, you just didn't know what it was called. Where exactly? Schemes in the form of Euler circles formed the basis of many popular Internet memes (images circulated online on a specific topic).

Let's figure out together what kind of circles these are, why they are called that and why they are so convenient to use to solve many problems.

Origin of the term

is a geometric diagram that helps to find and/or make logical connections between phenomena and concepts more clear. It also helps to depict the relationship between a set and its part.

It’s not very clear yet, right? Look at this picture:

The picture shows a variety of all possible toys. Some of the toys are construction sets - they are highlighted in a separate oval. This is part of a large set of “toys” and at the same time a separate set (after all, a construction set can be “Lego” or primitive construction sets made from blocks for kids). Some part of the large variety of “toys” may be wind-up toys. They are not constructors, so we draw a separate oval for them. The yellow oval “wind-up car” refers both to the set “toy” and is part of the smaller set “wind-up toy”. Therefore, it is depicted inside both ovals at once.

Well, has it become clearer? That is why Euler circles are a method that clearly demonstrates: it is better to see once than to hear a hundred times. Its merit is that clarity simplifies reasoning and helps to get an answer faster and easier.

The author of the method is the scientist Leonhard Euler (1707-1783). He said this about the diagrams named after him: “circles are suitable to facilitate our thinking.” Euler is considered a German, Swiss and even Russian mathematician, mechanic and physicist. The fact is that he worked for many years at the St. Petersburg Academy of Sciences and made a significant contribution to the development of Russian science.

Before him, the German mathematician and philosopher Gottfried Leibniz was guided by a similar principle when constructing his conclusions.

Euler's method has received well-deserved recognition and popularity. And after him, many scientists used it in their work, and also modified it in their own way. For example, Czech mathematician Bernard Bolzano used the same method, but with rectangular circuits.

The German mathematician Ernest Schroeder also made his contribution. But the main merits belong to the Englishman John Venn. He was a specialist in logic and published the book “Symbolic Logic”, in which he outlined in detail his version of the method (he used mainly images of intersections of sets).

Thanks to Venn's contribution, the method is even called Venn diagrams or Euler-Venn diagrams.

Why are Euler circles needed?

Euler circles have an applied purpose, that is, with their help, problems involving the union or intersection of sets in mathematics, logic, management and more are solved in practice.

If we talk about the types of Euler circles, we can divide them into those that describe the unification of some concepts (for example, the relationship between genus and species) - we looked at them using an example at the beginning of the article.

And also those that describe the intersection of sets according to some characteristic. John Venn was guided by this principle in his schemes. And it is this that underlies many popular memes on the Internet. Here is one example of such Euler circles:

It's funny, isn't it? And most importantly, everything immediately becomes clear. You can spend a lot of words explaining your point of view, or you can just draw a simple diagram that will immediately put everything in its place.

By the way, if you can’t decide which profession to choose, try drawing a diagram in the form of Euler circles. Perhaps a drawing like this will help you make your choice:

Those options that will be at the intersection of all three circles are the profession that will not only be able to feed you, but will also please you.

Solving problems using Euler circles

Let's look at some examples of problems that can be solved using Euler circles.

Here on this site - http://logika.vobrazovanie.ru/index.php?link=kr_e.html Elena Sergeevna Sazhenina offers interesting and simple problems, the solution of which will require the Euler method. Using logic and mathematics, we will analyze one of them.

Problem about favorite cartoons

Sixth graders filled out a questionnaire asking about their favorite cartoons. It turned out that most of them liked “Snow White and the Seven Dwarfs,” “SpongeBob SquarePants,” and “The Wolf and the Calf.” There are 38 students in the class. 21 students like Snow White and the Seven Dwarfs. Moreover, three of them also like “The Wolf and the Calf,” six like “SpongeBob SquarePants,” and one child equally likes all three cartoons. “The Wolf and the Calf” has 13 fans, five of whom named two cartoons in the questionnaire. We need to determine how many sixth graders like SpongeBob SquarePants.

Solution:

Since according to the conditions of the problem we are given three sets, we draw three circles. And since the guys’ answers show that the sets intersect with each other, the drawing will look like this:

We remember that according to the terms of the task, among fans of the cartoon “The Wolf and the Calf”, five guys chose two cartoons at once:

It turns out that:

21 – 3 – 6 – 1 = 11 – the guys chose only “Snow White and the Seven Dwarfs”.

13 – 3 – 1 – 2 = 7 – the guys only watch “The Wolf and the Calf.”

It remains only to figure out how many sixth-graders prefer the cartoon “SpongeBob SquarePants” to the other two options. From the total number of students we subtract all those who love the other two cartoons or chose several options:

38 – (11 + 3 + 1 + 6 + 2 + 7) = 8 – people only watch “SpongeBob SquarePants.”

Now we can safely add up all the resulting numbers and find out that:

cartoon “SpongeBob SquarePants” was chosen by 8 + 2 + 1 + 6 = 17 people. This is the answer to the question posed in the problem.

Let's also look at task, which in 2011 was submitted to the Unified State Examination demonstration test in computer science and ICT (source - http://eileracrugi.narod.ru/index/0-6).

Conditions of the problem:

In the search engine query language, the symbol "|" is used to denote the logical "OR" operation, and the symbol "&" is used for the logical "AND" operation.

The table shows the queries and the number of pages found for a certain segment of the Internet.

How many pages (in thousands) will be found for the query? Cruiser & Battleship?

It is assumed that all questions are executed almost simultaneously, so that the set of pages containing all the searched words does not change during the execution of queries.

Solution:

Using Euler circles we depict the conditions of the problem. In this case, we use the numbers 1, 2 and 3 to designate the resulting areas.

Based on the conditions of the problem, we create the equations:

1. Cruiser | Battleship: 1 + 2 + 3 = 7000
2. Cruiser: 1 + 2 = 4800
3. Battleship: 2 + 3 = 4500

To find Cruiser & Battleship(indicated in the drawing as area 2), substitute equation (2) into equation (1) and find out that:

4800 + 3 = 7000, from which we get 3 = 2200.

Now we can substitute this result into equation (3) and find out that:

2 + 2200 = 4500, from which 2 = 2300.

Answer: 2300 - the number of pages found by request Cruiser & Battleship.

As you can see, Euler circles help to quickly and easily solve even quite complex or simply confusing problems at first glance.

Conclusion

I think we have managed to convince you that Euler circles are not just a fun and interesting thing, but also a very useful method for solving problems. And not only abstract problems in school lessons, but also quite everyday problems. Choosing a future profession, for example.

You will probably also be curious to know that in modern popular culture Euler’s circles are reflected not only in the form of memes, but also in popular TV series. Such as “The Big Bang Theory” and “4Isla”.

Use this useful and visual method to solve problems. And be sure to tell your friends and classmates about it. There are special buttons under the article for this purpose.

website, when copying material in full or in part, a link to the source is required.

Story

Definition 1

Leonhard Euler was asked the question: is it possible, while walking around Königsberg, to go around all the bridges of the city without passing through any of them twice. A city plan with seven bridges is included.

In a letter to an Italian mathematician he knew, Euler gave a short and beautiful solution to the problem of the 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 are sufficient to solve it...”.

When solving many problems, L. Euler depicted sets using circles, which is why they got the name "Eulerian circles". This method was previously used by the German philosopher and mathematician Gottfried Leibniz, who used them to geometrically explain the logical connections between concepts, but more often used linear diagrams. Euler 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 diagrams are often called Euler-Venn diagrams. They are used in many fields, for example, in set theory, probability theory, logic, statistics and computer science.

Principle of diagramming

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, when $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 represent the truth of the expression $A$, and the area outside the circle will indicate 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, in 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 the sets).

Figure 1. Conjunction of the sets $A$ and $B$

Using Euler-Venn Diagrams to Prove Logical Equalities

Let's look at how the method of constructing Euler-Venn diagrams is used to prove logical equalities.

Let us prove De Morgan's law, which is described by the equality:

Proof:

Figure 4. Inversion of $A$

Figure 5. Inversion of $B$

Figure 6. Conjunction of inversions $A$ and $B$

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” in the Russian language. The meaning of logical connectives becomes clearer if they are illustrated using 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.

Solution:

Let's build an Euler-Venn diagram for each request:

Figure 8.

Answer: BVA.

Solving a logical meaningful problem using Euler-Venn diagrams

Example 2

During the winter holidays, out of $36$ students in the $2$ class were neither in the cinema, nor in the theater, nor in the circus. $25$ people went to the cinema, $11$ people went to the theater, $17$ people went to the circus; both in the cinema and in the theater - $6$; both to the cinema and to the circus - $10$; and to the theater and circus - $4$.

How many people have been to the cinema, the theater, and the circus?

Solution:

Let us denote the number of children who have been to the cinema, the theater, and the circus as $x$.

Let's build a diagram and find out the number of guys in each area:

Figure 9.

Haven't been to the theatre, cinema or circus - $2$ per person.

So, $36 - 2 = $34 people. attended events.

$6$ people went to the cinema and theater, which means only to the cinema and theater ($6 - x)$ people.

$10$ people went to the cinema and circus, which means only to the cinema and circus ($10 - x$) people.

$4$ people went to the theater and circus, which means only $4 - x$ people went to the theater and circus.

$25$ people went to the cinema, which means that $25 - (10 - x) - (6 - x) - x = (9+x)$ went to the cinema alone.

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, the cinema, and the circus.

Federal Agency for Education

State educational institution of higher professional education

National Research

Tomsk Polytechnic University

Institute of Natural Resources

Department of VM

ABSTRACT

Subject : « Euler-Venn diagram»

Executor:

Student of group 2U00

Supervisor:

Introduction……………………………………………………………………………….………..3

1. From history……………………………………………………………………………….….…..4

2. Euler-Venn diagram……………………………………………………………….…..4

3. Operations on Euler-Venn diagram sets………………….5

a) Association……………………….. ……………………………….……7

b) Intersection, addition………………….……………………………..7

c) Peirce's arrow, Schaeffer's stroke and difference....................................8

d) Difference……………………………………………………………8

e) Symmetric difference and equivalence…………………….…….9

Conclusion…………………………………………………………………………………10

References…………………………………………………….………..11

Introduction

Euler circles are a geometric diagram that can be used to depict relationships between subsets for visual representation. Circles were invented by Leonhard Euler. Used in mathematics, logic, management and other applied areas.

An important special case of Euler circles are Euler-Venn diagrams, which depict all 2n combinations of n properties, that is, a finite Boolean algebra. When n = 3, the Euler-Venn diagram is usually depicted as three circles with centers at the vertices of an equilateral triangle and the same radius, approximately equal to the length of the side of the triangle.

When solving a number of problems, Leonhard Euler used the idea of ​​representing sets using circles. However, this method was used even before Euler by an outstanding German philosopher and mathematician (1646-1716). Leibniz used them for a geometric interpretation of logical connections between concepts, but still preferred to use linear diagrams.

But L. Euler himself developed this method quite thoroughly. Euler's circle method was also used by the German mathematician Ernst Schröder (1841-1902) in his book “Algebra of Logic”. Graphic methods reached a particular flowering in the works of the English logician John Venn (1843-1923), who outlined them in detail in the book “Symbolic Logic”, published in London in 1881. Therefore, such diagrams are sometimes called Euler-Venn diagrams.

1.From history

Leonard Euler(1707 - 1783, St. Petersburg, Russian Empire) - mathematician, mechanic, physicist. Adjunct in physiology, professor of physics, professor of higher mathematics, who made a significant contribution to the development of mathematics, as well as mechanics, physics, astronomy and a number of applied sciences.

Euler is the author of more than 800 works on mathematical analysis, differential geometry, number theory, approximate calculations, celestial mechanics, mathematical physics, optics, ballistics, shipbuilding, music theory, etc.

He spent almost half his life in Russia, where he made a significant contribution to the development of Russian science. In 1726 he was invited to work in St. Petersburg, where he moved a year later. From 1711 to 1741, and also from 1766, he was an academician of the St. Petersburg Academy of Sciences (in 1741-1766 he worked in Berlin, while remaining at the same time an honorary member of the St. Petersburg Academy). He knew the Russian language well and published some of his works (especially textbooks) in Russian. The first Russian academic mathematicians (S.K. Kotelnikov) and astronomers (S.Ya. Rumovsky) were students of Euler. Some of his descendants still live in Russia.

John Venn (1, English logician. Worked in the field of class logic, where he created a special graphical apparatus (the so-called Venn diagrams), which found application in the logical-mathematical theory of “formal neural networks”. Venn is responsible for the justification of inverse operations in the logical calculus of J. Boole. Main John's area of ​​interest was logic, and he published three works on this topic: The Logic of Chance, which introduced the interpretation of frequency or frequency theory of probability in 1866, with which Venn diagrams were introduced in 1881; empirical logic" in 1889, which provides justification for inverse operations in Boolean logic.

In mathematics, drawings in the form of circles representing sets have been used for a very long time. One of the first to use this method was an outstanding German mathematician and philosopher (1Drawings with such circles were found in his rough sketches. Then this method was quite thoroughly developed by Leonhard Euler. He worked for many years at the St. Petersburg Academy of Sciences. This time dates back to his famous “Letters to a German Princess,” written in the period from 1761 to 1768. In some of these “Letters...” Euler talks about his method. After Euler, the same method was developed by the Czech mathematician Bernard Bolzano (1Only in Unlike Euler, he drew not circular, but rectangular diagrams. Euler’s method of circles was also used by the German mathematician Ernest Schroeder (1This method is widely used in the book “Algebra of Logic.” But graphical methods reached their greatest flowering in the works of the English logician John Venn (1C this method reached its greatest completeness). the method was outlined by him in the book “Symbolic Logic”, published in London in 1881. In honor of Venn, instead of Euler circles, the corresponding drawings are sometimes called Venn diagrams; in some books they are also called Euler-Venn diagrams (or circles).

2. Euler-Venn diagram

The concepts of set and subset are used in the definition of many concepts in mathematics and, in particular, in the definition of a geometric figure. Let us define a plane as a universal set. Then we can give the following definition of a geometric figure in planimetry:

Geometric figure any set of points on a plane is called. To visually display sets and relationships between them, draw geometric figures that are in these relationships with each other. Such images of sets are called Euler–Venn diagrams. Euler–Venn diagrams make clear various statements about sets. On them, the universal set is depicted as a rectangle, and its subsets as circles. Used in mathematics, logic, management and other applied areas.

The Euler-Venn diagram consists of a large rectangle representing the universal set U, and inside it - circles (or some other closed figures) representing sets. The shapes must intersect in the most general way required by the problem and must be labeled accordingly. Points lying inside different areas of the diagram can be considered as elements of the corresponding sets. With the diagram constructed, you can shade certain areas to indicate newly formed sets.

Basic operations on sets:

Intersection Union Difference

3.Operations on Euler-Venn diagram sets

Set operations are considered to obtain new sets from existing ones.

Now in more detail with examples.

Let a certain set of objects be given, which after recalculation could be denoted as

A = (1, 2, 4, 6) and B = (2, 3, 4, 8, 9)

round and white objects. You can call the original set fundamental, and subsets A and B are simply sets.

As a result, we get four classes of elements:

C 0 = (5, 7, 10, 11) - elements do not have any of the named properties,

C 1 = (1, 6) - elements have only property A (round),

C 2 = (3, 8, 9) - elements have only property B (white),

C 3 = (2, 4) - elements simultaneously possess two properties A and B.

In Fig. 1.1. the specified classes are depicted using Euler - Venn diagrams.

Rice. 1.1

Often diagrams do not have complete generality, for example the one shown in Fig. 1.2. On it, the set A is already completely included in B. For this case, a special inclusion symbol (Ì) is used: A Ì B = (1, 2, 4) Ì (1, 2, 3, 4, 6).

If two conditions are simultaneously satisfied: A Ì B and B Ì A, then A = B, in this case they say that the sets A and B completely equivalent.

Rice. 1.2

After the four classes of elements are defined and the necessary information about Euler-Venn diagrams is given, we introduce operations on sets. First, let's consider the operation associations.

a) Association

Association sets A = (1, 2, 4, 6) and B = (2, 3, 4, 8, 9)

let's call the set

A È B = (1, 2, 3, 4, 6, 8, 9),

where È is the symbol for the union of sets. Thus, the union covers three classes of elements - C 1, C 2 and C 3, which are shaded in the diagram (Fig. 1.3).

Logically, the operation of combining two sets can be characterized by the words: element x belongs to set A or set B. Moreover, the connective “or” simultaneously means the connective “and”. Fact of element ownership x set A is denoted as xО A. Therefore, what x belongs to A or/and B, expressed by the formula:

xÎ A È B = ( xÎ A) Ú ( xО B),

where Ú is the symbol of the logical connective or, which is called disjunction.

b) Intersection, addition

By crossing sets A and B is called a set A Ç B containing those elements from A and B that are included simultaneously in both sets. For our numerical example we will have:

A Ç B = (1, 2, 4, 6) Ç (2, 3, 4, 8, 9) = (2, 4) = C 3.

The Euler–Venn diagram for intersection is shown in Fig. 1.4.

What x belongs simultaneously to two sets A and B can be represented by the expression:

xÎ A Ç B = ( xÎ A) Ù ( xО B),

where Ù is the symbol of the logical connective “and”, which is called conjunction.

Let's imagine an operation that results in shaded areas C 1 and C 3, forming set A (Fig. 1.5). Then another operation that will cover two other areas - C 0 and C 2 not included in A, which is denoted as A(Fig. 1.6).

If we combine the shaded areas in both diagrams, we get the entire shaded set 1; the intersection of A and A will give the empty set 0, which does not contain a single element:

A È A= 1, A Ç A = 0.

A bunch of A complements set A to fundamental set V (or 1); hence the name: additional set A, or addition like an operation. Boolean Variable Complement x, i.e. x (Not- x), called most often negation of x.

After introducing the operations of intersection and addition, all four areas Ci the Euler–Venn diagram can be expressed as follows:

C 0 = A Ç B, C 1 = A Ç B, C 2 = AÇ B, C 3 = A Ç B.

By combining relevant areas Ci You can imagine any multiple operation, including the union itself:

A È B = (A Ç B) È ( AÇ B) È (A Ç B).

The Euler-Venn diagram for implication (Fig. 1.10) shows partial inclusion of set A in set B, which must be distinguished from full inclusions (Fig. 1.2).

If it is stated that "elements of set A are included in set B", then the domain C 3 must be shaded, and the area C 1 with the same necessity should be left white. Regarding areas C 0 and C 1 located in A, note that we do not have the right to leave them white, but we are still obliged to areas that fall into A, shade.

E) Symmetric difference and equivalence

It remains to give two more mutually complementary operations - symmetric difference and equivalence. The symmetric difference of two sets A and B is the union of two differences:

A + B = (A – B) È (B – A) = C 1 È C 2 = {1, 3, 6, 8, 9}.

Equivalence is determined by those elements of sets A and B that are common to them. However, elements not in either A or B are also considered equivalent:

A ~ B = ( AÇ B) È (A Ç B) = C 0 È C 3 = {2, 4, 5, 7, 10, 11}.

In Fig. Figures 1.11 and 1.12 show the shading of Euler-Venn diagrams.

In conclusion, we note that the symmetric difference has several names: strict disjunction, exclusionary alternative, sum modulo two. This operation can be expressed in words - “either A or B”, i.e. it is a logical connective “or”, but without the connective “and” included in it.

Conclusion

Euler-Venn diagrams are geometric representations of sets. Simple diagramming provides a visual representation of the universal set U, and inside it - circles (or some other closed figures) representing sets. The figures intersect in the most general case required in the problem and correspond to the figurative image. Points lying inside different areas of the diagram can be considered as elements of the corresponding sets. With the diagram constructed, you can shade certain areas to indicate newly formed sets. This allows us to have the most complete understanding of the problem and its solution. The simplicity of Euler-Venn diagrams allows this technique to be used in areas such as mathematics, logic, management and other applied areas.

Bibliography

1. Dictionary of logic. - M.: Tumanit, ed. VLADOS center. , . 1997

2. Weisstein, Eric W. “Venn Diagram” (English) on the Wolfram MathWorld website.

Story

Definition 1

Leonhard Euler was asked the question: is it possible, while walking around Königsberg, to go around all the bridges of the city without passing through any of them twice. A city plan with seven bridges is included.

In a letter to an Italian mathematician he knew, Euler gave a short and beautiful solution to the problem of the 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 are sufficient to solve it...”.

When solving many problems, L. Euler depicted sets using circles, which is why they got the name "Eulerian circles". This method was previously used by the German philosopher and mathematician Gottfried Leibniz, who used them to geometrically explain the logical connections between concepts, but more often used linear diagrams. Euler 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 diagrams are often called Euler-Venn diagrams. They are used in many fields, for example, in set theory, probability theory, logic, statistics and computer science.

Principle of diagramming

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, when $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 represent the truth of the expression $A$, and the area outside the circle will indicate 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, in 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 the sets).

Figure 1. Conjunction of the sets $A$ and $B$

Using Euler-Venn Diagrams to Prove Logical Equalities

Let's look at how the method of constructing Euler-Venn diagrams is used to prove logical equalities.

Let us prove De Morgan's law, which is described by the equality:

Proof:

Figure 4. Inversion of $A$

Figure 5. Inversion of $B$

Figure 6. Conjunction of inversions $A$ and $B$

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” in the Russian language. The meaning of logical connectives becomes clearer if they are illustrated using 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.

Solution:

Let's build an Euler-Venn diagram for each request:

Figure 8.

Answer: BVA.

Solving a logical meaningful problem using Euler-Venn diagrams

Example 2

During the winter holidays, out of $36$ students in the $2$ class were neither in the cinema, nor in the theater, nor in the circus. $25$ people went to the cinema, $11$ people went to the theater, $17$ people went to the circus; both in the cinema and in the theater - $6$; both to the cinema and to the circus - $10$; and to the theater and circus - $4$.

How many people have been to the cinema, the theater, and the circus?

Solution:

Let us denote the number of children who have been to the cinema, the theater, and the circus as $x$.

Let's build a diagram and find out the number of guys in each area:

Figure 9.

Haven't been to the theatre, cinema or circus - $2$ per person.

So, $36 - 2 = $34 people. attended events.

$6$ people went to the cinema and theater, which means only to the cinema and theater ($6 - x)$ people.

$10$ people went to the cinema and circus, which means only to the cinema and circus ($10 - x$) people.

$4$ people went to the theater and circus, which means only $4 - x$ people went to the theater and circus.

$25$ people went to the cinema, which means that $25 - (10 - x) - (6 - x) - x = (9+x)$ went to the cinema alone.

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, the cinema, and the circus.