1632
правки
Изменения
м
rollbackEdits.php mass rollback
== Определение ==
[[Определение отношения|Бинарное отношение]] <tex>R</tex> на [[Множества|множестве]] <tex>X</tex> называется ''транзитивным'', если для любых трёх элементов ''<tex>a, b, c'' </tex> из выполнения отношений <tex> aRb </tex> и <tex> bRc </tex> следует выполнение отношения <tex> aRc </tex>.
{{Определение
|definition =
Бинарное отношение <tex>R</tex>, заданное на множестве <tex>X,</tex> называется '''транзитивным'''(англ. ''transitive binary relation''), если для <tex>\forall ~a, b, c \in X\colon ~(aRb)~ \land ~(bRc) \Rightarrow ~(aRc)</tex>.
}}
Если это условие соблюдается не для всех троек ''<tex>a, b, c''</tex>, то такое отношение называется нетранзитивным. Например, не для всех троек <tex> a, b, c \in \mathbb{N} </tex> верно, что <tex>~(a \nmid b)~ \land ~(b \nmid c)~ \Rightarrow ~(a \nmid c) </tex>.
{{Определение
|definition =
Бинарное отношение <tex>R</tex>, заданное на множестве <tex>X,</tex> называется '''нетранзитивным'''(англ. ''intransitive binary relation''), если <tex>\exists ~a, b, c \in X\colon ~(aRb)~ \land ~(bRc)~ \land ~\neg(aRc)</tex>.
}}
Существует более "сильное" свойство {{---}} '''антитранзитивность'''. Под этим термином понимается, что для любых троек ''<tex>a, b, c'' </tex> отсутствует транзитивность. Антитранзитивное отношение, например {{---}} отношение '''победить''' в турнирах «на вылет»: если <tex>A </tex> победил игрока <tex>B</tex>, а <tex>B </tex> победил игрока <tex>C</tex>, то <tex>A </tex> не играл с <tex>C</tex>, следовательно, не мог его победить.
{{Определение
|definition =
Бинарное отношение <tex>R</tex>, заданное на множестве <tex>X,</tex> называется '''антитранзитивным'''(англ. ''antitransitive binary relation''), если для <tex>\forall ~a, b, c \in X\colon ~(aRb)~ \land ~(bRc)~ \Rightarrow ~\neg(aRc)</tex>.
}}
== Свойства ==
* Отношения '''[[Частичный порядок|частичного порядка]]''':
** строгое неравенство <tex>\colon ~(a < b), ~(b < c)~ \Rightarrow ~(~a < c)\;</tex>
** нестрогое неравенство <tex>\colon ~("\le leqslant ")\;</tex>
** '''включение подмножества:'''
*** строгое подмножество <tex>\colon ~ ("\subset ")\;</tex>
*** <tex>(a \,\vdots\, b), ~(b \,\vdots\, c)~ \Rightarrow ~(a \,\vdots\, c)\;</tex>
* '''Равенство''' <tex>\colon ~(a = b), ~(b = c) \Rightarrow ~(a = c)\;</tex>
* '''[[Отношение эквивалентности|Эквивалентность]]''' <tex>\colon ~(a \Leftrightarrow b), ~(b \Leftrightarrow c)~ \Rightarrow ~(a \Leftrightarrow c)\;</tex>
* '''Импликация''' <tex>\colon ~(a \Rightarrow b), ~(b \Rightarrow c)~ \Longrightarrow ~(a \Rightarrow c)\;</tex>
* '''Параллельность''' <tex>\colon ~(a \parallel b), ~(b \parallel c)~ \Rightarrow ~(a \parallel c)\;</tex>
== Примеры нетранзитивных отношений ==
* Пищевая цепочка: это отношение не всегда является транзитивным (пример {{---}} волки едят оленей, олени едят траву, но волки не едят траву).
* ''Быть предпочтительнее чем''. Если мы хотим яблоко вместо апельсина, а вместо яблока мы бы хотели арбуз, то это не значит, что мы предпочтём арбуз апельсину.
* Быть другом.* Являться коллегой по работе.
* Быть подчиненным. Например, во времена феодального строя в Западной Европе была в ходу поговорка: ''Вассал моего вассала {{---}} не мой вассал''.
* Быть похожим на другого человека.
== Примеры антитранзитивных отношений ==
* Быть сыном (отцом, бабушкой).
* Игра "Камень, ножницы, бумага". Камень побеждает ножницы, ножницы выигрывают у бумаги, но камень проигрывает бумаге и т. д.
== См. также ==
* [[Определение_отношения|Определение отношения]]
* [[Транзитивное_замыкание|Транзитивное замыкание]]
* [[Алгоритм_Флойда_—_Уоршалла|Алгоритм Флойда-Уоршалла (построение транзитивного замыкания отношения)]]
* [[Транзитивный_остов|Транзитивный остов]]
* [[Отношение_порядка|Отношение порядка]]
* [[Отношение_эквивалентности|Отношение эквивалентности]]
== Источники информации ==
* [http[wikipedia://en.wikipedia.org/wiki/Transitive_relation | Wikipedia | {{---}} Transitive relation]]* [http[wikipedia://en.wikipedia.org/wiki/Intransitivity | Wikipedia | {{---}} Intransivity]]* [http[wikipedia://ru.wikipedia.org/wiki/:Отношение_эквивалентности | Wikipedia | {{---}} Отношение эквивалентности]]
* [http://golovolomka.hobby.ru/books/gardner/gotcha/ch5/11.html Парадокс Кондорсе]
* [http://sarodom.ru/Statyi/002.htm Отношения на графах]
* [http://www.hse.ru/data/2010/11/21/1209059687/intr.doc Развитие понимания транзитивности и нетранзитивности]
* [http://www.smolensk.ru/user/sgma/MMORPH/N-3-html/1.htm Бинарные отношения. Отношения эквивалентности] (очень хорошая статья про отношения, в ней суть раскрыта более полноподробно)
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Отношения]]
