Свойства на бинарните отношения - Студиопедия
1. Рефлексивност. Отношението R се наричарефлексивноако (х, x)нR за всяко xнA. Примери за рефлексивни отношения: отношения "³", "£" върху множеството R.
2. Антирефлексивност. Отношение R се наричаантирефлексивно, ако (x, x)ÏR за всеки xОA. Примери за антирефлексивни отношения: отношения " " върху множеството R.
Ако R е антирефлексивна релация, тогава xÏGR(x) и xÏHR(x) за всяко xОA .
3. Симетрия. Отношение R се наричасиметрично, ако за всяко x, yОA фактът, че (x, y)ОR предполага (y, x)ОR и обратно. Примери за симетрични връзки: връзки "=" и "¹".
Ако отношението R е симетрично, то за всяко xОA
4. Антисиметрия. Отношение R се наричаантисиметрично, ако за всяко x и y от A следва от едновременното изпълнение на условия (x, y)нR и (y, x)нR, че x = y. Пример за антисиметрична връзка. Нека A е множеството от хора в опашката. Отношението R - "не заставай зад някого в опашката" ще бъде антисиметрично.
Нека x = Вася и y = ИВАНОВ. Фактът, че (x, y)ÎR означава, че "ВАСЯ не е на линия за ИВАНОВ", (y, x)ÎR означава "ИВАНОВ не е зад Вася". Очевидно и двете включвания могат да се извършат едновременно само ако ВАСЯ е ИВАНОВ, т.е. x = y.
Отношението "³" също е антисиметрично: ако x ³ y и y ³ x, тогава x = y.
5. Асиметрия. Отношението Rе асиметрично, ако R Ç R -1 = Æ, т.е. пресечната точка на връзката R с обратната връзка е празна.
Еквивалентна дефиниция на асиметрия: от двете отношения (x, y) О R и (y, x) ОR едното не е изпълнено.
Примери за асиметрични релации: ">", " s = R ÇR –1 иасиметрична частна релацията R a = R \ R s. Ако релацията Rсиметрично, тогава R= R s , ако връзката R е асиметрична, тогава R = R a .
Примери. Ако R е "³", тогава R -1 е "s - "=", Ra е ">".
6. Преходност. Отношението Rе транзитивно, ако за всяко x, y, zнA фактът, че (x, y)нR и (y, z)нR предполага (x, z)нR.
Свойства на транзитивна релация:
б) за всяко xОA от yОGR(x) следва, че GR(y) Î GR(x).
Релацията "¹" не е транзитивна. Нека x = 2, y = 3, z = 2, тогава x ¹ y и y ¹ z, но x = z, т.е. (x, z)R.
Отношението R1 се нарича транзитивно по отношение на отношението R2, ако:
а) от (x, y)Î R1 и (y, x)Î R2 следва, че (x, z)Î R1;
б) от (x, y)Î R2 и (y, x)Î R1 следва, че (x, z)Î R1.
7. Отрицателно-транзитивно. Отношение R се наричаотрицателно-транзитивно, ако R е транзитивно.
Примери. Отношения R1 – ">" и R2 –" ¹" са отрицателни, тъй като отношенията `R1 - "£",`R2 - "=" са транзитивни. Възможно е едновременното изпълнение на свойствата на транзитивност и негативност. Например отношението R1 е както транзитивно, така и отрицателно, докато R2 е известно, че е нетранзитивно.
8. Пълнота. Отношението Rе пълноако за всяко x, yнА или (x, y)нR или (y, x)нR, или и двете отношения са изпълнени едновременно.
Пълни свойства на връзката:
а) GR(x) È HR(x) = A за всяко xОA;
б) пълното отношение е рефлексивно.
9. Слаба пълнота. Отношение R се наричаслабо пълно, ако за всяко x ¹ y от A или (x, y)®R, или (y, x)®R.
Пример за слабо пълна връзка. Нека A е набор от предприятия, които са "неблагоприятни" по отношение на своя бюджет. Отношението R "да дължим" е слабо пълно, тъй като всяко от тези предприятия или дължи на някого, или някой му дължи, но дължи(x, x)ПR също е невъзможно само по себе си.
10. Ацикличност. Бинарна връзка Rе ацикличнаако R n ÇR –1 = Æ за всяко nнN. С други думи, ако от всяка крайна верига от отношения x1Rx2, x2Rx3. xn-1Rxn предполага, че x1 ¹ xn, тогава отношението R е ациклично.
Не намерихте това, което търсихте? Използвайте търсачката:
Деактивирайте adBlock! и обновете страницата (F5)наистина е необходимо