Определения
- 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 \u003d 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, a) или (3, б). Ако се добавят и двете двойки, тогава второто условие няма да бъде изпълнено, тъй като ab. По същата причина една от двойките (1, a) или (1, b) трябва да бъде изхвърлена от R. Следователно отношението 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, съответстващо на този дял и класовете на еквивалентност.
Подобен проблем за b) и c).
а) две точки са еквивалентни, ако лежат на права линия от вида 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 функции има от А до Б?
За какви m и n има съответствие едно към едно между A и B?
3. Докажете, че f удовлетворява условието f(AB)=f(A)f(B) за всякакви A и B, само ако f е функция 1-1.
Свойства на връзката:
1) рефлексивност;
2) симетрия;
3) транзитивност.
4) свързаност.
Поведение Рна снимачната площадка хНаречен отразяващако за всеки елемент от множеството хможе да се каже, че е във връзка РСъс себе си: хRx.Ако релацията е рефлексивна, тогава във всеки връх на графа има цикъл. Обратно, граф, чийто всеки връх съдържа цикъл, е рефлексивна релационна графа.
Примери за рефлексивни отношения са „множественото“ отношение на множеството от естествени числа (всяко число е кратно на себе си) и отношението на подобието на триъгълниците (всеки триъгълник е подобен на себе си) и отношението „равенство“ (всяко число е равно на себе си) и т.н.
Има отношения, които нямат свойството на рефлексивност, например отношението на перпендикулярност на сегментите: аб, ба(няма сегмент, за който може да се каже, че е перпендикулярен на себе си) . Следователно на графиката на тази връзка няма цикли.
Той няма свойството на рефлексивност и съотношението е „по-дълго“ за сегменти, „по-голямо с 2“ за естествени числа и т.н.
Поведение Рна снимачната площадка хНаречен антирефлексен, ако за който и да е елемент от множеството хвинаги фалшиво хRx: .
Има отношения, които не са нито рефлексивни, нито антирефлексивни. Пример за такава връзка е връзката „точка хсиметрични към точка вотносително прав л”, дефиниран върху множеството точки на равнината. Всъщност всички точки от линията лса симетрични на себе си и точки, които не лежат на права л,не са симетрични на себе си.
Поведение Рна снимачната площадка хНаречен симетрични, ако условието е изпълнено: от факта, че елементът хе във връзка с елемента г, следва, че елементът ге във връзка Рс елемент Х:xRyyRx .
Графиката на симетрична връзка има следната характеристика: заедно с всяка стрелка, идваща от хДа се г, графиката съдържа стрелка, водеща от гДа се х(фиг. 35).
Примери за симетрични връзки могат да бъдат следните: съотношението на "паралелност" на сегментите, съотношението на "перпендикулярност" на сегментите, съотношението на "равенството" на сегментите, съотношението на подобие на триъгълниците, съотношението на "равенството" на дроби и др.
Има отношения, които нямат свойството на симетрия.
Наистина, ако сегментът хпо-дълъг от сегмента в, след това сегментът вне може да бъде по-дълъг от сегмента х. Графиката на тази връзка има особеност: стрелката, свързваща върховете, е насочена само в една посока.
Поведение РНаречен антисиметрични, ако за някакви елементи хи гот истината xRyследва фалшификация yRx: : xRyyRx.
В допълнение към „по-дългата“ връзка има и други антисиметрични отношения на множеството от сегменти. Например, отношението "по-голямо от" за числа (ако хПовече ▼ в, тогава вне може да бъде повече х), съотношението „повече от“ и т.н.
Има отношения, които нямат нито свойството на симетрия, нито свойството на антисиметрия.
Отношение R на снимачната площадка хНаречен преходенако от какъв елемент хе във връзка Рс елемент y,и елементът ге във връзка Рс елемент z, следва, че елементът хе във връзка Рс елемент z: xRyи yRzxRz.
Графика на преходна връзка с всяка двойка стрелки, тръгваща от хДа се ги от гДа се z, съдържа стрелка, водеща от хДа се z.
Връзката "по-дълго" на множеството от сегменти също има свойството на транзитивност: ако сегментът апо-дълъг от сегмента б, раздел бпо-дълъг от сегмента С, след това сегментът апо-дълъг от сегмента С.Отношението "равенство" върху множеството от сегменти също има свойството на транзитивност: (а=b, b=c)(a=c).
Има отношения, които нямат свойството на преходност. Такава релация е например релацията на перпендикулярност: ако сегментът аперпендикулярно на сегмента б, и сегментът бперпендикулярно на сегмента С, след това сегментите аи Сне перпендикулярно!
Има още едно свойство на отношенията, наречено свързано свойство, а отношение, което го притежава, се нарича свързано.
Поведение Рна снимачната площадка хНаречен свързани,ако за някакви елементи хи гот това множество е изпълнено следното условие: ако хи гса различни, значи хе във връзка Рс елемент г, или елемент ге във връзка Рс елемент х. Използвайки символи, това може да бъде написано по следния начин: xyxRyили yRx.
Например, отношението "по-голямо от" за естествени числа има свойството да бъде свързано: за всякакви различни числа x и y може да се твърди или x>y, или y>x.
В релационна графика всеки два върха са свързани със стрелка. Обратното също е вярно.
Има отношения, които нямат свойството на свързаност. Такава връзка, например, е отношението на делимост на множеството от естествени числа: можем да наречем такива числа x и гкаквото и да е числото хне е делител г, без номер гне е делител х(числа 17 и 11 , 3 и 10 и др.) .
Нека разгледаме няколко примера. На снимачната площадка X=(1, 2, 4, 8, 12)връзката „число хкратно на г". Нека построим графика на тази връзка и да формулираме нейните свойства.
Казват за отношението на равенството на дробите, това е отношение на еквивалентност.
Поведение Рна снимачната площадка хНаречен отношение на еквивалентност,ако едновременно притежава свойствата на рефлексивност, симетрия и транзитивност.
Примери за отношения на еквивалентност са: отношения на равенство на геометрични форми, успоредност на прави линии (при условие, че съвпадащите прави се считат за успоредни).
В обсъденото по-горе отношение на "равенството на дробите", множеството хразделени на три подмножества: ; ; }, {; } , (). Тези подмножества не се пресичат и тяхното обединение съвпада с множеството х, т.е. имаме разделяне на множеството на класове.
Така, ако е дадено релация на еквивалентност върху множество X, тогава тя генерира разделяне на това множество на двойно несвързани подмножества - класове на еквивалентност.
Така установихме, че отношението на равенство на множеството
х=( ;; ; ; ; ) съответства на разделянето на това множество на еквивалентни класове, всеки от които се състои от равни дроби.
Принципът за разделяне на множество на класове чрез някакво отношение на еквивалентност е важен принцип на математиката. Защо?
Първо, еквивалентен - означава еквивалентен, взаимозаменяем. Следователно елементите от един и същ клас на еквивалентност са взаимозаменяеми. И така, дроби, които са в същия клас на еквивалентност (; ; ), са неразличими от гледна точка на отношението на равенството и дроба може да бъде заменен с друг, например . И тази подмяна няма да промени резултата от изчисленията.
На второ място, тъй като в класа на еквивалентност има елементи, които са неразличими от гледна точка на някаква връзка, се смята, че класът на еквивалентност се определя от всеки негов представител, т.е. произволен елемент от класа. Така че всеки клас от равни дроби може да бъде определен чрез посочване на всяка фракция, принадлежаща към този клас. на класа на еквивалентност от един представител позволява вместо всички елементи на множеството да се изследва множеството от представители от класовете на еквивалентност. Например, релацията за еквивалентност "има еднакъв брой върхове", дадена на набор от многоъгълници, генерира разделяне на този набор на класове от триъгълници, четириъгълници, петоъгълници и т.н. свойства, присъщи на определен клас, се разглеждат върху един от неговите представители.
На трето място, разделянето на множество на класове с помощта на релация на еквивалентност се използва за въвеждане на нови понятия. Например, концепцията за "сноп от линии" може да се дефинира като това общо нещо, което успоредните прави имат една с друга.
Взаимоотношенията по поръчка са друг важен вид взаимоотношения. Помислете за проблема.На снимачната площадка х={3, 4, 5, 6, 7, 8, 9, 10 ) отношението „има еднакъв остатък, когато се раздели на 3 ". Тази връзка генерира дял на множеството хв класове: един ще включва всички числа, когато е разделен на 3 получени в остатъка 0 (това са числа 3, 6, 9 ). Във втория - числа, когато се делят на 3 остатъкът е 1 (това са числа 4, 7, 10 ). Третата ще включва всички числа, когато е разделена на 3 остатъкът е 2 (това са числа 5, 8 ). Действително, получените множества не се пресичат и тяхното обединение съвпада с множеството х. Следователно отношението „да има същия остатък, когато се дели на 3 » дефиниран в комплекта х, е релация на еквивалентност.
За да вземем друг пример, много ученици в клас могат да бъдат сортирани по височина или възраст. Забележете, че тази връзка има свойствата на антисиметрия и транзитивност. Или всеки знае реда на буквите в азбуката. То се осигурява от отношението „трябва“.
Поведение Рна снимачната площадка хНаречен стриктно отношение на реда, ако едновременно притежава свойствата на антисиметрия и транзитивност. Например релацията х< г».
Ако връзката има свойствата на рефлексивност, антисиметрия и транзитивност, тогава тя ще бъде такава нестриктно отношение на поръчката. Например релацията хг».
Примери за отношението на реда са: отношението „по-малко от“ на множеството естествени числа, отношението „по-късо“ на множеството от сегменти. Ако едно порядково отношение също има свойството да бъде свързано, тогава се казва, че е линейно отношение на ред. Например, отношението "по-малко от" на множеството естествени числа.
Няколко хНаречен подреден,ако има отношение на поръчка.
Например, много X={2, 8, 12, 32 ) може да се подреди с помощта на релацията “по-малко от” (фиг. 41), или това може да стане с помощта на релацията “множество” (фиг. 42). Но, като отношение на ред, отношенията „по-малко от“ и „умножават“ подреждат множеството от естествени числа по различни начини. Връзката "по-малко от" ви позволява да сравните произволни две числа от набора х, а релацията "умножи" няма такова свойство. Да, няколко числа. 8 и 12 не е обвързана от отношението "умножавам": не може да се каже, че 8 многократни 12 или 12 многократни 8.
Не трябва да се мисли, че всички отношения се делят на отношения на еквивалентност и отношения на ред. Има огромен брой отношения, които не са нито отношения на еквивалентност, нито отношения на ред.
Позволявам Р- някаква бинарна релация на множеството X, а x, y, z са всеки от неговите елементи. Ако елементът x е във връзка R с елемента y, тогава пишем xRy.
1. Връзка R върху множество X се нарича рефлексивна, ако всеки елемент от множеството е в тази връзка със себе си.
R -рефлексивно върху X<=>xRx за всяко x€ X
Ако отношението R е рефлексивно, тогава във всеки връх на графа има цикъл. Например, отношенията за равенство и успоредност за отсечките са рефлексивни, докато перпендикулярността и "по-дългите" отношения не са рефлексивни. Това е отразено в графиките на фигура 42.
2. Връзка R върху множество X се нарича симетрична, ако фактът, че елемент x е в дадена връзка с елемент y, предполага, че елемент y е в същата връзка с елемент x.
R - симетричен на (xYau => y Rx)
Графиката на симетрична връзка съдържа сдвоени стрелки, движещи се в противоположни посоки. Отношенията на успоредност, перпендикулярност и равенство за отсечките са симетрични, а отношението "по-дълго" не е симетрично (фиг. 42).
3. Връзка R върху множество X се нарича антисиметрична, ако за различни елементи x и y от множеството X фактът, че елементът x е в дадена връзка с елемента y, предполага, че елементът y не е в тази връзка с елемента x.
R - антисиметричен на X" (xRy и xy ≠ yRx)
Забележка: надчертанието означава отрицание на твърдението.
На графика на антисиметричното съотношение само една стрелка може да свърже две точки. Пример за такава връзка е „по-дългата” връзка за сегменти (фиг. 42). Отношенията на паралелизъм, перпендикулярност и равенство не са антисиметрични. Има връзки, които не са нито симетрични, нито антисиметрични, като връзката „да бъдеш брат“ (Фигура 40).
4. Връзка R върху множество X се нарича транзитивна, ако фактът, че елемент x е в дадена връзка с елемент y и елемент y е в тази връзка с елемент z, предполага, че елементът x е в дадена връзка с елемент Z
R - преходен на A≠ (xRy и yRz=> xRz)
На графиките на отношенията „по-дълги“, паралелизъм и равенство на фигура 42, можете да видите, че ако стрелката върви от първия елемент към втория и от втория към третия, тогава задължително има стрелка, която върви от първия елемент към третия. Тези отношения са преходни. Перпендикулярността на отсечките няма свойството на транзитивност.
Съществуват и други свойства на отношения между елементи от едно и също множество, които не разглеждаме.
Една и съща връзка може да има няколко свойства. Така, например, на набор от сегменти, отношението „е равно“ е рефлексивно, симетрично, преходно; отношението "по-голямо от" е антисиметрично и преходно.
Ако релация на множество X е рефлексивна, симетрична и транзитивна, тогава тя е релация на еквивалентност на това множество. Такива отношения разделят множеството X на класове.
Тези взаимоотношения се проявяват например при изпълнение на задачи: „Вземете ленти с еднаква дължина и ги подредете в групи“, „Разпръснете топките, така че всяка кутия да съдържа топки от същия цвят“. Отношенията на еквивалентност („да са еднакви по дължина“, „да са от един и същи цвят“) определят в този случай разделянето на наборите от ивици и топки на класове.
Ако релация от множество 1 е транзитивна и антисиметрична, тогава тя се нарича порядка на това множество.
Множество с дефинирана връзка на ред се нарича подредено множество.
Например, когато изпълняват задачи: „Сравнете лентите по ширина и ги подредете от най-тясната към най-широката“, „Сравнете числата и подредете картите с числа“, децата подреждат елементите на наборите от ленти и картички с числа с помощта на отношения на поръчката; „бъди по-широк“, „следвай“.
Като цяло отношенията на еквивалентност и ред играят голяма роля за формирането у децата на правилни представи за класификацията и подреждането на множествата. Освен това има много други отношения, които не са нито еквивалентни, нито подредени отношения.
6. Какво е характеристично свойство на множество?
7. В какви отношения могат да бъдат множествата? Дайте обяснения за всеки случай и ги изобразете с помощта на кръгове на Ойлер.
8. Дефинирайте подмножество. Дайте пример за множества, едното от които е подмножество на другото. Запишете връзката им с помощта на символи.
9. Дефиниране на равни множества. Дайте примери за две равни множества. Запишете връзката им с помощта на символи.
10. Определете пресечната точка на две множества и я изобразете с помощта на окръжности на Ойлер за всеки конкретен случай.
11. Дефинирайте обединението на две множества и го представете с помощта на Ойлерови кръгове за всеки конкретен случай.
12. Определете разликата на две множества и я изобразете с помощта на Ойлерови кръгове за всеки конкретен случай.
13. Определете допълнението и го изобразете с помощта на кръгове на Ойлер.
14. Какво се нарича разделяне на множество на класове? Назовете условията за правилна класификация.
15. Какво се нарича съответствие между две множества? Назовете начините за задаване на съответствия.
16. Какво съответствие се нарича едно към едно?
17. Кои множества се наричат еквивалентни?
18. Кои множества се наричат равни?
19. Назовете начините за задаване на отношения на множеството.
20. Какво отношение върху множество се нарича рефлексивно?
21. Кое отношение върху множество се нарича симетрично?
22. Кое отношение върху множество се нарича антисиметрично?
23. Кое отношение върху множество се нарича транзитивно?
24. Дефинирайте релация на еквивалентност.
25. Дефинирайте отношението на поръчката.
26. Какво множество се нарича подредено?
За да дефинираме общото понятие за бинарна релация върху множество, ние действаме по същия начин, както в случая на съответствията,
тези. Нека първо разгледаме конкретен пример. Нека отношението "по-малко от" е дадено на множеството X = (2, 4, 6, 8). Това означава, че за произволни две числа от множеството X можете да кажете кое от тях е по-малко: 2< 4, 2 < 6, 2 < 8, 4 < 6, 4 < 8, 6 < 8. Полученные неравенства можно записать иначе, в виде упорядоченных пар: (2, 4), (2, 6), (2, 8), (4, 6), (4, 8), (6, 8). Но все эти пары есть элементы декартова произведения X х X, поэтому об отношении «меньше», заданном на множестве X, можно сказать, что оно является подмножеством множества X х X.
Най-общо, бинарните отношения върху множество X се дефинират по следния начин:
Определение. Бинарна релация върху множество X е всяко подмножество на декартовото произведение X x X.
Тъй като в бъдеще ще разглеждаме само бинарни отношения, думата "двоичен", като правило, ще бъде пропусната.
Нека се съгласим да обозначаваме отношенията с буквите R, S, T, P и т.н.
Ако R са релации на множеството X, тогава, според дефиницията, R X x X. От друга страна, ако е дадено някакво подмножество от множеството X x X, то дефинира някаква връзка R на множеството X.
Твърдението, че елементите x и y са във връзка R, може да се запише като: (x, y) R или x R y. Последният запис гласи: "Елемент x е във връзка R с елемент y."
Връзките се дефинират по същия начин като съответствията. Връзката може да бъде определена чрез изброяване на двойките елементи от множеството X, които са в тази релация. Формите на представяне на такива двойки могат да бъдат различни - те са подобни на формите на присвояване на съответствия. Разликите са свързани със задаване на връзки с помощта на графика.
Нека построим, например, графика на отношенията "по-малко от", дадени на множеството X= (2, 4, 6, 8). За да направим това, изобразяваме елементите на множеството X като точки (те се наричат върхове на графиката), а релацията „по-малко от“ е представена със стрелка (фиг. 1).
На същото множество X може да се разглежда и друга релация - "умножаване". Графиката на тази връзка ще има цикъл във всеки връх (стрелка, чието начало и край съвпадат), тъй като всяко число е кратно на себе си (фиг. 2).
Връзка може да бъде определена с помощта на клауза с две променливи. Така например са дадени отношенията „по-малко от“ и „множество“, разгледани по-горе, и кратката форма на изреченията „числото x е по-малко от числото y“ и „числото x е кратно на числото y " се използва. Някои от тези изречения могат да бъдат написани с помощта на символи. Например, отношенията „по-малко от“ и „умножават“ могат да бъдат посочени в следната форма: „x<у», «х у». Отношение «х больше у на 3» можно записать в виде равенства х = у + 3 (или х – у = 3).
За отношението R, дадено на множеството X, винаги може да се зададе релацията R -1 , нейната обратна - тя се дефинира по същия начин като съответствието, обратно на дадената. Например, ако R е отношението "x е по-малко от y", тогава отношението "y е по-голямо от x" ще бъде нейното обратно.
Концепцията за връзка, обратна на дадена, често се използва в първоначалното преподаване на математика. Например, за да се предотврати грешка при избора на действие, с което се решава задачата: „Петя има 7 молива, което е с 2 по-малко от Борис. Колко молива има Борис? - ще бъде преформулирано: „Петя има 7 молива, а Боря има още 2. Колко молива има Борис? Виждаме, че преформулирането е сведено до замяна на отношението „по-малко от 2“ с обратното отношение „по-голямо от 2“.
Свойства на връзката
Установихме, че бинарна релация върху множество X е набор от подредени двойки елементи, принадлежащи на декартовото произведение XxX. Това е математическата същност на всяка връзка. Но, както всички други понятия, отношенията имат свойства. Те успяха да се изолират чрез изучаване на различни специфични взаимоотношения. Има много имоти, в нашия курс ще изучаваме само няколко. Помислете за набора от сегменти, показан на фиг. 3, връзката на перпендикулярност, равенство и "по-дълго". Ще построим графики на тези отношения (фиг. 4) и ще ги сравним.
Виждаме, че графиката на релациите на равенството се различава от другите две по наличието на цикли във всеки от своите върхове. Тези цикли са резултат от факта, че отношението на равни отсечки има свойството всеки сегмент да е равен на себе си. За отношението на равенство се казва, че има свойството рефлексивност или просто какво е то рефлексивно .
Определение. За релация R върху множество X се казва, че е рефлексивна, ако всеки елемент от множеството X може да се каже, че е във връзка с R със себе си.
R рефлексивно върху X<=>xRx за всяко x X
Ако отношението R е рефлексивно върху множеството X, тогава във всеки връх на графика на тази връзка има цикъл. Обратното твърдение също е вярно: граф, всеки връх на който има цикъл, дефинира отношения, които имат свойството на рефлексивност.
Примери за рефлексивни връзки:
Отношението е "кратно" на множеството естествени числа (всяко естествено число е кратно на себе си);
Отношение на подобие на триъгълници (всеки триъгълник е подобен на себе си).
Има отношения, които нямат свойството на рефлексивност. Такова, например, е отношението на перпендикулярност на множество отсечки: няма нито един сегмент, за който може да се каже, че е перпендикулярен на себе си. Следователно на графиката на отношението на перпендикулярността няма нито един цикъл (фиг. 4). Той няма свойството на рефлексивност и съотношението е "по-дълго" за сегменти.
Нека сега обърнем внимание на графиките на перпендикулярност и равенство на отсечките. Те са "подобни" по това, че ако има една стрелка, свързваща двойка елементи, тогава трябва да има друга, свързваща същите елементи, но вървяща в обратна посока. Тази характеристика на графиката отразява свойствата, които имат отношенията на паралелизъм и равенство на сегментите:
Ако един сегмент е перпендикулярен на друг сегмент, тогава този "друг" е перпендикулярен на първия;
Ако един сегмент е равен на друг сегмент, тогава този „друг“ е равен на първия.
За връзката на перпендикулярност и равенство на сегментите те казват, че имат свойството на симетрия или са просто симетрични.
Определение. Връзката R върху множество X се казва, че е симетрична, ако е изпълнено следното условие: от факта, че елемент x е във връзка R с елемент y, следва, че елемент y също е във връзка R с елемент x.
Използвайки символи, тази връзка може да бъде написана, както следва:
R е симетричен на X<=>(xRy => yRx)
Графиката на симетрична връзка има особеността, че наред с всяка стрелка, която върви от x до y, графиката съдържа и стрелка, движеща се от y до x. Обратното също е вярно. Графика, съдържаща, заедно с всяка стрелка, движеща се от x до y, и стрелка, водеща от y до x, е график на симетрична връзка.
В допълнение към двата разгледани примера за симетрични отношения, ние добавяме следното:
Отношението на паралелизъм върху множеството от прави (ако правата x е успоредна на правата y, тогава правата y също е успоредна на правата x);
Отношение на подобие на триъгълници (ако триъгълник F е подобен на триъгълник P, тогава триъгълник P е подобен на триъгълник F).
Има отношения, които нямат свойството на симетрия. Такава, например, е релацията "по-дълго" на множеството от сегменти. Наистина, ако отсечката x е по-дълга от отсечката y, тогава отсечката y не може да бъде по-дълга от отсечката x. За връзката "по-дълго" казват, че тя има свойството на антисиметрия или просто антисиметрична.
Определение. Връзката R върху множество X се нарича антисиметрична, ако за различни елементи x и y от множеството X е изпълнено следното условие: от факта, че x е във връзка R с елемент y, следва, че елемент y не е в връзка R с елемент x .
антисиметрично на X<=>(xRy и x≠y => )
Графа на антисиметрична връзка има особеност: ако два върха на графа са свързани със стрелка, тогава тази стрелка е само една. Обратното твърдение също е вярно: граф, чиито върхове са свързани само с една стрелка, е графика на антисиметрична връзка.
В допълнение към „по-дългата“ връзка на множеството от сегменти, например, следните притежават свойството на антисиметрия:
Връзката "по-голямо от" за числа (ако x е по-голямо от y, тогава y не може да бъде по-голямо от x);
Съотношението "по-голямо от 2" за числа (ако x е по-голямо от y с 2, тогава y не може да бъде с 2 по-голямо от x).
Има отношения, които нямат нито свойството на симетрия, нито свойството на антисиметрия. Помислете например за връзката „да бъдеш сестра“ на снимачната площадка на деца от едно и също семейство. Нека в семейството има три деца: Катя, Маша и Толя. Тогава графиката на релацията "да бъдеш сестра" ще бъде като на фигура 5. От нея се вижда, че тази връзка няма нито свойството на симетрия, нито свойството на антисиметрия.
Нека отново обърнем внимание на една особеност на графика на релациите "по-дълго" (фиг. 4). На него можете да видите: ако стрелките са нарисувани от дДа се аи от аДа се С, тоест стрелка от дДа се С; ако стрелките са от дДа се би от бДа се С, тоест стрелка и от дДа се Си т.н. Тази характеристика на графиката отразява важно свойство на „по-дългата“ връзка: ако първият сегмент е по-дълъг от втория, а вторият е по-дълъг от третия, тогава първият е по-дълъг от третия. За тази връзка се казва, че има свойството на транзитивност или просто транзитивност.
Определение. Връзката R върху множество X се нарича транзитивна, ако е изпълнено следното условие: от факта, че елемент x е във връзка R с елемент y и елемент y е във връзка R с елемент z, следва, че елемент x е в релация R с елемент z.
Използвайки символи, тази дефиниция може да бъде написана, както следва:
R е транзитивен на X<=>(xRy и yRz => xRz)
Графика на преходна връзка с всяка двойка стрелки, тръгваща от хДа се ви вДа се z, съдържа стрелка, водеща от хДа се z. Обратното също е вярно.
В допълнение към отношението „по-дълго“ на множеството от сегменти, отношението на равенството има свойството на транзитивност: ако сегментът хравно на отсечката ви сегмент вравно на отсечката z, след това сегментът хравно на отсечката z. Това свойство е отразено и в графиката на отношенията на равенство (фиг. 4)
Има отношения, които нямат свойството на преходност. Такава връзка е например отношението на перпендикулярност: ако отсечката a е перпендикулярна на отсечка d, а отсечката d е перпендикулярна на отсечка b, тогава отсечките a и b не са перпендикулярни!
Помислете за друго свойство на отношенията, което се нарича свързано свойство, а отношение, което го притежава, се нарича свързано.
Определение. Връзка R върху множество X се нарича свързана, ако за някои елементи x и y от множеството X е изпълнено следното условие: тъй като x и y са различни, следва, че или x е във връзка R с елемент y, или елемент y е във връзка R с елемент x.
Използвайки символи, тази дефиниция може да бъде написана, както следва:
R е свързан на множеството X<=>(x≠y xRy или yRx)
Например, отношението "по-голямо от" за естествени числа има свойството да бъде свързано: за всякакви различни числа x и y може да се каже, че или x > y, или y > x.
В релационна графика всеки два върха са свързани със стрелка. Обратното също е вярно.
Има отношения, които нямат свойството да бъдат свързани. Такава връзка, например, е отношението на делимост на множеството от естествени числа: такива числа могат да бъдат наречени xny такива, че нито числото x е делител на числото y, нито числото y е делител на числото x .
Избраните свойства ни позволяват да анализираме различни отношения от обща гледна точка - наличието (или отсъствието) на определени свойства в тях.
И така, ако обобщим всичко казано за отношението на равенство, дадено върху множеството от сегменти (фиг. 4), тогава се оказва, че то е рефлексивно, симетрично и преходно. Връзката „по-дълго“ на един и същ набор от сегменти е антисиметрична и транзитивна, докато перпендикулярността е симетрична, но няма свойствата на рефлексивност и транзитивност. Всички тези отношения върху даден набор
сегментите не са свързани.
Задача 1. Формулирайте свойствата на отношението R, дадено от графиката (фиг. 6).
Решение. Отношението R- е антисиметрично, тъй като върховете на графа са свързани само с една стрелка.
Отношението R е преходно, тъй като с двойка стрелки, идващи от бДа се аи от аДа се С, на графиката има стрелка, която върви от бДа се С.
Връзката R е свързана, тъй като всеки два върха са свързани със стрелка.
Връзката R няма свойството на рефлексивност, тъй като в графа има върхове, в които няма цикли.
Задача 2. Формулирайте свойствата на отношението "по-голямо от 2 пъти", дадено върху множеството от естествени числа.
Решение. „Повече от 2 пъти“ е кратка форма на връзката „броят на x е по-голям от броя на y е 2 пъти“. Това отношение е антисиметрично, тъй като условието е изпълнено: от факта, че числото x е 2 пъти по-голямо от числото y, следва, че числото y не е по-голямо от числото x с 2 пъти.
Тази връзка няма свойството на рефлексивност, тъй като за никое число не може да се каже, че е два пъти по-голямо от себе си.
Даденото отношение не е транзитивно, тъй като от факта, че числото хповече брой вс 2, а числото y е по-голямо от числото zс 2, следва, че числото хне може да бъде повече от число zна 2.
Това отношение върху множеството от естествени числа няма свойството на свързаност, тъй като има двойки числа x и y такива, че нито числото е два пъти по-голямо от y, нито числото y е два пъти по-голямо от x. Например, това са числата 7 и 3,5 и 8 и т.н.
Основи на дискретната математика.
Концепцията за комплект. Връзка между множества.
Множество е съвкупност от обекти, които притежават определено свойство, обединени в едно цяло.
Обектите, които съставляват множество, се наричат елементикомплекти. За да може определен набор от обекти да бъде наречен набор, трябва да са изпълнени следните условия:
· Трябва да има правило, чрез което е моно да се определи дали даден елемент принадлежи към дадена колекция.
· Трябва да има правило, чрез което елементите могат да бъдат разграничени един от друг.
Множествата се обозначават с главни букви, а неговите елементи с малки букви. Начини за определяне на набори:
· Изброяване на множество елементи. - за крайни множества.
Посочване на характерно свойство 
.
празен комплект- се нарича множество, което не съдържа никакъв елемент (Ø).
Две множества се наричат равни, ако се състоят от едни и същи елементи. , A=B
Няколко Бнаречено подмножество на множеството А( , ако и само ако всички елементи от множеството Бпринадлежат към комплекта А.
Например: , Б =>
Имот:
Забележка: обикновено се разглежда подмножество от същия набор, което се нарича универсален(u). Универсалният комплект съдържа всички елементи.
Операции върху множества.
| А |
| Б |
2.пресичане 2 комплекта е нов набор, състоящ се от елементи, които едновременно принадлежат както на първия, така и на втория набор.
№: , ,
Собственост: операции на обединение и пресичане.
· Комутативност. 
Асоциативност. ;
· Разпределителен. ;
| У |
Бинарни отношения и техните свойства.
Позволявам Аи Vтова са набори от производно естество, разгледайте подредена двойка елементи (а, в) a ϵ A, c ϵ Bпоръчани "енкс" могат да бъдат разгледани.
(a 1, a 2, a 3,...a n), където а 1 ϵ A 1; а 2 ϵ A 2; …; ан ϵ A 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 Антирефлексивна антисиметрична транзитивна релация се нарича строга редовна връзка.
