Открыть главное меню

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

Транзитивность — свойство бинарного отношения. Бинарное отношение на множестве называется транзитивным, если для любых трёх элементов множества выполнение отношений и влечёт выполнение отношения .

Формально, отношение транзитивно, если

.

ПримерыПравить

  • Равенство:   и  , значит   (на самом деле, отношение равенства вместе с отношением эквивалентности и параллельности прямых обладает более сильным свойством также ещё и «равенства третьему» по причине своей симметричности)
  • Отношение порядка:   и  , значит   или нестрогого порядка:   и  , значит  
  • Параллельность прямых:   и  , значит   (см. примечание к «равенству чисел»)
  • Импликация:   и  , значит  
  • Эквивалентность:   и  , значит   (см. примечание к «равенству чисел»)
  • Включение подмножества: если   является подмножеством  , и в свою очередь   является подмножеством  , тогда   является подмножеством  
  • Делимость: если   делится на  , и   делится на  , тогда   делится на  .
  • Отношение следования вершин ориентированного графа: если вершина   достижима из вершины  , а вершина  , в свою очередь, — из  , то   достижима из  .

Примеры отсутствия транзитивности (встречаются, когда логические высказывания связаны не арифметическими отношениями или их эквивалентами в языке, а другими смысловыми отношениями):

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

См. такжеПравить