Понедельник, Июль 5th, 2010

МЛОИ

Понятия декартового произведения и отношения играет важную роль в теории и практике баз данных и баз знаний, поэтому мы сочли необходимым остановиться здесь на этом понятии. Понадобится оно нам и в последующих разделах нашего курса.
Из бинарных отношений особый интерес представляют отношения, называемые отношениями эквивалентности.
Прежде, чем дать определение отношению эквивалентности, рассмотрим некоторые свойства бинарных отношений.
Пусть имеется бинарное отношение R(X,Y), являющееся подмножеством декартового произведения X?Y множеств X и Y. (Множества X и Y могут совпадать, хотя и не обязательно). Элементы x?X и y?Y будем считать находящимися в отношении R, если пара ?R.
Бинарное отношение R(X,Y) будем называть рефлексивным, если пара ?R.
Бинарное отношение R(X,Y) будем называть симметричным, если из того, что ?R следует ?R
Бинарное отношение R(X,Y) будем называть транзитивным, если из того, что ?R и ?R следует, что ?R.

Бинарное отношение, являющееся одновременно рефлексивным, симметричным и транзитивным, называется отношением эквивалентности.
Например, отношение параллельности прямых на плоскости является отношением эквивалентности, так как оно:
рефлексивно (каждая прямая x параллельна сама себе);
симметрично (если прямая x параллельна прямой y, то и прямая y параллельная прямой x);
транзитивно (если прямая x параллельна прямой y, а прямая y параллельна прямой z, то прямая x параллельна прямой z).

Отношение перпендикулярности прямых на плоскости не является отношением эквивалентности: оно симметрично, но не рефлексивно и не транзитивно.

Рассмотрим бинарное отношение «x — родственник y». Оно, очевидно, транзитивно и симметрично. Если посчитать, что это отношение рефлексивно, то есть имеет место «Я являюсь родственником Я», то оно будет являться отношением эквивалентности.

Отношение эквивалентности R, определенное на множестве Х, разбивает это множество на подмножества (классы) тех объектов, которые находятся между собой в отношении R. Эти подмножества называют классами эквивалентности.
Так отношение «x имеет ту же фамилию, что и y», определенное на множестве всех людей и являющееся (как легко убедиться) отношением эквивалентности, разбивает множество всех людей на классы эквивалентности – подмножества такие, что люди, принадлежащие одному подмножеству, являются однофамильцами, принадлежащие же разным классам — однофамильцами не являются.
Справедливы следующие свойства разбиения множества на классы эквивалентности:
1.Классы эквивалентности между собой не пересекаются.
2.Объединение всех классов эквивалентности, на которое отношение R разбивает множество X, дает множество X.
С другой стороны, любое разбиение множества X на непересекающиеся подмножества задает некоторое отношение эквивалентности R на множестве X.

Разбиение множества на классы эквивалентности потребуется нам в дальнейшем при знакомстве с теорией конечных автоматов.

Страницы: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

Категория: Лекции