Fundamentals of discrete mathematics.

The concept of a set. Relationship between sets.

A set is a collection of objects that have a certain property, united into a single whole.

The objects that make up a set are called elements sets. In order for a certain set of objects to be called a set, the following conditions must be met:

· There should be a rule by which it is mono to determine whether an element belongs to a given collection.

· There must be a rule by which elements can be distinguished from each other.

Sets are denoted by capital letters, and its elements by small letters. Ways to specify sets:

· Enumeration of set elements. - for finite sets.

Specifying a characteristic property .

empty set- is called a set that does not contain any element (Ø).

Two sets are said to be equal if they consist of the same elements. , A=B

A bunch of B called a subset of the set A( , if and only if all elements of the set B belong to the set A.

For example: , B =>

Property:

Note: usually consider a subset of the same set, which is called universal(u). The universal set contains all elements.

Operations on sets.

A

B

1. Association 2 sets A and B is called such a set to which the elements of set A or set B belong (elements of at least one of the sets).

2.crossing 2 sets is a new set consisting of elements that simultaneously belong to both the first and second sets.

Nr: , ,

Property: union and intersection operations.

· Commutativity.

Associativity. ;

· Distributive. ;

U

4.Addition. If A is a subset of the universal set U, then the complement of the set A to many U(denoted) is the set consisting of those elements of the set U, which do not belong to the set A.

Binary relations and their properties.

Let A And IN these are sets of derived nature, consider an ordered pair of elements (a, c) a ϵ A, c ϵ B ordered "enks" can be considered.

(a 1, a 2, a 3,…a n), Where A 1 ϵ A 1; A 2 ϵ A 2; …; A n ϵ A n ;

Cartesian (direct) product of sets A 1, A 2, ..., A n, is called a set, which consists of ordered n k of the form .

Nr: M= {1,2,3}

M× M= M 2= {(1,1);(1,2);(1,3); (2,1);(2,2);(2,3); (3,1);(3,2);(3,3)}.

Subsets of the Cartesian product called the degree ratio n or enary relation. If n=2, then consider binary relationship. What do they say that a 1 , a 2 are in binary relation R, When a 1 R a 2.

Binary relation on a set M is called a subset of the direct product of the set n on himself.

M× M= M 2= {(a, b)| a, b ϵ M) in the previous example, the ratio is smaller on the set M generates the following set: ((1,2);(1,3); (2,3))

Binary relations have various properties including:

Reflexivity: .

· Anti-reflexivity (irreflexivity): .

· Symmetry: .

· Antisymmetry: .

· Transitivity: .

· Asymmetry: .

Types of relationships.

Equivalence relation;

· Order relation.

v A reflexive transitive relation is called a quasi-order relation.

v A reflexive symmetric transitive relation is called an equivalence relation.

v A reflexive antisymmetric transitive relation is called a (partial) order relation.

v An antireflexive antisymmetric transitive relation is called a strict order relation.

Definition. Binary relation R is called a subset of pairs (a,b)∈R the Cartesian product A×B, i.e. R⊆A×B . At the same time, many A is called the domain of definition of the relation R, the set B is called the domain of values.

Notation: aRb (i.e. a and b are in relation to R). /

Comment: if A = B , then R is said to be a relation on the set A .

Ways to specify binary relations

1. List (enumeration of pairs) for which this relationship is satisfied.

2. Matrix. The binary relation R ∈ A × A , where A = (a 1 , a 2 ,..., a n), corresponds to a square matrix of order n , in which the element c ij , which is at the intersection of the i-th row and the j-th column, is equal to 1 if there is a relation R between a i and a j , or 0 if it is absent:

Relationship Properties

Let R be a relation on a set A, R ∈ A×A . Then the relation R:

reflexively if Ɐ a ∈ A: a R a (the main diagonal of the matrix of the reflexive relation contains only ones);

is antireflexive if Ɐ a ∈ A: a R a (the main diagonal of the reflexive relation matrix contains only zeros);

symmetric if Ɐ a , b ∈ A: a R b ⇒ b R a (the matrix of such a relation is symmetric with respect to the main diagonal, i.e. c ij c ji);

antisymmetric if Ɐ a, b ∈ A: a R b & b R a ⇒ a = b (in the matrix of such a relation, there are no ones symmetric with respect to the main diagonal);

transitively if Ɐ a, b, c ∈ A: a R b & b R c ⇒ a R c row, i.e. c ij = 1 , then all ones in the j-th row (let these units correspond to k e coordinates such that, c jk = 1) must correspond to ones in the i-th row in the same k coordinates, i.e. c ik = 1 (and, perhaps, also in other coordinates).

Task 3.1. Determine the properties of the relation R - "to be a divisor", given on the set of natural numbers.

Solution.

ratio R = ((a,b):a divisor b):

reflexive, not antireflexive, since any number divides itself without remainder: a/a = 1 for all a∈N ;

not symmetrical, antisymmetric, for example, 2 is a divisor of 4, but 4 is not a divisor of 2;

transitively, since if b/a ∈ N and c/b ∈ N, then c/a = b/a ⋅ c/b ∈ N, for example, if 6/3 = 2∈N and 18/6 = 3∈N, then 18/3 = 18/6⋅6/3 = 6∈N.

Task 3.2. Determine the properties of the relation R - "to be a brother", given on a set of people.
Solution.

Ratio R = ((a,b):a - brother of b):

non-reflexive, anti-reflexive due to the obvious absence of aRa for all a;

not symmetrical, since in general there is aRb between brother a and sister b, but not bRa ;

not antisymmetric, since if a and b are brothers, then aRb and bRa, but a≠b;

transitively, if we call brothers people who have common parents (father and mother).

Task 3.3. Determine the properties of the relation R - "to be the boss" specified on the set of structure elements

Solution.

Ratio R = ((a,b) : a - boss b):

• non-reflexive, anti-reflexive, if it does not make sense in a particular interpretation;
• not symmetric, antisymmetric, since for all a≠b aRb and bRa are not satisfied simultaneously;
• transitively, since if a is the head of b and b is the head of c , then a is the head of c .

Determine the properties of the relation R i , defined on the set M i by a matrix, if:

1. R 1 "have the same remainder when divided by 5"; M 1 is the set of natural numbers.
2. R 2 "be equal"; M 2 is the set of natural numbers.
3. R 3 "live in the same city"; M 3 set of people.
4. R 4 "be familiar"; M 4 many people.
5. R 5 ((a,b):(a-b) - even; M 5 set of numbers (1,2,3,4,5,6,7,8,9).
6. R 6 ((a,b):(a+b) - even; M 6 set of numbers (1,2,3,4,5,6,7,8,9).
7. R 7 ((a,b):(a+1) - divisor (a+b)) ; M 7 - set (1,2,3,4,5,6,7,8,9).
8. R 8 ((a,b):a - divisor (a+b),a≠1); M 8 is the set of natural numbers.
9. R 9 "to be a sister"; M 9 - a lot of people.
10. R 10 "to be a daughter"; M 10 - a lot of people.

Operations on binary relations

Let R 1 , R 1 be relations defined on the set A .

Union R 1 ∪ R 2: R 1 ∪ R 2 = ((a,b) : (a,b) ∈ R 1 or (a,b) ∈ R 2 ) ;

intersection R 1 ∩ R 2: R 1 ∩ R 2 = ((a,b) : (a,b) ∈ R 1 and (a,b) ∈ R 2 ) ;

difference R 1 \ R 2: R 1 \ R 2 = ((a,b) : (a,b) ∈ R 1 and (a,b) ∉ R 2 ) ;

universal relation U: = ((a;b)/a ∈ A & b ∈ A). ;

addition R 1 U \ R 1 , where U = A × A;

identity relation I: = ((a;a) / a ∈ A);

reverse relation R-1 1 :R-1 1 = ((a,b) : (b,a) ∈ R 1 );

composition R 1 º R 2: R 1 º R 2: = ((a,b) / a ∈ A&b ∈ B& ∃ c ∈ C: aR 1 c & c R 2 b), where R 1 ⊂ A × C and R 2 ⊂ C×B;

Definition. Degree of relationship R on a set A is its composition with itself.

Designation:

Definition. If R ⊂ A × B, then R º R -1 is called the kernel of the relation R .

Theorem 3.1. Let R ⊂ A × A be a relation defined on a set A .

1. R is reflexive if and only if (hereinafter the ⇔ sign is used) when I ⊂ R.
2. R is symmetrical ⇔ R = R -1 .
3. R is transitive ⇔ R º R ⊂ R
4. R is antisymmetric ⇔ R ⌒ R -1 ⊂ I .
5. R is antireflexive ⇔ R ⌒ I = ∅ .

Task 3.4 . Let R be the relation between the sets (1,2,3) and (1,2,3,4) given by the enumeration of pairs: R = ((1,1), (2,3), (2,4), ( 3.1), (3.4)). In addition, S is a relation between the sets S = ((1,1), (1,2), (2,1), (3,1), (4,2)). Calculate R -1 , S -1 and S º R. Check that (S º R) -1 = R -1 , S -1 .

Solution.
R -1 = ((1.1), (1.3), (3.2), (4.2), (4.3));
S -1 = ((1.1), (1.2), (1.3), (2.1), (2.4));
S º R = ((1,1), (1,2), (2,1), (2,2), (3,1), (3,2));
(S º R) -1 = ((1,1), (1,2), (1,3), (2,1), (2,2), (2,3));
R -1 º S -1 = ((1.1), (1.2), (1.3), (2 .1), (2.2), (2.3)) = (S º R ) -1 .

Task 3.5 . Let R be the relation "...parent..." and S the relation "...brother..." on the set of all people. Give a brief verbal description of the relationship:

R -1 , S -1 , R º S, S -1 º R -1 and R º R.

Solution.

R -1 - relation "... child ...";

S -1 - relation "... brother or sister ...";

R º S - relation "... parent ...";

S -1 º R -1 - relation "... child ..."

R º R - relation "...grandmother or grandfather..."

Tasks for independent solution

1) Let R be the relation "...father...", and S be the relation "...sister..." on the set of all people. Give a verbal description of the relationship:

R -1 , S -1 , R º S, S -1 º R -1 , R º R.

2) Let R be the relation "...brother...", and S be the relation "...mother..." on the set of all people. Give a verbal description of the relationship:

R -1 , S -1 , S º R, R -1 º S -1 , S º S.

3) Let R be the relation "...grandfather...", and S be the relation "...son..." on the set of all people. Give a verbal description of the relationship:

4) Let R be the relation “...daughter...”, and S be the relation “...grandmother...” on the set of all people. Give a verbal description of the relationship:

5) Let R be the relation "...niece...", and S be the relation "...father..." on the set of all people. Give a verbal description of the relationship:

R -1 , S -1 , S º R, R -1 º S -1 , R º R.

6) Let R be the relation "sister..." and S be the relation "mother..." on the set of all people. Give a verbal description of the relationship:

R -1 , S -1 , R º S, S -1 º R -1 , S º S.

7) Let R be the relation “...mother...”, and S be the relation “...sister...” on the set of all people. Give a verbal description of the relationship:

R -1 , S1, R º S, S1 º R1, S º S.

8) Let R be the relation “...son...”, and S be the relation “...grandfather...” on the set of all people. Give a verbal description of the relationship:

R -1 , S -1 , S º R, R -1 º S -1 , R º R.

9) Let R be the relation “...sister...”, and S be the relation “...father...” on the set of all people. Give a verbal description of the relationship:

R -1 , S -1 , R º S, S -1 º R -1 , S º S.

10) Let R be the relation “...mother...”, and S be the relation “...brother...” on the set of all people. Give a verbal description of the relationship:

R -1 , S -1 , S º R, R -1 º S -1 , R º R.

Definitions

• 1. A binary relation between elements of sets A and B is any subset of the Cartesian product RAB, RAA.
• 2. If A=B, then R is a binary relation on A.
• 3. Notation: (x, y)R xRy.
• 4. The domain of the binary relation R is the set R = (x: there is y such that (x, y)R).
• 5. The range of the binary relation R is the set R = (y: there is x such that (x, y)R).
• 6. The complement of a binary relation R between elements A and B is the set R = (AB) R.
• 7. The inverse relation for the binary relation R is the set R1 = ((y, x) : (x, y)R).
• 8. The product of the relations R1AB and R2BC is the relation R1 R2 = ((x, y) : there exists zB such that (x, z)R1 and (z, y)R2).
• 9. The relation f is called a function from A to B if two conditions are met:
  • a) f \u003d A, f B
  • b) for all x, y1, y2, the fact that (x, y1)f and (x, y2)f implies y1=y2.
• 10. The relation f is called a function from A to B if in the first paragraph f = A, f = B.
• 11. Notation: (x, y)f y = f(x).
• 12. The identity function iA: AA is defined as follows: iA(x) = x.
• 13. A function f is called a 1-1-function if for any x1, x2, y the fact that y = f(x1) and y = f(x2) implies x1=x2.
• 14. The function f: AB performs a one-to-one correspondence between A and B if f = A, f = B and f is a 1-1 function.
• 15. Properties of the binary relation R on the set A:
  • - reflexivity: (x, x)R for all xA.
  • - irreflexivity: (x, x)R for all xA.
  • - symmetry: (x, y)R (y, x)R.
  • - antisymmetry: (x, y)R and (y, x)R x=y.
  • - transitivity: (x, y)R and (y, z)R (x, z)R.
  • - dichotomy: either (x, y)R or (y, x)R for all xA and yA.
• 16. The sets A1, A2, ..., Ar from P(A) form a partition of the set A if
• - Аi , i = 1, ..., r,
• - A = A1A2...Ar,
• - AiAj = , i j.

Subsets Аi , i = 1, ..., r, are called partition blocks.

• 17. Equivalence on a set A is a reflexive, transitive, and symmetric relation on A.
• 18. The equivalence class of an element x by equivalence R is the set [x]R=(y: (x, y)R).
• 19. The factor set A by R is the set of equivalence classes of elements of the set A. Designation: A/R.
• 20. Equivalence classes (elements of the factor set A/R) form a partition of the set A. Conversely. Any partition of the set A corresponds to an equivalence relation R whose equivalence classes coincide with the blocks of the specified partition. Differently. Each element of the set A falls into some equivalence class from A/R. The equivalence classes either do not intersect or coincide.
• 21. A preorder on a set A is a reflexive and transitive relation on A.
• 22. A partial order on a set A is a reflexive, transitive, and antisymmetric relation on A.
• 23. Linear order on the set A is a reflexive, transitive, and antisymmetric relation on A that satisfies the dichotomy property.

Let A=(1, 2, 3), B=(a, b). Let's write out the Cartesian product: AB = ( (1, a), (1, b), (2, a), (2, b), (3, a), (3, b) ). Take any subset of this Cartesian product: R = ( (1, a), (1, b), (2, b) ). Then R is a binary relation on the sets A and B.

Will this relation be a function? Let us check the fulfillment of two conditions 9a) and 9b). The domain of the relation R is the set R = (1, 2) (1, 2, 3), that is, the first condition is not satisfied, so one of the pairs must be added to R: (3, a) or (3, b). If both pairs are added, then the second condition will not be satisfied, since ab. For the same reason, one of the pairs (1, a) or (1, b) must be dropped from R. Thus the relation R = ( (1, a), (2, b), (3, b) ) is a function. Note that R is not a 1-1 function.

On the given sets A and B, the following relations will also be functions: ( (1, a), (2, a), (3, a) ), ( (1, a), (2, a), (3, b ) ), ( (1, b), (2, b), (3, b) ) etc.

Let A=(1, 2, 3). An example of a relation on a set A is R = ( (1, 1), (2, 1), (2, 3) ). An example of a function on the set A is f = ( (1, 1), (2, 1), (3, 3) ).

Examples of problem solving

1. Find R, R, R1, RR, RR1, R1R for R = ((x, y) | x, y D and x+y0).

If (x, y)R, then x and y run through all real numbers. Therefore R = R = D.

If (x, y)R, then x+y0, so y+x0 and (y, x)R. Therefore R1=R.

For any xD, yD we take z=-|max(x, y)|-1, then x+z0 and z+y0, i.e. (x, z)R and (z, y)R. Therefore RR = RR1 = R1R = D2.

2. For which binary relations R is R1= R true?

Let RAB. Two cases are possible:

• (1) AB. Let's take xAB. Then (x, x)R (x, x)R1 (x, x)R (x, x)(AB) R (x, x)R. Contradiction.
• (2) AB=. Since R1BA and RAB, then R1= R= . From R1 = it follows that R = . From R = it follows that R=AB. Contradiction.

Therefore, if A and B, then such relations R do not exist.

3. On the set D of real numbers, we define the relation R as follows: (x, y)R (x-y) is a rational number. Prove that R is an equivalence.

Reflexivity:

For any xD x-x=0 is a rational number. Because (x, x)R.

Symmetry:

If (x, y)R, then x-y = . Then y-x=-(x-y)=- is a rational number. Therefore (y, x)R.

Transitivity:

If (x, y)R, (y, z)R, then x-y = and y-z =. Adding these two equations, we get that x-z = + is a rational number. Therefore (x, z)R.

Hence R is an equivalence.

4. The partition of the plane D2 consists of the blocks shown in figure a). Write down the equivalence relation R corresponding to this partition and the equivalence classes.

Similar problem for b) and c).

a) two points are equivalent if they lie on a straight line of the form y=2x+b, where b is any real number.

b) two points (x1,y1) and (x2,y2) are equivalent if (the integer part of x1 is equal to the integer part of x2) and (the integer part of y1 is equal to the integer part of y2).

c) Decide for yourself.

Tasks for independent solution

• 1. Prove that if f is a function from A to B and g is a function from B to C, then fg is a function from A to C.
• 2. Let A and B be finite sets consisting of m and n elements, respectively.

How many binary relations exist between elements of sets A and B?

How many functions are there from A to B?

How many 1-1 functions are there from A to B?

For what m and n is there a one-to-one correspondence between A and B?

3. Prove that f satisfies the condition f(AB)=f(A)f(B) for any A and B if and only if f is a 1-1 function.

A relation defined on a set can have a number of properties, namely:

2. Reflexivity

Definition. Attitude R on the set X is called reflexive if each element X sets X is in relation R With myself.

Using symbols, this relationship can be written as follows:

R reflectively on X Û(" XÎ X) x R x

Example. The relation of equality on the set of segments is reflexive, since each segment is equal to itself.

The reflexive relation graph has loops at all vertices.

2. Antireflexivity

Definition. Attitude R on the set X is called anti-reflexive if no element X sets X not in relation R With myself.

R antireflexively on X Û(" XÎ X)

Example. The relationship "direct X perpendicular to the line at» on the set of lines in the plane is antireflexive, because no straight line of a plane is perpendicular to itself.

The graph of an antireflexive relation does not contain any loops.

Note that there are relations that are neither reflexive nor antireflexive. For example, consider the relation "point X symmetrical to a point at» on the set of points of the plane.

Dot X symmetrical to a point X- true; dot at symmetrical to a point at- is false, therefore, we cannot assert that all points of the plane are symmetrical to themselves, nor can we assert that no point of the plane is symmetrical to itself.

3. Symmetry

Definition. Attitude R on the set X is called symmetric if, from the fact that the element X is in relation R with element at, it follows that the element at is in relation R with element X.

R symmetrical X Û(" X, atÎ X) x R y Þ y R x

Example. The relationship "direct X crosses the line at on the set of straight lines of the plane” is symmetrical, because if straight X crosses the line at, then the straight line at must cross the line X.

Symmetric relation graph along with each arrow from a point X exactly at should contain an arrow connecting the same points, but in the opposite direction.

4. Asymmetry

Definition. Attitude R on the set X is called asymmetric if for no elements X, at from many X it cannot happen that the element X is in relation R with element at and element at is in relation R with element X.

R asymmetric X Û(" X, atÎ X) x R y Þ

Example. Attitude " X < at» asymmetrically, because for any pair of elements X, at cannot be said to be at the same time X < at And at<X.

A graph of an asymmetric relation has no loops, and if two vertices of the graph are connected by an arrow, then this arrow is only one.

5. Antisymmetry

Definition. Attitude R on the set X is called antisymmetric if, from the fact that X is in relationship with at, A at is in relationship with X follows that X = y.

R antisymmetric X Û(" X, atÎ X) x R y Ù y R xÞ x = y

Example. Attitude " X£ at» is antisymmetric, because conditions X£ at And at£ X are executed at the same time only when X = y.

The graph of an antisymmetric relation has loops, and if two vertices of the graph are connected by an arrow, then this arrow is only one.

6. Transitivity

Definition. Attitude R on the set X is called transitive if for any elements X, at, z from many X from what X is in relationship with at, A at is in relationship with z follows that X is in relationship with z.

R transitive X Û(" X, at, zÎ X) x R y Ù at RzÞ x Rz

Example. Attitude " X multiple at» is transitive, because if the first number is a multiple of the second, and the second is a multiple of the third, then the first number is a multiple of the third.

Graph of a transitive relation with each pair of arrows from X To at and from at To z contains an arrow going from X To z.

7. Connectivity

Definition. Attitude R on the set X is called connected if for any elements X, at from many x x is in relationship with at or at is in relationship with X or x = y.

R connected X Û(" X, at, zÎ X) x R y Ú at RzÚ X= at

In other words: relationship R on the set X is called connected if for any distinct elements X, at from many x x is in relationship with at or at is in relationship with X or x = y.

Example. Attitude " X< at» is connected, because no matter what real numbers we take, one of them is sure to be greater than the other or they are equal.

On a relation graph, all vertices are connected by arrows.

Example. Check what properties

attitude " X - divider at» defined on the set

X= {2; 3; 4; 6; 8}.

1) this relation is reflexive, since each number from the given set is a divisor of itself;

2) this relation does not have the property of antireflexivity;

3) the symmetry property is not satisfied, because for example, 2 is a divisor of 4, but 4 is not a divisor of 2;

4) this relation is antisymmetric: two numbers can simultaneously be divisors of each other only if these numbers are equal;

5) the relation is transitive, since if one number is a divisor of the second, and the second is a divisor of the third, then the first number will necessarily be a divisor of the third;

6) the relation does not have the property of connectivity, since for example, the numbers 2 and 3 on the graph are not connected by an arrow, because two distinct numbers 2 and 3 are not divisors of each other.

Thus, this relation has the properties of reflexivity, asymmetry and transitivity.

§ 3. Equivalence relation.
Connection of the equivalence relation with the division of a set into classes

Definition. Attitude R on the set X is called an equivalence relation if it is reflexive, symmetric, and transitive.

Example. Consider the relationship " X classmate at» on a set of students of the pedagogical faculty. It has properties:

1) reflexivity, since each student is a classmate to himself;

2) symmetry, because if student X at, then the student at is a classmate of a student X;

3) transitivity, because if student X- classmate at, and the student at- classmate z, then the student X be a classmate of a student z.

Thus, this relation has the properties of reflexivity, symmetry and transitivity, and therefore is an equivalence relation. At the same time, the set of students of the pedagogical faculty can be divided into subsets consisting of students enrolled in the same course. We get 5 subsets.

The equivalence relation is also, for example, the relation of parallel lines, the relation of equality of figures. Each such relation is connected with the division of the set into classes.

Theorem. If on the set X given an equivalence relation, then it splits this set into pairwise disjoint subsets (equivalence classes).

The converse statement is also true: if any relation defined on the set X, generates a partition of this set into classes, then it is an equivalence relation.

Example. On the set X= (1; 2; 3; 4; 5; 6; 7; 8) the relation "have the same remainder when divided by 3" is given. Is it an equivalence relation?

Let's build a graph of this relationship:

This relation has the properties of reflexivity, symmetry and transitivity, therefore, it is an equivalence relation and splits the set X into equivalence classes. Each equivalence class will have numbers that, when divided by 3, give the same remainder: X 1 = {3; 6}, X 2 = {1; 4; 7}, X 3 = {2; 5; 8}.

It is believed that the equivalence class is determined by any of its representatives, i.e. arbitrary element of this class. So, the class of equal fractions can be specified by specifying any fraction belonging to this class.

In the initial course of mathematics, equivalence relations also occur, for example, "expressions X And at have the same numerical values", "figure X equal to figure at».

Let some non-empty set A be given and R be some subset of the Cartesian square of set A: R  A  A.

attitude R on the set A called a subset of a set A A(or A 2 ). Thus attitude there is a special case of matching where the arrival area is the same as the departure area. Just like a match, a relation is an ordered pair where both elements belong to the same set.

R  A  A = ((a, b) | aA, bA, (a, b)R).

The fact that ( a, b)R can be written as follows: a R b. It reads: " A is in relation R to b" or "between A And b relation R holds. Otherwise write: a, b)R or aR b.

An example of relations on a set of numbers are the following: "=", "", "", ">", etc. On the set of employees of any company, the attitude “to be a boss” or “to be a subordinate”, on a set of relatives – “to be an ancestor”, “to be a brother”, “to be a father”, etc.

The considered relations are called binary (two-place) homogeneous relations and are the most important in mathematics. Along with them, they also consider P-local or P-ary relations:

R  A  A … A = A n = ((a 1 , a 2 ,…a n) | a 1 , a 2 ,…a n  A).

Since the relationship is a special case of correspondence, all previously described methods can be used to set them.

Obviously, by setting the ratio in a matrix way, we get a square matrix.

With a geometric (graphic) representation of the relationship, we get a diagram that includes:

vertices, denoted by dots or circles, which correspond to the elements of the set,

and arcs (lines) corresponding to pairs of elements included in binary relations, denoted by lines with arrows directed from the vertex corresponding to the element a to the top corresponding to the element b , If a Rb .

Such a figure is called a directed graph (or digraph) of a binary relation.

Task 4.9.1 . Ratio "to be a divisor on the set M = (1, 2, 3, 4)" can be given matrix:

enumeration: R = ((1.1), (1.2), (1.3), (1.4), (2.2), (2.4), (3.3), ((4.4 ));

geometrically (graphically):

1. Write out the ordered pairs belonging to the following binary relations on the set A = (1, 2, 3, 4, 5, 6, 7):

R1 = ((x, y)| x, yA; x + y = 9);

R2 = ((x, y)| x, yA; x< y}.

2. The relation R on the set X = (a, b, c, d) is given by the matrix

,

in which the order of rows and columns corresponds to the order of the written out elements. List the ordered pairs that belong to the given relation. Show the relationship using a graph.

3. The relation on the set A = (1, 2, 3, 4) is represented by a graph. Necessary:

list the ordered pairs that belong to R;

write out the corresponding matrix;

define this relationship using predicates.

(answer: a-b= 1).

4.10. Basic types (properties) of binary relations

Let the binary relation R on the set A 2 : R  A  A = (( a, b) | aA, bA, ( a, b)R)

binary relation R on the set A called reflective, if for any aA performed aRa, that is ( A,A)R. The main diagonal of the reflexive relation matrix consists of ones. A reflexive relation graph necessarily has loops at every vertex.

Examples reflexive relations: , =,  on the set of real numbers, “not to be the boss” on the set of employees.

binary relation R on the set A is called anti-reflexive (irreflexive), if for any aA does not hold the relation aRa, that is ( A,A)R. The main diagonal of the irreflexive relation matrix consists of zeros. The graph of an irreflexive relation has no loops.

Examples anti-reflexive relations:<, >on the set of real numbers, perpendicularity of lines on the set of lines.

binary relation R on the set A called symmetrical, if for any a, bA from aRb should bRa, that is, if ( a, b)R, then and ( b, a)R. The symmetric ratio matrix is ​​symmetric about its main diagonal ( σ ij = σ ji). The graph of a symmetric relation is not directed (edges are shown without arrows). Each pair of vertices here is connected by an undirected edge.

Examples symmetric relations:  on the set of real numbers, "to be a relative" on the set of people.

binary relation R on the set A called:

antisymmetrical, if for any a, bA from aRb And bRa follows that a=b. That is, if ( a, b)R And( b, a)R, then it follows that a=b. The antisymmetric ratio matrix along the main diagonal has all 1's and no pair of 1's located at symmetrical locations with respect to the main diagonal. In other words, everything σ ii=1, and if σ ij=1, then necessarily σ ji=0. An antisymmetric relation graph has loops at each vertex, and the vertices are connected by only one directed arc.

Examples antisymmetric relations: , ,  on the set of real numbers; ,  on sets;

Asymmetrical, if for any a, bA from aRb followed by failure bRa, that is, if ( a, b)R, That ( b, a) R. The skew ratio matrix along the main diagonal has zeros ( σ ij=0) all and no symmetrical pairs of ones (if σ ij=1, then necessarily σ ji=0). A graph of an asymmetric relation has no loops, and the vertices are connected by a single directed arc.

Examples of asymmetric relationships:<, >on the set of real numbers, "to be a father" on the set of people.

binary relation R on the set A called transitivenym, if for any a, b, WithA from aRb And bRa it follows that and aRWith. That is, if ( a, b)R And( b, With)R it follows that ( A, With)R. The transitive relation matrix is ​​characterized by the fact that if σ ij=1 and σ jm=1, then necessarily σ im=1. The transitive relation graph is such that if, for example, the first-second and second-third vertices are connected by arcs, then there are necessarily arcs from the first to the third vertex.

Examples transitive relations:<, , =, >,  on the set of real numbers; "to be the boss" on a set of employees.

binary relation R on the set A called antitransitivenym, if for any a, b, WithA from aRb And bRa it follows that it is not fulfilled aRWith. That is, if ( a, b)R And( b, With)R it follows that ( A, With) R. The antitransitive relation matrix is ​​characterized by the fact that if σ ij=1 and σ jm=1, then necessarily σ im=0. The graph of the antitransitive relation is such that if, for example, the first-second and second-third vertices are connected by arcs, then there is necessarily no arc from the first to the third vertex.

Examples of antitransitive relations: "parity mismatch" on the set of integers; "to be the immediate supervisor" on a set of employees.

If the relation does not have some property, then by adding the missing pairs, you can get a new relation with this property. The set of such missing pairs is called closure relationship for this property. Designate it as R* . This way you can get a reflexive, symmetric and transitive closure.

Problem 4.10.1. On the set A = (1, 2, 3, 4) the relation R=(( a,b)| a,bA, a+b an even number). Determine the type of this relationship.

Solution. The matrix of this relation is:

. Obviously the relationship is reflective, since there are units along the main diagonal. It symmetrically: σ 13 = σ 31 , σ 24 = σ 42 . transitively: (1,3)R, (3,1)R and (1,1)R; (2,4)R, (4,2)R and (2,2)R etc.

Problem 4.10.2. What properties on the set A = ( a, b, c, d) has the binary relation R = (( a,b), (b,d), (a,d), (b,a), (b,c)}?

Solution . Let's construct a matrix of this relation and its graph:

Attitude irreflexively, since all σ ii= 0. It Not symmetrically, since σ 23 =1, and σ 32 =0, however, σ 12 =σ 21 =1. Attitude Not transitively, because σ 12 =1, σ 23 =1 and σ 13 =0; σ 12 =1, σ 21 =1 and σ 11 =0; but at the same time σ 12 =1, σ 24 =1 and σ 14 =1.

Task 4.10.3. On the set A = (1,2,3,4,5) the relation R = ((1,2), (2,3), (2,4), (4,5)) is given. Determine the type of relation and find the following closures for R:

reflective;

symmetrical;

transitive.

Solution. The relation is irreflexive because there is no element of the form ( A,A). Asymmetric, since it does not contain pairs of the form ( a,b) And ( b,a) and all diagonal elements are 0. Antitransitive since (1,2)R, (2,3)R, but (1,3)R. Similarly (2.4)R, (4.5)R, and (2.5)R etc.

reflexive closure of the given relation R * =((1,1), (2,2), (3,3), (4,4), (5,5));

symmetrical closure: R*=((2,1), (3,2), (4,2), (5,4));

transitive closure: R*=((1,3), (1,4), (2,5)). Consider the graph of the original relation and the resulting transitive one.

Tasks for independent solution.

1. The relation R = ((1,1), (1,2), (1,3), (3,1), (2,3)) is given. Determine its type and find closures by reflexivity, symmetry, and transitivity.

2. The relation on the set of words of the Russian language is defined as follows: A R b if and only if they have at least one common letter. Determine the type of relation on the set A = (cow, wagon, thread, ax).

3. Indicate examples of binary relations on the set A = (1, 2) and B = (1, 2, 3), which would be:

not reflexive, not symmetrical, not transitive;

reflexive, not symmetrical, not transitive;

symmetrical, but not reflexive and not transitive;

transitive, but not reflexive and not symmetrical;

reflexive, symmetrical but not transitive;

reflexive, transitive, but not symmetrical;

non-reflexive, symmetrical, transitive;

reflexive, symmetrical, transitive.