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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

В математике бинарное отношение R на множестве X называется транзитивным, если для любых трёх элементов множества a, b, c выполнение отношений a R b и b R c влечёт выполнение отношения a R c. Формально, отношение R транзитивно, если \forall a, b, c \in X,\ a R b \land b R c \Rightarrow a R c.

Примеры[править | править исходный текст]

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

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

  • Игра «Камень, ножницы, бумага»: Камень сильнее Ножниц; Ножницы сильнее Бумаги; однако Камень не сильнее Бумаги (t R s \land s R p \nRightarrow t R p). Здесь "сильнее" не имеет буквального значения, поскольку "сила" Бумаги в том, что она просто обертывает Камень.
  • В круговом турнире часто бывает ситуация, когда команда A победила команду B, команда B — команду C, а команда C победила команду A. Следовательно, в таком турнире отношение «победа» является нетранзитивным и не имеет эквивалента арифметической операции или арифметического отношения.
  • Отношение связи вершин граф-схемы алгоритма: например, если в граф-схеме алгоритма имеет место альтернативное ветвление, начинающееся условной вершиной a^{\psi}, и две вершины a_1 и a_2, входящие в состав различных альтернативных ветвей ветвления, то вершина a_1 связана с a^{\psi}, a^{\psi} связана с a_2, однако вершины a_1 и a_2 не связаны (они либо параллельны, либо альтернативны).
  • Отношение параллельности вершин параллельной граф-схемы алгоритма: например, если в составе параллельного фрагмента алгоритма в одной из ветвей находится вершина a_1, а другая представлена альтернативным ветвлением с двумя ветвями, одна из которых содержит вершину a_2, а другая — a_3, то вершины a_2 и a_1 находятся в отношении параллельности, также как и вершины a_1 и a_3, однако вершины a_2 и a_3 не параллельны (они находятся в отношении альтернативы).
  • Отношение альтернативы вершин граф-схемы алгоритма: например, если в составе альтернативного фрагмента алгоритма одна из ветвей представлена вершиной a_1, а другая включает последовательно выполняемые вершины a_2 и a_3, то вершины a_2 и a_1 находятся в отношении альтернативы, что справедливо и для вершин a_1 и a_3, однако вершины a_2 и a_3 не состоят в отношении альтернативы (они состоят в отношениях следования и связи).

См. также[править | править исходный текст]