Свойства бинарных отношений

1. Отношение R называется рефлексивным, если для любого имеет место aRa.

Отношение антирефлексивно, если ни для какого не выполняется aRa.

2. Отношение R симметрично, если из aRa следует bRa. В противном случае отношение R несимметрично, т.е. если aRb истинно, то bRa – ложно.

3. Отношение R транзитивно, если для любых a, b, c из aRb и bRc следует aRc, в противном случае отношение антитранзитивно, например, если , то еще не следует, что .

Бинарное отношение R называется отношением эквивалентности, если оно одновременно рефлексивно, симметрично, транзитивно.

Например, отношение равенства х = y является эквивалентностью на любом множестве А, так как оно рефлексивно (x = x), симметрично и транзитивно .

Пусть E – эквивалентность на множестве А. Классом эквивалентности элемента называется множество .

Множество А \ Е называется фактор - множествоммножества А по отношению Е.

Например, для отношения принадлежности к одной студенческой группе классов эквивалентности является множество студентов одной группы.

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

Например, если а – множество студентов Академии, то разбиением этого множества является совокупность студенческих групп или совокупность потоков.

Отношение эквивалентности является обобщением отношения равенства: эквивалентные элементы считаются “равными”.

Обобщением обычного отношения служат отношения порядка.

Отношение R называется отношением порядка на множестве А, если оно обладает свойствами антисимметричности и транзитивности.

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

Отношение строгого порядка ( ) рефлексивно, антисимметрично и транзитивно.

Отношение строгого порядка ( ) антирефлексивно, антисимметрично и транзитивно.

Пример:Из 100 студентов английский язык изучают 28 студентов, немецкий – 30, французский – 42, английский и немецкий – 8, английский и французский – 10, немецкий и французский – 5, все три языка – 3 студента.

Сколько студентов не изучает ни одного языка и сколько студентов изучают только один язык?

Решение:Пусть А, Н, обозначают соответственно множества студентов, изучающих английский, немецкий и французский языки. Тогда N(A), N(H), N( )- число студентов, изучающих английский, немецкий и французский языки. Обозначим через Е множество рассматриваемых студентов. Тогда N(Е) есть число всех студентов (рис.10).

Рис.10.

есть множество студентов, изучающих английский, немецкий и французский языки. есть множество студентов, которые не изучают ни одного языка.

есть множество студентов, изучающих только один язык. На рис.11 и 12 названные множества выполнены штриховкой.

Теперь запишем условия примера:

N(E) = 100, N(A) = 28, N(H) = 30, N( ) = 42, N( )= 8, N( ) = 10, N( ) = 5, N( ) = 3.

Рис. 11. Рис.12.

Найти: , Для вычисления числа элементов используем формулу -

+

+

Для нашего случая:

Таким образом, число студентов, не изучающих ни одного языка, равна 20.

Тогда,

=80-17=63.

Число студентов, изучающих только один язык, равно 63.

Примечание:При преобразовании были использованы свойства коммутативности и ассоциативности пересечения множеств. Например:

.