1.2. Operations on sets. Euler Circles

Sets can be defined using operations on some other sets and subsets. Let given a certain set of objects, which can be described as a set

V = {a, b, c, d, e, f, g, h, i, j, k} .

Suppose that some of the objects, namely: a , b , d, and f are round, while some — b , c , d , h , and i — are painted white. In this case, it is said that the set V has two subsets A = { a , b , d , f } and B = { b , c , d , h , i } of round and white objects. One can say otherwise: the initial set is called fundamental or by the universe , and the subsets A and B are simply sets.

As a result, we get four classes of elements:

С 0 = { e , g , j , k } - elements that do not have any of the named properties,

С 1 = { a , f } - elements with only property A (round),

С 2 = { c , h , i } - elements possessing only property B (white),

С 3 = { b , d } are elements possessing simultaneously two properties.

It is convenient to depict operations on sets using a graphical Euler-Venn diagram (Fig. 1).

Fig. one . Euler-Venn diagram for two sets A and B

The union of the sets A = { a , b , d , f } and B = { b , c , d , h , i } let's call the set A B = { a , b , c , d , f , h , i }. Thus, the union covers three classes of elements - C 1 , C 2 , C 3 , which are shaded in the diagram (Fig. 2). Moreover, both sets may not intersect; do not have common elements. The logical operation of combining two sets can be characterized in words: the element belongs to the set A or the set B. The fact that the element x belongs to A or B can be expressed by the formula

x  A  B = ( x  A )  ( x  B ),

Where - a logical connection symbol or , which is called a disjunction .

Intersection the sets A and B are called the set K = A  B, containing those elements from A and B that are simultaneously included in both sets. For our example, we will have (Fig. 3):

The fact that the element x simultaneously belongs to two sets A and B can be expressed by the formula

Where - the symbol of the logical connective and , which is called a conjunction.

Fig. 2. A  B Fig. 3. A  B

Consider areas C 1 and C 3 , forming a set A (Fig. 4). Then the regions С 2 and С 0 form a set of elements that are not included in A (Fig. 5). This is referred to as . The union or disjunction of sets A and will give the whole universe V (A = V ) , and the intersection or conjunction will give us the zero set  ; (  A =  ) . So many complements the set A to the universe V , hence the name - an additional set or addition as an operation. The operation of addition is also called inversion.

Fig. 4. A Figure five.

After considering the inversion operation (addition), all four areas Сj on the diagram can be expressed as follows:

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

Using inversion, you can imagine any multiple operation, for example, a union:

A  B = (A )  (  B)  (A  B) .

The operations of addition or inversion of the union and intersection of sets are called, respectively, the Pierce arrow ( D = ) and the Schaeffer stroke ( K = ) , which are denoted by A ↓ B and A / B respectively . The diagrams for these operations are shown in Fig. 6 and 7.

Fig. 6. A ↓ In Fig. 7. A / B

Fig. 8. ( In ← A ) Fig. 9. (B → A)

The difference between the sets B and A is the set of those elements of the set B that are not included in the set A (Fig. 8). Such an operation is also called prohibition A and is denoted ( B ← A ). For our case, this will be the C 2 region.

At the same time ( B ← A ) =  v .

Fig. 10. ( A  B) Fig. 11. ( A  B)

An addition to the ban is the implication A. In the Euler-Venn diagram, this is a partial inclusion of the set B in the set A (Fig. 9). Denoted by such an operation (B → A) . At the same time (B → A) = A .

bc

Fig. 12. (A  B)  (A  C)

a ( A  B ) b (( A  B ) → ( C  D ))

c (( A  B ) / ( C  D )) d (( A B ) → ( C  D )) 

 (( A B ) / ( C  D ))

Fig.13. Venn diagrams for operations on four sets

The prohibition B (A ← B) = A  is determined similarly. and implication B (A → B) =  v .

It remains to cite two mutually complementary operations — a symmetric difference or an inequality and equivalence or equivalence.

Equivalence is determined by those elements of the sets A and B , which are common to them, as well as elements that are not included in either A or B. In our case, these will be the C 0 and C 3 regions (Fig. 10). Denotes the equivalence of A  B or A ~ B.

A ~ B = (  )  (A  B) .

Inequality is the union of two differences or two prohibitions. This operation is denoted ( A  B) . In this way,

( A  B) = (A ← B)  ( B ← A ), or ( A B) = (  B)  (A  ) .

In the Euler-Venn diagram, these are the C 1 and C 2 (Fig. 11). Inequality has the name strict disjunction . This operation can be expressed by the words: “either A or B ”.

Euler-Venn diagrams quite clearly illustrate operations on three and four sets. Consider the operation (A  B) (A  C) and construct the Euler-Venn diagrams for three sets. The diagram in fig. 12a depicts the operation (A  B), and fig. 12b - (A  C) . The conjunction of these relations is illustrated in the resulting diagram in Fig. 12c.

For four sets, four Euler circles do not give a complete Venn diagram, since their intersection gives only 14 regions, but 16 is necessary. Therefore, the circles must be deformed into ellipses. Let us show by example the construction of a diagram for the expression (( A  B ) → ( C  D ))  (( A B ) / ( C  D )) .

In fig. 13 depicts four diagrams corresponding to the indicated sequence of operations. The last diagram (Fig. 13d) is the resulting one.