Русская Википедия:Транзитивность
Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску
Шаблон:Значения Транзитивность — свойство бинарного отношения. Бинарное отношение <math>R</math> на множестве <math>X</math> называется транзитивным, если для любых трёх элементов множества <math>a, b, c</math> выполнение отношений <math>a R b</math> и <math>b R c</math> влечёт выполнение отношения <math>a R c</math> (запись <math>a R b</math> означает отношение <math>a</math> к <math>b</math>, <math>b R c</math> — <math>b</math> к <math>c</math>, <math>a R c</math> — <math>a</math> к <math>c</math>).
Формально, отношение <math>R</math> транзитивно, если
- <math>\forall a, b, c \in X,\ a R b \land b R c \Rightarrow a R c.</math>
Примеры
- Равенство: <math>a=b</math> и <math>b=c</math>, значит <math>a=c</math>.
- Отношение порядка: <math>a>b</math> и <math>b>c</math>, значит <math>a>c</math> или нестрогого порядка: <math>a \geqslant b</math> и <math>b \geqslant c</math>, значит <math>a \geqslant c</math>.
- Параллельность прямых: <math>a||b</math> и <math>b||c</math>, значит <math>a||c</math> (см. примечание к «равенству чисел»).
- Импликация: <math>a \Rightarrow b</math> и <math>b \Rightarrow c</math>, значит <math>a \Rightarrow c</math>.
- Эквивалентность: <math>a \Leftrightarrow b</math> и <math>b \Leftrightarrow c</math>, значит <math>a \Leftrightarrow c</math> (см. примечание к «равенству чисел»).
- Включение подмножества: если <math>b</math> является подмножеством <math>a</math>, и в свою очередь <math>c</math> является подмножеством <math>b</math>, тогда <math>c</math> является подмножеством <math>a</math>.
- Делимость: если <math>a</math> делится на <math>b</math>, и <math>b</math> делится на <math>c</math>, тогда <math>a</math> делится на <math>c</math>.
- Сравнение чисел по модулю: два числа, сравнимые с третьим числом по одному и тому же модулю, сравнимы между собой.
- Отношение следования вершин ориентированного графа: если вершина <math>a</math> достижима из вершины <math>b</math>, а вершина <math>b</math>, в свою очередь, — из <math>c</math>, то <math>a</math> достижима из <math>c</math>.
Примеры отсутствия транзитивности (встречаются, когда логические высказывания связаны не арифметическими отношениями или их эквивалентами в языке, а другими смысловыми отношениями):
- Игра «Камень, ножницы, бумага»: Камень сильнее Ножниц; Ножницы сильнее Бумаги; однако Камень не сильнее Бумаги (<math>t R s \land s R p \nRightarrow t R p</math>). Здесь "сильнее" не имеет буквального значения, поскольку "сила" Бумаги в том, что она просто обёртывает Камень.
- В круговом турнире часто бывает ситуация, когда команда <math>A</math> победила команду <math>B</math>, команда <math>B</math> — команду <math>C</math>, а команда <math>C</math> победила команду <math>A</math>. Следовательно, в таком турнире отношение «победа» является нетранзитивным и не имеет эквивалента арифметической операции или арифметического отношения.
- Отношение связи вершин граф-схемы алгоритма: например, если в граф-схеме алгоритма имеет место альтернативное ветвление, начинающееся условной вершиной <math>a^{\psi}</math>, и две вершины <math>a_1</math> и <math>a_2</math>, входящие в состав различных альтернативных ветвей ветвления, то вершина <math>a_1</math> связана с <math>a^{\psi}</math>, <math>a^{\psi}</math> связана с <math>a_2</math>, однако вершины <math>a_1</math> и <math>a_2</math> не связаны (они либо параллельны, либо альтернативны).
- Отношение параллельности вершин параллельной граф-схемы алгоритма: например, если в составе параллельного фрагмента алгоритма в одной из ветвей находится вершина <math>a_1</math>, а другая представлена альтернативным ветвлением с двумя ветвями, одна из которых содержит вершину <math>a_2</math>, а другая — <math>a_3</math>, то вершины <math>a_2</math> и <math>a_1</math> находятся в отношении параллельности, также как и вершины <math>a_1</math> и <math>a_3</math>, однако вершины <math>a_2</math> и <math>a_3</math> не параллельны (они находятся в отношении альтернативы).
- Отношение альтернативы вершин граф-схемы алгоритма: например, если в составе альтернативного фрагмента алгоритма одна из ветвей представлена вершиной <math>a_1</math>, а другая включает последовательно выполняемые вершины <math>a_2</math> и <math>a_3</math>, то вершины <math>a_2</math> и <math>a_1</math> находятся в отношении альтернативы, что справедливо и для вершин <math>a_1</math> и <math>a_3</math>, однако вершины <math>a_2</math> и <math>a_3</math> не состоят в отношении альтернативы (они состоят в отношениях следования и связи).
См. также
