Основное содержание

Информатика

Course: Информатика > Модуль 2

Урок 5: Модульная арифметика

Отношения эквивалентности

Классная комната Google

Отношения эквивалентности

Прежде всего важно понимать, что следующие выражения эквивалентны

A, \equiv, B, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis
A, start text, space, m, o, d, space, end text, C, equals, B, start text, space, m, o, d, space, end text, C
C, space, vertical bar, space, left parenthesis, A, minus, B, right parenthesis (Символ | означает «делит», то есть является делителем)
A, equals, B, plus, K, dot, C (здесь K — это некое целое число)

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

Например, следующие выражения эквивалентны:

13, \equiv, 23, space, left parenthesis, start text, m, o, d, space, end text, 5, right parenthesis
13, start text, space, m, o, d, space, end text, 5, equals, 23, start text, space, m, o, d, space, end text, 5
- 5, space, vertical bar, space, left parenthesis, 13, minus, 23, right parenthesis, left parenthesis, 5, space, vertical bar, space, minus, 10 верно, поскольку 5, times, left parenthesis, minus, 2, right parenthesis, equals, minus, 10, right parenthesis
13, equals, 23, plus, K, dot, 5. Для этого подойдёт K, equals, minus, 2: 13, equals, 23, plus, left parenthesis, minus, 2, right parenthesis, times, 5

Сравнение по модулю — это отношение эквивалентности

Убедитесь, что секторы из предыдущего примера обладают следующими свойствами.

Все значения в одном секторе попарно связаны друг с другом.
Каждое значение встречается не более чем в одном секторе (секторы взаимно непересекаются).
Если собрать вместе все секторы, получится «пирог» из всех возможных целых чисел.

Пирог, куски которого обладают этими свойствами, называется отношением эквивалентности.
Отношение эквивалентности определяет, как именно следует разрезать наш пирог (то есть как мы разобъём множество всех значений) на куски (классы эквивалентности).

В общем случае, отношение эквивалентности задаётся следующими тремя свойствами.

Пирог — это все интересующие нас значения
Кусок (или сектор) пирога — класс эквивалентности
Принцип разрезания пирога на куски — соотношение эквивалентности

В частности, для предыдущего примера:

Пирог — множество всех целых чисел
Кусок пирога с пометкой B — это класс эквивалентности, в котором все значения start text, m, o, d, space, end text, C, equals, B
Принцип разрезания пирога на куски — отношение сравнения по модулю C, то есть \equiv, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis

Именно поэтому сравнение по модулю C — это отношение эквивалентности. Оно разделяет множество целых чисел на C различных классов эквивалентности.

Почему нам так важно, что сравнение по модулю C — это отношение эквивалентности?

Выяснив, что сравнение по модулю C — это отношение эквивалентности, давайте разберём несколько присущих ему свойств.
Отношения эквивалентности — это отношения, обладающих следующими свойствами.

Они рефлексивны, то есть A эквивалентно A.
Они симметричны, то есть если A эквивалентно B, то B эквивалентно A.
Они транзитивны, то есть если A эквивалентно B, а B эквивалентно C, то A эквивалентно C.

Поскольку сравнение по модулю C — это отношение эквивалентности, следовательно:

A, \equiv, A, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis
Если A, \equiv, B, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis, тогда B, \equiv, A, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis
Если A, \equiv, B, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis и B, \equiv, D, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis, тогда A, \equiv, D, space, left parenthesis, start text, m, o, d, space, end text, C, right parenthesis

Пример

Рассмотрим эти свойства на конкретном примере — сравнения по start text, m, o, d, space, end text, 5.

3, \equiv, 3, space, left parenthesis, start text, m, o, d, space, end text, 5, right parenthesis (свойство рефлексивности).
Если 3, \equiv, 8, space, left parenthesis, start text, m, o, d, space, end text, 5, right parenthesis, то 8, \equiv, 3, space, left parenthesis, start text, m, o, d, space, end text, 5, right parenthesis (свойство симметричности).
Если 3, \equiv, 8, space, left parenthesis, start text, m, o, d, space, end text, 5, right parenthesis и 8, \equiv, 18, space, left parenthesis, start text, m, o, d, space, end text, 5, right parenthesis, то 3, \equiv, 18, space, left parenthesis, start text, m, o, d, space, end text, 5, right parenthesis (свойство транзитивности).

Хотите присоединиться к обсуждению?

Войти

Сортировать по:

Пока нет ни одной записи.

Знаете английский? Нажмите здесь, чтобы увидеть обсуждение, которое происходит на английской версии сайта.