Бинарна релация

от Уикипедия, свободната енциклопедия
Направо към: навигация, търсене

Бинарната релация или двуместна релация е множество от наредени двойки елементи. Бинарните релации са обект на изучаване в теория на множествата, теория на наредбите, математическата логика и компютърните науки.

Означения и определения[редактиране | edit source]

Два елемента x, y\, са в релация R\,, ако (x, y) \in R и (x, y) \neq (y, x), т.е. (x, y)\, е наредена двойка. Записва се xRy\, и се чете y\, е R\,-свързано с x\,, например добре познатите  x < y,\, x \leq y,\, x = y,\, x \equiv y\pmod{m} и др.

Дефиниционна област Dom (R) = \{ x\, |\, \exists y,\, xRy\} на релация е множеството от всички първи елементи на релацията.

Аналогично множество от стойности Cod (R) = \{y\, |\,\exists x,\, xRy\} е множеството от всички втори елементи на релацията.

Композиция R_{1} \circ R_{2} на две релации R_1\, и R_2\, е множеството от всички двойки \{ (x, y)\, |\, \exists y,\, xR_1y,\, yR_2z \}.

Идентитет или идентична релация Id_S\, на множество S\, e множеството от всички (x, x), x \in S.

Обратна релация R^{-1}\, се получава при смяна на реда на всички двойки от R\,, или R^{-1} = \{(x,y)\, |\, yRx\}. Изпълено е също Dom (R^{-1}) =\, Cod (R) и Cod (R^{-1}) =\, Dom (R).

Видове бинарни релации[редактиране | edit source]

Рефлексивна релация е релация R\,, за която всеки елемент от дефиниционната област и от множеството от стойности е R\,-свързан със себе си, т.е. \forall (x,y) \in (Dom (R), Cod (R)) е в сила xRx,\, yRy.

Антирефлексивна релация е релация R\,, за която не съществува елемент x\,, който да е R\,-свързан със себе си.

Симетрична релация е релация R\,, такава че xRy \Rightarrow yRx, или още релация която съвпада с обратната си R = R^{-1}\,

Антисиметрична релация е налице когато е изпълнена една и само една от следните алтернативи: xRy\, или yRx\,. Формулирано с помоща на обратна релация, условието се записва: R \cap R^{-1} = \varnothing.

Транзитиван релация се получава когато xRy,\, yRz \Rightarrow xRz. Формулирано с помоща на композиция, условието придобива вида: R \circ R \subset R

Кръгова релация на множество S\, е налице, когато  xRy,\, yRz \Rightarrow zRx,\ x, y, z \in S.

Наследник на релация R\, в множество S\, е най-малката транзитивна релация Succ_R\,, такава че R \subset Succ_R.

Една релация е релация на еквивалентност ако е едновременно рефлексивна, симетрична и транзитивна.

Частична наредба е релация която е рефлексивна, антисиметрична и транзитивна.