Примеры отношения эквивалентности

Определение

Определение

Пусть – конечное множество. Отношением на данном множестве будем называть любое подмножество его декартового произведения .

Рассмотрим декартово произведение на себя: . Т.е. это множество всевозможных слов из двух букв в алфавите .

Отношением эквивалентности называется подмножество декартового произведения, которое удовлетворяет следующих трем свойствам:

1. Рефлексивность. .

2. Симметричность. .

3. Транзитивность. .

Пример 1. Рассмотрим в качестве множества X множество натуральных чисел: . Для него рассмотрим обычное равенство натуральных чисел. Скажем, что два натуральных числа эквивалентны, если они равны в обычном смысле. Очевидно, что это есть отношение эквивалентности.

Пример 2. Рассмотрим произвольное натуральное число . Числа x и y назовем эквивалентными , если они дают один и тот же остаток при делении на . Очевидно, что это есть отношение эквивалентности.

Пример 3. Введем отношение эквивалентности на множестве слов, длина которых не меньше числа . Рассмотрим множество этих слов в алфавите . Скажем, что пара слов и эквивалентны, если совпадают их первые букв. Убедитесь сами, что все три свойства эквивалентности выполнены.

Утверждение. Пусть – множество, – отношение эквивалентности на нем. Тогда разбивает все элементы на классы эквивалентных элементов (Любая пара различных классов не пересекается между собой- , и их объединение совпадает с множеством ; ; количество классов может быть бесконечным). Любая пара элементов одного класса эквивалентна, а любая пара элементов различных классов не эквивалентна. Данное разбиение однозначно определяется отношением эквивалентности .

Доказательство данного утвнрждения предлагается в качестве самостоятельного упражнения.

Определение: суперпозицией булевых функции

называется функция

, полученная путем подстановки

функции в функцию вместо некоторой переменной: .

Дата добавления: 2017-01-13