Математические отношения - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Математические отношения. Доклад-сообщение содержит 110 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

ОТНОШЕНИЯ

Слайд 2

Описание слайда:

Введение Когда говорят о родстве двух человек, Ивана и Анны, то подразумевают, что есть некая семья, к членам которой они относятся. Упорядоченная пара (Иван, Анна) отличается от других упорядоченных пар людей тем, что между Иваном и Анной есть некое родство (кузина, отец, и т. д.).

Слайд 3

Описание слайда:

В математике среди всех упорядоченных пар прямого произведения А В двух множеств А и В тоже выделяются некоторые пары в связи с тем, что между их компонентами есть некоторые «родственные» отношения, которых нет у других. В математике среди всех упорядоченных пар прямого произведения А В двух множеств А и В тоже выделяются некоторые пары в связи с тем, что между их компонентами есть некоторые «родственные» отношения, которых нет у других. В качестве примера рассмотрим множество S студентов какого-нибудь института и множество К читаемых там курсов.

Слайд 4

Описание слайда:

В прямом произведении S К можно выделить большое подмножество упорядоченных пар (s, k), обладающих свойством: студент s слушает курс k. Построенное подмножество отражает отношение «... слушает ...», естественно возникающее между множествами студентов и курсов. В прямом произведении S К можно выделить большое подмножество упорядоченных пар (s, k), обладающих свойством: студент s слушает курс k. Построенное подмножество отражает отношение «... слушает ...», естественно возникающее между множествами студентов и курсов.

Слайд 5

Описание слайда:

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

Слайд 6

Описание слайда:

Отношения между элементами нескольких множеств задаются в виде таблиц данных. Такие n-арные отношения применяются, например, для описания систем управления базами данных. Отношения между элементами нескольких множеств задаются в виде таблиц данных. Такие n-арные отношения применяются, например, для описания систем управления базами данных.

Слайд 7

Описание слайда:

Бинарные отношения Бинарным отношением между множествами А и В называется подмножество R прямого произведения А В. В том случае, когда А = В, мы говорим просто об отношении R на А.

Слайд 8

Описание слайда:

Пример 4.1. Рассмотрим генеалогическое древо, изображенное на рис. 4.1. Пример 4.1. Рассмотрим генеалогическое древо, изображенное на рис. 4.1. Выпишите упорядоченные пары, находящиеся в следующих отношениях на множестве Р членов этой семьи: (а) R = { (х, у): х — дедушка у }; (б) S = { (х, у): х — сестра у }.

Слайд 9

Описание слайда:

Слайд 10

Описание слайда:

Решение. Решение. (а) R содержит упорядоченные пары: (Фред, Джейн), (Фред, Фиона), (Фред, Алан), (Джон, Джейн), (Джон, Фиона) и (Джон, Алан). (б) S состоит из пар: (Сью, Пенни), (Пенни, Сью), (Джейн, Фиона), (Фиона, Джейн), (Элис, Кен), (Сью, Майк), (Пенни, Майк), (Джейн, Алан) и (Фиона, Алан).

Слайд 11

Описание слайда:

Пример 4.2. Выпишите упорядоченные пары, принадлежащие следующим бинарным отношениям на множествах А = {1, 3, 5, 7} и В = {2, 4, 6}: Пример 4.2. Выпишите упорядоченные пары, принадлежащие следующим бинарным отношениям на множествах А = {1, 3, 5, 7} и В = {2, 4, 6}: (а) U = {(x, у): х + у = 9}; (б) V = {(x, y): x < y}. Решение. (а) U состоит из пар: (3, 6), (5, 4) и (7, 2); (б) V = {(1, 2), (1, 4), (1, 6), (3, 4), (3, 6), (5, 6)}.

Слайд 12

Описание слайда:

Пример 4.3. Множество Пример 4.3. Множество R = {(x, у): х — делитель у} определяет отношение на множестве А = {1, 2, 3, 4, 5, 6}. Найдите все упорядоченные пары, ему принадлежащие. Решение. R состоит из пар: (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 2), (2, 4), (2, 6), (3, 3), (3, 6), (4, 4), (5, 5) и (6, 6).

Слайд 13

Описание слайда:

Теперь мы познакомимся с двумя более удобными способами перечисления упорядоченных пар, принадлежащих данному отношению. Теперь мы познакомимся с двумя более удобными способами перечисления упорядоченных пар, принадлежащих данному отношению. Первый из них основан на понятии «ориентированный граф», а второй опирается на понятие матрицы.

Слайд 14

Описание слайда:

Пусть А и В — два конечных множества и R — бинарное отношение между ними. Пусть А и В — два конечных множества и R — бинарное отношение между ними. Мы изобразим элементы этих множеств точками на плоскости. Для каждой упорядоченной пары отношения R нарисуем стрелку, соединяющую точки, представляющие компоненты пары. Такой объект называется ориентированным графом или орграфом, точки же, изображающие элементы множеств, принято называть вершинами графа.

Слайд 15

Описание слайда:

В качестве примера рассмотрим отношение V между множествами А = {1, 3, 5, 7} и В = {2, 4, 6} из примера 4.2 (б): V = {(x, y): x < y}. В качестве примера рассмотрим отношение V между множествами А = {1, 3, 5, 7} и В = {2, 4, 6} из примера 4.2 (б): V = {(x, y): x < y}. Соответствующий ориентированный граф показан на рис. 4.2. Для иллюстрации отношения на отдельном множестве А мы чертим орграф, чьи вершины соответствуют одному лишь множеству A, а стрелки, как обычно, соединяют элементы упорядоченных пар, находящихся в отношении.

Слайд 16

Описание слайда:

Слайд 17

Описание слайда:

Пример 4.4. Изобразите граф, представляющий отношение R из примера 4.3: R = {(x, у): х — делитель у} определяет отношение на множестве А = {1, 2, 3, 4, 5, 6}. Пример 4.4. Изобразите граф, представляющий отношение R из примера 4.3: R = {(x, у): х — делитель у} определяет отношение на множестве А = {1, 2, 3, 4, 5, 6}. Решение. Поскольку R — отношение на множестве А = {1, 2, 3, 4, 5, 6}, то ориентированный граф будет иметь шесть вершин. Он приведен на рис. 4.3.

Слайд 18

Описание слайда:

Слайд 19

Описание слайда:

Второй способ задания бинарного отношения на конечных множествах основан на использовании таблиц. Второй способ задания бинарного отношения на конечных множествах основан на использовании таблиц. Предположим, что мы хотим определить бинарное отношение R между множествами А и В. Необходимо обозначить элементы множеств и выписать их в каком-нибудь порядке. Сделаем это так: A = {a1, a2, …, an}, B = {b1, b2, …, bm}.

Слайд 20

Описание слайда:

Для определения отношения R заполним таблицу M с n строками и т столбцами. Для определения отношения R заполним таблицу M с n строками и т столбцами. Строки «перенумеруем» элементами множества А, а столбцы — элементами множества B в соответствии с порядком, в котором мы выписали элементы.

Слайд 21

Описание слайда:

Слайд 22

Описание слайда:

В этих терминах отношение U из примера 4.2(а): А = {1, 3, 5, 7} и В = {2, 4, 6}, U = {(x, у): х + у = 9} (т.е. U состоит из пар: (3, 6), (5, 4) и (7, 2)) В этих терминах отношение U из примера 4.2(а): А = {1, 3, 5, 7} и В = {2, 4, 6}, U = {(x, у): х + у = 9} (т.е. U состоит из пар: (3, 6), (5, 4) и (7, 2)) с помощью матрицы задается следующим образом:

Слайд 23

Описание слайда:

Пример 4.5. Отношение R на множестве А = { а, b, с, d } задается матрицей: Пример 4.5. Отношение R на множестве А = { а, b, с, d } задается матрицей: , порядок строк и столбцов в которой соответствует порядку выписанных элементов множества А. Назовите упорядоченные пары, принадлежащие R. Решение. Отношение R содержит упорядоченные пары: (а, b), (а, с), (b, с), (b, d), (с, b), (d, а), (d, b) и (d, d).

Слайд 24

Описание слайда:

Пример 4.6. Выпишите матрицу, представляющую отношение R из примера 4.3: R = {(x, у): х — делитель у} определяет отношение на множестве А = {1, 2, 3, 4, 5, 6}. R состоит из пар: (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 2), (2, 4), (2, 6), (3, 3), (3, 6), (4, 4), (5, 5) и (6, 6). Пример 4.6. Выпишите матрицу, представляющую отношение R из примера 4.3: R = {(x, у): х — делитель у} определяет отношение на множестве А = {1, 2, 3, 4, 5, 6}. R состоит из пар: (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 2), (2, 4), (2, 6), (3, 3), (3, 6), (4, 4), (5, 5) и (6, 6). Решение. Матрица отношения R имеет вид:

Слайд 25

Описание слайда:

Если R — бинарное отношение, то вместо записи (х, у) R можно употреблять обозначение х R y. Например, предикат «х — сестра у» определяет отношение на множестве всех людей. В примере 4.3 предикат «х — делитель у» дает ясное словесное описание еще одного отношения. Если R — бинарное отношение, то вместо записи (х, у) R можно употреблять обозначение х R y. Например, предикат «х — сестра у» определяет отношение на множестве всех людей. В примере 4.3 предикат «х — делитель у» дает ясное словесное описание еще одного отношения.

Слайд 26

Описание слайда:

Подводя итог этой части теории отношений, напомним, что бинарное отношение между конечными множествами может быть задано одним из следующих способов: Подводя итог этой части теории отношений, напомним, что бинарное отношение между конечными множествами может быть задано одним из следующих способов: словами (с помощью подходящих предикатов); как множество упорядоченных пар; как орграф; как матрица.

Слайд 27

Описание слайда:

Пример 4.7. Отношение R на множестве А = { 1, 2, 3, 4 } представлено графом на рис. 4.3. Пример 4.7. Отношение R на множестве А = { 1, 2, 3, 4 } представлено графом на рис. 4.3. Перечислите упорядоченные пары, принадлежащие A, выпишите соответствующую матрицу и определите это отношение с помощью предикатов.

Слайд 28

Описание слайда:

Решение. В терминах упорядоченных пар R = {(2, 1), (3, 2), (4, 3)}. Матрица (относительно данного в условии порядка элементов множества) имеет вид: Решение. В терминах упорядоченных пар R = {(2, 1), (3, 2), (4, 3)}. Матрица (относительно данного в условии порядка элементов множества) имеет вид: С помощью предикатов данное отношение может быть описано как x - у = 1.

Слайд 29

Описание слайда:

Свойства отношений Ограничимся рассмотрением бинарных отношений, заданных на одном множестве и введем некоторый набор их свойств.

Слайд 30

Описание слайда:

Говорят, что отношение R на множестве А Говорят, что отношение R на множестве А рефлексивно, если для всех х A x R x; симметрично, если x R y y R x для каждой пары х и у из A; кососимметрично, если (х R y и y R x x = у) для всех x и у из А; транзитивно, если (х R у и у R z х R z) для любой тройки элементов x, у, z A.

Слайд 31

Описание слайда:

В терминах упорядоченных пар эти свойства определяются следующим образом. Данное отношение R рефлексивно, если (x, х) R для любого возможного значения переменной х; симметрично, если из включения (x, у) R следует, что (у, х) R; кососимметрично, если из предположений: (x, у) R и х у вытекает, что (у, х) R; транзитивно, если включения (x, у) R и (у, z) R влекут (x, z) R. В терминах упорядоченных пар эти свойства определяются следующим образом. Данное отношение R рефлексивно, если (x, х) R для любого возможного значения переменной х; симметрично, если из включения (x, у) R следует, что (у, х) R; кососимметрично, если из предположений: (x, у) R и х у вытекает, что (у, х) R; транзитивно, если включения (x, у) R и (у, z) R влекут (x, z) R.

Слайд 32

Описание слайда:

У ориентированного графа, изображающего рефлексивное отношение, каждая вершина снабжена петлей, т.е. стрелкой, начинающейся и заканчивающейся в одной и той же вершине. У ориентированного графа, изображающего рефлексивное отношение, каждая вершина снабжена петлей, т.е. стрелкой, начинающейся и заканчивающейся в одной и той же вершине. Орграф симметричного отношения вместе с каждой стрелкой из вершины х в вершину у имеет стрелку, направленную в обратную сторону: из у в х.

Слайд 33

Описание слайда:

Если отношение кососимметрично, то при наличии стрелки из вершины х в несовпадающую с ней вершину у, стрелка из у в х будет обязательно отсутствовать. Если отношение кососимметрично, то при наличии стрелки из вершины х в несовпадающую с ней вершину у, стрелка из у в х будет обязательно отсутствовать. И, наконец, орграф транзитивного отношения устроен так, что вместе со стрелками из вершины х в у и из у в z у него будет стрелка и из х в z.

Слайд 34

Описание слайда:

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

Слайд 35

Описание слайда:

Матрица М, задающая рефлексивное отношение, отличается от других тем, что каждый ее элемент, стоящий на главной диагонали (М(i, i)), равен И; матрица М симметричного отношения будет симметричной, т.е. M(i, j) = M(j, i); в матрице кососимметричного отношения выполнено условие: Матрица М, задающая рефлексивное отношение, отличается от других тем, что каждый ее элемент, стоящий на главной диагонали (М(i, i)), равен И; матрица М симметричного отношения будет симметричной, т.е. M(i, j) = M(j, i); в матрице кососимметричного отношения выполнено условие: (M(i, j) = И и i j ) M(j, i) = Л. Отличительное свойство матрицы транзитивного отношения довольно трудно сформулировать четко и наглядно.

Слайд 36

Описание слайда:

Пример 4.8. Что можно сказать о свойствах (рефлексивности, симметричности, кососимметричности и транзитивности) следующих отношений: Пример 4.8. Что можно сказать о свойствах (рефлексивности, симметричности, кососимметричности и транзитивности) следующих отношений: (а) « х делит у » на множестве натуральных чисел; (б) « x у » на множестве целых чисел; (в) « количество лет х совпадает с возрастом у » на множестве всех людей.

Слайд 37

Описание слайда:

Решение. Решение. (а) Поскольку х всегда делит сам себя, то это отношение рефлексивно. Оно, конечно, не симметрично, поскольку, например, 2 является делителем 6, но не наоборот: 6 не делит 2. Проверим, что отношение делимости транзитивно. Предположим, что х делит у, а у в свою очередь делит z. Тогда из первого предположения вытекает, что у = mx для некоторого натурального числа m, а из второго z = nу, где n — натуральное число.

Слайд 38

Описание слайда:

Следовательно, z = nу = (nт)х, т. е. х делит z. Следовательно, z = nу = (nт)х, т. е. х делит z. Значит, данное отношение транзитивно. Наконец, наше отношение кососимметрично, поскольку из предположений: х делит у и у делит х немедленно вытекает, что у = х.

Слайд 39

Описание слайда:

Решение. Решение. (б) Так как высказывание «x х» ложно, то это отношение не рефлексивно. Оно симметрично, поскольку х у тогда и только тогда, когда у х. Наше отношение не обладает свойством транзитивности, так как, например, 2 3 и 3 2, но, тем не менее, 2 = 2. Наше отношение не кососимметрично, поскольку из условий х у и у х нельзя заключить, что х = у.

Слайд 40

Описание слайда:

Решение. Решение. (в) Отношение этого пункта рефлексивно, так как возраст любого человека х совпадает с количеством прожитых им лет. Оно симметрично, поскольку высказывание «количество лет х совпадает с возрастом у» равносильно высказыванию «количество лет у совпадает с возрастом x»

Слайд 41

Описание слайда:

Отношение и транзитивно, так как, если найдутся такие три человека x, у и z, что «количество лет х совпадает с возрастом у», а «количество лет у совпадает с возрастом z», то все трое будут одинакового возраста. Отношение и транзитивно, так как, если найдутся такие три человека x, у и z, что «количество лет х совпадает с возрастом у», а «количество лет у совпадает с возрастом z», то все трое будут одинакового возраста. Так как мы можем найти много ровесников, то данное отношение не кососимметрично.

Слайд 42

Описание слайда:

Если отношение R на множестве А не обладает тем или иным свойством, то его стоит попытаться продолжить до отношения R*, которое будет иметь нужное свойство. Под «продолжением» мы понимаем присоединение некоторых упорядоченных пар к подмножеству R А А так, что новое полученное множество R* уже будет обладать требуемым свойством. Если отношение R на множестве А не обладает тем или иным свойством, то его стоит попытаться продолжить до отношения R*, которое будет иметь нужное свойство. Под «продолжением» мы понимаем присоединение некоторых упорядоченных пар к подмножеству R А А так, что новое полученное множество R* уже будет обладать требуемым свойством.

Слайд 43

Описание слайда:

Ясно, что исходное множество R будет подмножеством в R*. Ясно, что исходное множество R будет подмножеством в R*. В том случае, если вновь построенное множество R* будет минимальным среди всех расширений R с выделенным свойством, то говорят, что R* является замыканием R относительно данного свойства.

Слайд 44

Описание слайда:

Более строго, R* называется замыканием отношения R относительно свойства Р, если Более строго, R* называется замыканием отношения R относительно свойства Р, если R* обладает свойством Р; R R*; R* является подмножеством любого другого отношения, содержащего R и обладающего свойством Р.

Слайд 45

Описание слайда:

Пример 4.9. Пусть А = { 1, 2, 3 }, а отношение R на A задано упорядоченными парами: Пример 4.9. Пусть А = { 1, 2, 3 }, а отношение R на A задано упорядоченными парами: R = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3)}. Оно не рефлексивно, не симметрично и не транзитивно. Найдите соответствующие замыкания.

Слайд 46

Описание слайда:

Решение. Замыкание относительно рефлексивности должно содержать все пары вида (х, х). Поэтому, искомое замыкание имеет вид: Решение. Замыкание относительно рефлексивности должно содержать все пары вида (х, х). Поэтому, искомое замыкание имеет вид: R* = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3); (2, 2), (3, 3)}, где добавленные пары отделены от исходных точкой с запятой. Замыкание относительно симметричности должно содержать все пары, симметричные исходным. Значит, R* = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3); (2, 1), (3, 2)}.

Слайд 47

Описание слайда:

Чтобы найти замыкание относительно транзитивности, необходимо выполнить несколько шагов. Так как R содержит пары (3, 1) и (1, 2), замыкание обязано включать в себя и пару (3, 2). Аналогично, пары (2, 3) и (3, 1) добавляют пару (2, 1), а пары (3, 1) и (1, 3) — пару (3, 3). Добавим сначала эти пары: Чтобы найти замыкание относительно транзитивности, необходимо выполнить несколько шагов. Так как R содержит пары (3, 1) и (1, 2), замыкание обязано включать в себя и пару (3, 2). Аналогично, пары (2, 3) и (3, 1) добавляют пару (2, 1), а пары (3, 1) и (1, 3) — пару (3, 3). Добавим сначала эти пары: R* {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3); (3, 2), (2, 1), (3, 3)}.

Слайд 48

Описание слайда:

Теперь у нас возникло сочетание (2, 1) и (1, 2). Стало быть, замыкание R* должно содержать пару (2, 2). Теперь можно увидеть, что все необходимые пары мы добавили (хотя бы потому, что перебрали все пары из А2). Следовательно, Теперь у нас возникло сочетание (2, 1) и (1, 2). Стало быть, замыкание R* должно содержать пару (2, 2). Теперь можно увидеть, что все необходимые пары мы добавили (хотя бы потому, что перебрали все пары из А2). Следовательно, R* = {(1, 1), (1, 2), (1, 3), (3, 1), (2, 3); (3, 2), (2, 1), (3, 3), (2, 2)}.

Слайд 49

Описание слайда:

Метод, которым мы нашли замыкание по транзитивности в последнем примере 4.9, довольно специфичен. Метод, которым мы нашли замыкание по транзитивности в последнем примере 4.9, довольно специфичен. Позднее в разделе 8 мы обсудим более систематический подход, использующий алгоритм, который по матрице отношения вычисляет матрицу замыкания относительно транзитивности.

Слайд 50

Описание слайда:

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

Слайд 51

Описание слайда:

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

Слайд 52

Описание слайда:

Эквивалентные элементы (т.е. находящиеся в отношении эквивалентности), как правило, обладают какими-то общими признаками. Эквивалентные элементы (т.е. находящиеся в отношении эквивалентности), как правило, обладают какими-то общими признаками.

Слайд 53

Описание слайда:

Приведем примеры отношения эквивалентности: Приведем примеры отношения эквивалентности: Отношение «... имеет те же углы, что и ...» на множестве всех треугольников. Очевидно, что треугольники эквивалентны относительно этого отношения тогда и только тогда, когда они подобны.

Слайд 54

Описание слайда:

Отношение R, заданное условием: х R y, если и только если ху > 0 на множестве ненулевых целых чисел является отношением эквивалентности. При этом эквивалентные числа имеют одинаковый знак. Отношение R, заданное условием: х R y, если и только если ху > 0 на множестве ненулевых целых чисел является отношением эквивалентности. При этом эквивалентные числа имеют одинаковый знак. Отношение «... имеет тот же возраст, что и ...» на множестве всех людей. «Эквивалентные» люди принадлежат к одной и той же возрастной группе.

Слайд 55

Описание слайда:

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

Слайд 56

Описание слайда:

Разбиением множества А называется совокупность непустых подмножеств A1, А2, …, Аn множества A, удовлетворяющих следующим требованиям: Разбиением множества А называется совокупность непустых подмножеств A1, А2, …, Аn множества A, удовлетворяющих следующим требованиям: А = A1 А2 … Аn; Ai Aj = Ø при i j. Подмножества Ai называются блоками разбиения.

Слайд 57

Описание слайда:

Диаграмма Венна разбиения множества А на пять блоков показана на рис. 4.4. Диаграмма Венна разбиения множества А на пять блоков показана на рис. 4.4. Заметим, что блоки изображены как лоскуты, не заходящие один на другой. Это связано с тем, что блоки разбиения не могут иметь общих элементов.

Слайд 58

Описание слайда:

Слайд 59

Описание слайда:

Как мы уже говорили, отношение эквивалентности R на множестве А задает на нем разбиение. Блоки разбиения при этом состоят из эквивалентных друг другу элементов. Мы сейчас докажем это утверждение. Но прежде определим класс эквивалентности Еx произвольного элемента х А как подмножество Еx = {z А: z R x }. Как мы уже говорили, отношение эквивалентности R на множестве А задает на нем разбиение. Блоки разбиения при этом состоят из эквивалентных друг другу элементов. Мы сейчас докажем это утверждение. Но прежде определим класс эквивалентности Еx произвольного элемента х А как подмножество Еx = {z А: z R x }. Докажем теорему.

Слайд 60

Описание слайда:

Теорема. Пусть R — отношение эквивалентности на непустом множестве А. Тогда различные классы эквивалентности определяют разбиение А. Теорема. Пусть R — отношение эквивалентности на непустом множестве А. Тогда различные классы эквивалентности определяют разбиение А. Доказательство. Доказательство состоит из четырех частей. 1) Сначала покажем, что классы эквивалентности являются непустыми подмножествами в А. По определению, Еx — подмножество в А. Кроме того, R — рефлексивное отношение, т.е. x R x. Следовательно, х Еx и Еx не пусто.

Слайд 61

Описание слайда:

2) Далее проверим, что из x R y вытекает равенство Еx = Еy. Предположим, что x R y и возьмем произвольный z Еx. Тогда z R x и x R y. Поскольку R — транзитивное отношение, мы получаем, что z R y. Иными словами, z Еy. Следовательно, Еx Еy. Аналогично можно показать, что Еy Еx, откуда Еx = Еy, что и требовалось. 2) Далее проверим, что из x R y вытекает равенство Еx = Еy. Предположим, что x R y и возьмем произвольный z Еx. Тогда z R x и x R y. Поскольку R — транзитивное отношение, мы получаем, что z R y. Иными словами, z Еy. Следовательно, Еx Еy. Аналогично можно показать, что Еy Еx, откуда Еx = Еy, что и требовалось.

Слайд 62

Описание слайда:

3) Теперь мы покажем, что классы эквивалентности удовлетворяют первому свойству разбиения, а именно, что А является объединением всех классов эквивалентности. Как уже отмечалось в первой части нашего доказательства, Еx — подмножество в A и поэтому объединение всех классов эквивалентности тоже будет подмножеством в A. 3) Теперь мы покажем, что классы эквивалентности удовлетворяют первому свойству разбиения, а именно, что А является объединением всех классов эквивалентности. Как уже отмечалось в первой части нашего доказательства, Еx — подмножество в A и поэтому объединение всех классов эквивалентности тоже будет подмножеством в A.

Слайд 63

Описание слайда:

В обратную сторону, если х А, то х Еx. В частности, х принадлежит объединению классов эквивалентности. Значит, и А является подмножеством нашего объединения. Следовательно, А совпадает с объединением классов эквивалентности. В обратную сторону, если х А, то х Еx. В частности, х принадлежит объединению классов эквивалентности. Значит, и А является подмножеством нашего объединения. Следовательно, А совпадает с объединением классов эквивалентности.

Слайд 64

Описание слайда:

4) И, наконец, в последней части мы покажем, что два разных класса эквивалентности не пересекаются. Этим мы проверим, что классы удовлетворяют второму свойству разбиения. Воспользуемся методом «от противного». Допустим, что Еx Еy Ø. Тогда найдется элемент z в A принадлежащий пересечению Еx Еy. Следовательно, z R x и z R y. Так как R — симметричное отношение, можно утверждать, что х R z и z R y. Ввиду транзитивности R, это влечет х R y. Значит, по второй части доказательства, Еx = Еy. 4) И, наконец, в последней части мы покажем, что два разных класса эквивалентности не пересекаются. Этим мы проверим, что классы удовлетворяют второму свойству разбиения. Воспользуемся методом «от противного». Допустим, что Еx Еy Ø. Тогда найдется элемент z в A принадлежащий пересечению Еx Еy. Следовательно, z R x и z R y. Так как R — симметричное отношение, можно утверждать, что х R z и z R y. Ввиду транзитивности R, это влечет х R y. Значит, по второй части доказательства, Еx = Еy.

Слайд 65

Описание слайда:

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

Слайд 66

Описание слайда:

Заметим, чтобы показать, что классы эквивалентности служат блоками разбиения множества А, мы использовали все определяющие свойства отношения эквивалентности: рефлексивность, симметричность и транзитивность. Заметим, чтобы показать, что классы эквивалентности служат блоками разбиения множества А, мы использовали все определяющие свойства отношения эквивалентности: рефлексивность, симметричность и транзитивность.

Слайд 67

Описание слайда:

Пример 4.10. Отношение R на вещественной прямой  задано условием: x R y, если и только если х - у — целое число. Докажите, что R — отношение эквивалентности и опишите классы эквивалентности, содержащие 0, и . Пример 4.10. Отношение R на вещественной прямой  задано условием: x R y, если и только если х - у — целое число. Докажите, что R — отношение эквивалентности и опишите классы эквивалентности, содержащие 0, и . Решение. Так как х - х = 0  для любого вещественного числа х, отношение R рефлексивно. Если х - у число целое, то и противоположное к нему у - х = -(х - у) является целым.

Слайд 68

Описание слайда:

Следовательно, R — симметричное отношение. Следовательно, R — симметричное отношение. Пусть х - у и у - z — целые числа. Тогда х - z = (х - у) + (у - z) — сумма целых чисел, т. е. целое число. Это означает, что R транзитивно. Итак, мы показали, что R рефлексивно, симметрично и транзитивно. Следовательно, R — отношение эквивалентности.

Слайд 69

Описание слайда:

Ранее были введены обозначения множеств: Ранее были введены обозначения множеств:  = { все десятичные дроби } — множество вещественных чисел;  = { 0, ±1, ±2, ±3, ... } — множество целых чисел.

Слайд 70

Описание слайда:

Класс эквивалентности Еx произвольного вещественного числа х определяется по формуле: Класс эквивалентности Еx произвольного вещественного числа х определяется по формуле: Еx = {z : z - x — целое число }. Поэтому, Е0 = ; Е½ = { z : z - ½ — целое число } = = Е = { z : z - — целое число }=

Слайд 71

Описание слайда:

Рефлексивное, транзитивное, но косо- симметричное отношение R на множестве А называется частичным порядком. Частичный порядок важен в тех ситуациях, когда мы хотим как-то охарактеризовать старшинство. Иными словами, решить - при каких условиях считать, что один элемент множества превосходит другой. Рефлексивное, транзитивное, но косо- симметричное отношение R на множестве А называется частичным порядком. Частичный порядок важен в тех ситуациях, когда мы хотим как-то охарактеризовать старшинство. Иными словами, решить - при каких условиях считать, что один элемент множества превосходит другой.

Слайд 72

Описание слайда:

( Отношение R на множестве А кососимметрично, если (х R y и y R x x = у) для всех x и у из А ). ( Отношение R на множестве А кососимметрично, если (х R y и y R x x = у) для всех x и у из А ). Примеры частичных порядков: « ≤ » на множестве вещественных чисел; « » на подмножествах универсального множества; «...делит...» на множестве натуральных чисел.

Слайд 73

Описание слайда:

Множества с частичным порядком принято называть частично упорядоченными множествами. Множества с частичным порядком принято называть частично упорядоченными множествами.

Слайд 74

Описание слайда:

Если R — отношение частичного порядка на множестве А, то при х у и x R y мы называем х предшествующим элементом или предшественником, а у — последующим. У произвольно взятого элемента у может быть много предшествующих элементов. Однако если х предшествует у, и не существует таких элементов z, для которых x R z и z R y, мы называем х непосредственным предшественником у и пишем х у (иногда говорят, что y покрывает x).

Слайд 75

Описание слайда:

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

Слайд 76

Описание слайда:

Пример 4.11. Дано, что отношение «... делитель ...» определяет частичный порядок на множестве А = {1, 2, 3, 6, 12, 18}. Составьте таблицу предшественников и непосредственных предшественников, после чего постройте соответствующую диаграмму Хассе. Пример 4.11. Дано, что отношение «... делитель ...» определяет частичный порядок на множестве А = {1, 2, 3, 6, 12, 18}. Составьте таблицу предшественников и непосредственных предшественников, после чего постройте соответствующую диаграмму Хассе. Решение. Таблица и диаграмма приведены ниже.

Слайд 77

Описание слайда:

Таблица 4.1 Таблица 4.1

Слайд 78

Описание слайда:

Рисунок 4.5. Диаграмма Хассе

Слайд 79

Описание слайда:

Линейным порядком на множестве А называется отношение частичного порядка, при котором из любой пары элементов можно выделить предшествующий и последующий. Линейным порядком на множестве А называется отношение частичного порядка, при котором из любой пары элементов можно выделить предшествующий и последующий. Примеры линейного порядка: « ≤ » на множестве вещественных чисел; лексикографическое упорядочение слов в словаре.

Слайд 80

Описание слайда:

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

Слайд 81

Описание слайда:

Частично упорядоченное множество из примера 4.11 обладает одним минимальным элементом, а именно, числом 1. С другой стороны, в нем есть два максимальных: 12 и 18. В этом множестве содержится несколько линейно упорядоченных подмножеств. Каждое из них соответствует цепочке ребер на диаграмме Хассе. Например, множество { 1, 2, 6, 18 } линейно упорядочено относительно отношения «...делитель...». Частично упорядоченное множество из примера 4.11 обладает одним минимальным элементом, а именно, числом 1. С другой стороны, в нем есть два максимальных: 12 и 18. В этом множестве содержится несколько линейно упорядоченных подмножеств. Каждое из них соответствует цепочке ребер на диаграмме Хассе. Например, множество { 1, 2, 6, 18 } линейно упорядочено относительно отношения «...делитель...».

Слайд 82

Описание слайда:

Краткое содержание главы Бинарным отношением между множествами А и В называется подмножество R в А В. Если А = В, то говорят, что R — отношение на А. Бинарное отношение между конечными множествами может быть описано на словах (при помощи подходящих предикатов), как множество упорядоченных пар, как орграф и с помощью матрицы.

Слайд 83

Описание слайда:

Отношение R на множестве А называется Отношение R на множестве А называется рефлексивным, если х R x для всех х А; симметричным, если x R y у R x для всех х, у А; кососимметричным, если (х R y и у R x х = у) для всех x, y A; транзитивным, если (x R y и y R z) x R z для всех x, у, z А.

Слайд 84

Описание слайда:

Отношение R* называют замыканием отношения R относительно свойства Р, если Отношение R* называют замыканием отношения R относительно свойства Р, если R* обладает свойством Р; R R*: R* — подмножество любого другого отношения, содержащего R и обладающего свойством Р.

Слайд 85

Описание слайда:

Рефлексивное, симметричное и транзитивное отношение R на множестве А называется отношением эквивалентности. Классом эквивалентности элемента х А является подмножество Рефлексивное, симметричное и транзитивное отношение R на множестве А называется отношением эквивалентности. Классом эквивалентности элемента х А является подмножество Еx = {z A: z R x}.

Слайд 86

Описание слайда:

Разбиение множества А представляет собой совокупность подмножеств А1, А2, ..., Аn в A, удовлетворяющих требованиям: Разбиение множества А представляет собой совокупность подмножеств А1, А2, ..., Аn в A, удовлетворяющих требованиям: А = А1 A2 … Аn и Ai Aj = Ø при i j. Подмножества Ai из предыдущего определения называются блоками разбиения. Если R — отношение эквивалентности на А, то различные классы эквивалентности образуют разбиение А.

Слайд 87

Описание слайда:

Рефлексивное, кососимметричное и транзитивное отношение R на множестве А называется частичным порядком. Множества, на которых определено такое отношение, в свою очередь, называются частично упорядоченными множествами. Рефлексивное, кососимметричное и транзитивное отношение R на множестве А называется частичным порядком. Множества, на которых определено такое отношение, в свою очередь, называются частично упорядоченными множествами. Линейный порядок на множестве — это такой частичный порядок, при котором можно сравнить любую пару элементов.

Слайд 88

Описание слайда:

Если R — отношение частичного порядка на множестве А и x R y, х у, то х называется предшественником у. В том случае, когда х предшествует у и нет такого элемента z, для которого х R z и z R у, то говорят, что х — непосредственный предшественник у. Последний факт обозначают так: х у. Если R — отношение частичного порядка на множестве А и x R y, х у, то х называется предшественником у. В том случае, когда х предшествует у и нет такого элемента z, для которого х R z и z R у, то говорят, что х — непосредственный предшественник у. Последний факт обозначают так: х у. Диаграмма Хассе представляет собой граф, чьи вершины изображают элементы частично упорядоченного множества. В том случае, когда х у, вершина х располагается непосредственно под вершиной у и соединяется с ней ребром.

Слайд 89

Описание слайда:

Системы управления базами данных Данные, хранящиеся в компьютере, называются базой данных. Программы, с помощью которых пользователь извлекает информацию из базы данных или вносит в нее изменения, называются системами управления базами данных (СУБД).

Слайд 90

Описание слайда:

Данные в компьютере, как правило, организованы в виде таблиц. Например, табл. 4.2 содержит информацию о группе студентов: личный номер студента, фамилию, пол, дату рождения, семейное положение и адрес. В табл. 4.3 занесена информация об успеваемости некоторых студентов по отдельным курсам. Данные в компьютере, как правило, организованы в виде таблиц. Например, табл. 4.2 содержит информацию о группе студентов: личный номер студента, фамилию, пол, дату рождения, семейное положение и адрес. В табл. 4.3 занесена информация об успеваемости некоторых студентов по отдельным курсам.

Слайд 91

Описание слайда:

Таблица 4.2. Т1 = Персональные данные Таблица 4.2. Т1 = Персональные данные

Слайд 92

Описание слайда:

Таблица 4.3. Т2 = Успеваемость Таблица 4.3. Т2 = Успеваемость

Слайд 93

Описание слайда:

Эти таблицы составят основу для наших обсуждений, хотя и не представляют практического интереса. Например, проблемы при работе с табл. 4.2 могут возникнуть при попытке извлечь информацию о двух различных Смитах, а в табл. 4.2 отсутствует детальная информация о некоторых из студентов, появляющихся в табл. 4.3. Эти таблицы составят основу для наших обсуждений, хотя и не представляют практического интереса. Например, проблемы при работе с табл. 4.2 могут возникнуть при попытке извлечь информацию о двух различных Смитах, а в табл. 4.2 отсутствует детальная информация о некоторых из студентов, появляющихся в табл. 4.3.

Слайд 94

Описание слайда:

Строки таблицы с n колонками, помеченными множествами А1, А2, ..., Аn можно представить как подмножество в прямом произведении А1 А2 ... Аn. Строки образуют список из n элементов, по одному из каждого Аi а вся таблица представляет собой парное отношение. Строки таблицы с n колонками, помеченными множествами А1, А2, ..., Аn можно представить как подмножество в прямом произведении А1 А2 ... Аn. Строки образуют список из n элементов, по одному из каждого Аi а вся таблица представляет собой парное отношение.

Слайд 95

Описание слайда:

Например, табл. 4.3 можно рассматривать как подмножество Т2 в А1 А2 А3 А4 А5, где А1 — множество фамилий студентов, а А2 = А3 = А4 = А5 = {отл, хор, удовл, неуд}. Один из элементов этого пятинарного отношения — строка (Джонс, хор, удовл, хор, неуд), в которой записаны оценки Джонса, полученные им за четыре предмета. Например, табл. 4.3 можно рассматривать как подмножество Т2 в А1 А2 А3 А4 А5, где А1 — множество фамилий студентов, а А2 = А3 = А4 = А5 = {отл, хор, удовл, неуд}. Один из элементов этого пятинарного отношения — строка (Джонс, хор, удовл, хор, неуд), в которой записаны оценки Джонса, полученные им за четыре предмета.

Слайд 96

Описание слайда:

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

Слайд 97

Описание слайда:

Операция проект формирует новую таблицу из определенных столбцов старой. Например, проект(Т1, {Фамилия, Адрес}) создает табл. 4.4. Операция проект формирует новую таблицу из определенных столбцов старой. Например, проект(Т1, {Фамилия, Адрес}) создает табл. 4.4.

Слайд 98

Описание слайда:

Таблица 4.4. ТЗ = проект(Т1, {Фамилия, Адрес}) Таблица 4.4. ТЗ = проект(Т1, {Фамилия, Адрес})

Слайд 99

Описание слайда:

Задача 1. Найти проект (Т2, {Фамилия, Основы матем., Дискр. матем.}). Задача 1. Найти проект (Т2, {Фамилия, Основы матем., Дискр. матем.}). Решение. Смотри табл. 4.5 Таблица 4.5

Слайд 100

Описание слайда:

Операция соединение объединяет две таблицы в большую, выписывая в одну строку информацию, соответствующую общему атрибуту. Предположим, что R и S — отношения, представленные двумя таблицами, причем R — подмножество в прямом произведении А1 … Аm В1 … Вn, a S — в прямом произведении А1 … Аm С1 … Ср. Операция соединение объединяет две таблицы в большую, выписывая в одну строку информацию, соответствующую общему атрибуту. Предположим, что R и S — отношения, представленные двумя таблицами, причем R — подмножество в прямом произведении А1 … Аm В1 … Вn, a S — в прямом произведении А1 … Аm С1 … Ср.

Слайд 101

Описание слайда:

В этом случае общие атрибуты представлены множествами А1, А2,…, Аm. Соединение R и S — это подмножество в А1 … Аm В1 … Вn С1 … Ср, состоящее из элементов вида (a1, a2, …, аm, b1, b2, …, bm, c1, c2, ..., ср), где (a1, ..., аm, b1, ..., bm) лежит в R, а (a1, ..., аm, c1, ..., ср) — в подмножестве S. В этом случае общие атрибуты представлены множествами А1, А2,…, Аm. Соединение R и S — это подмножество в А1 … Аm В1 … Вn С1 … Ср, состоящее из элементов вида (a1, a2, …, аm, b1, b2, …, bm, c1, c2, ..., ср), где (a1, ..., аm, b1, ..., bm) лежит в R, а (a1, ..., аm, c1, ..., ср) — в подмножестве S.

Слайд 102

Описание слайда:

Например, соединение(ТЗ, Т2) дает табл. 4.6. Например, соединение(ТЗ, Т2) дает табл. 4.6. Таблица 4.6

Слайд 103

Описание слайда:

Операция выбор отбирает строки таблицы, удовлетворяющие подходящему критерию. Например, выбор(Т1, Пол = М и Семейное положение = Женат) верстает табл. 4.7. Операция выбор отбирает строки таблицы, удовлетворяющие подходящему критерию. Например, выбор(Т1, Пол = М и Семейное положение = Женат) верстает табл. 4.7. Таблица 4.7.

Слайд 104

Описание слайда:

Задача 2. Найдите выбор(Т2, Дискр. матем. = отл). Задача 2. Найдите выбор(Т2, Дискр. матем. = отл). Решение. В новую таблицу (табл. 4.8) войдут только те строки таблицы Т2, у которых в столбце, помеченном Дискр. математика будет стоять «отл». Таблица 4.8

Слайд 105

Описание слайда:

Как иллюстрируют следующие задачи, комбинация всех трех операций позволит нам извлекать различную информацию из баз данных. Как иллюстрируют следующие задачи, комбинация всех трех операций позволит нам извлекать различную информацию из баз данных. Задача 3. Найдите таблицу, которая получится в результате операций: R1 = проект(Т2, {Фамилия, Прогр., Вычисл. системы}); R2 = выбор(R1, Вычисл. системы=отл или Прогр.=отл);

Слайд 106

Описание слайда:

Решение. Во-первых, все столбцы таблицы Т2, отличные от Фамилия, Прогр. и Вычисл. системы, удаляются. В результате получится таблица R1. Затем, в новой таблице нужно оставить только те строки, в которых есть хотя бы одна оценка «отл», а остальные отбросить. Это даст нам требуемую таблицу R2 (табл. 4.9). Решение. Во-первых, все столбцы таблицы Т2, отличные от Фамилия, Прогр. и Вычисл. системы, удаляются. В результате получится таблица R1. Затем, в новой таблице нужно оставить только те строки, в которых есть хотя бы одна оценка «отл», а остальные отбросить. Это даст нам требуемую таблицу R2 (табл. 4.9). Таблица 4.9

Слайд 107

Описание слайда:

Задача 4. Найдите результат действий следующих операций: Задача 4. Найдите результат действий следующих операций: R1 = выбор(Т1, пол = Ж); R2 = проект(Т2,{Фамилия, Дискр. матем.}); R3 = соединение(R1, R2). Решение. Прежде всего выберем из таблицы Т1 строки, соответствующие студенткам, и составим из них таблицу R1. Затем удалим из Т2 все столбцы, кроме двух выбранных, и получим таблицу R2. Общим атрибутом таблиц R1 и R2 является Фамилия. Соединив R1 и R2, получим искомую таблицу (табл. 4.10).

Слайд 108

Описание слайда:

Таблица 4.10. Таблица 4.10.

Слайд 109

Описание слайда:

Задача 5. Выпишите последовательность операций (выбор, проект и соединение) для определения имен и адресов всех тех студенток, которые получили оценку не ниже «хор» по обоим предметам: основы математики и дискретная математика. Задача 5. Выпишите последовательность операций (выбор, проект и соединение) для определения имен и адресов всех тех студенток, которые получили оценку не ниже «хор» по обоим предметам: основы математики и дискретная математика.

Слайд 110

Описание слайда:

Решение. Одна из последовательностей операций выглядит следующим образом. Решение. Одна из последовательностей операций выглядит следующим образом. R1 = выбор(Т1, пол = Ж); R2 = выбор(Т2, Дискр. матем. = «отл» или Дискр. матем. = «хор»); R3 = выбор (R2, Основы матем. = «отл» или Основы матем. = «хор»); R4 = соединение(R1, R3); R = проект(R4,{Фамилия, Адрес}).

Теги Математические отношения

Похожие презентации