Бинарные отношения

Пусть р Ì Х´ Y; если Х = Y, то в этом случае говорят о бинарном отношении между элементами одного множества или об отношении на множестве и пишут p ´ х или р Ì х²

Отношения на множестве X могут обладать следующими свойствами:

1. Говорят, что отношение р обладает свойством рефлексивности, если для любого х из множества Х истинно х р х, другими словами, если каждый элемент х Î Х находится в отношении р с самим собой ("хÎХ)х р х – И.

2. Говорят, что отношение р обладает свойством антирефлексивности если о любом элементе множества х можно сказать, что он не находится в отношении р с самим собой.

("хÎ Х) –И.

3. Говорят, что отношение р обладает свойством симметричности, если для всех элементов х и у из множества Х истинно утвержде­ние: если элемент х находится в отношении р с элементом у, то и элемент у находится в отношении р с элементом х.

("х, уÎ Х)хру ® урх –И.

4. Говорят, что отношение/» обладает свойством антисимметрич­ности, если для всех различных элементов х и у из множества X из того, что элемент х находится в отношении р с элементом у, сле­дует, что элемент у не находится в отношении р с элементом х.

("х, уÎ Х, х ¹ у)х р у® – И.

5. Говорят, что отношение р обладает свойством транзитивности, если для всех элементов х, у, z из множества X истинно утверждение: если элемент х находится в отношении p с элементом у и элемент у находится в отношении р с элементом z, то элемент х находится в отношении р с элементом z.

("х, у,z ÎХ)х р у Ù у р z® х р z – И.

6. Говорят, что отношение р обладает свойством связности, если для любых элементов х и у из множествах Х и х ¹ у, следует, что или х находится в отношении р с у, или у находится в отношении р с х.

("х, уÎХ, х ¹ у)х р у или у р х – И.

Указанные свойства отношений позволяют выделить два вида отношений.

1. Отношение р на множестве X называется отношением эквивалентности, если оно обладает свойствами рефлективности, симметричности и транзитивности.

Имеет место теорема:

Для того чтобы отношение р определяло разбиение множества Х на классы, необходимо и достаточно, чтобы р было отношением эквивалентности.

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

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

Если отношение порядка, заданное на множестве X, обладает свойством связности, то говорят, что оно линейно упорядочивает множество X.

Задача 6.

На множестве Х = {1, 2, 3, 4, 5} задано отношение p, хру х >y

а) задать отношение перечислением пар;

б) построить граф отношения;

в) определить вид отношения.

Решение.

а) а = {(2,1); (3,1); (3,2); (4,1); (4,2); (4,3);(5,1); (5,2); (5,3); (5,4)}

б)

в) Определим, какими свойствами обладает отношение.

1) Сформулируем свойство рефлективности: ("хÎХ)х > х – Л. Получим ложное высказывание, отношение свойством рефлективности не обладает.

Следовательно, Р не является отношением эквивалентности.

2) Проверим далее остальные свойства.

3) Антирефлексивность:("xÎ X) –- истинно, обладает.

4) Симметричность: ("х, у Î Х)х > у ® у > х – ложно, не обладает.

5) Антисимметричность: ("х, уÎХ, х ¹ у) х > у ® – истинно, обладает.

6) Транзитивность: ("х, у, zÎХ), х > у и у > z ® x > z – истинно, обладает.

7) Связность: ("х, уÎХ, х ¹ у) х > у или у > х – истинно, обладает.

Отношение р обладает свойствами антисимметричности и транзитивности, значит, оно отношение порядка, а т.к. оно обладает еще свойствами антирефлексивности и связности, то оно – отношение строгого линейного порядка, и множество X этим отношением линейно упорядочено (5 > 4 > 3 > 2 >1).

Задача 7.

На множестве Х= {х/х Î N, х < 12} задано отношение К – «иметь один и тот же остаток при делении на 4». Объясните, почему отношение К является отношением эквивалентности, и запишите классы разбиения множества, определяемые этим отношением.

Решение. Отношение К является отношением эквивалентности, т.к. оно рефлексивно (можно сказать, что любое число имеет один и тот же остаток при делении на 4 с самим собой), симметрично (если число х имеет один и тот же остаток при делении на 4 с числом у, то и число у имеет один и тот же остаток при делении на 4 с числом х), транзитивно (если число х имеет при делении на 4 тот же остаток, что и число у, а число у имеет при делении на 4 тот же остаток, что и число z, то числа х и z имеют равные остатки при делении на 4).

Как известно, любое отношение эквивалентности, заданное на множестве X, определяет разбиение этого множества на классы таким образом, что в один класс попадают элементы, находящиеся в данном отношении, а в разные классы – не находящиеся в нем. Таким образом, каждый класс будет состоять из чисел, дающих один и тот же остаток при делении на 4. Таких классов 4: {1, 5, 9}, {2, 6, 10}, {3, 7, 11}, {4, 8, 12}.

АЛГЕБРАИЧЕСКИЕ ОПЕРАЦИИ

Определение 10. Алгебраической операцией на множестве Х называется соответствие, при котором каждой паре элементов из множества Х соответствует единственный элемент этого же множества.

Условились алгебраические операции обозначить символами (читается «звездочка») и (читается «кружок»).

Определение алгебраической операции символически можно записать так: - алгебраическая опреация на множестве Х, если (" х, у Î Х) ($! z Î Х) х у= z.

Определение 11. Частичной алгебраической операцией на множестве называется соответствие, при котором некоторым парам элементов из множества Х соответствует единственный элемент того же множества.

Свойства алгебраических операций

1. Алгебраическая операция, заданная на множестве Х, называется ассоциативной (обладает свойством ассоциативности), если для любых элементов х, у, z из множества Х выполняется равенство (х у) z = х (у z).

2. Алгебраическая операция на множестве Х называется коммутативной (обладает свойством коммутативности), если для любых двух элементов х и у из множества выполняется равенство х у = у х.

3. Алгебраическая операция называется дистрибутивной (обладает свойством дистрибутивности) относительно алгебраической операции , если для любых элементов у, х, и z из множества X выполняются равенства:

1 ) (х у) z = (х у) (у z) и 2) х (у z) = (х у) (х z)

4. Алгебраическая операция, заданная на множестве Х, называется сократимой (обладает свойством сократимости), если из условий а х = а у и х а = у а следует, что х = у для любых элементов а, х, у.

Задача 8.

На множестве натуральных чисел, кратных 5, заданы операции: сложение, вычитание. Какие из них являются на этом множестве:

а) алгебраическими;

б) частично алгебраическими?

Решение. Пусть Х – множество натуральных чисел, кратных 5.

Любое натуральное число, кратное 5, имеет вид 5 п, где пÎ N.

Пусть 5 n и 5 m – два натуральных числа из множества Х, n Î N, mÎ N.

Тогда 5n + 5m= 5(n + m), причем (n + m) – сумма двух натуральных чисел, и, значит, число натуральное и единственное. Следовательно, складывая два любых натуральных числа, кратных 5, мы всегда получаем число, кратное 5, и это число единственное. Таким образом сложение на данном множестве Х есть алгебраическая операция.

Рассмотрим вычитание на множестве Х: 5n – 5m = 5(n – m), но n – m существует на множестве натуральных чисел лишь при условии, что n > m, то разность 5n – 5m существует и является числом, кратным 5. Таким образом, вычитание на множестве Х есть частичная алгебраическая операция.

Контрольные вопросы

1. Что называется отношением на множестве А?Приведите примеры отношения на множестве А = {1, 2, 3, 4, 5, 6}.

2. Сформулируйте свойства отношения эквивалентности, приведите примеры.

3. Сформулируйте свойства отношения порядка, отношения строгого линейного порядка, приведите примеры.

4. Какова связь отношения эквивалентности, заданного на множестве, и разбиения множества на классы? Приведите примеры.

5. Сформулировать определение алгебраической операции на множестве Х.

6. Приведите примеры алгебраических операций на множестве целых чисел.

7. Приведите примеры операций, не являющихся алгебраическими на множестве целых чисел.