Основи на дискретната математика.

Концепцията за набор. Връзка между множества.

Наборът е съвкупност от обекти, които имат определено свойство, обединени в едно цяло.

Обектите, които съставляват едно множество, се наричат елементимножества. За да може определена колекция от обекти да се нарече набор, трябва да бъдат изпълнени следните условия:

· Трябва да има правило, по което може да се определи дали даден елемент принадлежи към дадена популация.

· Трябва да има правило, по което елементите да се различават един от друг.

Множествата се означават с главни букви, а елементите им с малки букви. Методи за определяне на комплекти:

· Изброяване на елементите на множество. - за крайни множества.

· Индикация за характерно свойство .

Празен комплект– извиква се множество, което не съдържа нито един елемент (Ø).

Две множества се наричат ​​равни, ако се състоят от едни и същи елементи. , А=Б

Няколко бнаречено подмножество на множеството А( , ако и само ако всички елементи на множеството бпринадлежат на много А.

Например: , б =>

Имот:

Забележка: обикновено се разглежда подмножество от същото множество, което се нарича универсален(u). Универсалният комплект съдържа всички елементи.

Операции върху множества.

А

б

1. Асоциация 2 множества A и B е множество, което съдържа елементи от множество A или множество B (елементи на поне едно от множествата).

2.Чрез пресичане 2 набора е ново множество, състоящо се от елементи, които едновременно принадлежат към първото и второто множество.

Не.: , ,

Свойство: операции на обединение и пресичане.

· Комутативност.

· Асоциативност. ;

· Разпределителен. ;

U

4.Допълнение. Ако А– подмножество на универсалното множество U, след това допълнението на комплекта Аза мнозина U(означено с ) е множество, състоящо се от тези елементи на множеството U, които не принадлежат към множеството А.

Бинарни отношения и техните свойства.

Позволявам АИ INтова са набори от производна природа, помислете за подредена двойка елементи (a, b) a ϵ A, c ϵ Bможе да се счита за подредени "енки".

(a 1, a 2, a 3,...a n), Където А 1 ϵ A 1; А 2 ϵ A 2; ...; Ан ϵ А n;

Декартово (пряко) произведение на множества A 1, A 2, …, A n, се нарича множество, което се състои от подредени n k от вида .

Не.: М= {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)}.

Подмножества на декартовия продукт наречен коефициент на мощност нили енарна връзка. Ако н=2, тогава помислете двоиченвръзка. Какво казват това 1, 2са в двоично отношение Р, Кога a 1 R a 2.

Бинарна релация върху множество Ме подмножество на прекия продукт на множеството нвърху себе си.

M × M = M 2= {(а, б)| a, b ϵ M) в предишния пример отношението е по-малко в множеството Мгенерира следния набор: ((1,2);(1,3); (2,3))

Бинарните отношения имат различни свойства, включително:

Рефлексивност: .

· Антирефлексивност (иррефлексивност): .

· Симетрия: .

· Антисиметрия: .

· Преходност: .

· Асиметрия: .

Видове взаимоотношения.

· Отношение на еквивалентност;

· Отношение на поръчката.

v Рефлексивна транзитивна релация се нарича квази-редова релация.

v Рефлексивно симетрично транзитивно отношение се нарича отношение на еквивалентност.

v Рефлексивно антисиметрично транзитивно отношение се нарича (частично) отношение на ред.

v Антирефлексивна антисиметрична транзитивна релация се нарича стриктна релация на ред.

Определение. Бинарна връзка Rнаречено подмножество от двойки (a,b)∈RДекартово произведение A×B, т.е. R⊆A×B. В същото време мн Асе нарича област на дефиниране на отношението R, множеството B се нарича област на стойности.

Обозначение: aRb (т.е. a и b са във връзка с R). /

Коментирайте: ако A = B, тогава R се казва, че е релация в множеството A.

Методи за специфициране на бинарни отношения

1. Списък (изброяване на двойки), за които тази връзка е валидна.

2. Матрица. Бинарното отношение R ∈ A × A, където A = (a 1, a 2,..., a n), съответства на квадратна матрица от ред n, в която елементът c ij, разположен в пресечната точка на i- ред и j-та колона, е равно на 1, ако има връзка R между a i и a j, или 0, ако липсва:

Свойства на отношенията

Нека R е релация върху множество A, R ∈ A×A. Тогава съотношението R:

рефлексивен, ако Ɐ a ∈ A: a R a (главният диагонал на матрицата на рефлексивните отношения съдържа само единици);

антирефлексивно, ако Ɐ a ∈ A: a R a (главният диагонал на матрицата на рефлексивните отношения съдържа само нули);

симетрична, ако Ɐ a , b ∈ A: a R b ⇒ b R a (матрицата на такава връзка е симетрична по отношение на главния диагонал, т.е. c ij c ji);

антисиметрична, ако Ɐ a, b ∈ A: a R b & b R a ⇒ a = b (в матрицата на такава връзка няма единици, симетрични спрямо главния диагонал);

транзитивно ако Ɐ a, b, c ∈ A: a R b & b R c ⇒ a R c (в матрицата на такава връзка трябва да е изпълнено условието: ако има единица в i-тия ред, напр. , в j-тата координатна (колона) редове, т.е. c ij = 1, тогава всички единици в j-тия ред (нека тези единици съответстват на k e координати, така че c jk = 1) трябва да съответстват на единици в i- ред в същите k координати, т.е. c ik = 1 (а може би и в други координати).

Задача 3.1.Определете свойствата на релацията R – „да бъде делител”, определена върху множеството от естествени числа.

Решение.

отношение R = ((a,b):a делител b):

рефлексивен, а не антирефлексивен, тъй като всяко число се дели без остатък: a/a = 1 за всички a∈N;

не е симетричен, антисиметричен, например 2 е делител на 4, но 4 не е делител на 2;

транзитивно, тъй като ако b/a ∈ N и c/b ∈ N, тогава c/a = b/a ⋅ c/b ∈ N, например, ако 6/3 = 2∈N и 18/6 = 3∈N , тогава 18/3 = 18/6⋅6/3 = 6∈N.

Задача 3.2.Определете свойствата на отношението R – „да бъдеш брат“, определено върху множество хора.
Решение.

Отношение R = ((a,b):a - брат на b):

не рефлексивен, антирефлексивен поради очевидното отсъствие на aRa за всички a;

не е симетричен, тъй като в общия случай между брат a и сестра b има aRb, но не и bRa;

не е антисиметричен, тъй като ако a и b са братя, тогава aRb и bRa, но a≠b;

преходно, ако наричате братя хора, които имат общи родители (баща и майка).

Задача 3.3.Определете свойствата на релацията R – „да бъдеш шеф”, дефинирана върху набор от структурни елементи

Решение.

Отношение R = ((a,b) : a е шефът на b):

• неотражателен, антирефлексен, ако няма смисъл в конкретна интерпретация;
• не симетричен, антисиметричен, тъй като за всички a≠b aRb и bRa не са изпълнени едновременно;
• транзитивно, тъй като ако a е шефът на b и b е шефът на c, тогава a е шефът на c.

Определете свойствата на отношението R i, дефинирано върху множеството M i от матрицата, ако:

1. R 1 „имат същия остатък при деление на 5“; M 1 е множеството от естествени числа.
2. R 2 „да бъдем равни“; M 2 е множеството от естествени числа.
3. R 3 „живея в същия град“; M 3 много хора.
4. R 4 „да бъдеш запознат“; M 4 много хора.
5. R 5 ((a,b):(a-b) - четен; M 5 набор от числа (1,2,3,4,5,6,7,8,9).
6. R 6 ((a,b):(a+b) - четен; M 6 набор от числа (1,2,3,4,5,6,7,8,9).
7. R 7 ((a,b):(a+1) - делител (a+b)) ; M 7 - комплект (1,2,3,4,5,6,7,8,9).
8. R 8 ((a,b):a - делител (a+b),a≠1); M 8 е множеството от естествени числа.
9. R 9 „да бъда сестра“; M 9 - много хора.
10. R 10 „да бъдеш дъщеря“; M 10 - много хора.

Операции върху бинарни отношения

Нека R 1, R 1 са отношения, дефинирани в множеството A.

съюз R 1 ∪ R 2: R 1 ∪ R 2 = ((a,b) : (a,b) ∈ R 1 или (a,b) ∈ R 2 ) ;

кръстовище R 1 ∩ R 2: R 1 ∩ R 2 = ((a,b) : (a,b) ∈ R 1 и (a,b) ∈ R 2 ) ;

разлика R 1 \ R 2: R 1 \ R 2 = ((a,b) : (a,b) ∈ R 1 и (a,b) ∉ R 2 ) ;

универсално отношение U: = ((a;b)/a ∈ A & b ∈ A). ;

допълнение R 1 U \ R 1, където U = A × A;

идентична връзка I: = ((a;a) / a ∈ A);

обратна връзка R -1 1 : R -1 1 = ((a,b) : (b,a) ∈ R 1 );

състав R 1 º R 2: R 1 º R 2: = ((a,b) / a ∈ A&b ∈ B& ∃ c ∈ C: aR 1 c & c R 2 b), където R 1 ⊂ A × C и R 2 ⊂ C×B;

Определение. Степен на родство R на множество A е неговата композиция със себе си.

Обозначаване:

Определение. Ако R ⊂ A × B, тогава се извиква R º R -1 ядрото на релацията R .

Теорема 3.1.Нека R ⊂ A × A е релация, дефинирана в множеството A.

1. R е рефлексивен тогава и само тогава (по-нататък се използва знакът ⇔), когато I ⊂ R.
2. R симетричен ⇔ R = R -1.
3. R преходен ⇔ R º R ⊂ R
4. R е антисиметрично ⇔ R ⌒ R -1 ⊂ I .
5. R е антирефлексивно ⇔ R ⌒ I = ∅ .

Задача 3.4 . Нека R е връзката между множествата (1,2,3) и (1,2,3,4), дадена чрез изброяване на двойките: R = ((1,1), (2,3), (2, 4), (3.1), (3.4)). Освен това S е връзката между множествата S = ((1,1), (1,2), (2,1), (3,1), (4,2)). Изчислете R -1 , S -1 и S º R. Проверете дали (S º R) -1 = R -1 , S -1 .

Решение.
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 .

Задача 3.5 . Нека R е релацията “...родител...” и S релацията “...брат...” в множеството на всички хора. Дайте кратко устно описание на връзката:

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

Решение.

R -1 - отношение “...дете...”;

S -1 - отношение “...брат или сестра...”;

R º S - релация “...родител...”;

S -1 º R -1 - връзка “...дете...”

R º R - отношение “...баба или дядо...”

Проблеми за самостоятелно решаване

1) Нека R е отношението “...баща...” и S е отношението “...сестра...” в множеството от всички хора. Дайте словесно описание на връзката:

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

2) Нека R е отношението “...брат...” и S е отношението “...майка...” в множеството на всички хора. Дайте словесно описание на връзката:

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

3) Нека R е отношението “...дядо...” и S е отношението “...син...” на множеството от всички хора. Дайте словесно описание на връзката:

4) Нека R е релацията “...дъщеря...” и S е релацията “...баба...” в множеството от всички хора. Дайте словесно описание на връзката:

5) Нека R е отношението “...племенница...” и S е отношението “...баща...” в множеството от всички хора. Дайте словесно описание на връзката:

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

6) Нека R е релацията “сестра...” и S е релацията “майка...” в множеството на всички хора. Дайте словесно описание на връзката:

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

7) Нека R е релацията “...майка...” и S е релацията “...сестра...” в множеството от всички хора. Дайте словесно описание на връзката:

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

8) Нека R е релацията “...син...” и S е релацията “...дядо...” на множеството от всички хора. Дайте словесно описание на връзката:

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

9) Нека R е отношението “...сестра...” и S е отношението “...баща...” в множеството от всички хора. Дайте словесно описание на връзката:

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

10) Нека R е отношението “...майка...” и S е отношението “...брат...” в множеството на всички хора. Дайте словесно описание на връзката:

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

Дефиниции

• 1. Бинарна релация между елементи от множества A и B е всяко подмножество на декартовото произведение RAB, RAA.
• 2. Ако A=B, тогава R е двоична релация върху A.
• 3. Обозначение: (x, y)R xRy.
• 4. Областта на дефиниране на бинарно отношение R е множеството R = (x: съществува y, такова че (x, y)R).
• 5. Диапазонът от стойности на двоично отношение R е множеството R = (y: съществува x, така че (x, y)R).
• 6. Допълнението на бинарна връзка R между елементите A и B е множеството R = (AB) R.
• 7. Обратната връзка за двоична връзка R е множеството R1 = ((y, x) : (x, y)R).
• 8. Продуктът на отношенията R1AB и R2BC е отношението R1 R2 = ((x, y) : съществува zB такова, че (x, z)R1 и (z, y)R2).
• 9. Отношението f се нарича функция от A към B, ако са изпълнени две условия:
  • а) f = A, f B
  • б) за всички x, y1, y2 от факта, че (x, y1)f и (x, y2)f следва, че y1=y2.
• 10. Отношението f се нарича функция от A към B, ако в първия параграф f = A, f = B.
• 11. Означения: (x, y)f y = f(x).
• 12. Функцията на идентичност iA: AA се дефинира както следва: iA(x) = x.
• 13. Функция f се нарича функция 1-1, ако за всяко x1, x2, y от факта, че y = f(x1) и y = f(x2) следва x1=x2.
• 14. Функция f: AB предоставя едно-към-едно съответствие между A и B, ако f = A, f = B и f е функция 1-1.
• 15. Свойства на двоичното отношение R върху множеството A:
  • - рефлексивност: (x, x)R за всички xA.
  • - ирефлексивност: (x, x)R за всички xA.
  • - симетрия: (x, y)R (y, x)R.
  • - антисиметрия: (x, y)R и (y, x)R x=y.
  • - транзитивност: (x, y)R и (y, z)R (x, z)R.
  • - дихотомия: или (x, y)R, или (y, x)R за всички xA и yA.
• 16. Множествата A1, A2, ..., Ar от P(A) образуват дял на множеството A, ако
• - Аi, i = 1, ..., r,
• - A = A1A2...Ar,
• - AiAj = , i j.

Подмножествата Аi, i = 1, ..., r, се наричат ​​разделителни блокове.

• 17. Еквивалентността върху множество A е рефлексивна, транзитивна и симетрична релация върху A.
• 18. Класът на еквивалентност на елемент x по еквивалентност R е множеството [x]R=(y: (x, y)R).
• 19. Факторно множество A по R е множеството от класове на еквивалентност на елементи от множество A. Обозначение: A/R.
• 20. Класове на еквивалентност (елементи на факторното множество A/R) образуват дял на множеството A. Обратно. Всяко разделение на множеството A съответства на отношение на еквивалентност R, чиито класове на еквивалентност съвпадат с блоковете на определеното разделение. различно. Всеки елемент от множеството A попада в някакъв клас на еквивалентност от A/R. Класовете на еквивалентност или не се пресичат, или съвпадат.
• 21. Предварителният ред върху множество A е рефлексивна и транзитивна релация върху A.
• 22. Частичен ред върху множество A е рефлексивна, транзитивна и антисиметрична релация върху A.
• 23. Линеен редвърху множеството A е рефлексивна, транзитивна и антисиметрична релация върху A, удовлетворяваща свойството дихотомия.

Нека A=(1, 2, 3), B=(a, b). Нека напишем декартовото произведение: AB = ( (1, a), (1, b), (2, a), (2, b), (3, a), (3, b) ). Нека вземем произволно подмножество на това декартово произведение: R = ( (1, a), (1, b), (2, b) ). Тогава R е двоично отношение върху множествата A и B.

Ще бъде ли тази връзка функция? Нека проверим изпълнението на две условия 9а) и 9б). Областта на дефиниране на отношението R е множеството R = (1, 2) (1, 2, 3), т.е. първото условие не е изпълнено, така че една от двойките трябва да се добави към R: (3, а) или (3, б). Ако добавите и двете двойки, тогава второто условие няма да бъде изпълнено, тъй като ab. По същата причина една от двойките трябва да бъде елиминирана от R: (1, a) или (1, b). По този начин отношението R = ( (1, a), (2, b), (3, b) ) е функция. Имайте предвид, че R не е функция 1-1.

На дадени множества A и B следните отношения също ще бъдат функции: ( (1, a), (2, a), (3, a) ), ( (1, a), (2, a), (3 , b ) ), ( (1, b), (2, b), (3, b) ) и т.н.

Нека A=(1, 2, 3). Пример за релация върху множество A е R = ( (1, 1), (2, 1), (2, 3) ). Пример за функция върху множество A е f = ( (1, 1), (2, 1), (3, 3) ).

Примери за решаване на проблеми

1. Намерете R, R, R1, RR, RR1, R1R за R = ((x, y) | x, y D и x+y0).

Ако (x, y)R, тогава x и y преминават през всички реални числа. Следователно R = R = D.

Ако (x, y)R, тогава x+y0, което означава y+x0 и (y, x)R. Следователно R1=R.

За всяко xD, yD вземаме z=-|max(x, y)|-1, след това x+z0 и z+y0, т.е. (x, z)R и (z, y)R. Следователно RR = RR1 = R1R = D2.

2. За кои бинарни отношения R е валидно R1= R?

Нека RAB. Има два възможни случая:

• (1) AB. Да вземем xAB. Тогава (x, x)R (x, x)R1 (x, x)R (x, x)(AB) R (x, x)R. Противоречие.
• (2) AB=. Тъй като R1BA и RAB, тогава R1= R= . От R1 = следва, че R = . От R = следва, че R=AB. Противоречие.

Следователно, ако A и B, тогава такива отношения R не съществуват.

3. Върху множеството D от реални числа дефинираме отношението R по следния начин: (x, y)R (x-y) е рационално число. Докажете, че R е еквивалентност.

Рефлексивност:

За всяко xD x-x=0 е рационално число. Тъй като (x, x)R.

Симетрия:

Ако (x, y)R, тогава x-y = . Тогава y-x=-(x-y)=- е рационално число. Следователно (y, x)R.

Преходност:

Ако (x, y)R, (y, z)R, тогава x-y = и y-z =. Като добавим тези две уравнения, получаваме, че x-z = + е рационално число. Следователно (x, z)R.

Следователно R е еквивалентност.

4. Разделянето на равнината D2 се състои от блоковете, показани на фигура а). Запишете отношението на еквивалентност R, съответстващо на това разпределение и класовете на еквивалентност.

Подобна задача за б) и в).

а) две точки са еквивалентни, ако лежат на права от вида y=2x+b, където b е всяко реално число.

б) две точки (x1,y1) и (x2,y2) са еквивалентни, ако (цялата част от x1 е равна на цялата част от x2) и (цялата част от y1 е равна на цялата част от y2).

в) решавайте сами.

Проблеми за самостоятелно решаване

• 1. Докажете, че ако f е функция от A до B и g е функция от B до C, тогава fg е функция от A до C.
• 2. Нека A и B са крайни множества, състоящи се съответно от m и n елемента.

Колко бинарни релации има между елементите на множествата A и B?

Колко функции има от А до Б?

Колко функции 1-1 има от A до B?

За кои m и n има взаимно еднозначно съответствие между A и B?

3. Докажете, че f удовлетворява условието f(AB)=f(A)f(B) за всяко A и B тогава и само ако f е функция 1-1.

Връзка, дефинирана върху набор, може да има редица свойства, а именно:

2. Рефлексивност

Определение.Поведение Рпо различни начини хсе нарича рефлексивен, ако всеки елемент хкомплекти хе във връзка РСъс себе си.

Използвайки символи, тази връзка може да бъде записана по следния начин:

Ротразяващо върху х Û(" хÎ х) x R x

Пример.Отношението на равенство върху множество отсечки е рефлексивно, т.к всеки сегмент е равен на себе си.

Графът на рефлексивната връзка има цикли във всички върхове.

2. Антирефлексивност

Определение.Поведение Рпо различни начини хсе нарича антирефлексивно, ако няма елемент хкомплекти хне във връзка РСъс себе си.

Рантирефлексно на х Û(" хÎ х)

Пример.Пряка връзка хперпендикулярно на права линия при» върху множеството прави линии на равнината е антирефлексивно, т.к нито една права линия на равнината не е перпендикулярна на себе си.

Графиката на антирефлексното отношение не съдържа нито един цикъл.

Имайте предвид, че има отношения, които не са нито рефлексивни, нито антирефлексивни. Например, разгледайте отношението "точка хсиметричен на точката при"на набор от точки на равнината.

Точка хсиметричен на точката х- вярно; точка присиметричен на точката при- невярно, следователно не можем да твърдим, че всички точки от равнината са симетрични на себе си и също не можем да твърдим, че нито една точка от равнината не е симетрична на себе си.

3. Симетрия

Определение. Поведение Рпо различни начини хсе нарича симетричен, ако от факта, че елементът хе във връзка Рс елемент при, следва, че елементът прие във връзка Рс елемент х.

Рсиметричен х Û(" х, приÎ х) x R y Þ y R x

Пример.Пряка връзка хпресича права привърху множеството прави на равнината” е симетрично, т.к ако е прав хпресича права при, след това линията приопределено ще премине границата х.

Графика на симетрична връзка заедно с всяка стрелка от точка хточно притрябва да съдържа стрелка, свързваща същите точки, но в обратна посока.

4. Асиметрия

Определение. Поведение Рпо различни начини хсе нарича асиметричен, ако за никакви елементи х, приот много хне може да се случи елементът хе във връзка Рс елемент прии елемент прие във връзка Рс елемент х.

Расиметричен х Û(" х, приÎ х) x R y Þ

Пример.Поведение " х < при» асиметрично, т.к за всяка двойка елементи х, прине може да се каже, че в същото време х < приИ при<х.

Една асиметрична релационна графика няма цикли и ако два върха на графиката са свързани със стрелка, тогава има само една стрелка.

5. Антисиметрия

Определение. Поведение Рпо различни начини хсе нарича антисиметрично ако, от факта, че хе в отношения с при, А прие в отношения с хследва това х = u.

Рантисиметричен х Û(" х, приÎ х) x R y Ù y R xÞ x = y

Пример.Поведение " х£ при» антисиметрично, т.к условия х£ приИ при£ хсе изпълняват едновременно само когато х = u.

Антисиметричната релационна графика има цикли и ако два върха на графиката са свързани със стрелка, тогава има само една стрелка.

6. Преходност

Определение. Поведение Рпо различни начини хсе нарича транзитивно, ако за всякакви елементи х, при, zот много хот това, което хе в отношения с при, А прие в отношения с zследва това хе в отношения с z.

Ртранзитивенона х Û(" х, при, zÎ х) x R y Ù y R zÞ x R z

Пример.Поведение " хмногократни при» преходен, т.к ако първото число е кратно на второто, а второто е кратно на третото, тогава първото число ще бъде кратно на третото.

Графика на транзитивна връзка с всяка двойка стрелки от хДа се прии от приДа се zсъдържа стрелка, тръгваща от хДа се z.

7. Свързаност

Определение. Поведение Рпо различни начини хсе нарича свързан ако за някакви елементи х, приот много X xе в отношения с приили прие в отношения с хили x = y.

Рсвързан х Û(" х, при, zÎ х) x R y Ú y R zÚ х= при

С други думи: отношение Рпо различни начини хсе нарича свързан, ако за всеки различен елемент х, приот много X xе в отношения с приили прие в отношения с хили x = y.

Пример.Поведение " х< при» съгласувано, т.к каквито и реални числа да вземем, едно от тях със сигурност ще бъде по-голямо от другото или те ще бъдат равни.

В графика на свързана релация всички върхове са свързани помежду си чрез стрелки.

Пример.Проверете какви свойства има

поведение " Х -разделител при“, определени на снимачната площадка

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

1) тази връзка е рефлексивна, т.к всяко число от дадено множество е делител на себе си;

2) тази връзка не притежава свойството антирефлексивност;

3) свойството за симетрия не е изпълнено, т.к например 2 е делител на 4, но 4 не е делител на 2;

4) тази връзка е антисиметрична: две числа могат да бъдат едновременно делители едно на друго само ако тези числа са равни;

5) отношението е преходно, т.к ако едно число е делител на второто, а второто е делител на третото, то първото число задължително ще бъде делител на третото;

6) отношението не притежава свойството на свързаност, т.к например числата 2 и 3 на графиката не са свързани със стрелка, т.к две различни числа 2 и 3 не са делители едно на друго.

По този начин тази връзка има свойствата на рефлексивност, асиметрия и транзитивност.

§ 3. Отношение на еквивалентност.
Връзката между релацията на еквивалентност и разделянето на множество на класове

Определение.Поведение Рна снимачна площадка хсе нарича релация на еквивалентност, ако е рефлексивна, симетрична и транзитивна.

Пример.Помислете за връзката " хсъученик при„на много студенти от Педагогическия факултет. Има следните свойства:

1) рефлексивност, т.к всеки ученик е свой съученик;

2) симетрия, т.к ако ученик х при, след това ученикът прие съученик на ученик х;

3) преходност, т.к ако ученик х- съученик при, и ученикът при– съученик z, след това ученикът хще бъде съученик на ученика z.

По този начин тази връзка има свойствата на рефлексивност, симетрия и транзитивност и следователно е връзка на еквивалентност. В същото време много студенти от Педагогическия факултет могат да бъдат разделени на подгрупи, състоящи се от студенти, обучаващи се в един и същи курс. Получаваме 5 подмножества.

Отношенията на еквивалентност също са например отношението на паралелност на линиите, отношението на равенство на фигурите. Всяка такава връзка е свързана с разделяне на набора на класове.

Теорема.Ако на снимачната площадка хдадено отношение на еквивалентност, то разделя това множество на по двойки несвързани подмножества (класове на еквивалентност).

Обратното твърдение също е вярно: ако всяко отношение, дефинирано на множеството х, генерира разделяне на това множество на класове, тогава това е релация на еквивалентност.

Пример.На снимачната площадка х= (1; 2; 3; 4; 5; 6; 7; 8) се уточнява връзката „да има същия остатък при деление на 3”. Отношение на еквивалентност ли е?

Нека изградим графика на тази връзка:

Това отношение има свойствата на рефлексивност, симетрия и транзитивност, следователно е отношение на еквивалентност и разделя множеството хкъм класове за еквивалентност. Във всеки клас на еквивалентност ще има числа, които, разделени на 3, дават същия остатък: х 1 = {3; 6}, х 2 = {1; 4; 7}, х 3 = {2; 5; 8}.

Смята се, че класът на еквивалентност се определя от всеки негов представител, т.е. произволен елемент от този клас. По този начин клас от равни дроби може да бъде специфициран чрез указване на всяка дроб, принадлежаща към този клас.

В началния курс по математика се срещат и отношения на еквивалентност, например „изрази хИ приимат еднакви числови стойности", "фигура хравен на фигурата при».

Нека някое непразно множество A и R е определено подмножество на декартовия квадрат на множеството A: Р  А  А.

Поведение Рна снимачна площадка Анаречено подмножество на множество А А(или А 2 ). По този начин поведениеима специален случай на кореспонденция, когато зоната на пристигане съвпада с зоната на заминаване. Точно като съответствието, релацията е подредена двойка, където и двата елемента принадлежат към едно и също множество.

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

Фактът че ( а, b)R може да се запише по следния начин: а Р b. Той гласи: " Ае в съотношението R към b“ или „между АИ bвръзката R е изпълнена. Иначе пиши:( а, b)R или аR b.

Пример за отношения върху набор от числа са следните: “=”, “”, “”, “>” и т.н. Към съвкупността от служители на една компания има нагласата „да си шеф” или „да си подчинен”, към съвкупността от роднини – „да си прародител”, „да си брат”, „да си баща” и др.

Разгледаните отношения се наричат ​​бинарни (двуместни) еднородни отношения и са най-важните в математиката. Наред с тях смятат и те П- местно или П-арни отношения:

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

Тъй като отношенията са частен случай на съответствие, всички описани по-горе методи могат да бъдат използвани за тяхното дефиниране.

Очевидно, като зададем релацията по матричен начин, получаваме квадратна матрица.

С геометрично (графично) представяне на връзката получаваме диаграма, която включва:

върхове, обозначени с точки или кръгове, които съответстват на елементи от множеството,

и дъги (линии), съответстващи на двойки елементи, включени в бинарни отношения, обозначени с линии със стрелки, насочени от върха, съответстващ на елемента а към върха, съответстващ на елемента b , Ако а Рb .

Такава фигура се нарича насочена графа (или диграф) на двоична релация.

Задача 4.9.1 . Съотношение може да се даде "да бъде делител на множеството M = (1, 2, 3, 4)". матрица:

обява: R = ((1,1), (1,2), (1,3), (1,4), (2,2), (2,4), (3,3), ((4,4 ));

геометрично (графично):

1. Запишете подредени двойки, принадлежащи към следните двоични отношения на множеството 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. Отношението R върху множеството X = (a, b, c, d) е дадено от матрицата

,

в който редът на редовете и колоните съответства на реда на изписаните елементи. Избройте подредени двойки, принадлежащи към тази релация. Представете връзката с помощта на графика.

3. Отношението върху множеството A = (1, 2, 3, 4) се представя с графика. Необходимо:

списък на подредени двойки, принадлежащи на R;

изпишете съответната матрица;

дефинирайте тази връзка с помощта на предикати.

(отговор: a-b= 1).

4.10. Основни типове (свойства) на бинарни отношения

Нека е дадено двоично отношение Рна снимачна площадка А 2 : R  A  A = (( а, b) | аA, bA, ( а, b)R)

Бинарна релация Р на снимачна площадка А Наречен отразяващ, ако има такива аА изпълнени аРа, това е ( А,А)R. Главният диагонал на матрицата на рефлексивните отношения се състои от единици. Рефлексивната релационна графа задължително има цикли във всеки връх.

Примерирефлексивни отношения: , =,  върху множеството от реални числа, „да не съм шеф” върху множеството от служители.

Бинарна релация Рна множеството A се нарича антирефлекс (ирефлексивен), ако има такива аИ връзката не е изпълнена аРа, това е ( А,А)R. Главният диагонал на ирефлексивната релационна матрица се състои от нули. Нерефлексивната релационна графика няма цикли.

Примериантирефлексивни отношения:<, >върху множеството от реални числа, перпендикулярност на правите върху множеството от прави.

Бинарна релация Р на снимачната площадка А Наречен симетричен, ако има такива а, bАот аРbТрябва bРа, тоест ако ( а, b)Р, тогава и( b, а)Р. Симетричната релационна матрица е симетрична спрямо главния си диагонал ( σ ij = σ джи). Графикът на симетрична връзка не е насочен (ръбовете са показани без стрелки). Всяка двойка върхове тук е свързана с неориентирано ребро.

Примерисиметрични отношения:  върху множеството от реални числа, „свързани“ върху множеството от хора.

Бинарна релация Р на снимачната площадка А Наречен:

антисиметричен, ако има такива а, bАот аРbИ bРаследва това а=b. Тоест, ако ( а, b)РИ( b, а)Р, тогава следва това а=b. Матрицата на антисиметричното съотношение по главния диагонал има всички единици и няма двойка единици, разположени на симетрични места по отношение на главния диагонал. С други думи всичко σ ii=1 и ако σ ij=1, тогава задължително σ джи=0. Антисиметричната релационна графа има цикли във всеки връх и върховете са свързани само с една насочена дъга.

Примериантисиметрични отношения: , ,  върху множеството от реални числа; ,  на комплекти;

Асиметричен, ако има такива а, bАот аРb следва несъответствие bРа, тоест ако ( а, b)Р, Че ( b, а) Р. Матрицата на асиметричното отношение по главния диагонал има нули ( σ ij=0) всички и никакви симетрични двойки единици (ако σ ij=1, тогава задължително σ джи=0). Графът на асиметрична връзка няма цикли и върховете са свързани с една насочена дъга.

Примери за асиметрични връзки:<, >на набор от реални числа, „да бъдеш баща“ на набор от хора.

Бинарна релация Р на снимачната площадка А Наречен преходенназ, ако има такива а, b, сАот аРbИ bРаследва, че аРс. Тоест, ако ( а, b)РИ( b, с)Рследва, че ( А, с)Р. Матрицата на транзитивна релация се характеризира с това, че ако σ ij=1 и σ jm=1, тогава задължително σ аз съм=1. Графът на транзитивната връзка е такъв, че ако например първият-вторият и вторият-третият връх са свързани с дъги, тогава задължително има дъги от първия до третия връх.

Примерипреходни отношения:<, , =, >,  върху множеството от реални числа; „да бъдеш шеф“ на много служители.

Бинарна релация Р на снимачната площадка А Наречен антитранзитивниназ, ако има такива а, b, сАот аРbИ bРаследва, че не е изпълнено аРс. Тоест, ако ( а, b)РИ( b, с)Рследва, че ( А, с) Р. Матрицата на антитранзитивната релация се характеризира с това, че ако σ ij=1 и σ jm=1, тогава задължително σ аз съм=0. Графикът на една антитранзитивна релация е такъв, че ако, например, първият-вторият и вторият-третият връх са свързани с дъги, тогава не е задължително да има дъга от първия до третия връх.

Примери за антитранзитивни отношения: „разминаване на паритета“ на набор от цели числа; „да бъдеш пряк ръководител“ на много служители.

Ако една релация няма някакво свойство, тогава чрез добавяне на липсващите двойки можете да получите нова релация с това свойство. Множеството от такива липсващи двойки се нарича късо съединениеотношения за този имот. Обозначава се като Р* . По този начин можете да получите рефлексивно, симетрично и транзитивно затваряне.

Задача 4.10.1. Върху множеството A = (1, 2, 3, 4) отношението R=(( а,b)| а,bA, а+b-четен брой). Определете вида на тази връзка.

Решение. Матрицата на тази връзка:

. Очевидно е, че връзката е отразяващ, тъй като единиците са разположени по главния диагонал. То симетрично: σ 13 = σ 31, σ 24 = σ 42. Преходно: (1,3)R, (3,1)R и (1,1)R; (2,4)R, (4,2)R и (2,2)R и т.н.

Задача 4.10.2. Какви са свойствата на множеството A = ( а, b, ° С, д) има двоична връзка R = (( а,b), (b,д), (а,д), (b,а), (b,° С)}?

Решение . Нека изградим матрицата на тази връзка и нейната графика:

Поведение ирефлексивно, тъй като всички σ ii= 0. То Не симетрично, тъй като σ 23 =1 и σ 32 =0 обаче, σ 12 =σ 21 =1. Поведение Не преходно, тъй като σ 12 =1, σ 23 =1 и σ 13 =0; σ 12 =1, σ 21 =1 и σ 11 =0; но в същото време σ 12 =1, σ 24 =1 и σ 14 =1.

Задача 4.10.3. Върху множеството A = (1,2,3,4,5) е дадено отношението R = ((1,2), (2,3), (2,4), (4,5)). Определете типа връзка и намерете следните затваряния за R:

отразяващ;

симетричен;

преходен.

Решение. Отношението е ирефлексивно, тъй като няма нито един елемент от формата ( А,А). Асиметричен, тъй като не съдържа двойки от формата ( а,b) И ( b,а) и всички диагонални елементи са 0. Антитранзитивни, защото (1,2)R, (2,3)R, но (1,3)R. По същия начин (2,4)R, (4,5)R и (2,5)R и т.н.

рефлексивно затваряне на дадено отношение R * =((1,1), (2,2), (3,3), (4,4), (5,5));

симетрично затваряне: R*=((2,1), (3,2), (4,2), (5,4));

транзитивно затваряне: R*=((1,3), (1,4), (2,5)). Разгледайте графиката на първоначалната връзка и получената транзитивна.

Задачи за самостоятелно решаване.

1. Дадена е връзката R = ((1,1), (1,2), (1,3), (3,1), (2,3)). Определете неговия тип и намерете затваряния въз основа на рефлексивност, симетрия и транзитивност.

2. Отношението към набора от думи на руския език се определя, както следва: АР bако и само ако имат поне една обща буква. Определете вида на връзката върху множеството A = (крава, карета, конец, брадва).

3. Дайте примери за двоични отношения в множеството A = (1, 2) и B = (1, 2, 3), които биха били:

не е рефлексивен, не е симетричен, не е преходен;

рефлексивен, несиметричен, непреходен;

симетричен, но не рефлексивен и непреходен;

преходен, но не рефлексивен и не симетричен;

рефлексивен, симетричен, но не и преходен;

рефлексивен, преходен, но не симетричен;

нерефлексивен, симетричен, преходен;

рефлексивен, симетричен, преходен.