Слайд 2
![Рассмотрим два множества X ={x1, x2 ,...,xn} и Y ={y1, y2 ,..., ym}](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-1.jpg)
Рассмотрим два множества
X ={x1, x2 ,...,xn} и Y ={y1, y2
,..., ym}
Слайд 3
![Соответствие q представляет собой тройку множеств q = (X,Y,Q), где](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-2.jpg)
Соответствие q представляет собой
тройку множеств q = (X,Y,Q), где X и
Y –
это множества, элементы которых
сопоставляются
Слайд 4
![Множество Q X×Y определяет закон, по которому осуществляется соответствие ,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-3.jpg)
Множество Q X×Y определяет закон,
по которому осуществляется
соответствие , т.е. перечисляет все
пары,
участвующие в сопоставлении.
Слайд 5
![Для каждого q = (X, Y, Q) можно указать обратное](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-4.jpg)
Для каждого q = (X, Y, Q) можно указать
обратное соответствие q-1
= (X,Y,Q-1), где
Q-1 = Y×X.
Слайд 6
![](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-5.jpg)
Слайд 7
![Обратное соответствие обратного соответствия даст прямое соответствие (q-1)-1 = q.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-6.jpg)
Обратное соответствие обратного
соответствия даст прямое соответствие
(q-1)-1 = q.
Слайд 8
![Соответствие называется взаимно однозначным, если каждому элементу множества X соответствует](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-7.jpg)
Соответствие называется взаимно
однозначным, если каждому элементу
множества X соответствует (поставлен в
пару с
ним) единственный элемент
множества Y и обратно.
Если между X и Y установлено
взаимно однозначное соответствие, то
они имеют поровну элементов.
Слайд 9
![Отображения Отображение является частным случаем соответствия (однозначное соответствие). Соответствие, характеризующее](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-8.jpg)
Отображения
Отображение является частным
случаем соответствия (однозначное
соответствие).
Соответствие, характеризующее
правило, по которому каждому элементу
множества
X сопоставляется один или
несколько элементов множества Y,
называется отображением и
записывается как Г: X→Y , где
множество Г определяет закон
отображения.
Слайд 10
![Пусть X = {х1, х2, х3}; Y = {у1, у2, у3, у4, у5, у6}.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-9.jpg)
Пусть
X = {х1, х2, х3}; Y = {у1, у2, у3,
у4, у5, у6}.
Слайд 11
![Каждому элементу xi x отображение Г ставит в соответствие некоторое](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-10.jpg)
Каждому элементу xi x отображение Г
ставит в соответствие некоторое
подмножество Г Y
, называемое
образом элемента х:
Гx1 = {y1, y2}, Гx2 = {y3}, Гx3 = {y4, y5, y6}.
Слайд 12
![Отображение называется сюръективным (или отображением "на"), если образы точек множества](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-11.jpg)
Отображение называется сюръективным (или отображением "на"), если образы точек множества X
заполняют все множество Y, причем различные точки множества X могут иметь один и тот же образ.
Слайд 13
![](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-12.jpg)
Слайд 14
![Отображение называется инъективным (или отображением "в"), если элементы множества X](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-13.jpg)
Отображение называется инъективным (или отображением "в"), если элементы множества X отображаются
не на все множество Y, а в его какую-то часть.
Слайд 15
![](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-14.jpg)
Слайд 16
![Биективное отображение является одновременно инъективным и сюръективным, т.е. является взаимно однозначным.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-15.jpg)
Биективное отображение является одновременно инъективным и сюръективным, т.е. является взаимно однозначным.
Слайд 17
![Важным случаем отображения является отображение элементов внутри одного множества. При](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-16.jpg)
Важным случаем отображения является отображение элементов внутри одного множества.
При этом
отображение Г: Х→Х будет определяться парой (X, Г),
где Г Х×Х или Г Х 2.
Слайд 18
![С помощью отображений могут быть даны определения таким понятиям, как функция, функционал, оператор.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-17.jpg)
С помощью отображений могут быть даны определения таким понятиям, как функция,
функционал, оператор.
Слайд 19
![Если отображение Г: X→Y рассматривается как соответствие между множествами X](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-18.jpg)
Если отображение Г: X→Y рассматривается как соответствие между множествами X и
Y, то множество f ={(x, y) X Y : y = f (x)} называется функцией.
Слайд 20
![Таким образом, f является множеством, элементами которого являются пары (х,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-19.jpg)
Таким образом, f является множеством, элементами которого являются пары
(х, у),
участвующие в соответствии, и f(x) является обозначением для y Y , соответствующего данному x X.
Слайд 21
![Произвольное подмножество множества А1 x А2 x…x Аn. называется отношением,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-20.jpg)
Произвольное подмножество множества А1 x А2 x…x Аn.
называется отношением, заданным или
определенным на множествах
А1, А2,…, Аn.
Слайд 22
![элементы (где ) связаны отношением R тогда и только тогда,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-21.jpg)
элементы
(где )
связаны отношением R тогда и только
тогда, когда
,
а –
упорядоченный набор из n элементов.
Слайд 23
![Бинарным отношением (соответствием) R из A в B называется подмножество](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-22.jpg)
Бинарным отношением (соответствием) R из A в B называется подмножество декартового
произведения множеств A × B.
R A × B.
Слайд 24
![Если (а,b) R, это записывается как aRb; при этом говорят,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-23.jpg)
Если (а,b) R, это записывается
как aRb;
при этом говорят, что
а и b находятся в отношении R, или просто,
что а относится к b.
Слайд 25
![Примером отношений могут служить такие понятия: как "меньше, чем", "делится](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-24.jpg)
Примером отношений могут служить такие понятия:
как "меньше, чем",
"делится на",
"включено в",
"больше
чем" и т.д.
Слайд 26
![Примеры отношений: а) соответствие между множеством отпечатков пальцев A =](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-25.jpg)
Примеры отношений:
а) соответствие между множеством отпечатков пальцев A = {a, b,
c} и множеством подозреваемых
B = {Иванов, Петров}.
б) все множество A × B есть отношение множеств А и В.
Слайд 27
![в) пусть А – множество товаров в магазине, а В](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-26.jpg)
в) пусть А – множество товаров в магазине, а В –
множество действительных чисел.
Тогда {(х,у) A × B: у – цена х} – отношение множеств А и В.
Слайд 28
![г) пусть А – множество женщин, а В – множество](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-27.jpg)
г) пусть А – множество женщин, а
В – множество мужчин,
тогда {(х,у) A × B: у является мужем х} есть отношение А и В.
д) если А – множество людей,
то {(х,у) A × А: у является родственником х} есть отношение на А.
Слайд 29
![е) если А = {1,2,3},а В = {r, s}, так](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-28.jpg)
е) если А = {1,2,3},а В = {r, s},
так что
A × B = {(1,r), (1,s), (2,r), (2,s), (3,r), (3,s)},
тогда R = {(1,r), (1,s), (3,s)}
есть отношение множеств А и В.
Слайд 30
![Пример](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-29.jpg)
Слайд 31
![Подмножество R декартового произведения множеств A1 A2 … An называется отношением степени n (n-арным отношением).](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-30.jpg)
Подмножество R декартового произведения множеств
A1 A2 … An называется отношением
степени n
(n-арным отношением).
Слайд 32
![Если А1=А2=А3=…=Аn, то декартово произведение A1 A2 … An называется](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-31.jpg)
Если А1=А2=А3=…=Аn, то декартово произведение A1 A2 … An
называется декартовым
произведением n-й степени множества А(Аn), а отношение R, заданное на множествах А1, А2,…Аn – n –арным отношением на множестве А.
Слайд 33
![Обобщенное понятие отношения: n-местное отношение R – множество упорядоченных наборов](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-32.jpg)
Обобщенное понятие отношения: n-местное отношение R – множество упорядоченных наборов
Слайд 34
![Пример Отношение круг радиуса 1 с центром в начале координат,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-33.jpg)
Пример
Отношение
круг радиуса 1 с центром в начале координат, то есть множество
точек плоскости, координаты которых удовлетворяют неравенству
задает отношение между осью абсцисс и осью ординат.
Слайд 35
![Пример Если A –конечное, то отношение задают списком пар.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-34.jpg)
Пример
Если A –конечное, то отношение задают списком пар.
Слайд 36
![Бинарное отношение можно задавать матрицей , элементы которой равны: единице,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-35.jpg)
Бинарное отношение можно задавать матрицей , элементы которой равны:
единице, если пара
принадлежит отношению R,
нулю, если пара не принадлежит отношению.
Слайд 37
![Пример отношения заданного матрицей](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-36.jpg)
Пример отношения заданного матрицей
Слайд 38
![Любая матрица размерности является матрицей бинарного отношения между множествами А и В, мощность которых](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-37.jpg)
Любая матрица размерности
является матрицей бинарного отношения между множествами А и
В, мощность которых
Слайд 39
![Отношение между двумя элементами называется бинарным, или двухместным, между тремя-тернарным,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-38.jpg)
Отношение между двумя элементами называется бинарным, или двухместным, между тремя-тернарным, или
трехместным, между n элементами n–нарным, или n–местным.
Слайд 40
![Мощность множества кортежей, входящих в отношение R, называют мощностью отношения R.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-39.jpg)
Мощность множества кортежей, входящих в отношение R, называют мощностью отношения R.
Слайд 41
![](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-40.jpg)
Слайд 42
![Свяжем с каждым бинарным отношением R между А и В](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-41.jpg)
Свяжем с каждым бинарным отношением R между А и В
область
определения D(R) и
область значений (R) .
Они определяются следующим образом.
Слайд 43
![Область определения отношения R на А и В есть множество](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-42.jpg)
Область определения отношения R на А и В есть множество всех
х А таких, что для некоторых у В
имеем (х,у) R. Другими словами, область определения R есть множество всех первых координат упорядоченных пар из R.
Слайд 44
![Область значений отношения R на А и В есть множество](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-43.jpg)
Область значений отношения R на
А и В есть множество всех
у В таких, что для некоторых х А имеем
(х,у) R. Другими словами, область значений R есть множество всех вторых координат упорядоченных пар из R.
Слайд 45
![Пример](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-44.jpg)
Слайд 46
![](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-45.jpg)
Слайд 47
![С каждым отношением R на А В связано отношение R-1 на В А.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-46.jpg)
С каждым отношением R на А В связано отношение R-1 на
В А.
Слайд 48
![Пусть R А В есть отношение на А В. Тогда](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-47.jpg)
Пусть R А В
есть отношение на А В.
Тогда отношение
R-1 на В А
определяется
следующим образом:
R-1 = {(b,a): (а,b) R}.
Слайд 49
![Другими словами (b,a) R-1 , тогда и только тогда, когда](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-48.jpg)
Другими словами (b,a) R-1 , тогда и только тогда, когда (а,b)
R.
Отношение R-1 называется
обратным отношением к данному отношению R.
Слайд 50
![Пример: R = {(x,y) | x,y N & y=x2} –](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-49.jpg)
Пример:
R = {(x,y) | x,y N & y=x2} – отношение
на
множестве натуральных чисел N.
Если R – отношение возведения
натуральных чисел в квадрат, то R-1 –
извлечение квадратного корня.
Слайд 51
![Термин «реляционное представление данных», впервые введенный Коддом, происходит от термина relation.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-50.jpg)
Термин «реляционное представление данных», впервые введенный Коддом, происходит от термина relation.
Слайд 52
![Во-первых, все элементы отношения есть однотипные кортежи. Например, рассмотрим отношение,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-51.jpg)
Во-первых, все элементы отношения есть однотипные кортежи. Например, рассмотрим отношение, состоящее
из трех следующих кортежей
{(1, «Иванов», 1000), (2, «Петров», 2000), (3, «Сидоров», 3000)}.
Слайд 53
![Однотипность кортежей позволяет считать их аналогами строк в простой таблице,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-52.jpg)
Однотипность кортежей позволяет считать их аналогами строк в простой таблице, т.е.
в такой таблице, в которой все строки состоят из одинакового числа ячеек и в соответствующих ячейках содержатся одинаковые типы данных.
Слайд 54
![Множество {(1), (1, 2), (1, 2, 3)}, состоит из разнотипных](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-53.jpg)
Множество {(1), (1, 2), (1, 2, 3)}, состоит из разнотипных числовых
кортежей. Это множество не является отношением ни в R, ни в R2, ни в R3. Из кортежей, входящих в это множество, нельзя составить простую таблицу.
Слайд 55
![Во-вторых. За исключением крайнего случая, когда отношение есть само декартово](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-54.jpg)
Во-вторых. За исключением крайнего случая, когда отношение есть само декартово произведение
A1 A2 … An,
отношение включает в себя не все возможные кортежи из декартового произведения.
Слайд 56
![Для каждого отношения имеется критерий, позволяющий определить, какие кортежи входят](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-55.jpg)
Для каждого отношения имеется критерий, позволяющий определить, какие кортежи входят в
отношение, а какие - нет.
Этот критерий, по существу, определяет для смысл (семантику) отношения.
Слайд 57
![Каждому отношению можно поставить в соответствие некоторое логическое выражение P(x1,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-56.jpg)
Каждому отношению можно поставить в соответствие некоторое логическое выражение P(x1, x2,
…, xn), зависящее от n параметров (n-местный предикат) и определяющее, будет ли кортеж
(a1, a2, …, an) принадлежать отношению R.
Это логическое выражение называют предикатом отношения R.
Слайд 58
![Кортеж (a1, a2, …, an) принадлежит отношению R тогда и](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-57.jpg)
Кортеж (a1, a2, …, an) принадлежит отношению R тогда и только
тогда, когда предикат этого отношения
P(a1, a2, …, an) принимает значение «истина».
Слайд 59
![Каждый n-местный предикат задает некоторое n-арное отношение. Таким образом, существует](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-58.jpg)
Каждый n-местный предикат задает некоторое n-арное отношение.
Таким образом, существует взаимно
однозначное соответствие между
n-арными отношениями и n-местными предикатами.
Слайд 60
![основные свойства отношений](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-59.jpg)
основные свойства отношений
Слайд 61
![тождественность, рефлексивность, антирефлексивность, симметричность, антисимметричность, транзитивность.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-60.jpg)
тождественность,
рефлексивность,
антирефлексивность,
симметричность,
антисимметричность,
транзитивность.
Слайд 62
![Отношение R называется тождественным на множестве A, если, оно состоит](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-61.jpg)
Отношение R называется тождественным на множестве A, если, оно состоит из
всех пар вида (а,а), где
а А, и обозначается iА или просто i.
Пары вида (а,а) называются диагональными.
Например, "получают повышенную стипендию" и "сдали сессию на хорошо и отлично" на множестве студентов факультета.
Слайд 63
![Отношение R называется рефлексивными на множестве А, если для всех](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-62.jpg)
Отношение R называется рефлексивными на множестве А, если для всех а
А справедливо аRа или (а,а) R на множестве А.
Например, "равенство", ''самообслуживание".
Студент х – ровесник студента у. (iА R, т.е. включает диагональ).
Слайд 64
![Отношение R называется антирефлексивным, если для всех а А не](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-63.jpg)
Отношение R называется антирефлексивным, если для всех
а А не выполняется
аRа т.е. (а,а) R. Другими словами, если (а,b) R, следует, а≠b.
Например, "строгое неравенство", "быть старше", т.е. отношения, которые могут выполняться только для несовпадающих объектов. (А А)
Слайд 65
![Отношение R называется симметричным на множестве А, если для каждой](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-64.jpg)
Отношение R называется симметричным на множестве А, если для каждой пары
а и b А справедливо соотношение: если аRb, тo bRa или если (a,b) R, то (b,a) R. Например, "расстояние между двумя точками", "быть братом". Студент х является соседом по парте студента у. (R R-1).
Слайд 66
![Отношение R называется антисимметричным на множестве А, если для каждой](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-65.jpg)
Отношение R называется антисимметричным на множестве А, если для каждой пары
а и b А справедливо соотношение: если из аRb и bRa следует a=b.
Например, множество А является подмножеством множества В.
(R R-1 iА).
Слайд 67
![Отношение R называется транзитивным на множестве А, если для любой](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-66.jpg)
Отношение R называется транзитивным на множестве А, если для любой тройки
а,b,c А справедливо соотношение: если аRb и bRc, то aRc.
Например, "параллельность", "больше чем". Город х связан с городом у шоссейной дорогой. (R2 R).
Слайд 68
![Примеры: Рассмотрим следующее отношение «х делит у на множестве натуральных чисел».](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-67.jpg)
Примеры:
Рассмотрим следующее отношение
«х делит у на множестве натуральных чисел».
Слайд 69
![Отношение рефлексивно, так как х всегда делит сам себя. Отношение](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-68.jpg)
Отношение рефлексивно, так как х всегда делит сам себя.
Отношение не симметрично,
так как 2 является делителем, но не наоборот: 6 не делит 2.
Слайд 70
![Предположим, что х делит у, а у в свою очередь](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-69.jpg)
Предположим, что х делит у, а у в свою очередь делит
z.
Тогда из первого предположения следует, что у = m*х для некоторого натурального числа m, а из второго –
z = n*у, где n – натуральное число. Следовательно, z = n*у = (n*m)*х, т.е.
х делит z.
Значит данное отношение транзитивно.
Слайд 71
![Отношение антисимметрично, так как если из предположения х делит у](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-70.jpg)
Отношение антисимметрично, так как если из предположения х делит у и
у делит х вытекает, что х = у.
Слайд 72
![Рассмотрим следующее отношение: «количество лет х совпадает с возрастом у» на множестве всех людей».](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-71.jpg)
Рассмотрим следующее отношение: «количество лет х совпадает с возрастом у» на
множестве всех людей».
Слайд 73
![Отношение рефлексивно, так как возраст любого человека совпадает с количеством прожитых им лет.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-72.jpg)
Отношение рефлексивно, так как возраст любого человека совпадает с количеством прожитых
им лет.
Слайд 74
![Отношение симметрично, так как высказывание «количество лет х совпадает с](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-73.jpg)
Отношение симметрично, так как высказывание «количество лет х совпадает с возрастом
у» на множестве всех людей» равносильно высказыванию «количество лет у совпадает с возрастом х» на множестве всех людей.
Слайд 75
![Отношение транзитивно, так как если найдутся такие три человека х,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-74.jpg)
Отношение транзитивно, так как если найдутся такие три человека х, у,
z, что «количество лет х совпадает с возрастом у», «количество лет у совпадает с возрастом z», то все трое будут одинакового возраста.
Слайд 76
![Отношение антисимметрично, так как из высказывания высказывание «количество лет х](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-75.jpg)
Отношение антисимметрично, так как из высказывания высказывание «количество лет х совпадает
с возрастом у» и «количество лет у совпадает с возрастом х», следует, что х = у.
Слайд 77
![Пусть А = {1,2,3,4,5,6}, R А А R = {(1,1),](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-76.jpg)
Пусть А = {1,2,3,4,5,6},
R А А
R = {(1,1), (2,2),
(3,3), (4,4), (5,5), (6,6), (1,2), (1,4),(2,1), (2,4), (3,5), (5,3), (4,1), (4,2)}.
Слайд 78
![Отношение R рефлексивно, так как для каждого а А, (а,а)](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-77.jpg)
Отношение R рефлексивно,
так как для каждого а А, (а,а) R.
{(1,1), (2,2), (3,3), (4,4), (5,5), (6,6)}.
Слайд 79
![Отношение R симметрично так как, R = {(1,1), (2,2), (3,3),](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-78.jpg)
Отношение R симметрично так как,
R = {(1,1), (2,2), (3,3), (4,4),
(5,5), (6,6), (1,2), (1,4),(2,1), (2,4), (3,5), (5,3), (4,1), (4,2)}.
Слайд 80
![Отношение транзитивно,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-79.jpg)
Слайд 81
![Отношение R не является антисимметричным, так как, R = {(1,1),](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-80.jpg)
Отношение R не является
антисимметричным, так как,
R = {(1,1), (2,2), (3,3),
(4,4), (5,5), (6,6), (1,2), (1,4),(2,1), (2,4), (3,5), (5,3), (4,1), (4,2)}.
Слайд 82
![Пусть А = {♠, ♣, ♥, ♦} , R А](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-81.jpg)
Пусть А = {♠, ♣, ♥, ♦} ,
R А А
R = {(♠,♠), (♠,♣), (♠,♦), (♣,♠), (♦,♠),(♦,♦), (♥,♦), (♥,♥)}.
Слайд 83
![Отношение не рефлексивно, так как ♣ A, но (♣,♣) A , R = {(♠,♠), (♦,♦), (♥,♥)}.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-82.jpg)
Отношение не рефлексивно,
так как ♣ A, но (♣,♣) A ,
R
= {(♠,♠), (♦,♦), (♥,♥)}.
Слайд 84
![Отношение не симметрично, так как R = {(♠,♠), (♠,♣), (♠,♦), (♣,♠), (♦,♠),(♦,♦), (♥,♦), (♥,♥)}](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-83.jpg)
Отношение не симметрично, так как
R = {(♠,♠), (♠,♣), (♠,♦), (♣,♠),
(♦,♠),(♦,♦), (♥,♦), (♥,♥)}
Слайд 85
![Отношение не является антисимметричным, так как R = {(♠,♠), (♠,♣), (♠,♦), (♣,♠), (♦,♠),(♦,♦), (♥,♦), (♥,♥)}](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-84.jpg)
Отношение не является антисимметричным, так как
R = {(♠,♠), (♠,♣), (♠,♦),
(♣,♠), (♦,♠),(♦,♦), (♥,♦), (♥,♥)}
Слайд 86
![Отношение не является транзитивным, так как R = {(♠,♠), (♠,♣), (♠,♦), (♣,♠), (♦,♠),(♦,♦), (♥,♦), (♥,♥)}](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-85.jpg)
Отношение не является транзитивным,
так как R = {(♠,♠), (♠,♣), (♠,♦),
(♣,♠), (♦,♠),(♦,♦), (♥,♦), (♥,♥)}
Слайд 87
![Замыкание отношений](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-86.jpg)
Слайд 88
![Если отношение R на множестве А не обладает тем или](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-87.jpg)
Если отношение R на множестве А не обладает тем или иным
свойством, то его стоит попытаться продолжить до отношения R*, которое будет иметь нужное свойство.
Слайд 89
![Под продолжением понимается присоединение некоторых упорядоченных пар к подмножеству](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-88.jpg)
Под продолжением понимается присоединение некоторых упорядоченных пар к подмножеству
Слайд 90
![Новое полученное множество R* уже будет обладать требуемым свойством. Исходное множество R будет подмножеством R*.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-89.jpg)
Новое полученное множество R* уже будет обладать требуемым свойством. Исходное множество
R будет подмножеством R*.
Слайд 91
![Если вновь построенное множество R* будет минимальным среди всех расширений](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-90.jpg)
Если вновь построенное множество R* будет минимальным среди всех расширений R
с выделенным свойством, то R* является замыканием R относительно данного свойства.
Слайд 92
![Рефлексивное замыкание R есть наименьшее рефлексивное отношение на A, содержащее R как подмножество.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-91.jpg)
Рефлексивное замыкание R есть наименьшее рефлексивное отношение на A, содержащее R
как подмножество.
Слайд 93
![Рефлексивным замыканием Ri отношения R называется отношение , где i – отношение тождества на А (диагональ).](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-92.jpg)
Рефлексивным замыканием Ri отношения R
называется отношение
, где i – отношение
тождества на А (диагональ).
Слайд 94
![Симметричное замыкание R наименьшее симметричное отношение на A, содержащее R как подмножество.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-93.jpg)
Симметричное замыкание R наименьшее симметричное отношение на A, содержащее R как
подмножество.
Слайд 95
![Симметричным замыканием Rs отношения R называется отношение т.е. если (а,b)](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-94.jpg)
Симметричным замыканием Rs
отношения R называется отношение
т.е. если (а,b) R,
то
(а,b) Rs и (b,a) Rs
Слайд 96
![Транзитивное замыкание R наименьшее транзитивное отношение на A, содержащее R как подмножество.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-95.jpg)
Транзитивное замыкание R наименьшее транзитивное отношение на A, содержащее R как
подмножество.
Слайд 97
![Транзитивным замыканием Rt отношения R называется отношение т.е. (а,b) Rt](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-96.jpg)
Транзитивным замыканием Rt отношения R называется отношение
т.е. (а,b) Rt тогда
и только тогда, когда существуют элементы такие что а1Rа2, а2Rа3, …, аn-1Rаn.
Слайд 98
![Пример А = {1,2,3}, отношение R на А задано упорядоченными](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-97.jpg)
Пример
А = {1,2,3}, отношение R на А задано упорядоченными парами
R
= {(1,1), (1,2), (1,3), (3,1), (2.3)}. Отношение R не рефлексивно, не симметрично, не транзитивно.
Найти соответствующие замыкания.
Слайд 99
![Замыкание относительно рефлексивности должно содержать все пары вида (а,а). Поэтому,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-98.jpg)
Замыкание относительно рефлексивности должно содержать все пары вида (а,а). Поэтому, искомое
замыкание имеет вид:
Добавленные пары отделены от исходных пар точкой с запятой.
Слайд 100
![Замыкание относительно симметричности должно содержать все пары, симметричные исходным.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-99.jpg)
Замыкание относительно симметричности должно содержать все пары, симметричные исходным.
Слайд 101
![Замыкание относительно транзитивности. Необходимо выполнить несколько шагов. Отношение R =](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-100.jpg)
Замыкание относительно транзитивности.
Необходимо выполнить несколько шагов.
Отношение R = {(1,1), (1,2),
(1,3), (3,1),(2.3)}:
содержит пары (3,1) и (1,2), замыкание
обязано включать пару (3,2);
содержит пары (2,3) и (3,1) замыкание
обязано включать пару (2,1);
содержит пары (3,1) и (1,3) замыкание
обязано включать пару (3,3);
Добавим эти пары.
Слайд 102
![](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-101.jpg)
Слайд 103
![Появились пары (2,1) и (1,2). Следовательно, замыкание R* должно содержать пару (2,2). Все необходимые пары перебрали.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-102.jpg)
Появились пары (2,1) и (1,2).
Следовательно, замыкание R* должно
содержать пару (2,2).
Все необходимые
пары перебрали.
Слайд 104
![](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-103.jpg)
Слайд 105
![Пусть А = {а1, а2, а3,а4}, R = {(а1,а3), (а3,а4), (а4,а2), (а3,а3)}.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-104.jpg)
Пусть А = {а1, а2, а3,а4},
R = {(а1,а3), (а3,а4), (а4,а2),
(а3,а3)}.
Слайд 106
![Ri = {(а1,а3), (а3,а4), (а4,а2), (а3,а3); (а1,а1), (а2,а2), (а4,а4)}.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-105.jpg)
Ri = {(а1,а3), (а3,а4), (а4,а2), (а3,а3); (а1,а1), (а2,а2), (а4,а4)}.
Слайд 107
![Rs = {(а1,а3), (а3,а1), (а3,а4), (а4,а3); (а4,а2), (а2,а4), (а3,а3)}.](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/367771/slide-106.jpg)
Rs = {(а1,а3), (а3,а1), (а3,а4), (а4,а3); (а4,а2), (а2,а4), (а3,а3)}.