Транзитивность
Перейти к навигации
Перейти к поиску
Транзитивность — свойство бинарного отношения. Бинарное отношение на множестве называется транзитивным, если для любых трёх элементов множества выполнение отношений и влечёт выполнение отношения (запись означает отношение к , — к , — к ).
Формально, отношение транзитивно, если
Примеры
[править | править код]- Равенство: и , значит .
- Отношение порядка: и , значит или нестрогого порядка: и , значит .
- Параллельность прямых: и , значит .
- Импликация: и , значит .
- Эквивалентность: и , значит .
- Включение подмножества: если является подмножеством , и в свою очередь является подмножеством , тогда является подмножеством .
- Делимость: если делится на , и делится на , тогда делится на .
- Сравнение чисел по модулю: два числа, сравнимые с третьим числом по одному и тому же модулю, сравнимы между собой.
- Отношение следования вершин ориентированного графа: если вершина достижима из вершины , а вершина , в свою очередь, — из , то достижима из .
Примеры отсутствия транзитивности (встречаются, когда логические высказывания связаны не арифметическими отношениями или их эквивалентами в языке, а другими смысловыми отношениями):
- Игра «Камень, ножницы, бумага»: Камень сильнее Ножниц; Ножницы «сильнее» Бумаги; однако Камень не «сильнее» Бумаги (). Здесь «сильнее» не имеет буквального значения, поскольку сила Бумаги в том, что она просто обёртывает Камень.
- В круговом турнире часто бывает ситуация, когда команда победила команду , команда — команду , а команда победила команду . Следовательно, в таком турнире отношение «победа» является нетранзитивным и не имеет эквивалента арифметической операции или арифметического отношения.
- Отношение связи вершин граф-схемы алгоритма: например, если в граф-схеме алгоритма имеет место альтернативное ветвление, начинающееся условной вершиной , и две вершины и , входящие в состав различных альтернативных ветвей ветвления, то вершина связана с , связана с , однако вершины и не связаны (они либо параллельны, либо альтернативны).
- Отношение параллельности вершин параллельной граф-схемы алгоритма: например, если в составе параллельного фрагмента алгоритма в одной из ветвей находится вершина , а другая представлена альтернативным ветвлением с двумя ветвями, одна из которых содержит вершину , а другая — , то вершины и находятся в отношении параллельности, также как и вершины и , однако вершины и не параллельны (они находятся в отношении альтернативы).
- Отношение альтернативы вершин граф-схемы алгоритма: например, если в составе альтернативного фрагмента алгоритма одна из ветвей представлена вершиной , а другая включает последовательно выполняемые вершины и , то вершины и находятся в отношении альтернативы, что справедливо и для вершин и , однако вершины и не состоят в отношении альтернативы (они состоят в отношениях следования и связи).
См. также
[править | править код]В статье не хватает ссылок на источники (см. рекомендации по поиску). |