Как найти обратное отношение множеств

Операции над соответствиями на множествах

Поскольку соответствия можно считать множествами, то все операции над множествами (пересечение, объединение, разность, дополнение и т.д.) можно применить и к соответствиям. Заметим, что, говоря о дополнении соответствия из A в B, мы имеем в виду дополнение до универсального соответствия из A в B, т.е. до декартова произведения Atimes B. Естественно, что и равенство соответствий можно трактовать как равенство множеств.

В то же время на соответствия можно распространить операции, определяемые для отображений. Мы рассмотрим здесь две такие операции.

Композиция соответствии. Следуя аналогии с композицией отображнений, композицией (произведением) соответствий rhosubseteq Atimes B и sigmasubseteq Btimes C называют соответствие

rhocircsigma= bigl{(x,y)colon, (exists zin B)((x,z)inrho)land ((z,y)insigma)bigr}.

(1.3)

Поясним построение композиции двух соответствий. Обратимся сначала к отображениям (как частным случаям соответствий). Пусть заданы отображения (возможно, частичные): f из A в B и g из B в C. Композиция fcirc g определяется как отображение из A в C, задаваемое формулой y=g(f(x)). Тем самым задается график отображения fcirc g, т.е. множество упорядоченных пар (x,y), таких, что y=g(f(x)). При этом упорядоченная пара (x,y) будет принадлежать графику отображения fcirc g, если и только если найдется элемент zin b, такой, что z=f(x) и y=g(z). Таким образом, график композиции отображений f и g есть

fcirc g=bigl{(x,y)colon, (exists z)(z=f(x),, y=g(z))bigr}= bigl{(x,y)colon, y=g(f(x))bigr}.

(1.4)

Необходимо заметить, что запись gcirc f(x) означает g(f(x)), т.е. отображения в композиции пишутся в порядке, обратном тому, в каком они применяются. Мы же будем везде использовать запись fcirc g, полагая, что fcirc g(x)=g(f(x)) и порядок записи отображений в композиции совпадает с порядком их применения. Это обусловлено тем, что композиция отображений определяется нами как частный случай композиции соответствий, при записи которой естественным оказывается именно такой порядок.

Легко видеть, что (1.4) есть частный случай (1.3). Отметим, что при построении композиции отображений обычно предполагают, что пересечение области значений отображения f и области определения отображения g не пусто (R(f)cap D(g)ne varnothing), поскольку в противном случае композиция была бы пуста. Для отображений, не являющихся частичными, R(f)subseteq D(g), так как D(g)=B. Поэтому в данном случае пересечение R(f)cap D(g) всегда не пусто.

Полезно отметить также, что если f и g — биекции, то и композиция их тоже будет биекцией.

Вернемся к рассмотрению композиции соответствий rhocircsigma. Полагая, что область определения D(rho) соответствия rho не пуста, возьмем произвольный элемент xin D(rho). Пусть сечение rho(x)subseteq B соответствия rho не пусто и найдется такой элемент zinrho(x), что сечение sigma(z)subseteq C также не пусто. Тогда непустое множество {(x,t)colon, tinsigma(z)} будет подмножеством сечения соответствия rhocircsigma в точке x. Сечением соответствия rhocircsigma в точке x будет непустое в силу сделанных предположений множество всех таких упорядоченных пар (x,t)in Atimes C, что xin D(rho), а tinsigma(z) для некоторого zinrho(x). Говоря неформально, нужно перебрать все элементы z из сечения rho(x). Таким образом, различие в построении композиции соответствий и композиции отображений заключается в том, что «промежуточный» элемент z в общем случае не единственный и каждому такому элементу также ставится в соответствие не единственный элемент yin C.


Пример 1.8. Соответствие rho возьмем из примера 1.3. Соответствие sigma зададим как соответствие из множества программ {n_1,n_2 ,n_3, n_4, n_5} в множество заказчиков программного обеспечения {Z_1,Z_2,Z_3,Z_4}. Пусть

sigma=bigl{(n_1,Z_3),, (n_1,Z_4),, (n_2,Z_1),, (n_2,Z_1),, (n_3,Z_2),, (n_4,Z_4),, (n_5,Z_3)bigr}.

Рассмотрим процесс построения композиции соответствий rho и sigma. Начнем с элемента I. Имеем

rho(I)={n_1,n_3,n_5},quad sigma(n_1)={Z_3,Z_4},quad sigma(n_3)={Z_2},quad sigma(n_5)={Z_5}.

Отсюда получаем сечение композиции по элементу I:

sigma(n_1)cupsigma(n_3)cupsigma(n_5)= {Z_2,Z_3,Z_4}.

Рассуждая аналогично, получим (rhocircsigma)(P)={Z_1,Z_4} и (rhocircsigma)(C)={Z_1,Z_3}.

Построение графа композиции rhocircsigma проиллюстрировано на рис. 1.3.

Построение графа композиции соответствий

Отметим, что область определения композиции соответствий содержится в области определения первого соответствия, а область значений композиции соответствий — в области значений второго соответствия. Из приведенных рассуждений следует, что для того, чтобы композиция соответствий была отлична от пустого соответствия, необходимо и достаточно, чтобы пересечение области значений первого соответствия и области определения второго соответствия было не пусто.

К определению композиции соответствий можно подойти с более общих позиций. Пусть rho subseteq Atimes B и sigma subseteq Ctimes D. При этом на множества A,,B,,C и D априори не накладывается никаких органичений. Композиция rhocircsigma соответствий rho и sigma в этом случае также определяется соотношением (1.3). Чтобы такая композиция была отлична от пустого соответствия, необходимо и достаточно выполнение условия R(rho)cap D(sigma)ne varnothing. В частности, rhocircsigma=varnothing всякий раз, когда Bcap C=varnothing.


Пример 1.9. Рассмотрим соответствие tau={(1,a),(2,a),(3,d)} из множества A={1;2;3} в множество B={a,b,d} и соответствие varphi= {(b,e), (b,f), (c,f)} из множества C={b,c,d} в множество D={e,f}. В данном случае Bcap Cnevarnothing, но taucircvarphi=varnothing, поскольку

R(tau)={a,d},qquad D(varphi)={b,c},qquad R(tau)cap D(varphi)=varnothing.

Заметим, что композиция соответствий rho subseteq Atimes B и sigma subseteq Ctimes D не коммутативна, т.е. в общем случае rhocircsigmane sigmacircrho, поскольку rhocircsigma subseteq Atimes D, а sigmacircrho subseteq Ctimes B.


Композиция бинарного отношения на множестве

Бинарное отношение на множестве является частным случаем соответствия. Для двух бинарных отношении rho и sigma, заданных на множестве A, их композиция rhocircsigma (1.3) как соответствий является бинарным отношением на том же множестве A. В этом случае говорят о композиции бинарных отношений на множестве A.

Композицию rhocircrho бинарного отношения rho на некотором множестве с самим собой называют квадратом бинарного отношения rho и обозначают rho^2.

Рассмотрим пример построения композиции бинарных отношений на множестве и покажем, что в общем случае для двух бинарных отношений tau и varphi также имеет место неравенство taucircvarphine varphicirctau, хотя обе композиции, в отличие от аналогичных композиций двух произвольных соответствий, заданы на одном и том же множестве.


Построение композиции бинарных отношений

Пример 1.10. а. Зададим на множестве A={1,2,3,4} бинарные отношения tau,,varphi и найдем композицию taucircvarphi, если

tau=bigl{(x,y)colon, x+1<ybigr},quad varphi=bigl{(x,y)colon, |x-y|=2bigr}.

.

Имеем tau(1)={3;4},~ varphi(3)={1} и varphi(4)={2}. Следовательно, (taucircvarphi)(1)= varphi(3)cupvarphi(4)={1;2}. Далее tau(2)={4},~ varphi(4)={2} и (taucircvarphi)(2)={2}. Так как tau(3)= varphi(4)= varnothing, то в итоге получим taucircvarphi={(1;1),(1;2),(2;2)}. Построение композиции проиллюстрировано на рис. 1.4,а.

Найдем композицию varphicirctau. Поскольку varphi(1)={3}, а tau(3)=varnothing, то (varphicirctau)(1)=varnothing. Аналогично varphi(2)={4}, а tau(4)=varnothing, поэтому (varphicirc tau)(2)= varnothing. Далее varphi(3)={1},~ tau(1)={3;4}, поэтому (varphicirc tau)(3)= {3;4}, а varphi(4)={2},~ tau(2)={4} и (varphicirc tau)(4)= {4}. Построение композиции проиллюстрировано на рис. 1.4,б.

Легко видеть, что taucircvarphinevarphicirctau.

б. Пусть отношение rho на множестве действительных чисел определено как функция y=ax+b. Найдем квадрат этого отношения (линейной функции от одного переменного).

Согласно (1.4), это будет функция h, такая, что h(x)=a(ax+b)+c, то есть h(x)=a^2x+(ab+c). Это тоже линейная функция, но с другими коэффициентами.


Свойства композиции соответствий

Приведем некоторые свойства композиции соответствий:

1) rhocirc(sigmacirctau)= (rhocircsigma)circtau;
2) для любого соответствия rho имеет место rhocirc varnothing= varnothingcirc tau= varnothing;
3) rhocirc(sigmacuptau)= (rhocircsigma)cup (rhocirctau);
4) для любого бинарного отношения на множестве A имеет место равенство rhocirc operatorname{id}Acirc rho= rho.

Эти свойства нетрудно доказать методом двух включений. Рассмотрим в качестве примера доказательство свойства 3. Пусть некоторая упорядоченная пара (x,y) принадлежит композиции rhocirc(sigmacuptau). Тогда, согласно (1.3), найдется такой элемент z, что (x,z)inrho и (z,y)insigmacuptau. Последнее означает, что (z,y)insigma или (z,y)intau. Таким образом, для элемента z имеем (x,z)inrho и (z,y)insigma или (x,z)inrho и (z,y)intau. Первая альтернатива имеет место при (x,y)inrhocircsigma, а вторая — при (x,y)inrhocirctau, что означает (x,y)in rhocirc sigmacup rhocirc tau. Тем самым включение rhocirc (sigmacup tau)subseteq rhocirc sigmacup rhocirctau доказано.

Доказательство включения rhocirc sigmacup rhocirctau subseteq rhocirc (sigmacup tau) запишем коротко, используя логическую символику:

begin{aligned} (x,y)in rhocircsigmacup rhocirctau &Rightarrow (exists u)bigl(((x,u)inrho)land ((u,y)insigma)bigr)lor (exists v)bigl(((x,v)inrho)land ((v,y)intau)bigr) Rightarrow \[2pt] &Rightarrow (exists z)bigl(((x,z)inrho)land (((z,y)insigma)lor ((z,y)intau))bigr) Rightarrow\[2pt] &Rightarrow (exists z)bigl(((x,z)inrho)land ((z,y)insigmacuptau)bigr) Rightarrow\[2pt] &Rightarrow (x,y)in rhocirc (sigmacuptau). end{aligned}

В данном случае доказательства двух включений не совсем симметричны: элементы u и v во второй части доказательства не обязаны совпадать.

Замечание 1.4. В тождестве, выражающем свойство 3, нельзя вместо объединения поставить пересечение, так как в этом случае тождество нарушатся. Можно доказать, что сохранится лишь включение

rhocirc (sigmacap tau)subseteq rhocirc sigmacap rhocirctau,,

а обратное включение в общем случае не имеет места.

Анализ свойств 2 и 4 показывает, что роль пустого соответствия аналогична роли нуля при умножении чисел, а диагональ множества A играет роль, аналогичную роли единицы, на множестве всех бинарных отношений на A.


Обратное соответствие и его свойства

Соответствие, обратное к соответствию rho subseteq Atimes B, есть соответствие из B в A, обозначаемое rho^{-1} и равное, по определению, rho^{-1}= {(y,x)colon, (x,y)inrho}.

Для соответствия tau из примера 1.3

tau^{-1}= bigl{(n_1,I),, (n_2,P),, (n_2,C),, (n_3,I),, (n_4,P),, (n_5,I),, (n_5,C)bigr}.

Обратное соответствие обладает следующими легко проверяемыми свойствами:

1) (rho^{-1})^{-1}=rho;
2) (rhocircsigma)^{-1}=sigma^{-1}circrho^{-1}.

Для бинарного отношения rho на множестве A обратное соответствие есть бинарное отношение на том же множестве. В этом случае говорят о бинарном отношении rho^{-1} на множестве A, обратном к rho.

Заметим, что соответствия rhocircrho^{-1} и rho^{-1}circrho в общем случае не совпадают. Даже для бинарного отношения rho на множестве

Arhocircrho^{-1}ne rho^{-1}circrho, а также rhocirc rho^{-1}ne operatorname{id}A и rho^{-1}circ rhone operatorname{id}A.

Например, для бинарного отношения rho={(3;1), (4;1), (4;2)} на множестве A={1;2;3;4} графы самого отношения, обратного отношения rho^{-1}, композиций rhocircrho^{-1} и rho^{-1}circrho представлены на рис. 1.5.

Графы бинарного отношения, обратного отношения и композиций

Если fcolon Ato B — отображение, то оно является соответствием. Обратное к f соответствие из B в A в общем случае не является отображением. Действительно, соответствие f^{-1}, обратное к f, состоит из всех упорядоченных пар вида (f(x),x),, xin A. Поскольку в общем случае могут найтись такие два различных элемента x и x', что f(x)= f(x'), то соответствие f^{-1} в общем случае не будет функционально по второй компоненте и поэтому не будет отображением. Если отображение f инъективно, то обратное соответствие есть частичное отображение из B в A. Если отображение f биективно, то обратное соответствие является отображением из B в A, причем имеют место равенства

fcirc f^{-1}=operatorname{id}A,,qquad f^{-1}circ f= operatorname{id}B,.

Отображение f^{-1} в этом случае называют отображением, обратным к f.


Ограничение соответствия

Пусть rho subseteq Atimes B — соответствие из A в B и C subseteq A,~ D subseteq B. Ограничением соответствия rho на подмножества C и A (или (C,D)-ограничением соответствия rho) называется соответствие из C в D, обозначаемое rhobig|_{C,D}, такое, что

(x,y)in rhobig|_{C,D}~ Leftrightarrow~ bigl((x,y)inrhobigr)land (xin C)land (yin D).

Таким образом, (C,D)-ограничение соответствия rho есть «то же самое» соответствие rho, но из последнего берутся только упорядоченные пары, первая компонента которых принадлежит подмножеству C, а вторая — подмножеству D. Можно записать

rhobig|_{C,D}= rhocap (Ctimes D).

Так, «малый» арксинус, т.е. функция y=arcsin{x}, есть ограничение «большого» арксинуса y=operatorname{Arcsin}x, который является соответствием на подмножества [-1;1] и left[-frac{pi}{2};frac{pi}{2}right].

Рассмотрим некоторые важные частные случаи ограничений соответствий (в частности, бинарных отношений и отображений).

Всякое (C,D)-ограничение соответствия rho subseteq Atimes B будем называть сужением соответствия rho на подмножество C (коротко — C-сужением соответствия rho), а всякое (C,rho(C))-ограничение соответствия rho — строгим сужением соответствия rho на подмножество C (строгим C-сужением соответствия р). C-сужения соответствия rho будем обозначать rhobig|_{C}, а строгое сужение — rhobig|_{circ C} соответственно.

Полезно заметить, что для любого отображения fcolon Ato B строгое сужение fbig|_{circ A} есть сюръекция A на f(A). Если, сверх этого, f является инъекцией, то fbig|_{circ A} есть биекция A на f(A). Допуская некоторую вольность речи, можно сказать, что любое отображение сюръективно отображает свою область определения на свою область значений, в частности, любая инъекция устанавливает взаимно однозначное соответствие между областью определения и областью значений. Так, функция y=sin{x} сюръективно отображает множество mathbb{R} всех действительных чисел на отрезок [-1;1], а любая показательная функция биективно отображает mathbb{R} на подмножество всех положительных действительных чисел.

Для бинарного отношения rho subseteq A^2 и любого подмножества M subseteq A (M,M)-ограничение бинарного отношения называют ограничением бинарного отношения rho на подмножество M и обозначают rhobig|_{M}. Можно записать rhobig|_{M}=rhocap M^2.

Рассмотрим, например, отношение естественного порядка leqslant на множестве действительных чисел. Тогда отношение leqslantbig|_{mathbb{Z}}= bigl{(m,n)colon, m leqslant n;~ m,ninmathbb{Z}bigr} есть ограничение этого порядка на подмножество целых чисел. Но ни в коем случае нельзя путать это отношение с mathbb{Z}-сужением отношения leqslant! Это последнее состоит из всех таких упорядоченных пар (m,x), что minmathbb{Z},, xinmathbb{R} и mleqslant x, т.е. вторая компонента пары может быть произвольным действительным числом, не меньшим заданного целого m.

Математический форум (помощь с решением задач, обсуждение вопросов по математике).

Кнопка "Поделиться"

Если заметили ошибку, опечатку или есть предложения, напишите в комментариях.

Определение:
Композицией (произведением, суперпозицией) бинарных отношений (англ. composition of binary relations) и называется такое отношение , что:
.

Примером такого отношения может служить отношение на некотором множестве населенных пунктов — отношение «можно доехать на поезде», а — отношение «можно доехать на автобусе». Тогда отношение — отношение «можно добраться из пункта А в пункт Б, сначала проехав на поезде, а потом на автобусе (только по одному разу)».

Степень отношений

Определение:
Степень отношения (англ. power of relation) , определяется следующим образом:

  • ;

В связи с этим понятием, также вводятся обозначения:

— Транзитивное замыкание (англ. transitive closure) отношения ;

— Транзитивно-рефлексивное замыкание отношения

Обратное отношение

Определение:
Отношение называют обратным (англ. inverse relation) для отношения , если:
Определение:
Ядром отношения (англ. kernel of relation) называется отношение

Свойства

Композиция отношений обладает следующими свойствами:

  • Ядро отношения симметрично:  
  • Композиция отношений ассоциативна:  
  • Обратное отношение для отношения, являющемуся обратным к есть само  
  • Обратное отношение к композиции отношений и есть композиция отношений, обратных к и  
  • Обратное отношение к объединению отношений и есть объединение отношений, обратных к и  
  • Обратное отношение к пересечению отношений и есть пересечение отношений, обратных к и  

См. также

  • Бинарное отношение
  • Транзитивное замыкание

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

  • Новиков Ф. А. — Дискретная математика для программистов: Учебник для вузов. 3-е изд. — СПБ.: Питер, 2009 — 52 с.
  • Wikipedia — Composition of relations
  • UNC Charlotte — Lectures in Discrete Mathematics: Composition of Relations and Directed Graphs.

Если мы хотим
определить такое понятие, как отношение,
мы должны, прежде всего, ввести такое
понятие, как упорядоченная
пара
.

Различие между
неупорядоченной парой элементов {a,b}
и упорядоченной парой (a,b)
обычно поясняют на примере сравнения
двух пар элементов. Две неупорядоченные
пары {a,b}={c,d},
если a=b&c=da=c&b=d.
Для упорядоченных пар (a,b)=(c,d)

a=b&c=d.
То есть, в общем случае, для упорядоченных
пар (a,b)(b,a).
Иногда употребляют и такую запись:
R=(a,b)={a,{a,b}}.
Нетрудно догадаться, что существование
множества {a,b}
зависит от того, какое мы выберем a.
Если a,b
– числа, то мы можем описать множество
упорядоченных пар в виде графика,
откладывая по оси абсцисс значения a,
по оси ординат значения b,
для которых существует R=(a,b).

Упорядоченную
пару R
называют двухместным
или бинарным
отношением
.
Упорядоченный набор из n
элементов (a1,
… , an)
называют n-местным
отношением
или
кортежем.

Элементы для
формирования упорядоченных наборов
мы можем выбирать как из одного множества,
так и из разных. При построении графиков,
которые отображают бинарные отношения
между множествами действительных чисел
X
и Y,
мы используем так называемую декартову
систему координат.

Прямым (декартовым)
произведением двух множеств
A
и
B
называется множество упорядоченных
пар (a,b),
в которых aA
и bB:
AB={(a,b)|
aA
& bB}.

Степенью множества
A
называется его прямое произведение
само на себя: An=A…A
– всего n
раз.

Пользуясь введенным
понятием прямого произведения, можно
определить бинарное отношение как
подмножество
прямого произведения
AB:
R=ab={(a,b)R|
RAB}.

Запись ab
обозначает
отношение между элементами a
и b
в общем виде, а запись (a,b)
обозначает конкретную упорядоченную
пару элементов, то есть один элемент
отношения.

Если у нас задан
некоторый универсум U,
то мы можем рассматривать понятия
принадлежности (),
включения (),
и равенства (=), как отношения на B(U)
– множестве всех подмножеств универсума
U.

Способы задания
отношений.

Если отношение содержит небольшое
количество пар (или наборов), его можно
задать, как и множество, перечислением.
Бинарные отношения, как уже говорилось,
могут быть заданы в виде графиков, если
A,B
– числовые множества. В общем случае
отношения могут быть заданы в виде
таблиц или графов. В реляционных базах
данных понятие «кортеж» соответствует
записи в таблице, а поля таблицы с
именами A,B,C,…,
из которых берутся элементы записи,
образуют прямое произведение множеств
ABC…
.

Основные понятия,
связанные с понятием бинарного отношения.

Пусть
R=ab={(a,b)R|
RAB}.
Тогда
существуют:

обратное отношение
R-1={(b,a)|(a,b)R};

дополнение
отношения R={(a,b)|(a,b)R}=(AB)R;

тождественное
отношение I={(a,a)|aA};

однородное
отношение:
UR={(a,b)|aA&bA}.

Композиция
отношений.

Пусть заданы два
бинарных отношения: R1AB
и R2BC
(говорят так: отношение из A
в B
и отношение из B
в C).

Композицией
отношений

R1
и R2
называется
отношение R
из A
в C:

R=
R1
o R2
={(a,c)|
aA
&
cC
&
bB
: (a,b)

R
1
& (b,c)

R
2}.

Пример.Пусть
A
— множество студентов ФПК, B
– множество специальностей, С –
множество учебных курсов, изучаемых
на этих специальностях. Нам нужно
определить, какие дисциплины будет
изучать каждый конкретный студент ФПК
(что будет включать его приложение к
диплому).

Здесь R1
AB
– «студент aA
получает специальность bB»,
R2
BC
– «на специальности bВ
изучается дисциплина cC».
Искомое отношение R
– «студент aA
изучает дисциплину cC»
есть композиция отношений R=
R1
R2.
То есть, чтобы студент aA
изучал дисциплину cC
нужно, чтобы он учился на специальности
bB,
что соответствует отношению ab,
и на этой специальности изучалась
данная дисциплина cC,
что соответствует отношению bc.
Значит, для решения задачи нам нужно
выяснить, для каких пар (a,b)
имеются пары (b,c),
и из этих пар составить новые пары
(a,c),
взяв первый элемент из пары (a,b),
а второй элемент – из пары (b,c).

Графически операцию
композиции можно проиллюстрировать
на следующей схеме.

В этой графической
схеме каждой упорядоченной паре
элементов (a,b)
и (b,c)
сопоставлены стрелки из множества А
в множество B
и из множества B
в множество C
соответственно. Искомым парам (a,c)
соответствуют возможные переходы по
стрелкам из множества A
в множество C.

Теперь составим
бинарные таблицы R1
и R2
для
представленных данной схемой отношений.
Элементы этих таблиц rij(1)
и rjk(2)
соответствуют
отношениям (ai,bj)
и (bj,ck).
Первая таблица будет содержать |A|
строк и |B|
столбцов, вторая — |B|
строк и |C|
столбцов. Для нашего примера таблицы
будут иметь вид:

1

0

0

0

1

1

1

0

0

0

1

0

1

0

1

1

0

0

0

1

0

0

1

0

0

0

1

0

0

1

R1

R2

Одновременное
существование отношений rij(1)
и rjk(2)
соответствует
логическому произведению (конъюнкции)
элементов таблицы rij(1)

rij(2),
и значение каждого элемента rik
итоговой таблицы R
будет зависеть от того, принимает ли
хотя бы одна из этих элементарных
конъюнкций значение «1», что соответствует
логическому сложению (дизъюнкции). Для
нашего примера r11=(r11(1)
r21(1)
r31(1)
r41(1)
)(
r11r12(2)
r13(2)
r14(2)
r15(2)
r16(2)),
и так далее. То есть при i=1,…,|A|,
j=1,…,|B|,
k=1,…,|C|
мы имеем: R=
R1
o
R2
= R1
R2
, где R1
R2
логическое
перемножение матриц
.

Степенью отношения
Rn
называется композиция отношения R
n
раз с самим собой.

Ядром отношения
RAB
называется композиция R*=
R
o
R-1.
Ядро отношения является отношением на
A.

9.Однородные
(универсальные) отношения. Примеры
универсальных отношений. Свойства
однородных отношений (рефлексивность,
симметричность, транзитивность).
Отношение эквивалентности и отношение
порядка
.

однородным
отношением

отношение R=
a

b={(a,b)|aA&bA}.

однородное отношение
– это отношение RA2.
Однородные
бинарные отношения

– важный тип отношений для многих
приложений информатики и других разделов
дискретной математики, для задач теории
графов. Ребра любого графа задают
однородное бинарное отношение на
множестве его вершин V.
Множество точек на плоскости с заданной
системой координат (X,Y)
– это тоже однородное бинарное отношение,
где A
– множество действительных чисел.

Свойства однородных
отношений.

1. Рефлексивность:

aA
имеет место отношение (a,a).
То есть отношение (a,b)
всегда существует при a=b.
Свойство рефлексивности означает,
что IR.

2.
Антирефлексивность:

aA
имеет место (a,a).
То есть отношение (a,
b)
не существует
ни при каких a=b.
Если для каких-то a=b
отношение существует, а для каких-то
нет, то следует говорить, что отношение
просто не
рефлексивно
.

Примеры рефлексивных
отношений

на множестве точек плоскости XY:

1) R={(x,y)
| x=y};

2) R={(x,y)
| |y|<|x|+1};

3) R={(x,y)
| x+y=2k,
k=1,2,…,n}.

3.
Симметричность:

a,bA
(a,b)R

(b,a)R.
Свойство
симметричности означает, что R-1R.

Симметричными
отношениями на множестве точек плоскости
XY
являются отношения 1) и 3) из приведенных
выше.

4.
Антисимметричность:

a,bA
, ab,
(a,b)R


(b,a)R.
То есть
условие симметричности не
выполняется

ни при каких a,b.
Простейший пример антисимметричного
отношения на XY
– строгое неравенство x<y.

Если для каких-то
ab
симметричность выполняется, а для
каких-то нет, то следует говорить, что
отношение R
просто не
симметрично
.
Примером такого отношения является
отношение 2).

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

a,b,cA
(a,b)R
& (b,c)R

(a,c)R.
Очень важное свойство отношений.

Свойство
транзитивности можно записать через
степень отношения (композицию отношения
с самим собой): R2
=R

R

R.

Антитранзитивность
обычно не рассматривают, хотя можно и
ее определить так же, как в первых двух
случаях.

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

1) все три примера,
приведенных выше;

2) x<y
( в том числе и нестрогое неравенство);

3) отношение
вложенности на B(U):
пусть A,B,C

U.
Если A

B
& B

C

A

C.

6.
Полнота
(
линейность):

a,bA
, ab


(a,b)R

(b,a)R
.
Полнота
отношения означает, что R

R-1

I
= UR.

Свойство полноты,
вообще говоря, довольно редкое. Пример
полного отношения — неравенство xy.

Отношения
эквивалентности и отношения порядка.

Определение 1.
Если однородное отношение RA2:

  1. рефлексивно,
    2)симметрично, 3) транзитивно

то оно называется
отношением
эквивалентности.
Отношение
эквивалентности часто обозначается
«»,
как и операция эквивалентности в логике.
Множество элементов aA,
для которых выполняется отношение
эквивалентности R,
называется классом
эквивалентности
.
Класс эквивалентности будем обозначать
[x]:

[x]
= {y
| yA
& yx}.

Из рассмотренных
выше примеров отношениями эквивалентности
являются примеры 1) и 3).

Примером отношения
эквивалентности на B(U)
может служить отношение равномощности
множеств: |A|=|B|.
То есть все подмножества из U
одинаковой мощности образуют класс
эквивалентности.

Определееие 2.
Если однородное отношение RA2:

  1. антисимметрично,
    2) транзитивно,

то
оно называется отношением
порядка
.
Если отношение при этом еще и
антирефлексивно,
то это отношение
строгого порядка
.
Отношение нестрогого порядка может
быть как рефлексивным, так и просто не
рефлексивным.Для обозначения отношения
порядка можно использовать обычный
знак неравенства.Если отношение порядка
не обладает свойством полноты
(линейности), то обычно говорят об
отношении частичного
порядка
. В
задачах дискретной математики и
информатики чаще всего встречается
именно этот тип отношений.

Если на множестве
А определено отношение частичного
порядка, то оно называется частично
упорядоченным
.
Множество, на котором определено
отношение полного порядка, называется
вполне
упорядоченным
.
Например, числовые множества – это
вполне упорядоченные множества.

Теорема.
На всяком конечном, непустом, частично
упорядоченном множестве существует
минимальный
элемент
y
| 
xy
y<x.

Вполне упорядоченное
множество содержит только один
минимальный элемент, на частично
упорядоченном множестве их может быть
несколько. Булеан B(U),
— это вполне упорядоченное множество
относительно отношения вложенности
().
Минимальным элементом в этом случае
является пустое множество .

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

  • #
  • #
  • #
  • #
  • #
  • #
  • #
  • #
  • #
  • #
  • #

Обратное отношение в математике — это отношение, взятое в обратном порядке по отношению к данному.

Определение

Пусть на множестве {displaystyle X} задано бинарное отношение {displaystyle R.} Тогда его обратным называется отношение {displaystyle R^{-1},} построенное следующим образом:

{displaystyle forall x,yin Xquad {bigl (}xR^{-1}y{bigr )}Leftrightarrow {bigl (}yRx{bigr )}.}

Свойства

  • Если отношение {displaystyle R} обладает одним из перечисленных свойств: рефлексивностью, нерефлексивностью, симметрией, антисимметрией, асимметрией, транзитивностью или полнотой, то и обратное отношение {displaystyle R^{-1}} также обладает им.
  • Если {displaystyle R} инъективно, сюръективно или функционально, то {displaystyle R^{-1}}, вообще говоря, не обязано обладать таким же свойством.

Примеры

п·о·р

Бинарное отношение

между двумя множествами: инъективное · сюръективное · биективное · полное слева · полное справа · функциональное
на множестве: рефлексивное · нерефлексивное · симметричное · антисимметричное · асимметричное · транзитивное · полное · евклидово

1.Что такое отношение? 2.Что показывает отношение?
3.Как найти отношение?
4.Как найти обратное отношение
МАТЕМАТИКА СРОЧНО ЗА 30 МИНУТ​

nataxa199018

чтобы найти отношение, нужно оба числа разделить на одно и тоже число:

напр.: 12 : 3 = 4 : 1 (то есть оба числа — 12 и 3, разделили на 3 и получили 4 и 1),

Обратное отношение — это отношение, взятое в обратном порядке по отношению к данному.

Отношения

Нам известно, что для ответа на вопрос во сколько раз одно число больше другого (или меньше), или какую часть одно из них составляет от другого надо найти частное данных чисел.

Где и члены отношения; число предыдущий член отношения; последующий член отношения.

14 : 7 — отношение числа 14 к числу 7;

6 : 25 — отношение числа 6 к числу 25;

— отношение числа к числу ;

1,15 : 0,36 — отношение числа 1,15 к числу 0,36.

Отношение двух чисел показывает, во сколько раз одно число больше другого, или какую часть одно число составляет от другого. То есть отношение чисел и показывает, во сколько раз число больше числа или какую часть число составляет от числа .

Мы помним, что деление можно заменить чертой дроби, значит, отношение чисел и можно записать двумя способами: : и .

Основное свойство отношения:

Отношение не изменится, если его члены умножить или разделить на одно и то же число, не равное нулю.

Запишем отношение числа 3 к числу 10 и найдем его значение:

То есть отношение двух чисел можно выразить в процентах.

Процентное отношение двух чисел — это их отношение, выраженное в процентах.

Процентное отношение показывает, сколько процентов одно число составляет от другого.

Чтобы найти процентное отношение двух чисел, надо их отношение умножить на 100 и к результату дописать знак процента.

Пример:

Сколько процентов составляет число 5 от числа 10?

5 10 2 1 · 100 % = 1 2 · 100 % = 100 2 % = 50 % .

Ответ: 50% составляет число 5 от числа 10.

Если значение двух величин выражены одной и той же единицей измерения, то их отношение называют также отношением этих величин. При этом если значения величин выражены разными единицами измерения, то для нахождения отношения этих величин надо сначала перейти к одной единице измерения.

Например:

Дан прямоугольник, длина которого равна 12 см, а ширина 1 м. Найдем отношение длин сторон прямоугольника.

Отношение длины прямоугольника к его ширине равно 12 : 100 = .

Отношение ширины прямоугольника к его длине равно 100 : 12 = .

Дроби и взаимно обратны, поэтому и отношения 12 к 100 и 100 к 12 называют взаимно обратными.

На практике отношение величин используется, например, при составлении планов и географических карт. В этом случае участки земли на бумаге изображают в уменьшенном виде, при этом на карте или плане указывают отношение, которое показывает, во сколько раз длина отрезка на рисунке меньше длины длины соответствующего отрезка на местности.

Отношение длины отрезка на карте к длине соответствующего отрезка на местности называют масштабом карты (плана).

Пусть на карте задан масштаб , то есть карта сделана в масштабе одна десятитысячная.

Найдем, какой длине на местности соответствует отрезок 5 см на карте.

Для решения обозначим через />длину отрезка на местности (в сантиметрах). Тогда отношение длины отрезка на карте к длине отрезка на местности: 5 : />, данное отношение равно масштабу карты, поэтому получаем уравнение:

5 : = 1 : 10 000;

Решаем данное уравнение:

= 510 000;

= 50 000;

50 000 см = 500 м = 0,5 км.

Ответ: отрезок 5 см на карте соответствует 0,5 км на местности.

Найдем, какой длине на карте соответствует отрезок 9,5 км на карте.

Для решения обозначим через />длину отрезка на карте (в километрах). Тогда отношение длины отрезка на карте к длине отрезка на местности: />: 9,5, данное отношение равно масштабу карты, поэтому получаем уравнение:

: 9,5 = 1 : 10 000;

Решаем данное уравнение:

= 9,5 : 10 000;

= 0,00095;

0,00095 км = 0,95 м = 95 см.

Ответ: отрезок 9,5 км на карте соответствует 95 см на карте.

математика — Как найти обратное отношение данному?

Если пара (x,y) принадлежит отношению R, то пара (y,x) принадлежит обратному отношению (и наоборот). Поэтому достаточно написать, что R^ <-1>состоит из всех пар вида (y,x), а дальше всё ровно то же самое.

Если по каким-то причинам хочется, чтобы первая переменная обозначалась x, а вторая y (хотя это ни к чему), то можно оставить (x,y), а после двоеточия написать всё с заменой x на y и наоборот.

Дел в том, что по заданию требуется записать отношение R^ <-1>аналитически и графически. А также найти для него область определения, область значений.

Сделайте рисунок. Уже говорилось, что R^ <-1>состоит из всех пар вида (x,y), где 2y-x>=2 на квадрате (обе переменные от -4 до 7). Рисуете квадрат, потом график прямой, и берёте то, что сверху от неё. А аналитически всё уже задано (поменяли местами x и y).

Надо иметь в виду, что в таких заданиях не бывает ничего нетривиального.

Спасибо большое! Еще вопрос, не подскажите, что такое $$overline$$ и как его найти?

@lisp: такие обозначения могут использоваться для чего угодно. Их надо сверять с «документацией», то есть с лекциями. Одно из возможных толкований такое: это дополнение отношения, заданного на множестве. Элемент x находится в отношении $%bar R$% с y тогда и только тогда, когда x не находится в отношении R с y. Если в Вашем случае отношение задано на отрезке [-4;7], то надо просто поменять знак $%ge$% на $%<$%, и получится аналитическая запись для $%bar$%. А геометрически это то, что не входит в R (в пределах квадрата).

Для решения задач этого типа достаточно двух-трёх определений.

Здравствуйте

Математика — это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Понравилась статья? Поделить с друзьями:
  • Используя программу квадрат как вспомогательный алгоритм составьте алгоритм главный
  • Как составить финансовую налоговую отчетность
  • Excel как найти квартал
  • Как найти на сколько изменилась цена
  • Как можно составить план местности