Понятие соответствия. Понятие отображения

Рассмотрим два множества
X ={x1, x2 ,...,xn} и Y ={y1, y2

Соответствие q представляет собой
тройку множеств q = (X,Y,Q), где X и

Множество Q X×Y определяет закон,
по которому осуществляется
соответствие , т.е. перечисляет все

Для каждого q = (X, Y, Q) можно указать
обратное соответствие q-1

Обратное соответствие обратного
соответствия даст прямое соответствие
(q-1)-1 = q.

Соответствие называется взаимно
однозначным, если каждому элементу
множества X соответствует (поставлен в
пару с

Отображения

Отображение является частным
случаем соответствия (однозначное
соответствие).
Соответствие, характеризующее
правило, по которому каждому элементу
множества

Пусть X = {х1, х2, х3}; Y = {у1, у2, у3,

Отображение называется сюръективным (или отображением "на"), если образы точек множества X

Отображение называется инъективным (или отображением "в"), если элементы множества X отображаются

Биективное отображение является одновременно инъективным и сюръективным, т.е. является взаимно однозначным.

Важным случаем отображения является отображение элементов внутри одного множества.
При этом

С помощью отображений могут быть даны определения таким понятиям, как функция,

Если отображение Г: X→Y рассматривается как соответствие между множествами X и

Таким образом, f является множеством, элементами которого являются пары
(х, у),

Произвольное подмножество множества А1 x А2 x…x Аn.
называется отношением, заданным или

элементы
(где )
связаны отношением R тогда и только
тогда, когда

Бинарным отношением (соответствием) R из A в B называется подмножество декартового

Если (а,b) R, это записывается как aRb; при этом говорят, что

Примером отношений могут служить такие понятия:
как "меньше, чем",
"делится на",
"включено в",
"больше

Примеры отношений:

а) соответствие между множеством отпечатков пальцев A = {a, b,

в) пусть А – множество товаров в магазине, а В –

г) пусть А – множество женщин, а
В – множество мужчин,

е) если А = {1,2,3},а В = {r, s},
так что

Пример

Подмножество R декартового произведения множеств
A1 A2 … An называется отношением

Если А1=А2=А3=…=Аn, то декартово произведение A1 A2 … An
называется декартовым

Обобщенное понятие отношения: n-местное отношение R – множество упорядоченных наборов

Пример

Отношение
круг радиуса 1 с центром в начале координат, то есть множество

Пример

Если A –конечное, то отношение задают списком пар.

Бинарное отношение можно задавать матрицей , элементы которой равны:
единице, если пара

Пример отношения заданного матрицей

Любая матрица размерности
является матрицей бинарного отношения между множествами А и

Отношение между двумя элементами называется бинарным, или двухместным, между тремя-тернарным, или

Мощность множества кортежей, входящих в отношение R, называют мощностью отношения R.

Свяжем с каждым бинарным отношением R между А и В
область

Область определения отношения R на А и В есть множество всех

Область значений отношения R на
А и В есть множество всех

Пример

С каждым отношением R на А В связано отношение R-1 на

Пусть R А В
есть отношение на А В.
Тогда отношение

Другими словами (b,a) R-1 , тогда и только тогда, когда (а,b)

Пример:
R = {(x,y) | x,y N & y=x2} – отношение

Термин «реляционное представление данных», впервые введенный Коддом, происходит от термина relation.

Во-первых, все элементы отношения есть однотипные кортежи. Например, рассмотрим отношение, состоящее

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

Множество {(1), (1, 2), (1, 2, 3)}, состоит из разнотипных числовых

Во-вторых. За исключением крайнего случая, когда отношение есть само декартово произведение

Для каждого отношения имеется критерий, позволяющий определить, какие кортежи входят в

Каждому отношению можно поставить в соответствие некоторое логическое выражение P(x1, x2,

Кортеж (a1, a2, …, an) принадлежит отношению R тогда и только

Каждый n-местный предикат задает некоторое n-арное отношение.
Таким образом, существует взаимно

основные свойства отношений

тождественность,
рефлексивность,
антирефлексивность,
симметричность,
антисимметричность,
транзитивность.

Отношение R называется тождественным на множестве A, если, оно состоит из

Отношение R называется рефлексивными на множестве А, если для всех а

Отношение R называется антирефлексивным, если для всех
а А не выполняется

Отношение R называется симметричным на множестве А, если для каждой пары

Отношение R называется антисимметричным на множестве А, если для каждой пары

Отношение R называется транзитивным на множестве А, если для любой тройки

Примеры:

Рассмотрим следующее отношение
«х делит у на множестве натуральных чисел».

Отношение рефлексивно, так как х всегда делит сам себя.
Отношение не симметрично,

Предположим, что х делит у, а у в свою очередь делит

Отношение антисимметрично, так как если из предположения х делит у и

Рассмотрим следующее отношение: «количество лет х совпадает с возрастом у» на

Отношение рефлексивно, так как возраст любого человека совпадает с количеством прожитых

Отношение симметрично, так как высказывание «количество лет х совпадает с возрастом

Отношение транзитивно, так как если найдутся такие три человека х, у,

Отношение антисимметрично, так как из высказывания высказывание «количество лет х совпадает

Пусть А = {1,2,3,4,5,6},
R А А
R = {(1,1), (2,2),

Отношение R рефлексивно,
так как для каждого а А, (а,а) R.

Отношение R симметрично так как,
R = {(1,1), (2,2), (3,3), (4,4),

Отношение транзитивно,

Отношение R не является
антисимметричным, так как,
R = {(1,1), (2,2), (3,3),

Пусть А = {♠, ♣, ♥, ♦} ,
R А А

Отношение не рефлексивно,
так как ♣ A, но (♣,♣) A ,
R

Отношение не симметрично, так как
R = {(♠,♠), (♠,♣), (♠,♦), (♣,♠),

Отношение не является антисимметричным, так как
R = {(♠,♠), (♠,♣), (♠,♦),

Отношение не является транзитивным,
так как R = {(♠,♠), (♠,♣), (♠,♦),

Замыкание отношений

Если отношение R на множестве А не обладает тем или иным

Под продолжением понимается присоединение некоторых упорядоченных пар к подмножеству

Новое полученное множество R* уже будет обладать требуемым свойством. Исходное множество

Если вновь построенное множество R* будет минимальным среди всех расширений R

Рефлексивное замыкание R есть наименьшее рефлексивное отношение на A, содержащее R

Рефлексивным замыканием Ri отношения R
называется отношение
, где i – отношение

Симметричное замыкание R наименьшее симметричное отношение на A, содержащее R как

Симметричным замыканием Rs
отношения R называется отношение
т.е. если (а,b) R,
то

Транзитивное замыкание R наименьшее транзитивное отношение на A, содержащее R как

Транзитивным замыканием Rt отношения R называется отношение
т.е. (а,b) Rt тогда

Пример

А = {1,2,3}, отношение R на А задано упорядоченными парами
R

Замыкание относительно рефлексивности должно содержать все пары вида (а,а). Поэтому, искомое

Замыкание относительно симметричности должно содержать все пары, симметричные исходным.

Замыкание относительно транзитивности.
Необходимо выполнить несколько шагов.
Отношение R = {(1,1), (1,2),

Появились пары (2,1) и (1,2).
Следовательно, замыкание R* должно
содержать пару (2,2).
Все необходимые

Пусть А = {а1, а2, а3,а4},
R = {(а1,а3), (а3,а4), (а4,а2),

Ri = {(а1,а3), (а3,а4), (а4,а2), (а3,а3); (а1,а1), (а2,а2), (а4,а4)}.

Rs = {(а1,а3), (а3,а1), (а3,а4), (а4,а3); (а4,а2), (а2,а4), (а3,а3)}.