Транзитивное отношение — различия между версиями

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

Текущая версия на 19:07, 4 сентября 2022

Определение

Бинарное отношение [math]R[/math] на множестве [math]X[/math] называется транзитивным, если для любых трёх элементов [math]a, b, c[/math] из выполнения отношений [math] aRb [/math] и [math] bRc [/math] следует выполнение отношения [math] aRc [/math].

Определение:
Бинарное отношение [math]R[/math], заданное на множестве [math]X,[/math] называется транзитивным (англ. transitive binary relation), если для [math]\forall ~a, b, c \in X\colon ~(aRb)~ \land ~(bRc) \Rightarrow ~(aRc)[/math].


Если это условие соблюдается не для всех троек [math]a, b, c[/math], то такое отношение называется нетранзитивным. Например, не для всех троек [math] a, b, c \in \mathbb{N} [/math] верно, что [math]~(a \nmid b)~ \land ~(b \nmid c)~ \Rightarrow ~(a \nmid c) [/math].

Определение:
Бинарное отношение [math]R[/math], заданное на множестве [math]X,[/math] называется нетранзитивным (англ. intransitive binary relation), если [math]\exists ~a, b, c \in X\colon ~(aRb)~ \land ~(bRc)~ \land ~\neg(aRc)[/math].


Существует более "сильное" свойство — антитранзитивность. Под этим термином понимается, что для любых троек [math]a, b, c[/math] отсутствует транзитивность. Антитранзитивное отношение, например — отношение победить в турнирах «на вылет»: если [math]A[/math] победил игрока [math]B[/math], а [math]B[/math] победил игрока [math]C[/math], то [math]A[/math] не играл с [math]C[/math], следовательно, не мог его победить.

Определение:
Бинарное отношение [math]R[/math], заданное на множестве [math]X,[/math] называется антитранзитивным (англ. antitransitive binary relation), если для [math]\forall ~a, b, c \in X\colon ~(aRb)~ \land ~(bRc)~ \Rightarrow ~\neg(aRc)[/math].

Свойства

  • Если отношение [math]R[/math] транзитивно, то обратное отношение [math]R^{-1}[/math] также транзитивно. Пусть [math]aR^{-1}b, ~bR^{-1}c[/math], но по определению обратного отношения [math]cRb, ~bRa[/math]. Так как [math]R[/math] транзитивно, то [math]cRa[/math] и [math]aR^{-1}c[/math], что и требовалось доказать.
  • Если отношения [math]R, ~S[/math] транзитивны, то отношение [math]T~ = ~R \cap S[/math] транзитивно. Пусть [math]aTb, ~bTc \Rightarrow ~aRb, ~aSb, ~bRc, ~bSc[/math]. Из транзитивности [math]R, ~S[/math] следует [math]aRc, ~aSc[/math], но из определения пересечения отношений получаем [math]aTc[/math], что и требовалось доказать.

Примеры транзитивных отношений

  • Отношения частичного порядка:
    • строгое неравенство [math]\colon ~(a \lt b), ~(b \lt c)~ \Rightarrow ~(~a \lt c)\;[/math]
    • нестрогое неравенство [math]\colon ~("\leqslant ")\;[/math]
    • включение подмножества:
      • строгое подмножество [math]\colon ~ ("\subset ")\;[/math]
      • нестрогое подмножество [math]\colon ~ ("\subseteq ")\;[/math]
    • делимость:
      • [math](a \mid b), ~(b \mid c)~ \Rightarrow ~(a \mid c)\;[/math]
      • [math](a \,\vdots\, b), ~(b \,\vdots\, c)~ \Rightarrow ~(a \,\vdots\, c)\;[/math]
  • Равенство [math]\colon ~(a = b), ~(b = c) \Rightarrow ~(a = c)\;[/math]
  • Эквивалентность [math]\colon ~(a \Leftrightarrow b), ~(b \Leftrightarrow c)~ \Rightarrow ~(a \Leftrightarrow c)\;[/math]
  • Импликация [math]\colon ~(a \Rightarrow b), ~(b \Rightarrow c)~ \Longrightarrow ~(a \Rightarrow c)\;[/math]
  • Параллельность [math]\colon ~(a \parallel b), ~(b \parallel c)~ \Rightarrow ~(a \parallel c)\;[/math]
  • Отношение подобия геометрических фигур
  • Являться предком

Примеры нетранзитивных отношений

  • Пищевая цепочка: это отношение не всегда является транзитивным (пример — волки едят оленей, олени едят траву, но волки не едят траву).
  • Быть предпочтительнее чем. Если мы хотим яблоко вместо апельсина, а вместо яблока мы бы хотели арбуз, то это не значит, что мы предпочтём арбуз апельсину.
  • Быть другом.
  • Являться коллегой по работе.
  • Быть подчиненным. Например, во времена феодального строя в Западной Европе была в ходу поговорка: Вассал моего вассала — не мой вассал.
  • Быть похожим на другого человека.

Примеры антитранзитивных отношений

  • Быть сыном (отцом, бабушкой).
  • Игра "Камень, ножницы, бумага". Камень побеждает ножницы, ножницы выигрывают у бумаги, но камень проигрывает бумаге и т. д.

См. также

Источники информации